%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[12pt,a4paper,german]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \newenvironment{lyxlist}[1]
   {\begin{list}{}
     {\settowidth{\labelwidth}{#1}
      \setlength{\leftmargin}{\labelwidth}
      \addtolength{\leftmargin}{\labelsep}
      \renewcommand{\makelabel}[1]{##1\hfil}}}
   {\end{list}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{rotating}
\usepackage{amsthm}
\usepackage{amsxtra}


\newtheorem{Thm}{Theorem}[section]
\newtheorem{Satz}[Thm]{Satz}
\newtheorem{Lemma}[Thm]{Lemma}
\newtheorem{Kor}[Thm]{Korollar}
\newtheorem{Algo}[Thm]{Algorithmus}


\newtheorem{Ueb}{Aufgabe}[section]
\newtheorem{Def}[Thm]{Definition}
\newtheorem{Bei}[Thm]{Beispiel}
\newtheorem{Bem}[Thm]{Bemerkung}
\newtheorem{B+E}[Thm]{Beispiele und Eigenschaften}

\usepackage{babel}
\makeatother
\begin{document}

\title{Endliche Hüllensysteme\\
und ihre Implikationenbasen}


\author{Roman König%
\footnote{Adresse: Universität Erlangen-Nürnberg, Institut für Informatik III,
Martensstraße 3, \protect \\
D - 91058 Erlangen. \texttt{koenig@informatik.uni-erlangen.de}%
}}


\date{}

\maketitle

\begin{abstract}
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 \emph{kanonische Antikette}
liefert dieser eine Implikationenbasis, die ,,kompakter'' als die
sogenannte \emph{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. 
\end{abstract}

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 49 \rms (2003), Article~B49g\hfill}
\def\thepage{}
%
%

\newpage


\tableofcontents{}

\vspace{40pt}


%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
%\markboth{\SMALL STEEN RYOM--HANSEN}{\SMALL LITTELMANN'S REFINED DEMAZURE 
%CHARACTER FORMULA}

\section{\label{sec:Einleitung}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 \cite{key-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 \ref{sec:Implikationen} und \ref{sec:Die-Kontexte-H-und-B}
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\rightarrow 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 $\mathbb{H}$ als Limes einer Folge $\mathbb{H}_{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 \cite{key-15} und \cite{key-11}. 

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

Die Definition des Kontexts $\mathbb{H}_{n}$ erscheint in \cite{key-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 $\mathbb{H}_{n}$ im Kapitel \ref{sec:Die-Kontexte-H-und-B}
wird es möglich, die Menge $Imp(\mathbb{K})$ aller Implikationen,
die in einem gegebenen Kontext $\mathbb{K}$ mit $n$ Merkmalen gelten,
effektiv anzugeben, ohne das Hüllensystem, das durch $\mathbb{K}$
beschrieben wird, zu kennen. Durch vorhergehende Spaltenreduktion
des Kontexts $\mathbb{H}_{n}$ zu $\mathbb{B}_{n}$ kann auch die
Menge aller \emph{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 \ref{Anhang1:Ein-Beispiel} und \ref{Anhang2:Konstruktion-von-Teilsystemen}
ausgeführt.


\section{\label{sec:Grundlagen}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 $\mathbb{K}=(G,M,I)$ ein Kontext. Für $A\subseteq G$ sei
\[
A^{I}:=\{ m\in M\,|\,\,\mathrm{f}\ddot{\mathrm{u}}\mathrm{r}\,\mathrm{alle}\, g\in A\,\mathrm{ist}\,(g,m)\in I\}\]
 und für $B\subseteq M$ sei \[
B^{I}:=\{ g\in G\,|\,\,\mathrm{f}\ddot{\mathrm{u}}\mathrm{r}\,\mathrm{alle}\, m\in B\,\mathrm{ist}\,(g,m)\in 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^{\mathbb{K}}$
statt $A^{I}$ und $B^{\mathbb{K}}$ statt $B^{I}$. Dies ist besonders
angebracht, wenn $\mathbb{K}$ Teilkontext eines Kontexts $\mathbb{L}=(H,N,J)$
ist, wenn also $G\subseteq H,M\subseteq N$ und $I=J\cap(G\times M)$
ist. 

Für spätere Anwendungen ist es nützlich, einen Kontext $\mathbb{K}$
als Paar von adjungierten Abbildungen\[
\begin{array}{cc}
g\mapsto g^{\mathbb{K}} & m\mapsto m^{\mathbb{K}}\\
G\longrightarrow\mathfrak{P}(M) & M\longrightarrow\mathfrak{P}(G)\end{array}\]
zu sehen%
\footnote{Tatsächlich sind diese Abbildungen die Restriktionen der beiden zueinander
adjungierten Abbildungen $\mathfrak{P}(G)\longrightarrow\mathfrak{P}(M)$
und $\mathfrak{P}(M)\longrightarrow\mathfrak{P}(G)$ jeweils auf die
Menge der einelementigen Teilmengen.%
}. $\mathbb{K}$ heißt bereinigt, wenn diese beiden Abbildungen injektiv
sind. Ist die erste injektiv, dann heißt $\mathbb{K}$ gegenstands-
oder zeilenbereinigt, ist die zweite injektiv, dann heißt $\mathbb{K}$
merkmals- oder spaltenbereinigt. 

Da die eine dieser Abbildungen die andere eindeutig bestimmt (vgl.
z.B. \cite{key-3}, Kap. 0.4), genügt eine von beiden zur Beschreibung
eines Kontexts. Wir wählen die Abbildung $g\mapsto g^{\mathbb{K}}$
und nennen diese wieder%
\footnote{Es entspricht gängiger Praxis, Relationen sowohl als Teilmengen von
$G\times M$, als auch als Abbildungen $G\rightarrow\mathfrak{P}(M)$
zu betrachten.%
} $\mathbb{K}$, also \[
\mathbb{K}:G\longrightarrow\mathfrak{P}(M),\,\, g\mapsto\mathbb{K}(g):=g^{\mathbb{K}}\]
Man beachte, dass für Teilmengen $A$ von $G$ die Merkmalmengen $A^{\mathbb{K}}=\{ m\in M\,|\,\textrm{für alle }g\in A\textrm{ ist }(g,m)\in I\}$
und $\mathbb{K}(A)=\{\mathbb{K}(g)\,|\, g\in A\}=\{ g^{\mathbb{K}}\,|\, g\in A\}$
im Allgemeinen verschieden sind. 

\begin{Def}\label{Def:Komposition}\emph{Es seien der Kontext $\mathbb{K}=(G,M,I)$
und ein zweiter Kontext $\mathbb{S}=(\mathfrak{P}(M),X,J)$ gegeben.
Die} Komposition \emph{$\mathbb{K}\circ\mathbb{S}$ von $\mathbb{K}$
und $\mathbb{S}$ definieren wir durch \[
(\mathbb{K}\circ\mathbb{S})(g):=\mathbb{S}(\mathbb{K}(g))=\mathbb{S}(g^{\mathbb{K}})\]
für alle $g\in G$. Damit ist $\mathbb{K}\circ\mathbb{S}$ der Kontext
$\mathbb{K}\circ\mathbb{S}=(G,X,\widetilde{J})$ mit \[
(g,x)\in\widetilde{J}\iff(\mathbb{K}(g),x)\in J\]
}

\end{Def}

$\mathbb{K}\circ\mathbb{S}$ ist isomorph zu dem Teilkontext von $\mathbb{S}$,
der bestimmt wird durch die Zeilen von $\mathbb{K}$, wobei Zeilen
mehrfach auftreten können, wenn $\mathbb{K}$ nicht bereinigt ist. 

Die Elemente $(A,B)$ mit $A'=B$ und $B'=A$ heißen Begriffe des
Kontexts $\mathbb{K}$ und bestehen aus dem \emph{Begriffsumfang}
$A$ und dem \emph{Begriffsinhalt} $B$. Die Menge \[
\underline{\mathfrak{B}}(\mathbb{K})=\{(A,B)\,|\, A\subseteq G,B\subseteq M,A'=B,B'=A\}\]
mit der Ordnung \[
(A,B)\le(C,D)\iff A\subseteq C\,\,(\iff B\supseteq D)\]
ist der zugehörige Begriffsverband. $\underline{\mathfrak{B}}(\mathbb{K})$
ist ein vollständiger Verband. Für Teilmengen $\mathcal{B}\subseteq\underline{\mathfrak{B}}\mathcal{(}\mathbb{K}\mathcal{)}$
werden Infimum und Supremum folgendermaßen berechnet: \label{1}\begin{equation}\begin{split}
\bigwedge\mathcal{B} = (\bigcap_ {(A,B) \in \mathcal{B}}A, (\bigcup_ {(A,B) \in \mathcal{B}}B)'' ) &= (\bigcap_ {(A,B) \in \mathcal{B}}A, (\bigcap_ {(A,B) \in \mathcal{B}}A)' ) \\
&= ((\bigcup_ {(A,B) \in \mathcal{B}}B)' , (\bigcup_ {(A,B) \in \mathcal{B}}B)'' ) \\
\end{split}\end{equation}
und\\
\label{2}\begin{equation}\begin{split}
\bigvee\mathcal{B} = ((\bigcup_ {(A,B) \in \mathcal{B}}A)'', \bigcap_ {(A,B) \in \mathcal{B}}B ) &= ((\bigcap_ {(A,B) \in \mathcal{B}}B)', \bigcap_ {(A,B) \in \mathcal{B}}B ) \\
&= ((\bigcup_ {(A,B) \in \mathcal{B}}A)'' , (\bigcup_ {(A,B) \in \mathcal{B}}A)' ) \\
\end{split}\end{equation}
Insbesondere ist der Verband $\underline{\mathfrak{B}}(\mathbb{K})$
isomorph zum Verband aller Begriffsumfänge und antiisomorph zum Verband
aller Begriffsinhalte. Diese Verbände sind jeweils durch Inklusion
(auf $\mathfrak{P}(G)$ bzw. $\mathfrak{P}(M)$) geordnet und Hüllensysteme
auf den jeweiligen Mengen. Die abgeschlossenen Gegenstandsmengen (=
Begriffsumfänge) sind die Mengen $A''$ mit $A\subseteq G$, die abgeschlossenen
Merkmalmengen (= Begriffsinhalte) sind die $B''$ mit $B\subseteq M$. 

Das Hüllensystem aller Begriffsumfänge wird erzeugt von den \emph{Merkmals\-um\-fängen}
$\{ m\}'$ mit $m\in M$, das aller Begriffsinhalte von den \emph{Gegenstandsinhalten}
$\{ g\}'$ mit $g\in 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 $\mathbb{K}$ bereinigt ist, insbesondere wenn er
bis auf eine Vollzeile oder eine Vollspalte reduziert ist, sind alle
$(\{ g\},\{ g\}')$ mit $g\in G$ und alle $(\{ m\}',\{ m\})$ mit
$m\in M$ Begriffe. 

Hüllensysteme lassen sich bekanntlich adäquat beschreiben durch Abschlussoperatoren.
Ein Abschlussoperator auf einer Menge $M$ ist dabei eine Abbildung
$X\mapsto\overline{X}$ von $\mathfrak{P}(M)$ in sich mit den Eigenschaften%
\footnote{Man sieht ohne Schwierigkeit, dass dieses Axiomensystem äquivalent
ist zu dem üblichen: \[
X\subseteq Y\Rightarrow\overline{X}\subseteq\overline{Y}\textrm{, sowie }X\subseteq\overline{X}\textrm{ und }\overline{\overline{X}}=\overline{X}\]
 %
}
\begin{equation}\label{Hulloperator}\begin{split}
X &\subseteq \overline{X} \\ 
\mathrm{ aus }\quad X\subseteq \overline{Y} &\quad \mathrm{ folgt } \quad \overline{X} \subseteq \overline{Y}
\end{split}\end{equation}
für alle $X,Y\in\mathfrak{P}(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 \ref{sec:Die-Kontexte-H-und-B} konstruiert
wird. 


\section{\label{sec:Implikationen}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\rightarrow V$; man sagt, eine Teilmenge $T$ von $M$ \emph{respektiert}
die Implikation $(U,V),$ wenn gilt: $U\not\subseteq T\text{\, oder\, }V\subseteq T$,
abgekürzt durch\[
T\vdash U\rightarrow V:\iff(U\subseteq T\implies V\subseteq T).\]
Implikationen der Form $U\rightarrow V$ mit $V\subseteq U\subseteq M$
nennen wir \emph{trivial.} Triviale Implikationen werden von jeder
Teilmenge $T$ von $M$ respektiert. 

Die Potenzmenge $\mathfrak{P}(M)$ nehmen wir als Gegenstandsmenge,
die Produktmenge $\mathfrak{P}(M)^{2}=\mathfrak{P}(M)\times\mathfrak{P}(M)$
aller Implikationen nehmen wir als Merkmalmenge des Kontexts \[
\mathbb{H}(M)=(\mathfrak{P}(M),\mathfrak{P}(M)^{2},\vdash).\]
 Die Begriffe des dadurch definierten Begriffsverbands \( \underline{\mathfrak B}(\mathbb H(M)) \) sind die Paare \( (\mathfrak H,\mathcal F) \) mit \( \mathfrak H\subseteq \mathfrak P(M) \) und \( \mathcal F\subseteq \mathfrak P(M)^{2} \), die die Eigenschaft haben, dass\[ \mathfrak H^{\vdash }:=\{(U,V)\, |\, \mathrm {\, f\ddot{u}r\, alle\, }S\in \mathfrak H\mathrm {\, ist\, }\, S\vdash U\rightarrow V\}=\mathcal F\] und\[ \mathcal F^{\vdash }:=\{S\, |\, \mathrm {\, f\ddot{u}r\, alle\, }(U,V)\in \mathcal F\mathrm {\, ist\, }\, S\vdash U\rightarrow V\}=\mathfrak H.\]

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

Also ist der Begriffsverband $\underline{\mathfrak{B}}(\mathbb{H}(M))$
isomorph zum Verband aller Hüllensysteme auf $M$, geordnet durch
Inklusion. Dabei heißt $\mathfrak{H}\subseteq\mathfrak{G}$: Jede
Teilmenge von $M$, die in $\mathfrak{H}$ abgeschlossen ist, ist
auch in $\mathfrak{G}$ abgeschlossen. 

Der Verband $\underline{\mathfrak{B}}(\mathbb{H}(M))$ ist vollständig
und isomorph zu dem Hüllensystem auf der Menge $\mathfrak{P}(M)$,
das erzeugt wird von den Merkmalsumfängen $\{ U\rightarrow V\}^{\vdash}$
mit $(U,V)\in\mathfrak{P}(M)^{2}$; andererseits ist $\underline{\mathfrak{B}}(\mathbb{H}(M))$
antiisomorph zu dem Hüllensystem auf der Menge $\mathfrak{P}(M)^{2}$
aller Implikationen, das erzeugt wird von den Gegenstandsinhalten
$\{ S\}^{\vdash}$ mit $S\in\mathfrak{P}(M)$. Die erzeugende Operation
ist dabei der Durchschnitt von Implikationenmengen, also Teilmengen
von $\mathfrak{P}(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 \( \mathcal F_{t} \) mit \( t\in T \) auch \( \bigcap _{t\in T}\mathcal F_{t} \) wieder abgeschlossen, d.h. von der Form \( \mathfrak S^{\vdash } \) für ein geeignetes \( \mathfrak S\subseteq \mathfrak P(M) \). Sind speziell die \( \mathcal F_{t} \) von der Form \( \mathcal F_{t}=\{S_{t}\}^{\vdash } \) mit \( S_{t}\in \mathfrak P(M) \), so gilt\[ \bigcap _{t\in T}\mathcal F_{t}=\bigcap \{\{S_{t}\}^{\vdash }\, |\, t\in T\}=(\bigcup \{\{S_{t}\}\, |\, t\in T\})^{\vdash }=\{S_{t}\, |\, t\in T\}^{\vdash }.\]

Wegen Gleichung (\ref{2}) gilt dann:
\begin{equation*}
\bigvee_{t \in T}(\mathcal{F}_t^{\vdash},\mathcal{F}_t ) = (\{S_t|t \in T\}^{\vdash\vdash},\{S_t|t \in T \}^{\vdash}).
\end{equation*}

Jeden Begriffsinhalt $\mathcal{F}=\mathfrak{H}^\vdash$ des Kontexts
$\mathbb{H}(M)$ kann man als einen Abschlussoperator betrachten,
wenn man ihn als eine Abbildung $\mathcal{F}: \mathfrak{P}(M) \longrightarrow \mathfrak{P}(M)$
interpretiert, indem man für $X\in\mathfrak{P}(M)$ setzt: ~~\[ \mathcal{F}(X): = \bigcup\{V|U \rightarrow V \in \mathcal{F}, U \subseteq X\}\] Aus
der Eigenschaft $X\vdash\{ x\}\rightarrow\{ x\}$ für alle $X\in\mathfrak{P}(M)$
und alle $x\in M$ folgt \[ X \subseteq \mathcal{F}(X), \] und unmittelbar
aus der Definition der Abbildung \(\mathcal{F}\) ergibt sich \[ \textrm{wenn } X \subseteq \mathcal{F}(Y), \textrm{ dann ist auch }\mathcal{F}(X) \subseteq \mathcal{F}(Y) \]
für alle $X,Y\in\mathfrak{P}(M)$. Damit sind die Eigenschaften (\ref{Hulloperator})
erfüllt und die Abbildung $\mathcal{F}$ ist ein Abschlussoperator.
Dies zeigt, dass jeder Begriff im Verband $\underline{\mathfrak{B}}(\mathbb{H}(M))$
als Umfang ein Hüllensystem und als Inhalt den zugehörigen Abschlussoperator
hat. 

Wir sagen für zwei Implikationenmengen \( \mathcal F \) und \( \mathcal G \), dass \( \mathcal G \) aus \( \mathcal F \) folgt und schreiben \( \mathcal F\models \mathcal G \)\label{Folgerung}, wenn jeder Gegenstand in \( \mathfrak P(M) \), der \( \mathcal F \) respektiert, auch \( \mathcal G \) respektiert, also wenn \( \mathcal F^{\vdash }\subseteq \mathcal G^{\vdash } \) gilt. Wenn sowohl \( \mathcal F\models \mathcal G \), als auch \( \mathcal G\models \mathcal F \) gilt, nennen wir \( \mathcal F \) und \( \mathcal G \) äquivalent und schreiben \( \mathcal F\equiv \mathcal G \). Es
gilt $\mathcal{F} \models \mathcal{G}$ genau dann, wenn $\mathcal{F} \equiv \mathcal{F} \cup \mathcal{G}$.

\begin{proof}[Beispiel]

Es gelten für alle Teilmengen $U,V,W,Z$ von $M$ die folgenden Beziehungen: 
\begin{equation}\label{Armstrongaxiome}\begin{split}
\emptyset&\models \{ U\rightarrow U \} \\
\{U \rightarrow V \} &\models \{ U \cup W \rightarrow V \} \\ 
\{ U \rightarrow V, V \cup W \rightarrow Z \} &\models \{U \cup W \rightarrow Z \}. \\
\end{split}\end{equation} Die Beziehungen (\ref{Armstrongaxiome}) heißen \emph{Armstrongaxiome.}

\renewcommand{\qedsymbol}{}\end{proof}

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

\begin{Satz}

Eine Menge $\mathcal{F}$ von Implikationen ist genau dann von der
Form $\{ S_{t}\,|\, t\in T\}^{\vdash}$ mit $S_{t}\subseteq M$, wenn
sie die Bedingung erfüllt: 

Wenn die Implikationen der linken Seite einer der in (\ref{Armstrongaxiome})
genannten Beziehungen zu $\mathcal{F}$ gehören, dann auch die auf
der rechten Seite.

\end{Satz} 

\begin{proof}

Siehe \cite{key-3}, p.81 und die dort angegebene Literatur.\end{proof}

Für Implikationenmengen gelten die folgenden weiteren Beziehungen:
\begin{align}
\{ U \rightarrow V\} &\equiv \{ U \rightarrow U \cup V \} \label{Aquivalenz 1}\\
\{ U \rightarrow V , U \rightarrow W \} &\equiv \{ U \rightarrow V \cup W\} \label{Aquivalenz 2}\\
\{ U \rightarrow V \} &\equiv \{W \rightarrow V |U \subseteq W \} \label{Aquivalenz 3}\\
\{ U \rightarrow V , U \cup V \cup W \rightarrow Z\} &\equiv \{U \rightarrow V , U \cup W \rightarrow Z \}\label{Aquivalenz 4}.
\end{align}

Äquivalente Implikationenmengen definieren im Begriffsverband\break 
$\underline{\mathfrak{B}}(\mathbb{H}(M))$
denselben Begriffsumfang, also dasselbe Hüllensystem. Jede dieser
Implikationenmengen heißt \emph{vollständig} für dieses Hüllensystem.
Wenn eine Implikationenmenge minimal ist (bezüglich Inklusion in $\mathfrak{P}(\mathfrak{P}(M)\times\mathfrak{P}(M))$
) unter allen Implikationenmengen, die ein gegebenes Hüllensystem
definieren, so heißt diese eine \emph{Implikationenbasis}%
\footnote{In der Literatur findet man den Begriff ,,Implikationenbasis'' auch
als Bezeichnung für jede Implikationenmenge, die ein gegebenes Hüllensystem
definiert. %
} für dieses Hüllensystem. 


\section{\label{sec:Die-Kontexte-H-und-B}Die Kontexte $\mathbb{H}$ und $\mathbb{B}$}


\subsection{Induktive Definition des Kontexts $\mathbb{H}_{n}$ }

Wir bezeichnen mit $\boldsymbol2$ die geordnete Menge $\{0,1\}$
mit 2 Elementen, wobei $0<1$, und identifizieren die Potenzmenge
einer gegebenen Menge $M$ mit $\boldsymbol2^{M}$. $\mathbb{H}(M)$
hat dann die Gegenstandsmenge $\boldsymbol2^{M}$ und die Merkmalmenge
$\boldsymbol2^{M}\times\boldsymbol2^{M}$. 

Wir betrachten nun den Kontext $\mathbb{H}(M)$ für eine $n-$elementige
Menge $M$ $(n\ge0)$. Der Kontext $\mathbb{H}(M)$ hat dann $2^{n}$
Gegenstände und $2^{n}\cdot2^{n}$ Merkmale. Unter den Merkmalen liefert
zunächst nach Äquivalenz (\ref{Aquivalenz 1}) jede Implikation der
Form $U\rightarrow V$ im Kontext $\mathbb{H}(M)$ dieselbe Spalte
wie $U\rightarrow U\cup V$, also genügen die $3^{n}$ Spalten von
$\mathbb{H}(M)$ mit Merkmalen $U\rightarrow V$, für die $U\subseteq V$
ist. Den Teilkontext von $\mathbb{H}(M)$ mit dieser Merkmalmenge
und voller Gegenstandsmenge $\boldsymbol2^{n}$ nennen wir $\mathbb{H}_{n}$. 

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

\begin{Satz}

Für die Kontexte $\mathbb{H}_{n}$ gilt:

\[\mathbb{H}_0 = \begin{matrix}\mbox{\LARGE$\times $}\end{matrix} , \mathbb{L}_0 = \begin{matrix}\mbox{\LARGE$\varnothing $}\end{matrix}\]

\begin{equation}\mathbb{H}_{n+1} = \begin{tabular}{c|c|c}

$\mathbb{H}_n$ & $\mathbb{L}_n$ & $\begin{matrix}\mbox{\LARGE$\times$}\end{matrix}$ \\ \hline $\overset{}{\mathbb{H}_n}$ & $\mathbb{H}_n$ & $\mathbb{H}_n$ \end{tabular}\text{ \label{Rekursion H}und } \mathbb{L}_{n+1} = \begin{tabular}{c|c|c}$\mathbb{L}_n$ & $\mathbb{L}_n$ & $\begin{matrix}\mbox{\LARGE$\times$}\end{matrix}$ \\ \hline

$\overset {}{\mathbb{L}_n}$ & $\mathbb{L}_n$ & $\mathbb{L}_n$

\end{tabular}\quad ( n \ge 0 )\end{equation}Dabei steht, wie üblich, bei bekannten Gegenstands- und Merkmalmengen \(\begin{matrix}\mbox{\LARGE$\times $}\end{matrix}\)
für einen Kontext, in dem jeder Gegenstand mit jedem Merkmal inzidiert,
während \( \begin{matrix}\mbox{\Large$\varnothing$}\end{matrix}\)
für den entsprechenden Kontext ohne Inzidenzen steht. 

\end{Satz}

\begin{proof}

Offenbar beschreibt $\mathbb{H}_{0}$ den Fall $n=0$, denn $\emptyset\vdash\emptyset\rightarrow\emptyset$. 

Nun sei der Kontext $\mathbb{H}_{n}$ bereits bekannt und $*$ ein
neues Element, das an die Menge $M$ adjungiert wird. Die Gegenstandsmenge
$\mathbf{2}^{n+1}$ von $\mathbb{H}_{n+1}$ entsteht dann durch Erweiterung
von $\mathbf{2}^{n}$ um die Elemente $X+\{\ast\}$ mit $X\in\mathbf{2}^{n}$.

Die Merkmalmenge von $\mathbb{H}_{n+1}$ entsteht wegen der Eigenschaft
(\ref{Aquivalenz 1}) durch Erweiterung der Merkmalmenge von $\mathbb{H}_{n}$
um die Elemente $U\rightarrow V+\{*\}$ und $U+\{*\}\rightarrow V+\{*\}$,
wobei $U\rightarrow V$ ein Merkmal in $\mathbb{H}_{n}$ ist, d.h.
$U\subseteq V\in\boldsymbol2^{n}$. Für alle $X\in\boldsymbol2^{n}$
und Implikationen $U\rightarrow V$ von $\mathbb{H}_{n}$ gilt: $X\vdash U\rightarrow V$
in $\mathbb{H}_{n}$ $\iff$ $X\vdash U\rightarrow V$ in $\mathbb{H}_{n+1}$.
Daher ist $\mathbb{H}_{n}$ ein Teilkontext von $\mathbb{H}_{n+1}$. 

Offenbar ist für alle $X\in\boldsymbol2^{n}$ und $U\subseteq V\in\boldsymbol2^{n}$
\[
X\vdash U\rightarrow V\iff X+\{*\}\vdash U\rightarrow V,\]
 was die erste Spalte in der Definition von $\mathbb{H}_{n+1}$ erklärt. 

Für Gegenstände $X+\{*\}$ von $\mathbb{H}_{n+1}$ gilt\begin{align*}X+\{*\}\vdash U\rightarrow V & \iff X+\{*\}\vdash U\rightarrow V+\{*\}\\ & \iff X+\{*\}\vdash U+\{*\}\rightarrow V+\{*\}, \end{align*}
was die untere Zeile in der Definition von $\mathbb{H}_{n+1}$ erklärt. 

Es bleibt also zu untersuchen, welche der Implikationen, die zu $\mathbb{H}_{n+1}$,
aber nicht zu $\mathbb{H}_{n}$ gehören, die Gegenstände $X$ von
$\mathbb{H}_{n}$ respektieren. Die Implikationen $U+\{*\}\rightarrow V+\{*\}$
werden von allen diesen $X$ respektiert, weil $U+\{*\}\not\subseteq X$. 

Also ist als Letztes zu zeigen, dass der Fall $U\rightarrow V+\{*\}$
durch den Kontext $\mathbb{L}_{n}$ beschrieben wird. 

Die Gegenstandsmenge von $\mathbb{L}_{n}$ ist die von $\mathbb{H}_{n}$,
die Merkmalmenge ist \( \{U\rightarrow V+\{*\}\, |\, U \subseteq V\in \mathbf 2^{n}\} \).
Zunächst gilt also \(\mathbb{L}_0 = \mbox{\Large$\varnothing$}\);
denn $\emptyset\nvdash\emptyset\rightarrow\{*\}$. 

Es sei nach Induktionsannahme bereits gezeigt, dass $\mathbb{L}_{n}$
diesen Fall beschreibt, also $\mathbb{L}_{n}=(\boldsymbol2^{n},\{ U\rightarrow V+\{*\}\,|\, U\subseteq V\in\boldsymbol2^{n}\},\vdash)$. 

$\mathbb{L}_{n+1}$ ist ein Teilkontext von $\mathbb{H}_{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 $\mathbb{L}_{n+1}$ sind die $U\rightarrow V+\{**\}$,
wobei $U\rightarrow V$ Merkmal von $\mathbb{H}_{n+1}$ ist, also
können wir sie wieder einteilen in die drei Blöcke $U\rightarrow V+\{**\},U\rightarrow V+\{*\}+\{**\},U+\{*\}\rightarrow V+\{*\}+\{**\},$
wobei jetzt $U\rightarrow V$ ein Merkmal in $\mathbb{H}_{n}$ ist,
also $U\subseteq V\in\boldsymbol2^{n}$. 

Die Gegenstände des Kontexts $\mathbb{L}_{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\in\boldsymbol2^{n}$
und die, die $*$ enthalten, das sind die $X+\{*\}$ mit $X\in\boldsymbol2^{n}$.

Für diejenigen Gegenstände, die $*$ nicht enthalten, gilt:\[
\begin{array}{rl}
 & X\vdash U\rightarrow V+\{**\}\\
\iff & X\vdash U\rightarrow V+\{*\}\textrm{ }+\{**\}\\
\iff & X+\{*\}\vdash U\rightarrow V+\{*\}\textrm{ }+\{**\}\\
\iff & X\vdash U\rightarrow V+\{*\}\textrm{ }\end{array}\]
Dies besagt, dass $\mathbb{L}_{n}$ als Teilkontext zweimal in der
ersten Zeile und einmal in der zweiten Zeile der Definition von $\mathbb{L}_{n+1}$
auftaucht. Für Gegenstände, die $*$ enthalten, gilt folgendes \[
\begin{array}{rl}
 & X+\{*\}\vdash U\rightarrow V+\{**\}\\
\iff & X+\{*\}\vdash U\rightarrow V+\{*\}+\{**\}\\
\iff & X+\{*\}\vdash U+\{*\}+\{**\}\rightarrow V+\{*\}+\{**\}\end{array}\]
 Dies garantiert, dass in der zweiten Zeile der Definition von $\mathbb{L}_{n+1}$
dreimal der gleiche Teilkontext erscheint. Schließlich gilt wegen
$U+\{*\}\not\subseteq X$ in $\mathbb{L}_{n+1}$ stets $X\vdash U+\{*\}\rightarrow V+\{*\}+\{**\}$. 

Dies bestätigt den Aufbau von $\mathbb{L}_{n+1}$ aus $\mathbb{L}_{n}$,
und damit ist gezeigt, dass $\mathbb{H}_{n+1}$ aus $\mathbb{H}_{n}$
induktiv so aufgebaut wird, wie in (\ref{Rekursion H}) beschrieben.
\end{proof}

Da der Kontext $\mathbb{H}_{n+1}$ stets eine Erweiterung des Kontexts
$\mathbb{H}_{n}$ ist, können wir \[
\mathbb{H}:=\lim_{n\ge0}\mathbb{H}_{n}\]
bilden. Der Kontext $\mathbb{H}$ beschreibt alle Hüllensysteme auf
endlichen Mengen. 

Die ersten Kontexte $\mathbb{H}_{n}$ haben demnach die folgende Form: 

\[ \mathbb{H}_{1} = \begin{tabular}{|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}\hline

$\times$ & $ $ & $\times$ \\ \hline $\times$ & $\times$ & $\times$ \\ \hline \end{tabular}\quad,\quad 
\mathbb{H}_{2} = \begin{tabular}{|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}\hline

$\times$ & & $\times$ & $ $ & $ $ & $\times$ & $\times$ & $ \times$ & $\times$ \\ \hline 

$\times$ & $\times$ & $\times$ & & & & $\times$ & $ \times$ & $\times$ \\ \hline \hline 

$\times$ & & $\times$ & $\times$ & & $\times$ & $\times$ & & $\times$ \\ \hline 

$\times$ & $\times$ & $\times$ & $\times$ & $\times$ & $\times$ & $\times$ & $ \times$ & $\times$ \\ \hline 

\end{tabular}\]

\vspace{10pt}

Die Gegenstands- und Merkmalmengen sind \[
\boldsymbol2^{1}\textrm{ und }\{\emptyset\rightarrow\emptyset,\emptyset\rightarrow\{1\},\{1\}\rightarrow\{1\}\}\]
 bzw.$\boldsymbol2^{2}$ und\begin{align*}
\{\emptyset\rightarrow\emptyset,\emptyset\rightarrow\{1\},\{1\}\rightarrow\{1\}\} & \cup\{\emptyset\rightarrow\{*\},\emptyset\rightarrow\{1,*\},\{1\}\rightarrow\{1,*\}\}\\
 & \cup\{\{*\}\rightarrow\{*\},\{*\}\rightarrow\{1,*\},\{1,*\}\rightarrow\{1,*\}\}.\end{align*}


\label{Bem:Bereinigt}\begin{proof}[Bemerkung]

Der Kontext $\mathbb{H}_{n}$ ist weder bereinigt, noch reduziert,
denn er enthält z.B. viele Vollspalten.\renewcommand{\qedsymbol}{}\end{proof} 

\begin{Satz} \label{Satz:Zeilenbereinigt}

Für alle $n\in\mathbb{N}$ gilt:

\begin{enumerate}
\item \label{enu:zeilenbereinigt}Der Teilkontext von $\mathbb{H}_{n}$,
der durch Weglassen der Zeile des Gegenstands $M$ entsteht, ist zeilenbereinigt.
\item Je zwei Gegenstandsinhalte $S^{\vdash}$ und $T^{\vdash}$ von Gegenständen
$S$ und $T$ in $\mathbb{H}_{n}$ mit $S,T\neq M$ sind entweder
gleich oder unvergleichbar.
\end{enumerate}
\end{Satz}

\begin{proof}

\begin{enumerate}
\item Es gilt $S^{\vdash}\neq T^{\vdash}$ für je zwei voneinander verschiedene
Gegenstände $S,T\in\mathbb{H}_{n}$; denn für $T\neq S$ ist o.B.d.A.
$T\setminus S\neq\emptyset$ und es gilt für jedes $x\in T\setminus S$:
$T\vdash\emptyset\rightarrow\{ x\}$, aber $S\nvdash\emptyset\rightarrow\{ x\}$. 
\item Wenn $T^{\vdash}\subseteq S^{\vdash}$ gilt, dann gilt auch\[
T\vdash U\rightarrow V\Longrightarrow S\vdash U\rightarrow V\textrm{ f}\ddot{\textrm{u}}\textrm{r alle }U\subseteq V\subseteq M\]
 Falls $T\neq S$ ist, kann nach \ref{enu:zeilenbereinigt}. nicht
$T\setminus S\neq\emptyset$ sein, weil sonst $T^{\vdash}\nsubseteq S^{\vdash}$
wäre, also folgt $T\subsetneqq S$, und es muss ein $x\in S\setminus T$
geben; außerdem gibt es wegen $S\neq M$ ein $y\in M\setminus S$.
Für dieses gilt dann $T\vdash\{ x\}\rightarrow\{ x,y\}$ und $S\nvdash\{ x\}\rightarrow\{ x,y\}$,
was der Eigenschaft $T^{\vdash}\subseteq S^{\vdash}$ widerspricht.
Also folgt aus $T^{\vdash}\subseteq S^{\vdash}$ schon $T^{\vdash}=S^{\vdash}$
und damit sind alle Gegenstandsbegriffe, außer dem des Gegenstands
$M$, $\lor-$irreduzibel. \hfill \qedsymbol
\end{enumerate}
\renewcommand{\qedsymbol}{}\end{proof}

\begin{proof}[Bemerkung]Der Kontext $\mathbb{L}_{n}$ hat als letzte
Zeile stets eine Leerzeile und der Kontext $\mathbb{H}_{n}$ hat als
letzte Zeile stets eine Vollzeile. 

\renewcommand{\qedsymbol}

\end{proof}

\begin{Kor}\label{Kor:zeilenreduziert}

Der Kontext $\mathbb{H}_{n}$ ist bis auf die letzte Zeile zeilenreduziert. 

\end{Kor}


\subsection{Induktive Definition des Kontexts $\mathbb{B}_{n}$}

Wegen der Äquivalenz (\ref{Aquivalenz 2}) ist in $\mathbb{H}_{n}$
jedes Merkmal reduzibel, das nicht von der Form $U\rightarrow V$
mit $|V|=|U|+1$ ist. Wir bezeichnen die Merkmalmenge $\{ U\rightarrow V\,|\, U,V\in\boldsymbol2^{n},|V|=|U|+1\}$
mit dem Symbol \( \mathcal X_{n} \) und den Kontext \( (\boldsymbol 2^{n},\mathcal X_{n},\vdash ) \)
mit $\mathbb{B}_{n}$. $\mathbb{B}_{n}$ ist die Einschränkung des
Kontexts $\mathbb{H}_{n}$ auf die Merkmalmenge $\mathcal{X}_{n}$.

\begin{Satz}\label{Satz:Rekursion_Bn}

Die Kontexte $\mathbb{B}_{n}$ genügen der folgenden Rekursion:

\[\mathbb{B}_1 = \begin{tabular}{|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}\hline 

\\ \hline

$\times $ \\ \hline

\end{tabular} \; , \mathbb{A}_1= \begin{tabular}{|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}\hline 

$\phantom{\times}$ & $\times$ \\ \hline

& \\ \hline

\end{tabular}\]

\begin{equation}\mathbb{B}_{n+1} = \begin{tabular}{c|c|c}

$\mathbb{B}_n$ & $\mathbb{A}_n$ & $\mbox{\LARGE$\times$}$ \\ \hline 

$\mathbb{B}_n$ & ${\mbox{\LARGE$\times$}}$ & $\mathbb{B}_n$ \end{tabular}\text{ \label{Rekursion B}~und } \mathbb{A}_{n+1}=\begin{tabular}{c|c} $\mathbb{A}_n$ & $\mbox{\LARGE$\times$}$ \\ \hline 

$\overset{}{\mathbb{A}_n}$ & $\overset{}{\mathbb{A}_n}$

\end{tabular}\quad ( n \ge 1 )\end{equation}

\end{Satz}

\label{Beispiel:B2_und_B3}\begin{proof}[Beispiel]Nach dieser Regel
ergeben sich die ersten Kontexte zu

\[ \mathbb{B}_{2} = \begin{tabular}{|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}\hline

$ $ & $ $ & $\times$ & $\times$ \\ \hline $\times$ & $ $ & $ $ & $\times$ \\ \hline \hline

$ $ & $ \times$ & $\times$ & $ $ \\ \hline $\times$ & $\times $ & $ \times$ & $\times$ \\ \hline

\end{tabular}\; ,  \mathbb{A}_{2} = \begin{tabular}{|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}\hline

$\phantom{\times} $ & $\times $ & $\times$ & $\times$ \\ \hline $ $ & $ $ & $\times $ & $\times$ \\ \hline \hline

$ $ & $ \times$ & $ $ & $ \times $ \\ \hline $ $ & $ $ & $ $ & $ $ \\ \hline

\end{tabular} \]

\[\mathbb{B}_{3}= \begin{tabular}{|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}\hline 

$ $ & $ $ & $\times$ & $ \times$ & $ $ & $\times$ & $\times$ & $ \times$ & $\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

$\times$ & $ $ & $ $ &$\times$ & & & $\times$ & $ \times$ &$\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

$ $ & $\times$ & $\times$ & $ $ & & $\times$ & $$ &$\times$ & $\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

$\times$ & $\times$ & $\times$ & $\times$ & $$ & $$ & $$ & $ $ &$\times$& $\times$ & $ \times$ & $\times$ \\ \hline \hline

$$ &$ $ & $\times$ & $\times$ & $\times$ & $\times $ & $\times$ & $\times$ & $$ & $$ & $\times$ & $\times$ \\ \hline 

$\times$ & $ $ & $ $ &$\times$ &$\times$ & $\times$& $\times$ & $ \times$ & $\times$ & $$ & $$ & $\times$ \\ \hline 

$ $ & $\times$ & $\times$ & $ $ & $\times$& $\times$ & $\times$ &$\times$ & $$ &$\times$ &$\times$ & \\ \hline 

$\times$ & $\times$ & $\times$ & $\times$ & $\times$ &$\times$ & $\times$ & $\times$ & $\times$ & $\times$ &$\times$ & $\times$ \\ \hline

\end{tabular} \; , \mathbb{A}_{3}= \begin{tabular}{|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}\hline

$\phantom{\times} $ & $ \times$ & $\times$ & $ \times$ & $\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

$ $ &$ $ & $\times$ & $ \times$ &$\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

$ $ & $\times$ & $$ &$\times$ & $\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

$ $ & $$ & $$ & $ $ &$\times$& $\times$ & $ \times$ & $\times$ \\ \hline \hline

$ $ & $\times $ & $\times$ & $\times$ & $$ & $\times$ & $\times$ & $\times$ \\ \hline 

$ $ & $ $& $\times$ & $ \times$ & $ $ & $$ & $\times$ & $\times$ \\ \hline 

$ $& $\times$ & $ $ &$\times$ & $$ &$\times$ &$ $ & $\times$\\ \hline 

$ $ &$ $ & $ $ & $ $ & $ $ & $ $ &$ $ & $ $ \\ \hline 

\end{tabular}\]

\renewcommand{\qedsymbol}{}

\end{proof} 

$\mathbb{A}_{n}$ hat $2^{n}$ Gegenstände und $2^{n}$ Merkmale%
\footnote{Man vergleiche die Rekursion für $\mathbb{A}_{n}$ mit der Rekursion
in \cite{key-3}, p.50, für den freien vollständig distributiven Verband
$FCD(n)$ über $n$ Elementen:\[
\underline{\mathfrak{B}}(\mathbb{A}_{n})\cong FCD(n)\]
Über den Verband $FCD(n)$ und besonders $FCD(4)$ siehe auch Beispiel
14, p.216, in \cite{key-3}. %
}, $\mathbb{B}_{n}$ hat $n2^{n-1}$ Merkmale. Die letzte Zeile von
$\mathbb{B}_{n}$ ist nach wie vor eine Vollzeile, die letzte Zeile
von $\mathbb{A}_{n}$ eine Leerzeile. Außerdem ist die erste Spalte
von $\mathbb{A}_{n}$ stets eine Leerspalte%
\footnote{Der Kontext $\mathbb{B}_{3}$ erscheint in \cite{key-4}, p.20, mit
einigen Fehlern in der Zeile des Gegenstands $\{ a,c\}$. Richtig
muss es heißen: $\{ a,c\}\vdash\{ c\}\rightarrow\{ a\},\{ a,c\}\nvdash\{ c\}\rightarrow\{ b\},\{ a,c\}\vdash\{ a,b\}\rightarrow\{ c\}.$%
}. 

\label{Bez:punktierte_Implikationen}\begin{proof}[Bezeichnung]

Für $x\in M\setminus U$ schreiben wir $U\rightarrow\{ x\}$ oder
$(U,x)$ statt $U\rightarrow U\cup\{ x\}$ . \renewcommand{\qedsymbol}{}

\end{proof} 

\begin{proof}[Beweis des Satzes~\ref{Satz:Rekursion_Bn}]Der Fall
$n=1$ wird offenbar durch $\mathbb{B}_{1}$ beschrieben und $\mathbb{A}_{1}$
ist der passende Teilkontext von $\mathbb{B}_{2}$. 

Die Gegenstandsmenge $\boldsymbol2^{n+1}$ von $\mathbb{B}_{n+1}$
entsteht aus der von $\mathbb{B}_{n}$ durch Hinzunahme der Mengen
$X+\{\ast\}$, wobei $\ast$ der neue Punkt ist und $X\in\boldsymbol2^{n}$,
die Merkmalmenge $\mathcal{X}_{n+1}$ von $\mathbb{B}_{n+1}$ entsteht
aus $\mathcal{X}_{n}$, indem man diese vergrößert um die Implikationen
$U\rightarrow\{\ast\}$ mit $U\in\boldsymbol2^{n}$ und $U+\{\ast\}\rightarrow\{ x\}$,
wobei $U \rightarrow \{ x \} \in \mathcal{X}_{n}$.

$\mathbb{B}_{n+1}$ ist Erweiterung von $\mathbb{B}_{n}$, denn für
alle $X\in\boldsymbol2^{n},U\rightarrow\{ x\}\in$ $\mathcal{X}_ n$ 
ist \[
X\vdash U\rightarrow\{ x\}\textrm{ in }\mathbb{B}_{n}\iff X\vdash U\rightarrow\{ x\}\textrm{ in }\mathbb{B}_{n+1}.\]
Für alle $U\in\boldsymbol2^{n}$ und für die Gegenstände $X\in\boldsymbol2^{n}$
ist $X+\{*\}\vdash U\rightarrow\{*\}$ und $X\vdash U+\{*\}\rightarrow\{ x\}$,
und es gilt \[
X\vdash U\rightarrow\{ x\}\iff X+\{*\}\vdash U\rightarrow\{ x\}\iff X+\{*\}\vdash U+\{*\}\rightarrow\{ x\}.\]
 Es bleibt der Fall \[
X\in\boldsymbol2^{n},U\rightarrow\{*\}\textrm{ mit }U\in\boldsymbol2^{n}\]
zu untersuchen, von dem wir zeigen, dass $\mathbb{A}_{n}$ ihn beschreibt.

$\mathbb{A}_{n+1}$ ist ein Teilkontext von $\mathbb{B}_{n+2}$. Der
Übergang von $n+1$ nach $n+2$ werde wieder durch Adjunktion eines
weiteren Punktes $**$ und Erweiterung der Gegenstandsmenge von $\mathbb{B}_{n+1}$
um die $X+\{**\}$ für Gegenstände $X$ von $\mathbb{B}_{n+1}$ bewerkstelligt.
Die Merkmale von $\mathbb{A}_{n+1}$ sind die $U\rightarrow\{**\}$
mit $U \in \boldsymbol{2}^{n+1}$. Sie sind also von der Form $U\rightarrow\{**\}$
oder $U+\{*\}\rightarrow\{**\}$ mit $U\in\boldsymbol2^{n}$. 

Die Gegenstände des Kontexts $\mathbb{A}_{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 \in \boldsymbol{2}^n$ gilt \[
X\vdash U\rightarrow\{**\}\iff X+\{*\}\vdash U\rightarrow\{**\}\iff X+\{*\}\vdash U+\{*\}\rightarrow\{**\}.\]
Da für diese $X$ und $U$ auch \[
X\vdash U\rightarrow\{**\}\iff X\vdash U\rightarrow\{*\}\]
gilt, erkennt man, dass in $\mathbb{A}_{n+1}$ dreimal der Kontext
$\mathbb{A}_{n}$ auftaucht, während für alle diese $X$ und für $U \in \boldsymbol{2}^n$ stets
$X\vdash U+\{*\}\rightarrow\{**\}$ gilt. 

Damit ist gezeigt, dass $\mathbb{B}_{n+1}$ aus $\mathbb{B}_{n}$
induktiv so aufgebaut wird, wie in (\ref{Rekursion B}) beschrieben.\end{proof}

Entsprechend kann man wieder definieren \[
\mathbb{B}:=\lim_{n\ge0}\mathbb{B}_{n}\]
und erhält erneut einen Kontext, der alle Informationen über alle
endlichen Hüllensysteme enthält. 

\begin{proof}[Bemerkung]

Nun ist zwar klar, dass $\mathbb{B}_{n}$ aus $\mathbb{H}_{n}$ durch
Reduzieren entsteht, es könnte aber noch reduzible Merkmale in $\mathbb{B}_{n}$
geben. Dass dies nicht der Fall ist, sieht man, wenn man die Pfeilrelation
$\nearrow$ benutzt%
\footnote{vgl. \cite{key-3}, p.28, wo die Pfeilrelationen definiert sind. %
} und in die Tabellen der Kontexte $\mathbb{B}_{n}$ und $\mathbb{A}_{n}$
einträgt und die so entstehenden Tabellen $\widehat{\mathbb{B}}_{n}$
bzw. $\widehat{\mathbb{A}}_{n}$ nennt. Man erhält dann die folgende
Rekursion:\[\widehat{\mathbb{B}}_1 = \begin{tabular}{|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|}\hline

$ \nearrow$ \\ \hline

$\times$ \\ \hline

\end{tabular} \; , \widehat{\mathbb{A}}_1 = \begin{tabular}{|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|}\hline$\nearrow$ & $\times$ \\ \hline

$ $ & $\nearrow$ \\ \hline

\end{tabular}\]

\begin{equation}\widehat{\mathbb{B}}_{n+1} = \begin{tabular}{c|c|c}

$\widehat{\mathbb{B}}_n$ & $\widehat{\mathbb{A}}_n$ & $\mbox{\LARGE$\times$}$ \\ \hline 

$\mathbb{B}_n$ & ${\mbox{\LARGE$\times$}}$ & $\overset{}{\widehat{\mathbb{B}}_n}$ \end{tabular}\text{ \label{Rekursion Bdach}~und } \widehat{\mathbb{A}}_{n+1}=\begin{tabular}{c|c} $\widehat{\mathbb{A}}_n$ & $\mbox{\LARGE$\times$}$ \\ \hline 

$\overset{}{\mathbb{A}_n}$ & $\overset{}{\widehat{\mathbb{A}}_n}$

\end{tabular}\quad ( n \ge 1 )\end{equation}

\vspace{10pt}

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

\[ \widehat{\mathbb{B}}_{2} = \begin{tabular}{|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}||@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}||@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|}\hline

$ \nearrow$ & $ \nearrow$ & $\times$ & $\times$ \\ \hline $\times$ & $ $ & $ \nearrow$ & $\times$ \\ \hline \hline

$ $ & $ \times$ & $\times$ & $ \nearrow$ \\ \hline $\times$ & $\times $ & $ \times$ & $\times$ \\ \hline

\end{tabular} \; ,  \widehat{\mathbb{A}}_{2} = \begin{tabular}{|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}||@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|}\hline

$ \nearrow$ & $\times $ & $\times$ & $\times$ \\ \hline $ $ & $\nearrow $ & $\times $ & $\times$ \\ \hline \hline

$ $ & $ \times$ & $ \nearrow$ & $ \times $ \\ \hline $ $ & $ $ & $ $ & $ \nearrow$ \\ \hline

\end{tabular} \]

\[\widehat{\mathbb{B}}_{3}= \begin{tabular}{|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}||@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}||@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|}\hline 

$ \nearrow$ & $ \nearrow$ & $\times$ & $ \times$ & $\nearrow $ & $\times$ & $\times$ & $ \times$ & $\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

$\times$ & $$ & $ \nearrow$ &$\times$ & $$&$\nearrow$ & $\times$ & $ \times$ &$\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

$ $ & $\times$ & $\times$ & $ \nearrow$ & $$& $\times$ & $\nearrow$ &$\times$ & $\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

$\times$ & $\times$ & $\times$ & $\times$ & $$ & $$ & $$ & $\nearrow $ &$\times$& $\times$ & $ \times$ & $\times$ \\ \hline \hline

$$ &$ $ & $\times$ & $\times$ & $\times$ & $\times $ & $\times$ & $\times$ & $\nearrow$ & $\nearrow$ & $\times$ & $\times$ \\ \hline 

$\times$ & $ $ & $ $ &$\times$ &$\times$ & $\times$& $\times$ & $ \times$ & $\times$ & $$ & $\nearrow$ & $\times$ \\ \hline 

$ $ & $\times$ & $\times$ & $ $ & $\times$& $\times$ & $\times$ &$\times$ & $$ &$\times$ &$\times$ &$\nearrow$ \\ \hline 

$\times$ & $\times$ & $\times$ & $\times$ & $\times$ &$\times$ & $\times$ & $\times$ & $\times$ & $\times$ &$\times$ & $\times$ \\ \hline

\end{tabular} \; , \widehat{\mathbb{A}}_{3}= \begin{tabular}{|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}||@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|@{\hspace{0,2mm}}c@{\hspace{0,2mm}}|}\hline

$\nearrow $ & $ \times$ & $\times$ & $ \times$ & $\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

$ $ &$\nearrow $ & $\times$ & $ \times$ &$\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

$ $ & $\times$ & $\nearrow$ &$\times$ & $\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

$ $ & $$ & $$ & $\nearrow $ &$\times$& $\times$ & $ \times$ & $\times$ \\ \hline \hline

$ $ & $\times $ & $\times$ & $\times$ & $\nearrow$ & $\times$ & $\times$ & $\times$ \\ \hline 

$ $ & $ $& $\times$ & $ \times$ & $ $ & $\nearrow$ & $\times$ & $\times$ \\ \hline 

$ $& $\times$ & $ $ &$\times$ & $$ &$\times$ &$ \nearrow$ & $\times$\\ \hline 

$ $ &$ $ & $ $ & $ $ & $ $ & $ $ &$ $ & $ \nearrow$ \\ \hline \end{tabular}\]

\vspace{20pt}Aus der rekursiven Konstruktion von $\mathbb{B}_{n}$
und $\mathbb{A}_{n}$ sieht man:

\begin{enumerate}
\item Die letzte Zeile von $\mathbb{B}_{n}$ ist stets eine Vollzeile; 
\item Die letzte Zeile von $\mathbb{A}_{n}$ ist stets eine Leerzeile;
\item $\mathbb{B}_{n}$ enthält keine Vollspalte;
\item Jede Spalte von $\widehat{\mathbb{B}}_{n}$ enthält genau einen Pfeil. 
\end{enumerate}
Für einen Gegenstand $g$ und ein Merkmal $m$ eines Kontexts $\mathbb{K}$
heißt die Relation $g\nearrow 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 $\mathbb{B}_{n}$ und $\mathbb{A}_{n}$ nach $\mathbb{B}_{n+1}$
fortsetzt. Ferner ist die Pfeilrelation für $\mathbb{B}_{1}$ und
für $\mathbb{A}_{1}$ offenbar so, wie in $\widehat{\mathbb{B}}_{1}$
und $\widehat{\mathbb{A}}_{1}$ angegeben. Somit enthält jede Spalte
von $\widehat{\mathbb{B}}_{n+1}$ wieder genau einen Pfeil, also sind
alle Merkmale von $\mathbb{B}_{n+1}$ wieder irreduzibel. Die Implikationen
in $\mathcal{X}_n$ nennen wir aus diesem Grunde \emph{irreduzibel}
oder \emph{reduziert.}%
\footnote{Irreduzible Implikationen schreiben wir je nach Bedarf in der Form
$U\rightarrow\{ x\}$ oder $U\rightarrow x$, wobei $U$ eine Merkmalmenge
und  $x$ ein Merkmal mit $x\notin U$ ist. %
} \emph{}\renewcommand{\qedsymbol}{} \end{proof}

Da die Kontexte $\mathbb{H}_{n}$ in Korollar \ref{Kor:zeilenreduziert}
bereits als fast-zeilenreduziert erkannt sind, folgt

\begin{Kor}

Die Kontexte $\mathbb{B}_{n}$ sind bis auf eine Vollzeile reduziert.

\end{Kor}

\begin{proof}Beim Spaltenreduzieren von $\mathbb{H}_{n}$ können
keine neuen Abhängigkeiten zwischen den Zeilen entstehen, denn im
Beweis von Satz \ref{Satz:Zeilenbereinigt} wird nur von irreduziblen
Implikationen Gebrauch gemacht. Die Merkmalmenge von $\mathbb{B}_{n}$
enthält alle solchen Implikationen.\end{proof}

Der Aufbau von $\mathbb{B}_{n}$ nach (\ref{Rekursion B}) hat nach
\cite{key-3}, Satz 7, und Kap. 1.4 unmittelbar zur Folge:

\begin{Kor}

Der Begriffsverband $\underline{\mathfrak{B}}(\mathbb{B}_{n+1})$
ist ein subdirektes Produkt der Verbände $\underline{\mathfrak{B}}(\mathbb{B}_{n})$
und $\underline{\mathfrak{B}}(\mathbb{A}_{n})\times\underline{\mathfrak{B}}(\mathbb{B}_{n})$.

\end{Kor}

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


\section{\label{sec:Anwendungen}Anwendungen }

Die Konstruktionen in Kapitel \ref{sec:Die-Kontexte-H-und-B} benutzen
wir, um für einen beliebigen Kontext $\mathbb{K}$ 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 $\mathbb{K}$ interessieren,
können wir stets annehmen, dass $\mathbb{K}$ reduziert, also insbesondere
bereinigt ist. 

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

Das Hüllensystem $\mathfrak{H}$ wird definiert durch einen Abschlussoperator%
\footnote{Wir bezeichnen den zu \(\mathfrak H \) gehörigen Abschlussoperator
mit dem Symbol \(\mathcal H \), sodass ~~\(\mathcal H (U) = \bigcap\{V \in \mathfrak H|U \subseteq V \} \)
ist. %
}. Die Beschreibung dieses Abschlussoperators geschieht durch Angabe
einer Menge $\mathcal{F}$ von Implikationen, die zur Menge $Imp(\mathbb{K})$
äquivalent ist. Dabei berechnet sich der Abschluss $Y$ einer Menge
$X\subseteq M$, indem eine aufsteigende Folge \[
X_{0}\subseteq X_{1}\subseteq\ldots\]
von Teilmengen von $M$ folgendermaßen konstruiert wird: 

\begin{itemize}
\item $X_{0}=X$;
\item Ist $X_{i}$ bereits konstruiert und $U\rightarrow V\in\mathcal{F}$
eine Implikation mit $U\subseteq X_{i}$, dann ist $X_{i+1}=X_{i}\cup V$;
\item $Y=\bigcup_{i\in\mathbb{N}}X_{i}$ .
\end{itemize}
Das Verfahren bricht ab, wenn $\mathcal{F}$ geeignete Zusatzvoraussetzungen
erfüllt, insbesondere aber, wenn $\mathbb{K}$ endlich ist. Dies ist
in unseren Anwendungen stets der Fall. 

\begin{Def}

\emph{Eine Menge \(\mathcal F \) von Implikationen heißt} redundant\emph{,
wenn \(\mathcal F \) zu einer ihrer echten Teilmengen äquivalent
ist. Wir nennen eine Implikation $U\rightarrow V\in\mathcal{F}$}
entbehrlich, \emph{wenn $\mathcal{F}\equiv\mathcal{F}\setminus\{ U\rightarrow V\}$
gilt, ansonsten} unentbehrlich\emph{.}

\end{Def}

Die Menge $Imp(\mathbb{K})$ enthält sehr viel Redundanz. Zum Beispiel
enthält $Imp(\mathbb{K})$ zu jeder Implikation $U\rightarrow V$
nach (\ref{Aquivalenz 2}) und (\ref{Aquivalenz 3}) sowohl die Implikation
$U\rightarrow Z$ mit $Z\subseteq V$ als auch die Implikation $W\rightarrow V$
mit $U\subseteq W$. Die Menge $Imp(\mathbb{K})$ selbst ist daher
für die meisten Anwendungen ungeeignet, weil sie viel zu groß ist.
Um Redundanz zu beseitigen, sind die Eigenschaften (\ref{Armstrongaxiome})
bis (\ref{Aquivalenz 4}) zulässige Hilfsmittel. 

Eine (bezüglich Inklusion) minimale Menge \(\mathcal F\subseteq Imp(\mathbb K)\)
von Implikationen mit der Eigenschaft \(\mathcal F^{\vdash} = Imp(\mathbb K)^{\vdash}\)
ist die sogenannte \emph{Duquenne-Guigues-Basis}. Für den Kontext
$\mathbb{K}$ ist sie definiert durch \[
\{ P\rightarrow P''\,|\, P\textrm{ ist Pseudoinhalt von }\mathbb{K}\}\]
Nach \cite[Hilfssatz 25, p.84]{key-3} 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. 

\begin{proof}[Beispiel]\label{Beispiel:Duquenne-Guigues-Basis}Die
Menge \[\mathcal D=\bigl \{\{2\}\rightarrow \{2,4\},\{3\}\rightarrow \{1,3\},\{1,3,4\}\rightarrow \{1,2,3,4\},\{1,2,4\}\rightarrow \{1,2,3,4\}\bigr \}\]
ist die Duquenne-Guigues-Basis des Kontexts  \vspace{10pt}\[ \begin{tabular}{r||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}

$ $ & $ 1$ & $2$ & $3$ & $4$ \\

\hline \hline

$a$ & $\times$ & $ $ & $\times$ & $ $ \\ \hline 

$b$ & $ $ &$\times$ & $$ & $ \times$ \\ \hline 

$c$ & $ \times$ & $$ & $$ &$\times$ \\ \hline 

\end{tabular}\]\vspace{10pt} \\
also irredundant, aber nach (\ref{Aquivalenz 4}) äquivalent zu \[
\tilde{\mathcal{D}}=\bigl\{\{2\}\rightarrow\{2,4\},\{3\}\rightarrow\{1,3\},\{3,4\}\rightarrow\{1,2,3,4\},\{1,2\}\rightarrow\{1,2,3,4\}\bigr\}\]
 und nach dem ersten Anschein wird man die zweite Menge als ,,einfacher''
als die erste bezeichnen. 

Eine noch einfachere zu \( \mathcal D \) äquivalente Menge erhält
man, wenn man \( \mathcal D \) zunächst mittels (\ref{Aquivalenz 1})
umschreibt in \[ \mathcal D=\bigl \{\{2\}\rightarrow \{4\},\{3\}\rightarrow \{1\},\{1,3,4\}\rightarrow \{2\},\{1,2,4\}\rightarrow \{3\}\bigr \} \] und
dann (\ref{Aquivalenz 4}) anwendet. Man erhält auf diese Weise die
Menge\[
\tilde{\tilde{\mathcal{D}}}=\bigl\{\{2\}\rightarrow\{4\},\{3\}\rightarrow\{1\},\{3,4\}\rightarrow\{2\},\{1,2\}\rightarrow\{3\}\bigr\}\]
 welche auch noch einfacher als die entsprechend umgeschriebene Menge
\[
\tilde{\mathcal{D}}=\bigl\{\{2\}\rightarrow\{4\},\{3\}\rightarrow\{1\},\{3,4\}\rightarrow\{1,2\},\{1,2\}\rightarrow\{3,4\}\bigr\}\]
 ist. $\tilde{\tilde{\mathcal{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\rightarrow V$ mit $V\neq\emptyset$  und $U\cap V=\emptyset$
zu schreiben. Dann ist für eine Formelmenge $\mathcal{F}$ die natürliche
Zahl \[ \omega (\mathcal F):=\sum _{U\rightarrow V\in \mathcal F}|U|\cdot |V|\]
ein Maß für \( \mathcal F \), das invariant ist unter Umformungen
nach (\ref{Aquivalenz 2}), falls $V$ und $W$ disjunkt sind, und
das triviale Implikationen nicht zählt. Nach dieser Bewertung ist
tatsächlich $\tilde{\tilde{\mathcal{D}}}$ die einfachste der drei
Mengen $\mathcal{D},\tilde{\mathcal{D}},\tilde{\tilde{\mathcal{D}}}$.\renewcommand{\qedsymbol}{}\end{proof}

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\rightarrow U''$. 


\subsection{Berechnung der Wertetabelle}

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

Die Elemente der Gegenstandsmenge von $\mathbb{H}_{n}$ sind Teilmengen
$U$ von $M.$ Wir codieren sie als $0,1-$Vektoren $\lambda(U)=(\lambda(U)_{n-1},\lambda(U)_{n-2},\ldots,\lambda(U)_{0})$
der Länge $n$, also als Elemente von $\boldsymbol2^{n}$. $\lambda(U)$
heißt der charakteristische Vektor für $U$ und stellt eine Binärzahl
\[
|\lambda(U)|_{2}=\sum_{0\le i<n}\lambda(U)_{i}\cdot2^{i}\]
 dar. Entsprechend ist die Menge $\boldsymbol2^{n}$ auf zwei Weisen
geordnet: \[
U\subseteq V\iff\lambda(U)\le_{n}\lambda(V),\]
wobei $\le_{n}$ die $n-$fache Produktordnung von $0<1$ ist, und
\[
U\preceq V\iff|\lambda(U)|_{2}\le|\lambda(V)|_{2}.\]
 $\preceq$ ist die lexikographische Ordnung auf $\boldsymbol2^{n}$.
Wir identifizieren jedes $U$ mit seinem charakteristischen Vektor,
so dass gilt $U\subseteq V\iff U\le_{n}V$ und $U\le_{n}V\implies U\preceq V$. 

Implikationen schreiben wir in der Form $U\rightarrow V$ mit $U\cap V=\emptyset$
und codieren sie als Vektoren $\kappa(U,V)=(x_{n-1},x_{n-2},\ldots,x_{0})\in\boldsymbol3^{n}$
der Länge $n$ über der Menge $\boldsymbol3=\{0,1,2\}$ auf folgende
Weise:\[
x_{i}=\left\{ \begin{array}{rl}
2, & \textrm{falls }i+1\in U\\
1, & \textrm{falls }i+1\in V\\
0, & \textrm{sonst}\end{array}\right.\]
Dann kann man $\kappa(U,V)$ berechnen durch $\kappa(U,V)=2\lambda(U)+\lambda(V)$.
Beispielsweise wird die Implikation $\{3,4,6\}\rightarrow\{1,5\}$
codiert durch den Vektor $x=(2,1,2,2,0,1)$, also durch die Zahl $640=|x|_{3}=\sum_{0\le i\le5}x_{i}\cdot3^{i}$.
Dies liefert eine Bijektion zwischen der Menge aller Implikationen
mit $n$ Symbolen und der Menge $\boldsymbol3^{n}=\{0,1,\ldots,3^{n}-1\}$
mit zwei verschiedenen Ordnungen:\[
(U,V)\le(X,Y)\iff\kappa(U,V)\le_{n}\kappa(X,Y),\]
 wobei wieder $\le_{n}$ die $n-$fache Produktordnung von $0<1<2$
ist, und\[
(U,V)\preceq(X,Y)\iff|\kappa(U,V)|_{3}\le|\kappa(X,Y)|_{3}.\]
 Wie vorher ist $\preceq$ die lexikographische Ordnung auf $\boldsymbol3^{n}$
bezüglich $0<1<2$ und es gilt $(U,V)\le(X,Y)\implies(U,V)\preceq(X,Y)$. 

Indem wir Gegenstandsmenge und Merkmalmenge jeweils mit $\preceq$
ordnen, erhalten wir für $n=3$ den Kontext \(\mathbb{H}_{3}\)

\[ \begin{tabular}{c||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}

$$&$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$ \\

\hline\hline

$000 $ &$\times $ & $ $ & $\times$ & $$ & $$ & $\times$ & $\times$ & $ \times$ & $\times$& $$ & $$ & $\times$ & $$ & $$ & $\times$ & $\times$ & $ \times$ & $\times$ & $\times$ & $ \times$ & $\times$ & $\times$ & $ \times$ & $\times$ & $\times$ & $ \times$ & $\times$ \\ \hline 

$001$ &$\times$ & $\times $ & $ \times$ &$$ & $$&$$ & $\times$ & $ \times$ &$\times$ & $$ & $ $ & $$ & $$ & $ $ & $$ & $\times$ & $\times $ & $\times$ &$\times$ & $\times $ & $ \times$ &$\times$ & $\times$&$\times$ & $\times$ & $ \times$ &$\times$ \\ \hline 

$ 010$ &$\times$ & $$ & $ \times$ &$\times$ & $$&$\times$ & $\times$ & $ $ &$\times$ & $$ & $ $ & $\times$ & $$ & $ $ & $\times$ & $$ & $ $ & $\times$ &$\times$ & $\times $ & $ \times$ &$\times$ & $\times$&$\times$ & $\times$ & $ \times$ &$\times$ \\ \hline 

$011$ &$\times$ & $\times $ & $ \times$ &$\times$ & $\times$&$\times$ & $\times$ & $ \times$ &$\times$ & $$ & $ $ & $$ & $$ & $ $ & $$ & $$ & $ $ & $$ &$\times$ & $\times $ & $ \times$ &$\times$ & $\times$&$\times$ & $\times$ & $ \times$ &$\times$ \\ \hline \hline

$100$ &$\times$ & $$ & $ \times$ &$$ & $$&$\times$ & $\times$ & $\times$ &$\times$ & $\times$ & $ $ & $\times$ & $$ & $ $ & $\times$ & $\times$ & $\times $ & $\times$ &$\times$ & $$ & $ \times$ &$$ & $$&$\times$ & $\times$ & $\times $ &$\times$ \\ \hline 

$101$ &$\times$ & $\times $ & $ \times$ &$$ & $$&$$ & $\times$ & $ \times$ &$\times$ & $\times$ & $\times$ & $\times$ & $$ & $ $ & $$ & $\times$ & $\times$ & $\times$ &$\times$ & $\times $ & $ \times$ &$$ & $$&$$ & $\times$ & $ \times$ &$\times$ \\ \hline 

$110$ &$\times$ & $$ & $ \times$ &$\times$ & $$&$\times$ & $\times$ & $ $ &$\times$ & $\times$ & $ $ & $\times$ & $\times$ & $ $ & $\times$ & $\times$ & $ $ & $\times$ &$\times$ & $$ & $ \times$ &$\times$ & $$&$\times$ & $\times$ & $ $ &$\times$ \\ \hline 

$111 $ &$\times$ & $\times $ & $ \times$ &$\times$ & $\times$&$\times$ & $\times$ & $ \times$ &$\times$ & $\times$ & $ \times$ & $\times$ & $\times$ & $\times $ & $\times$ & $\times$ & $\times$ & $\times$ &$\times$ & $\times $ & $ \times$ &$\times$ & $\times$&$\times$ & $\times$ & $ \times$ &$\times$ \\ \hline 

\end{tabular} \]

\vspace{10pt}\noindent und \(\mathbb{L}_{3}\) ergibt sich zu 

\[ \begin{tabular}{c||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}

$$&$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$ \\

\hline\hline

$000 $ &$$ & $ $ & $\times$ & $$ & $$ & $\times$ & $\times$ & $ \times$ & $\times$& $$ & $$ & $\times$ & $$ & $$ & $\times$ & $\times$ & $ \times$ & $\times$ & $\times$ & $ \times$ & $\times$ & $\times$ & $ \times$ & $\times$ & $\times$ & $ \times$ & $\times$ \\ \hline 

$001$ &$$ & $$ & $ $ &$$ & $$&$$ & $\times$ & $ \times$ &$\times$ & $$ & $ $ & $$ & $$ & $ $ & $$ & $\times$ & $\times $ & $\times$ &$\times$ & $\times $ & $ \times$ &$\times$ & $\times$&$\times$ & $\times$ & $ \times$ &$\times$ \\ \hline 

$ 010$ &$$ & $$ & $ \times$ &$$ & $$&$\times$ & $$ & $ $ &$\times$ & $$ & $ $ & $\times$ & $$ & $ $ & $\times$ & $$ & $ $ & $\times$ &$\times$ & $\times $ & $ \times$ &$\times$ & $\times$&$\times$ & $\times$ & $ \times$ &$\times$ \\ \hline 

$011$ &$$ & $$ & $$ &$$ & $$&$$ & $$ & $$ &$$ & $$ & $ $ & $$ & $$ & $ $ & $$ & $$ & $ $ & $$ &$\times$ & $\times $ & $ \times$ &$\times$ & $\times$&$\times$ & $\times$ & $ \times$ &$\times$ \\ \hline \hline

$100$ &$$ & $$ & $ \times$ &$$ & $$&$\times$ & $\times$ & $\times$ &$\times$ & $$ & $$ & $\times$ & $$ & $$ & $\times$ & $\times$ & $\times$ & $\times$ &$$ & $$ & $ \times$ &$$ & $$&$\times$ & $\times$ & $\times$ &$\times$ \\ \hline 

$101$ &$$ & $$ & $$ &$$ & $$&$$ & $\times$ & $ \times$ &$\times$ & $$ & $$ & $$ & $$ & $ $ & $$ & $\times$ & $\times$ & $\times$ &$$ & $$ & $$ &$$ & $$&$$ & $\times$ & $ \times$ &$\times$ \\ \hline 

$110$ &$$ & $$ & $ \times$ &$$ & $$&$\times$ & $$ & $ $ &$\times$ & $$ & $ $ & $\times$ & $$ & $$ & $\times$ & $$ & $$ & $\times$ &$$ & $$ & $\times$ &$$ & $$&$\times$ & $$ & $ $ &$\times$ \\ \hline 

$111 $ &$\phantom{\times}$ & $\phantom{\times}$ & $ $ &$\phantom{\times}$ & $\phantom{\times}$&$$ & $$ & $$ &$$ & $\phantom{\times}$ & $\phantom{\times}$ &$$ & $\phantom{\times}$&$\phantom{\times}$ & $$ & $$ &$$ & $$ & $$ &$$ & $$&$$ & $$ & $$ &$$ & $$ & $ $ \\ \hline 

\end{tabular} \]

\vspace{10pt} Die Inzidenzrelation von $\mathbb{H}_{n}$ bzw. von
$\mathbb{L}_{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 $\mathbb{K}=(G,M,I)$ mit $|M|=n$ die
Teilmenge von $Imp(\mathbb{K})$ zu berechnen, die die Wertetabelle
des zugehörigen Abschlussoperators darstellt, untersuchen wir den
Kontext $\mathbb{K}\circ\mathbb{H}_{n}$ (siehe Definition \ref{Def:Komposition}
für die Definition der Komposition). Wir berechnen zunächst $Imp(\mathbb{K})$,
also alle Implikationen, die von allen Gegenstandsinhalten von $\mathbb{K}$
respektiert werden. 

Für einen Gegenstand $g\in G$ sei sein Gegenstandsinhalt $g'=(g_{n},\ldots,g_{1})\in\boldsymbol2^{n}$
als der entsprechende $0,1-$Vektor der Länge $n\ge1$ gegeben, das
ist die Zeile von $g$ im Kontext $\mathbb{K}$. Um die Schreibweise
zu vereinfachen, kürzen wir für $1\le k\le n$ die letzten $k$ Komponenten
von $(g_{n},\ldots,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]})^{\mathbb{H}_{1}}=\left\{ \begin{array}{cl}
1,0,1 & \textrm{falls }g_{1}=0\\
1,1,1 & \textrm{falls }g_{1}=1\end{array}\right.\textrm{und }\begin{array}{c}
(g_{[1]})^{\mathbb{L}_{1}}=\left\{ \begin{array}{cl}
0,0,1 & \textrm{falls }g_{1}=0\\
0,0,0 & \textrm{falls }g_{1}=1\end{array}\right.\end{array}\]
und für $n>1$ ist \[
(g_{[n]})^{\mathbb{H}_{n}}=\left\{ \begin{array}{ll}
(g_{[n-1]})^{\mathbb{H}_{n-1}},(g_{[n-1]})^{\mathbb{L}_{n-1}},1^{3^{n-1}} & \textrm{falls }g_{n}=0\\
(g_{[n-1]})^{\mathbb{H}_{n-1}},(g_{[n-1]})^{\mathbb{H}_{n-1}},(g_{[n-1]})^{\mathbb{H}_{n-1}} & \textrm{falls }g_{n}=1\end{array}\right.\]
sowie \[
(g_{[n]})^{\mathbb{L}_{n}}=\left\{ \begin{array}{ll}
(g_{[n-1]})^{\mathbb{L}_{n-1}},(g_{[n-1]})^{\mathbb{L}_{n-1}},1^{3^{n-1}} & \textrm{falls }g_{n}=0\\
(g_{[n-1]})^{\mathbb{L}_{n-1}},(g_{[n-1]})^{\mathbb{L}_{n-1}},(g_{[n-1]})^{\mathbb{L}_{n-1}} & \textrm{falls }g_{n}=1\end{array}\right.\]
Der $0,1-$Vektor $(g_{[n]})^{\mathbb{H}_{n}}\in\boldsymbol2^{3^{n}}$
ist die Indikatorfunktion $\varepsilon : \boldsymbol{3}^n \longrightarrow \boldsymbol{2}$
der Menge $\mathcal{F} = \{g'\}^{\mathbb{H}_n}$ aller Implikationen,
die von dem Gegenstandsinhalt $g'$ respektiert werden, d.h. $\varepsilon^{-1}(1)=\{ g'\}^{\mathbb{H}_{n}}$.
Wir bezeichnen daher die Komponente $x$ von $(g_{[n]})^{\mathbb{H}_{n}}$
mit $(g_{[n]})^{\mathbb{H}_{n}}(x)$. Eine 1 an der Stelle $x$ mit
$0\le x<3^{n}$ codiert die Implikation, die durch den Vektor $y=(x_{n-1},x_{n-2},\ldots,x_{0})$
mit $x=|y|_{3}=\sum_{0\le i<n}x_{i}\cdot3^{i}$ dargestellt wird.
$y$ ist also die Ternärdarstellung von $x$. Zu einem solchen Vektor
$y$ sei $\hat{y}$ 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(\mathbb{K})$ können wir nun bestimmen,
indem wir das komponentenweise Produkt aller Vektoren $(g_{[n]})^{\mathbb{H}_{n}}$
mit $g\in G$ berechnen. Sei $\varepsilon_{\mathbb{K}}$ diese Indikatorfunktion,
also \[
\varepsilon_{\mathbb{K}}(x)=1\iff\textrm{ f}\ddot{\textrm{u}}\textrm{r alle }g\in G\textrm{ ist }(g_{[n]})^{\mathbb{H}_{n}}(x)=1\]
Die Abbildung $\varepsilon_{\mathbb{K}}$ stellen wir dar als die
aufsteigende Folge aller natürlichen Zahlen $x<3^{n}$ mit $\varepsilon_{\mathbb{K}}(x)=1$.
Es gilt stets $\varepsilon_{\mathbb{K}}(0)=1$ und $\varepsilon_{\mathbb{K}}(3^{n}-1)=1$. 


\subsection{Ein Algorithmus zur Bestimmung der Wertetabelle }

Aus der Folge $\varepsilon_{\mathbb{K}}$ liefert der folgende Algorithmus
die Wertetabelle des Abschlussoperators \(\mathcal{H}\):

\begin{Algo}

\emph{Gegeben sei eine Folge $0=x_{1}<x_{2}<\ldots<x_{k}=3^{n}-1$. }

\begin{enumerate}
\item \emph{\(\mathcal{H}:=\emptyset\) , $L:=\emptyset$, $K:=\{(\underbrace{2,2,\ldots,2}_{n-\textrm{mal}})\}$;}
\item \textbf{Für} \emph{$i=k-1,k-2,\ldots,1$ \vspace{5pt} }\\
\emph{\phantom{MM}$y:=$ die Ternärdarstellung von $x_{i}$\vspace{5pt}}\\
\emph{\phantom{MM}}\textbf{Falls} \emph{$y\notin\{0,2\}^{n}\textrm{ und }\hat{y}\notin L$,
dann \(\mathcal{H}:=\mathcal{H}\cup \{y\}\) und $L:=L\cup\{\hat{y}\}$\vspace{5pt}}\\
\emph{\phantom{MM}}\textbf{Falls} \emph{$y\in\{0,2\}^{n}\textrm{ und }y\notin L$,
dann $K:=K\cup\{ y\}$}
\item \textbf{Ausgabe} \emph{\(\mathcal{H}, K\)}
\end{enumerate}
\end{Algo}

\begin{proof}[Beobachtungen]

\begin{enumerate}
\item $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\cap L=\emptyset$.
\item Wenn die Ausgangsfolge die charakteristische Folge einer Implikationenmenge
der Form $Imp(\mathbb{K})$ ist, dann gilt nach Ausführung des Algorithmus
$K\cup L\cong\boldsymbol2^{n}$.
\end{enumerate}
\renewcommand{\qedsymbol}{}\end{proof}

\noindent Außerdem gilt:

\begin{Satz}

$K$ ist die Menge der abgeschlossenen Teilmengen des Hüllensystems,
das sind die Fixpunkte des Abschlussoperators, \(\mathcal{H}\) ist
die Menge der nichttrivialen Implikationen $U\rightarrow V$, für
die $U\cup V$ abgeschlossen ist. 

\end{Satz}

\begin{proof}Zu jedem Zeitpunkt gilt: 

\begin{enumerate}
\item $y\notin\{0,2\}^{n}$ codiert eine nichttriviale Implikation $U\rightarrow V$
und $\hat{y}$ codiert deren linke Seite $U$. 
\item $\hat{y}\in L\iff$ es gibt eine Implikation $U\rightarrow W$ aus
einem früheren Durchgang mit gleicher linker Seite $U$, d.h. das
gegenwärtige $U\rightarrow V$ hat $V\subsetneq W$. 
\item $y\in\{0,2\}^{n}\textrm{ und }y\notin L$ heißt: die linke Seite $U$
der von $y$ codierten trivialen Implikation $U\rightarrow U$ war
zu keinem früheren Zeitpunkt linke Seite einer Implikation, d.h. $U$
ist abgeschlossen. \hfill \qedsymbol
\end{enumerate}
\renewcommand{\qedsymbol}{}\end{proof}

Der obige Algorithmus ist also nicht nur zur Konstruktion der Wertetabelle
\(\mathcal{H}\cup K\) $=\{ U\rightarrow V\,|\, U\in\boldsymbol2^{n},V\textrm{ 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 $\mathbb{K}$ -- durch
Angabe des Inhalts eines jeden Begriffs -- und die Wertetabelle simultan
bestimmen. Insbesondere braucht man nicht eines von beiden, um das
andere zu berechnen. 


\subsection{Ein kanonisches vollständiges Implikationensystem}

In unseren bisherigen Betrachtungen haben wir zur Vereinfachung einer
gegebenen Implikationenmenge noch nicht von der Eigenschaft (\ref{Aquivalenz 4})
Gebrauch gemacht. Im Beispiel auf p.\pageref{Beispiel:Duquenne-Guigues-Basis}
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 (\ref{Aquivalenz 2})
anwenden und nur irreduzible Implikationen benutzen. Wir ersetzen
also eine Implikation $U\rightarrow V$ durch die Menge $\{ U\rightarrow\{ v\}\,|\, v\in V\}$,
was das Maß $\omega$ nicht ändert. 

Implikationen $U\rightarrow\{ x\}$ in \(\mathcal{X}_n\) codieren
wir als punktierte $0,1-$Vektoren, das sind $0,1-$Vektoren mit einem
Sonderzeichen $\bullet$, das genau einmal vorkommt. Wir können nämlich
$U\rightarrow\{ x\}$ aus der Indikatorfunktion der Menge $U\cup\{ x\}\in\boldsymbol2^{n}$
rekonstruieren, wenn wir mit dem $\bullet$ zusätzlich kennzeichnen,
welches Element das $x$ ist, z.B. codiert der Vektor $(1,0,1,\bullet,0,1)$
die Implikation $\{6,4,1\}\rightarrow3$. Wenn wir Gegenstände und
Merkmale auf diese Weise an $\mathbb{B}_{3}$ und $\mathbb{A}_{3}$
schreiben, erhalten wir die Kontexte \vspace{20pt}\(\mathbb{B}_{3}\) \[\begin{tabular}{c||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}

$$&$0$ & $0$ & $0$ & $0$ & $\bullet$ & $\bullet$ & $\bullet$ & $\bullet$ & $1$& $1$ & $1$ & $1$ \\ 

$$ &$0$ & $\bullet $ & $\bullet$ & $1$& $0$ & $0$ & $1$ & $1$ & $0$& $\bullet$ & $ \bullet$ & $1$ \\ 

$$ &$\bullet $ & $0$ & $1$ & $ \bullet$& $ 0$ & $1$ & $0$ & $1$ & $\bullet$& $0$ & $1$ & $\bullet$ \\

\hline\hline

~~$000 $ &$ $ & $ $ & $\times$ & $ \times$ & $ $ & $\times$ & $\times$ & $ \times$ & $\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

~~$001$ &$\times$ & $ $ & $ $ &$\times$ & & & $\times$ & $ \times$ &$\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

~~$ 010$ &$ $ & $\times$ & $\times$ & $ $ & & $\times$ & $$ &$\times$ & $\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

~~$011$ &$\times$ & $\times$ & $\times$ & $\times$ & $$ & $$ & $$ & $ $ &$\times$& $\times$ & $ \times$ & $\times$ \\ \hline \hline

~~$100$ &$$ &$ $ & $\times$ & $\times$ & $\times$ & $\times $ & $\times$ & $\times$ & $$ & $$ & $\times$ & $\times$ \\ \hline 

~~$101$ &$\times$ & $ $ & $ $ &$\times$ &$\times$ & $\times$& $\times$ & $ \times$ & $\times$ & $$ & $$ & $\times$ \\ \hline 

~~$110$ &$ $ & $\times$ & $\times$ & $ $ & $\times$& $\times$ & $\times$ &$\times$ & $$ &$\times$ &$\times$ &$$ \\ \hline 

~~$111 $ &$\times$ & $\times$ & $\times$ & $\times$ & $\times$ &$\times$ & $\times$ & $\times$ & $\times$ & $\times$ &$\times$ & $\times$ \\ \hline 

\end{tabular} \]

\vspace{10pt}

\noindent und \(\mathbb{A}_{3}\) \[\begin{tabular}{c||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}

$ $ & $ \bullet$ & $\bullet$ & $\bullet$ & $\bullet $ & $ \bullet$ & $\bullet$ & $\bullet$ & $\bullet $ \\

$ $ & $ 0$ & $0$ & $0$ & $0$ & $ 1$ & $1$ & $1$ & $1$ \\

$ $ & $ 0$ & $0$ & $1$ & $1$ & $ 0$ & $0$ & $1$ & $1$ \\

$ $ & $ 0$ & $1$ & $0$ & $1$ &$ 0$ & $1$ & $0$ & $1$ \\

\hline \hline

~~$000$ & $\phantom{\times} $ & $ \times$ & $\times$ & $ \times$ & $\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

~~$001$ & $ $ &$ $ & $\times$ & $ \times$ &$\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

~~$010$ & $ $ & $\times$ & $$ &$\times$ & $\times$& $\times$ & $ \times$ & $\times$ \\ \hline 

~~$011$ & $ $ & $$ & $$ & $ $ &$\times$& $\times$ & $ \times$ & $\times$ \\ \hline \hline

~~$100$ & $ $ & $\times $ & $\times$ & $\times$ & $$ & $\times$ & $\times$ & $\times$ \\ \hline 

~~$101$ & $ $ & $ $& $\times$ & $ \times$ & $ $ & $$ & $\times$ & $\times$ \\ \hline 

~~$110$ & $ $& $\times$ & $ $ &$\times$ & $$ &$\times$ &$ $ & $\times$\\ \hline 

~~$111$ & $ $ &$ $ & $ $ & $ $ & $ $ & $ $ &$ $ & $ $ \\ \hline 

\end{tabular}\]

\vspace{10pt}

Schließlich beschreiben wir die Inzidenzrelation von $\mathbb{B}_{n}$
bzw. von $\mathbb{A}_{n}$ durch Angabe der Zeilen des Kontexts und
der Spalten des Kontexts (wieder als $0,1-$Vektoren oder Wörter der
Länge $\chi_n:= |\mathcal{X}_n|$ und $2^{n}$ für $\mathbb{B}_{n}$
bzw. $2^{n}$ und $2^{n}$ für $\mathbb{A}_{n}$). Beispielsweise
liest man vom Kontext $\mathbb{B}_{3}$ ab, dass für den Gegenstand
$\{3,2\}$ von $\mathbb{B}_{3}$, der durch $(1,1,0)$ codiert wird,
\[
\{(1,1,0)\}^{\mathbb{B}_{3}}=\{(1,1,0)\}^{\vdash}=(0,1,1,0,1,1,1,1,0,1,1,0)\]
 ist und dass die Implikation $\{3,1\}\rightarrow2$, die codiert
wird durch $(1,\bullet,1)$, die Spalte \[
\{(1,\bullet,1)\}^{\mathbb{B}_{3}}=\{(1,\bullet,1)\}^{\vdash}=(1,1,1,1,1,0,1,1)\]
 definiert. Im Kontext $\mathbb{A}_{n}$ gilt offenbar: \[
(x_{n},\ldots,x_{1})\vdash(\bullet,y_{n},\ldots,y_{1})\iff\exists i\in\{1,\ldots\, n\}\textrm{ mit }x_{i}<y_{i}\]


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

\begin{Satz}

Für einen Gegenstand $g\in G$ des Kontexts $\mathbb{K}=(G,M,I)$
mit $|M|=n$ sei sein Gegenstandsinhalt $g'=(g_{n},\ldots,g_{1})\in\boldsymbol2^{n}$
gegeben. \label{K circ B_n(g)}Dann gilt für $n=1$ \[
(g_{[1]})^{\mathbb{B}_{1}}=\left\{ \begin{array}{cl}
0, & \textrm{falls }g_{1}=0\\
1, & \textrm{falls }g_{1}=1\end{array}\right.\textrm{und }\begin{array}{c}
(g_{[1]})^{\mathbb{A}_{1}}=\left\{ \begin{array}{cl}
(0,1), & \textrm{falls }g_{1}=0\\
(0,0), & \textrm{falls }g_{1}=1\end{array}\right.\end{array}\]
und für $n>1$ ist \[
(g_{[n]})^{\mathbb{B}_{n}}=\left\{ \begin{array}{ll}
(g_{[n-1]})^{\mathbb{B}_{n-1}},(g_{[n-1]})^{\mathbb{A}_{n-1}},1^{(n-1)2^{n-2}}, & \textrm{falls }g_{n}=0\\
(g_{[n-1]})^{\mathbb{B}_{n-1}},1^{2^{n-1}},(g_{[n-1]})^{\mathbb{B}_{n-1}}, & \textrm{falls }g_{n}=1\end{array}\right.\]
sowie \[
(g_{[n]})^{\mathbb{A}_{n}}=\left\{ \begin{array}{ll}
(g_{[n-1]})^{\mathbb{A}_{n-1}},1^{2^{n-1}}, & \textrm{falls }g_{n}=0\\
(g_{[n-1]})^{\mathbb{A}_{n-1}},(g_{[n-1]})^{\mathbb{A}_{n-1}}, & \textrm{falls }g_{n}=1\end{array}\right.\]
\end{Satz}

\begin{proof}

Die Konstruktion folgt unmittelbar aus dem rekursiven Aufbau der $\mathbb{B}_{n}$
nach (\ref{Rekursion B}).\end{proof}

Der $0,1-$Vektor $(g_{[n]})^{\mathbb{B}_{n}}$ ist die Indikatorfunktion
$\varepsilon : \mathcal{X}_n \longrightarrow \boldsymbol{2}$ der
Menge $\mathcal{F} = \{g'\}^{\mathbb{B}_n}$ aller irreduziblen Implikationen,
die von dem Gegenstandsinhalt $g'$ respektiert werden, d.h. $\varepsilon^{-1}(1)=\{ g'\}^{\mathbb{B}_{n}}$,
wobei die Implikationen so angeordnet sind, wie durch die Konstruktion
von $\mathbb{B}_{n}$ vorgegeben. 

Um eine beliebige Menge $\mathcal{F}$ von irreduziblen Implikationen
im Kontext $\mathbb{B}_{n}$ explizit beschreiben zu können, müssen
wir aus dem $0,1-$Vektor für die Indikatorfunktion von $\mathcal{F}$
die zugehörige Teilmenge aller derjenigen $0,\bullet,1-$Vekto\-ren,
die die Elemente von $\mathcal{F}$ codieren, rekonstruieren. Dazu
kann man die Menge $\mathcal{X}_{n}$ in der Form $\mathcal{X}_n = \{0,1,\ldots, \chi_n-1\}$
schreiben; $\varepsilon_{k}$ sei dann der $0,1-$Vektor der Länge
$\chi_{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 $\varepsilon_{k}$ das Element $k-1\in$ $\mathcal{X}_n$ bezeichnet:
\[
\varepsilon_{k}(t)=1\iff t=k-1\]
 $\varepsilon_{k}$ fassen wir als die Indikatorfunktion $ \varepsilon_k : \mathcal{X}_n \longrightarrow \boldsymbol{2} $
einer einelementigen Merkmalmenge von $\mathbb{B}_{n}$ auf. Dann
ist eine beliebige Indikatorfunktion $\varepsilon$ darstellbar $\varepsilon=\sum_{\varepsilon(k)=1}\varepsilon_{k}$
und $\varepsilon^{-1}(1)=\bigcup_{\varepsilon(k)=1}\varepsilon_{k}^{-1}(1)$. 

Die Indikatorfunktion $\varepsilon_{k}$ repräsentiert eine irreduzible
Implikation $\varepsilon_{k}^{-1}(1)=$ $(b_{n}(t),\ldots,b_{1}(t))\in\{0,\bullet,1\}^{n}$,
wobei $t=k-1<\chi_{n}$. Der Vektor $(b_{n}(t),\ldots,b_{1}(t))$
wird wieder zu $b_{[n]}(t)$ abgekürzt und nach folgender Rekursion
berechnet, wobei wir Vektoren ohne Klammern schreiben.

\begin{Satz}\label{Satz:Berchenung_von_b[n](t)}

Es sei $t\in\mathbb{N}$ und $n\in\mathbb{N}$ mit $t<\chi_{n}$.
Für $n=1$ ist\[
b_{[1]}(0)=\bullet\textrm{ und }a_{[1]}(0)=0,a_{[1]}(1)=1\]
 und für $n>1$ gilt \[
b_{[n]}(t)=\left\{ \begin{array}{ll}
1,b_{[n-1]}(t-(n+1)2^{n-2}) & \textrm{falls }(n+1)2^{n-2}\le t\,(<\chi_{n})\\
\bullet,a_{[n-1]}(t-(n-1)2^{n-2}) & \textrm{falls }(n-1)2^{n-2}\le t<(n+1)2^{n-2}\\
0,b_{[n-1]}(t) & \textrm{falls }t<(n-1)2^{n-2}\end{array}\right.\]
und\[
a_{[n]}(t)=\left\{ \begin{array}{ll}
1,a_{[n-1]}(t-2^{n-1}) & \textrm{falls }2^{n-1}\le t\\
0,a_{[n-1]}(t) & \textrm{falls }t<2^{n-1}\end{array}\right.\]


\end{Satz}

\begin{proof}

Wegen der Bedingung $t<\chi_{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 $\mathbb{B}_{n}$ aus denen von $\mathbb{B}_{n-1}$
und $\mathbb{A}_{n-1}$.\end{proof}

\begin{proof}[Bemerkungen]

\begin{enumerate}
\item Für festes $t\in\mathbb{N}$ unterscheiden sich die Ergebnisse $b_{[n]}(t)$
für verschiedene $n$ mit $t<\chi_{n}$ nur um führende Nullen. 
\item Wegen $\chi_{n}+2^{n}=(n+2)\cdot2^{n-1}$ können wir diese Konstruktion
auch so umschreiben:  Jede natürliche Zahl $t\ge0$ hat eine eindeutige
Darstellung \begin{equation}
t=\sum_{i\ge0}t_{i}\tau_{i}\label{Summendarstellung}\end{equation}
mit $t_{i}\in\{0,1\}$ und der weiteren Eigenschaft: Es gibt genau
ein $j\ge0$ mit $t_{j}=1$ und

\begin{enumerate}
\item für alle $i>j$ ist $\tau_{i}=\chi_{i}+2^{i}$;
\item für $i=j$ ist $\tau_{i}=\chi_{i}$;
\item für alle $i<j$ ist $\tau_{i}=2^{i}$.
\end{enumerate}
\item Dabei haben wir zusätzlich $\chi_{0}=0$ benutzt. Die Summation (\ref{Summendarstellung})
ist endlich, denn $t_{i}=0$ für alle $i$, für die $\chi_{i}\ge t$
ist. Die $1$ an der Stelle $j$ wird durch den $\bullet$ gekennzeichnet.
Für $t=k-1$ ist die Folge \[
\varepsilon_{k}^{-1}(1)=(t_{n-1},\ldots,t_{j+1},\bullet,t_{j-1},\ldots,t_{0})=(b_{n}(k-1),\ldots,b_{1}(k-1))\]
die von $\varepsilon_{k}$ codierte irreduzible Implikation.
\item Die eindeutig bestimmte Komponente $i$ des charakteristischen Vektors
$(b_{n}(k-1),\ldots,b_{1}(k-1))$ mit $b_{i}(k-1)=\bullet$ nennen
wir seine \emph{signifikante} Komponente. 
\end{enumerate}
\renewcommand{\qedsymbol}{}\end{proof}

Die Indikatorfunktion der Menge aller irreduziblen Implikationen,
die in einem gegebenen Kontext $\mathbb{K}$ gelten, lässt sich effizient
berechnen, indem man das komponentenweise Produkt der Vektoren $(g_{[n]})^{\mathbb{B}_{n}}$
mit $g\in G$ bildet. Diese Indikatorfunktion wird beschrieben durch
die aufsteigende Folge \[
1\le k_{1}<k_{2}<\ldots<k_{s}\le\chi_{n}\]
aller natürlichen Zahlen $k_{i}$, für die $\varepsilon_{k_{i}}=1$
ist. Die zugehörigen irreduziblen Implikationen $y_{i}=(b_{n}(k_{i}-1),\ldots,b_{1}(k_{i}-1))$
für $1\le i\le s$ erhält man daraus nach Satz \ref{Satz:Berchenung_von_b[n](t)}.
Sie definieren eine Folge\begin{equation}
(0,0,\ldots\,0,\bullet)\preceq y_{1}\prec y_{2}\prec\ldots\prec y_{s}\preceq(1,1,\ldots,1,\bullet)\label{Implikationenfolge}\end{equation}
von Vektoren in $\{0,\bullet,1\}^{n}$, die alle Informationen über
das Hüllensystem $\underline{\mathfrak{B}}(\mathbb{K})$ enthält.
Diese Folge ist lexikographisch aufsteigend für $0<\bullet<1$. Aus
ihr lässt sich z.B. wieder der Verband aller abgeschlossenen Teilmengen
von $M$, also der Begriffsverband $\underline{\mathfrak{B}}(\mathbb{K})$,
gewinnen, weil eine Teilmenge $U\subseteq M$ genau dann nicht abgeschlossen
ist, wenn es eine irreduzible Implikation $U\rightarrow\{ x\}$ gibt,
deren Codierung in der Folge (\ref{Implikationenfolge}) vorkommt.

\begin{Def}\label{Def:Antiketten}

\emph{Für jede Zahl $j\in\{1,\ldots,n\}$ bilden wir die Menge \[
L_{j}=\{ y_{i}\,|\,1\le i\le s,j\textrm{ ist die signifikante Komponente von }y_{i}\}\]
Jede Menge $L_{j}$ betrachten wir durch die Produktordnung $\le_{n}$
von $0<\bullet<1$ geordnet und definieren\[
\min L_{j}:=\{ y\in L_{j}\,|\, x\in L_{j},x\le_{n}y\implies x=y\}\]
 als die Menge aller minimalen Elemente von $L_{j}$. Schließlich
sei \[
L:=\bigcup_{1\le j\le n}\min L_{j}\]
 Die Mengen $\min L_{j}$ sind also Antiketten}%
\footnote{Eine Teilmenge $X$ einer geordneten Menge $(M,\le)$ heißt eine Antikette,
wenn je zwei verschiedene Elemente von $X$ unvergleichbar bezüglich
$\le$ sind.%
} \emph{bezüglich $\le_{n}$.}

\end{Def}

Die Mengen $L_{j}$ bzw. $L$ beschreiben Mengen $\mathcal{L}_{j}$
bzw. $\mathcal{L}$ von irreduziblen Implikationen. 

\begin{Lemma}\label{Lemma:Unvergleichbarkeit}

Für je zwei $x,y\in\min L_{j}$ mit $x\not=y$ seien $U\rightarrow\{ u\}$
und $V\rightarrow\{ v\}$ die dargestellten Implikationen. Dann gilt
$u=v$ und $U\not\subseteq V,V\not\subseteq U$.

\end{Lemma}

\begin{Def}\emph{Zwei Vektoren $x\in L_{i}$ und $y\in L_{j}$ verknüpfen
wir zu $x\odot y$, indem wir komponentenweise $0\odot0=0,$ $0\odot1=1\odot0=1\odot1=1$,
$0\odot\bullet=\bullet\odot0=\bullet$ und $\bullet\odot\bullet=\bullet\odot1=1\odot\bullet=0$
berechnen.} \end{Def}

\begin{Lemma}

Es seien $x\in L_{i}$ und $y\in L_{j}$ mit $i\neq j$ und $U\rightarrow\{ u\}$
die von $x$ und $V\rightarrow\{ v\}$ die von $y$ codierte Implikation. 

\begin{lyxlist}{00.00.0000}
\item [Falls~$u\in V$~und~$v\notin 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\odot y$ die Codierung von
$U\cup V\setminus\{ u\}\rightarrow\{ v\}$, d.h. $x\odot y\in L_{j}$. 
\item [Falls~$u\notin V$~und~$v\in 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\odot y$ die Codierung von
$U\cup V\setminus\{ v\}\rightarrow\{ u\}$.
\end{lyxlist}
\end{Lemma}

\begin{proof}

Die Operation $\odot$ beschreibt das dritte der Armstrongaxiome in
den Fällen, in denen nur irreduzible Implikationen beteiligt sind.
\end{proof}

\begin{proof}[Bemerkungen]

\begin{enumerate}
\item \noindent Falls $i=j$ oder keine der beiden vorstehenden Bedingungen
erfüllt ist, liefert das komponentenweise Produkt $x\odot y$ zwar
ein Ergebnis, dieses ist aber nicht die Codierung einer irreduziblen
Implikation. Wir betrachten $x\odot y$ dann als undefiniert. 
\item \noindent Wenn einer der im Lemma genannten Fälle eintritt, schreiben
wir in Anlehnung an die Definition von $\models$ (auf p.\pageref{Folgerung})
$\{ x,y\}\models x\odot y$ (und auch $\{ x,y\}\models U\cup V\setminus\{ u\}\rightarrow\{ v\}$,
sowie $\{ U\rightarrow\{ u\},V\rightarrow\{ v\}\}\models z$ für $z=x\odot y$)%
\footnote{Wir erlauben uns auch, das Zeichen $\equiv$ im gleichen Sinne zwischen
Mengen von Implikationen und Mengen von Codierungen von Implikationen
zu verwenden. %
}. 
\item \noindent Die Definition von $\odot$ erweitern wir für $i\neq j$
durch $L_{i}\odot L_{j}=\{ x\odot y\,|\, x\in L_{i},y\in L_{j}\}$,
und es gilt dann $L_{i}\odot L_{j}\subseteq L_{i}\cup L_{j}$. 
\item 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: \[
\begin{array}{rl}
 & \{ U\rightarrow\{ x_{1},x_{2}\},W\cup\{ x_{1},x_{2}\}\rightarrow Z\}\\
\equiv & \{ U\rightarrow x_{1},U\rightarrow x_{2},(W\cup\{ x_{2}\})\cup\{ x_{1}\}\rightarrow Z\}\\
\textrm{liefert zunächst} & \{ U\rightarrow x_{1},U\rightarrow x_{2},U\cup W\cup\{ x_{2}\}\rightarrow Z\},\\
\textrm{dann} & \{ U\rightarrow x_{1},U\rightarrow x_{2},U\cup W\rightarrow Z\},\\
\textrm{also insgesamt} & \{ U\rightarrow\{ x_{1},x_{2}\},W\cup\{ x_{1},x_{2}\}\rightarrow Z\}\models\{ U\cup W\rightarrow Z\}.\end{array}\]

\end{enumerate}
\renewcommand{\qedsymbol}{}\end{proof}

\begin{Lemma}\label{Lemma:Monotonie}Es seien $x,y$ Codierungen
irreduzibler Implikationen in $Imp(\mathbb{K})$ und $x\odot y$ sei
nicht undefiniert. Dann gilt:

\begin{enumerate}
\item \label{enu:Lemma:Monotonie(1)}$x\not=x\odot y\not=y$;
\item \label{enu:Lemma:Monotonie(2)}Wenn $x\le_{n}y$, dann ist $x\odot y<_{n}y$;
\item \label{enu:Lemma:Monotonie(3)}Wenn $x\odot y\in L_{i}$, dann ist
entweder $x\in L_{i}$ oder $y\in L_{i}$;
\item \label{enu:Lemma:Monotonie(4)}Wenn $x\odot y=z\in L$, dann gibt
es $\tilde{x}$ und $\tilde{y}\in L$ mit $\tilde{x}\odot\tilde{y}=z$. 
\end{enumerate}
\end{Lemma}

\begin{proof}\ref{enu:Lemma:Monotonie(1)}., \ref{enu:Lemma:Monotonie(2)}.
und \ref{enu:Lemma:Monotonie(3)}. folgen direkt aus der Definition
von $\odot$. 

Es seien $x,y\in Imp(\mathbb{K})$ mit $x\odot y=z\in L$. Dann ist
o.B.d.A. $z\in\min L_{i}$, d.h. $x$ hat signifikante Komponente
$i$, und $y$ hat signifikante Komponente $j$ mit $i\not=j$. Die
Behauptung \ref{enu:Lemma:Monotonie(4)}. folgt aus der Monotonie
von $\odot$: Wenn $\tilde{x}$ signifikante Komponente $i$ hat mit
$\tilde{x}\le_{n}x$ und $\tilde{y}$ signifikante Komponente $j$
hat mit $\tilde{y}\le_{n}y$, dann ist $\tilde{x}\odot\tilde{y}\le_{n}z$.
Daher gibt es $\tilde{x}\in\min L_{i}$ und $\tilde{y}\in\min L_{j}$
mit $\tilde{x}\odot\tilde{y}=z$. \end{proof}

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

\begin{Satz}\label{Satz:kanonische_Antikette}Für einen Kontext $\mathbb{K}$
sei die Menge $L$ wie in Definition \ref{Def:Antiketten} gebildet.
Dann gilt:

\begin{enumerate}
\item Die Menge $L$ ist eine Antikette. 
\item \label{enu:L_equiv_Imp(K)}$\mathcal{L}\equiv Imp(\mathbb{K})$ 
\end{enumerate}
\end{Satz}

\begin{proof}Es seien $x\in\min L_{i}$ und $y\in\min L_{j}$ mit
$i\not=j$, so dass $x\le_{n}y$ gilt. Dann ist nach Eigenschaft \ref{enu:Lemma:Monotonie(2)}
von Lemma \ref{Lemma:Monotonie} $x\odot y=z\in L_{j}$ mit $z<_{n}y$,
also war $y$ nicht minimal in $L_{j}$. 

Es gilt $\bigcup_{1\le i\le n}\mathcal{L}_{i}\equiv Imp(\mathbb{K})$
nach Konstruktion und $L_{i}\equiv\min L_{i}$, denn nach dem zweiten
Armstrongaxiom ist jedes $x\in L_{i}$, das nicht minimal (innerhalb
$L_{i}$) bezüglich $\le_{n}$ ist, entbehrlich. \end{proof}

\begin{Def}\emph{Die in Definition \ref{Def:Antiketten} konstruierte
Menge $\mathcal{L}$ von irreduziblen Implikationen heiße die} kanonische
Antikette \emph{$\mathcal{L}(\mathbb{K})$ von $Imp(\mathbb{K})$.}

\end{Def}

Man beachte, dass die kanonische Antikette noch Redundanz aufweisen
kann. Da die Menge \emph{}$\mathcal{L}(\mathbb{K})$ eine Antikette
ist, die nur minimale Elemente enthält, kann diese Redundanz nur von
der Anwendbarkeit des dritten Armstrongaxioms herrühren.


\subsection{Ein Algorithmus zur Bestimmung einer irredundanten Teilmenge}

Der folgende Algorithmus erzeugt aus der kanonischen Antikette $\mathcal{L}$
eine irredundante Teilmenge. Dabei stellen wir irreduzible Implikationen
wieder durch ihre zugehörigen $0,\bullet,1-$Vek\-to\-ren dar. Der
Menge $\mathcal{L}$ entspricht dann eine Menge $L$ von $0,\bullet,1-$Vek\-to\-ren
und die Frage nach einer redundanzfreien Teilmenge von $\mathcal{L}$
transformiert sich in die Frage nach einem minimalen Erzeugendensystem
von $L$ bezüglich $\odot$.

\begin{Def}\emph{Für jede Teilmenge $Y$ von $L$ sei $Y\sptilde$
die Menge aller Elemente von $L$, die durch mindestens einmalige
Anwendung von $\odot$ auf Elemente von $Y$ enstehen:\begin{align*}
Y_{2} & :=Y\odot Y\\
Y_{n+1} & :=Y_{n}\cup\{ x\in L\,|\,\textrm{es gibt }u\in Y_{n},v\in Y\cup Y_{n}\textrm{ mit }x=u\odot v\,\}\\
Y\sptilde & :=\bigcup_{n\ge2}Y_{n}\end{align*}
Weiter sei $\overline{Y}:=Y\cup Y\sptilde$. Die Elemente von $Y\sptilde$
nennen wir} aus \emph{$Y$} echt erzeugt\emph{.}

\end{Def}

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

\begin{Lemma}\label{Lemma:LminusLmalL}Die Menge $Y:=L\setminus(L\odot L)$
aller Elemente von $L$, die sich nicht als Produkt zweier Elemente
von $L$ darstellen lassen, muss in jedem Erzeugendensystem enthalten
sein.\end{Lemma}

\noindent Die Menge $Y$ erzeugt mit Hilfe von $\odot$ eine Teilmenge
$\overline{Y}=Y\cup Y\sptilde\subseteq L$. 

\begin{Algo}\label{Algo: Min_Basis}

\begin{enumerate}
\item Sei $Y_{0}:=Y$
\item Die Menge $Y_{n}$ sei bereits konstruiert. Nach Lemma \ref{Lemma:LminusLmalL}
ist $Y_{n}=Y\cup Z_{n}$ mit $Z_{n}\subseteq L\setminus Y$.
\item (a) Falls $\overline{Y_{n}}=L$, dann gib $E:=Y_{n}$ aus.\\
(b)\label{enu:Falls} Falls $\overline{Y_{n}}\not=L$, dann gibt es
$z\in L\setminus\overline{Y_{n}}$. Die Menge $Y_{n}\cup\{ z\}$ erzeugt
eine Menge $\overline{Y_{n}\cup\{ z\}}=Y_{n}\cup\{ z\}\cup(Y_{n}\cup\{ z\})\sptilde$.
Die Menge $Y_{n+1}$ ist dann \[
Y_{n+1}:=(Y_{n}\setminus(Y_{n}\cup\{ z\})\sptilde)\cup\{ z\}=Y\cup(Z_{n}\setminus(Y_{n}\cup\{ z\})\sptilde)\cup\{ z\}\]

\end{enumerate}
\end{Algo}

\begin{proof}[Bemerkung]Die Gleichung\begin{equation}
(Y_{n}\setminus(Y_{n}\cup\{ z\})\sptilde)\cup\{ z\}=Y\cup(Z_{n}\setminus(Y_{n}\cup\{ z\})\sptilde)\cup\{ z\}\label{eq:Induktionsschritt}\end{equation}
folgt nach Definition von $Y$. Da das Element $z$ möglicherweise
selbst aus $Y_{n}\cup\{ z\}$ echt erzeugbar ist, gilt i.A. $(Y_{n}\setminus(Y_{n}\cup\{ z\})\sptilde)\cup\{ z\}\not=(Y_{n}\cup\{ z\})\setminus(Y_{n}\cup\{ z\})\sptilde$.
Alle Vereinigungszeichen in Gleichung (\ref{eq:Induktionsschritt})
sind daher als disjunkte Vereinigung zu lesen. Dies garantiert, dass
im Laufe des Algorithmus für jedes Paar $(x,y)\in L\times L$ nur
einmal das Produkt $x\odot y$ berechnet zu werden braucht.\renewcommand\qedsymbol{}\end{proof}

\begin{Kor}\label{Kor:Bei-jeder-Anwendung}Bei jeder Anwendung von
Schritt \ref{enu:Falls}(b) gilt $\overline{Y_{n}}\subsetneq\overline{Y_{n+1}}$.
Der Fall $\overline{Y_{n+1}}=L$ tritt daher nach spätestens $|L\setminus Y|$
Schritten ein.\end{Kor}\begin{proof}Bei jeder Anwendung von Schritt
\ref{enu:Falls}(b) ist zunächst nach Konstruktion $z\not\in\overline{Y_{n}}$,
$z\in\overline{Y_{n+1}}$. Weiter gilt: Jedes $y\in Y_{n}\sptilde$
, das bei seiner Erzeugung aus $Y_{n}$ ein $x\in Z_{n}$ benutzt,
das selbst wieder echt aus $Y_{n}\cup\{ z\}$ erzeugbar ist, kann
über der Menge $(Y_{n}\setminus(Y_{n}\cup\{ z\})\sptilde)\cup\{ z\}$
erzeugt werden. Daher gilt auch $\overline{Y_{n}}=Y_{n}\cup Y_{n}\sptilde=Y\cup Z_{n}\cup(Y\cup Z_{n})\sptilde\subseteq\overline{Y_{n+1}}$.\end{proof}

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

\begin{enumerate}
\item $E$ ist ein minimales Erzeugendensystem für $L$.
\item Die Menge $E$ beschreibt eine Menge $\mathcal{E}$ von irreduziblen
Implikationen. \emph{$\mathcal{E}$} ist eine (inklusions-)minimale
Teilmenge von $\mathcal{L}$ mit $\mathcal{E}\equiv\mathcal{L}$. 
\item Für $L=\mathcal{L}(\mathbb{K})$ ist $\mathcal{E}$ ist eine Basis
für $Imp(\mathbb{K})$.
\end{enumerate}
\end{Satz}

\begin{proof}Die Aussage 2. ist Umformulierung von Aussage 1. und
Aussage 3. folgt wegen $L\equiv Imp(\mathbb{K})$. 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\in Y_{n+1}$, das über $Y_{n+1}\setminus\{ x\}$ erzeugbar ist.
Dann ist $x\not\in Y$; ebenso ist $x=z$ unmöglich, da $z$ nicht
über $Y_{n}=Y\cup Z_{n}$, also erst recht nicht über $Y\cup(Z_{n}\setminus(Y_{n}\cup\{ z\})\sptilde)$
erzeugbar ist. Daher ist $x$ erzeugbar über $Y_{n+1}\setminus\{ x,z\}$.

Also ist $x\in Z_{n}\setminus(Y_{n}\cup\{ z\})\sptilde$, d.h. $x\in Y_{n}$,
und $x$ ist erzeugbar über $Y_{n+1}\setminus\{ x,z\}\subseteq Y\cup Z_{n}\setminus\{ x\}$.
Dann ist also auch $Y_{n}$ kein minimales Erzeugendensystem gewesen.\end{proof}

\begin{proof}[Bemerkungen]Den Algorithmus \ref{Algo: Min_Basis}
kann man nach einer leichten Modifikation verwenden, um auch für jede
andere vollständige Teilmenge $D$ von $Imp(\mathbb{K})$ ein äquivalentes
Teilsystem $E$ zu erhalten. Dazu ist die Bedingung im Punkt \ref{enu:Falls}
abzuändern in $\overline{Y_{n}}\supseteq L$ bzw. $\overline{Y_{n}}\not\not\supseteq 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\odot y<z$
gilt. Das Element $z$ ist dann redundant. Es gilt aber stets $\omega(E)\le\omega(D)$.

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

Das Beispiel $\mathcal{L}=\{\{1,4\}\rightarrow2,\{3,4\}\rightarrow2,\{1,4\}\rightarrow3,\{2,4\}\rightarrow3\}$
zeigt, dass das Ergebnis des Algorithmus von der Strategie abhängt,
mit der im Schritt \ref{enu:Falls} des Algorithmus \ref{Algo: Min_Basis}
das Element $z$ ausgewählt wird. Die für $\mathcal{L}(\mathbb{K})$
produzierte Menge $\mathcal{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 $\mathbb{K}$
mit $n$ Merkmalen ist nach Satz \ref{Satz:kanonische_Antikette}
$n-$fach parallel durchführbar. 

Wenn man die Anzahl der Multiplikationen $\odot$ und nicht die Anzahl
der Schleifendurchläufe in Algorithmus \ref{Algo: Min_Basis} als
Maßstab nimmt, kann man nach der Bemerkung vor Korollar \ref{Kor:Bei-jeder-Anwendung}
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 $\mathbf{2}^{n-1}$, also $|\min L_{i}|\le{{n-1 \choose \left\lceil \frac{n-1}{2}\right\rceil }}$.
Legt man also die Anzahl $n$ der Merkmale des zugrundeliegenden Kontexts
$\mathbb{K}$ als Maßstab an, so folgt für die Laufzeit des Algorithmus
die obere Schranke $O(4^{n})$.\renewcommand{\qedsymbol}{}\end{proof}

Der folgende Satz stellt einen engen Zusammenhang zwischen jeder Basis,
die der Algorithmus \ref{Algo: Min_Basis} erzeugt, und der Duquenne-Guigues-Basis
her.

\enlargethispage{-\baselineskip}\begin{Satz}\label{Satz:Duquenne}

Es sei $\mathcal{D}(\mathbb{K})$ die Duquenne-Guigues-Basis des Kontexts
$\mathbb{K}$, geschrieben in irreduziblen Implikationen und $\mathcal{E}$
eine Basis für $Imp(\mathbb{K})$, die der Algorithmus \ref{Algo: Min_Basis}
liefert, wenn er mit \emph{$\mathcal{L}(\mathbb{K})$} gestartet wird.

Zu jeder Implikation $P\rightarrow u$ von $\mathcal{D}(\mathbb{K})$
gibt es eine Implikation $U\rightarrow u$ in \emph{$\mathcal{L}(\mathbb{K})$}
mit $U\subseteq P$.

Zu jeder Implikation $U\rightarrow u$ in $\mathcal{E}$ gibt es genau
eine minimale (bezüglich $\le_{n}$) Implikation $P\rightarrow u$
in $\mathcal{D}(\mathbb{K})$ mit $U\subseteq P$. 

\end{Satz}

\begin{proof}

Die erste Eigenschaft folgt aus $\mathcal{L}(\mathbb{K})\equiv\mathcal{D}(\mathbb{K})\equiv Imp(\mathbb{K})$.

Offenbar ist $\mathcal{E}\subseteq\mathcal{L}(\mathbb{K})$. Es sei
$U\rightarrow u$ eine Implikation in $\mathcal{E}$, die nicht zu
$\mathcal{D}(\mathbb{K})$ gehört. Da $\mathcal{E}$ irredundant ist,
gibt es eine minimale Menge $P$ mit der Eigenschaft \[
P\vdash\mathcal{E}\setminus\{ U\rightarrow u\}\textrm{ und }P\not\vdash\mathcal{E}\]
Dann gilt $U\subseteq P$ und $u\not\in P$, also $P''\supseteq P\cup\{ u\}$
und für jede echte Teilmenge $Q\subseteq P,P\not=Q$ gilt $Q\vdash\mathcal{E}$,
also $Q''\subseteq P$. Daher ist $P$ ein Pseudoinhalt und es gilt
$P\rightarrow u\in\mathcal{D}(\mathbb{K})$.

Es seien $U\rightarrow u$ und $V\rightarrow u$ zwei verschiedene
Implikationen in $\mathcal{E}$ und $P\subseteq M$ mit \[
P\vdash\mathcal{E}\setminus\{ U\rightarrow u\}\textrm{ und }P\not\vdash\mathcal{E}\]
sowie \[
P\vdash\mathcal{E}\setminus\{ V\rightarrow u\}\textrm{ und }P\not\vdash\mathcal{E}\]
Da $U\not=V$ gilt, folgt aus der ersten Bedingung $P\vdash V\rightarrow u$,
was der zweiten Bedingung widerspricht. \end{proof}

\begin{Kor}

Für jedes Ergebnis $\mathcal{E}$ des Algorithmus \ref{Algo: Min_Basis}
gilt:\[
\omega(\mathcal{E})\le\omega(\mathcal{D}(\mathbb{K}))\]
 \end{Kor}

\begin{proof}Nach Satz \ref{Satz:Duquenne} gibt es eine injektive
und $\le_{n}-$monotone Abbildung $f:\mathbf{2}^{n}\longrightarrow\mathbf{2}^{n}$,
für die die Zuordnung $U\rightarrow u\mapsto f(U)\rightarrow u$ eine
Injektion $\mathcal{E}\longrightarrow\mathcal{D}(\mathbb{K})$ definiert.
Es folgt:\[
\omega(\mathcal{Y})=\sum_{U\rightarrow u\in\mathcal{E}}|U|\le\sum_{U\rightarrow u\in\mathcal{E}}|f(U)|\le\sum_{P\rightarrow P''\in\mathcal{D}(\mathbb{K})}|P|\cdot|P''\setminus P|=\omega(\mathcal{D}(\mathbb{K}))\]
\end{proof}


\section{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 \ref{sec:Anwendungen} durchgeführt,
für einen gegebenen Kontext $\mathbb{K}$ mit $n$ Merkmalen das ,,maximale
Rechteck'' $(\mathfrak{K},Imp(\mathbb{K}))$, das in $\mathbb{H}_{n}$
enthalten ist und dessen erste Komponente aus den Zeilen des Kontexts
$\mathbb{K}$ besteht, einfach bestimmbar. Dieses Rechteck ist ein
Begriff des Kontexts $\mathbb{H}_{n}$; sein Begriffsumfang ist ein
Mengensystem, bestehend aus den Zeilen von $\mathbb{K}$. Insoweit
sind $\mathbb{K}$ und $(\mathfrak{K},Imp(\mathbb{K}))$ äquivalent.
Wie bei allen Begriffen stellt sich die Frage nach einer einfachen
Beschreibung von $(\mathfrak{K},Imp(\mathbb{K}))$, also einem Paar
$(\mathfrak{X},\mathcal{Y})$ mit $\mathfrak{X}^{\vdash}=Imp(\mathbb{K})$
und $\mathcal{Y}^{\vdash}=\mathfrak{K}$. Die Vereinfachung von $Imp(\mathbb{K})$
besteht in der Beseitigung von Redundanz. Falls der Ausgangskontext
$\mathbb{K}$ reduziert ist, ist zumindest die erste Komponente $\mathfrak{K}$
in kanonischer Form. Ansonsten liefert Zeilenreduktion (in $\mathbb{K}$
statt in $\mathbb{H}_{n}$!) diese Form. Eine der möglichen kanonischen
Formen ist das Paar $(\mathfrak{K},\mathcal{D}(\mathbb{K}))$, mit
der Duquenne-Guigues-Basis $\mathcal{D}(\mathbb{K})$ als Merkmalmenge.

Die Eigenschaft (\ref{Aquivalenz 2}) liefert den ersten Schritt bei
der Vereinfachung von $Imp(\mathbb{K})$: die Beschränkung auf die
irreduziblen Implikationen. Nach (\ref{Aquivalenz 3}) (oder dem zweiten
Armstrongaxiom) ist der Übergang zur kanonischen Antikette eine weitere
Vereinfachung. Sie liefert als kanonische Form das Paar $(\mathfrak{K},\mathcal{L}(\mathbb{K}))$.
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 \ref{Anhang1:Ein-Beispiel} ausgeführt. 

Für gewisse Anwendungen ist es jedoch angebracht, statt des Begriffs
$(\mathfrak{K},Imp(\mathbb{K}))$ oder einer seiner möglichen Vereinfachungen
(z.B. $(\mathfrak{K},\mathcal{L}(\mathbb{K}))$) seine Erweiterung
zu einem Kontext $(\mathfrak{K},\mathcal{X}_{n},\vdash)$ zu betrachten.
Die Wirkung von $(\mathfrak{K},\mathcal{L}(\mathbb{K}))$ innerhalb
dieses Kontexts ist bekannt unter dem Namen ,,Hintergrundimplikationen'',
d.h. die Implikationenmenge $\mathcal{L}(\mathbb{K})$ kann man durch
weitere Implikationen, deren Gültigkeit man sich wünscht, vergrößern,
was den zugehörigen Begriffsumfang zu einem Teilkontext von $\mathbb{K}$
verkleinert. Im Anhang \ref{Anhang2:Konstruktion-von-Teilsystemen}
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 $\mathbb{B}_{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 $(\mathbf{2}^{n},\mathcal{L}(\mathbb{K}),\vdash)$,
wobei man jetzt $(\mathfrak{K},\mathcal{L}(\mathbb{K}))$ 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 $(\mathfrak{K},\mathcal{X}_{n},\vdash)$ verändern:
Wir sehen seine Zeilen nicht als boolesche, sondern als rationale
$0,1-$Vektoren der Länge $\chi_{n}$. Spaltenweise aufsummiert, erhält
man für jede Implikation in $\mathcal{X}_{n}$ die Anzahl der Gegenstände
des Kontexts $\mathbb{K}$, 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.

\begin{thebibliography}{1}
\bibitem{key-9}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).
\bibitem{key-15}J. Demetrovics, L. Libkin, I. Muchnik: Functional Dependencies in
Relational Databases: A Lattice Point of View. Discrete Applied Mathematics
40(2): 155--185 (1992)
\bibitem{key-3}B. Ganter, R. Wille: \emph{Formale Begriffsanalyse: Mathematische
Grundlagen}. Springer Verlag Heidelberg, 1996, ISBN 3-540-60868-0.
\bibitem{key-4}B. Ganter: Begriffe und Implikationen, in: Stumme, Wille (Hrsg.):
\emph{Begriffliche Wissensverarbeitung -- Methoden und Anwendungen},
pp.1--24, Springer Verlag, 2000, ISBN 3-540-66391-6
\bibitem{key-6}L. Libkin: Direct product decompositions of lattices, closures and
relation schemes. Discrete Mathematics 112: 119--138 (1993).
\bibitem{key-11}M. Wild: A theory of finite closure spaces based on implications.
Adv. in Math. 108: 118--139 (1994).
\bibitem{key-5}Download von \\
\texttt{www.mathematik.tu-darmstadt.de/ags/ag1/Software/software\_en.html}
\end{thebibliography}
\appendix

\section{\label{sec:Anhang}Anhang }


\subsection{\label{Anhang1:Ein-Beispiel}Ein Beispiel}

Um den Algorithmus \ref{Algo: Min_Basis} an einem nicht trivialen
Beispiel zu demonstrieren, untersuchen wir den Kontext $\mathbb{P}_{4}=(G,M,\diamond)$,
dessen Begriffsverband der Verband aller Äquivalenzrelationen auf
einer vierelementigen Menge ist. Die Bildung von $\mathbb{P}_{4}$
ist in \cite{key-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=\boldsymbol2^{\{ a,b,c\}}$,
$M={{\{ a,b,c,d\} \choose 2}}$%
\footnote{Für eine beliebige Menge $S$ bezeichne ${{S \choose 2}}$ die Menge
aller $2-$elementigen Teilmengen der Menge $S$.%
} und \(\mathbb{P}_4\) sei der Kontext%
\footnote{Die Vertauschung von $G$ und $M$ in $\mathbb{P}_{4}$ ergibt als
Begriffsverband den zum üblichen Äquivalenzrelationenverband dualen
Verband. %
}

\vspace{10pt}\[ \begin{tabular}{r||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}

$$ & $ b$ & $c$ & $c$ & $d$ & $ d$ & $d$ \\

$ $ & $ a$ & $b$ & $a$ & $c$ &$ b$ & $a$  \\

\hline \hline

$\emptyset$ & $\times$ & $ \times$ & $\times$ & $ \times$ & $\times$& $\times$ \\ \hline 

$a$ & $ $ &$\times$ & $$ & $ \times$ &$\times$& $$ \\ \hline 

$b$ & $ $ & $$ & $\times$ &$\times$ & $$& $\times$ \\ \hline 

$b,a$ & $ \times$ & $$ & $$ & $\times $ &$$& $$ \\ \hline \hline

$c$ & $\times $ & $$ & $$ & $$ & $\times$ & $\times$ \\ \hline 

$c,a$ & $ $ & $ $& $\times$ & $ $ & $\times$ & $$ \\ \hline 

$c,b$ & $ $& $\times$ & $ $ &$$ & $$ &$\times$ \\ \hline 

$c,b,a$ & $ \times$ &$ \times$ & $ \times$ & $ $ & $ $ & $ $ \\ \hline 

\end{tabular}\]\vspace{10pt}

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 $\rho$ heißt
dies: \[
\bigl\{\{ x,y\},\{ y,z\}\bigr\}\subseteq\rho\implies\bigl\{\{ x,z\}\bigr\}\subseteq\rho\]
 für alle $x,y,z\in S$; also müssen wir nachweisen, dass jeder Gegenstandsinhalt
für beliebige $x,y,z\in S$ die irreduzible Implikation $\bigl\{\{ x,y\},\{ y,z\}\bigr\}\rightarrow\bigl\{\{ x,z\}\bigr\}$
respektiert. Wir suchen $\bigcap_{g\in G}(\{ g\}')^{\vdash}$, also
alle Stellen, die in allen $(g_{[6]})^{\mathbb{B}_{6}}$ mit $g\in G$
vorkommen; das komponentenweise Produkt $\varepsilon$ aller $(g_{[6]})^{\mathbb{B}_{6}}$
mit $g\in G$ liefert gerade deren Indikatorfunktion. 

Obwohl der Kontext $\mathbb{B}_{6}$ schon $\chi_{6}=192$ Merkmale
hat, können wir diese Indikatorfunktion mit einigem Aufwand noch per
Hand berechnen%
\footnote{Bei der Konstruktion von $\mathbb{B}_{6}$ sowie bei der Untersuchung
anderer Beispiele hat das Darmstädter System \texttt{ConImp} \cite{key-5}
nützliche Dienste geleistet. %
}:

Die erste Zeile von $\mathbb{P}_{4}$ besteht nur aus Einsen, also
liefert die Konstruktion von $(\emptyset_{[6]})^{\mathbb{B}_{6}}=1^{192}$,
was nicht zum komponentenweisen Produkt beiträgt. \begin{eqnarray*}
a_{[6]}^{\mathbb{B}_{6}} & = & (0,a_{[5]})^{\mathbb{B}_{6}}=\textrm{ }(\textrm{wegen }a_{6}=0)\\
 & = & ((a_{[5]})^{\mathbb{B}_{5}},(a_{[5]})^{\mathbb{A}_{5}},1^{80})=\textrm{ }(\textrm{wegen }a_{5}=1)\\
 & = & ((a_{[4]})^{\mathbb{B}_{4}},1^{16},(a_{[4]})^{\mathbb{B}_{4}},(a_{[4]})^{\mathbb{A}_{4}},(a_{[4]})^{\mathbb{A}_{4}},1^{80})=\textrm{ }(\textrm{weil }a_{4}=0)\\
 & = & ((a_{[3]})^{\mathbb{B}_{3}},(a_{[3]})^{\mathbb{A}_{3}},1^{12},1^{16},(a_{[3]})^{\mathbb{B}_{3}},(a_{[3]})^{\mathbb{A}_{3}},1^{12},(a_{[3]})^{\mathbb{A}_{3}},1^{8},(a_{[3]})^{\mathbb{A}_{3}},1^{88})\end{eqnarray*}
Die $0,1-$Vektoren für den Index $n=3$ lassen sich direkt aus $\mathbb{B}_{3}$
und $\mathbb{A}_{3}$ ablesen, wodurch man erhält: \[
a_{[6]}^{\mathbb{B}_{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{array}{rl}
b_{[6]}^{\mathbb{B}_{6}} & =10011^{4}10011^{8}10011^{4}1001(0011)^{4}1^{32}(0011)^{4}1^{16}1^{80}\vspace{5pt}\\
b,a_{[6]}^{\mathbb{B}_{6}} & =00111^{4}0011(0111)^{2}1^{12}(0111)^{2}1^{72}00111^{4}0011(0111)^{2}1^{12}(0111)^{2}1^{40}\vspace{5pt}\\
c_{[6]}^{\mathbb{B}_{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}\vspace{5pt}\\
c,a_{[6]}^{\mathbb{B}_{6}} & =011001011^{4}1^{8}011001011^{4}01011^{4}01011^{4}1^{32}01011^{4}01011^{4}1^{16}1^{80}\vspace{5pt}\\
c,b_{[6]}^{\mathbb{B}_{6}} & =100100111^{4}00111^{4}1^{12}1^{16}100100111^{4}00111^{4}1^{12}00111^{4}1^{8}00111^{92}\vspace{5pt}\\
c,b,a_{[6]}^{\mathbb{B}_{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{array}\]
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\cdot\chi_{3}+1\cdot2^{2}+0\cdot2^{1}+1\cdot2^{0}$
die Implikation $\{3,1\}\rightarrow\{4\}$, und weil die Merkmale
in $\mathbb{P}_{4}$ von rechts nach links durchnummeriert sind, heißt
dies $\bigl\{\{ c,d\},\{ a,d\}\bigr\}\rightarrow\bigl\{\{ a,c\}\bigr\}$.
Alle Buchstaben in $\mathbb{P}_{4}$ sind gleichberechtigt, d.h. $\mathbb{P}_{4}$
ist invariant unter allen Permutationen der Grundmenge $\{ a,b,c,d\}$,
also gilt für jeden Begriffsinhalt von $\rho\in\mathbb{P}_{4}$: $\rho$
ist transitiv, also eine Äquivalenzrelation. Auf diese Weise haben
wir die Transitivität aller Begriffe von $\underline{\mathfrak{B}}(\mathbb{P}_{4})$
\emph{durch schlichtes Nachrechnen} im Verband aller Hüllensysteme
bewiesen. 

Außer diesen 12 Implikationen gibt es aber offenbar noch weitere.
Um die kanonische Antikette zu finden, wenden wir Satz \ref{Satz:kanonische_Antikette}
an und berechnen \[
\begin{array}{lcl}
L_{1} & = & \{29,32,72,77,80,116,124,136,141,144,164,169,172,184,189,192\}\vspace{1pt}\\
L_{2} & = & \{58,59,71,78,79,115,123,135,142,143,163,170,171,183,190,191\}\vspace{1pt}\\
L_{3} & = & \{26,28,55,56,74,75,76,138,139,140,166,167,168,186,187,188\}\vspace{1pt}\\
L_{4} & = & \{18,20,64,66,68,130,131,132,173,174,175,176,177,178,179,180\}\vspace{1pt}\\
L_{5} & = & \{39,40,44,47,48,150,151,152,153,154,155,156,157,158,159,160\}\vspace{1pt}\\
L_{6} & = & \{84,88,92,95,96,100,102,104,105,106,107,108,109,110,111,112\}\end{array}\]
Unter Ausnutzung der Eigenschaft $x<_{6}y\implies x\prec y$ findet
man die minimalen Antiketten:

\noindent \begin{align*}
X_{1} & =\{29,72,116,169\}\\
 & =\{\{3,4\}\rightarrow1,\{2,4,5\}\rightarrow1,\{2,6\}\rightarrow1,\{3,5,6\}\rightarrow1\}\\
X_{2} & =\{58,71,115,142\}\\
 & =\{\{3,5\}\rightarrow2,\{1,4,5\}\rightarrow2,\{1,6\}\rightarrow2,\{3,4,6\}\rightarrow2\}\\
X_{3} & =\{26,55,139,166\}\\
 & =\{\{1,4\}\rightarrow3,\{2,5\}\rightarrow3,\{2,4,6\}\rightarrow3,\{1,5,6\}\rightarrow3\}\\
X_{4} & =\{18,64,131,173\}\\
 & =\{\{1,3\}\rightarrow4,\{1,2,5\}\rightarrow4,\{2,3,6\}\rightarrow4,\{5,6\}\rightarrow4\}\\
X_{5} & =\{39,44,150,153\}\\
 & =\{\{2,3\}\rightarrow5,\{1,2,4\}\rightarrow5,\{1,3,6\}\rightarrow5,\{4,6\}\rightarrow5\}\\
X_{6} & =\{84,95,102,105\}\\
 & =\{\{1,2\}\rightarrow6,\{2,3,4\}\rightarrow6,\{1,3,5\}\rightarrow6,\{4,5\}\rightarrow6\}\end{align*}


\noindent Deren Vereinigung ist die kanonische Antikette \[
L=\mathcal{L}(\mathbb{P}_{4})=X_{1}\cup\ldots\cup X_{6}\]
 Um die Menge $Y\equiv L\setminus L\odot L$ aller Implikationen,
die nach Lemma \ref{Lemma:LminusLmalL} in jedem Erzeugendensystem
enthalten ist, zu finden, benutzen wir die Eigenschaft $X_{i}\odot X_{j}\subseteq X_{i}\cup X_{j}$
und die Kommutativität von $\odot$ und bilden die Produkte \[ \begin{split}
X_{1}\odot X_{2}=\bigl \{ & \{3,4,5\}\rightarrow 1,\{3,5,6\}\rightarrow 1,\{3,4,5,6\}\rightarrow 1,\{3,4,6\}\rightarrow 1, \\ 
&\{3,4,5\}\rightarrow 2,\{3,4,6\}\rightarrow 2,\{3,4,5,6\}\rightarrow 2,\{3,5,6\}\rightarrow 2\bigr \} \\ 
X_{1}\odot X_{3}=\bigl \{ & \{2,4,5\}\rightarrow 1,\{2,5,6\}\rightarrow 1,\{2,4,6\}\rightarrow 1,\{2,4,5,6\}\rightarrow 1, \\ 
&\{2,4,5\}\rightarrow 3,\{2,4,5,6\}\rightarrow 3,\{2,4,6\}\rightarrow 3,\{2,5,6\}\rightarrow 3\bigr \} \\ 
\end{split} \] 

\noindent Bereits hier ist klar, dass $X_{1}\setminus(L\odot L)=\bigl\{\{3,4\}\rightarrow1,\{2,6\}\rightarrow1\bigr\}$
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

\begin{center}$X_{2}\setminus(L\odot L)=\bigl\{\{3,5\}\rightarrow2,\{1,6\}\rightarrow2\bigr\}$\end{center}

\begin{center}$X_{3}\setminus(L\odot L)=\bigl\{\{1,4\}\rightarrow3,\{2,5\}\rightarrow3\bigr\}$\end{center}

\begin{center}$X_{4}\setminus(L\odot L)=\bigl\{\{1,3\}\rightarrow4,\{5,6\}\rightarrow4\bigr\}$\end{center}

\begin{center}$X_{5}\setminus(L\odot L)=\bigl\{\{2,3\}\rightarrow5,\{4,6\}\rightarrow5\bigr\}$\end{center}

\begin{center}$X_{6}\setminus(L\odot L)=\bigl\{\{1,2\}\rightarrow6,\{4,5\}\rightarrow6\bigr\}$\end{center}

Man erhält $Y$ als Vereinigung dieser Mengen und nach Verfikation
der Eigenschaft $\overline{Y}=L$ bricht der Algorithmus \ref{Algo: Min_Basis}
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 $\mathcal{Y}$) mit Hilfe der
Armstrongaxiome herleitbar ist: \\
\[ \begin{split}
\mathcal {E}=\mathcal{Y}=\bigl \{ & \{3,4\}\rightarrow 1,\{2,6\}\rightarrow 1,\{3,5\}\rightarrow 2,\{1,6\}\rightarrow 2, \\ 
& \{1,4\} \rightarrow 3,\{2,5\}\rightarrow 3,\{1,3\}\rightarrow 4,\{5,6\}\rightarrow 4, \\
& \{2,3\} \rightarrow 5,\{4,6\}\rightarrow 5,\{1,2\}\rightarrow 6,\{4,5\}\rightarrow 6 \bigr \} \\ 
\end{split} \]


\subsection{\label{Anhang2:Konstruktion-von-Teilsystemen}Konstruktion von Teilsystemen}


\subsubsection{Allgemeine Teilsysteme }

Der Begriffsverband $\underline{\mathfrak{B}}(\mathbb{K})$ eines
Kontextes $\mathbb{K}=(G,M,I)$ mit höchstens $n$ Merkmalen wird
repräsentiert durch ein Hüllensystem auf einer $n-$elementi\-gen
Menge und ist daher ein Begriff im Begriffsverband $\underline{\mathfrak{B}}(\mathbb{B}_{n})$
des Kontextes $\mathbb{B}_{n}=(\boldsymbol2^{n},\mathcal{X}_{n},\vdash)$.
$\underline{\mathfrak{B}}(\mathbb{K})$ wird also beschrieben durch
ein maximales Rechteck $(A,\mathcal{B})$ in $\mathbb{B}_{n}$%
\footnote{das heißt: für jedes $a\in A$ und jedes $U\rightarrow V\in\mathcal{B}$
gilt $a\vdash U\rightarrow V$, und sowohl $A$, als auch $\mathcal{B}$
sind inklusionsmaximal für diese Eigenschaft. %
}; dessen Seiten sind einerseits $A\supseteq\{ g'\,|\, g\in G\}=\mathbb{K}(G)$,
und $\mathcal{B}$ ist die Menge $Imp(\mathbb{K})$ der irreduziblen
Implikationen, die $\mathbb{K}$ erfüllt. Wir betrachten daher im
Folgenden Kontexte der Form $\mathbb{K}\circ\mathbb{B}_{n}$. 

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

Eine andere Möglichkeit, sich die Menge $\mathcal{G}$ vorzugeben,
ist, eine Teilmenge $\mathcal{F}\subseteq\mathcal{G}$ dadurch zu
spezifizieren, dass man einen Kontext $\mathbb{K}_{\mathcal{F}}$
angibt, von dem man schon weiß, dass er die Eigenschaft $Imp(\mathbb{K}_{\mathcal{F}})\equiv\mathcal{F}$
hat, und die restlichen Bedingungen explizit zu erzwingen. Ist $\mathbb{K}_{\mathcal{F}}$
ein solcher Kontext, dann betrachten wir $\mathbb{K}_{\mathcal{F}}\circ\mathbb{B}_{n}$
für das passende $n\in\mathbb{N}$. Die Begriffsinhalte dieses Kontextes
sind die abgeschlossenen Implikationenmengen, die $\mathcal{F}$ enthalten,
also ist $\underline{\mathfrak{B}}(\mathbb{K}_{\mathcal{F}}\circ\mathbb{B}_{n})$
der Verband aller Hüllensysteme auf dem Verband der Begriffsinhalte
von $\mathbb{K}_{\mathcal{F}}$. 

Dabei benutzen wir eine Verallgemeinerung des Begriffs ,,Hüllensystem'':
Eine Teilmenge $\mathfrak{U}$ eines vollständigen Verbands $\mathfrak{V}$
heißt ein Hüllensystem auf $\mathfrak{V}$, wenn gilt\[
\mathfrak{X}\subseteq\mathfrak{U}\implies\inf\mathfrak{X}\in\mathfrak{U}\]


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 $\mathbb{P}_{n}$ gegeben, und wir wissen schon, dass
$Imp(\mathbb{P}_{n})$ die von der Transitivität $\{\{ x,y\},\{ y,z\}\}\rightarrow\{ x,z\}$
(durch Instantiierung $x,y,z\in 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 \begin{equation}
\{\{ x_{i},y_{i}\}\}\rightarrow\{ f(x_{1},\ldots,x_{i-1},x_{i},x_{i+1},\ldots,x_{k}),f(x_{1},\ldots,x_{i-1},y_{i},x_{i+1},\ldots,x_{k})\}\label{Kongruenz}\end{equation}
 für alle $i\in\{1,\ldots,k\}$ und alle $x_{1},\ldots,x_{k},y_{i}\in M$
erforderlich macht. 

Am Beispiel der zyklischen Gruppe $(\mathbb{Z}_{4},+)$ und der Gruppe
$(\mathbb{Z}_{2}\times\mathbb{Z}_{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 \ref{Anhang1:Ein-Beispiel}
durch den Kontext $\mathbb{P}_{4}$ beschrieben. Weiter identifizieren
wir die Elemente $0,1,2,3$ von $\mathbb{Z}_{4}$ mit $a,b,c,d$ und
nützen aus, dass $b$ dann ein erzeugendes Element von $\mathbb{Z}_{4}$
ist. Auf diese Weise müssen wir nach (\ref{Kongruenz}) und wegen
der Kommutativität nur noch fordern: \begin{eqnarray*}
\{\{ a,b\}\}\rightarrow\{ b,c\},\{\{ b,c\}\}\rightarrow\{ c,d\},\,\{\{ a,c\}\}\rightarrow\{ b,d\},\{\{ c,d\}\}\rightarrow\{ a,d\},\\
\{\{ b,d\}\}\rightarrow\{ a,c\},\{\{ a,d\}\}\rightarrow\{ a,b\}\phantom,\end{eqnarray*}
Umgeschrieben in Merkmale von $\mathcal{X}_{6}$ heißt dies: \begin{eqnarray*}
(1,\bullet,0,0,0,0),(0,1,0,\bullet,0,0),(0,0,1,0,\bullet,0),(0,0,0,1,0,\bullet),\\
(0,0,\bullet,0,1,0),(\bullet,0,0,0,0,1)\phantom,\end{eqnarray*}
 Wir müssen also im Kontext \[
\mathbb{P}_{4}\circ\mathbb{B}_{6}=(\{ g^{\mathbb{P}_{4}}\,|\, g\in\boldsymbol2^{3}\},\mathcal{X}_{6},\vdash)\]
 - wobei die Zeile $\mathbb{P}_{4}\circ\mathbb{B}_{6}(\emptyset)$
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 $\mathbb{P}_{4}$ besteht,
und dessen Begriffsverband ist tatsächlich der Kongruenzenverband
von $\mathbb{Z}_{4}$. 

Dieselbe Konstruktion für die Gruppe $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$
mit der Zuordnung $(0,0)\leftrightarrow a,(0,1)\leftrightarrow b,(1,0)\leftrightarrow c,(1,1)\leftrightarrow d$
liefert\begin{eqnarray*}
\{\{ a,b\}\}\rightarrow\{ c,d\},\{\{ b,c\}\}\rightarrow\{ a,d\},\{\{ a,c\}\}\rightarrow\{ b,d\},\{\{ c,d\}\}\rightarrow\{ a,b\},\\
\{\{ b,d\}\}\rightarrow\{ a,c\},\{\{ a,d\}\}\rightarrow\{ b,c\}\phantom,\end{eqnarray*}
 Die entsprechenden Spalten in $\mathbb{P}_{4}\circ\mathbb{B}_{6}$
haben die folgenden Merkmale mit den zugehörigen Spaltennummern \begin{eqnarray*}
(1,0,0,\bullet,0,0)\approx117, & (0,1,0,0,0,\bullet)\approx49, & (0,0,1,0,\bullet,0)\approx22\\
(\bullet,0,0,1,0,0)\approx85, & (0,0,\bullet,0,1,0)\approx15, & (0,\bullet,0,0,0,1)\approx34\end{eqnarray*}
 Als Gegenstände, die diese Implikationen respektieren, erhält man\break
$(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 $\mathbb{P}_{4}$. $(1,0,0,1,0,0)$
beschreibt den Kern der Projektion $\mathbb{Z}_{2}\times\mathbb{Z}_{2}\longrightarrow\mathbb{Z}_{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})\mapsto x_{1}+x_{2}$. Insgesamt
hat also der Kontext, der aus der vierten, sechsten und siebten Zeile
von $\mathbb{P}_{4}$ besteht, als Begriffsverband den zum Kongruenzenverband
von $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ isomorphen Verband. 


\subsubsection{Unterverbände}

Im vorhergehenden Abschnitt haben wir gesehen, dass für manche Anwendungen
nicht die volle Information, die im Kontext $\mathbb{B}$ steckt,
notwendig ist. Insbesondere genügt zur Berechnung des Kongruenzenverbandes
einer Algebra wegen der Bedingung (\ref{Kongruenz}) der Teil von
$\mathbb{B}$, der nur Implikationen der Form $\{ x\}\rightarrow\{ y\}$
als Merkmale benutzt, wobei $x,y\in M$. Implikationen dieser einfachen
Form heißen manchmal \emph{unär} \cite{key-15,key-6}. 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 $\mathbb{E}_{n}$ von $\mathbb{B}_{n}$,
der nur aus all den Spalten besteht, die zu unären Implikationen gehören,
gehen wir wieder so vor, wie bei $\mathbb{H}_{n}$ und bei $\mathbb{B}_{n}$,
indem wir eine induktive Konstruktion angeben: 

Es seien \vspace{10pt}\[\mathbb{E}_2= \begin{tabular}{|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}\hline

$\times$ & $\times$ \\ \hline

$$ & $\times$ \\ \hline

$\times$ & $$ \\ \hline 

$\times$ & $\times$ \\ \hline

\end{tabular}\; , \mathbb{F}_1 = \begin{tabular}{|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}\hline

$ \times$ \\ \hline

$ $\\ \hline

\end{tabular} \]

\begin{equation}\mathbb{E}_{n+1} \label{Rekursion E}= \begin{tabular}{c|c|c}

$\mathbb{E}_n$ & $\mathbb{F}_n$ & $\mbox{\LARGE$\times$}$ \\ \hline

$\mathbb{E}_n$ & ${\mbox{\LARGE$\times$}}$ & $\mathbb{F}_n{\uparrow}$ \end{tabular}\quad ( n \ge 2 )\text{ und } \mathbb{F}_{n+1}=\begin{tabular}{c} $\mathbb{F}_n^{1}$ \\ \hline

$\overset{}{\mathbb{F}_n^{0}}$

\end{tabular}\quad ( n \ge 1 )\end{equation}

\vspace{10pt} Dabei bezeichne $\mathbb{F}_{n}^{0}$ den Kontext $\mathbb{F}_{n}$
mit einer rechts angehängten Leerspalte, $\mathbb{F}_{n}^{1}$ den
Kontext $\mathbb{F}_{n}$ mit einer rechts angehängten Vollspalte,
und $\mathbb{F}_{n}\hspace{-1,5mm}\uparrow$ den Kontext, der aus
$\mathbb{F}_{n}$ entsteht, wenn man seine Zeilen in umgekehrter Reihenfolge
aufschreibt%
\footnote{Die Zeile Nummer $k$ von $\mathbb{F}_{n}\hspace{-1,5mm}\uparrow$
ist die Binärdarstellung von $k-1$ in umgekehrter Reihenfolge der
Bits. %
}. Dies ergibt also die Kontexte \vspace{10pt}\[\mathbb{F}_1^0= \begin{tabular}{|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}\hline 

$\times$ & $\phantom{\times}$ \\ \hline

$$ & $$ \\ \hline

\end{tabular}\; ,\mathbb{F}_1^1= \begin{tabular}{|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}\hline

$\times$ & $\times$ \\ \hline

$$ & $\times$ \\ \hline

\end{tabular}\; ,\mathbb{F}_2= \begin{tabular}{|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}\hline

$\times$ & $\times$ \\ \hline

$$ & $\times$ \\ \hline 

$\times$ & $$ \\ \hline

$$ & $$ \\ \hline

\end{tabular} \]

Als weitere Kontexte erhalten wir 
\vspace{20pt}\[\mathbb{E}_{3}= \begin{tabular}{c@{\hspace{0,1mm}}c@{\hspace{2mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}

&$$& $0$ & $0$ & $\bullet$ & $\bullet$ & $1$& $1$ \\ 

&$$ & $\bullet$ & $1$& $0$ & $1$ & $0$& $\bullet$ \\ 

&$$ & $1$ & $ \bullet$& $1$ & $0$ & $\bullet$& $0$ \\

\hline\hline

&$000 $ & $\times$ & $ \times$ & $\times$ & $\times$ & $\times$& $\times$  \\ \hline 

&$001$&$ $ &$\times$ & & $\times$ & $\times$& $\times$ \\ \hline 

&$010$ &$\times$ & $ $ & $\times$ & $$ & $\times$& $\times$ \\ \hline 

&$011$ & $\times$ & $\times$ & $$ & $$ & $\times$& $\times$ \\ \hline \hline

&$100$ & $\times$ & $\times$ & $\times $ & $\times$ & $$ & $$ \\ \hline 

&$101$ & $ $ &$\times$ & $\times$& $\times$ & $\times$ & $$ \\ \hline 

&$110$ & $\times$ & $ $ & $\times$ & $\times$ & $$ &$\times$ \\ \hline 

&$111 $ & $\times$ & $\times$ & $\times$ & $\times$ & $\times$ & $\times$ \\ \hline 

\end{tabular}\]\vspace{10pt} \[ \mathbb{F}_{3}= \begin{tabular}{c||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|}

$ $ & $ \bullet$ & $\bullet$ & $\bullet$ \\

$ $ & $0$ & $0$ & $ 1$ \\

$ $ & $0$ & $1$ & $ 0$ \\

$ $ & $1$ & $0$ &$ 0$ \\

\hline \hline

$0000$ & $ \times$ & $ \times$ & $\times$ \\ \hline 

$0001$ &$ $ & $\times$ &$\times$ \\ \hline 

$0010$ & $\times$ & $$ & $\times$ \\ \hline 

$0011$ & $$ & $$ &$\times$ \\ \hline \hline

$0100$ & $\times $ & $\times$ & $$ \\ \hline 

$0101$ & $ $& $\times$ & $$ \\ \hline 

$0110$ & $\times$ & $ $ &$$ \\ \hline 

$0111$ &$ $ & $ $ & $ $  \\ \hline 

\end{tabular} \; ,\mathbb{F}_{3}{\uparrow}=\begin{tabular}{c||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|@{\hspace{0,7mm}}c@{\hspace{0,7mm}}||@{\hspace{0,7mm}}c@{\hspace{0,7mm}}|} 

$ $ & $1$ & $1$ & $1$ \\

$ $ & $0$ & $0$ & $ \bullet$ \\

$ $ & $0$ & $\bullet$ & $ 0$ \\

$ $ & $\bullet$ & $0$ &$ 0$ \\

\hline \hline

$1000$ & $ $ & $ $ & $ $ \\ \hline 

$1001$ &$ \times$ & $$ &$$ \\ \hline 

$1010$ & $ $ & $\times$ & $ $ \\ \hline 

$1011$ & $\times$ & $\times$ &$ $ \\ \hline \hline

$1100$ & $ $ & $ $ & $\times$ \\ \hline 

$1101$ & $\times $& $$ & $\times$ \\ \hline 

$1110$ & $ $ & $ \times$ &$\times$ \\ \hline 

$1111$ &$ \times$ & $ \times$ & $ \times$  \\ \hline 

\end{tabular}\]  \vspace{10pt} \\
Dabei benutzen wir die folgende Codierung für unäre Implikationen:

Zunächst drücken wir die Implikation $\{ u\}\rightarrow\{ v\}$ mit
$u,v\in M=\{ n,\ldots,1\}$ und $u\neq v$ durch ihren $0,\bullet,1-$Vektor
$x\in\mathcal{X}_{n}$ aus: Für $u=i,v=j\neq i$ und $0\le k\le n-1$
ist dann $x=(x_{n-1},\ldots,x_{0})$ mit \[
x_{k}=\left\{ \begin{array}{cl}
1, & \textrm{falls }k=i-1\\
\bullet, & \textrm{falls }k=j-1\\
0, & \textrm{sonst }\end{array}\right.\]
Die Menge $\mathcal{Z}_{n}$ aller solcher Vektoren ist als Teilmenge
von $\mathcal{X}_{n}$ wieder lexikographisch geordnet. Die lexikographische
Position dieses Vektors innerhalb $\mathcal{Z}_{n}$ erhalten wir,
indem wir jedem $x=(x_{n-1},\ldots,x_{0})$ mit $x_{j}=\bullet$ und
$x_{i}=1$ die Zahl \[
s(x_{n-1},\ldots,x_{0})=1+\left\{ \begin{array}{lr}
j(j-1)+i, & \textrm{falls }i<j\\
i^{2}+j, & \textrm{falls }i>j\end{array}\right.\]
 zuordnen. Umgekehrt läßt sich aus der Position $s$ der Vektor zurückrechnen.
Dazu benutzen wir die folgende Eigenschaft: Für jedes $t\in\mathbb{N}$
gibt es genau ein $r\in\mathbb{N}$ mit $r^{2}\le t<(r+1)^{2}$; \[
\begin{array}{lll}
\textrm{falls }t-r^{2}<r,\textrm{ dann setze} & i(t):=r, & j(t):=t-r^{2},\\
\textrm{falls }t-r^{2}\ge r,\textrm{ dann setze} & j(t):=r+1, & i(t):=t-r^{2}-r.\end{array}\]
 Dann ist der Vektor $x(t)=(x_{n-1},\ldots,x_{0})$ mit \[
x_{k}=\left\{ \begin{array}{cl}
1, & \textrm{falls }k=i(t)\\
\bullet, & \textrm{falls }k=j(t)\\
0, & \textrm{sonst }\end{array}\right.\]
 die Codierung einer unären Implikation und die Abbildung $s\mapsto x(s-1)$
eine Bijektion zwischen $\{1,\ldots,n(n-1)\}\textrm{ und }\mathcal{Z}_{n}$
für jedes $n\in\mathbb{N}$. 

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

Für $n=2$ ist der Kontext $\mathbb{E}_{2}$ derjenige Teilkontext
von $\mathbb{B}_{2}$, der aus den Spalten mit unärer Implikation
besteht, und $\mathbb{F}_{2}$ sowie $\mathbb{F}_{2}\hspace{-1,5mm}\uparrow$
sind der jeweils passende Teilkontext von $\mathbb{E}_{3}$. 

Für $n\ge2$ erklärt sich der Aufbau von $\mathbb{E}_{n+1}$ durch
die folgende Betrachtung, wobei wieder $*$ der zu $M$ neu hinzukommende
Punkt ist: \\
 $\mathbb{E}_{n+1}$ ist Erweiterung von $\mathbb{E}_{n}$, denn für
alle $X\in\boldsymbol2^{n},\{ u\}\rightarrow\{ v\}\in\mathcal{Z}_{n}$
ist \[
X\vdash\{ u\}\rightarrow\{ v\}\textrm{ in }\mathbb{E}_{n}\iff X\vdash\{ u\}\rightarrow\{ v\}\textrm{ in }\mathbb{E}_{n+1}.\]
Für alle $u\in M$ und für alle Gegenstände $X\in\boldsymbol2^{n}$
ist $X\vdash\{*\}\rightarrow\{ u\}$ und $X+\{*\}\vdash\{ u\}\rightarrow\{*\}$,
was die beiden $\mbox{\LARGE$\times$}$ in der Definition von $\mathbb{E}_{n+1}$
erklärt. Weiter gilt \[
X\vdash\{ u\}\rightarrow\{ v\}\iff X+\{*\}\vdash\{ u\}\rightarrow\{ v\}.\]
 Es bleiben die Fälle \[
X\in\boldsymbol2^{n}\textrm{ und }\{ u\}\rightarrow\{*\}\textrm{ mit }u\in M\]
\[
X+\{*\}\textrm{ mit }X\in\boldsymbol2^{n}\textrm{ und }\{*\}\rightarrow\{ u\},u\in M\]
 zu untersuchen, von denen wir zeigen, dass $\mathbb{F}_{n}$ und
$\mathbb{F}_{n}\uparrow$ sie beschreiben. 

Die beiden Fälle sind zueinander komplementär, denn es gilt \[
X\vdash\{ u\}\rightarrow\{*\}\iff X+\{*\}\nvdash\{*\}\rightarrow\{ u\}\textrm{ f}\ddot{\textrm{u}}\textrm{r alle }X\in\boldsymbol2^{n},u\in M\]
also bleibt noch die Rekursion für $\mathbb{F}_{n+1}$ mit $n>1$
zu zeigen.

$\mathbb{F}_{n+1}$ ist ein Teilkontext von $\mathbb{E}_{n+2}$. Der
Übergang von $n+1$ nach $n+2$ werde wieder durch Adjunktion eines
weiteren Punktes $**$ realisiert. Die Merkmale von $\mathbb{F}_{n+1}$
sind die $\{ u\}\rightarrow\{**\}$ mit $u\in M+\{*\}$, sind also
von der Form $\{ u\}\rightarrow\{**\}$ mit $u\in M$ oder $\{*\}\rightarrow\{**\}$. 

Die Gegenstände des Kontexts $\mathbb{F}_{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\vdash\{*\}\rightarrow\{**\}$
und für die, die $*$ enthalten, gilt $X\nvdash\{*\}\rightarrow\{**\}$.
Dies rechtfertigt das Anhängen der Leerspalte bzw. Vollspalte an $\mathbb{F}_{n}$. 

Schließlich gilt für alle Gegenstände $X\in\boldsymbol2^{n},u\in M$\[
X\vdash\{ u\}\rightarrow\{*\}\iff X\vdash\{ u\}\rightarrow\{**\}\iff X+\{*\}\vdash\{ u\}\rightarrow\{**\}.\]


Damit ist gezeigt, dass $\mathbb{E}_{n+1}$ aus $\mathbb{E}_{n}$
induktiv so aufgebaut wird, wie in (\ref{Rekursion E}) beschrieben,
und wir definieren wieder\[
\mathbb{E}:=\lim_{n\ge0}\mathbb{E}_{n}\]
 

Wie früher machen wir uns die reguläre Struktur von $\mathbb{E}_{n}$
zunutze, um für eine gegebene Menge $\mathcal{F}\subseteq\mathcal{Z}_{n}$
unärer Implikationen den Teilkontext von $\mathbb{K}=(G,M,I)$ mit
$M=\{ n,\ldots,1\}$ und $n\ge2$ zu bestimmen, der diese Implikationenmenge
erfüllt. Dazu müssen wir für eine gegebene Implikation $\{ u\}\rightarrow\{ v\}\in\mathcal{F}$
mit $u,v\in M,u\neq v$, die Menge aller Gegenstände von $\mathbb{K}$,
deren Merkmalmenge die Implikation respektiert, berechnen. Die Implikation
$\{ u\}\rightarrow\{ v\}$ in $\mathcal{F}$ sei dargestellt durch
ihren $0,\bullet,1-$Vektor $(x_{n-1},\ldots,x_{0})$. Damit definiert
sich die zugehörige Spalte von $\mathbb{E}_{n}$, wobei wir wieder
die Abkürzung $x_{[k]}$ für $(x_{k-1},\ldots,x_{0})$ benutzen, folgendermaßen:
\\
Für $n=2$ gilt \[
(x_{[2]})^{\mathbb{E}_{2}}=\left\{ \begin{array}{cl}
1,0,1,1, & \textrm{falls }x_{1}=\bullet\\
1,1,0,1, & \textrm{falls }x_{1}=1\end{array}\right.\textrm{ }\]
\[
\begin{array}{c}
(x_{[2]})^{\mathbb{F}_{2}}=\left\{ \begin{array}{cl}
1,1,0,0, & \textrm{falls x}_{1}=1\\
1,0,1,0, & \textrm{falls x}_{1}=0\end{array}\right.\textrm{und }\end{array}(x_{[2]})^{\mathbb{F}_{2}\uparrow}=\left\{ \begin{array}{cl}
0,0,1,1, & \textrm{falls x}_{1}=\bullet\\
0,1,0,1, & \textrm{falls x}_{1}=0\end{array}\right.\]
und für $n>2$ ist \[
\begin{array}{lcl}
(x_{[n]})^{\mathbb{E}_{n}} & = & \left\{ \begin{array}{lr}
(x_{[n-1]})^{\mathbb{E}_{n-1}},(x_{[n-1]})^{\mathbb{E}_{n-1}}, & \textrm{falls }x_{n-1}=0\\
(x_{[n-1]})^{\mathbb{F}_{n-1}},1^{2^{n-1}}, & \textrm{falls }x_{n-1}=\bullet\\
1^{2^{n-1}},(x_{[n-1]})^{\mathbb{F}_{n-1}\uparrow}, & \,\,\,\textrm{falls }x_{n-1}=1\end{array}\right.\\
\\(x_{[n]})^{\mathbb{F}_{n}} & = & \left\{ \begin{array}{lr}
(x_{[n-1]})^{\mathbb{F}_{n-1}},(x_{[n-1]})^{\mathbb{F}_{n-1}}, & \textrm{falls }x_{n-1}=0\\
1^{2^{n-1}},0^{2^{n-1}}, & \,\,\,\,\,\textrm{falls }x_{n-1}=1\end{array}\right.\\
\\(x_{[n]})^{\mathbb{F}_{n}\uparrow} & = & \left\{ \begin{array}{lr}
(x_{[n-1]})^{\mathbb{F}_{n-1}\uparrow},(x_{[n-1]})^{\mathbb{F}_{n-1}\uparrow}, & \textrm{falls }x_{n-1}=0\\
0^{2^{n-1}},1^{2^{n-1}}, & \textrm{falls }x_{n-1}=1\end{array}\right.\end{array}\]
Das komponentenweise Produkt der Vektoren $(x_{[n]})^{\mathbb{E}_{n}}$
mit $x\in\mathcal{F}$ beschreibt die Zeilen des Kontextes $\mathbb{K}$,
die alle Implikationen von $\mathcal{F}$ respektieren. Sie definieren
einen Teilkontext von $\mathbb{K}$, dessen Begriffsverband der Unterverband
von $\underline{\mathfrak{B}}(\mathbb{K})$ ist, dessen Begriffsinhalte
den zusätzlichen Bedingungen $\mathcal{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 $\mathbb{P}_{n}$ diese Konstruktion durchführt
und dann für den Kontext $\mathbb{E}_{{{n \choose 2}}}$ die Menge
$\mathcal{F}$ nach (\ref{Kongruenz}) wählt. Man erhält einen Teilkontext
von $\mathbb{P}_{n}$, dessen Begriffsverband (bis auf Anti-Isomorphie)
der Kongruenzenverband der gegebenen Struktur ist. 
\end{document}
