Logikoptimierung

  • Überblick digitale Synthese
  • Logikoptimierung
  • Begriffe
  • Mehrstufige Logik
  • Zweistufige Logik: Exakte Verfahren
  • ... Heuristische Verfahren
  • ... Expansion/Reduktion
  • ... Streichen
Startseite
Begriffe   Boolesche Funktion x = x(a,b,c,d) = ab + b(c+d) + abcd Literale Disjunktive Normalform (DNF) x = (ab) + (bc) + (bd) + abcd Produktterme Minterm Konjunktive Normalform (KNF)  x = (a+b) (b+c) (b+d) (a+b+c+d) Maxterm Summenterme

Produktterme bzw. Summenterme, die alle Variablen der booleschen Funktion invertiert oder nicht invertiert enthalten, heißen Minterme bzw. Maxterme. Enthält eine DNF bzw. KNF nur Minterme bzw. Maxterme, heißt sie kanonische DNF bzw. KNF.

Ein Produktterm p heißt Implikant für eine Funktion f, wenn gilt: p=1 => f=1. Ein Implikant heißt Primimplikant, wenn aus dem Produktterm kein Literal entfernt werden kann, ohne dass er seine Eigenschaft Implikant zu sein, verliert.

In der disjunktiven Normalform sind alle Produktterme Implikanten. In einer minimierten DNF sind alle Implikanten Primimplikanten.

Um die Schreibweise zu vereinfachen, wird im Folgenden ähnlich wie bei der Multiplikation das UND-Zeichen in den Gleichungen weggelassen.