Séminaire Lotharingien de Combinatoire, B49g (2003), 46 pp.

Roman König

Endliche Hüllensysteme und ihre Implikationenbasen

Zusammenfassung. Für jede natürliche Zahl n wird induktiv ein Kontext konstruiert, dessen Begriffe genau die Hüllensysteme auf einer n-elementigen Menge beschreiben. Die Begriffe bestehen aus Paaren, deren Umfang das Hüllensystem und deren Inhalt die zugehörige Menge aller respektierten Implikationen ist. Darauf basierend werden zwei Algorithmen zur Berechnung einer vollständigen Implikationenmenge eines gegebenen Kontexts angegeben. Der erste liefert die Wertetabelle des Abschlussoperators, der zu dem Begriffsverband des gegebenen Kontexts gehört und simultan die Inhalte dieses Begriffsverbandes, ohne den Abschlussoperator explizit zu benutzen. Der zweite liefert zu jedem System irreduzibler Implikationen ein äquivalentes Teilsystem; angewandt auf die kanonische Antikette liefert dieser eine Implikationenbasis, die ,,kompakter'' als die sogenannte Duquenne-Guigues-Basis ist. Im Anhang wird ein Beispiel durchgeführt und gezeigt, wie man umgekehrt den Teilkontext eines gegebenen Kontexts findet, der durch die Gültigkeit zusätzlicher Implikationen beschrieben wird. Für den besonders einfachen Spezialfall unärer Implikationen ergibt sich als Anwendung ein Konstruktionsverfahren für den Kongruenzenverband einer algebraischen Struktur.


Received: November 6, 2002. Revised: June 25, 2003, and August 5, 2003. Accepted: December 13, 2003.

The following versions are available: