Die zweistufige Logikminimierung sucht für eine Boolesche Funktion ein Polynom (DNF) mit minimalen Kosten. Das KV-Diagramm (Karnaugh-Veitch) ist eine grafische Methode, um Primimplikanten zu bestimmen — durch Erkennen maximaler Teilwürfel (Blöcke aus 1en). Es ist die in der Klausur verlangte Methode; Quine-McCluskey liefert zwar dieselben Ergebnisse, wird aber explizit nicht akzeptiert.

Definition (Literal): Ein Literal einer Booleschen Funktion ist (positives Literal, auch ) oder (negatives Literal, auch ), wobei eine Eingangsvariable ist.

Definition (Monom): Ein Monom ist eine Konjunktion von Literalen, in der kein Literal mehrfach vorkommt und nicht sowohl als auch für dieselbe Variable. Außerdem ist ein Monom.

Definition (Minterm): Ein Monom heißt vollständig oder Minterm, wenn jede Variable entweder als positives oder negatives Literal vorkommt. Der zu gehörende Minterm ist:

mit und .

Definition (Polynom / DNF): Eine Disjunktion von paarweise verschiedenen Monomen heißt Polynom (auch disjunktive Normalform, DNF). Sind alle Monome vollständig, heißt es kanonische DNF (KDNF).

Für ist die Erfüllbarkeitsmenge (ON-Menge):

Die KDNF ist gegeben durch:

Beispiel: mit 3 Variablen.

Sei ein Monom. Die Kosten sind die Anzahl der Literale: .

Primäre Kosten : Anzahl der verschiedenen Monome (Zeilen im PLA):

Sekundäre Kosten : Anzahl der benötigten Transistoren im PLA:

Kombiniertes Kostenmaß : gilt genau dann, wenn

Definition (): gilt, wenn . (Wenn an einer Stelle 1 ist, dann auch .)

Definition (Implikant): Ein Implikant von ist ein Monom mit .

Definition (Primimplikant): Ein Primimplikant von ist ein maximaler Implikant von , d.h. es gibt keinen Implikanten von mit .

Veranschaulichung durch Würfel:

Lemma: Die Monome eines Polynoms von sind alle Implikanten von .

Satz (Quine's Primimplikantensatz): Jedes Minimalpolynom von besteht ausschließlich aus Primimplikanten von .

Ein Monom der Länge (mit Literalen) in Variablen entspricht einem -dimensionalen Teilwürfel:

Größerer Block weniger Literale günstiger.

Das KV-Diagramm für Variablen ist eine -Tabelle. Für : -Tabelle.

Standardlayout für 4 Variablen ( Zeilen, Spalten):

Für einen Block der Größe :

Beispiel: Ein -Block über den Zellen (Zeilen 00 und 10, Spalten 00 und 10):

Ein Block ist nicht prim, wenn er in einen größeren Block eingebettet werden kann. Man muss immer prüfen, ob der Block noch vergrößert werden kann (durch Hinzufügen benachbarter Zeilen/Spalten), ohne eine 0 einzuschließen.

Gegeben (aus Exam und probeklausur):

In Binär (): .

Schritt 1: KV-Diagramm ausfüllen

Schritt 2: Maximale Blöcke finden

Block 1 — Spalte 11 (alle 4 Zeilen):

Block 2 — Zeilen 00 und 10, Spalten 10 und 11:

Block 3 — Zeilen 00 und 10, Spalten 00 und 10:

Schritt 3: Prüfen, ob alle 1en überdeckt sind

Alle 1en sind überdeckt. Es gibt genau 3 Primimplikanten.

Anteil a): Reduziertes Polynom aller Primimplikanten:

Anteil b): Gegeben ist --11 (). Die zwei fehlenden Primimplikanten sind:

Anteil c): Primimplikantentafel — siehe T02-Primimplikanten-und-Ueberdeckungsproblem.

Gegeben:

KV-Diagramm:

Primimplikanten (6 Stück — Hinweis: "mehr als 5"):

Blockgröße → Literale: Monom mit Literalen -dimensionaler Teilwürfel

Die Klausuraufgabe A1 hat folgenden Aufbau:

Vorgehen in der Klausur:

Häufige Fallstricke:

Höchste Priorität — A1 ist stabil, 16P, und rein methodisch lösbar. KV-Diagramm muss sitzen wie Multiplizieren. Übe mindestens 3 verschiedene Funktionen komplett durch (KV → Primimplikanten → PIT → Minimalpolynom).