2.4 Das Venn-Diagramm

Um ein Venn-Diagramm einwandfrei definieren zu können, ist es zunächst notwendig, einige grundlegende geometrische und topologische Begriffe eindeutig festzulegen.

Definition 2.18 (Region)  

Eine Region ist eine Teilmenge des ${\R{^{2}}}$.

Bemerkung 2.10  

Das Komplement einer Region ist wieder eine Region.

Definition 2.19 (innerer Punkt)  

Ein Punkt heißt innerer Punkt einer Region, wenn es eine Umgebung um diesen Punkt gibt, die vollständig in der Region enthalten ist.

Definition 2.20 (äußerer Punkt)  

Ein Punkt heißt äußerer Punkt, wenn er innerer Punkt des Komplements der Region ist.

Definition 2.21 (Rand einer Region)  

Randpunkt einer Region ist ein Punkt, der weder innerer noch äußerer Punkt ist. Die Menge der Randpunkte bildet den Rand einer Region.

Definition 2.22 (Kurve)  

Eine Punktmenge heißt eine Kurve, wenn eine stetige, injektive Abbildung eines Intervalles auf diese Menge existiert.

Definition 2.23 (zusammenhängende Region)  

Eine Region heißt zusammenhängend, wenn zwei beliebige verschiedene Punkte der Region durch eine Kurve verbunden werden können, deren Punkte nur Punkte der Region sind.

Definition 2.24 (konvexe Region)  

Eine Region ist konvex, wenn zwei beliebige verschiedene Punkte der Region durch eine Strecke verbunden werden können, deren Punkte nur innere Punkte der Region sind.

Zur Verdeutlichung einige Beispiele von Kurven und Regionen:

(a) ist eine Kurve, (b) ist eine zusammenhängende Region, wenn der ,,Kreuzungspunkt`` zur Region gehört, sonst ist die Region nicht zusammenhängend, (c) ist eine zusammenhängende Region, (d) ist eine konvexe Region und daher natürlich auch zusammenhängend.

Definition 2.25 (offener Kern)  

Der offene Kern einer Region ist die Menge der inneren Punkte der Region.

Definition 2.26 (offene Region)  

Eine Region heißt offen, wenn der offene Kern einer Region die gesamte Region ist, wenn sie also nur aus inneren Punkten besteht.

Definition 2.27 (Schnitt von Regionen)  

Ein Schnitt zweier Regionen ist die Schnittmenge der beiden Regionen und selbst wieder eine Region.

Definition 2.28 (unabhängige Familie von Regionen)  

Es sei $A = { A_{1}, \ldots , A_{n} }$ eine Familie von $n$ Regionen. $A$ ist eine unabhängige Familie von Regionen, wenn die Regionen offen und zusammenhängend sind, die Komplemente der Regionen zusammenhängend und jeder Schnitt $y_{1} \cap \ldots \cap y_{n}$ von Regionen existiert (also nicht leer ist), wobei $y_{i}$ entweder die Region $A_{i}$ oder der offene Kern des Komplements von $A_{i}$ ist.

Definition 2.29 (Venn-Diagramm)   Sei $A = { A_{1}, \ldots , A_{n} }$ eine unabhängige Familie von Regionen. Ein Venn-Diagramm besteht aus einer endlichen Region, genannt der Rahmen des Diagrammes, sowie im Inneren des Rahmens aus einer unabhängigen Familie von Regionen $A$, wobei die Schnitte $y_{1} \cap \ldots \cap y_{n}$ zusätzlich offene zusammenhängende Regionen sein müssen, die Zellen des Venn-Diagrammes genannt werden.

Bemerkung 2.11 (Venn-Diagramm)  

Der Rahmen um die unabhängige Familie von Regionen im Venn-Diagramm bezeichnet das sogenannte ,,Univers of Discurs``, und grenzt die unendliche Punktebene auf einen kleinen Bereich ein, der nur die $n$ betrachteten Regionen enthält. Dieses ist notwendig, damit die später noch einzuführende Schraffierungsoperation auf den Regionen endlich ist.

Einige Beispiele von Venn-Diagrammen:

(a) ist ein Venn-Diagramm mit einer Region, (b) ein Venn-Diagramm mit zwei Regionen, (c) ein Venn-Diagramm mit drei Regionen, (d) ein Venn-Diagramm mit vier Regionen und (e) ein Venn-Diagramm mit fünf Regionen. Besonderes Kennzeichen dieser Diagramme ist, daß die verwendeten Regionen konvex sind.

(f) zeigt kein Venn-Diagramm, denn zwei der Schnitte sind nicht zusammenhängend. (g) ist nicht einmal eine unabhängige Familie, denn der Schnitt der drei Regionen ist leer. (h) zeigt ein Diagramm mit fünf Regionen, das oft als Venn-Diagramm bezeichnet wird. Im Sinne der Definition 2.29 trifft das jedoch nicht zu, denn die fünfte Region ist ein Ring, das Komplement dieser Region daher nicht zusammenhängend.

(i) zeigt ein weiteres Venn-Diagramm mit vier Regionen. Die vierte Region ist aber nicht mehr konvex. Dieses Diagramm bildet den Ausgangspunkt einer ganzen Reihe von Diagrammen. Gezeigt seien hier nur die Diagramme mit fünf (j) und sechs (k) Regionen. Jedes Diagramm entsteht aus dem vorherigen, indem der Rand der $n$-1-ten Region in einer ,,schlauchförmigen`` neuen Region verpackt wird. Diese Konstruktion läßt sich bis zu einem beliebigen $n$ fortsetzen, allerdings gibt es bald zeichentechnische Probleme.

Definition 2.30  

Die $n$ Variablen $a_{1}, \ldots , a_{n}$ eines endlichen Booleschen Verbandes seien in beliebiger, z.B. alphabetischer, aber letztlich fester Reihenfolge geordnet. Dann wird jedem Minterm $X = x_{n}\ldots x_{1}$ für $n$ Variablen in einem Venn-Diagramm mit einer unabhängigen Familie von $n$ Regionen $A_{1}, \ldots , A_{n}$ die Zelle zugeordnet, die sich als Schnitt von $n$ Regionen ergibt, wobei jeweils die Region $A_{i}$ berücksichtigt wird, wenn $x_{i} = a_{i}$ ist, oder aber der offene Kern des Komplements von $A_{i}$, wenn $x_{i} = \overline{a_{i}}$ ist.

Satz 2.36  

Die in Definition 2.30 beschriebene Abbildung ist bijektiv.

Beweis: Unterscheiden sich zwei Minterme für $n$ Variablen an mindestens einer Stelle, so werden sie auch mit unterschiedlichen Zellen im Venn-Diagramm identifiziert, da dann der Schnitt mit dem Komplement einer Region durchgeführt wird und nicht mit der Region selbst (bzw. umgekehrt). Die Abbildung ist also injektiv.

Die Definition des Venn-Diagrammes legt fest, daß für eine unabhängige Familie von $n$ Regionen jeder der Schnitte $y_{1} \cap y_{2} \cap \ldots \cap y_{n}$ eine offene zusammenhängende Region ist, wobei jedes $y_{i}$ entweder die (offene) Region $A_{i}$ oder der offene Kern des Komplements von $A_{i}$ ist. Jedes der $y_{i}$ kann also in den Schnitten $y_{1} \cap y_{2} \cap \ldots \cap y_{n}$ zwei Regionen darstellen. Daher gibt es rein kombinatorisch mindestens $2^{n}$ verschiedene Zellen in einem Venn-Diagramm. Jeder dieser Schnitte ist nach Definition zudem zusammenhängend, d.h., es gibt genau $2^{n}$ Zellen in einem Venn-Diagramm.

Daher ist für die Abbildung aus Definition 2.30 die Anzahl der Bilder (Zellen) gleich der Anzahl der Urbilder (Minterme), die Abbildung ist daher surjektiv, also insgesamt bijektiv.

Aufgrund der Zuordnung der Mintermvariablen zu den Regionen (Def. 2.30 und Satz 2.36), gibt es also eine eineindeutige Abbildung zwischen den Zellen im Venn-Diagramm und den Mintermen Boolescher Funktionen für $n$ Variablen.

Bemerkung 2.12  

Um bestimmte Zellen zu markieren wird im folgenden ein Punkt in den betreffenden Zellen plaziert werden^2.1

Nun wird eine Beziehung zwischen beliebigen Booleschen Funktionen und Mengen von Zellen hergestellt.

Definition 2.31  

Seien $x$ und $y$ Boolesche Funktionen, die ein Grundobjekt repräsentieren. Dann sind $M_{x}$ und $M_{y}$ Mengen der Zellen, die in der jeweiligen Region liegen, die das Grundobjekt $x$ bzw. $y$ repräsentiert. Dann gilt:

• $M_{x \sqcap y}$ = $M_{x} \cap M_{y}$.

• $M_{x \sqcup y}$ = $M_{x} \cup M_{y}$.

• $0$ wird mit dem Schnitt aller Zellen identifiziert, d.h., da die Zellen disjunkt sind, mit der leeren Punktmenge, also mit keiner Zelle, abgekürzt $M_{0}$.

• $1$ wird mit der Vereinigung aller Zellen identifiziert, mit dem gesamten Diagramm (ohne Ränder), abgekürzt $M_{1}$.

• $M_{\overline{x}}$ = $M_{1} \backslash M_{x}$.

Mit dieser Definition haben wir die sogenannten Vennschen Umfangs-Diagramme definiert. Wir hätten genausogut sog. Inhalts-Diagramme definieren können. Im folgenden werden wir uns nur mit den Umfangs-Diagrammen beschäftigen, dieses also auch nicht mehr gesondert erwähnen. Wer sich für die Inhaltsdiagramme interessiert, sollte in [5] nachlesen.

Satz 2.37  

Die in Definition 2.31 definierte Abbildung, genannt ,,$h$``, zwischen Booleschen Funktionen und Mengen von Zellen ist ein Isomorphismus.

Beweis: Es gilt:

$$\begin{eqnarray*}h(x \sqcap y) & = & M_{x \sqcap y} \\ & = & M_{x} \cap M_{y} \\ & = & h(x) \cap h(y) \end{eqnarray*}$$

$$\begin{eqnarray*} h(x \sqcup y) & = & M_{x \sqcup y} \\ & = & M_{x} \cup M_{y} \\ & = & h(x) \cup h(y) \end{eqnarray*}$$

$$\begin{eqnarray*}h(\overline{x}) & = & M_{1} \backslash M_{x} \\ & = & h(1) \backslash h(x) \end{eqnarray*}$$

$h$ ist also ein Homomorphismus. Aus dem Beweis von Satz 2.36 hat sich ergeben, daß ein Venn-Diagramm mit einer unabhängigen Familie von $n$ Regionen genau $2^{n}$ Zellen enthält, die eineindeutig auf die $2^{n}$ Minterme Boolescher Verbände für $n$ Variablen abgebildet werden. Mehrere Zellen können zu einem größeren Bereich zusammengefaßt werden. Dieses entspricht nach Definition 2.31 der Disjunktion der entsprechenden Minterme. Die gleiche Argumentation wie in Satz 2.30 führt dazu, daß sich $2^{(2^n)}$ verschiedene Zellenkombinationen bilden lassen. Nach Satz 2.31 gibt es $2^{(2^n)}$ verschiedene Boolesche Funktionen für $n$ Variablen. Die Abbildung $h$ ist also surjektiv, daher insgesamt bijektiv und damit ein Isomorphismus.

Satz 2.38  

Alle Axiome des Booleschen Verbandes lassen sich im Venn-Diagramm verifizieren.

Beweis: Wir bilden die Vereinigung von $a$ und $b$ (a) und vereinigen das Ergebnis mit $c$ (b). Andererseits vereinige man $a$ mit der Vereinigung von $b$ und $c$ (c). Das Ergebnis (d) ist identisch mit (b).

Damit ist (V1a) bewiesen. Nun bilden wir den Schnitt von $a$ und $b$ (e) und schneiden das Ergebnis mit $c$ (f). Andererseits schneide man $a$ mit dem Schnitt von $b$ und $c$ (g). Das Ergebnis (h) ist identisch mit (f).

Damit ist (V1b) bewiesen. Es ist im Venn-Diagramm völlig beliebig, ob der Schnitt von $a$ und $b$ oder der Schnitt von $b$ und $a$ gebildet wird. Betroffen ist (sind) immer die gleiche(n) Zelle(n). Ebensolches gilt für die Vereinigung von $a$ und $b$ und die Vereinigung von $b$ und $a$. Damit sind auch (V2a) und (V2b) erledigt.

Schneidet man $a$ mit der Vereinigung von $a$ und $b$, so bleiben die Zellen von $a$, womit (V3a) bewiesen ist. Vereinigt man $a$ mit dem Schnitt von $a$ und $b$, so bleiben die Zellen von $a$, daher ist auch (V3b) bewiesen.

Schneidet man $a$ mit der Vereinigung von $b$ und $c$ (i), so ist das Ergebnis (j). Vereinigt man den Schnitt von $a$ und $b$ (k) mit dem Schnitt von $a$ und $c$ (l), so ist das Ergebnis (m) identisch mit (j).

Damit ist (V4a) bewiesen. Vereinigt man $a$ mit dem Schnitt von $b$ und $c$ (n), so ist das Ergebnis (o). Schneidet man die Vereinigung von $a$ und $b$ (p) mit der Vereinigung von $a$ und $c$ (q), so ist das Ergebnis (r) identisch mit (o).

Damit ist (V4b) bewiesen. Die leere Menge vereinigt mit den Zellen von $a$ ergibt die Zellen von $a$. D.h. es ist $0 \sqcup a = a$. Daher ist die leere Punktmenge das Null-Objekt. Das gesamte Diagramm $M_{1}$ geschnitten mit den Zellen, die $a$ repräsentieren, ergibt wieder die Zellen von $a$. D.h. es ist $1 \sqcap a = a$. Daher ist $M_{1}$ das Eins-Objekt. Das Innere der Region, die $a$ repräsentiert, vereinigt mit dem offenen Kern des Komplements der von $a$ repräsentierten Region ergibt nach Definition das gesamte Diagramm, ist also $1$. Das Innere der Region, die $a$ repräsentiert, geschnitten mit dem offenen Kern des Komplements der $a$ repräsentierenden Region ergibt nach Definition der Diagramme den leeren Schnitt, ist also $0$. Daher erfüllt der offene Kern des Komplements der $a$ repräsentierenden Region die Bedingungen der Booleschen Komplementdefinition. Eine vergleichbare Form der Substitutionsregel gilt, zumindest auf dieser Stufe der Einführung der Venn-Diagramme, auch im Hintergrund der Diagramme. Wie sonst hätte man auch die Booleschen Gleichungen bearbeiten können. Ein Beweis der Substitutionsregel ist daher nicht notwendig.

Satz 2.39  

Ein endlicher Boolescher Verband mit $n$ Variablen ist isomorph mit einem Venn-Diagramm mit einer unabhängigen Familie von $n$ Regionen.

Beweis: Mit dem Beweis von Satz 2.38 ist gezeigt, daß sich mit Venn-Diagrammen alles machen läßt, was in endlichen Booleschen Verbänden möglich ist. Umgekehrt zeigte der Beweis von Satz 2.37 die Isomorphie des Booleschen Verbandes mit den Venn-Diagrammen. Weitere Axiome haben die Venn-Diagramme in dem Sinne nicht.

Satz 2.40  

Mit Kreisen können nur Venn-Diagramme bis $n = 3$ erzeugt werden. Mit Ellipsen kann man bis $n = 5$ kommen. Siehe dazu [3].

Beweis: Für ein zusammenhängendes Netz in der Ebene gilt der Euler Satz:

$$e - k + f = 2$$

wobei $e$ die Zahl der Schnittpunkte, $k$ die Zahl der Kanten und $f$ die Zahl der Zellen ist, die durch das Netz in der Ebene erzeugt werden.

Das Netz werde durch die Ränder einer unabhängigen Familie von $n$ Regionen erzeugt, wie sie für Venn-Diagramme definiert sind. Es können ${n \choose 2}$ Regionen-Paare aus den $n$ Regionen kombiniert werden. Schneiden sich je 2 Regionen-Ränder in $j$ Punkten, und haben keine 3 Regionen-Ränder einen gemeinsamen Punkt, so hat das Netz $e \leq j \cdot {n \choose 2}$ Schnittpunkte und $k = 2 \cdot e$ Kanten. Dann vereinfacht sich der Euler-Satz zu:

$$f - e = 2$$

Für ein Venn-Diagramm ist $f = 2^{n}$. Daher gilt:

$$2^{n} - e = 2$$

Einsetzen der Ergebnisse für Schnittpunkte und Kanten ergibt:

$$2^{n} - j \cdot { n \choose 2} \geq 2$$

Umgeformt nach $j$ ergibt sich:

$$j \geq \frac{( 2^{n} -2 )}{{n \choose 2}} = \frac{ 4 \cdot ( 2^{n-1} - 1)}{n \cdot ( n - 1 )}$$

Die Ränder zweier kreisförmiger Regionen schneiden sich in maximal 2 Punkten, die Ränder zweier ellipsenförmiger Regionen in maximal 4 Punkten. $j$ ist also für Kreise gleich 2 und obige Formel ist erfüllbar für $n < 4$. Für Ellipsen ist $j$ gleich 4, und obige Formel ist erfüllbar für $n < 6$.