Wikibooks:Abstellraum: Strukturwissenschaften: Mathematik der Technischen Informatik

Aus Wikibooks

Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

[Bearbeiten] Mathematische Grundlagen der Technischen Informatik

[Bearbeiten] 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.

[Bearbeiten] einstellige Aussage-Operationen

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

[Bearbeiten] 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

[Bearbeiten] 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

[Bearbeiten] 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.

[Bearbeiten] 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 Schluss folgern erfolgen.

[Bearbeiten] 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

[Bearbeiten] 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 2n Funktionswerte.

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

  • f(...,xi = 1,...) = f(... + 2i + ...)
  • f(...,xi = 0,...) = f(... + 0 + ...)

[Bearbeiten] 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}\}

[Bearbeiten] 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 2n 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 +...}

[Bearbeiten] 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}

[Bearbeiten] 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}

[Bearbeiten] 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}}

[Bearbeiten] 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}}

Von „http://de.wikibooks.org/wiki/Wikibooks:Abstellraum:_Strukturwissenschaften:_Mathematik_der_Technischen_Informatik“
Persönliche Werkzeuge