Minimierungsverfahren nach Karnaugh

Ausgangspunkt:

Wertetabelle

Idee:

 

• Grafische Aufstellung der Wertetabelle so, daß benachbarte Belegungen auch in der Tabelle benachbart sind.
  • Zwei Belegungen und heißen benachbart, wenn sie sich in genau einem Bit an der r-ten Stelle unterscheiden, d.h. es gilt:

    

  • Elementarkonjunktionen benachbarter Belegungen sind in der Variablen kürzbar zu Fundamental-Konjunktionen entsprechend folgender Kürzungsregeln:

    

    

• Grafische Gruppenbildung benachbarter Belegungen

Verfahren:

 

• zwei im Karnaugh-Plan benachbarte Felder erfüllen die Nachbarschaftsbeziehung (1)
• linker und rechter sowie oberer und unterer Rand des Karnaugh-Planes sind benachbart
• Minimierung durch Bilden von 2er-, 4er-, 8er-, Blöcken untereinander benachbarter Felder
• die Variablen, deren Wert innerhalb eines Blockes konstant ist, bilden den (diese Belegungen repräsentierenden) Minimalausdruck

Beispiel