6.2 Eine Abbildung der Diagramme in eine einfache Struktur

Welches ist nun eine geeignete Umsetzungsmethode eines Hyperdiagrammes für den Computer ? Dazu sehen wir uns das folgende Beispiel an:

Wir verwenden ein Venn-Diagramm für 3 Grundobjekte. Dieses hat 2$^{3}$ = 8 Zellen. Den drei Grundobjekten geben wir die Namen $a$, $b$ und $c$. Eine Zelle wird eindeutig definiert durch die Angabe, zu welchen Grundobjekten sie gehört und zu welchen sie nicht gehört ( die Minterme ).

Desweiteren soll das Grundobjekt durch eine 1, sein Negat durch eine 0 gekennzeichnet werden. Das führt zu den folgenden Bezeichnungen der acht Zellen:

						$c$ $b$ $a$
$\overline{c}$	$\sqcap$	$\overline{b}$	$\sqcap$	$\overline{a}$		0 0 0		0
$\overline{c}$	$\sqcap$	$\overline{b}$	$\sqcap$	$a$		0 0 1		1
$\overline{c}$	$\sqcap$	$b$	$\sqcap$	$\overline{a}$		0 1 0		2
$\overline{c}$	$\sqcap$	$b$	$\sqcap$	$a$		0 1 1		3
$c$	$\sqcap$	$\overline{b}$	$\sqcap$	$\overline{a}$		1 0 0		4
$c$	$\sqcap$	$\overline{b}$	$\sqcap$	$a$		1 0 1		5
$c$	$\sqcap$	$b$	$\sqcap$	$\overline{a}$		1 1 0		6
$c$	$\sqcap$	$b$	$\sqcap$	$a$		1 1 1		7

Für jede der Zellen ergibt sich in diesem Beispiel eine eindeutige Ziffernkombination als Identifikation. Wenn man die Ziffernkombinationen als dreistellige Dualzahlen betrachtet, ergeben sich die Zahlen von 0 bis 7.

Bemerkung 6.1  

Nun werden wir die im Beispiel realisierte Idee verallgemeinern. Dazu ist eine Ordung der Grundobjekte notwendig. Diese kann beliebig sein, z.B. alphabetisch, muß dann aber fest sein.

Definition 6.1  

Sei $a_{1}, \ldots , a_{n}$ eine geordnete Folge von $n$ Grundobjekten. Sei $X$ ein Minterm mit $n$ Variablen, bestehend aus den Literalen $x_{n}\ldots x_{1}$. Sei $a_{i}$ das i-te Grundobjekt in der vorgegebenen Ordnung, $\overline{a_{i}}$ das Komplement des i-ten Grundobjekts. Es läßt sich eine charakteristische Funktion $F$ wie folgt definieren:

$$F_{i}(X) = \left\{ \begin{array}{ll} 1, & x_{i} = a_{i} \\ 0, & x_{i} = \overline{a_{i}} \end{array} \right.$$

Damit läßt sich eine Funktion $W$ definieren:

$$W(X) = \sum_{i=1}^{n}{F_{i}(X) \cdot 2^{i-1}}$$

Satz 6.1  

Die Funktionen $F$ und $W$ ordnen bei $n$ Grundobjekten den Mintermen eindeutig die Zahlen von 0 bis $2^{n}-1$ zu.

Beweis: Sei $n$ = 1. Dann gibt es zwei Minterme $a$ und $\overline{a}$, die gemäß Definition 6.1 die Nummern 0 und 1 haben. Die Minterme sind damit eindeutig durch die Zahlen 0 bis $2^{1}-1 = 1$ dargestellt.

Seien nun bei $n$ Grundobjekten die $2^{n}$ Minterme gemäß Definition 6.1 eindeutig durch die Zahlen von 0 bis $2^{n}-1$ dargestellt. Fügt man nun ein weiteres Grundobjekt zu der dualen Zahlenfolge $x_{n}\ldots x_{1}$ hinzu, so ergeben sich aus jeder Zahlenfolge zwei neue, nämlich $0x_{n}\ldots x_{1}$ und $1x_{n}\ldots x_{1}$. Es ist $0x_{n}\ldots x_{1}$ = $x_{n}\ldots x_{1}$, die Zahl bleibt also erhalten. Es ist $1x_{n}\ldots x_{1}$ = $2^{n} + x_{n}\ldots x_{1}$, d.h. zu jeder Zahl wird $2^{n}$ hinzuaddiert. Es gibt also keine ,,Kollisionen`` und auch keine ,,Lücke``, d.h. $n+1$ Grundobjekte sind durch die Zahlen von 0 bis $2^{n+1}-1$ eindeutig dargestellt.

Satz 6.2  

Die in Definition 6.1 definierte Abbildung ist bijektiv.

Beweis: Unterscheiden sich zwei Minterme an mindestens einer Stelle (dieses sei die Stelle $i$), so ist deren charakteristische Funktion $F$ an dieser Stelle entweder 0 oder $2^{i-1}$. Aufgrund der binären Konstruktion der Zahlen durch die Funktion $W$ läßt sich dieser fehlende Summand nicht durch andere Summanden kompensieren, daher sind die Bildwerte der Abbildung ebenfalls verschieden und die Abbildung ist injektiv. Da $2^{n}$ Minterme gemäß Satz 6.1 durch die Zahlen von 0 bis $2^{n}-1$ dargestellt werden können, ist die Abbildung auch surjektiv, also bijektiv.

Die Umkehrabbildung könnte z.B. wie folgt aussehen:

(mit $\&$ als bitweisem ,,Booleschen`` UND-Operator)

$$F_{i}^{'}(W) = 2^{i-1} \;\&\; W$$

$$x_{i} = \left\{ \begin{array}{ll}a_{i}, & F_{i}^{'}(W) \not = 0 \\ \overline{a_{i}}, & F_{i}^{'}(W) = 0 \end{array} \right.$$

Definition 6.2  

Sei $B^{n}$ die Menge der Booleschen Funktionen eines Booleschen Verbandes mit $n$ Objekten. Sei $V_{0}^{n}$ die Menge der Zellen eines Venn-Diagrammes, welches aus einer unabhängigen Familie von $n$ Regionen gebildet wird. Sei $V^{n}$ die Potenzmenge von $V_{0}^{n}$. Sei $M^{n}$ die Potenzmenge der Menge $\left\{ 0,\ldots , 2^{n}-1\right\}$. Wir definieren eine Abbildung $G^{n}: B^{n} \longrightarrow M^{n}, y \mapsto G_{y}^{n} = \bigcup_{X \in y} \{W(X)\}$, die Boolesche Funktionen auf Mengen von Zahlen abbildet.

Satz 6.3  

Venn-Diagramme für $n$ Regionen und die Menge $M^{n}$ mit den Operatoren $\cap$, $\cup$ und ' sind zueinander isomorph.

Beweis: Satz 2.39 lieferte die Isomorphie zwischen Booleschen Verbänden für $n$ Variablen und Venn-Diagrammen für $n$ Regionen. Die Abbildung $G^{n}$ ist eine isomorphe Abbildung (die Isomorphie basiert auf der Bijektion zwischen Mintermen und den Zahlen aus Satz 6.2) zwischen Booleschen Verbänden für $n$ Variablen und der Menge $M^{n}$. Daher sind auch Venn-Diagramme für $n$ Regionen mit der Menge $M^{n}$ isomorph.

Bemerkung 6.2  

Sei $a_{k}$ das $k$-te Grundobjekt. Dann kann man die zugehörige Menge von Zahlen auch durch die folgende Vorschrift gewinnen:

$$G^{n}_{a_{k}} := \bigcup_{m = 0}^{2^{n-k}-1}{\left\{ m \cdot ... ...) \cdot 2^{k}-1 \right\}} \hspace{1.4cm} k = \{ 1,\ldots , n \}$$

Aus der Menge der Zahlen von 0 bis $2^{n}-1$ werden die Zahlen ausgewählt, die in dualer Darstellung an der $k$-ten Stelle eine 1 haben.

Für $k = 1$ wechseln sich 0 und 1 jeweils ab (beginnend mit 0), die Länge der 0- und 1-Blöcke ist also 1. Für jedes weitere Grundobjekt verdoppelt sich die Länge der 0- und der 1-Blöcke, die Länge ist allgemein $2^{k-1}$. Die Anzahl der jeweiligen Blöcke halbiert sich bei jedem Schritt.

Es seien $G^{n}_{z}$ und $G^{n}_{y}$ die zwei Booleschen Funktionen $z$ und $y$ gemäß Definition 6.2 zugeordneten Mengen.

$$G^{n}_{z \sqcap y} = G^{n}_{z} \cap G^{n}_{y} \hspace{1cm} G^... ... \hspace{1cm} G^{n}_{\overline{z}} = G^{n} \backslash G^{n}_{z}$$

Man kann also ein Venn-Diagramm für $n$ Grundobjekte auf die Menge der Zahlen $\left\{ 0,\ldots , 2^{n}-1\right\}$ abbilden. Dabei ist jede Zahl eine eindeutige Identifikation der jeweils gemeinten Zelle im Venn-Diagramm.

Ein Venn-Diagramm für $n$ Grundobjekte kann ganz einfach durch ein eindimensionales Array oder eine lineare Liste mit $2^{n}$ noch zu definierenden Einträgen dargestellt werden, wobei die Einträge mit 0 beginnend fortlaufend numeriert werden.

Jede Boolesche Funktion kann gemäß Satz 6.3 als eine einfache Menge von Zahlen, als eine Teilmenge der Menge $\left\{ 0,\ldots , 2^{n}-1\right\}$ dargestellt werden. Hier ist eine Repräsentation als lineare Liste von Zahlen am geeignetsten. Durch einen einfachen Parser werden die Prämissen/Konklusionen gelesen und die Menge der betroffenen Zellen regelrecht ausgerechnet. Dazu sind die ,,Booleschen`` Operationen UND, ODER und NICHT als Mengenoperationen ,,Schnitt``, ,,Vereinigung`` und ,,Komplementbildung`` auf den linearen Listen realisiert.

Das Grundobjekt ,,$a$`` wird im Programm also dargestellt durch eine Liste der Zellennummern, die es im Venn-Diagramm belegt. Im obigen Beispiel für drei Grundobjekte sind das alle die Nummern, die in der dualen Darstellung eine 1 ganz rechts haben, also die Zahlen 1, 3, 5 und 7. Das Grundobjekt ,,$b$`` des Beispiels besteht aus den Zahlen 2, 3, 6 und 7. Das Objekt ,,$a$ UND $b$`` entsteht dann als Schnittmenge der Listen der Grundobjekte ,,$a$`` und ,,$b$``; es entspricht also einer Liste, welche die Nummern 3 und 7 enthält.