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 ($\mathrm{\neg }$)
x	NOT(x)
0	1
1	0

zweistellige Aussage-Operationen

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

Konjunktion ($\wedge$) 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 ($\iff$) 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,+,\ast )$ bestehend aus einer Trägermenge $B=\{0,1\}$ sowie den Verknüpfungen $+$ (ODER), $\ast$ (UND) bezeichnet man als Bool'sche Algebra, falls folgende Axiome erfüllt sind :

• Abgeschlossenheit : $\mathrm{\forall }a,b\in B:a+b\in B,a\ast b\in B$
• Kommutativität : $\mathrm{\forall }a,b\in B:a+b=b+a,a\ast b=b\ast a$
• Assoziativität : $\mathrm{\forall }a,b,c\in B:a+(b+c)=(a+b)+c,a\ast (b\ast c)=(a\ast b)\ast c$
• Distributivität : $\mathrm{\forall }a,b,c\in B:a+b\ast c=(a+b)\ast (a+c),a\ast (b+c)=a\ast b+a\ast c$
• Neutrale Elemente : $\mathrm{\forall }a\in B:a=0+a,a=1\ast a$
• Inverse Elemente : $\mathrm{\forall }a\in B:a+\bar{a}=1,a\ast \bar{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 :

• $\mathrm{\forall }a\in B:a=a+a=a\ast 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 :

• $\mathrm{\forall }a\in B:a+1=1,a\ast 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 :

• $\mathrm{\forall }x,x_1,x_2\in B:x_1=\bar{x},x_2=\bar{x}⟹x_1=x_2⟹\overline{\stackrel{‾}{x}}=x$

Definition: Bool'sche Funktion

Eine Bool'sche Funktion $f$ bezeichnet die Abbildung $f:B^n⟶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⟼f(x_n,\mathrm{...},x_0)$ üblich :

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

Lemma: Literal

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

• $\underset{\_}{x}=\{x,\bar{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:{\underset{\_}{x}}^n⟶B^n⟶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⟼f(\underset{\_}{x_n},\mathrm{...},\underset{\_}{x_0})$ :

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

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=\bar{x}$ $x\Rightarrow 1=1$

$0\iff x=\bar{x}$ $1\iff x=x$ $x\iff 0=\bar{x}$ $x\iff 1=x$

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

Definition: Shannon'scher Inversionssatz

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

• $\overline{a\wedge b}=\bar{a}\vee \bar{b}$
• $\overline{a\vee b}=\bar{a}\wedge \bar{b}$

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

• $\overline{{\wedge }_i{x}_i}={\vee }_i\overline{x_i}$
• $\overline{{\vee }_i{x}_i}={\wedge }_i\overline{x_i}$

Das NAND-System ($\overline{a\wedge 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 :

$\bar{x}=\overline{x\wedge x}$

• Disjunktion

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

$x\vee y=\overline{\stackrel{‾}{x\vee y}}=\overline{\stackrel{‾}{x}\wedge \stackrel{‾}{y}}=\overline{\stackrel{‾}{x\wedge x}\wedge \stackrel{‾}{y\wedge y}}$

• Konjunktion

Analog verhält es sich bei der Konjunktion:

$x\wedge y=\overline{\stackrel{‾}{x\wedge y}}=\overline{\stackrel{‾}{x\wedge y}\wedge \stackrel{‾}{x\wedge y}}$

Das NOR-System ($\overline{a\vee 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 :

$\bar{x}=\overline{x\vee x}$

• Disjunktion :

$x\vee y=\overline{\stackrel{‾}{x\vee y}}=\overline{\stackrel{‾}{x\vee y}\vee \stackrel{‾}{x\vee y}}$

• Konjunktion :

$x\wedge y=\overline{\stackrel{‾}{x\wedge y}}=\overline{\stackrel{‾}{x}\vee \stackrel{‾}{y}}=\overline{\stackrel{‾}{x\vee x}\vee \stackrel{‾}{y\vee y}}$