Zum Inhalt springen

Wikibooks:Abstellraum: Strukturwissenschaften: Mathematik der Technischen Informatik

Aus Wikibooks

Mathematische Grundlagen der Technischen Informatik

[Bearbeiten]

Definition: Logische Aussage-Operationen

[Bearbeiten]

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

[Bearbeiten]
Negation ()
x NOT(x)
0 1
1 0

zweistellige Aussage-Operationen

[Bearbeiten]
Disjunktion ()
x y OR(x,y)
0 0 0
1 0 1
0 1 1
1 1 1
Konjunktion ()
x y AND(x,y)
0 0 0
1 0 0
0 1 0
1 1 1
Implikation ()
x y IMPL(x,y)
0 0 1
1 0 0
0 1 1
1 1 1
Äquivalenz ()
x y NXOR(x,y)
0 0 1
1 0 0
0 1 0
1 1 1
Antivalenz ()
x y XOR(x,y)
0 0 0
1 0 1
0 1 1
1 1 0

Definition: Bool'sche Algebra

[Bearbeiten]

Ein Tripel bestehend aus einer Trägermenge sowie den Verknüpfungen (ODER), (UND) bezeichnet man als Bool'sche Algebra, falls folgende Axiome erfüllt sind :

  • Abgeschlossenheit :
  • Kommutativität :
  • Assoziativität :
  • Distributivität :
  • Neutrale Elemente :
  • Inverse Elemente :

Korollar: Idempotenzgesetz

[Bearbeiten]

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

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

Korollar: Reduktionsgesetz

[Bearbeiten]

Des weiteren gilt das Reduktionsgesetz :

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

[Bearbeiten]

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

Definition: Bool'sche Funktion

[Bearbeiten]

Eine Bool'sche Funktion bezeichnet die Abbildung .

Hat eine Bool'sche Funktion Variablen, so besitzt sie insgesamt Funktionswerte.

Hierbei ist die folgende Schreibweise bei Funktionsanwendung der Funktion üblich :

Lemma: Literal

[Bearbeiten]

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

Definition: Bool'sches Funktional

[Bearbeiten]

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 bezeichnet die Abbildung .

Folglich gibt es genau verschiedene Funktionen und verschiedene Funktionswerte der Variablenanzahl .

Analog der Funktionsbezeichnung verwendet man üblicherweise für Bool'sche Funktionalanwendung der Art  :

Definition: Vollständiges Operatoren-System

[Bearbeiten]

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:

Definition: Shannon'scher Inversionssatz

[Bearbeiten]

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

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

Das NAND-System ()

[Bearbeiten]

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 :

  • Disjunktion

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

  • Konjunktion

Analog verhält es sich bei der Konjunktion:

Das NOR-System ()

[Bearbeiten]

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

  • Negation :

  • Disjunktion :

  • Konjunktion :