2.1 Verbandstheorie

Definition 2.1 (Bereich)  

Ein Bereich enthält Objekte, die in irgendeiner Weise definiert sind, welche im folgenden nicht weiter wichtig ist. Diese Objekte seien mit $a, b, c, \ldots$ als Variablen bezeichnet und dürfen sowohl überstrichen als auch indiziert sein. Zusätzlich wird angenommen, daß ein Bereich mindestens ein Objekt enthält.

Die später behandelten Varianten von Verbänden werden mindestens ein Objekt enthalten, zuvor wird es die Beweise vereinfachen. Diese Definition ist für den augenblicklichen Bedarf etwas zu weit konzipiert, im weiteren Verlauf werden diese Erweiterungen jedoch benötigt.

Zunächst aber zur Theorie der Verbände, die hier nur soweit entwickelt werden soll, wie es zur Behandlung der Venn-Diagramme nötig ist. Dazu wurden im wesentlichen [1] und [2] verwendet.

2.1.1 Verband

Definition 2.2 (Abgeschlossene Verknüpfung)  

Eine beliebigstellige Verknüpfung  $\circ$  heißt abgeschlossen über dem Bereich $A$, wenn für alle $a, b, c, \ldots$, auch $\circ ( a, b, c, \ldots )$ in $A$ ist.

Definition 2.3 (Algebraische Struktur)  

Ein Bereich $A$ mit einer oder mehreren abgeschlossenenen Verknüpfungen heißt algebraische Struktur: $( A, \circ_{1}, \circ_{2}, \ldots )$. $A$ heißt Trägerbereich dieser Struktur.

Wenn im folgenden also auf Objekte $a, b, c, \ldots , x, y, z$ bezug genommen wird, so sind immer Objekte aus dem Bereich gemeint.

Definition 2.4 (Verband)  

Die algebraische Struktur $( L, \sqcup, \sqcap )$ heißt Verband, wenn folgende Bedingungen für alle Variablen $a, b, c$ aus dem Bereich $L$ erfüllt sind:

(V1a)	$a \sqcup ( b \sqcup c ) = ( a \sqcup b ) \sqcup c$		(V1b)	$a \sqcap ( b \sqcap c ) = ( a \sqcap b ) \sqcap c$
(V2a)	$a \sqcup b = b \sqcup a$		(V2b)	$a \sqcap b = b \sqcap a$
(V3a)	$a \sqcap ( a \sqcup b ) = a$		(V3b)	$a \sqcup ( a \sqcap b ) = a$

Bemerkung 2.1 (Substitutionsregel)  

Ein Objekt aus dem Bereich wird auch Term genannt, ebenso alle Objekte, die sich durch Verknüpfung mittels $\sqcap$ oder $\sqcup$ erzeugen lassen. Terme werden mittels des Gleichheitszeichens = in Beziehung zueinander gesetzt. Für dieses Zeichen gilt unter anderem die Substitutionsregel, die besagt, daß Terme, die in der Gleichheitsbeziehung zueinander stehen, wechselseitig in und füreinander eingesetzt (substituiert) werden dürfen. Die Gleichheit ist eine Äquivalenzrelation, also symmetrisch, transitiv und auch reflexiv.

Bemerkung 2.2 (Dualitätsprinzip)  

In den Verbandsaxiomen treten die Operationen $\sqcup$ und $\sqcap$ gleichberechtigt auf. Daraus läßt sich das fundamentale Dualitätsprinzip formulieren. Dazu muß zunächst geklärt werden, was ein verbandstheoretischer Ausdruck ist. Ein solcher Ausdruck ist ein sprachliches Gebilde, in dem neben einigen logischen Teilen und Variablen für die Objekte eines Verbandes nur die Symbole $\sqcup$ und $\sqcap$ auftreten. Einem solchen Ausdruck $X$ ist eindeutig ein sogenannter dualer Ausdruck $D(X)$ zugeordnet, der aus $X$ dadurch entsteht, daß in $X$ überall $\sqcup$ durch $\sqcap$ ersetzt wird und umgekehrt. Natürlich ist dann $D(D(X)) = X$.

Ein in jedem Verband gültiger verbandstheoretischer Ausdruck, insbesondere also auch jedes Axiom, heiße ein Satz der Verbandstheorie.

Satz 2.1 (Dualitätsprinzip für Verbände)  

Der duale Ausdruck eines Satzes der Verbandstheorie ist wieder ein Satz der Verbandstheorie.

Beweis: Für jedes Axiom ist auch dessen dualer Ausdruck ein Axiom, daher kann für jeden aus den Axiomen erzeugten Ausdruck auch dessen dualer Ausdruck aus den Axiomen erzeugt werden.

Satz 2.2 (Idempotenz)  

Sei $( L, \sqcup, \sqcap )$ ein Verband. Dann gilt für alle $a$:

(a) $a \sqcap a = a$

(b) $a \sqcup a = a$

Beweis: (a) Es ist $a \sqcap a \stackrel{\rm (V2b)}{=} a \sqcap a$. Ersetzen des rechten $a$ auf der rechten Seite der Gleichung nach (V3b) durch $( a \sqcup ( a \sqcap b ) )$ ergibt $a \sqcap a = a \sqcap ( a \sqcup ( a \sqcap b ) )$. Anwendung von (V3a) ergibt $a \sqcap a = a$.

Der Beweis für (b) ergibt sich unmittelbar durch Anwendung des Dualitätsprinzips.

Satz 2.3  

In jedem Verband $( L, \sqcup, \sqcap )$ gilt für alle $a$ und $b$:

$a \sqcup b = b \Leftrightarrow a \sqcap b = a$

Beweis: ,,$\Rightarrow$`` Es ist $a \sqcap b \stackrel{\rm (Vor.)}{=} a \sqcap ( a \sqcup b ) \stackrel{\rm (V3a)}{=} a$.

,,$\Leftarrow$`` Es ist $a \sqcup b \stackrel{\rm (Vor.)}{=} ( a \sqcap b ) \sqcup b \stackrel{\rm (V2a)... ...p b ) \stackrel{\rm (V2b)}{=} b \sqcup ( b \sqcap a ) \stackrel{\rm (V3b)}{=} b$.

Satz 2.4  

In jedem Verband $( L, \sqcup, \sqcap )$ gilt für alle $a, b, c$:

(a) $a = b \Rightarrow a \sqcap c = b \sqcap c$

(b) $a = b \Rightarrow a \sqcup c = b \sqcup c$

Beweis: (a) Es ist $a \sqcap c \stackrel{\rm (Bem.\ \ref{BEM0})}{=} a \sqcap c$. Mit $a = b$ gilt dann: $a \sqcap c = b \sqcap c$.

(b) Der Beweis verläuft analog.

Definition 2.5 (Null/Eins-Objekt)  

Es gelte:

Ein Objekt $y$ des Verbandes $( L, \sqcup, \sqcap )$ mit $y \sqcup x = x$ und $y \sqcap x = y$ für alle $x$ heißt Nullobjekt.

Ein Objekt $y$ des Verbandes $( L, \sqcup, \sqcap )$ mit $y \sqcap x = x$ und $y \sqcup x = y$ für alle $x$ heißt Einsobjekt.

Satz 2.5  

In jedem Verband gibt es höchstens ein Nullobjekt und höchstens ein Einsobjekt.

Beweis: Sind $x$ und $y$ zwei Nullobjekte, so gilt $x \sqcap y = x$ ( da $x$ Nullobjekt ) und $y \sqcap x = y$ ( da $y$ Nullobjekt ), also ist $x \stackrel{\rm (Def~ \ref{DEF5})}{=} x \sqcap y \stackrel{\rm (V2b)}{=} y \sqcap x \stackrel{\rm (Def~ \ref{DEF5})}{=} y$. Der Beweis für das Einsobjekt verläuft analog mit den dualen Ausdrücken.

Bemerkung 2.3  

Da es nur höchstens ein Null- und höchstens ein Einsobjekt in einem Verband geben kann, seinen diese (falls vorhanden) mit 0 bzw. 1 bezeichnet. Die Bedingungen für Nullobjekt und Einsobjekt sind dual zueinander definiert. Daher ist (falls beide vorhanden) die 0 das Dual der 1 und umgekehrt. Für einen solchen Verband wird die Dualisierungsregel dementsprechend erweitert.

2.1.2 Halbordnungsstruktur

In der Verbandstheorie spielen neben den Verbänden die Halbordnungsstrukturen eine große Rolle.

Definition 2.6 (Halbordnungsstruktur)  

Gegeben sei ein Bereich $H$ und eine Beziehung $R$ mit $x \sqsubseteq y$ genau dann, wenn die Beziehung $R$ zwischen $x$ und $y$ besteht. (,,$x$ kleiner-gleich $y$``).

$R$ heißt Halbordnung auf $H$ genau dann, wenn gilt:

(H1)	$\forall_{x}: x \sqsubseteq x$
(H2)	$\forall_{x,y}: x \sqsubseteq y \;\wedge\; y \sqsubseteq x \Rightarrow x = y$
(H3)	$\forall_{x,y,z}: x \sqsubseteq y \;\wedge\; y \sqsubseteq z \Rightarrow x \sqsubseteq z$

$( H, \sqsubseteq )$ heißt Halbordnungsstruktur mit $H$ als Trägerbereich. Es handelt sich lediglich um eine Halbordnung, da $\forall_{x,y}: x \sqsubseteq y \;\vee\; y \sqsubseteq x$ nicht garantiert ist.

Bemerkung 2.4  

In Halbordnungsstrukturen gilt wie in den Verbänden ein Dualitätsprinzip. Aus einem gültigen ordnungstheoretischen Ausdruck $X$ erhält man den dualen Ausdruck $D(X)$, indem man überall $a \sqsubseteq b$ durch $b \sqsubseteq a$ ersetzt, wobei $a$ und $b$ beliebige Terme sind.

Satz 2.6 (Dualitätsprinzip für Halbordnungsstrukturen)  

Der duale Ausdruck eines Satzes der Theorie der Halbordnungsstrukturen ist ebenfalls ein Satz dieser Theorie.

Beweis: Jedes Axiom ist selbstdual (bis auf Umbenennung der Variablen), daher kann man zu jedem aus den Axiomen hergeleiteten Satz der Theorie der Halbordnungsstrukturen der duale Ausdruck ebenfalls abgeleitet werden.

Definition 2.7 (Minimale/Maximale Objekte)  

Sei $( H, \sqsubseteq )$ eine Halbordnungsstruktur.

Ein Objekt $u$ heißt genau dann minimal, wenn es kleiner-gleich allen mit ihm vergleichbaren ist, also wenn für alle $x$ aus $H$ aus der Gleichung $x \sqsubseteq u$ die Gleichnung $x = u$ folgt.

Ein Objekt $v$ heißt genau dann maximal, wenn jedes mit ihm vergleichbare Objekt kleiner-gleich $v$ ist, also wenn für alle $x$ aus $H$ aus der Gleichnung $v \sqsubseteq x$ die Gleichnung $x = v$ folgt.

Definition 2.8 (Kleinstes/größtes Objekt)  

Sei $( H, \sqsubseteq )$ eine Halbordungsstruktur.

Ein Objekt $y$ heißt genau dann kleinstes Objekt von $( H, \sqsubseteq )$, wenn für alle $x$ gilt: $y \sqsubseteq x$.

Ein Objekt $y$ heißt genau dann größtes Objekt von $( H, \sqsubseteq )$, wenn für alle $x$ gilt: $x \sqsubseteq y$.

Satz 2.7  

Es gibt in einer Halbordnungsstruktur höchstens ein kleinstes Objekt und höchstens ein größtes Objekt.

Beweis: Seien $y$ und $z$ kleinste Objekte. Dann gilt $y \sqsubseteq x$ für alle $x$, insbesondere gilt also auch $y \sqsubseteq z$. Mit der gleichen Argumentation gilt $z \sqsubseteq y$, nach (H2) also $y = z$. Der Beweis für größte Objekte verläuft analog mit den dualen Ausdrücken.

Bemerkung 2.5  

Ein kleinstes Objekt wird (falls vorhanden) mit $0_{\sqsubseteq}$ bezeichnet. Ein größtes Objekt, wird (falls vorhanden) mit $1_{\sqsubseteq}$ bezeichnet. Größtes und kleinstes Objekt sind dual zueinander definiert, daher ist (falls beide vorhanden sind) $0_{\sqsubseteq}$ das Dual von $1_{\sqsubseteq}$ und umgekehrt. Die Dualisierungsregel für Ordnungstrukturen ist dementsprechend zu erweitern, falls die betrachtete Struktur größte und kleinste Objekte enthält.

Definition 2.9 (obere/untere Schranke)  

Sei $( H, \sqsubseteq )$ eine Halbordnungsstruktur, $T \subseteq H$.

Ein $x$ heißt obere Schranke von $T$ genau dann, wenn für jedes Objekt $y$ aus $T$ gilt: $y \sqsubseteq x$.

Ein $x$ heißt untere Schranke von $T$ genau dann, wenn für jedes Objekt $y$ aus $T$ gilt: $x \sqsubseteq y$.

Definition 2.10 (Supremum/Infimum)  

Sei $( H, \sqsubseteq )$ eine Halbordnungsstruktur, $T \subseteq H$.

Ein $x$ heißt Supremum von $T$ genau dann, wenn $x$ die kleinste obere Schranke von $T$ ist, d.h. wenn für alle oberen Schranken $y$ von $T$ gilt: $x \sqsubseteq y$. Abgekürzt schreibt man $sup(T)$.

Ein $x$ heißt Infimum von $T$ genau dann, wenn $x$ die größte untere Schranke von $T$ ist, d.h. wenn für alle unteren Schranken $y$ von $T$ gilt: $y \sqsubseteq x$. Abgekürzt schreibt man $inf(T)$.

Satz 2.8  

Sei $T \subseteq H$. Dann gibt es höchstens ein Supremum (Infimum) von $T$.

Beweis: Seien $e$ und $e'$ zwei Suprema (Infima) von $T$. Dann sind beide insbesondere auch obere (untere) Schranken von $T$(Def 2.10). Dann gilt $e \sqsubseteq e'$ und $e'\sqsubseteq e$, d.h. nach (H2): $e = e'$.

Bemerkung 2.6  

Wir wollen uns im folgenden auf Halbordnungsstrukturen beschränken, in denen Suprema und Infima von Objekten eines Bereiches immer existieren und mit zu dem Bereich gehören. $sup(T)$ und $inf(T)$ sind zueinander dual definiert. Die Dualisierungsregel für Halbordnungsstrukturen ist dementsprechend zu erweitern.

Satz 2.9  

Es gilt:

(a) $inf(a,a) = a$

(b) $sup(a,a) = a$

Beweis: (a) Nach Definition 2.9 ist $inf(a,a) \sqsubseteq a$. Andererseits gilt aber $a \sqsubseteq a$, d.h. $a$ ist untere Schranke von $a$.

Da $inf(a,a)$ nach Definition 2.10 die größte untere Schranke von $a$ und $a$ ist, gilt $a \sqsubseteq inf(a,a)$. Nach (H2) gilt damit $inf(a,a) = a$.

(b) Der Beweis ist dual zu dem von (a).

Die Beweise lassen sich einfach auf mehr als zwei Komponenten erweitern.

Satz 2.10  

Es gilt:

(a) $x \sqsubseteq inf(T) \Leftrightarrow x \sqsubseteq y$ für alle $y$ aus $T$.

(b) $sup(T) \sqsubseteq x \Leftrightarrow y \sqsubseteq x$ für alle $y$ aus $T$.

Beweis: (a) ,,$\Rightarrow$`` Nach Definition 2.9  ist das Infimum eine untere Schranke, daß heißt es gilt $inf(T) \sqsubseteq y$ für alle $y$ aus $T$. Nach Voraussetzung gilt $x \sqsubseteq inf(T)$, daher gilt nach Axiom (H3): $x \sqsubseteq y$ für alle $y$ aus $T$.

,,$\Leftarrow$`` Umgekehrt folgt aus $x \sqsubseteq y$ für alle $y$ aus $T$, daß $x$ untere Schranke von $T$ ist, nach Definition 2.10 gilt dann aber $x \sqsubseteq inf(T)$.

(b) Der Beweis ist dual zu (a).

Satz 2.11  

Es gilt:

(a) $a \sqsubseteq b \Rightarrow inf(a,b) = a$

(b) $a \sqsubseteq b \Rightarrow sup(a,b) = b$

Beweis: (a) Nach Voraussetzung ist $a \sqsubseteq b$. Außerdem gilt $a \sqsubseteq a$ (H1), daher gilt nach Satz 2.10 $a \sqsubseteq inf(a,b)$. Nach Definition 2.9 gilt auch $inf(a,b) \sqsubseteq a$, daher gilt nach (H2) $inf(a,b) = a$.

(b) Der Beweis ist dual zu (a).

Satz 2.12  

Es gilt: $a \sqsubseteq b, inf(a,b) \sqsubseteq 0 ~\Rightarrow~ a \sqsubseteq 0$.

Beweis: Nach Satz 2.11 folgt aus $a \sqsubseteq b$: $inf(a,b) = a$, damit auch (Beweis von Satz 2.11)
$a \sqsubseteq inf(a,b)$. Da $inf(a,b) \sqsubseteq 0$ folgt daher nach (H3) $a \sqsubseteq 0$.

2.1.3 Verband und Halbordnungsstruktur

Nun werden Verband- und Halbordnungsstruktur zueinander in Beziehung gesetzt.

Satz 2.13  

Sei $( L, \sqcup, \sqcap )$ ein Verband. Dann wird durch $a \sqsubseteq b :\Leftrightarrow a \sqcap b = a$ auf $L$ eine Halbordnungsstruktur $( L, \sqsubseteq )$ definiert.

Beweis: (1) Aus Satz 2.2 ( $a \sqcap a = a$) folgt nach der Definition aus Satz 2.13: $a \sqsubseteq a$.

(2) Aus $x \sqsubseteq y$ und $y \sqsubseteq x$ folgt zunächst nach obiger Definition $x \sqcap y = x$ und $y \sqcap x = y$, daher gilt: $x \stackrel{\rm (Vor.)}{=} x \sqcap y \stackrel{\rm (V2b)}{=} y \sqcap x \stackrel{\rm (Vor.)}{=} y$.

(3) Aus $x \sqsubseteq y$ und $y \sqsubseteq z$ folgt zunächst nach Definition $x \sqcap y = x$ und $y \sqcap z = y$. Dann ist durch Einsetzen $x \sqcap z \stackrel{\rm (Vor.)}{=} ( x \sqcap y ) \sqcap z \stackrel{\rm (V1b)... ...p ( y \sqcap z ) \stackrel{\rm (Vor.)}{=} x \sqcap y \stackrel{\rm (Vor.)}{=} x$, also $x \sqsubseteq z$.

Satz 2.14  

Seien $( L, \sqcup, \sqcap )$ ein Verband und $( L, \sqsubseteq )$ eine wie vor definierte Halbordnungsstruktur. Dann gilt für alle $a$ und $b$:

(a) $a \sqcup b = sup(a,b)$

(b) $a \sqcap b = inf(a,b)$

Falls Verband wie Halbordnungsstruktur über 0/1 bzw. 0 $_{\sqsubseteq}$/1 $_{\sqsubseteq}$ verfügen, gilt:

(c) $0 = 0_{\sqsubseteq}$

(d) $1 = 1_{\sqsubseteq}$

Beweis: (a) Nach (V3a) gilt $a \sqcap ( a \sqcup b ) = a$ und $b \sqcap ( a \sqcup b ) = b$, was nach obiger Definition mit $a \sqsubseteq a \sqcup b$ sowie $b \sqsubseteq a \sqcup b$ gleichbedeutend ist; somit ist $a \sqcup b$ obere Schranke von $a$ und $b$.

$a \sqcup b$ ist aber auch die kleinste obere Schranke. Ist nämlich $a \sqsubseteq c$ und $b \sqsubseteq c$, so ist $a \sqcap c = a$ und $b \sqcap c = b$, sowie nach Satz 2.3 $a \sqcup c = c$ und $b \sqcup c = c$. Daher ist $c \sqcup ( a \sqcup b ) \stackrel{\rm (V1a)}{=} ( a \sqcup c ) \sqcup b \stackrel{\rm (Vor.)}{=} \linebreak c \sqcup b \stackrel{\rm (Vor.)}{=} c$ und daher (Satz 2.3) ist wiederum nach obiger Definition $c \sqcap ( a \sqcup b ) = a \sqcup b$, was gleichwertig mit $a \sqcup b \sqsubseteq c$ ist.

(b) Der Beweis ist dual zu (a).

(c) Nach Definition 2.5 gilt im Verband für das Nullobjekt 0 für alle $x$: $0 \sqcap x = 0$. Nach Satz 2.13 gilt daher $0 \sqsubseteq x$ für alle $x$, daher ist die 0 ein kleinstes Objekt im Sinne von Definition 2.8. Daher gilt: $0 = 0_{\sqsubseteq}$

(d) Der Beweis ist dual zu (c).

Sei nun umgekehrt eine Halbordnungsstruktur $( L, \sqsubseteq )$ vorgegeben. Es sollen nun zwei abgeschlossene Verknüpfungen $\sqcup$ und $\sqcap$ definiert werden, so daß $( L, \sqcup, \sqcap )$ einen Verband darstellt.

Satz 2.15  

Sei $( L, \sqsubseteq )$ eine Halbordnungsstruktur. Mit $a \sqcup b := sup(a,b)$ und $a \sqcap b := inf(a,b)$ ist $( L, \sqcup, \sqcap )$ eine Verbandsstruktur, und es gilt $a \sqsubseteq b \Rightarrow a \sqcap b = a$.

Beweis: (1) Nach Definition 2.10 sind Suprema bzw. Infima bereits kommutativ definiert, nach Übersetzung sind daher (V2a) und (V2b) bewiesen.

(2) Es ist nach Definition 2.10 $inf(a,inf(x,y)) \sqsubseteq a$ und $inf(a,inf(x,y)) \sqsubseteq inf(x,y)$. Weiterhin ist nach Definition 2.10 $inf(x,y) \sqsubseteq x$ und $inf(x,y) \sqsubseteq y$. Daher gilt nach (H3) $inf(a,inf(x,y)) \sqsubseteq x$ und $inf(a,inf(x,y)) \sqsubseteq y$. Daraus folgt nach Definition 2.10, daß $inf(a,inf(x,y)) \sqsubseteq inf(a,x)$ und $inf(a,inf(x,y)) \sqsubseteq inf(a,y)$ gilt. Das ergibt wiederum nach Definition 2.10, daß $inf(a,inf(x,y)) \sqsubseteq inf(inf(a,x),inf(a,y))$ gilt.

Umgekehrt gilt nach Def. 2.10 $inf(inf(a,x),inf(a,y)) \sqsubseteq inf(a,x)$ und $inf(inf(a,x),inf(a,y)) \sqsubseteq inf(a,y)$. Ebenso ist nach Def. 2.10 $inf(a,x) \sqsubseteq a$; $inf(a,x) \sqsubseteq x$; $inf(a,y) \sqsubseteq a$ und $inf(a,y) \sqsubseteq y$.

Daher gilt $inf(inf(a,x),inf(a,y)) \sqsubseteq a$; $inf(inf(a,x),inf(a,y)) \sqsubseteq x$; $inf(inf(a,x),inf(a,y)) \sqsubseteq y$ nach (H3). Daher ist nach Definition 2.10 $inf(inf(a,x),inf(a,y)) \sqsubseteq inf(x,y)$ und damit ist nach Definition 2.10 auch $inf(inf(a,x),inf(a,y)) \sqsubseteq inf(a,inf(x,y))$.

Daher ist $inf(inf(a,x),inf(a,y)) = inf(a,inf(x,y))$ nach (H2).

Das kann man ebenso für $inf(inf(a,x),y)$ durchführen, woraus sich ergibt: $inf(a,inf(x,y)) = inf(inf(a,x),y)$. Das bedeutet, daß nach Übersetzung $a \sqcap ( b \sqcap c ) = ( a \sqcap b ) \sqcap c$ gilt, womit (V1b) bewiesen ist. Der Beweis von (V1a) verläuft dual.

(3) Es gilt nach Definition 2.10 $a \sqsubseteq sup(a,b)$, daher gilt nach Satz 2.11 $inf(a,sup(a,b)) = a$. Ebenso gilt nach Definition 2.10 $inf(a,b) \sqsubseteq a$, daher gilt nach Satz 2.11 $sup(inf(a,b),a) = a$. Damit sind nach Übersetzung (V3a) und (V3b) bewiesen.

(4) Es sei $a \sqsubseteq b$. Nach Satz 2.11 gilt $inf(a,b) = a$. Nach Übersetzung gemäß Satz 2.14 gilt dann $a \sqcap b = a$.

Für Null- und Einsobjekt gilt die Argumentation wie im Beweis von Satz 2.14.

Damit ist eine eindeutige Beziehung zwischen den Verbänden und den hier betrachteten Halbordnungsstrukturen hergestellt. Es ist üblich, Verbände mit den Halbordnungsstrukturen zu identifizieren, bei denen zu zwei Objekten aus dem Trägerbereich der Halbordnungsstruktur auch deren Supremum und Infimum zu dem Trägerbereich gehört. Alle Sätze, die für $\sqcap$ und $\sqcup$ bewiesen wurden, gelten daher auch für $inf$ und $sup$ und umgekehrt. Die Dualisierungsprinzipien beider Strukturen können ebenfalls ineinander überführt bzw. ergänzt werden.

Satz 2.16  

Es gilt für alle $x, y$: $x = y \Leftrightarrow x \sqsubseteq y \;\wedge\; y \sqsubseteq x$

Beweis: $x \sqsubseteq y \,\wedge\, y \sqsubseteq x \Rightarrow x = y$ ist Axiom (H2). Es ist $x \stackrel{\rm (Satz\ \ref{SATZ1})}{=} x \sqcap x \stackrel{\rm (Vor.)}{=} x \sqcap y$. Dann gilt nach Satz 2.13 $x \sqsubseteq y$. Umgekehrt ist $y \stackrel{\rm (Satz\ \ref{SATZ1})}{=} y \sqcap y \stackrel{\rm (Vor.)}{=} y \sqcap x$. Dann gilt nach Satz 2.13 $y \sqsubseteq x$.

2.1.4 Boolesche Verbände

Die Booleschen Verbände sind das eigentliche Ziel dieses Kapitels, zunächst erfolgen aber noch einige weitere einleitende Definitionen, Sätze und Beweise.

Definition 2.11 (Distributiver Verband)  

Ein Verband $( L, \sqcup, \sqcap )$ heißt genau dann distributiv, wenn für alle $x, y, z$ gilt:

(V4a)

$x \sqcap ( y \sqcup z ) = ( x \sqcap y ) \sqcup ( x \sqcap z )$

(V4b)

$x \sqcup ( y \sqcap z ) = ( x \sqcup y ) \sqcap ( x \sqcup z )$

Man gibt zwei Distributivgesetze an, um die Gleichwertigkeit von $\sqcap$ und $\sqcup$ und damit die Dualität zu erhalten.

Satz 2.17 (Kürzungsregel)  

Ist $( L, \sqcup, \sqcap )$ ein distributiver Verband, dann gilt für alle $x, y, z$:

$x \sqcup y = x \sqcup z, ~x \sqcap y = x \sqcap z ~\Rightarrow ~y = z$.

Beweis: Es ist: $y \stackrel{\rm (V3b)}{=} y \sqcup ( x \sqcap y ) \stackrel{\rm (Vor.)}{=} y \s... ... y ) \stackrel{\rm (Vor.)}{=} z \sqcup ( x \sqcap z ) \stackrel{\rm (V3b)}{=} z$.

Definition 2.12 (Komplementärer Verband)  

Ein Verband $( L, \sqcup, \sqcap )$ mit Nullobjekt 0 und Einsobjekt 1 heißt genau dann komplementär, wenn es zu jedem $a$ mindestens ein $x$ mit $a \sqcup x = 1$ und $a \sqcap x = 0$ gibt. $x$ heißt ein Komplement von $a$.

Satz 2.18  

In einem distributiven Verband gibt es zu jedem Objekt höchstens ein Komplement.

Beweis: Sind $x$ und $y$ Komplemente von $a$, so gilt gemäß Definition 2.12: $a \sqcup x = 1 = a \sqcup y$, sowie $a \sqcap x = 0 = a \sqcap y$.

Dann ist $x \stackrel{\rm (V3b)}{=} x \sqcup ( a \sqcap x ) \stackrel{\rm (Vor.)}{=} x \s... ...up y \stackrel{\rm (Vor.)}{=} ( a \sqcap y ) \sqcup y \stackrel{\rm (V3b)}{=} y$.

Satz 2.19 (Doppelte Negation)  

In einem distributiven Verband ist das Komplement des Komplementes eines Objektes wieder das Objekt.

Beweis: Sei $x$ das Komplement von $y$. Dann gilt nach Definition 2.12: $y \sqcap x = 0$ und $y \sqcup x = 1$. Sei ebenso $z$ das Komplement von $x$. Dann gilt gemäß Definition 2.12: $x \sqcap z = 0$ und $x \sqcup z = 1$. Insbesondere gilt also auch $x \sqcap y \stackrel{\rm (V2b)}{=} y \sqcap x \stackrel{\rm (s.o.)}{=} 0 \stackrel{\rm (s.o.)}{=} x \sqcap z$ und $x \sqcup y \stackrel{\rm (V2a)}{=} y \sqcup x \stackrel{\rm (s.o.)}{=} 1 \stackrel{\rm (s.o.)}{=} x \sqcup z$. Da der Verband distributiv ist, darf Satz 2.17 angewendet werden, so daß sich $y = z$ ergibt.

Definition 2.13 (Boolescher Verband)  

Ein Verband mit 0 und 1, der sowohl komplementär als auch distributiv ist, heißt Boolescher Verband oder auch Boolesche Algebra.

Bemerkung 2.7 (Boolescher Verband)  

Für einen Booleschen Verband gelten also insgesamt die folgenden Axiome:

Abgeschlossenheit bezüglich der Operationen $\sqcap$ und $\sqcup$.

(V1a)	$a \sqcup ( b \sqcup c ) = ( a \sqcup b ) \sqcup c$		(V1b)	$a \sqcap ( b \sqcap c ) = ( a \sqcap b ) \sqcap c$
(V2a)	$a \sqcup b = b \sqcup a$		(V2b)	$a \sqcap b = b \sqcap a$
(V3a)	$a \sqcap ( a \sqcup b ) = a$		(V3b)	$a \sqcup ( a \sqcap b ) = a$
(V4a)	$x \sqcap ( y \sqcup z ) = ( x \sqcap y ) \sqcup ( x \sqcap z )$		(V4b)	$x \sqcup ( y \sqcap z ) = ( x \sqcup y ) \sqcap ( x \sqcup z )$

Es gibt ein kleinstes Objekt 0 und es gilt für alle $a$: $a \sqcup 0 = a$ und $a \sqcap 0 = 0$.

Es gibt ein größtes Objekt 1 und es gilt für alle $a$: $a \sqcap 1 = a$ und $a \sqcup 1 = 1$.

Für jedes Objekt $a$ gibt es ein eindeutiges Komplement, das mit $\overline{a}$ bezeichnet wird.

Es gilt $a \sqcup \overline{a} = 1$ und $a \sqcap \overline{a} = 0$.

Bemerkung 2.8  

Die Axiome des Booleschen Verbandes sind nicht unabhängig, (V1a), (V1b), (V3a) und (V3b) sind z.B. aus den anderen Axiomen herleitbar, die eindeutige Negation ergibt sich aus (V4a) und (V4b).

Zur besseren Unterscheidung wird der Boolesche Gleichungskalkül mit dem Kürzel BV$^{=}$ bezeichnet.

Mit dem Wort Variable wird ein beliebiges unbestimmtes Objekt aus dem Trägerbereich bezeichnet. Eindeutig bestimmte Objekte, wie z.B. 0 und 1 werden als Konstanten bezeichnet.

Ausdrücke wie z.B. $a = b$ in Booleschen Verbänden oder $a \sqsubseteq b$ in Halbordnungsstrukturen werden auch Formeln genannt.

Bisher wurde nur bewiesen, daß die Axiomensysteme V1-V3 (der Gleichungskalkül) und H1-H3 (der Halbordnungskalkül) äquivalent sind. Was ist mit BV$^{=}$ ? Zumindest weiß man, daß man (nach Satz 2.15) in Halbordnungsstrukturen $\sqcap$ und $\sqcup$ statt inf bzw. sup verwenden kann.

Satz 2.20  

In $( L, \sqsubseteq )$ gilt:

(a) $x \sqcup ( y \sqcap z ) \sqsubseteq ( x \sqcup y ) \sqcap ( x \sqcup z )$

(b) $( x \sqcap y ) \sqcup ( x \sqcap z ) \sqsubseteq x \sqcap ( y \sqcup z )$

Beweis: (a) Es ist $x \sqsubseteq x \sqcup y$ und $x \sqsubseteq x \sqcup z$. Daher ist nach Definition 2.10 $x \sqsubseteq ( x \sqcup y ) \sqcap ( x \sqcup z )$. Es ist $y \sqcap z \sqsubseteq y$ und $y \sqsubseteq x \sqcup y$. Daher gilt (H3) $y \sqcap z \sqsubseteq x \sqcup y$. Außerdem ist $y \sqcap z \sqsubseteq z$ und $z \sqsubseteq x \sqcup z$, daher nach (H3) $y \sqcap z \sqsubseteq x \sqcup z$. Daher gilt nach Definition 2.10 $x \sqcup ( y \sqcap z ) \sqsubseteq ( x \sqcup y ) \sqcap ( x \sqcup z )$.

(b) Der Beweis ist dual zu (a).

Es fehlen die anderen Richtungen der Distributivgesetze. Diese fügen wir als Axiome H4 hinzu:

(H4)	$\forall_{x,y,z}: ( x \sqcup y ) \sqcap ( x \sqcup z ) \sqsubseteq x \sqcup ( y \sqcap z )$
	$\forall_{x,y,z}: x \sqcap ( y \sqcup z ) \sqsubseteq ( x \sqcap y ) \sqcup ( x \sqcap z )$

(H5) sei die Definition der größten/kleinsten Objekte gemäß Definition 2.8. (H6) sei die Definition des Komplements gemäß Definition 2.12 lediglich nun mit Hilfe von Satz 2.14 auf die Halbordnungsstruktur bezogen.

Aus Satz 2.20 und (H4) folgt mittels (H2) sofort (V4). Umgekehrt folgt aus (V4) mittels Satz 2.16 sofort (H4). Dieser Boolesche Halbordnungskalkül ( H1 - H6 ) wird mit BV $^{\sqsubseteq}$ bezeichnet.

Satz 2.21  

Sei $( L, \sqcup, \sqcap )$ ein Boolescher Verband. Dann gilt: $\overline{1} = 0$ und $\overline{0} = 1$.

Beweis: Für das Komplement $\overline{1}$ von $1$ muß gelten: $1 \sqcap \overline{1} = 0$ und $1 \sqcup \overline{1} = 1$. $\overline{1} = 0$ erfüllt diese Bedingungen, denn es ist $1 \sqcap 0 = 0$ und $1 \sqcup 0 = 1$. Für das Komplement $\overline{0}$ von $0$ muß gelten: $0 \sqcap \overline{0} = 0$ und $0 \sqcup \overline{0} = 1$. $\overline{0} = 1$ erfüllt diese Bedingungen, denn es ist $0 \sqcap 1 = 0$ und $0 \sqcup 1 = 1$.

Satz 2.22  

Es gilt:

(a) $x \sqsubseteq y \Leftrightarrow x \sqcap \overline{y} = 0$

(b) $x \sqsubseteq y \Leftrightarrow 1 = \overline{x} \sqcup y$

Beweis: (a) ,,$\Rightarrow$`` Es gilt $x \sqsubseteq y$. Dann gilt nach Satz 2.13 $x = x \sqcap y$. Dann ist $x \sqcap \overline{y} \stackrel{\rm (Vor.)}{=} \lin... ...el{\rm (Bem.\ \ref{BEM4})}{=} x \sqcap 0 \stackrel{\rm (Def.\ \ref{DEF5})}{=} 0$.

,,$\Leftarrow$`` Es ist $x \sqcap \overline{y} = 0$. Dann gilt: $y \stackrel{\rm (Def.\ \ref{DEF5})}{=} 0 \sqcup y \... ...4})}{=} ( x \sqcup y ) \sqcap 1 \stackrel{\rm (Def.\ \ref{DEF5})}{=} x \sqcup y$. Dann gilt nach Satz 2.3 $x = x \sqcap y$ und daraus folgt nach Satz 2.13 $x \sqsubseteq y$.

(b) ,,$\Rightarrow$`` Es gilt $x \sqsubseteq y$. Dann gilt nach Satz 2.13 $x = x \sqcap y$ und nach Satz 2.3 gilt dann $y = x \sqcup y$. Dann ist $\overline{x} \sqcup y \stackrel{\rm (Vor.)}{=} \ove... ...el{\rm (Bem.\ \ref{BEM4})}{=} 1 \sqcup y \stackrel{\rm (Def.\ \ref{DEF5})}{=} 1$.

,,$\Leftarrow$`` Es ist $1 = \overline{x} \sqcup y$. Dann gilt: $x \stackrel{\rm (Def.\ \ref{DEF5})}{=} 1 \sqcap x \... ...4})}{=} 0 \sqcup ( x \sqcap y ) \stackrel{\rm (Def.\ \ref{DEF5})}{=} x \sqcap y$. Nach Satz 2.13 gilt dann: $x \sqsubseteq y$.

Satz 2.23 (De Morgan)  

Sei $( L, \sqcup, \sqcap )$ ein Boolescher Verband. Dann gilt für alle $x, y$:

(a) $\overline{(x \sqcap y)} = \overline{x} \sqcup \overline{y}$

(b) $\overline{(x \sqcup y)} = \overline{x} \sqcap \overline{y}$

Beweis: (a) Es ist $( x \sqcap y ) \sqcap ( \overline{x} \sqcup \overli... ...l{\rm (Def.\ \ref{DEF5})}{=} 0 \sqcup 0 \stackrel{\rm (Satz\ \ref{SATZ1})}{=} 0$. Daraus folgt nach Satz 2.22: $\overline{x} \sqcup \overline{y} \sqsubseteq \overline{( x \sqcap y)}$.

Umgekehrt ist $( x \sqcap y ) \sqcup ( \overline{x} \sqcup \overli... ...l{\rm (Def.\ \ref{DEF5})}{=} 1 \sqcap 1 \stackrel{\rm (Satz\ \ref{SATZ1})}{=} 1$. Daraus folgt nach Satz 2.22: $\overline{( x \sqcap y)} \sqsubseteq \overline{x} \sqcup \overline{y}$. Nach (H2) folgt daher: $\overline{(x \sqcap y)} = \overline{x} \sqcup \overline{y}$.

(b) Der Beweis verläuft dual.

Satz 2.24  

Sei $( L, \sqcup, \sqcap )$ ein Boolescher Verband. Dann gilt für alle $x, y$: $x \sqsubseteq y \Leftrightarrow \overline{y} \sqsubseteq \overline{x}$

Beweis: ,,$\Rightarrow$`` Es ist $x \sqsubseteq y$. Dann gilt nach Satz 2.22: $x \sqcap \overline{y} = 0$. (V2b) liefert $\overline{y} \sqcap x = 0$. Daraus folgt wieder mit Satz 2.22: $\overline{y} \sqsubseteq \overline{x}$.

,,$\Leftarrow$`` Es ist $\overline{y} \sqsubseteq \overline{x}$. Dann gilt nach Satz 2.22: $\overline{y} \sqcap \overline{\overline{x}} = 0$. Dann ist nach (V2b): $\overline{\overline{x}} \sqcap \overline{y} = 0$. Gemäß Satz 2.19 gilt dann: $x \sqcap \overline{y} = 0$. Dann gilt nach Satz 2.22: $x \sqsubseteq y$.

Satz 2.25  

Sei $( L, \sqcup, \sqcap )$ ein Boolescher Verband. Dann gilt für alle $a, b$:

(a) $a = ( a \sqcap b ) \sqcup ( a \sqcap \overline{b} )$

(b) $a = ( a \sqcup b ) \sqcap ( a \sqcup \overline{b} )$

Beweis: (a) Es ist: $( a \sqcap b ) \sqcup ( a \sqcap \overline{b} ) \st... ...el{\rm (Bem.\ \ref{BEM4})}{=} a \sqcap 1 \stackrel{\rm (Def.\ \ref{DEF5})}{=} a$.

(b) Der Beweis ist dual.

Satz 2.26 (Transportationsregel von Peirce)  

Sei $( L, \sqcup, \sqcap )$ ein Boolescher Verband. Dann gilt für alle $a, b, c$:

(a) $a \sqsubseteq b \sqcup c \Leftrightarrow a \sqcap \overline{b} \sqsubseteq c$

(b) $a \sqcap b \sqsubseteq c \Leftrightarrow a \sqsubseteq \overline{b} \sqcup c$

Beweis: (a) ,,$\Leftarrow$`` Es gilt nach Voraussetzung $a \sqcap \overline{b} \sqsubseteq c$. Nach Definition 2.10 gilt $c \sqsubseteq b \sqcup c$. Mit (H3) folgt daher $a \sqcap \overline{b} \sqsubseteq b \sqcup c$. Andererseits gilt nach Definition 2.10  $a \sqcap b \sqsubseteq b$ und auch $b \sqsubseteq b \sqcup c$. Daraus folgt nach (H3) $a \sqcap b \sqsubseteq b \sqcup c$. Nach Definition 2.10 folgt aus $a \sqcap \overline{b} \sqsubseteq b \sqcup c$ und $a \sqcap b \sqsubseteq b \sqcup c$, daß $( a \sqcap b ) \sqcup ( a \sqcap \overline{b} ) \sqsubseteq b \sqcup c$. Dann gilt nach Satz 2.25: $a \sqsubseteq b \sqcup c$.

,,$\Rightarrow$`` Es gilt nach Voraussetzung $a \sqsubseteq b \sqcup c$. Nach Definition 2.10 gilt $a \sqcap \overline{b} \sqsubseteq a$. Mit (H3) folgt daher $a \sqcap \overline{b} \sqsubseteq b \sqcup c$. Andererseits gilt nach Definition 2.10  $a \sqcap \overline{b} \sqsubseteq \overline{b}$ und auch $\overline{b} \sqsubseteq \overline{b} \sqcup c$. Daraus folgt nach (H3) $a \sqcap \overline{b} \sqsubseteq \overline{b} \sqcup c$. Nach Definition 2.10 folgt aus $a \sqcap \overline{b} \sqsubseteq b \sqcup c$ und $a \sqcap \overline{b} \sqsubseteq \overline{b} \sqcup c$, daß $a \sqcap \overline{b} \sqsubseteq ( b \sqcup c ) \sqcap ( \overline{b} \sqcup c )$ gilt. Dann gilt nach Satz 2.25: $a \sqcap \overline{b} \sqsubseteq c$.

(b) ,,$\Leftarrow$`` Den Beweis erhält man, indem man im Beweis (a) ,,$\Rightarrow$`` jedes Auftreten von $b$ durch $\overline{b}$ ersetzt und umgekehrt.

,,$\Rightarrow$`` Den Beweis erhält man, indem man im Beweis (a) ,,$\Leftarrow$`` jedes Auftreten von $b$ durch $\overline{b}$ ersetzt und umgekehrt.

Definition 2.14 (Literal)  

Ein Literal ist die Variable für ein Objekt oder dessen Komplement aus dem Trägerbereich eines Booleschen Verbandes.

Definition 2.15 (Boolesche Funktion)  

Eine Boolesche Funktion ist ein beliebiger Ausdruck, der aus endlich vielen Symbolen besteht, der die Verknüpfung von Konstanten und Variablen durch die Operationen $\sqcup$, $\sqcap$ und  $\overline{~}$ beschreibt. Dabei werden ggf. Klammern zur Erzielung der Eindeutigkeit der Ausdrücke eingesetzt.

Bemerkung 2.9  

Alle weiteren Ergebnisse dieses Abschnittes beziehen sich auf Boolesche Verbände mit endlichem Trägerbereich, also auf endliche Boolesche Verbände.

Definition 2.16 (Minterm)  

Sei $n > 0$ die Zahl der im Trägerbereich eines Booleschen Verbandes vorkommenden verschiedenen Literale. Ein Minterm ist die Verknüpfung aller $n$ Literale durch die $\sqcap$-Operation, wobei kein Literal doppelt vorkommt.

Satz 2.27  

Mit $n > 0$ Variablen kann man $2^{n}$ verschiedene Minterme erzeugen.

Beweis: (Vollständige Induktion) Sei $n = 1$. Dann gibt es nur eine Variable, sie heiße $a_{1}$ und zwei Minterme, nämlich $a_{1}$ und $\overline{a}_{1}$. Die Behauptung gilt also für $n = 1$.

Angenommen die Behauptung gelte für $n$ Variablen, es gebe also $S_{n} = 2^{n}$ Minterme. Jeder dieser Minterme hat die Form

$$m_{i}^{n} = x_{1} \sqcap x_{2} \sqcap \ldots \sqcap x_{n}, wobei~x_{i} = a_{i}~oder~\overline{a}_{i}$$

Fügt man eine weitere Variable $a_{n+1}$ hinzu, so sehen die Minterme wie folgt aus:

$$m_{i}^{n+1} = x_{1} \sqcap x_{2} \sqcap \ldots \sqcap x_{n} \sqcap x_{n+1}, wobei~x_{i} = a_{i}~oder~\overline{a}_{i}$$

Dann gilt:

$$m_{i}^{n+1} = ( x_{1} \sqcap x_{2} \sqcap \ldots \sqcap x_{n} ) \sqcap x_{n+1}$$

Der geklammerte Ausdruck ist einer der $2^{n}$ Minterme $m_{i}^{n}$, also gilt:

$$m_{i}^{n+1} = m_{i}^{n} \sqcap x_{n+1}$$

d.h., jeder Minterm für $n$ Variablen spaltet sich in zwei Minterme für $n+1$ Variablen auf, nämlich in:

$$m_{i}^{n} \sqcap a_{n+1}~{\rm und}~m_{i}^{n} \sqcap \overline{a}_{n+1}$$

Insgesamt gibt es also

$$S_{n+1} = 2 \cdot S_{n} = 2 \cdot 2^{n} = 2^{n+1}$$

Minterme für $n+1$ Variablen.

Definition 2.17 (kanonische Disjunktive Normalform)  

Eine Boolesche Funktion ist in kanonischer disjuktiver Normalform, wenn sie eine $\sqcup$-Verknüpfung (Disjunktion) von Mintermen der Funktion ist, wobei kein Minterm doppelt auftaucht.

Die konstanten Funktionen 0 und 1 sind ebenfalls in kanonischer disjunktiver Normalform für alle $n \geq 0$.

Satz 2.28  

Die kanonische disjunktive Normalform, die bei $n$ Variablen alle $2^{n}$ Minterme enthält, entspricht der 1.

Beweis: Von den $2^{n}$ Mintermen enthalten $2^{n-1}$ das Literal $a_{1}$ und $2^{n-1}$ das Literal $\overline{a}_{1}$, wie bereits im Beweis von Satz 2.27 zu erkennen war. Aus den $2^{n-1}$ Mintermen, die das Literal $a_{1}$ enthalten, wird $a_{1}$ durch mehrfache Anwendung von (V4a) ,,ausgeklammert``. Ebenso wird mit dem Literal $\overline{a}_{1}$ verfahren. Die beiden jeweils verbleibenden Terme sind gemäß Beweis von Satz 2.27 identisch, wodurch sich die Disjunktion aller Minterme in der Form $( a_{1} \sqcap q ) \sqcup ( \overline{a}_{1} \sqcap q ) \stackrel{\rm (Satz \ref{SATZ17a})}{=} q$ schreiben läßt, wobei $q$ der identische Restterm ist.

Wendet man nun auf $q$ die gleiche Technik nocheinmal an, klammert jedoch $a_{2}$ aus, so kann man $q$ schreiben als $( a_{2} \sqcap r ) \sqcup ( \overline{a}_{2} \sqcap r ) \stackrel{\rm Satz \ref{SATZ17a}}{=} r$, wobei $r$ der verbleibende Restterm ist.

Anwendung dieser Technik bis zur Ausklammerung von $a_{n-1}$ ergibt als Restterm $a_{n} \sqcup \overline{a}_{n} \stackrel{\rm (Def.\ \ref{DEF12})}{=} 1$.

Satz 2.29  

Jede Boolesche Funktion läßt sich in die kanonische disjunktive Normalform umformen.

Beweis: Dieser Beweis wird durch die Angabe eines Konstruktionsverfahrens geführt. Das Verfahren funktioniert wie folgt:

Sei $f$ eine beliebige Boolesche Funktion von $n$ Variablen, einschließlich der Konstanten 0 und 1. Wenn $f$ Ausdrücke der Form $\overline{( a \sqcup b )}$ oder $\overline{( a \sqcap b )}$ enthält, so ergibt die Anwendung von Satz 2.23 
$\overline{a} \sqcap \overline{b}$ bzw. $\overline{a} \sqcup \overline{b}$. Das wiederholt man solange, bis jede Komplement-Überstreichung nur noch über einer einzigen Variablen/Konstanten steht. Gemäß Satz 2.19 werden doppelte Negationen aufgelöst. Durch Anwendung von (V4a) und (V4b) erhält man Glieder, deren Literale nur durch $\sqcap$ verbunden sind, und diese Glieder sind wiederum nur durch $\sqcup$ verknüpft. Enthält eines dieser Glieder eine 0, so ist gemäß Definition 2.5 das ganze Glied gleich 0 und kann daher gemäß Definition 2.5 ersatzlos entfallen, falls noch ein anderes Glied vorhanden ist. Ist das einzige verbleibende Glied eine 0, so ist das Verfahren beendet. Enthält eines dieser Glieder eine 1, so entfällt gemäß Definition 2.5 die 1, falls noch ein anderes Literal in dem Glied vorkommt. Ist eines der Glieder gleich 1, so ist gemäß Definition 2.5 die gesamte Disjunktion gleich 1 und das Verfahren damit beendet. Angenommen ein Glied $g$ der Disjunktion enthält weder die Variable $a_{i}$ noch deren Komplement $\overline{a}_{i}$. Dann ist $g \stackrel{\rm (Satz \ref{SATZ17a})}{=} ( a_{i} \sqcap g ) \sqcup ( \overline{a}_{i} \sqcap g )$. Wiederholt man diesen Schritt für jede fehlende Variable in jedem Glied der Disjunktion, so erhält man schließlich eine Disjunktion von Mintermen. Satz 2.2 erlaubt es, doppelt vorkommende Glieder wegzulassen. Dann ist die entstandene Disjunktion von Mintermen eine kanonische disjunktive Normalform.

Da im beschriebenen Konstruktionsverfahren nur substituiert wird, also nur Gleichungen verwendet werden, ist das Verfahren auch umkehrbar, d.h. Boolesche Funktionen in kanonischer DNF teilen die Menge der Booleschen Funktionen in Klassen äquivalenter Funktionen ein.

Satz 2.30  

Bei $n$ Variablen lassen sich genau $2^{(2^n)}$ verschiedene disjunktive Normalformen bilden.

Beweis: Bei $n$ Variablen kann jeder der $2^{n}$ Minterme in einer kanonischen disjunktiven Normalform vorkommen oder nicht, kann etwas zu der Disjunktion beitragen oder nicht. Entsprechend der bekannten kombinatorischen Grundregel zur Variation mit Wiederholung ergibt sich daher:

$$\underbrace{2 \cdot \ldots \cdot 2}_{2^{n}} = 2^{(2^{n})}$$

Ein andere Beweismöglichkeit beruht auf dem ,,Auswählen ohne Zurücklegen und ohne Berücksichtigung der Reihenfolge``. Das entspricht der Art und Weise des Auswählens der Minterme, denn erstens wird jeder Minterm nur einmal verwendet und zweitens ist die Reihenfolge beliebig, da die Disjunktion kommutativ ist. Für diesen Fall ist die Anzahl der Auswahlmöglichkeiten von $k$ Objekten aus einer Menge von $l$ gleich ${ l \choose k}$. Für den Fall der Minterme, die die kanonischen disjunktiven Normalformen bilden sollen, muß man die Auswahlen aller $k = 0 \ldots 2^{n}$ aus $l = 2^{n}$ Mintermen betrachten. Dann ist die Anzahl der verschiedenen kanonischen disjunktiven Normalformen gleich

$$\sum_{i=0}^{2^{n}}{2^{n} \choose i} = 2^{(2^{n})},$$

ein bekanntes Ergebnis der Kombinatorik. Dabei entspricht das Auftauchen keines Mintermes der konstanten Funktion 0 und das Auftauchen aller Minterme gemäß Satz 2.28 der konstanten Funktion 1.

Satz 2.31  

Es gibt bei $n$ Variablen genau $2^{(2^n)}$ Äquivalenzklassen verschiedener Boolescher Funktionen.

Beweis: Da jede Boolesche Funktion mit $n$ Variablen in eine Boolesche Funktion in kanonisch disjunktiver Normalform mit $n$ Variablen umgeformt werden kann (Satz 2.29) und es für $n$ Variablen genau $2^{(2^n)}$ verschiedene kanonische disjunktive Normalformen gibt, heißt das, daß es genau $2^{(2^n)}$ verschiedene Boolesche Funktionen für $n$ Variablen gibt.