Wikibooks:Abstellraum: Strukturwissenschaften: Mathematik der Technischen Informatik

Mathematische Grundlagen der Technischen InformatikBearbeiten

Definition: Logische Aussage-OperationenBearbeiten

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-OperationenBearbeiten

Negation ( )
x NOT(x)
0 1
1 0

zweistellige Aussage-OperationenBearbeiten

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 AlgebraBearbeiten

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: IdempotenzgesetzBearbeiten

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: ReduktionsgesetzBearbeiten

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 ElementesBearbeiten

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

  •  

Definition: Bool'sche FunktionBearbeiten

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: LiteralBearbeiten

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 FunktionalBearbeiten

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-SystemBearbeiten

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 InversionssatzBearbeiten

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 :