Maria Oelinger. Schaltungen und Boolesche Algebra (7)

http://www.oelinger.de

Home Maria Oelinger
zurück zur Übersicht     Teil I Teil II Teil III

1.3 Schaltfunktionen – Teil III

Darstellung der Schaltfunktionen
in kostengünstiger Form DNF
Disjunktive Normalform
= Summe der Minterme zu den einschlägigen Indizes
      f (i₁…i_n) = 1
= ( • … • ) + … + ( • … • )
      für Zeilen der Wertetabelle mit 1 in der Ergebnisspalte
KNF
Konjunktive Normalform
= Produkt der Maxterme zu den nicht-einschlägigen Indizes
      f (i₁…i_n) = 0
= ( + … + ) • … • ( + … + )
      für Zeilen der Wertetabelle mit 0 in der Ergebnisspalte
Im allgemeinen wähle die Darstellung mit den wenigsten Termen:
Weniger Einsen: DNF
Weniger Nullen: KNF
Eindeutige Darstellung einer Booleschen Funktion (kann man evtl. noch kürzen).

Anzahl verschiedener Boolescher
bzw. Schaltfunktionen Für jede natürliche Zahl n gibt es 2^2ⁿ verschiedene Boolesche Funktionen f: BⁿB.
Schaltfunktionen f: BⁿB^m gibt es 2^m•2ⁿ Stück.

Vollständiges System
Boolescher Funktionen S := {f₁, … f_k}, wenn jede Boolesche Funktion sich durch Einsetzen und Komposition aus S darstellen läßt.

z.B. (+, •, ¬)

(+, ¬) Beweis: de Morgan

(•, ¬) Beweis: de Morgan

NAND: ¬(x • y) Beweis:
NAND <=> (NAND, NOT) <=> (AND, NOT)

NOR: ¬(x + y)

(XOR, 1, •)

weiter...

zurück zur Übersicht
Feel free to send me email: maria@oelinger.de

© 2000 Maria Oelinger
cand. math. Schaltungen und Boolesche Algebra (7) Letzte Änderung: 19.11.2000
address: http://www.oelinger.de/maria/schalt/schalt07.htm