Boolescher Verband/Einführung/Textabschnitt

Definition

Ein Verband ${}M$ heißt boolesch, wenn er komplementär und distributiv ist.

Statt boolescher Verband sagt man auch boolesche Algebra. Ein boolescher Verband ist insbesondere ein kommutativer Halbring. Der Teilmengenverband auf einer beliebigen Menge ist ein boolescher Verband, die Komplementarität ist durch die Komplementbildung auf Teilmengen gegeben, daher der Name. Von diesem Hauptbeispiel her sind auch die folgenden Regeln vertraut.

Lemma

In einem booleschen Verband ${}M$ gelten die folgenden Rechenregeln.

1. Zu jedem Element ${}x\in M$ gibt es genau ein Element ${}y\in M$ mit ${}x\sqcap y=0$ und ${}x\sqcup y=1$. Es wird mit ${}\neg x$ bezeichnet.
2. Es ist

   ${}\neg \neg x=x\,.$

3. Es ist ${}\neg 0=1$ und ${}\neg 1=0$.
4. Es ist

   ${}\neg (x\sqcap y)=\neg x\sqcup \neg y\,.$

5. Es ist

   ${}\neg (x\sqcup y)=\neg x\sqcap \neg y\,.$

Beweis

1. Es seien ${}y$ und ${}z$ Komplemente von ${}x$. Dann ist

   ${}y=y\sqcup 0=y\sqcup (x\sqcap z)=(y\sqcup x)\sqcap (y\sqcup z)=1\sqcap (y\sqcup z)=y\sqcup z\,.$

   Da ebenso ${}z=y\sqcup z$ gilt, folgt ${}y=z$.

2. Siehe Aufgabe.
3. Siehe Aufgabe.
4. Siehe Aufgabe.
5. Siehe Aufgabe.

$\Box$

Die letzten beiden Regeln nennt man Regeln von de Morgan.