Ereignisalgebra
Binäre Logik
Ein bestimmtes Ereignis ist entweder wahr oder falsch, es tritt ein oder es tritt nicht ein. Wir haben es also mit einer zweiwertigen Logik zu tun. Ein Ereignis ist eine Größe, die nur zwei bewertete Zustände besitzt. Man muß also unterscheiden zwischen der Definition eines Ereignisses und dem Wert eines Ereignisses. Die beiden möglichen Werte einer binären Variablen werden im folgenden immer durch die Symbole 0 und 1 bezeichnet. Man muß sich davor hüten, diese Symbole als Zahlen zu interpretieren. Wir hätten genausogut 0 und L oder f und w einführen können ( was man auch tatsächlich in der Literatur findet). Beispiele für eine binäre Aussage, unter Verwendung der formalen Zeichen 0 für ,,falsch'' und 1 für ,,wahr'', sind

\begin{displaymath}
\begin{array}{lll}
X \neq 0 & \rightarrow & X = 1 \\
X \neq 1 & \rightarrow & X = 0.
\end{array}\end{displaymath}

Verglichen mit der arithmetischen Algebra, bei der durch die Aussage $X \neq 0$ der Wert von $X$ in keiner Weise festgelegt ist, ist bei der Ereignisalgebra der Wertevorrat einer Variablen stark eingeschränkt. Die Ereignisalgebra arbeitet mit zweiwertigen Variablen, die arithmetische Algebra mit mehrwertigen Variablen. Wie jedes andere Rechenverfahren stellt auch die Ereignisalgebra einen mathematischen Formalismus dar, der es erlaubt, bei Berücksichtigung und Einhaltung einmal vereinbarter Rechenregeln beliebige Rechenvorgänge auszuführen und widerspruchsfreie Funktionen aufzustellen. Die arithmetische Algebra rechnet mit den Grundfunktionen ,,Multiplikation'', ,,Division'', ,,Addition'' und ,,Subtraktion''. In der Ereignisalgebra werden ähnliche Grundoperationen eingeführt und auch durch dieselben Symbole gekennzeichnet. Man muß sich aber auch hier wieder davor hüten, die Grundoperationen der Ereignisalgebra und die Grundoperationen der arithmetischen Algebra zu verwechseln. Sie haben nichts miteinander gemeinsam.

Der Amerikaner Boole leitete die Ereignisalgebra aus der symbolischen Logik ab. Daher wird die Ereignisalgebra auch als Boolsche Algebra bezeichnet. Eine Weiterentwicklung stellt die von Shannon entwickelte Schaltalgebra dar. Die Schaltalgebra ist ein Spezialfall der Ereignisalgebra. Beide können daher gemeinsam behandelt werden, was wir im folgenden auch tun werden.

Grundverknüpfungen
Von einer Funktion oder Verknüpfung sprechen wir bekanntlich, wenn der Wert der Ausgangsgrößen in ganz bestimmter Weise von dem Wert der Eingangsgrößen abhängt. Da der Wert einer binären Variblen nur zwei Werte annehmen kann, sprechen wir im folgenden statt vom Wert einer Variablen auch vom Zustand einer Variablen. In der Ereignisalgebra und in der Schaltalgebra läßt sich jeder logische Zusammenhang zwischen binären Variablen mit Hilfe von 3 logischen Grundfunktionen beschreiben:

\begin{displaymath}
\begin{array}{lll}
NOT & (NICHT) & Negation \\
AND & (UND) & Konjunktion \\
OR & (ODER) & Disjunktion
\end{array}\end{displaymath}

Wir haben die amerikanischen Bezeichnungen gewählt und die deutsche Übersetzung in Klammern aufgeführt. Im folgenden benutzen wir immer die amerikanischen Originalbezeichnungen. Jede dieser Verknüpfungen stellt eine definierte Rechenoperation dar, die man in 4 verschiedenen Weisen anschaulich darstellen kann:
- rechnerisch durch eine formale Gleichung;
- tabellarisch durch Funktionstabellen;
- grafisch durch eine flächenmäßige Veranschaulichung des Ereignisraumes, dem sogenannten Venn- Diagramm;
- durch symbolische Schaltzeichen der Digitaltechnik;
Um dem Anfänger den Einstieg zu erleichtern, werden wir im folgenden alle 4 Möglichkeiten zur Veranschaulichung benutzen.

Die NOT Verknüpfung (Negation oder auch Inversion) ist eine logische Funktion mit nur einer binären Variablen. Sie bewirkt daß die Ausgangsvariable stets den entgegengesetzten Zustand der Eingangsvariablen annimmt. Wir definieren:
Die NOT Verknüpfung hat die Eigenschaft, den Zustand einer binären Variablen stets umzukehren (zu negieren, zu invertieren).
Wir schreiben:

\begin{displaymath}
Y= \overline{X},
\end{displaymath} (1)

was heißen soll, angewandt auf die zwei Grundzustände 0 und 1:

\begin{displaymath}
\begin{array}{ll}
\overline{0} = 1 \\
\overline{1} = 0.
\end{array}\end{displaymath}

Die Funktionstabelle, das Symbol der Schaltalgebra und die Veranschaulichung im Venn- Diagramm sind in Abbildung 1 aufgeführt.

Abbildung 1: Funktionstabelle, Symbol der Schaltalgebra und Venn- Diagramm der NOT- Verknüpfung.

Für die Anwendung in der Schaltalgebra bedeutet dieses also, daß am Ausgang Y eine Spannung anliegt, wenn am Eingang X keine Spannung anliegt, und umgekehrt. In der Ereignisalgebra sagen wir, daß das Ereignis Y eingetreten ist, wenn das Ereignis X nicht eingetreten ist, und umgekehrt. Wir sehen an diesem Beispiel bereits, daß die rechnerische Formel und die Funktionstabelle unabhängig von der speziellen Anwendung, in unserem Fall von der Ereignisalgebra oder der Schaltalgebra, sind, während Schaltzeichen und Venn- Diagramm auf die speziellen Anwendungen zugeschnitten sind. Zweifache Anwendungen der Negation auf ein und dieselbe Größe kann weggelassen werden:

$\displaystyle \overline{\overline{X}}$ $\textstyle =$ $\displaystyle X$ (2)
$\displaystyle \overline{\overline{\overline{X}}}$ $\textstyle =$ $\displaystyle \overline{X}.$ (3)

Dieses ist einleuchtend, denn auch im normalen Sprachgebrauch hebt sich eine doppelte Verneinung auf, z.B. bedeutet ,,es gibt nichts, was es nicht gibt'' sinngemäß soviel wie ,,es gibt alles'' oder ,,alles ist möglich''.

Die AND Verknüpfung (Konjunktion) ist eine logische Funktion mit mindestens 2 binären Eingangsvariablen $X_{1}$, $X_{2}$, ....,$X_{n}$. Wir definieren:
Eine AND Verknüpfung liefert nur dann den logischen Wert 1, wenn alle Eingangsvariablen ebenfalls eine logische 1 aufweisen.
Sobald also nur eine Eingangsvariable den Wert 0 hat, liefert die AND Verknüpfung den Wert 0. Wir schreiben:

\begin{displaymath}
Y= X_{1} \cdot X_{2} \cdot \cdot \cdot \cdot \cdot X_{n}.
\end{displaymath} (4)

Funktionstabelle, Symbol der Schaltalgebra und Venn- Diagramm bei 2 Eingangsvariablen sind in Abbildung 2 gezeigt.

Abbildung 2: Funktionstabelle, Symbol der Schaltalgebra und Venn- Diagramm der AND- Verknüpfung.

Abbildung:

In der Sprache der Ereignisalgebra sagen wir, daß das Ereignis $Y$ eingetreten ist, genau dann, wenn die Ereignisse $X_{1}$ und $X_{2}$ beide eingetreten sind. Bei der digitalen AND Schaltung liegt genau dann am Ausgang eine Spannung an, wenn alle Eingänge unter Spannung stehen.

Die OR Verknüpfung (Disjunktion) ist eine logische Funktion mit mindestens 2 binären Eingangsvariablen und einer binären Ausgangsvariablen Y. Es gilt die Definition:
Eine OR Verknüpfung liefert bereits dann am Ausgang eine logische 1, sobald nur eine Eingangsvariable den logischen Wert 1 annimmt.
Es erscheint also am Ausgang eine Null, dann und nur dann, wenn alle Eingänge gleichzeitig im Nullzustand sind. Wir schreiben:

\begin{displaymath}
Y = X_{1}+ X_{2} + .... + X_{n}
\end{displaymath} (5)

Funktionstabelle, Schaltsymbol und Darstellung im Venn- Diagramm sind für 2 Eingangsvariable in Abbildung 3 gezeigt.

Abbildung 3: Funktionstabelle, Schaltalgebra und Darstellung im Venn- Diagramm der OR- Verknüpfung.

In der Sprache der Ereignisalgebra sagen wir, daß das Ereignis Y eingetreten ist, wenn $X_{1}$ oder $X_{2}$ eingetreten ist, oder auch wenn beide eingetreten sind. Die Schaltzeichen für die AND und OR Verknüpfung bei n Eingangsvariablen sind in Abbildung 4 aufgeführt.

Abbildung 4: Schaltzeichen für die AND- und OR- Verknüpfungen bei n Eingangsvariablen.

Ereignisraum
Wir kommen jetzt noch einmal auf den Ausgangspunkt unserer Betrachtungen im vorherigen Kapitel zurück, nämlich auf die Darstellung des Ereignisraumes. Ist $E_{1}$, $E_{2}$, ...., $E_{n}$ ein System von Ereignissen eines Versuches, sind ferner die $E_{\nu}$ paarweise unvereinbar,

\begin{displaymath}
E_{\nu} \cdot E_{\mu} = 0 \; f''ur \; \nu \neq \mu ,
\end{displaymath} (6)

und tritt eines der Ereignisse $E_{\nu}$ immer ein,
\begin{displaymath}
\sum_{i=1}^{n} E_{i} = 1 ,
\end{displaymath} (7)

so bilden die Ereignisse $E_{1}$, $E_{2}$, ...., $E_{n}$ ein System von Elementarereignissen. Ein beliebiges Ereignis $X$ läßt sich als Summe (logisches OR) von Elementarereignissen schreiben:
\begin{displaymath}
X = \sum_{i=1}^{m} E_{\nu_{i}} , \; \; m \leq n .
\end{displaymath} (8)

Wir erhalten damit ein System von $2^{n}-1$ Ereignissen im Ereignisraum. Hiervon sind allerdings nur n paarweise unvereinbar, nämlich die Elementarereignisse $E_{i}$ $(i=1,2,...,n)$. Der Ereignisraum wird zusätzlich vervollständigt durch das unmögliche Ereignis $X=0$. Mit Hilfe der Verknüpfungsrelationen zwischen Ereignissen läßt sich also auch der Ereignisraum mathematisch exakt definieren. Die verschiedenen logischen Verknüpfungen zwischen diesen Ereignissen $X_{i}$ $(i=1,2,...,2^{n})$ werden uns im folgenden weiter beschäftigen.

Andere Schreibweisen
Man findet in der Literatur für die Grundoperationen andere Schreibweisen (DIN Norm 66000):

\begin{displaymath}
\begin{array}{lllll}
X_{1} \cdot X_{2} & \equiv & X_{1} \wed...
...uiv & X_{1} \vee X_{2} & \equiv & X_{1} \cup X_{2}
\end{array}\end{displaymath}

In der amerikanischen Literatur und auch im deutschsprachigen Raum werden auch noch andere Schaltzeichen benutzt.

Dualität
Die AND Verknüpfung

\begin{displaymath}
Y = X_{1} \cdot X_{2} \cdot \cdot \cdot X_{n}
\end{displaymath}

ist identisch mit der OR Verknüpfung

\begin{displaymath}
\overline{Y} = \overline{X}_{1} + \overline{X}_{2} + .... + \overline{X}_{n}.
\end{displaymath}

Die Richtigkeit dieser Behauptung kann man leicht an Hand der beiden Funktionstabellen in Tabelle 1 verifizieren.

Tabelle 1: Funktionstabellen zum Text.
$X_{1}$ $X_{2}$ $Y=X_{1} \cdot X_{2}$
     
0 0 0
1 0 0
0 1 0
1 1 1
$\overline{X}_{1}$ $\overline{X}_{2}$ $\overline{Y} =
\overline{X}_{1} + \overline{X}_{2}$
     
1 1 1
0 1 1
1 0 1
0 0 0

Ebenso folgt aus

\begin{displaymath}
Y = X_{1} + X_{2} + ..... + X_{n}
\end{displaymath}

die Relation

\begin{displaymath}
\overline{Y} = \overline{X}_{1} \cdot \overline{X}_{2}
\cdot \cdot \cdot \cdot \overline{X}_{n}.
\end{displaymath}

Es gilt also: Eine AND Verknüpfung bezogen auf den Funktionswert 1 ist eine OR Verknüpfung bezogen auf den Funktionswert 0. Eine OR Verknüpfung bezogen auf den Funktionswert 1 ist eine AND Verknüpfung bezogen auf den Funktionswert 0. Diesen Sachverhalt bezeichnet man auch als Dualität zwischen AND und OR. Die prinzipelle Bedeutung dieser Aussage besteht darin, daß man wegen der Dualität nur 2 der 3 logischen Grundverknüpfungen wirklich braucht, um alle logischen Funktionen zu beschreiben. Für die Schaltalgebra heißt dieses, daß man nur 2 Schaltelemente (NOT und AND, oder NOT und OR) braucht, um alle nur denkbaren logischen Schaltungen zu realisieren. Tatsächlich benutzt man allerdings in der Digitaltechnik zwei andere Schaltelemente, nämlich NAND und NOR. Diese können wir mit unseren Verknüpfungsregeln schreiben als $\overline{X_{1} \cdot X_{2}}$ und $\overline{X_{1} + X_{2}}$. Für weitere Einzelheiten verweisen wir auf die einschlägige Literatur. Wir geben in Abbildung 5 noch die Schaltzeichen für die NAND und NOR Verknüpfung.

Abbildung 5: Schaltzeichen der in der Digitaltechnik verwendeten NAND- und NOR- Verknüpfungen.

Rechenregeln
Die folgenden Rechenregeln kann man sich leicht an Hand einer Funktionstabelle oder mit Hilfe von Venn- Diagrammen klar machen.
Erweiterung:

$\displaystyle X$ $\textstyle =$ $\displaystyle X \cdot X \cdot X \cdot \cdot \cdot \cdot X$ (9)
$\displaystyle X$ $\textstyle =$ $\displaystyle X + X + X + .... + X$ (10)

Kommutativität:
$\displaystyle X_{1} \cdot X_{2}$ $\textstyle =$ $\displaystyle X_{2} \cdot X_{1}$ (11)
$\displaystyle X_{1} + X_{2}$ $\textstyle =$ $\displaystyle X_{2} + X_{1}$ (12)

Assoziativität:
$\displaystyle X_{1} \cdot ( X_{2} \cdot X_{3})$ $\textstyle =$ $\displaystyle (X_{1} \cdot X_{2}) \cdot X_{3} =
X_{1} \cdot X_{2} \cdot X_{3}$ (13)
$\displaystyle X_{1} + (X_{2} + X_{3})$ $\textstyle =$ $\displaystyle (X_{1} + X_{2}) + X_{3} = X_{1} + X_{2} + X_{3}$ (14)

Distributivität:
$\displaystyle X_{1} \cdot (X_{2} + X_{3})$ $\textstyle =$ $\displaystyle X_{1} \cdot X_{2} + X_{1} \cdot X_{3}$ (15)
$\displaystyle X_{1} + (X_{2} \cdot X_{3})$ $\textstyle =$ $\displaystyle (X_{1} + X_{2}) \cdot (X_{1} + X_{3})$ (16)

De Morgansche Gesetze:
$\displaystyle \overline{X_{1} \cdot X_{2} \cdot \cdot \cdot \cdot \cdot X_{n}}$ $\textstyle =$ $\displaystyle \overline{X}_{1} + \overline{X}_{2} + ... + \overline{X}_{n}$ (17)
$\displaystyle \overline{X_{1} + X_{2} + ... + X_{n}}$ $\textstyle =$ $\displaystyle \overline{X}_{1} \cdot
\overline{X}_{2} \cdot \cdot \cdot \cdot \cdot \overline{X}_{n}$ (18)

Insbesondere die Gesetze zur Erweiterung und das zweite distributive Gesetz haben kein Analogon in der arithmetischen Algebra. Besonders weitreichende Konsequenzen haben die Gesetze zur Erweiterung. Sie zeigen nämlich, daß es nicht möglich ist, höherwertige Funktionen wie etwa die Exponentialfunktion oder den Logarithmus zu definieren. Die beiden de Morganschen Gesetze hatten wir bereits in anderer Schreibweise als Dualität zwischen AND und OR behandelt. Für spätere Anwendungen definieren wir noch die Subtraktion:
\begin{displaymath}
X_{1} - X_{2} = X_{1} \cdot \overline{X}_{2} .
\end{displaymath} (19)

Für die Subtraktion gelten ebenfalls Distributivgesetze:
$\displaystyle X_{1} \cdot (X_{2}- X_{3}) = X_{1} \cdot X_{2} - X_{1} \cdot X_{3}$     (20)
$\displaystyle X_{1} - (X_{2} \cdot X_{3}) = (X_{1} - X_{2}) \cdot (X_{1} - X_{3})$     (21)

Rechenbeispiel
Wir betrachten die logische Gleichung

\begin{displaymath}
Y = (X_{1} \cdot \overline{X}_{2}) + (X_{1} \cdot X_{2}) +
(\overline{X}_{1} \cdot X_{2}) .
\end{displaymath} (22)

Hierbei kann es sich entweder um ein Ereignis $Y$ handeln, daß durch eine logische Verknüpfung mit Hilfe zweier anderer Ereignisse $X_{1}$ und $X_{2}$ definiert wurde, oder um eine digitale Schaltung mit den Eingängen $X_{1}$, $X_{2}$ und dem Ausgang $Y$. Das Venn- Diagramm dieser Gleichung ist außerordentlich unübersichtlich. Wir haben daher darauf verzichtet, es hier aufzumalen. Die Schaltung würde wie auf der linken Seite in Abbildung 7 aussehen.

Die Frage ist nun, kann man die logische Gleichung (22) auch einfacher schreiben, bzw. kann man den Schaltplan vereinfachen? Wir erweitern zunächst mit einem der auftretenden Klammerausdrücke,

\begin{displaymath}
Y = (X_{1} \cdot \overline{X}_{2}) + (X_{1} \cdot X_{2}) + (X_{1} \cdot X_{2})
+ (\overline{X}_{1} \cdot X_{2}).
\end{displaymath}

Sodann wenden wir das distributive Gesetz an,

\begin{displaymath}
Y = X_{1} \cdot (\overline{X}_{2} + X_{2}) + X_{2} \cdot (X_{1} +
\overline{X}_{1}).
\end{displaymath}

Wegen $\overline{X}_{2}+X_{2}= X_{1}+\overline{X}_{1}=1$ erhalten wir schließlich
\begin{displaymath}
Y = X_{1} + X_{2} .
\end{displaymath} (23)

In der Sprache der Ereignisalgebra ist das Ereignis $Y$ also nichts anderes als das Ereignis ,,$X_{1}$ oder $X_{2}$''. Man erkennt an diesem Beispiel bereits, das es recht mühsam sein kann, komplizierte Gleichungen oder Aussagen zu vereinfachen, insbesondere für mehr als 2 Eingangsvariable.

Dieses Beispiel soll im folgenden Applet noch einmal erläutert werden. Mit NOT, AND und OR Elementen ist hierbei die Funktion (22) realisiert. Im unteren Teil des Appletfensters ist die Schaltung zur Gleichung (23) gezeigt. In diesem Applet können Sie beliebige Schaltungen mit den Schaltelementen des Menus auf der linken Seite entwickeln. Ziehen Sie dazu einfach mit der Maus das Element vom Menu in das Appletfenster hinein. Umgekehrt können Sie ein Element aus der Schaltung entfernen, wenn es wieder in das Menu zurückgezogen wird. Alternativ können Sie auch das Element anklicken und dann mit der Schere entfernen. Die Verbindung zwischen zwei Elementen kann durch Anklicken der gelben Lötstellen entfernt werden. Im oberen Menu ist ausser der Schere noch eine Diskette zum Abspeichern der Schaltung, sowie ein Ordner zum Laden einer Schaltung. Mit dem leeren Blatt ganz links können Sie das Appletfenster löschen.

Allgemeine Funktionstabelle.
Betrachten wir ganz allgemein ein logisches System mit n Eingangsvariablen $X_{1}$, $X_{2}$, ...., $X_{n}$. Wieviel verschiedene logische Funktionen sind nun bei den n Eingangsvariablen überhaupt möglich?

Wir konstruieren uns für 2 Eingangsvariable das Bitmuster aller möglichen Eingangs- und Ausgangskombinationen und schreiben dieses nicht wie bisher nebeneinander, sondern untereinander. Wir erhalten dann die allgemeinste Funktionstabelle in Tabelle 2.


Tabelle: Bitmuster aller möglichen Ein- und Ausgangskombinationen bei 2 Eingangsvariablen.
Eingangsvariable $X_{1}$ 0 1 0 1 Verknüpfung mit
  $X_{2}$ 0 0 1 1 AND, OR und NOT
             
Ausgangsvariable $Y_{0}$ 0 0 0 0 0
  $Y_{1}$ 0 0 0 1 $X_{1} \cdot X_{2}$
  $Y_{2}$ 0 0 1 0 $\overline{X}_{1} \cdot X_{2}$
  $Y_{3}$ 0 0 1 1 $X_{2}$
  $Y_{4}$ 0 1 0 0 $X_{1} \cdot \overline{X}_{2}$
  $Y_{5}$ 0 1 0 1 $X_{1}$
  $Y_{6}$ 0 1 1 0 $X_{1} \cdot \overline{X}_{2} +
\overline{X}_{1} \cdot X_{2}$
  $Y_{7}$ 0 1 1 1 $X_{1} + X_{2}$
  $Y_{8}$ 1 0 0 0 $\overline{X_{1} + X_{2}}$
  $Y_{9}$ 1 0 0 1 $\overline{X}_{1} \cdot \overline{X}_{2}
+ X_{1} \cdot X_{2}$
  $Y_{10}$ 1 0 1 0 $\overline{X}_{1}$
  $Y_{11}$ 1 0 1 1 $\overline{X}_{1} + X_{2}$
  $Y_{12}$ 1 1 0 0 $\overline{X}_{2}$
  $Y_{13}$ 1 1 0 1 $X_{1} + \overline{X}_{2}$
  $Y_{14}$ 1 1 1 0 $\overline{X_{1} \cdot X_{2}}$
  $Y_{15}$ 1 1 1 1 1

Es ergeben sich 16 logische Verknüpfungen. Dieses Ergebnis läßt sich verallgemeinern:
Bei n Eingangsvariablen $X_{1}$, $X_{2}$, ...., $X_{n}$ können $2^{2^{n}}$ verschiedene logische Verknüpfungen gebildet werden. Jede Ausgangsfunktion besteht aus einem Bitmuster von $2^{n}$ binären Zeichen.
Die in der Tabelle vorkommenden Ausdrücke $\overline{X_{1} \cdot X_{2}}$ und $\overline{X_{1} + X_{2}}$ hatten wir bei der Diskussion der Dualität bereits als NAND und NOR Verknüpfung identifiziert. Wir sehen aus der Tabelle, daß alle Funktionen ausschließlich mit NOT, AND und OR Verknüpfungen gebildet werden konnten. Das Verknüpfungsgesetz selbst kann man bei 2 Eingangsvariablen noch relativ leicht aus dem Bitmuster ,,erraten''. Bei mehreren Eingangsvariablen kann das dagegen eine mühsame Aufgabe werden. Insbesondere wollten wir ja die Formel finden, die einen geforderten Zusammenhang zwischen Ein- und Ausgangsvariablen mit der geringsten Zahl von Grundverknüpfungen erfüllt. Wir hatten ein derartiges Verfahren oben in unserem Rechenbeispiel schon durch Rechnen und Probieren geübt. Ein systematisches Verfahren wurde von Karnaugh und Veitch entwikelt (KV Tafeln). Eine Diskusiion dieser Methode führt aber über den Rahmen dieses Tutorials hinaus.

Normalformen
Wir definieren zunächst zwei Begriffe:
Ein Minterm oder Vollkonjunktion ist die AND Verknüpfung aller vorkommenden Variablen. Ein Maxterm oder Volldisjunktion ist die OR Verknüpfung aller vorkommenden Variablen.
Mit Hilfe dieser Begriffe kann man eine vorgegebene Funktionstabelle durch die sogenannte Normalform beschreiben. Wir definieren:
In der disjunktiven Normalform

\begin{displaymath}
Y_{D} = f(X_{1},X_{2},....,X_{n})
\end{displaymath} (24)

werden alle Vollkonjunktionen (Minterme) der Eingangsvariablen $X_{1}$, $X_{2}$, ..., $X_{n}$, die den Funktionswert $Y=1$ ergeben, disjunktiv (OR) miteinander verknüpft. In der konjunktiven Normalform
\begin{displaymath}
Y_{K} = f(X_{1},X_{2},....,X_{n})
\end{displaymath} (25)

werden alle Volldisjunktionen (Maxterme) der Eingangsvariablen $X_{1}$, $X_{2}$, ..., $X_{n}$, die den Funktionswert $Y=0$ ergeben, konjunktiv (AND) miteinander verknüpft.
Zur Erläuterung greifen wir aus obiger Tabelle die Funktion $Y_{3}$ heraus. Dieses ist in Tablelle 3 gezeigt.

Tabelle 3: Beispiel einer Funktionstabelle.
$X_{1}$ 0 1 0 1
$X_{2}$ 0 0 1 1
         
$Y_{3}$ 0 0 1 1

Die disjunktive Normalform ist

\begin{displaymath}
Y_{3D} = X_{1} \cdot X_{2} + \overline{X}_{1} \cdot X_{2} ,
\end{displaymath}

während die konjunktive Normalform durch

\begin{displaymath}
Y_{3K} = (X_{1}+X_{2}) \cdot (\overline{X}_{1} + X_{2})
\end{displaymath}

gegeben ist. In beiden Fällen können die Ausdrücke weiter durch die distributiven Gesetze vereinfacht werden zu

\begin{displaymath}
Y_{3D}= (X_{1}+\overline{X}_{1}) \cdot X_{2} = X_{2}
\end{displaymath}


\begin{displaymath}
Y_{3K}= X_{2} + (X_{1} \cdot \overline{X}_{1}) = X_{2} .
\end{displaymath}

Dieses ist genau die Funktion, die in der Funktionstabelle angeschrieben wurde. Wir sehen also, daß man mit Hilfe der Normalformen zwar immer einen logischen Ausdruck aus der Funktionstabelle herleiten kann, daß es sich hierbei aber noch nicht um den einfachsten Ausdruck handelt. Die Normalformen liefern Zerlegungen des Ereignisses $Y$ in paarweise unvereinbare Ereignisse. Um dieses klarer zu erkennen, schreiben wir die Minterme mit $Y=1$ und Maxterme mit $Y=0$ für alle Kombinationen der Eingangsvariablen $X_{1}$ und $X_{2}$ an (siehe Tabelle 4).


Tabelle 4: Minterme und Maxterme bei 2 Eingangsvariablen.
$X_{1}$ $X_{2}$ Minterme mit $Y=1$ Maxterme mit $Y=0$
       
0 0 $Y_{D1}=\overline{X}_{1} \cdot \overline{X}_{2}$ $Y_{K1}=X_{1} + X_{2}$
1 0 $Y_{D2}=X_{1} \cdot \overline{X}_{2}$ $Y_{K2}= \overline{X}_{1}+X_{2}$
0 1 $Y_{D3}= \overline{X}_{1} \cdot X_{2}$ $Y_{K3} = X_{1}+\overline{X}_{2}$
1 1 $Y_{D4}=X_{1} \cdot X_{2}$ $Y_{K4}= \overline{X}_{1}
+ \overline{X}_{2}$

Wir bezeichnen diese Tabelle als die Minterm- bzw. Maxterm- Tabelle. Man sieht sofort daß die AND Verknüpfung von 2 beliebigen Mintermen den Wert 0 ergibt, was wir als paarweise unvereinbar definiert hatten. Ebenso liefert die OR Verknüpfung beliebiger Maxterme den Wert 0.

Übungen
Aufgabe 1:
Vereinfachen Sie die Gleichung

\begin{displaymath}
Y = \overline{X_{1} + X_{2}} + X_{1} \cdot \overline{X}_{2}
+ \overline{X}_{1} \cdot X_{2}
\end{displaymath}

so, daß Sie mit einem einzigen Schaltelement auskommen.
Die obige Gleichung haben wir im folgenden Applet als Schaltung realisiert. Erweitern Sie das Applet und bauen Sie im unteren Teil des Fensters Ihre Lösung ein
Aufgabe 2:
Gegeben sei die Schaltung des folgenden Applets, die nur mit NAND- Gliedern aufgebaut wurde. Ändern Sie die Schaltung so, daß nur NOT-, AND- und OR- Elemente benutzt werden. Wie lautet die Funktionsgleichung, ausgedrückt in Mintermen ?



Harm Fesefeldt
2004-06-30