Wikibooks:Abstellraum: Strukturwissenschaften: Mathematik der Technischen Informatik

Mathematische Grundlagen der Technischen Informatik

Definition: Logische Aussage-Operationen

Hierbei sind im Folgenden ausschließlich extensionale logische Aussage-Operationen gemeint, also solche, deren Wahrheitsgehalt ausschließlich vom Wahrheitswert der Eingänge abhängt, aber nicht von deren Inhalt. Weiterhin bedeutet 0 = FALSCH, 1 = WAHR.

einstellige Aussage-Operationen

Negation ($\neg$)
x	NOT(x)
0	1
1	0

zweistellige Aussage-Operationen

Disjunktion ($\lor$) x y OR(x,y) 0 0 0 1 0 1 0 1 1 1 1 1

Konjunktion ($\land$) x y AND(x,y) 0 0 0 1 0 0 0 1 0 1 1 1

Implikation ($\Rightarrow$) x y IMPL(x,y) 0 0 1 1 0 0 0 1 1 1 1 1

Äquivalenz ($\Leftrightarrow$) x y NXOR(x,y) 0 0 1 1 0 0 0 1 0 1 1 1

Antivalenz ($\oplus$) x y XOR(x,y) 0 0 0 1 0 1 0 1 1 1 1 0

Definition: Bool'sche Algebra

Ein Tripel $(B,+,*)$ bestehend aus einer Trägermenge $B=\{0,1\}$ sowie den Verknüpfungen $+$ (ODER), $*$ (UND) bezeichnet man als Bool'sche Algebra, falls folgende Axiome erfüllt sind :

• Abgeschlossenheit : $\forall a,b\in B:a+b\in B,a*b\in B$
• Kommutativität : $\forall a,b\in B:a+b=b+a,a*b=b*a$
• Assoziativität : $\forall a,b,c\in B:a+(b+c)=(a+b)+c,a*(b*c)=(a*b)*c$
• Distributivität : $\forall a,b,c\in B:a+b*c=(a+b)*(a+c),a*(b+c)=a*b+a*c$
• Neutrale Elemente : $\forall a\in B:a=0+a,a=1*a$
• Inverse Elemente : $\forall a\in B:a+{\overline {a}}=1,a*{\overline {a}}=0$

Korollar: Idempotenzgesetz

Aus den obigen Axiomen lässt sich ein weiteres, für die technische Implementierung Bool'scher Funktionen äußerst wichtiges Gesetz ableiten :

• $\forall a\in B:a=a+a=a*a$

Der Beweis über eine Wertetabelle ist jedoch erheblich einfacher und, da es sich um diskrete Mengen handelt auch vollkommen legal.

Korollar: Reduktionsgesetz

Des weiteren gilt das Reduktionsgesetz :

• $\forall a\in B:a+1=1,a*0=0$

Auch hier ist der Beweis über eine Wertetabelle möglich, er kann - und sollte - aber auch axiomatisch durch logisches Schlussfolgern erfolgen.

Korollar: Eindeutigkeit des Inversen Elementes

Da jede Variable/jedes Literal genau ein Inverses Element besitzt, ist das Inverse des Inversen wieder das Ausgangselement, formal :

• $\forall x,x_{1},x_{2}\in B:x_{1}={\overline {x}},x_{2}={\overline {x}}\Longrightarrow x_{1}=x_{2}\Longrightarrow {\overline {\overline {x}}}=x$

Definition: Bool'sche Funktion

Eine Bool'sche Funktion $f$ bezeichnet die Abbildung $f:B^{n}\longrightarrow B$.

Hat eine Bool'sche Funktion $n$ Variablen, so besitzt sie insgesamt $2^{n}$ Funktionswerte.

Hierbei ist die folgende Schreibweise bei Funktionsanwendung der Funktion $y\longmapsto f(x_{n},...,x_{0})$ üblich :

• $f(...,x_{i}=1,...)=f(...+2^{i}+...)$
• $f(...,x_{i}=0,...)=f(...+0+...)$

Lemma: Literal

Unter einem Literal versteht man eine eingebettete Funktionsanwendung auf genau eine Variable. In der Bool'schen Algebra besteht die Menge der Literale ${\underline {x}}$ einer Variablen $x$ aus der Identität sowie Inversion dieser Variablen, etwas formaler ausgedrückt :

• ${\underline {x}}=\{x,{\overline {x}}\}$

Definition: Bool'sches Funktional

Nach Einführung des Literal-Begriffs ist es nun möglich die Funktionaldefinition, also die Definition einer Funktion, welche auf Mengen operiert, vorzunehmen.

Ein Bool'sches Funktional $f$ bezeichnet die Abbildung $f:{\underline {x}}^{n}\longrightarrow B^{n}\longrightarrow B$.

Folglich gibt es genau $2^{n}$ verschiedene Funktionen und $2^{2^{n}}$ verschiedene Funktionswerte der Variablenanzahl $n$.

Analog der Funktionsbezeichnung verwendet man üblicherweise für Bool'sche Funktionalanwendung der Art $f\longmapsto f({\underline {x_{n}}},...,{\underline {x_{0}}})$ :

• $f(...,x_{i},...)=f_{...+2^{i}+...}$
• $f(...,{\overline {x_{i}}},...)=f_{...+0+...}$

Definition: Vollständiges Operatoren-System

Ein Operatorensystem ist genau dann vollständig, falls Negation, Konjunktion, sowie Disjunktion darstellbar sind. Andere Bool'sche Operationen werden hierbei durch Anwendung auf eine Konstante, welche vorher ausgewertet werden muss, eliminiert:

$0\Rightarrow x=1$ $1\Rightarrow x=x$ $x\Rightarrow 0={\overline {x}}$ $x\Rightarrow 1=1$

$0\Leftrightarrow x={\overline {x}}$ $1\Leftrightarrow x=x$ $x\Leftrightarrow 0={\overline {x}}$ $x\Leftrightarrow 1=x$

$0\oplus x=x$ $1\oplus x={\overline {x}}$ $x\oplus 0=x$ $x\oplus 1={\overline {x}}$

Definition: Shannon'scher Inversionssatz

Essentiell für die Konvertierung konjunktiver/disjunktiver Normalformen ist der Shannon'sche Inversionsatz. Dessen einfache Fassung lautet:

• ${\overline {a\land b}}={\overline {a}}\lor {\overline {b}}$
• ${\overline {a\lor b}}={\overline {a}}\land {\overline {b}}$

Er lässt sich jedoch auch für beliebige Anzahl von Literalen erweitern:

• ${\overline {\land _{i}x_{i}}}=\lor _{i}{\overline {x_{i}}}$
• ${\overline {\lor _{i}x_{i}}}=\land _{i}{\overline {x_{i}}}$

Das NAND-System (${\overline {a\land b}}$)

Ein technisch einfach zu realisierendes und von daher sehr wichtiges Operatorensystem ist das NAND-System. Folgender Abschnitt beschreibt die Herleitung der essentiellen Operationen:

• Negation

Die Negation ist durch Anwendung des Idempotenzgesetzes recht schnell gezeigt :

${\overline {x}}={\overline {x\land x}}$

• Disjunktion

Dies ist durch Eindeutigkeit des Inversen Elements, Anwendung des Shannon'schen Inversionssatzes, sowie der Idempotenz einfach hergeleitet:

$x\lor y={\overline {\overline {x\lor y}}}={\overline {{\overline {x}}\land {\overline {y}}}}={\overline {{\overline {x\land x}}\land {\overline {y\land y}}}}$

• Konjunktion

Analog verhält es sich bei der Konjunktion:

$x\land y={\overline {\overline {x\land y}}}={\overline {{\overline {x\land y}}\land {\overline {x\land y}}}}$

Das NOR-System (${\overline {a\lor b}}$)

Ebenfalls einfach zu realisieren sind NOR-Systeme. Nachgewiesen werden die notwendigen Eigenschaften mit Idempotenz, Shannon'schen Inversionssatz, sowie der Eindeutigkeit des Inversen Elements:

• Negation :

${\overline {x}}={\overline {x\lor x}}$

• Disjunktion :

$x\lor y={\overline {\overline {x\lor y}}}={\overline {{\overline {x\lor y}}\lor {\overline {x\lor y}}}}$

• Konjunktion :

$x\land y={\overline {\overline {x\land y}}}={\overline {{\overline {x}}\lor {\overline {y}}}}={\overline {{\overline {x\lor x}}\lor {\overline {y\lor y}}}}$