Sminaire Lotharingien de Combinatoire 49 (2003), Article B49g

Endliche Hüllensysteme und ihre Implikationenbasen

Roman König^{∗}

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.

∗Adresse: Universität Erlangen-Nürnberg, Institut für Informatik III, Martensstraße 3, D - 91058 Erlangen. koenig@informatik.uni-erlangen.de

Inhaltsverzeichnis

1 Einleitung 2

2 Grundlagen 4

3 Implikationen 6

4 Die Kontexte ℍ und 𝔹 9 4.1 Induktive Definition des Kontexts ℍ_{n} . . . . . . . . . . . . . 9 4.2 Induktive Definition des Kontexts 𝔹_{n} . . . . . . . . . . . . . . 13

5 Anwendungen 17 5.1 Berechnung der Wertetabelle . . . . . . . . . . . . . . . . . . . 19 5.2 Ein Algorithmus zur Bestimmung der Wertetabelle . . . . . . 22 5.3 Ein kanonisches vollständiges Implikationensystem . . . . . . . 23 5.4 Ein Algorithmus zur Bestimmung einer irredundanten Teilmenge 30

6 Abschließende Bemerkungen 33

A Anhang 36 A.1 Ein Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 A.2 Konstruktion von Teilsystemen . . . . . . . . . . . . . . . . . 39

A.2.1 Allgemeine Teilsysteme . . . . . . . . . . . . . . . . . 39 A.2.2 Unterverbände . . . . . . . . . . . . . . . . . . . . . . 41

1 Einleitung

Die begriffliche Wissensverarbeitung stellt starke Hilfsmittel zur Verfügung, um große Datenmengen zu analysieren. Gleichzeitig ist die formale Begriffsanalyse mit Hilfe der Begriffsverbände eine schöne Anwendung der Verbandstheorie. Die grundlegenden Definitionen und Tatsachen dieser Theorie setzen wir als bekannt voraus, insbesondere die Begriffe „(formaler) Kontext”, „(formaler) Begriff”, „Begriffsverband” und deren Zusammenhänge und Eigenschaften. Standardtext ist das Buch von B. Ganter und R. Wille [3], aus dem wir alle hier nicht explizit definierten Begriffe und Bezeichnungen übernehmen.

Besondere Bedeutung für die Datenanalyse haben Implikationen. Sie sind die Grundlage der Merkmalslogik und dienen sowohl dem Studium der Eigenschaften, die ein gegebener Kontext hat, als auch zur Beschreibung oder Konstruktion eines Kontextes, der gewisse Eigenschaften haben soll.

Aus diesen Gründen sind Implikationen bisher meist nur im Zusammenhang mit einem konkret gegebenen Kontext gesehen und untersucht worden. Die bekannten Algorithmen zum Auffinden seiner Begriffe und einer Implikationenmenge, die den gegebenen Kontext und damit auch seinen Begriffsverband adäquat beschreibt, sind deshalb aufwändig und liefern im Allgemeinen Implikationenmengen, die noch vereinfacht werden können.

Hier nehmen wir einen übergeordneten Standpunkt ein und betrachten in den Kapiteln 3 und 4 Implikationen über einer abstrakten Merkmalmenge, ohne schon von einem konkreten Kontext zu sprechen. Das hat den Vorteil, dass wir durch eine einfache induktive Definition angeben können, welche Mengen T eine Implikation U → V respektieren und von welchen Implikationen eine gegebene Menge respektiert wird. Die einzige Einschränkung, die wir dabei fordern, ist die Endlichkeit von T, U und V. Als Ergebnis erhalten wir einen Kontext ℍ als Limes einer Folge ℍ_{n} von endlichen Kontexten, der alle Informationen über alle endlichen Hüllensysteme und damit über alle endlichen Begriffsverbände enthält.

Endliche Hüllensysteme sind vielfach studiert worden. Um Implikationenbasen oder andere vollständige Implikationenmengen zu finden, werden dabei aus dem Hüllensystem geeignete Mengen abgeleitet (quasi- oder pseudoabgeschlossene Mengen), die zur Definition von Implikationen benutzt werden können. Details findet man z.B. in [2] und [6].

Einen Überblick über die Eigenschaften des Verbands aller Hüllensysteme auf einer endlichen Menge gibt [1]. Dort findet man auch ein ausführliches Literaturverzeichnis zum Thema endliche Hüllensysteme. Implizit spielt der Kontext ℍ_{n} zwar hier stets eine Rolle (siehe auch die Fußnote auf p.266 in [1]), aber er wird nicht konstruiert.

Die Definition des Kontexts ℍ_{n} erscheint in [4]; verwendet wird er dort aber nicht explizit, sondern als ein Hilfsmittel, um Eigenschaften der abgeschlossenen Implikationenmengen von Teilkontexten eines gegebenen Kontexts zu studieren.

Durch die Angabe eines induktiven Konstruktionsverfahrens für den Kontext ℍ_{n} im Kapitel 4 wird es möglich, die Menge Imp(𝕂) aller Implikationen, die in einem gegebenen Kontext 𝕂 mit n Merkmalen gelten, effektiv anzugeben, ohne das Hüllensystem, das durch 𝕂 beschrieben wird, zu kennen. Durch vorhergehende Spaltenreduktion des Kontexts ℍ_{n} zu 𝔹_{n} kann auch die Menge aller irreduziblen Implikationen (das sind die mit einelementiger Konsequenz) effektiv berechnet werden. Dadurch werden in den Anwendungen interessierende Fragen algorithmisch behandelbar. Erste Beispiele dafür sind in den Anhängen A.1 und A.2 ausgeführt.

2 Grundlagen

In diesem Abschnitt werden einige bekannte Tatsachen wiederholt, um später darauf referieren zu können und um die Notation zu fixieren. Der Leser, der mit der Theorie der Begriffsverbände vertraut ist, kann diesen Abschnitt ohne Verlust überspringen und nur bei Bedarf nachlesen.

Es sei 𝕂 = (G, M, I) ein Kontext. Für A ⊆ G sei

A^{I} := {m ∈ M | für alle g ∈ A ist (g, m) ∈ I}

und für B ⊆ M sei

B^{I} := {g ∈ G | für alle m ∈ B ist (g, m) ∈ I}.

Wenn keine Zweifel über den gerade benutzten Kontext zu befürchten sind, schreiben wir einfach A′ statt A^{I} und B′ statt B^{I}. Umgekehrt verwenden wir zur eindeutigen Kennzeichnung, in welchem Kontext wir uns gerade befinden, auch die Schreibweise A^{𝕂} statt A^{I} und B^{𝕂} statt B^{I}. Dies ist besonders angebracht, wenn 𝕂 Teilkontext eines Kontexts 𝕃 = (H, N, J) ist, wenn also G ⊆ H, M ⊆ N und I = J ∩ (G × M) ist.

Für spätere Anwendungen ist es nützlich, einen Kontext 𝕂 als Paar von adjungierten Abbildungen

\begin{matrix}g ↦ g^{𝕂} & m ↦ m^{𝕂} \\ G ⟶ 𝔓(M) & M ⟶ 𝔓(G) \end{matrix}

zu sehen^{1}. 𝕂 heißt bereinigt, wenn diese beiden Abbildungen injektiv sind. Ist die erste injektiv, dann heißt 𝕂 gegenstands- oder zeilenbereinigt, ist die zweite injektiv, dann heißt 𝕂 merkmals- oder spaltenbereinigt.

Da die eine dieser Abbildungen die andere eindeutig bestimmt (vgl. z.B. [3], Kap. 0.4), genügt eine von beiden zur Beschreibung eines Kontexts. Wir wählen die Abbildung g ↦ g^{𝕂} und nennen diese wieder^{2} 𝕂, also

𝕂 : G ⟶ 𝔓(M), g ↦ 𝕂(g) := g^{𝕂}

1Tatsächlich sind diese Abbildungen die Restriktionen der beiden zueinander adjungierten Abbildungen 𝔓(G) ⟶ 𝔓(M) und 𝔓(M) ⟶ 𝔓(G) jeweils auf die Menge der einelementigen Teilmengen.

2Es entspricht gängiger Praxis, Relationen sowohl als Teilmengen von G × M, als auch als Abbildungen G → 𝔓(M) zu betrachten.

Man beachte, dass für Teilmengen A von G die Merkmalmengen A^{𝕂} = {m ∈ M | für alle g ∈ A ist (g, m) ∈ I} und 𝕂(A) = {𝕂(g) | g ∈ A} = {g^{𝕂} | g ∈ A} im Allgemeinen verschieden sind.

Definition 2.1. Es seien der Kontext 𝕂 = (G, M, I) und ein zweiter Kontext 𝕊 = (𝔓(M), X, J) gegeben. Die Komposition 𝕂 ∘ 𝕊 von 𝕂 und 𝕊 definieren wir durch

(𝕂 ∘ 𝕊)(g) := 𝕊(𝕂(g)) = 𝕊(g^{𝕂})

für alle g ∈ G. Damit ist 𝕂 ∘ 𝕊 der Kontext 𝕂 ∘ 𝕊 = (G, X, J̃) mit

(g, x) ∈ J̃ ⟺ (𝕂(g), x) ∈ J

𝕂 ∘ 𝕊 ist isomorph zu dem Teilkontext von 𝕊, der bestimmt wird durch die Zeilen von 𝕂, wobei Zeilen mehrfach auftreten können, wenn 𝕂 nicht bereinigt ist.

Die Elemente (A, B) mit A′ = B und B′ = A heißen Begriffe des Kontexts 𝕂 und bestehen aus dem Begriffsumfang A und dem Begriffsinhalt B. Die Menge

\underline{𝔅}(𝕂) = \{(A, B) | A ⊆ G, B ⊆ M, A′ = B, B′ = A\}

mit der Ordnung

(A, B) ≤ (C, D) ⟺ A ⊆ C ( ⟺ B ⊇ D)

ist der zugehörige Begriffsverband. \underline{𝔅}(𝕂) ist ein vollständiger Verband. Für Teilmengen B ⊆ \underline{𝔅}(𝕂) werden Infimum und Supremum folgendermaßen berechnet:

\begin{aligned}⋀ B = ( ⋂_{(A,B)∈B} A, ( ⋃_{(A,B)∈B} B)′′) & = ( ⋂_{(A,B)∈B} A, ( ⋂_{(A,B)∈B} A)′) \\ & = (( ⋃_{(A,B)∈B} B)′, ( ⋃_{(A,B)∈B} B)′′) \end{aligned}  (1)

und

\begin{aligned}⋁ B = (( ⋃_{(A,B)∈B} A)′′, ⋂_{(A,B)∈B} B) & = (( ⋂_{(A,B)∈B} B)′, ⋂_{(A,B)∈B} B) \\ & = (( ⋃_{(A,B)∈B} A)′′, ( ⋃_{(A,B)∈B} A)′) \end{aligned}  (2)

Insbesondere ist der Verband \underline{𝔅}(𝕂) isomorph zum Verband aller Begriffsumfänge und antiisomorph zum Verband aller Begriffsinhalte. Diese Verbände sind jeweils durch Inklusion (auf 𝔓(G) bzw. 𝔓(M)) geordnet und Hüllensysteme auf den jeweiligen Mengen. Die abgeschlossenen Gegenstandsmengen (= Begriffsumfänge) sind die Mengen A′′ mit A ⊆ G, die abgeschlossenen Merkmalmengen (= Begriffsinhalte) sind die B′′ mit B ⊆ M.

Das Hüllensystem aller Begriffsumfänge wird erzeugt von den Merkmalsumfängen {m}′ mit m ∈ M, das aller Begriffsinhalte von den Gegenstandsinhalten {g}′ mit g ∈ G. Es ist zwar üblich, diese Bezeichnungen zu m′ und g′ zu verkürzen, im Folgenden wird es aber gelegentlich nützlich sein, Elemente und einelementige Teilmengen einer Menge genau auseinanderzuhalten.

Wenn der Kontext 𝕂 bereinigt ist, insbesondere wenn er bis auf eine Vollzeile oder eine Vollspalte reduziert ist, sind alle ({g}, {g}′) mit g ∈ G und alle ({m}′, {m}) mit m ∈ M Begriffe.

Hüllensysteme lassen sich bekanntlich adäquat beschreiben durch Abschlussoperatoren. Ein Abschlussoperator auf einer Menge M ist dabei eine Abbildung X ↦ \overline{X} von 𝔓(M) in sich mit den Eigenschaften^{3}

X ⊆ \overline{X}
aus X ⊆ \overline{Y} folgt \overline{X} ⊆ \overline{Y}

(3)

für alle X, Y ∈ 𝔓(M). Die Beziehung zwischen Hüllensystem und Abschlussoperator ist dabei noch viel natürlicher, als auf den ersten Blick sichtbar: Hüllensystem und zugehöriger Abschlussoperator sind Umfang und Inhalt eines Begriffs im Begriffsverband eines geeigneten Kontexts, der im Kapitel 4 konstruiert wird.

3 Implikationen

Es sei eine endliche Menge M vorgegeben, die wir in den Anwendungen als Merkmalmenge eines gegebenen Kontexts interpretieren werden, die aber zunächst keine Semantik hat. Für Teilmengen U und V der Menge M nennt man das Paar (U, V) eine Implikation, geschrieben U → V; man sagt, eine Teilmenge T von M respektiert die Implikation (U, V), wenn gilt: U ⊈ T oder V ⊆ T, abgekürzt durch

T ⊢ U → V : ⟺ (U ⊆ T ⟹ V ⊆ T).

3Man sieht ohne Schwierigkeit, dass dieses Axiomensystem äquivalent ist zu dem üblichen:

X ⊆ Y ⇒ \overline{X} ⊆ \overline{Y}, sowie X ⊆ \overline{X} und \overline{\overline{X}} = \overline{X}

Implikationen der Form U → V mit V ⊆ U ⊆ M nennen wir trivial. Triviale Implikationen werden von jeder Teilmenge T von M respektiert.

Die Potenzmenge 𝔓(M) nehmen wir als Gegenstandsmenge, die Produktmenge 𝔓(M)^{2} = 𝔓(M) × 𝔓(M) aller Implikationen nehmen wir als Merkmalmenge des Kontexts

ℍ(M) = (𝔓(M), 𝔓(M)^{2}, ⊢).

Die Begriffe des dadurch definierten Begriffsverbands \underline{𝔅}(ℍ(M)) sind die Paare (ℌ, F) mit ℌ ⊆ 𝔓(M) und F ⊆ 𝔓(M)^{2}, die die Eigenschaft haben, dass

ℌ^{⊢} := {(U, V) | für alle S ∈ ℌ ist S ⊢ U → V } = F

und

F^{⊢} := {S | für alle (U, V) ∈ F ist S ⊢ U → V } = ℌ.

Jeder Begriffsumfang ℌ dieses Kontexts ist eine Teilmenge von 𝔓(M), also ein Mengensystem auf M. Da der Durchschnitt von Mengen, die ein System von Implikationen respektieren, dieses System wieder respektiert, ist ℌ unter beliebigen Durchschnitten abgeschlossen. Daher ist jeder Begriffsumfang ein Hüllensystem auf M. Umgekehrt ist jedes Hüllensystem ℌ auf M ein Begriffsumfang, nämlich der von ℌ^{⊢}; denn einerseits ist ℌ ist ein Mengensystem auf M, das alle Implikationen in ℌ^{⊢} respektiert, andererseits ist ℌ^{⊢⊢} das kleinste Mengensystem mit dieser Eigenschaft.

Also ist der Begriffsverband \underline{𝔅}(ℍ(M)) isomorph zum Verband aller Hüllensysteme auf M, geordnet durch Inklusion. Dabei heißt ℌ ⊆ 𝔊: Jede Teilmenge von M, die in ℌ abgeschlossen ist, ist auch in 𝔊 abgeschlossen.

Der Verband \underline{𝔅}(ℍ(M)) ist vollständig und isomorph zu dem Hüllensystem auf der Menge 𝔓(M), das erzeugt wird von den Merkmalsumfängen \{U → V \}^{⊢} mit (U, V) ∈ 𝔓(M)^{2}; andererseits ist \underline{𝔅}(ℍ(M)) antiisomorph zu dem Hüllensystem auf der Menge 𝔓(M)^{2} aller Implikationen, das erzeugt wird von den Gegenstandsinhalten {S}^{⊢} mit S ∈ 𝔓(M). Die erzeugende Operation ist dabei der Durchschnitt von Implikationenmengen, also Teilmengen von 𝔓(M)^{2} (d.h. Elemente sind Paare von Teilmengen von M). Die so entstehenden Implikationenmengen nennen wir abgeschlossen. Daher ist für jedes System von abgeschlossenen Implikationenmengen F_{t} mit t ∈ T auch ⋂_{t∈T} F_{t} wieder abgeschlossen, d.h. von der Form 𝔖^{⊢} für ein geeignetes 𝔖 ⊆ 𝔓(M). Sind speziell die F_{t} von der Form F_{t} = {S_{t}}^{⊢} mit S_{t} ∈ 𝔓(M), so gilt

⋂_{t∈T} F_{t} = ⋂{{S_{t}}^{⊢} | t ∈ T } = (⋃{{S_{t}} | t ∈ T })^{⊢} = {S_{t} | t ∈ T }^{⊢}.

Wegen Gleichung (2) gilt dann:

⋁_{t∈T}(F_{t}^{⊢}, F_{t}) = ({S_{t}|t ∈ T }^{⊢⊢}, {S_{t}|t ∈ T }^{⊢}).

Jeden Begriffsinhalt F = ℌ^{⊢} des Kontexts ℍ(M) kann man als einen Abschlussoperator betrachten, wenn man ihn als eine Abbildung F : 𝔓(M) ⟶ 𝔓(M) interpretiert, indem man für X ∈ 𝔓(M) setzt:

F(X) := ⋃{V |U → V ∈ F, U ⊆ X}

Aus der Eigenschaft X ⊢ {x} → {x} für alle X ∈ 𝔓(M) und alle x ∈ M folgt

X ⊆ F(X),

und unmittelbar aus der Definition der Abbildung F ergibt sich

wenn X ⊆ F(Y), dann ist auch F(X) ⊆ F(Y)

für alle X, Y ∈ 𝔓(M). Damit sind die Eigenschaften (3) erfüllt und die Abbildung F ist ein Abschlussoperator. Dies zeigt, dass jeder Begriff im Verband \underline{𝔅}(ℍ(M)) als Umfang ein Hüllensystem und als Inhalt den zugehörigen Abschlussoperator hat.

Wir sagen für zwei Implikationenmengen F und G, dass G aus F folgt und schreiben F ⊧ G, wenn jeder Gegenstand in 𝔓(M), der F respektiert, auch G respektiert, also wenn F^{⊢} ⊆ G^{⊢} gilt. Wenn sowohl F ⊧ G, als auch G ⊧ F gilt, nennen wir F und G äquivalent und schreiben F ≡ G. Es gilt F ⊧ G genau dann, wenn F ≡ F ∪ G.

Beispiel. Es gelten für alle Teilmengen U, V, W, Z von M die folgenden Beziehungen:

\begin{matrix}∅ & ⊧ \{U → U\} \\ \{U → V \} & ⊧ \{U ∪ W → V \} \\ \{U → V, V ∪ W → Z\} & ⊧ \{U ∪ W → Z\}. \end{matrix}  (4)

Die Beziehungen (4) heißen Armstrongaxiome.

Dass wir weiter oben die Begriffsinhalte in \underline{𝔅}(ℍ(M)) als abgeschlossen bezeichnet haben, ist dadurch gerechtfertigt, dass sie genau die Implikationenmengen F sind, die im folgenden Sinne abgeschlossen sind:

Satz 3.1. Eine Menge F von Implikationen ist genau dann von der Form {S_{t} | t ∈ T }^{⊢} mit S_{t} ⊆ M, wenn sie die Bedingung erfüllt:

Wenn die Implikationen der linken Seite einer der in (4) genannten Beziehungen zu F gehören, dann auch die auf der rechten Seite.

Beweis. Siehe [3], p.81 und die dort angegebene Literatur.

Für Implikationenmengen gelten die folgenden weiteren Beziehungen:

{U → V } ≡ {U → U ∪ V }  (5)
{U → V, U → W } ≡ {U → V ∪ W }  (6)
{U → V } ≡ {W → V |U ⊆ W }  (7)
{U → V, U ∪ V ∪ W → Z} ≡ {U → V, U ∪ W → Z}.  (8)

Äquivalente Implikationenmengen definieren im Begriffsverband \underline{𝔅}(ℍ(M)) denselben Begriffsumfang, also dasselbe Hüllensystem. Jede dieser Implikationenmengen heißt vollständig für dieses Hüllensystem. Wenn eine Implikationenmenge minimal ist (bezüglich Inklusion in 𝔓(𝔓(M) × 𝔓(M)) ) unter allen Implikationenmengen, die ein gegebenes Hüllensystem definieren, so heißt diese eine Implikationenbasis^{4} für dieses Hüllensystem.

4 Die Kontexte ℍ und 𝔹

4.1 Induktive Definition des Kontexts ℍ_{n}

Wir bezeichnen mit 2 die geordnete Menge {0, 1} mit 2 Elementen, wobei 0 < 1, und identifizieren die Potenzmenge einer gegebenen Menge M mit 2^{M}. ℍ(M) hat dann die Gegenstandsmenge 2^{M} und die Merkmalmenge 2^{M} ×2^{M}.

Wir betrachten nun den Kontext ℍ(M) für eine n−elementige Menge M (n ≥ 0). Der Kontext ℍ(M) hat dann 2^{n} Gegenstände und 2^{n} · 2^{n} Merkmale. Unter den Merkmalen liefert zunächst nach Äquivalenz (5) jede Implikation der Form U → V im Kontext ℍ(M) dieselbe Spalte wie U → U ∪ V, also genügen die 3^{n} Spalten von ℍ(M) mit Merkmalen U → V, für die U ⊆ V ist. Den Teilkontext von ℍ(M) mit dieser Merkmalmenge und voller Gegenstandsmenge 2^{n} nennen wir ℍ_{n}.

Für n = 0 sind Gegenstands- und Merkmalmenge einelementig. Zur Konstruktion von ℍ_{n+1} benutzen wir außer ℍ_{n} noch einen zweiten Kontext 𝕃_{n}, für den 𝕃_{0} ebenfalls einelementige Gegenstands- und Merkmalmenge hat.

4In der Literatur findet man den Begriff „Implikationenbasis” auch als Bezeichnung für jede Implikationenmenge, die ein gegebenes Hüllensystem definiert.

Satz 4.1. Für die Kontexte ℍ_{n} gilt:

ℍ_{0} = ×, 𝕃_{0} = ∅

ℍ_{n+1} = \begin{matrix}ℍ_{n} & 𝕃_{n} & × \\ ℍ_{n} & ℍ_{n} & ℍ_{n} \end{matrix} und 𝕃_{n+1} = \begin{matrix}𝕃_{n} & 𝕃_{n} & × \\ 𝕃_{n} & 𝕃_{n} & 𝕃_{n} \end{matrix} (n ≥ 0) (9)

Dabei steht, wie üblich, bei bekannten Gegenstands- und Merkmalmengen × für einen Kontext, in dem jeder Gegenstand mit jedem Merkmal inzidiert, während ∅ für den entsprechenden Kontext ohne Inzidenzen steht.

Beweis. Offenbar beschreibt ℍ_{0} den Fall n = 0, denn ∅ ⊢ ∅ → ∅.

Nun sei der Kontext ℍ_{n} bereits bekannt und ∗ ein neues Element, das an die Menge M adjungiert wird. Die Gegenstandsmenge 2^{n+1} von ℍ_{n+1} entsteht dann durch Erweiterung von 2^{n} um die Elemente X + {∗} mit X ∈ 2^{n}.

Die Merkmalmenge von ℍ_{n+1} entsteht wegen der Eigenschaft (5) durch Erweiterung der Merkmalmenge von ℍ_{n} um die Elemente U → V + {∗} und U + {∗} → V + {∗}, wobei U → V ein Merkmal in ℍ_{n} ist, d.h. U ⊆ V ∈ 2^{n}. Für alle X ∈ 2^{n} und Implikationen U → V von ℍ_{n} gilt: X ⊢ U → V in ℍ_{n} ⟺ X ⊢ U → V in ℍ_{n+1}. Daher ist ℍ_{n} ein Teilkontext von ℍ_{n+1}.

Offenbar ist für alle X ∈ 2^{n} und U ⊆ V ∈ 2^{n}

X ⊢ U → V ⟺ X + {∗} ⊢ U → V,

was die erste Spalte in der Definition von ℍ_{n+1} erklärt.

Für Gegenstände X + {∗} von ℍ_{n+1} gilt

X + {∗} ⊢ U → V ⟺ X + {∗} ⊢ U → V + {∗}
⟺ X + {∗} ⊢ U + {∗} → V + {∗},

was die untere Zeile in der Definition von ℍ_{n+1} erklärt.

Es bleibt also zu untersuchen, welche der Implikationen, die zu ℍ_{n+1}, aber nicht zu ℍ_{n} gehören, die Gegenstände X von ℍ_{n} respektieren. Die Implikationen U + {∗} → V + {∗} werden von allen diesen X respektiert, weil U + {∗} ⊈ X.

Also ist als Letztes zu zeigen, dass der Fall U → V + {∗} durch den Kontext 𝕃_{n} beschrieben wird.

Die Gegenstandsmenge von 𝕃_{n} ist die von ℍ_{n}, die Merkmalmenge ist {U → V +{∗} | U ⊆ V ∈ 2^{n}}. Zunächst gilt also 𝕃_{0} = ∅; denn ∅ ⊬ ∅ → {∗}.

Es sei nach Induktionsannahme bereits gezeigt, dass 𝕃_{n} diesen Fall beschreibt, also 𝕃_{n} = (2^{n}, {U → V + {∗} | U ⊆ V ∈ 2^{n}}, ⊢).

𝕃_{n+1} ist ein Teilkontext von ℍ_{n+2}. Der Übergang von n+1 nach n+2 werde durch Adjunktion eines weiteren Punktes ∗∗ an die zugrundeliegende Menge M + {∗} bewerkstelligt. Die Merkmale von 𝕃_{n+1} sind die U → V + {∗∗}, wobei U → V Merkmal von ℍ_{n+1} ist, also können wir sie wieder einteilen in die drei Blöcke U → V +{∗∗}, U → V +{∗}+{∗∗}, U +{∗} → V +{∗}+{∗∗}, wobei jetzt U → V ein Merkmal in ℍ_{n} ist, also U ⊆ V ∈ 2^{n}.

Die Gegenstände des Kontexts 𝕃_{n+1} enthalten jeweils das Element ∗∗ nicht; wir teilen sie wieder ein in die Gegenstände, die ∗ nicht als Element enthalten, das sind die X ∈ 2^{n} und die, die ∗ enthalten, das sind die X + {∗} mit X ∈ 2^{n}.

Für diejenigen Gegenstände, die ∗ nicht enthalten, gilt:

X ⊢ U → V + {∗∗}
⟺ X ⊢ U → V + {∗} + {∗∗}
⟺ X + {∗} ⊢ U → V + {∗} + {∗∗}
⟺ X ⊢ U → V + {∗}

Dies besagt, dass 𝕃_{n} als Teilkontext zweimal in der ersten Zeile und einmal in der zweiten Zeile der Definition von 𝕃_{n+1} auftaucht. Für Gegenstände, die ∗ enthalten, gilt folgendes

X + {∗} ⊢ U → V + {∗∗}
⟺ X + {∗} ⊢ U → V + {∗} + {∗∗}
⟺ X + {∗} ⊢ U + {∗} + {∗∗} → V + {∗} + {∗∗}

Dies garantiert, dass in der zweiten Zeile der Definition von 𝕃_{n+1} dreimal der gleiche Teilkontext erscheint. Schließlich gilt wegen U + {∗} ⊈ X in 𝕃_{n+1} stets X ⊢ U + {∗} → V + {∗} + {∗∗}.

Dies bestätigt den Aufbau von 𝕃_{n+1} aus 𝕃_{n}, und damit ist gezeigt, dass ℍ_{n+1} aus ℍ_{n} induktiv so aufgebaut wird, wie in (9) beschrieben.

Da der Kontext ℍ_{n+1} stets eine Erweiterung des Kontexts ℍ_{n} ist, können wir

ℍ := lim_{n≥0} ℍ_{n}

bilden. Der Kontext ℍ beschreibt alle Hüllensysteme auf endlichen Mengen. Die ersten Kontexte ℍ_{n} haben demnach die folgende Form:

ℍ_{1} = \begin{matrix}× & & × \\ × & × & × \end{matrix} , ℍ_{2} = \begin{matrix}× & & × & & & × & × & × & × \\ × & × & × & & & & × & × & × \\ × & & × & × & & × & × & & × \\ × & × & × & × & × & × & × & × & × \end{matrix}

Die Gegenstands- und Merkmalmengen sind

2^{1} und {∅ → ∅, ∅ → {1}, {1} → {1}}

bzw.2^{2} und

{∅ → ∅, ∅ → {1}, {1} → {1}} ∪ {∅ → {∗}, ∅ → {1, ∗}, {1} → {1, ∗}}
∪ {{∗} → {∗}, {∗} → {1, ∗}, {1, ∗} → {1, ∗}}.

Bemerkung. Der Kontext ℍ_{n} ist weder bereinigt, noch reduziert, denn er enthält z.B. viele Vollspalten.

Satz 4.2. Für alle n ∈ ℕ gilt:

1. Der Teilkontext von ℍ_{n}, der durch Weglassen der Zeile des Gegenstands M entsteht, ist zeilenbereinigt.

2. Je zwei Gegenstandsinhalte S^{⊢} und T^{⊢} von Gegenständen S und T in ℍ_{n} mit S, T ≠ M sind entweder gleich oder unvergleichbar.

Beweis. 1. Es gilt S^{⊢} ≠ T^{⊢} für je zwei voneinander verschiedene Gegenstände S, T ∈ ℍ_{n}; denn für T ≠ S ist o.B.d.A. T \ S ≠ ∅ und es gilt für jedes x ∈ T \ S: T ⊢ ∅ → {x}, aber S ⊬ ∅ → {x}.

2. Wenn T^{⊢} ⊆ S^{⊢} gilt, dann gilt auch

T ⊢ U → V ⟹ S ⊢ U → V für alle U ⊆ V ⊆ M

Falls T ≠ S ist, kann nach 1. nicht T \ S ≠ ∅ sein, weil sonst T^{⊢} ⊈ S^{⊢} wäre, also folgt T ⫋ S, und es muss ein x ∈ S \T geben; außerdem gibt es wegen S ≠ M ein y ∈ M \ S. Für dieses gilt dann T ⊢ {x} → {x, y} und S ⊬ {x} → {x, y}, was der Eigenschaft T^{⊢} ⊆ S^{⊢} widerspricht. Also folgt aus T^{⊢} ⊆ S^{⊢} schon T^{⊢} = S^{⊢} und damit sind alle Gegenstandsbegriffe, außer dem des Gegenstands M, ∨−irreduzibel.

Bemerkung. Der Kontext 𝕃_{n} hat als letzte Zeile stets eine Leerzeile und der Kontext ℍ_{n} hat als letzte Zeile stets eine Vollzeile.

Korollar 4.3. Der Kontext ℍ_{n} ist bis auf die letzte Zeile zeilenreduziert.

4.2 Induktive Definition des Kontexts 𝔹_{n}

Wegen der Äquivalenz (6) ist in ℍ_{n} jedes Merkmal reduzibel, das nicht von der Form U → V mit |V | = |U| + 1 ist. Wir bezeichnen die Merkmalmenge {U → V | U, V ∈ 2^{n}, |V | = |U| + 1} mit dem Symbol X_{n} und den Kontext (2^{n}, X_{n}, ⊢) mit 𝔹_{n}. 𝔹_{n} ist die Einschränkung des Kontexts ℍ_{n} auf die Merkmalmenge X_{n}.

Satz 4.4. Die Kontexte 𝔹_{n} genügen der folgenden Rekursion:

𝔹_{1} = × , 𝔸_{1} = ×

𝔹_{n+1} = \begin{matrix}𝔹_{n} & 𝔸_{n} & × \\ 𝔹_{n} & × & 𝔹_{n} \end{matrix} und 𝔸_{n+1} = 𝔸_{n} ×_{𝔸_{n} 𝔸_{n}} (n ≥ 1)  (10)

Beispiel. Nach dieser Regel ergeben sich die ersten Kontexte zu

𝔹_{2} = \begin{aligned}& & × & × \\ × & & & × \\ & × & × \\ × & × & × & × \end{aligned} , 𝔸_{2} = \begin{aligned}× & × & × \\ & × & × \\ × & & × \end{aligned}

𝔹_{3} = \begin{aligned}& & × & × & & × & × & × & × & × & × & × \\ × & & & × & & & × & × & × & × & × & × \\ & × & × & & & × & & × & × & × & × & × \\ × & × & × & × & & & & & × & × & × & × \\ & & × & × & × & × & × & × & & & × & × \\ × & & & × & × & × & × & × & × & & & × \\ & × & × & & × & × & × & × & & × & × \\ × & × & × & × & × & × & × & × & × & × & × & × \end{aligned} , 𝔸_{3} = \begin{aligned}× & × & × & × & × & × & × \\ & × & × & × & × & × & × \\ × & & × & × & × & × & × \\ & & & × & × & × & × \\ × & × & × & & × & × & × \\ & × & × & & & × & × \\ × & & × & & × & & × \end{aligned}

𝔸_{n} hat 2^{n} Gegenstände und 2^{n} Merkmale^{5}, 𝔹_{n} hat n2^{n−1} Merkmale. Die letzte Zeile von 𝔹_{n} ist nach wie vor eine Vollzeile, die letzte Zeile von 𝔸_{n} eine Leerzeile. Außerdem ist die erste Spalte von 𝔸_{n} stets eine Leerspalte^{6}.

5Man vergleiche die Rekursion für 𝔸_{n} mit der Rekursion in [3], p.50, für den freien vollständig distributiven Verband F CD(n) über n Elementen:

\underline{𝔅}(𝔸_{n}) ≅ F CD(n)

Über den Verband F CD(n) und besonders F CD(4) siehe auch Beispiel 14, p.216, in [3].

Bezeichnung. Für x ∈ M \ U schreiben wir U → {x} oder (U, x) statt U → U ∪ {x} .

Beweis des Satzes 4.4. Der Fall n = 1 wird offenbar durch 𝔹_{1} beschrieben und 𝔸_{1} ist der passende Teilkontext von 𝔹_{2}.

Die Gegenstandsmenge 2^{n+1} von 𝔹_{n+1} entsteht aus der von 𝔹_{n} durch Hinzunahme der Mengen X+{∗}, wobei ∗ der neue Punkt ist und X ∈ 2^{n}, die Merkmalmenge X_{n+1} von 𝔹_{n+1} entsteht aus X_{n}, indem man diese vergrößert um die Implikationen U → {∗} mit U ∈ 2^{n} und U + {∗} → {x}, wobei U → {x} ∈ X_{n}.

𝔹_{n+1} ist Erweiterung von 𝔹_{n}, denn für alle X ∈ 2^{n}, U → {x} ∈ X_{n} ist

X ⊢ U → {x} in 𝔹_{n} ⟺ X ⊢ U → {x} in 𝔹_{n+1}.

Für alle U ∈ 2^{n} und für die Gegenstände X ∈ 2^{n} ist X + {∗} ⊢ U → {∗} und X ⊢ U + {∗} → {x}, und es gilt

X ⊢ U → {x} ⟺ X + {∗} ⊢ U → {x} ⟺ X + {∗} ⊢ U + {∗} → {x}.

Es bleibt der Fall

X ∈ 2^{n}, U → {∗} mit U ∈ 2^{n}

zu untersuchen, von dem wir zeigen, dass 𝔸_{n} ihn beschreibt.

𝔸_{n+1} ist ein Teilkontext von 𝔹_{n+2}. Der Übergang von n+1 nach n+2 werde wieder durch Adjunktion eines weiteren Punktes ∗∗ und Erweiterung der Gegenstandsmenge von 𝔹_{n+1} um die X + {∗∗} für Gegenstände X von 𝔹_{n+1} bewerkstelligt. Die Merkmale von 𝔸_{n+1} sind die U → {∗∗} mit U ∈ 2^{n+1}. Sie sind also von der Form U → {∗∗} oder U + {∗} → {∗∗} mit U ∈ 2^{n}.

Die Gegenstände des Kontexts 𝔸_{n+1} enthalten jeweils das Element ∗∗ nicht; wir teilen sie wieder ein in die Gegenstände, die ∗ als Element enthalten und die, die ∗ nicht enthalten.

Für diejenigen Gegenstände X, die ∗ nicht enthalten, und für U ∈ 2^{n} gilt

X ⊢ U → {∗∗} ⟺ X +{∗} ⊢ U → {∗∗} ⟺ X +{∗} ⊢ U +{∗} → {∗∗}.

Da für diese X und U auch

X ⊢ U → {∗∗} ⟺ X ⊢ U → {∗}

6Der Kontext 𝔹_{3} erscheint in [4], p.20, mit einigen Fehlern in der Zeile des Gegenstands {a, c}. Richtig muss es heißen: {a, c} ⊢ {c} → {a}, {a, c} ⊬ {c} → {b}, {a, c} ⊢ {a, b} → {c}.

gilt, erkennt man, dass in 𝔸_{n+1} dreimal der Kontext 𝔸_{n} auftaucht, während für alle diese X und für U ∈ 2^{n} stets X ⊢ U + {∗} → {∗∗} gilt.

Damit ist gezeigt, dass 𝔹_{n+1} aus 𝔹_{n} induktiv so aufgebaut wird, wie in (10) beschrieben.

Entsprechend kann man wieder definieren

𝔹 := lim_{n≥0} 𝔹_{n}

und erhält erneut einen Kontext, der alle Informationen über alle endlichen Hüllensysteme enthält.

Bemerkung. Nun ist zwar klar, dass 𝔹_{n} aus ℍ_{n} durch Reduzieren entsteht, es könnte aber noch reduzible Merkmale in 𝔹_{n} geben. Dass dies nicht der Fall ist, sieht man, wenn man die Pfeilrelation ↗ benutzt^{7} und in die Tabellen der Kontexte 𝔹_{n} und 𝔸_{n} einträgt und die so entstehenden Tabellen 𝔹̂_{n} bzw. 𝔸̂_{n} nennt. Man erhält dann die folgende Rekursion:

𝔹̂_{1} = \begin{matrix}↗ \\ × \end{matrix} , 𝔸̂_{1} = \begin{aligned}↗ & × \\ & ↗ \end{aligned}

𝔹̂_{n+1} = \begin{matrix}𝔹̂_{n} & 𝔸̂_{n} & × \\ 𝔹_{n} & × & 𝔹̂_{n} \end{matrix} und 𝔸̂_{n+1} = 𝔸̂_{n} ×_{𝔸_{n} 𝔸̂_{n}} (n ≥ 1)  (11)

Für n = 2, 3 berechnet man die Kontexte:

𝔹̂_{2} = \begin{aligned}↗ & ↗ & × & × \\ × & & ↗ & × \\ & × & × & ↗ \\ × & × & × & × \end{aligned} , 𝔸̂_{2} = \begin{aligned}↗ & × & × & × \\ & ↗ & × & × \\ & × & ↗ & × \\ & & & ↗ \end{aligned}

𝔹̂_{3} = \begin{aligned}↗ & ↗ & × & × & ↗ & × & × & × & × & × & × & × \\ × & & ↗ & × & & ↗ & × & × & × & × & × & × \\ & × & × & ↗ & & × & ↗ & × & × & × & × & × \\ × & × & × & × & & & & ↗ & × & × & × & × \\ & & × & × & × & × & × & × & ↗ & ↗ & × & × \\ × & & & × & × & × & × & × & × & & ↗ & × \\ & × & × & & × & × & × & × & & × & × & ↗ \\ × & × & × & × & × & × & × & × & × & × & × & × \end{aligned} , 𝔸̂_{3} = \begin{aligned}↗ & × & × & × & × & × & × & × \\ & ↗ & × & × & × & × & × & × \\ & × & ↗ & × & × & × & × & × \\ & & & ↗ & × & × & × & × \\ & × & × & × & ↗ & × & × & × \\ & & × & × & & ↗ & × & × \\ & × & & × & & × & ↗ & × \\ & & & & & & & ↗ \end{aligned}

7vgl. [3], p.28, wo die Pfeilrelationen definiert sind.

Aus der rekursiven Konstruktion von 𝔹_{n} und 𝔸_{n} sieht man:

1. Die letzte Zeile von 𝔹_{n} ist stets eine Vollzeile;

2. Die letzte Zeile von 𝔸_{n} ist stets eine Leerzeile;

3. 𝔹_{n} enthält keine Vollspalte;

4. Jede Spalte von 𝔹̂_{n} enthält genau einen Pfeil.

Für einen Gegenstand g und ein Merkmal m eines Kontexts 𝕂 heißt die Relation g ↗ m bekanntlich: m′ ist maximal unter allen Spalten des Kontexts, die den Gegenstand g nicht enthalten. Mit den obigen Eigenschaften 1. bis 3. erkennt man, wie sich die Pfeilrelation aus 𝔹_{n} und 𝔸_{n} nach 𝔹_{n+1} fortsetzt. Ferner ist die Pfeilrelation für 𝔹_{1} und für 𝔸_{1} offenbar so, wie in 𝔹̂_{1} und 𝔸̂_{1} angegeben. Somit enthält jede Spalte von 𝔹̂_{n+1} wieder genau einen Pfeil, also sind alle Merkmale von 𝔹_{n+1} wieder irreduzibel. Die Implikationen in X_{n} nennen wir aus diesem Grunde irreduzibel oder reduziert.^{8}

Da die Kontexte ℍ_{n} in Korollar 4.3 bereits als fast-zeilenreduziert erkannt sind, folgt

Korollar 4.5. Die Kontexte 𝔹_{n} sind bis auf eine Vollzeile reduziert.

Beweis. Beim Spaltenreduzieren von ℍ_{n} können keine neuen Abhängigkeiten zwischen den Zeilen entstehen, denn im Beweis von Satz 4.2 wird nur von irreduziblen Implikationen Gebrauch gemacht. Die Merkmalmenge von 𝔹_{n} enthält alle solchen Implikationen.

Der Aufbau von 𝔹_{n} nach (10) hat nach [3], Satz 7, und Kap. 1.4 unmittelbar zur Folge:

Korollar 4.6. Der Begriffsverband \underline{𝔅}(𝔹_{n+1}) ist ein subdirektes Produkt der Verbände \underline{𝔅}(𝔹_{n}) und \underline{𝔅}(𝔸_{n}) × \underline{𝔅}(𝔹_{n}).

Einerseits bilden die Gegenstandsbegriffe, also die Zeilen von 𝔹_{n+1} (ohne die letzte Zeile), ein supremum-dichtes Erzeugendensystem für (die Begriffsinhalte von) \underline{𝔅}(𝔹_{n+1}), andererseits sind die Merkmalbegriffe, also die Spalten von 𝔹_{n+1} ein infimum-dichtes Erzeugendensystem für (die Begriffsumfänge von) \underline{𝔅}(𝔹_{n+1}).

8Irreduzible Implikationen schreiben wir je nach Bedarf in der Form U → {x} oder U → x, wobei U eine Merkmalmenge und x ein Merkmal mit x ∉ U ist.

5 Anwendungen

Die Konstruktionen in Kapitel 4 benutzen wir, um für einen beliebigen Kontext 𝕂 sowohl eine Implikationenbasis, als auch gleichzeitig den zugehörigen Begriffsverband durch Angabe der Menge aller Begriffsinhalte zu erzeugen. Solange wir uns nur für den Begriffsverband und die Implikationen von 𝕂 interessieren, können wir stets annehmen, dass 𝕂 reduziert, also insbesondere bereinigt ist.

Es sei ein Kontext 𝕂 = (G, M, I) gegeben. Der Kontext 𝕂 erfüllt die Implikation U → V, wenn für jeden Gegenstand g ∈ G gilt: {g}′ ⊢ U → V. Die Menge aller Implikationen, die 𝕂 erfüllt, heiße Imp(𝕂). Die Menge Imp(𝕂) charakterisiert den Kontext 𝕂 in der Weise, dass sie das Hüllensystem ℌ aller Begriffsinhalte von 𝕂 beschreibt. Dieses ist anti-isomorph zum Verband \underline{𝔅}(𝕂).

Das Hüllensystem ℌ wird definiert durch einen Abschlussoperator^{9}. Die Beschreibung dieses Abschlussoperators geschieht durch Angabe einer Menge F von Implikationen, die zur Menge Imp(𝕂) äquivalent ist. Dabei berechnet sich der Abschluss Y einer Menge X ⊆ M, indem eine aufsteigende Folge

X_{0} ⊆ X_{1} ⊆ …

von Teilmengen von M folgendermaßen konstruiert wird:

• X_{0} = X;

• Ist X_{i} bereits konstruiert und U → V ∈ F eine Implikation mit U ⊆ X_{i}, dann ist X_{i+1} = X_{i} ∪ V;

• Y = ⋃_{i∈ℕ} X_{i} .

Das Verfahren bricht ab, wenn F geeignete Zusatzvoraussetzungen erfüllt, insbesondere aber, wenn 𝕂 endlich ist. Dies ist in unseren Anwendungen stets der Fall.

Definition 5.1. Eine Menge F von Implikationen heißt redundant, wenn F zu einer ihrer echten Teilmengen äquivalent ist. Wir nennen eine Implikation U → V ∈ F entbehrlich, wenn F ≡ F \ {U → V } gilt, ansonsten unentbehrlich.

9Wir bezeichnen den zu ℌ gehörigen Abschlussoperator mit dem Symbol H, sodass H(U) = ⋂{V ∈ ℌ|U ⊆ V } ist.

Die Menge Imp(𝕂) enthält sehr viel Redundanz. Zum Beispiel enthält Imp(𝕂) zu jeder Implikation U → V nach (6) und (7) sowohl die Implikation U → Z mit Z ⊆ V als auch die Implikation W → V mit U ⊆ W. Die Menge Imp(𝕂) selbst ist daher für die meisten Anwendungen ungeeignet, weil sie viel zu groß ist. Um Redundanz zu beseitigen, sind die Eigenschaften (4) bis (8) zulässige Hilfsmittel.

Eine (bezüglich Inklusion) minimale Menge F ⊆ Imp(𝕂) von Implikationen mit der Eigenschaft F^{⊢} = Imp(𝕂)^{⊢} ist die sogenannte Duquenne-Guigues-Basis. Für den Kontext 𝕂 ist sie definiert durch

{P → P′′ | P ist Pseudoinhalt von 𝕂}

Nach [3, Hilfssatz 25, p.84] kann es keine äquivalente Implikationenmenge mit weniger Elementen geben. In diesem Sinne ist sie „einfach”. Sie ist aber i.A. noch nicht die einfachste, denn es kann mehrere äquivalente Implikationenmengen mit minimaler Anzahl von Elementen geben.

Beispiel. Die Menge

D = {{2} → {2, 4}, {3} → {1, 3}, {1, 3, 4} → {1, 2, 3, 4}, {1, 2, 4} → {1, 2, 3, 4}}

ist die Duquenne-Guigues-Basis des Kontexts

\begin{aligned}& 1 & 2 & 3 & 4 \\ a & × & & × \\ b & & × & & × \\ c & × & & & × \end{aligned}

also irredundant, aber nach (8) äquivalent zu

D̃ = {{2} → {2, 4}, {3} → {1, 3}, {3, 4} → {1, 2, 3, 4}, {1, 2} → {1, 2, 3, 4}}

und nach dem ersten Anschein wird man die zweite Menge als „einfacher” als die erste bezeichnen.

Eine noch einfachere zu D äquivalente Menge erhält man, wenn man D zunächst mittels (5) umschreibt in

D = {{2} → {4}, {3} → {1}, {1, 3, 4} → {2}, {1, 2, 4} → {3}}

und dann (8) anwendet. Man erhält auf diese Weise die Menge

˜D̃ = {{2} → {4}, {3} → {1}, {3, 4} → {2}, {1, 2} → {3}}

welche auch noch einfacher als die entsprechend umgeschriebene Menge

D̃ = {{2} → {4}, {3} → {1}, {3, 4} → {1, 2}, {1, 2} → {3, 4}}

ist. ˜ D̃ ist unverkürzbar und damit die ökonomischste Form zur Beschreibung der Begriffsinhalte des gegebenen Kontexts.

Um Implikationenmengen vergleichbar zu machen, ist es nützlich, Implikationen stets in der Form U → V mit V ≠ ∅ und U ∩ V = ∅ zu schreiben. Dann ist für eine Formelmenge F die natürliche Zahl

ω(F) := ∑_{U→V ∈F} |U| · |V |

ein Maß für F, das invariant ist unter Umformungen nach (6), falls V und W disjunkt sind, und das triviale Implikationen nicht zählt. Nach dieser Bewertung ist tatsächlich ˜ D̃ die einfachste der drei Mengen D, D̃, ˜ D̃.

Das Beispiel zeigt, dass die Bedeutung des Begriffs „Basis” als minimales Erzeugendensystem davon abhängt, welche „elementaren” Implikationen man zur Beschreibung von Implikationenmengen verwendet. Bei Beschränkung auf irreduzible Implikationen kann man, wie gesehen, möglicherweise einfachere Basen als die Duquenne-Guiges-Basis finden.

Eine weitere vollständige Implikationenmenge ist die Wertetabelle eines Abschlussoperators. Sie ist zwar im Allgemeinen keine Implikationenbasis, denn jede nicht abgeschlossene Menge kommt genau einmal auf der linken Seite einer Implikation vor, aber die Berechnung des Abschlusses einer Menge U ist besonders einfach. Sie geschieht in einem Schritt durch Anwedung genau einer Implikation, nämlich U → U′′.

5.1 Berechnung der Wertetabelle

Aus dem Kontext ℍ lässt sich mit wenig Aufwand die Wertetabelle für den Abschlussoperator H gewinnen, sofern der gegebene Kontext 𝕂 = (G, M, I) endlich ist. Dann benötigen wir zur Untersuchung von 𝕂 ein endliches Anfangsstück ℍ_{n} von ℍ, wobei n = |M| ist. Wir identifizieren M mit der Menge {n, …, 1}.

Die Elemente der Gegenstandsmenge von ℍ_{n} sind Teilmengen U von M. Wir codieren sie als 0, 1−Vektoren λ(U) = (λ(U)_{n−1}, λ(U)_{n−2}, …, λ(U)_{0}) der Länge n, also als Elemente von 2^{n}. λ(U) heißt der charakteristische Vektor für U und stellt eine Binärzahl

|λ(U)|_{2} = ∑_{0≤i<n} λ(U)_{i} · 2^{i}

dar. Entsprechend ist die Menge 2^{n} auf zwei Weisen geordnet:

U ⊆ V ⟺ λ(U) ≤_{n} λ(V),

wobei ≤_{n} die n−fache Produktordnung von 0 < 1 ist, und

U ⪯ V ⟺ |λ(U)|_{2} ≤ |λ(V)|_{2}.

⪯ ist die lexikographische Ordnung auf 2^{n}. Wir identifizieren jedes U mit seinem charakteristischen Vektor, so dass gilt U ⊆ V ⟺ U ≤_{n} V und U ≤_{n} V ⟹ U ⪯ V.

Implikationen schreiben wir in der Form U → V mit U ∩ V = ∅ und codieren sie als Vektoren κ(U, V) = (x_{n−1}, x_{n−2}, …, x_{0}) ∈ 3^{n} der Länge n über der Menge 3 = {0, 1, 2} auf folgende Weise:

x_{i} = \{ \begin{matrix}2, & falls i + 1 ∈ U \\ 1, & falls i + 1 ∈ V \\ 0, & sonst \end{matrix}

Dann kann man κ(U, V) berechnen durch κ(U, V) = 2λ(U) + λ(V). Beispielsweise wird die Implikation {3, 4, 6} → {1, 5} codiert durch den Vektor x = (2, 1, 2, 2, 0, 1), also durch die Zahl 640 = |x|_{3} = ∑_{0≤i≤5} x_{i}·3^{i}. Dies liefert eine Bijektion zwischen der Menge aller Implikationen mit n Symbolen und der Menge 3^{n} = {0, 1, …, 3^{n} − 1} mit zwei verschiedenen Ordnungen:

(U, V) ≤ (X, Y) ⟺ κ(U, V) ≤_{n} κ(X, Y),

wobei wieder ≤_{n} die n−fache Produktordnung von 0 < 1 < 2 ist, und

(U, V) ⪯ (X, Y) ⟺ |κ(U, V)|_{3} ≤ |κ(X, Y)|_{3}.

Wie vorher ist ⪯ die lexikographische Ordnung auf 3^{n} bezüglich 0 < 1 < 2 und es gilt (U, V) ≤ (X, Y) ⟹ (U, V) ⪯ (X, Y).

Indem wir Gegenstandsmenge und Merkmalmenge jeweils mit ⪯ ordnen, erhalten wir für n = 3 den Kontext ℍ_{3}

0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2
000 × ×  × × × ×  ×  × × × × × × × × × × × × ×
001 × × ×  × × ×  × × × × × × × × × × × ×
010 × × × × × ×  ×  ×  × × × × × × × × × ×
011 × × × × × × × × ×  × × × × × × × × ×
100 × ×  × × × × × ×  × × × × × ×  × × × ×
101 × × ×  × × × × × ×  × × × × × ×  × × ×
110 × × × × × × × × × × × × × × × × × ×
111 × × × × × × × × × × × × × × × × × × × × × × × × × × ×

und 𝕃_{3} ergibt sich zu

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2
000  ×  × × × ×  ×  × × × × × × × × × × × × ×
001  × × ×  × × × × × × × × × × × ×
010  ×  ×  ×  ×  ×  × × × × × × × × × ×
011  × × × × × × × × ×
100  ×  × × × ×  ×  × × × ×  ×  × × × ×
101  × × ×  × × ×  × × ×
110  ×  ×  ×  ×  ×  ×  ×  ×  ×

111

Die Inzidenzrelation von ℍ_{n} bzw. von 𝕃_{n} beschreiben wir durch Angabe der Zeilen des jeweiligen Kontexts als 0, 1−Vektoren oder Wörter der Länge 3^{n} und der Spalten des jeweiligen Kontexts als 0, 1−Vektoren oder Wörter der Länge 2^{n}.

Um für den gegebenen Kontext 𝕂 = (G, M, I) mit |M| = n die Teilmenge von Imp(𝕂) zu berechnen, die die Wertetabelle des zugehörigen Abschlussoperators darstellt, untersuchen wir den Kontext 𝕂 ∘ ℍ_{n} (siehe Definition 2.1 für die Definition der Komposition). Wir berechnen zunächst Imp(𝕂), also alle Implikationen, die von allen Gegenstandsinhalten von 𝕂 respektiert werden.

Für einen Gegenstand g ∈ G sei sein Gegenstandsinhalt g′ = (g_{n}, …, g_{1}) ∈ 2^{n} als der entsprechende 0, 1−Vektor der Länge n ≥ 1 gegeben, das ist die Zeile von g im Kontext 𝕂. Um die Schreibweise zu vereinfachen, kürzen wir für 1 ≤ k ≤ n die letzten k Komponenten von (g_{n}, …, g_{1}) ab zu g_{[k]}, so dass sich g_{[n]} = (g_{n}, g_{[n−1]}) schreiben lässt. Den Vektor der Länge n, dessen Einträge sämtlich gleich 1 sind, bezeichne 1^{n}, und auch sonst lassen wir auf der rechten Seite der folgenden Definitionen möglichst viele Klammern weg. Für n = 1 gilt

(g_{[1]})^{ℍ_{1}} = \{ \begin{matrix}1, 0, 1 & falls g_{1} = 0 \\ 1, 1, 1 & falls g_{1} = 1 \end{matrix} und (g_{[1]})^{𝕃_{1}} = \{ \begin{matrix}0, 0, 1 & falls g_{1} = 0 \\ 0, 0, 0 & falls g_{1} = 1 \end{matrix}

und für n > 1 ist

(g_{[n]})^{ℍ_{n}} = \{ \begin{matrix}(g_{[n−1]})^{ℍ_{n−1}}, (g_{[n−1]})^{𝕃_{n−1}}, 1^{3^{n−1}} & falls g_{n} = 0 \\ (g_{[n−1]})^{ℍ_{n−1}}, (g_{[n−1]})^{ℍ_{n−1}}, (g_{[n−1]})^{ℍ_{n−1}} & falls g_{n} = 1 \end{matrix}

sowie

(g_{[n]})^{𝕃_{n}} = \{ \begin{matrix}(g_{[n−1]})^{𝕃_{n−1}}, (g_{[n−1]})^{𝕃_{n−1}}, 1^{3^{n−1}} & falls g_{n} = 0 \\ (g_{[n−1]})^{𝕃_{n−1}}, (g_{[n−1]})^{𝕃_{n−1}}, (g_{[n−1]})^{𝕃_{n−1}} & falls g_{n} = 1 \end{matrix}

Der 0, 1−Vektor (g_{[n]})^{ℍ_{n}} ∈ 2^{3^{n}} ist die Indikatorfunktion ε : 3^{n} ⟶ 2 der Menge F = {g′}^{ℍ_{n}} aller Implikationen, die von dem Gegenstandsinhalt g′ respektiert werden, d.h. ε^{−1}(1) = {g′}^{ℍ_{n}}. Wir bezeichnen daher die Komponente x von (g_{[n]})^{ℍ_{n}} mit (g_{[n]})^{ℍ_{n}}(x). Eine 1 an der Stelle x mit 0 ≤ x < 3^{n} codiert die Implikation, die durch den Vektor y = (x_{n−1}, x_{n−2}, …, x_{0}) mit x = |y|_{3} = ∑_{0≤i<n} x_{i} · 3^{i} dargestellt wird. y ist also die Ternärdarstellung von x. Zu einem solchen Vektor y sei ŷ derjenige 0, 2−Vektor der Länge n, der dadurch entsteht, dass in y jede 1 durch eine 0 ersetzt wird.

Die Indikatorfunktion von Imp(𝕂) können wir nun bestimmen, indem wir das komponentenweise Produkt aller Vektoren (g_{[n]})^{ℍ_{n}} mit g ∈ G berechnen. Sei ε_{𝕂} diese Indikatorfunktion, also

ε_{𝕂}(x) = 1 ⟺ für alle g ∈ G ist (g_{[n]})^{ℍ_{n}}(x) = 1

Die Abbildung ε_{𝕂} stellen wir dar als die aufsteigende Folge aller natürlichen Zahlen x < 3^{n} mit ε_{𝕂}(x) = 1. Es gilt stets ε_{𝕂}(0) = 1 und ε_{𝕂}(3^{n} − 1) = 1.

5.2 Ein Algorithmus zur Bestimmung der Wertetabelle

Aus der Folge ε_{𝕂} liefert der folgende Algorithmus die Wertetabelle des Abschlussoperators H:

Algorithmus 5.2. Gegeben sei eine Folge 0 = x_{1} < x_{2} < … < x_{k} = 3^{n} −1.

1. H := ∅ , L := ∅, K := \{(\underbrace{2, 2, …, 2}_{n−mal})\};

2. Für i = k − 1, k − 2, …, 1

y := die Ternärdarstellung von x_{i}

Falls y ∉ {0, 2}^{n} und ŷ ∉ L, dann H := H ∪ {y} und L := L ∪ {ŷ}

Falls y ∈ {0, 2}^{n} und y ∉ L, dann K := K ∪ {y}

3. Ausgabe H, K

Beobachtungen. 1. K und L enthalten 0, 2−Vektoren. Wenn man sie als 0, 1−Vektoren interpretiert, ersieht man aus der Konstruktion sofort: Zu jedem Zeitpunkt gilt K ∩ L = ∅.

2. Wenn die Ausgangsfolge die charakteristische Folge einer Implikationenmenge der Form Imp(𝕂) ist, dann gilt nach Ausführung des Algorithmus K ∪ L ≅ 2^{n}.

Außerdem gilt:

Satz 5.3. K ist die Menge der abgeschlossenen Teilmengen des Hüllensystems, das sind die Fixpunkte des Abschlussoperators, H ist die Menge der nichttrivialen Implikationen U → V, für die U ∪ V abgeschlossen ist.

Beweis. Zu jedem Zeitpunkt gilt:

1. y ∉ {0, 2}^{n} codiert eine nichttriviale Implikation U → V und ŷ codiert deren linke Seite U.

2. ŷ ∈ L ⟺ es gibt eine Implikation U → W aus einem früheren Durchgang mit gleicher linker Seite U, d.h. das gegenwärtige U → V hat V ⊊ W.

3. y ∈ {0, 2}^{n} und y ∉ L heißt: die linke Seite U der von y codierten trivialen Implikation U → U war zu keinem früheren Zeitpunkt linke Seite einer Implikation, d.h. U ist abgeschlossen.

Der obige Algorithmus ist also nicht nur zur Konstruktion der Wertetabelle H ∪ K = {U → V | U ∈ 2^{n}, V ist der Abschluss von U} des Abschlussoperators geeignet ist, sondern sammelt auch noch gleichzeitig alle abgeschlossenen Teilmengen in der Menge K auf. Man kann daher den Begriffsverband des gegebenen Kontexts 𝕂 – durch Angabe des Inhalts eines jeden Begriffs – und die Wertetabelle simultan bestimmen. Insbesondere braucht man nicht eines von beiden, um das andere zu berechnen.

5.3 Ein kanonisches vollständiges Implikationensystem

In unseren bisherigen Betrachtungen haben wir zur Vereinfachung einer gegebenen Implikationenmenge noch nicht von der Eigenschaft (8) Gebrauch gemacht. Im Beispiel auf p.18 haben wir gesehen, wie man diese Eigenschaft zur Vereinfachung von Implikationenmengen einsetzen kann. Dabei hat es sich als nützlich erwiesen, die Implikationen zu normieren, indem wir Eigenschaft (6) anwenden und nur irreduzible Implikationen benutzen. Wir ersetzen also eine Implikation U → V durch die Menge {U → {v} | v ∈ V }, was das Maß ω nicht ändert.

Implikationen U → {x} in X_{n} codieren wir als punktierte 0, 1−Vektoren, das sind 0, 1−Vektoren mit einem Sonderzeichen •, das genau einmal vorkommt. Wir können nämlich U → {x} aus der Indikatorfunktion der Menge U ∪ {x} ∈ 2^{n} rekonstruieren, wenn wir mit dem • zusätzlich kennzeichnen, welches Element das x ist, z.B. codiert der Vektor (1, 0, 1, •, 0, 1) die Implikation {6, 4, 1} → 3. Wenn wir Gegenstände und Merkmale auf diese Weise an 𝔹_{3} und 𝔸_{3} schreiben, erhalten wir die Kontexte 𝔹_{3}

0 0 0 0 • • • • 1 1 1 1
0 • • 1 0 0 1 1 0 • • 1
• 0 1 • 0 1 0 1 • 0 1 •
000  × × × × × × × × ×
001 × × × × × × × ×
010 × ×  × × × × × ×
011 × × × ×  × × × ×
100  × × × × × ×  × ×
101 ×  × × × × × ×  ×
110 × × × × × × × ×
111 × × × × × × × × × × × ×

und 𝔸_{3}

• • • • • • • •
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
000 × × × × × × ×
001  × × × × × ×
010 × × × × × ×
011  × × × ×
100 × × × × × ×
101 × × × ×
110 × × × ×

111

Schließlich beschreiben wir die Inzidenzrelation von 𝔹_{n} bzw. von 𝔸_{n} durch Angabe der Zeilen des Kontexts und der Spalten des Kontexts (wieder als 0, 1−Vektoren oder Wörter der Länge χ_{n} := |X_{n}| und 2^{n} für 𝔹_{n} bzw. 2^{n} und 2^{n} für 𝔸_{n}). Beispielsweise liest man vom Kontext 𝔹_{3} ab, dass für den Gegenstand {3, 2} von 𝔹_{3}, der durch (1, 1, 0) codiert wird,

{(1, 1, 0)}^{𝔹_{3}} = {(1, 1, 0)}^{⊢} = (0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0)

ist und dass die Implikation {3, 1} → 2, die codiert wird durch (1, •, 1), die Spalte

{(1, •, 1)}^{𝔹_{3}} = {(1, •, 1)}^{⊢} = (1, 1, 1, 1, 1, 0, 1, 1)

definiert. Im Kontext 𝔸_{n} gilt offenbar:

(x_{n}, …, x_{1}) ⊢ (•, y_{n}, …, y_{1}) ⟺ ∃i ∈ {1, … n} mit x_{i} < y_{i}

Unser erstes Ziel ist es, für den gegebenen Kontext 𝕂 = (G, M, I) mit |M| = n die Menge aller gültigen irreduziblen Implikationen zu berechnen.

Satz 5.4. Für einen Gegenstand g ∈ G des Kontexts 𝕂 = (G, M, I) mit |M| = n sei sein Gegenstandsinhalt g′ = (g_{n}, …, g_{1}) ∈ 2^{n} gegeben. Dann gilt für n = 1

(g_{[1]})^{𝔹_{1}} = \{ \begin{matrix}0, & falls g_{1} = 0 \\ 1, & falls g_{1} = 1 \end{matrix} und (g_{[1]})^{𝔸_{1}} = \{ \begin{matrix}(0, 1), & falls g_{1} = 0 \\ (0, 0), & falls g_{1} = 1 \end{matrix}

und für n > 1 ist

(g_{[n]})^{𝔹_{n}} = \{ \begin{matrix}(g_{[n−1]})^{𝔹_{n−1}}, (g_{[n−1]})^{𝔸_{n−1}}, 1^{(n−1)2^{n−2}}, & falls g_{n} = 0 \\ (g_{[n−1]})^{𝔹_{n−1}}, 1^{2^{n−1}}, (g_{[n−1]})^{𝔹_{n−1}}, & falls g_{n} = 1 \end{matrix}

sowie

(g_{[n]})^{𝔸_{n}} = \{ \begin{matrix}(g_{[n−1]})^{𝔸_{n−1}}, 1^{2^{n−1}}, & falls g_{n} = 0 \\ (g_{[n−1]})^{𝔸_{n−1}}, (g_{[n−1]})^{𝔸_{n−1}}, & falls g_{n} = 1 \end{matrix}

Beweis. Die Konstruktion folgt unmittelbar aus dem rekursiven Aufbau der 𝔹_{n} nach (10).

Der 0, 1−Vektor (g_{[n]})^{𝔹_{n}} ist die Indikatorfunktion ε : X_{n} ⟶ 2 der Menge F = {g′}^{𝔹_{n}} aller irreduziblen Implikationen, die von dem Gegenstandsinhalt g′ respektiert werden, d.h. ε^{−1}(1) = {g′}^{𝔹_{n}}, wobei die Implikationen so angeordnet sind, wie durch die Konstruktion von 𝔹_{n} vorgegeben.

Um eine beliebige Menge F von irreduziblen Implikationen im Kontext 𝔹_{n} explizit beschreiben zu können, müssen wir aus dem 0, 1−Vektor für die Indikatorfunktion von F die zugehörige Teilmenge aller derjenigen 0, •, 1−Vektoren, die die Elemente von F codieren, rekonstruieren. Dazu kann man die Menge X_{n} in der Form X_{n} = {0, 1, …, χ_{n} − 1} schreiben; ε_{k} sei dann der 0, 1−Vektor der Länge χ_{n}, der genau an der k−ten Stelle den Eintrag 1 und sonst den Eintrag 0 hat. Man beachte, dass die Stelle k des Vektors ε_{k} das Element k − 1 ∈ X_{n} bezeichnet:

ε_{k}(t) = 1 ⟺ t = k − 1

ε_{k} fassen wir als die Indikatorfunktion ε_{k} : X_{n} ⟶ 2 einer einelementigen Merkmalmenge von 𝔹_{n} auf. Dann ist eine beliebige Indikatorfunktion ε darstellbar ε = ∑_{ε(k)=1} ε_{k} und ε^{−1}(1) = ⋃_{ε(k)=1} ε_{k}^{−1}(1).

Die Indikatorfunktion ε_{k} repräsentiert eine irreduzible Implikation ε_{k}^{−1}(1) = (b_{n}(t), …, b_{1}(t)) ∈ {0, •, 1}^{n}, wobei t = k−1 < χ_{n}. Der Vektor (b_{n}(t), …, b_{1}(t)) wird wieder zu b_{[n]}(t) abgekürzt und nach folgender Rekursion berechnet, wobei wir Vektoren ohne Klammern schreiben.

Satz 5.5. Es sei t ∈ ℕ und n ∈ ℕ mit t < χ_{n}. Für n = 1 ist

b_{[1]}(0) = • und a_{[1]}(0) = 0, a_{[1]}(1) = 1

und für n > 1 gilt

b_{[n]}(t) = \{ \begin{matrix}1, b_{[n−1]}(t − (n + 1)2^{n−2}) & falls (n + 1)2^{n−2} ≤ t (< χ_{n}) \\ •, a_{[n−1]}(t − (n − 1)2^{n−2}) & falls (n − 1)2^{n−2} ≤ t < (n + 1)2^{n−2} \\ 0, b_{[n−1]}(t) & falls t < (n − 1)2^{n−2} \end{matrix}

und

a_{[n]}(t) = \{ \begin{matrix}1, a_{[n−1]}(t − 2^{n−1}) & falls 2^{n−1} ≤ t \\ 0, a_{[n−1]}(t) & falls t < 2^{n−1} \end{matrix}

Beweis. Wegen der Bedingung t < χ_{n} tritt das Argument t = 1 in der Definition für b_{[1]} nicht auf.

Die Berechnung und Eindeutigkeit von b_{[n]}(t) folgt aus dem Aufbau der Merkmalmenge von 𝔹_{n} aus denen von 𝔹_{n−1} und 𝔸_{n−1}.

Bemerkungen. 1. Für festes t ∈ ℕ unterscheiden sich die Ergebnisse b_{[n]}(t) für verschiedene n mit t < χ_{n} nur um führende Nullen.

2. Wegen χ_{n} + 2^{n} = (n + 2) · 2^{n−1} können wir diese Konstruktion auch so umschreiben: Jede natürliche Zahl t ≥ 0 hat eine eindeutige Darstellung

t = ∑_{i≥0} t_{i}τ_{i}  (12)

mit t_{i} ∈ {0, 1} und der weiteren Eigenschaft: Es gibt genau ein j ≥ 0 mit t_{j} = 1 und

(a) für alle i > j ist τ_{i} = χ_{i} + 2^{i}; (b) für i = j ist τ_{i} = χ_{i};

(c) für alle i < j ist τ_{i} = 2^{i}.

3. Dabei haben wir zusätzlich χ_{0} = 0 benutzt. Die Summation (12) ist endlich, denn t_{i} = 0 für alle i, für die χ_{i} ≥ t ist. Die 1 an der Stelle j wird durch den • gekennzeichnet. Für t = k − 1 ist die Folge

ε_{k}^{−1}(1) = (t_{n−1}, …, t_{j+1}, •, t_{j−1}, …, t_{0}) = (b_{n}(k − 1), …, b_{1}(k − 1))

die von ε_{k} codierte irreduzible Implikation.

4. Die eindeutig bestimmte Komponente i des charakteristischen Vektors (b_{n}(k −1), …, b_{1}(k −1)) mit b_{i}(k −1) = • nennen wir seine signifikante Komponente.

Die Indikatorfunktion der Menge aller irreduziblen Implikationen, die in einem gegebenen Kontext 𝕂 gelten, lässt sich effizient berechnen, indem man das komponentenweise Produkt der Vektoren (g_{[n]})^{𝔹_{n}} mit g ∈ G bildet. Diese Indikatorfunktion wird beschrieben durch die aufsteigende Folge

1 ≤ k_{1} < k_{2} < … < k_{s} ≤ χ_{n}

aller natürlichen Zahlen k_{i}, für die ε_{k_{i}} = 1 ist. Die zugehörigen irreduziblen Implikationen y_{i} = (b_{n}(k_{i}−1), …, b_{1}(k_{i}−1)) für 1 ≤ i ≤ s erhält man daraus nach Satz 5.5. Sie definieren eine Folge

(0, 0, … 0, •) ⪯ y_{1} ≺ y_{2} ≺ … ≺ y_{s} ⪯ (1, 1, …, 1, •)  (13)

von Vektoren in {0, •, 1}^{n}, die alle Informationen über das Hüllensystem \underline{𝔅}(𝕂) enthält. Diese Folge ist lexikographisch aufsteigend für 0 < • < 1. Aus ihr lässt sich z.B. wieder der Verband aller abgeschlossenen Teilmengen von M, also der Begriffsverband \underline{𝔅}(𝕂), gewinnen, weil eine Teilmenge U ⊆ M genau dann nicht abgeschlossen ist, wenn es eine irreduzible Implikation U → {x} gibt, deren Codierung in der Folge (13) vorkommt.

Definition 5.6. Für jede Zahl j ∈ {1, …, n} bilden wir die Menge

L_{j} = {y_{i} | 1 ≤ i ≤ s, j ist die signifikante Komponente von y_{i}}

Jede Menge L_{j} betrachten wir durch die Produktordnung ≤_{n} von 0 < • < 1 geordnet und definieren

min L_{j} := {y ∈ L_{j} | x ∈ L_{j}, x ≤_{n} y ⟹ x = y}

als die Menge aller minimalen Elemente von L_{j}. Schließlich sei

L := ⋃_{1≤j≤n} min L_{j}

Die Mengen min L_{j} sind also Antiketten^{10} bezüglich ≤_{n}.

Die Mengen L_{j} bzw. L beschreiben Mengen L_{j} bzw. L von irreduziblen Implikationen.

Lemma 5.7. Für je zwei x, y ∈ min L_{j} mit x ≠ y seien U → {u} und V → {v} die dargestellten Implikationen. Dann gilt u = v und U ⊈ V, V ⊈ U.

Definition 5.8. Zwei Vektoren x ∈ L_{i} und y ∈ L_{j} verknüpfen wir zu x ⊙ y, indem wir komponentenweise 0 ⊙ 0 = 0, 0 ⊙ 1 = 1 ⊙ 0 = 1 ⊙ 1 = 1, 0 ⊙ • = • ⊙ 0 = • und • ⊙ • = • ⊙ 1 = 1 ⊙ • = 0 berechnen.

Lemma 5.9. Es seien x ∈ L_{i} und y ∈ L_{j} mit i ≠ j und U → {u} die von x und V → {v} die von y codierte Implikation.

Falls u ∈ V und v ∉ U, d.h. an der signifikanten Komponente von x hat y den Wert 1 und an der signifikanten Stelle von y hat x den Wert 0, dann ist x ⊙ y die Codierung von U ∪ V \ {u} → {v}, d.h. x ⊙ y ∈ L_{j}.

Falls u ∉ V und v ∈ U, d.h. an der signifikanten Komponente von x hat y den Wert 0 und an der signifikanten Stelle von y hat x den Wert 1, dann ist x ⊙ y die Codierung von U ∪ V \ {v} → {u}.

Beweis. Die Operation ⊙ beschreibt das dritte der Armstrongaxiome in den Fällen, in denen nur irreduzible Implikationen beteiligt sind.

Bemerkungen. 1. Falls i = j oder keine der beiden vorstehenden Bedingungen erfüllt ist, liefert das komponentenweise Produkt x⊙y zwar ein Ergebnis, dieses ist aber nicht die Codierung einer irreduziblen Implikation. Wir betrachten x ⊙ y dann als undefiniert.

2. Wenn einer der im Lemma genannten Fälle eintritt, schreiben wir in Anlehnung an die Definition von ⊧ (auf p.8) {x, y} ⊧ x ⊙ y (und auch {x, y} ⊧ U ∪ V \ {u} → {v}, sowie {U → {u}, V → {v}} ⊧ z für z = x ⊙ y)^{11}.

10Eine Teilmenge X einer geordneten Menge (M, ≤) heißt eine Antikette, wenn je zwei verschiedene Elemente von X unvergleichbar bezüglich ≤ sind.

11Wir erlauben uns auch, das Zeichen ≡ im gleichen Sinne zwischen Mengen von Implikationen und Mengen von Codierungen von Implikationen zu verwenden.

3. Die Definition von ⊙ erweitern wir für i ≠ j durch L_{i}⊙L_{j} = {x⊙y | x ∈ L_{i}, y ∈ L_{j}}, und es gilt dann L_{i} ⊙ L_{j} ⊆ L_{i} ∪ L_{j}.

4. Wir wenden zwar das dritte Armstrongaxiom nur auf irreduzible Implikationen an, für endliche Systeme haben wir damit aber schon den allgemeinen Fall erledigt, denn:

{U → {x_{1}, x_{2}}, W ∪ {x_{1}, x_{2}} → Z}
≡ {U → x_{1}, U → x_{2}, (W ∪ {x_{2}}) ∪ {x_{1}} → Z}
liefert zunächst {U → x_{1}, U → x_{2}, U ∪ W ∪ {x_{2}} → Z},
dann {U → x_{1}, U → x_{2}, U ∪ W → Z},
also insgesamt {U → {x_{1}, x_{2}}, W ∪ {x_{1}, x_{2}} → Z} ⊧ {U ∪ W → Z}.

Lemma 5.10. Es seien x, y Codierungen irreduzibler Implikationen in Imp(𝕂) und x ⊙ y sei nicht undefiniert. Dann gilt:

1. x ≠ x ⊙ y ≠ y;

2. Wenn x ≤_{n} y, dann ist x ⊙ y <_{n} y;

3. Wenn x ⊙ y ∈ L_{i}, dann ist entweder x ∈ L_{i} oder y ∈ L_{i};

4. Wenn x ⊙ y = z ∈ L, dann gibt es x̃ und ỹ ∈ L mit x̃ ⊙ ỹ = z.

Beweis. 1., 2. und 3. folgen direkt aus der Definition von ⊙.

Es seien x, y ∈ Imp(𝕂) mit x ⊙ y = z ∈ L. Dann ist o.B.d.A. z ∈ min L_{i}, d.h. x hat signifikante Komponente i, und y hat signifikante Komponente j mit i ≠ j. Die Behauptung 4. folgt aus der Monotonie von ⊙: Wenn x̃ signifikante Komponente i hat mit x̃ ≤_{n} x und ỹ signifikante Komponente j hat mit ỹ ≤_{n} y, dann ist x̃⊙ỹ ≤_{n} z. Daher gibt es x̃ ∈ min L_{i} und ỹ ∈ min L_{j} mit x̃ ⊙ ỹ = z.

Obwohl die Mengen min L_{j} zunächst nur für sich Antiketten sind, ist sogar ganz L eine Antikette.

Satz 5.11. Für einen Kontext 𝕂 sei die Menge L wie in Definition 5.6 gebildet. Dann gilt:

1. Die Menge L ist eine Antikette.

2. L ≡ Imp(𝕂)

Beweis. Es seien x ∈ min L_{i} und y ∈ min L_{j} mit i ≠ j, so dass x ≤_{n} y gilt. Dann ist nach Eigenschaft 2 von Lemma 5.10 x ⊙ y = z ∈ L_{j} mit z <_{n} y, also war y nicht minimal in L_{j}.

Es gilt ⋃_{1≤i≤n} L_{i} ≡ Imp(𝕂) nach Konstruktion und L_{i} ≡ min L_{i}, denn nach dem zweiten Armstrongaxiom ist jedes x ∈ L_{i}, das nicht minimal (innerhalb L_{i}) bezüglich ≤_{n} ist, entbehrlich.

Definition 5.12. Die in Definition 5.6 konstruierte Menge L von irreduziblen Implikationen heiße die kanonische Antikette L(𝕂) von Imp(𝕂).

Man beachte, dass die kanonische Antikette noch Redundanz aufweisen kann. Da die Menge L(𝕂) eine Antikette ist, die nur minimale Elemente enthält, kann diese Redundanz nur von der Anwendbarkeit des dritten Armstrongaxioms herrühren.

5.4 Ein Algorithmus zur Bestimmung einer irredundanten Teilmenge

Der folgende Algorithmus erzeugt aus der kanonischen Antikette L eine irredundante Teilmenge. Dabei stellen wir irreduzible Implikationen wieder durch ihre zugehörigen 0, •, 1−Vektoren dar. Der Menge L entspricht dann eine Menge L von 0, •, 1−Vektoren und die Frage nach einer redundanzfreien Teilmenge von L transformiert sich in die Frage nach einem minimalen Erzeugendensystem von L bezüglich ⊙.

Definition 5.13. Für jede Teilmenge Y von L sei Y^{∼} die Menge aller Elemente von L, die durch mindestens einmalige Anwendung von ⊙ auf Elemente von Y enstehen:

Y_{2} := Y ⊙ Y
Y_{n+1} := Y_{n} ∪ {x ∈ L | es gibt u ∈ Y_{n}, v ∈ Y ∪ Y_{n} mit x = u ⊙ v }
Y^{∼} := ⋃_{n≥2} Y_{n}

Weiter sei \overline{Y} := Y ∪Y^{∼}. Die Elemente von Y^{∼} nennen wir aus Y echt erzeugt.

Um ein minimales Erzeugendensystem zu finden, bemerken wir zunächst:

Lemma 5.14. Die Menge Y := L \ (L ⊙ L) aller Elemente von L, die sich nicht als Produkt zweier Elemente von L darstellen lassen, muss in jedem Erzeugendensystem enthalten sein.

Die Menge Y erzeugt mit Hilfe von ⊙ eine Teilmenge \overline{Y} = Y ∪ Y^{∼} ⊆ L.

Algorithmus 5.15. 1. Sei Y_{0} := Y

2. Die Menge Y_{n} sei bereits konstruiert. Nach Lemma 5.14 ist Y_{n} = Y ∪Z_{n} mit Z_{n} ⊆ L \ Y.

3. (a) Falls \overline{Y_{n}} = L, dann gib E := Y_{n} aus.

(b) Falls \overline{Y_{n}} ≠ L, dann gibt es z ∈ L \ \overline{Y_{n}}. Die Menge Y_{n} ∪ \{z\} erzeugt eine Menge \overline{Y_{n} ∪ \{z\}} = Y_{n} ∪ \{z\} ∪ (Y_{n} ∪ \{z\})^{∼}. Die Menge Y_{n+1} ist dann

Y_{n+1} := (Y_{n} \ (Y_{n} ∪ {z})^{∼}) ∪ {z} = Y ∪ (Z_{n} \ (Y_{n} ∪ {z})^{∼}) ∪ {z}

Bemerkung. Die Gleichung

(Y_{n} \ (Y_{n} ∪ {z})^{∼}) ∪ {z} = Y ∪ (Z_{n} \ (Y_{n} ∪ {z})^{∼}) ∪ {z}  (14)

folgt nach Definition von Y. Da das Element z möglicherweise selbst aus Y_{n}∪{z} echt erzeugbar ist, gilt i.A. (Y_{n}\(Y_{n}∪{z})^{∼})∪{z} ≠ (Y_{n}∪{z})\(Y_{n}∪ {z})^{∼}. Alle Vereinigungszeichen in Gleichung (14) sind daher als disjunkte Vereinigung zu lesen. Dies garantiert, dass im Laufe des Algorithmus für jedes Paar (x, y) ∈ L × L nur einmal das Produkt x ⊙ y berechnet zu werden braucht.

Korollar 5.16. Bei jeder Anwendung von Schritt 3(b) gilt \overline{Y_{n}} ⊊ \overline{Y_{n+1}}. Der Fall \overline{Y_{n+1}} = L tritt daher nach spätestens |L \ Y | Schritten ein.

Beweis. Bei jeder Anwendung von Schritt 3(b) ist zunächst nach Konstruktion z ∉ \overline{Y_{n}}, z ∈ \overline{Y_{n+1}}. Weiter gilt: Jedes y ∈ Y_{n}^{∼} , das bei seiner Erzeugung aus Y_{n} ein x ∈ Z_{n} benutzt, das selbst wieder echt aus Y_{n} ∪ {z} erzeugbar ist, kann über der Menge (Y_{n} \ (Y_{n} ∪ {z})^{∼}) ∪ {z} erzeugt werden. Daher gilt auch \overline{Y_{n}} = Y_{n} ∪ Y_{n}^{∼} = Y ∪ Z_{n} ∪ (Y ∪ Z_{n})^{∼} ⊆ \overline{Y_{n+1}}.

Satz 5.17. Es sei E := Y_{n} eine Menge mit der Eigenschaft \overline{Y_{n}} = L. Dann gilt:

1. E ist ein minimales Erzeugendensystem für L.

2. Die Menge E beschreibt eine Menge E von irreduziblen Implikationen. E ist eine (inklusions-)minimale Teilmenge von L mit E ≡ L.

3. Für L = L(𝕂) ist E ist eine Basis für Imp(𝕂).

Beweis. Die Aussage 2. ist Umformulierung von Aussage 1. und Aussage 3. folgt wegen L ≡ Imp(𝕂). Also ist nur die Aussage 1. zu beweisen. Wir zeigen:

Wenn Y_{n} ein minimales Erzeugendensystem für \overline{Y_{n}} ist, dann ist Y_{n+1} ein minimales Erzeugendensystem für \overline{Y_{n+1}}.

Es sei Y_{n+1} kein minimales Erzeugendensystem, d.h. es gibt ein x ∈ Y_{n+1}, das über Y_{n+1}\{x} erzeugbar ist. Dann ist x ∉ Y; ebenso ist x = z unmöglich, da z nicht über Y_{n} = Y ∪ Z_{n}, also erst recht nicht über Y ∪ (Z_{n} \ (Y_{n} ∪ {z})^{∼}) erzeugbar ist. Daher ist x erzeugbar über Y_{n+1} \ {x, z}.

Also ist x ∈ Z_{n} \ (Y_{n} ∪ {z})^{∼}, d.h. x ∈ Y_{n}, und x ist erzeugbar über Y_{n+1} \ {x, z} ⊆ Y ∪ Z_{n} \ {x}. Dann ist also auch Y_{n} kein minimales Erzeugendensystem gewesen.

Bemerkungen. Den Algorithmus 5.15 kann man nach einer leichten Modifikation verwenden, um auch für jede andere vollständige Teilmenge D von Imp(𝕂) ein äquivalentes Teilsystem E zu erhalten. Dazu ist die Bedingung im Punkt 3 abzuändern in \overline{Y_{n}} ⊇ L bzw. \overline{Y_{n}} ⊉ L und dieser modifizierte Algorithmus anzuwenden auf die Antikette L = min D. E kann dann aber noch Elemente x, y, z enthalten, für die x ⊙ y < z gilt. Das Element z ist dann redundant. Es gilt aber stets ω(E) ≤ ω(D).

Insbesondere kann man möglicherweise eine gegebene Duquenne-Guigues-Basis damit verkleinern.

Das Beispiel L = {{1, 4} → 2, {3, 4} → 2, {1, 4} → 3, {2, 4} → 3} zeigt, dass das Ergebnis des Algorithmus von der Strategie abhängt, mit der im Schritt 3 des Algorithmus 5.15 das Element z ausgewählt wird. Die für L(𝕂) produzierte Menge E ist daher zwar stets irredundant, also eine Basis, aber nicht notwendigerweise minimal in der Anzahl der irreduziblen Implikationen.

Die Berechnung der kanonischen Antikette für einen Kontext 𝕂 mit n Merkmalen ist nach Satz 5.11 n−fach parallel durchführbar.

Wenn man die Anzahl der Multiplikationen ⊙ und nicht die Anzahl der Schleifendurchläufe in Algorithmus 5.15 als Maßstab nimmt, kann man nach der Bemerkung vor Korollar 5.16 die Laufzeit des Algorithmus durch O(|L|^{2}) abschätzen, wobei L die gegebene Antikette ist. Andererseits ist jedes min L_{i} eine Antikette in 2^{n−1}, also | min L_{i}| ≤ \binom{n−1}{⌈\frac{n−1}{2}⌉}. Legt man also die Anzahl n der Merkmale des zugrundeliegenden Kontexts 𝕂 als Maßstab an, so folgt für die Laufzeit des Algorithmus die obere Schranke O(4^{n}).

Der folgende Satz stellt einen engen Zusammenhang zwischen jeder Basis, die der Algorithmus 5.15 erzeugt, und der Duquenne-Guigues-Basis her.

Satz 5.18. Es sei D(𝕂) die Duquenne-Guigues-Basis des Kontexts 𝕂, geschrieben in irreduziblen Implikationen und E eine Basis für Imp(𝕂), die der Algorithmus 5.15 liefert, wenn er mit L(𝕂) gestartet wird.

Zu jeder Implikation P → u von D(𝕂) gibt es eine Implikation U → u in L(𝕂) mit U ⊆ P.

Zu jeder Implikation U → u in E gibt es genau eine minimale (bezüglich ≤_{n}) Implikation P → u in D(𝕂) mit U ⊆ P.

Beweis. Die erste Eigenschaft folgt aus L(𝕂) ≡ D(𝕂) ≡ Imp(𝕂).

Offenbar ist E ⊆ L(𝕂). Es sei U → u eine Implikation in E, die nicht zu D(𝕂) gehört. Da E irredundant ist, gibt es eine minimale Menge P mit der Eigenschaft

P ⊢ E \ {U → u} und P ⊬ E

Dann gilt U ⊆ P und u ∉ P, also P′′ ⊇ P ∪{u} und für jede echte Teilmenge Q ⊆ P, P ≠ Q gilt Q ⊢ E, also Q′′ ⊆ P. Daher ist P ein Pseudoinhalt und es gilt P → u ∈ D(𝕂).

Es seien U → u und V → u zwei verschiedene Implikationen in E und P ⊆ M mit

P ⊢ E \ {U → u} und P ⊬ E

sowie

P ⊢ E \ {V → u} und P ⊬ E

Da U ≠ V gilt, folgt aus der ersten Bedingung P ⊢ V → u, was der zweiten Bedingung widerspricht.

Korollar 5.19. Für jedes Ergebnis E des Algorithmus 5.15 gilt:

ω(E) ≤ ω(D(𝕂))

Beweis. Nach Satz 5.18 gibt es eine injektive und ≤_{n} −monotone Abbildung f : 2^{n} ⟶ 2^{n}, für die die Zuordnung U → u ↦ f(U) → u eine Injektion E ⟶ D(𝕂) definiert. Es folgt:

ω(Y) = ∑_{U→u∈E} |U| ≤ ∑_{U→u∈E} |f(U)| ≤ ∑_{P →P′′∈D(𝕂)}|P | · |P′′ \ P | = ω(D(𝕂))

6 Abschließende Bemerkungen

Die Kenntnis und leichte Konstruierbarkeit eines Kontexts, der alle Hüllensysteme auf einer n−elementigen Menge als Begriffsinhalte besitzt, hat einige weitere für die Anwendungen nützliche Konsequenzen.

Zunächst ist, wie in Kapitel 5 durchgeführt, für einen gegebenen Kontext 𝕂 mit n Merkmalen das „maximale Rechteck” (𝔎, Imp(𝕂)), das in ℍ_{n} enthalten ist und dessen erste Komponente aus den Zeilen des Kontexts 𝕂 besteht, einfach bestimmbar. Dieses Rechteck ist ein Begriff des Kontexts ℍ_{n}; sein Begriffsumfang ist ein Mengensystem, bestehend aus den Zeilen von 𝕂. Insoweit sind 𝕂 und (𝔎, Imp(𝕂)) äquivalent. Wie bei allen Begriffen stellt sich die Frage nach einer einfachen Beschreibung von (𝔎, Imp(𝕂)), also einem Paar (𝔛, Y) mit 𝔛^{⊢} = Imp(𝕂) und Y^{⊢} = 𝔎. Die Vereinfachung von Imp(𝕂) besteht in der Beseitigung von Redundanz. Falls der Ausgangskontext 𝕂 reduziert ist, ist zumindest die erste Komponente 𝔎 in kanonischer Form. Ansonsten liefert Zeilenreduktion (in 𝕂 statt in ℍ_{n}!) diese Form. Eine der möglichen kanonischen Formen ist das Paar (𝔎, D(𝕂)), mit der Duquenne-Guigues-Basis D(𝕂) als Merkmalmenge.

Die Eigenschaft (6) liefert den ersten Schritt bei der Vereinfachung von Imp(𝕂): die Beschränkung auf die irreduziblen Implikationen. Nach (7) (oder dem zweiten Armstrongaxiom) ist der Übergang zur kanonischen Antikette eine weitere Vereinfachung. Sie liefert als kanonische Form das Paar (𝔎, L(𝕂)). Das dritte Armstrongaxiom kann man nun deuten als eine weitere zugelassene Operation, um die kanonische Antikette noch zu vereinfachen. Der Gewinn besteht in einer weiteren Verringerung der Redundanz, allerdings verliert man nun in der Regel die Kanonizität.

Man kann demnach eine vollständige irredundante Menge von irreduziblen Implikationen eines gegebenen Kontexts finden, ohne von dem zugrundeliegenden Abschlussoperator Gebrauch zu machen, also mit „rein syntaktischen” Mitteln. Wie dies von praktischem Interesse sein kann, wird an einem Beispiel im Anhang A.1 ausgeführt.

Für gewisse Anwendungen ist es jedoch angebracht, statt des Begriffs (𝔎, Imp(𝕂)) oder einer seiner möglichen Vereinfachungen (z.B. (𝔎, L(𝕂))) seine Erweiterung zu einem Kontext (𝔎, X_{n}, ⊢) zu betrachten. Die Wirkung von (𝔎, L(𝕂)) innerhalb dieses Kontexts ist bekannt unter dem Namen „Hintergrundimplikationen”, d.h. die Implikationenmenge L(𝕂) kann man durch weitere Implikationen, deren Gültigkeit man sich wünscht, vergrößern, was den zugehörigen Begriffsumfang zu einem Teilkontext von 𝕂 verkleinert. Im Anhang A.2 ist gezeigt, wie man damit ein effektives Verfahren zur Konstruktion des Kongruenzenverbands einer beliebigen Algebra gewinnen kann. Da die Kongruenzenbedingung von besonders einfacher Bauart ist, genügt es dabei sogar, nur einen Teil des Kontexts 𝔹_{n} zu konstruieren.

Die Duquenne-Guigues-Basis ist mit Hilfe eines Abschlussoperators, der aus dem gegebenen Abschlussoperator durch Erweiterung entsteht, definiert. Also kann man fragen, ob diese Erweiterung aus dem analog gebildeten Kontext (2^{n}, L(𝕂), ⊢), wobei man jetzt (𝔎, L(𝕂)) als „Hintergrundabschlüsse” sehen kann, einfach zu konstruieren ist. Wäre dies der Fall, dann hätte man vielleicht auch ein einfaches Verfahren zur Konstruktion der Duquenne-Guigues-Basis.

Alle bisherigen Betrachtungen sind, wie auch die Anwendungen im Anhang zeigen, von überwiegend innermathematischem Interesse. Für die Anwendungen außerhalb der Mathematik ist die Forderung des Respektierens einer Implikation häufig zu strikt. Beispielsweise sind Implikationen von geringer Bedeutung, die zwar in einem gegebenen Kontext respektiert werden, für die es aber keine Gegenstände gibt, die die Prämisse erfüllen.

Wir können unsere Ergebnisse weiterverwenden, indem wir den Blick auf den Kontext (𝔎, X_{n}, ⊢) verändern: Wir sehen seine Zeilen nicht als boolesche, sondern als rationale 0, 1−Vektoren der Länge χ_{n}. Spaltenweise aufsummiert, erhält man für jede Implikation in X_{n} die Anzahl der Gegenstände des Kontexts 𝕂, die diese Implikation respektieren. Dies ist der Ausgangspunkt für die quantitative Begriffsanalyse. Ein Artikel mit den ersten Ergebnissen erscheint demnächst an anderer Stelle.

Literatur

[1] N. Caspard, B. Monjardet: The lattice of closure systems, closure operators, and implicational systems on a finite set: a survey, Discrete Applied Math. 127: 241–269 (2003).

[2] J. Demetrovics, L. Libkin, I. Muchnik: Functional Dependencies in Relational Databases: A Lattice Point of View. Discrete Applied Mathematics 40(2): 155–185 (1992)

[3] B. Ganter, R. Wille: Formale Begriffsanalyse: Mathematische Grundlagen. Springer Verlag Heidelberg, 1996, ISBN 3-540-60868-0.

[4] B. Ganter: Begriffe und Implikationen, in: Stumme, Wille (Hrsg.): Begriffliche Wissensverarbeitung – Methoden und Anwendungen, pp.1–24, Springer Verlag, 2000, ISBN 3-540-66391-6

[5] L. Libkin: Direct product decompositions of lattices, closures and relation schemes. Discrete Mathematics 112: 119–138 (1993).

[6] M. Wild: A theory of finite closure spaces based on implications. Adv. in Math. 108: 118–139 (1994).

[7] Download von

   www.mathematik.tu-darmstadt.de/ags/ag1/Software/software_en.html

A Anhang

A.1 Ein Beispiel

Um den Algorithmus 5.15 an einem nicht trivialen Beispiel zu demonstrieren, untersuchen wir den Kontext ℙ_{4} = (G, M, ⋄), dessen Begriffsverband der Verband aller Äquivalenzrelationen auf einer vierelementigen Menge ist. Die Bildung von ℙ_{4} ist in [3], p.53 beschrieben. Gegenüber dieser Konstruktion vertauschen wir allerdings, aus Gründen, die sofort ersichtlich sein werden, die Mengen G und M, so dass wir setzen: G = 2^{\{a,b,c\}}, M = \binom{\{a,b,c,d\}}{2}^{12} und ℙ_{4} sei der Kontext^{13}

b c c d d d
a b a c b a
∅ × × × × × ×
a × × ×
b  × × ×
b, a ×  ×
c ×  × ×
c, a  × ×
c, b ×  ×
c, b, a × × ×

Die Begriffsinhalte dieses Kontexts sind Mengen von zweielementigen Teilmengen von S = {a, b, c, d}; man kann sie als reflexive, symmetrische Relationen auf S deuten. Wir benutzen unsere Konstruktion, um deren Transitivität nachzuweisen. Für die Begriffsinhalte ρ heißt dies:

{{x, y}, {y, z}} ⊆ ρ ⟹ {{x, z}} ⊆ ρ

für alle x, y, z ∈ S; also müssen wir nachweisen, dass jeder Gegenstandsinhalt für beliebige x, y, z ∈ S die irreduzible Implikation {{x, y}, {y, z}} → {{x, z}} respektiert. Wir suchen ⋂_{g∈G}({g}′)^{⊢}, also alle Stellen, die in allen (g_{[6]})^{𝔹_{6}} mit g ∈ G vorkommen; das komponentenweise Produkt ε aller (g_{[6]})^{𝔹_{6}} mit g ∈ G liefert gerade deren Indikatorfunktion.

12Für eine beliebige Menge S bezeichne \binom{S}{2} die Menge aller 2−elementigen Teilmengen der Menge S.

13Die Vertauschung von G und M in ℙ_{4} ergibt als Begriffsverband den zum üblichen Äquivalenzrelationenverband dualen Verband.

Obwohl der Kontext 𝔹_{6} schon χ_{6} = 192 Merkmale hat, können wir diese Indikatorfunktion mit einigem Aufwand noch per Hand berechnen^{14}:

Die erste Zeile von ℙ_{4} besteht nur aus Einsen, also liefert die Konstruktion von (∅_{[6]})^{𝔹_{6}} = 1^{192}, was nicht zum komponentenweisen Produkt beiträgt.

a_{[6]}^{𝔹_{6}} = (0, a_{[5]})^{𝔹_{6}} = (wegen a_{6} = 0)
= ((a_{[5]})^{𝔹_{5}}, (a_{[5]})^{𝔸_{5}}, 1^{80}) = (wegen a_{5} = 1)
= ((a_{[4]})^{𝔹_{4}}, 1^{16}, (a_{[4]})^{𝔹_{4}}, (a_{[4]})^{𝔸_{4}}, (a_{[4]})^{𝔸_{4}}, 1^{80}) = (weil a_{4} = 0)
= ((a_{[3]})^{𝔹_{3}}, (a_{[3]})^{𝔸_{3}}, 1^{12}, 1^{16}, (a_{[3]})^{𝔹_{3}}, (a_{[3]})^{𝔸_{3}}, 1^{12}, (a_{[3]})^{𝔸_{3}}, 1^{8}, (a_{[3]})^{𝔸_{3}}, 1^{88})

Die 0, 1−Vektoren für den Index n = 3 lassen sich direkt aus 𝔹_{3} und 𝔸_{3} ablesen, wodurch man erhält:

a_{[6]}^{𝔹_{6}} = 01101^{4}0110(01)^{4}1^{12}1^{16}01101^{4}0110(01)^{4}1^{12}(01)^{4}1^{8}(01)^{4}1^{88}

Auf analoge Weise ergibt sich:

\begin{aligned}b_{[6]}^{𝔹_{6}} & = 10011^{4}10011^{8}10011^{4}1001(0011)^{4}1^{32}(0011)^{4}1^{16}1^{80} \\ b, a_{[6]}^{𝔹_{6}} & = 00111^{4}0011(0111)^{2}1^{12}(0111)^{2}1^{72}00111^{4}0011(0111)^{2}1^{12}(0111)^{2}1^{40} \\ c_{[6]}^{𝔹_{6}} & = 1^{4}0^{4}1^{4}0^{4}1^{4}1^{12}0^{4}1^{4}1^{8}1^{32}1^{32}1^{4}0^{4}1^{4}0^{4}1^{4}1^{12}0^{4}1^{4}1^{8}1^{32} \\ c, a_{[6]}^{𝔹_{6}} & = 011001011^{4}1^{8}011001011^{4}01011^{4}01011^{4}1^{32}01011^{4}01011^{4}1^{16}1^{80} \\ c, b_{[6]}^{𝔹_{6}} & = 100100111^{4}00111^{4}1^{12}1^{16}100100111^{4}00111^{4}1^{12}00111^{4}1^{8}00111^{92} \\ c, b, a_{[6]}^{𝔹_{6}} & = \underbrace{0^{2}1^{2}01^{3}1^{4}1^{8}0^{2}1^{2}01^{3}1^{4}1^{16}0^{2}1^{2}01^{3}1^{4}1^{8}0^{2}1^{2}01^{3}1^{4}}_{=:q} 1^{32}q \end{aligned}

Das komponentenweise Produkt dieser Vektoren ergibt einen 0, 1−Vektor der Länge 192, der an den Stellen 18, 20, 26, 28, 29, 32, 39, 40, 44, 47, 48, 55, 56, 58, 59, 64, 66, 68, 71, 72, 74-80, 84, 88, 92, 95, 96, 100, 102, 104-112, 115, 116, 123, 124, 130, 131, 132, 135, 136, 138-144, 150-160, 163, 164, 166-180, 183, 184, 186-192 den Eintrag 1, und sonst den Eintrag 0 hat.

Jede dieser Stellen repräsentiert eine irreduzible Implikation. Die Stelle 18 beispielsweise repräsentiert wegen 17 = 1 · χ_{3} + 1 · 2^{2} + 0 · 2^{1} + 1 · 2^{0} die Implikation {3, 1} → {4}, und weil die Merkmale in ℙ_{4} von rechts nach links durchnummeriert sind, heißt dies {{c, d}, {a, d}} → {{a, c}}. Alle Buchstaben in ℙ_{4} sind gleichberechtigt, d.h. ℙ_{4} ist invariant unter allen Permutationen der Grundmenge {a, b, c, d}, also gilt für jeden Begriffsinhalt von ρ ∈ ℙ_{4}: ρ ist transitiv, also eine Äquivalenzrelation. Auf diese Weise haben wir die Transitivität aller Begriffe von \underline{𝔅}(ℙ_{4}) durch schlichtes Nachrechnen im Verband aller Hüllensysteme bewiesen.

14Bei der Konstruktion von 𝔹_{6} sowie bei der Untersuchung anderer Beispiele hat das Darmstädter System ConImp [7] nützliche Dienste geleistet.

Außer diesen 12 Implikationen gibt es aber offenbar noch weitere. Um die kanonische Antikette zu finden, wenden wir Satz 5.11 an und berechnen

\begin{aligned}L_{1} & = & \{29, 32, 72, 77, 80, 116, 124, 136, 141, 144, 164, 169, 172, 184, 189, 192\} \\ L_{2} & = & \{58, 59, 71, 78, 79, 115, 123, 135, 142, 143, 163, 170, 171, 183, 190, 191\} \\ L_{3} & = & \{26, 28, 55, 56, 74, 75, 76, 138, 139, 140, 166, 167, 168, 186, 187, 188\} \\ L_{4} & = & \{18, 20, 64, 66, 68, 130, 131, 132, 173, 174, 175, 176, 177, 178, 179, 180\} \\ L_{5} & = & \{39, 40, 44, 47, 48, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160\} \\ L_{6} & = & \{84, 88, 92, 95, 96, 100, 102, 104, 105, 106, 107, 108, 109, 110, 111, 112\} \end{aligned}

Unter Ausnutzung der Eigenschaft x <_{6} y ⟹ x ≺ y findet man die minimalen Antiketten:

X_{1} = {29, 72, 116, 169}
= {{3, 4} → 1, {2, 4, 5} → 1, {2, 6} → 1, {3, 5, 6} → 1}
X_{2} = {58, 71, 115, 142}
= {{3, 5} → 2, {1, 4, 5} → 2, {1, 6} → 2, {3, 4, 6} → 2}
X_{3} = {26, 55, 139, 166}
= {{1, 4} → 3, {2, 5} → 3, {2, 4, 6} → 3, {1, 5, 6} → 3}
X_{4} = {18, 64, 131, 173}
= {{1, 3} → 4, {1, 2, 5} → 4, {2, 3, 6} → 4, {5, 6} → 4}
X_{5} = {39, 44, 150, 153}
= {{2, 3} → 5, {1, 2, 4} → 5, {1, 3, 6} → 5, {4, 6} → 5}
X_{6} = {84, 95, 102, 105}
= {{1, 2} → 6, {2, 3, 4} → 6, {1, 3, 5} → 6, {4, 5} → 6}

Deren Vereinigung ist die kanonische Antikette

L = L(ℙ_{4}) = X_{1} ∪ … ∪ X_{6}

Um die Menge Y ≡ L \ L ⊙ L aller Implikationen, die nach Lemma 5.14 in jedem Erzeugendensystem enthalten ist, zu finden, benutzen wir die Eigenschaft X_{i} ⊙ X_{j} ⊆ X_{i} ∪ X_{j} und die Kommutativität von ⊙ und bilden die Produkte

X_{1} ⊙ X_{2} = {{3, 4, 5} → 1, {3, 5, 6} → 1, {3, 4, 5, 6} → 1, {3, 4, 6} → 1,
{3, 4, 5} → 2, {3, 4, 6} → 2, {3, 4, 5, 6} → 2, {3, 5, 6} → 2}
X_{1} ⊙ X_{3} = {{2, 4, 5} → 1, {2, 5, 6} → 1, {2, 4, 6} → 1, {2, 4, 5, 6} → 1,
{2, 4, 5} → 3, {2, 4, 5, 6} → 3, {2, 4, 6} → 3, {2, 5, 6} → 3}

Bereits hier ist klar, dass X_{1} \ (L ⊙ L) = {{3, 4} → 1, {2, 6} → 1} ist, denn die Transitivität ist, wie oben gesehen, zumindest erfüllt, also kann keine dieser Implikationen entbehrlich sein. Ganz analog ergeben sich die restlichen Mengen

X_{2} \ (L ⊙ L) = {{3, 5} → 2, {1, 6} → 2}
X_{3} \ (L ⊙ L) = {{1, 4} → 3, {2, 5} → 3}
X_{4} \ (L ⊙ L) = {{1, 3} → 4, {5, 6} → 4}
X_{5} \ (L ⊙ L) = {{2, 3} → 5, {4, 6} → 5}
X_{6} \ (L ⊙ L) = {{1, 2} → 6, {4, 5} → 6}

Man erhält Y als Vereinigung dieser Mengen und nach Verfikation der Eigenschaft \overline{Y} = L bricht der Algorithmus 5.15 schon beim ersten Durchgang ab. Es ergibt sich die bekannte Tatsache, dass im Verband aller Äquivalenzrelationen (auf einer vierelementigen Menge) eine Implikation genau dann respektiert wird, wenn sie aus der Transitivität (d.h. aus der Menge Y) mit Hilfe der Armstrongaxiome herleitbar ist:

E = Y = {{3, 4} → 1, {2, 6} → 1, {3, 5} → 2, {1, 6} → 2,
{1, 4} → 3, {2, 5} → 3, {1, 3} → 4, {5, 6} → 4,
{2, 3} → 5, {4, 6} → 5, {1, 2} → 6, {4, 5} → 6}

A.2 Konstruktion von Teilsystemen

A.2.1 Allgemeine Teilsysteme

Der Begriffsverband \underline{𝔅}(𝕂) eines Kontextes 𝕂 = (G, M, I) mit höchstens n Merkmalen wird repräsentiert durch ein Hüllensystem auf einer n−elementigen Menge und ist daher ein Begriff im Begriffsverband \underline{𝔅}(𝔹_{n}) des Kontextes 𝔹_{n} = (2^{n}, X_{n}, ⊢). \underline{𝔅}(𝕂) wird also beschrieben durch ein maximales Rechteck (A, B) in 𝔹_{n}^{15}; dessen Seiten sind einerseits A ⊇ {g′ | g ∈ G} = 𝕂(G), und B ist die Menge Imp(𝕂) der irreduziblen Implikationen, die 𝕂 erfüllt. Wir betrachten daher im Folgenden Kontexte der Form 𝕂 ∘ 𝔹_{n}.

Der rekursive Aufbau von 𝔹_{n} hat es ermöglicht, zu 𝕂 die Menge Imp(𝕂) zu konstruieren. Umgekehrt ist die rekursive Struktur von 𝔹_{n} ebenso nützlich, um zu einer gegebenen Menge G von irreduziblen Implikationen mit höchstens n Merkmalen einen entsprechenden Kontext zu finden, der alle Implikationen in G erfüllt. Um den Aufwand zu reduzieren, ist es angebracht, sich dabei auf eine möglichst kleine zu G äquivalente Menge von Implikationen zu beschränken und für diese den Kontext zu bestimmen. Der Algorithmus 5.15 lässt sich dabei nutzbringend einsetzen.

15das heißt: für jedes a ∈ A und jedes U → V ∈ B gilt a ⊢ U → V, und sowohl A, als auch B sind inklusionsmaximal für diese Eigenschaft.

Eine andere Möglichkeit, sich die Menge G vorzugeben, ist, eine Teilmenge F ⊆ G dadurch zu spezifizieren, dass man einen Kontext 𝕂_{F} angibt, von dem man schon weiß, dass er die Eigenschaft Imp(𝕂_{F}) ≡ F hat, und die restlichen Bedingungen explizit zu erzwingen. Ist 𝕂_{F} ein solcher Kontext, dann betrachten wir 𝕂_{F} ∘ 𝔹_{n} für das passende n ∈ ℕ. Die Begriffsinhalte dieses Kontextes sind die abgeschlossenen Implikationenmengen, die F enthalten, also ist \underline{𝔅}(𝕂_{F} ∘ 𝔹_{n}) der Verband aller Hüllensysteme auf dem Verband der Begriffsinhalte von 𝕂_{F}.

Dabei benutzen wir eine Verallgemeinerung des Begriffs „Hüllensystem”: Eine Teilmenge 𝔘 eines vollständigen Verbands 𝔙 heißt ein Hüllensystem auf 𝔙, wenn gilt

𝔛 ⊆ 𝔘 ⟹ inf 𝔛 ∈ 𝔘

In dieser Situation sind wir zum Beispiel, wenn wir den Kongruenzenverband einer algebraischen Struktur mit n−elementiger Grundmenge M konstruieren wollen. Den Verband aller Äquivalenzrelationen haben wir als Kontext ℙ_{n} gegeben, und wir wissen schon, dass Imp(ℙ_{n}) die von der Transitivität {{x, y}, {y, z}} → {x, z} (durch Instantiierung x, y, z ∈ M und durch Abschluss unter Anwendung der Armstrongaxiome) erzeugte Implikationenmenge ist. Zusätzlich muss noch die Verträglichkeit mit allen Operationen garantiert werden, was für jede k−stellige Operation f die Implikationen

{{x_{i}, y_{i}}} → {f(x_{1}, …, x_{i−1}, x_{i}, x_{i+1}, …, x_{k}), f(x_{1}, …, x_{i−1}, y_{i}, x_{i+1}, …, x_{k})}

(15)

für alle i ∈ {1, …, k} und alle x_{1}, …, x_{k}, y_{i} ∈ M erforderlich macht.

Am Beispiel der zyklischen Gruppe (ℤ_{4}, +) und der Gruppe (ℤ_{2} × ℤ_{2}, +) zeigen wir, wie man den Kongruenzenverband konstruieren kann, indem man einen Kontext angibt, dessen Begriffsverband zu diesem Kongruenzenverband isomorph ist. Den Verband aller Äquivalenzrelationen auf einer vierelementigen Menge {a, b, c, d} haben wir schon im Teil A.1 durch den Kontext ℙ_{4} beschrieben. Weiter identifizieren wir die Elemente 0, 1, 2, 3 von ℤ_{4} mit a, b, c, d und nützen aus, dass b dann ein erzeugendes Element von ℤ_{4} ist. Auf diese Weise müssen wir nach (15) und wegen der Kommutativität nur noch fordern:

{{a, b}} → {b, c}, {{b, c}} → {c, d}, {{a, c}} → {b, d}, {{c, d}} → {a, d}, {{b, d}} → {a, c}, {{a, d}} → {a, b} Umgeschrieben in Merkmale von X_{6} heißt dies:

(1, •, 0, 0, 0, 0), (0, 1, 0, •, 0, 0), (0, 0, 1, 0, •, 0), (0, 0, 0, 1, 0, •),
(0, 0, •, 0, 1, 0), (•, 0, 0, 0, 0, 1)

Wir müssen also im Kontext

ℙ_{4} ∘ 𝔹_{6} = ({g^{ℙ_{4}} | g ∈ 2^{3}}, X_{6}, ⊢)

- wobei die Zeile ℙ_{4} ∘ 𝔹_{6}(∅) wieder überflüssig ist - die Spalten 145, 53, 22, 9, 15, 82 untersuchen und feststellen, welche Gegenstände alle diese Implikationen respektieren. Es stellt sich heraus, dass es nur einen Gegenstand gibt, der dies erfüllt, nämlich (0, 0, 1, 0, 1, 0). Das Ergebnis ist also der einzeilige Kontext, der nur aus der sechsten Zeile von ℙ_{4} besteht, und dessen Begriffsverband ist tatsächlich der Kongruenzenverband von ℤ_{4}.

Dieselbe Konstruktion für die Gruppe ℤ_{2}×ℤ_{2} mit der Zuordnung (0, 0) ↔ a, (0, 1) ↔ b, (1, 0) ↔ c, (1, 1) ↔ d liefert

{{a, b}} → {c, d}, {{b, c}} → {a, d}, {{a, c}} → {b, d}, {{c, d}} → {a, b}, {{b, d}} → {a, c}, {{a, d}} → {b, c}

Die entsprechenden Spalten in ℙ_{4} ∘ 𝔹_{6} haben die folgenden Merkmale mit den zugehörigen Spaltennummern

(1, 0, 0, •, 0, 0) ≈ 117, (0, 1, 0, 0, 0, •) ≈ 49, (0, 0, 1, 0, •, 0) ≈ 22
(•, 0, 0, 1, 0, 0) ≈ 85, (0, 0, •, 0, 1, 0) ≈ 15, (0, •, 0, 0, 0, 1) ≈ 34

Als Gegenstände, die diese Implikationen respektieren, erhält man (0, 0, 1, 0, 1, 0), (0, 1, 0, 0, 0, 1) und (1, 0, 0, 1, 0, 0), das sind die sechste, siebte und vierte Zeile von ℙ_{4}. (1, 0, 0, 1, 0, 0) beschreibt den Kern der Projektion ℤ_{2}×ℤ_{2} ⟶ ℤ_{2} auf die erste Komponente, (0, 0, 1, 0, 1, 0) beschreibt den Kern der Projektion auf die zweite Komponente, und (1, 0, 0, 1, 0, 0) beschreibt den Kern des Morphismus (x_{1}, x_{2}) ↦ x_{1}+x_{2}. Insgesamt hat also der Kontext, der aus der vierten, sechsten und siebten Zeile von ℙ_{4} besteht, als Begriffsverband den zum Kongruenzenverband von ℤ_{2} × ℤ_{2} isomorphen Verband.

A.2.2 Unterverbände

Im vorhergehenden Abschnitt haben wir gesehen, dass für manche Anwendungen nicht die volle Information, die im Kontext 𝔹 steckt, notwendig ist. Insbesondere genügt zur Berechnung des Kongruenzenverbandes einer Algebra wegen der Bedingung (15) der Teil von 𝔹, der nur Implikationen der Form {x} → {y} als Merkmale benutzt, wobei x, y ∈ M. Implikationen dieser einfachen Form heißen manchmal unär [2, 5]. Die Bedeutung dieses Spezialfalls liegt darin, dass dann der zugehörige Abschlussoperator topologisch ist, d.h. der Abschluss der Vereinigung zweier Mengen stimmt mit der Vereinigung der Abschlüsse überein. In unserer Situation, in der wir Hüllensysteme auf vollständigen Verbänden – nicht notwendigerweise Potenzmengenverbänden – betrachten, heißt dies: Hüllenbildung ist mit Supremumbildung verträglich, also ist die Menge aller abgeschlossenen Elemente des Verbandes ein Unterverband. Es folgt also auch aus diesen Betrachtungen die bekannte Tatsache, dass für jede algebraische Struktur der Kongruenzrelationenverband ein Unterverband des Äquivalenzrelationenverbandes ist.

Zur Berechnung des Teilkontexts 𝔼_{n} von 𝔹_{n}, der nur aus all den Spalten besteht, die zu unären Implikationen gehören, gehen wir wieder so vor, wie bei ℍ_{n} und bei 𝔹_{n}, indem wir eine induktive Konstruktion angeben:

Es seien

𝔼_{2} = \begin{aligned}× & × \\ & × \\ × \\ × & × \end{aligned} , 𝔽_{1} = ×

𝔼_{n+1} = \begin{matrix}𝔼_{n} & 𝔽_{n} & × \\ 𝔼_{n} & × & 𝔽_{n}↑ \end{matrix} (n ≥ 2) und 𝔽_{n+1} = \frac{𝔽_{n}^{1}}{𝔽_{n}^{0}} (n ≥ 1)  (16)

Dabei bezeichne 𝔽_{n}^{0} den Kontext 𝔽_{n} mit einer rechts angehängten Leerspalte, 𝔽_{n}^{1} den Kontext 𝔽_{n} mit einer rechts angehängten Vollspalte, und 𝔽_{n}↑ den Kontext, der aus 𝔽_{n} entsteht, wenn man seine Zeilen in umgekehrter Reihenfolge aufschreibt^{16}. Dies ergibt also die Kontexte

𝔽_{1}^{0} = × , 𝔽_{1}^{1} = \begin{aligned}× & × \\ & × \end{aligned} , 𝔽_{2} = \begin{aligned}× & × \\ & × \\ × \end{aligned}

Als weitere Kontexte erhalten wir

16Die Zeile Nummer k von 𝔽_{n}↑ ist die Binärdarstellung von k − 1 in umgekehrter Reihenfolge der Bits.

𝔼_{3} = \begin{aligned}& 0 & 0 & • & • & 1 & 1 \\ & • & 1 & 0 & 1 & 0 & • \\ & 1 & • & 1 & 0 & • & 0 \\ 000 & × & × & × & × & × & × \\ 001 & & × & & × & × & × \\ 010 & × & & × & & × & × \\ 011 & × & × & & & × & × \\ 100 & × & × & × & × \\ 101 & & × & × & × & × \\ 110 & × & & × & × & & × \\ 111 & × & × & × & × & × & × \end{aligned}

𝔽_{3} = \begin{aligned}& • & • & • \\ & 0 & 0 & 1 \\ & 0 & 1 & 0 \\ & 1 & 0 & 0 \\ 0000 & × & × & × \\ 0001 & & × & × \\ 0010 & × & & × \\ 0011 & & & × \\ 0100 & × & × \\ 0101 & & × \\ 0110 & × \\ 0111 \end{aligned} , 𝔽_{3}↑ = \begin{aligned}& 1 & 1 & 1 \\ & 0 & 0 & • \\ & 0 & • & 0 \\ & • & 0 & 0 \\ 1000 \\ 1001 & × \\ 1010 & & × \\ 1011 & × & × \\ 1100 & & & × \\ 1101 & × & & × \\ 1110 & & × & × \\ 1111 & × & × & × \end{aligned}

Dabei benutzen wir die folgende Codierung für unäre Implikationen:

Zunächst drücken wir die Implikation {u} → {v} mit u, v ∈ M = {n, …, 1} und u ≠ v durch ihren 0, •, 1−Vektor x ∈ X_{n} aus: Für u = i, v = j ≠ i und 0 ≤ k ≤ n − 1 ist dann x = (x_{n−1}, …, x_{0}) mit

x_{k} = \{ \begin{matrix}1, & falls k = i − 1 \\ •, & falls k = j − 1 \\ 0, & sonst \end{matrix}

Die Menge Z_{n} aller solcher Vektoren ist als Teilmenge von X_{n} wieder lexikographisch geordnet. Die lexikographische Position dieses Vektors innerhalb Z_{n} erhalten wir, indem wir jedem x = (x_{n−1}, …, x_{0}) mit x_{j} = • und x_{i} = 1 die Zahl

s(x_{n−1}, …, x_{0}) = 1 + \{ \begin{matrix}j(j − 1) + i, & falls i < j \\ i^{2} + j, & falls i > j \end{matrix}

zuordnen. Umgekehrt läßt sich aus der Position s der Vektor zurückrechnen. Dazu benutzen wir die folgende Eigenschaft: Für jedes t ∈ ℕ gibt es genau ein r ∈ ℕ mit r^{2} ≤ t < (r + 1)^{2};

falls t − r^{2} < r, dann setze i(t) := r,  j(t) := t − r^{2},
falls t − r^{2} ≥ r, dann setze j(t) := r + 1, i(t) := t − r^{2} − r.

Dann ist der Vektor x(t) = (x_{n−1}, …, x_{0}) mit

x_{k} = \{ \begin{matrix}1, & falls k = i(t) \\ •, & falls k = j(t) \\ 0, & sonst \end{matrix}

die Codierung einer unären Implikation und die Abbildung s ↦ x(s − 1) eine Bijektion zwischen {1, …, n(n − 1)} und Z_{n} für jedes n ∈ ℕ.

Wie früher überzeugen wir uns zunächst davon, dass der konstruierte Kontext 𝔼_{n} das behauptete leistet:

Für n = 2 ist der Kontext 𝔼_{2} derjenige Teilkontext von 𝔹_{2}, der aus den Spalten mit unärer Implikation besteht, und 𝔽_{2} sowie 𝔽_{2}↑ sind der jeweils passende Teilkontext von 𝔼_{3}.

Für n ≥ 2 erklärt sich der Aufbau von 𝔼_{n+1} durch die folgende Betrachtung, wobei wieder ∗ der zu M neu hinzukommende Punkt ist: 𝔼_{n+1} ist Erweiterung von 𝔼_{n}, denn für alle X ∈ 2^{n}, {u} → {v} ∈ Z_{n} ist

X ⊢ {u} → {v} in 𝔼_{n} ⟺ X ⊢ {u} → {v} in 𝔼_{n+1}.

Für alle u ∈ M und für alle Gegenstände X ∈ 2^{n} ist X ⊢ {∗} → {u} und X + {∗} ⊢ {u} → {∗}, was die beiden × in der Definition von 𝔼_{n+1} erklärt. Weiter gilt

X ⊢ {u} → {v} ⟺ X + {∗} ⊢ {u} → {v}.

Es bleiben die Fälle

X ∈ 2^{n} und {u} → {∗} mit u ∈ M
X + {∗} mit X ∈ 2^{n} und {∗} → {u}, u ∈ M

zu untersuchen, von denen wir zeigen, dass 𝔽_{n} und 𝔽_{n} ↑ sie beschreiben. Die beiden Fälle sind zueinander komplementär, denn es gilt

X ⊢ {u} → {∗} ⟺ X + {∗} ⊬ {∗} → {u} für alle X ∈ 2^{n}, u ∈ M

also bleibt noch die Rekursion für 𝔽_{n+1} mit n > 1 zu zeigen.

𝔽_{n+1} ist ein Teilkontext von 𝔼_{n+2}. Der Übergang von n+1 nach n+2 werde wieder durch Adjunktion eines weiteren Punktes ∗∗ realisiert. Die Merkmale von 𝔽_{n+1} sind die {u} → {∗∗} mit u ∈ M + {∗}, sind also von der Form {u} → {∗∗} mit u ∈ M oder {∗} → {∗∗}.

Die Gegenstände des Kontexts 𝔽_{n+1} enthalten jeweils das Element ∗∗ nicht; wir teilen sie wieder ein in die Gegenstände, die ∗ als Element enthalten und die, die ∗ nicht enthalten.

Für diejenigen Gegenstände X, die ∗ nicht enthalten,gilt X ⊢ {∗} → {∗∗} und für die, die ∗ enthalten, gilt X ⊬ {∗} → {∗∗}. Dies rechtfertigt das Anhängen der Leerspalte bzw. Vollspalte an 𝔽_{n}.

Schließlich gilt für alle Gegenstände X ∈ 2^{n}, u ∈ M

X ⊢ {u} → {∗} ⟺ X ⊢ {u} → {∗∗} ⟺ X + {∗} ⊢ {u} → {∗∗}.

Damit ist gezeigt, dass 𝔼_{n+1} aus 𝔼_{n} induktiv so aufgebaut wird, wie in (16) beschrieben, und wir definieren wieder

𝔼 := lim_{n≥0} 𝔼_{n}

Wie früher machen wir uns die reguläre Struktur von 𝔼_{n} zunutze, um für eine gegebene Menge F ⊆ Z_{n} unärer Implikationen den Teilkontext von 𝕂 = (G, M, I) mit M = {n, …, 1} und n ≥ 2 zu bestimmen, der diese Implikationenmenge erfüllt. Dazu müssen wir für eine gegebene Implikation {u} → {v} ∈ F mit u, v ∈ M, u ≠ v, die Menge aller Gegenstände von 𝕂, deren Merkmalmenge die Implikation respektiert, berechnen. Die Implikation {u} → {v} in F sei dargestellt durch ihren 0, •, 1−Vektor (x_{n−1}, …, x_{0}). Damit definiert sich die zugehörige Spalte von 𝔼_{n}, wobei wir wieder die Abkürzung x_{[k]} für (x_{k−1}, …, x_{0}) benutzen, folgendermaßen: Für n = 2 gilt

(x_{[2]})^{𝔼_{2}} = \{ \begin{matrix}1, 0, 1, 1, & falls x_{1} = • \\ 1, 1, 0, 1, & falls x_{1} = 1 \end{matrix}

(x_{[2]})^{𝔽_{2}} = \{ \begin{matrix}1, 1, 0, 0, & falls x_{1} = 1 \\ 1, 0, 1, 0, & falls x_{1} = 0 \end{matrix} und (x_{[2]})^{𝔽_{2}↑} = \{ \begin{matrix}0, 0, 1, 1, & falls x_{1} = • \\ 0, 1, 0, 1, & falls x_{1} = 0 \end{matrix}

und für n > 2 ist

(x_{[n]})^{𝔼_{n}} = \{ \begin{matrix}(x_{[n−1]})^{𝔼_{n−1}}, (x_{[n−1]})^{𝔼_{n−1}}, & falls x_{n−1} = 0 \\ (x_{[n−1]})^{𝔽_{n−1}}, 1^{2^{n−1}}, & falls x_{n−1} = • \\ 1^{2^{n−1}}, (x_{[n−1]})^{𝔽_{n−1}↑}, & falls x_{n−1} = 1 \end{matrix}

(x_{[n]})^{𝔽_{n}} = \{ \begin{matrix}(x_{[n−1]})^{𝔽_{n−1}}, (x_{[n−1]})^{𝔽_{n−1}}, & falls x_{n−1} = 0 \\ 1^{2^{n−1}}, 0^{2^{n−1}}, & falls x_{n−1} = 1 \end{matrix}

(x_{[n]})^{𝔽_{n}↑} = \{ \begin{matrix}(x_{[n−1]})^{𝔽_{n−1}↑}, (x_{[n−1]})^{𝔽_{n−1}↑}, & falls x_{n−1} = 0 \\ 0^{2^{n−1}}, 1^{2^{n−1}}, & falls x_{n−1} = 1 \end{matrix}

Das komponentenweise Produkt der Vektoren (x_{[n]})^{𝔼_{n}} mit x ∈ F beschreibt die Zeilen des Kontextes 𝕂, die alle Implikationen von F respektieren. Sie definieren einen Teilkontext von 𝕂, dessen Begriffsverband der Unterverband von \underline{𝔅}(𝕂) ist, dessen Begriffsinhalte den zusätzlichen Bedingungen F genügen.

Für eine gegebene algebraische Struktur auf einer n−elementigen Menge kann man deren Kongruenzenverband dadurch konstruieren, dass man für den Kontext ℙ_{n} diese Konstruktion durchführt und dann für den Kontext 𝔼\binom{n}{2} die Menge F nach (15) wählt. Man erhält einen Teilkontext von ℙ_{n}, dessen Begriffsverband (bis auf Anti-Isomorphie) der Kongruenzenverband der gegebenen Struktur ist.