T02-Primimplikanten-und-Ueberdeckungsproblem

Primimplikanten und Überdeckungsproblem

Zusammenfassung

Nachdem die Primimplikanten einer Booleschen Funktion bestimmt wurden (per KV-Diagramm oder Quine-McCluskey), muss eine kostenminimale Teilmenge ausgewählt werden, die alle Minterme überdeckt. Dies ist das Matrix-Überdeckungsproblem. Die Primimplikantentafel (PIT) ist die zentrale Datenstruktur; drei Reduktionsregeln und Petrick's Methode lösen das Problem. Quine-McCluskey ist in der Klausur verboten, aber das Verständnis des Algorithmus hilft, die Struktur der Primimplikanten zu verstehen.

Exam-Relevanz

  • Aufgabe 1 (A1) in der Klausur: 16 Punkte — Teil c) verlangt die Primimplikantentafel (5P)
  • Sowohl in der Exam-Klausur (WS 2024/25) als auch in der probeklausur (SoSe 2026) ist A1 identisch
  • Punkteverteilung: a) 7P (KV + Primimplikanten), b) 2P (fehlende PIs), c) 5P (PIT + wesentliche PIs + reduzierte Tafel + Minimalpolynom), d) 2P
  • Was in Teil c) verlangt wird:
    1. Primimplikantentafel ausfüllen (welcher PI überdeckt welchen Minterm)
    2. Wesentliche Primimplikanten bestimmen (Hinweis: 2 PIs)
    3. Reduzierte Tafel nach Entfernen der wesentlichen PIs ausfüllen
    4. Falls Tafel leer: "Leer" schreiben und begründen
    5. Minimales Polynom angeben
  • Wichtig: Quine-McCluskey ist in der Klausur verboten — aber die PIT und Petrick müssen beherrscht werden
  • Beide Klausuren sind nahezu identisch — dieses Thema ist STABIL

Kernkonzepte

Minimalpolynom

Definition: Ein Minimalpolynom einer Booleschen Funktion ist ein Polynom von mit minimalen Kosten:

ü

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

Beweisidee: Enthielte einen nicht-primen Implikanten , so existiert ein Primimplikant mit und . Ersetze durch → sinkt → Widerspruch zur Minimalität.

Folgerung: Die Disjunktion aller Primimplikanten ist ein Polynom für , aber im Allgemeinen kein Minimalpolynom. Man muss eine kostenminimale Teilmenge auswählen.

Berechnung von Implikanten (Grundlage für QM)

Lemma 1: Ist ein Implikant von , so auch und für jede Variable , die nicht in vorkommt.

Lemma 2: Sind und Implikanten von , so auch .

Beweis:

Satz (Charakterisierung): Ein Monom ist genau dann ein Implikant von , wenn entweder:

  • ein Minterm von ist, oder
  • und Implikanten von sind für eine Variable , die nicht in vorkommt.

Quine-McCluskey

Achtung: Quine-McCluskey ist in der Klausur verboten! Die Klausur verlangt explizit das KV-Diagramm. Das Verständnis von QM hilft aber, die Systematik hinter den Primimplikanten zu verstehen.

Idee

Berechne alle Implikanten systematisch, dann identifiziere die primen (die nicht weiter vereinheitlicht werden können).

Algorithmus

Prime implicants function Quine (f : B^n → B)
begin
    L₀ := Minterm(f);
    i := 0;
    Prim(f) := ∅
    while (Lᵢ ≠ ∅) and (i < n) do
        // Lᵢ enthält alle Implikanten von f der Länge n−i
        Lᵢ₊₁ := {m | m·x und m·x' sind in Lᵢ für ein x};
        Prim(f) := Prim(f) ∪
            {m' | m' ∈ Lᵢ und m' wird von keinem q ∈ Lᵢ₊₁ überdeckt};
        i := i + 1;
    end while;
    return Prim(f) ∪ Lᵢ;
end;

Verbesserung durch McCluskey

Vergleiche nur Monome, die:

  1. Dieselben Variablen enthalten, und
  2. Bei denen sich die Anzahl der positiven Literale um 1 unterscheidet.

Dies wird erreicht durch Partitionierung von in Klassen mit und :

  • enthält die Implikanten aus , deren Literale alle aus sind
  • Anordnung der Monome in gemäß Anzahl der positiven Literale

Worked Example: QM für 4 Variablen

Funktion (aus k341-Berechnung_eines_Minimalpolynoms_Quine_McCluskey):

Schritt 0: — alle Minterme (partitioniert nach Anzahl positiver Literale)

# positive Literale Minterme Binär ()
0 0000
1 0001, 0100, 1000
2 0011, 0101, 1001, 1010, 1100
3 0111, 1101, 1110

Schritt 1: — Vereinheitlichung (Minterme, die sich in genau 1 Bit unterscheiden, werden zusammengefasst; das differierende Bit wird zu -)

Man vergleicht nur Minterme aus benachbarten Blöcken (Anzahl positiver Literale unterscheidet sich um 1).

Beispiele:

  • 0000 und 0001 → 000- ()
  • 0000 und 0100 → 0-00 ()
  • 0000 und 1000 → -000 ()
  • 0011 und 0111 → 0-11 ()
  • 0011 und 1011 → ... aber , also nicht möglich

Alle Minterme werden zu Kanten (1-dim Implikanten). (kein Minterm ist prim).

Schritt 2: — Vereinheitlichung von -Implikanten

Je zwei Implikanten aus , die dieselben Variablen enthalten und sich in genau einer Position unterscheiden (eine hat 0, die andere 1, Rest gleich), werden zu Flächen (2-dim Implikanten).

Beispiele:

  • 0-01 und 0-11 → 0--1 () [differieren in ]
  • 100- und 110- → 1-0- () [differieren in ]
  • -000 und -010 → --00... aber prüfen: -000 = , -010 = → --00... nein, das wäre vs , differieren in → -0-0? Nein, das stimmt nicht mit der Partitionierung.

Die Implikanten aus , die nicht zu beitragen (nicht weiter vereinheitlicht werden können), sind prim.

Schritt 3: — weitere Vereinheitlichung

  • 1-0- und -0-0... verschiedene Variablenmengen, nicht vergleichbar.
  • 0--1 kann nicht weiter vereinheitlicht werden.
  • --0- entsteht aus 1-0- und 0-0- → das ist

Endergebnis:

Korrektheit und Komplexität

Satz: Für alle gilt:

  • enthält nur Monome mit Literalen
  • enthält genau die Implikanten von mit Literalen
  • Nach Iteration enthält genau die Primimplikanten mit mindestens Literalen

Komplexität: Es gibt verschiedene Monome in Variablen (jede Variable: positiv, negativ, oder absent). Die Laufzeit liegt in bzw. mit .

Warum QM in der Klausur verboten ist: Für ist QM noch machbar, aber der Aufwand ist viel größer als das KV-Diagramm. QM skaliert exponentiell und ist für Computer gedacht, nicht für Klausuren.

Primimplikantentafel

Definition

Die Primimplikantentafel ist eine Boolesche Matrix:

  • Zeilen = Primimplikanten von
  • Spalten = Minterme von

Der Eintrag ist 1, wenn der Minterm eine Ecke des Würfels (Teilwürfels) des Primimplikanten ist.

Gesucht: Eine kostenminimale Teilmenge , so dass jede Spalte überdeckt ist:

Worked Example: PIT für die Klausurfunktion

Primimplikanten (aus T01-KV-Diagramm-und-Logikminimierung):

Kurzform Monom
--11
-01-
-0-0

Minterme:

PIT ausfüllen — für jeden PI prüfen, welche Minterme er überdeckt:

  • --11 (): überdeckt alle Minterme mit :
  • -01- (): überdeckt alle mit :
  • -0-0 (): überdeckt alle mit :
Primimplikant
--11 () ✓ ✓ ✓ ✓
-01- () ✓ ✓ ✓ ✓
-0-0 () ✓ ✓ ✓ ✓

Wesentliche Primimplikanten bestimmen

Definition: Ein Primimplikant heißt wesentlich (essential), wenn es einen Minterm gibt, der nur von überdeckt wird:

Lemma: Jedes Minimalpolynom enthält alle wesentlichen Primimplikanten.

Vorgehen: Für jede Spalte (jeden Minterm) zählen, wie viele ✓ sie hat. Hat eine Spalte nur ein ✓, ist der entsprechende PI wesentlich.

Für unser Beispiel:

Minterm Welche PIs überdecken ihn? Wesentlicher PI?
nur -0-0 ja → -0-0 wesentlich
-01-, -0-0 nein
--11, -01- nein
nur --11 ja → --11 wesentlich
nur -0-0 (bereits wesentlich)
-01-, -0-0 nein
--11, -01- nein
nur --11 (bereits wesentlich)

Wesentliche Primimplikanten: --11 () und -0-0 () — das sind 2, wie im Klausurhinweis angegeben.

Reduzierte Tafel

1. Reduktionsregel: Entferne alle wesentlichen Primimplikanten und alle von ihnen überdeckten Minterme.

  • --11 überdeckt:
  • -0-0 überdeckt:

Alle 8 Minterme sind überdeckt! Die reduzierte Tafel ist leer.

Primimplikant
(leer)

Antwort: "Leer" — alle Minterme werden bereits von den wesentlichen Primimplikanten --11 und -0-0 überdeckt. Der dritte Primimplikant -01- ist nicht notwendig.

Minimales Polynom

Das minimale Polynom besteht nur aus den 2 wesentlichen Primimplikanten. , .

Drei Reduktionsregeln

1. Reduktionsregel — Wesentlicher Implikant

Ein Primimplikant ist wesentlich, wenn ein Minterm nur von überdeckt wird.

Regel: Entferne alle wesentlichen Primimplikanten und alle von ihnen überdeckten Minterme aus der PIT.

Wiederholen, bis keine wesentlichen PIs mehr existieren.

2. Reduktionsregel — Spaltendominanz

Definition: Spalte dominiert Spalte , wenn für jede Zeile gilt: .

Nutzen: Dominiert Minterm den Minterm , so braucht man nicht weiter zu betrachten, da jeder PI, der überdeckt, auch überdeckt.

Regel: Entferne alle Minterme (Spalten), die einen anderen Minterm dominieren.

3. Reduktionsregel — Zeilendominanz

Definition: Zeile dominiert Zeile , wenn für jede Spalte gilt: .

Nutzen: Dominiert PI den PI und ist , so braucht man nicht weiter zu betrachten.

Regel: Entferne alle Primimplikanten (Zeilen), die durch einen anderen, nicht teureren Primimplikanten dominiert werden.

Reihenfolge der Regeln

  1. Wende 1. Reduktionsregel an (wesentliche PIs finden und entfernen)
  2. Wende 2. Reduktionsregel an (Spaltendominanz)
  3. Wende 3. Reduktionsregel an (Zeilendominanz)
  4. Wiederhole ab Schritt 1, bis keine Regel mehr anwendbar ist
  5. Ist die Matrix leer → fertig. Sonst: zyklisches Überdeckungsproblem → Petrick oder Greedy

Beispiel: Reduktionsregeln (aus k342-Berechnung_eines_Minimalpolynoms_Ueberdeckungsproblem)

Ausgangsmatrix (nach Entfernen wesentlicher PIs):

9 10 11 12 13 14 15 16 17
E 1 1
F 1 1
G 1 1
H 1 1
I 1 1 1
J 1 1 1
K 1 1 1
L 1 1 1
M 1

2. Reduktionsregel (Spaltendominanz): Spalte 17 dominiert Spalte 10 (jeder PI, der Spalte 10 überdeckt, überdeckt auch 17, aber nicht umgekehrt — M überdeckt nur 17). Also: Spalte 17 kann gelöscht werden.

3. Reduktionsregel (Zeilendominanz) (bei gleichen Kosten): E wird von L dominiert (L überdeckt alles, was E überdeckt, und mehr). E, F, G, H werden dominiert und können entfernt werden.

Nach Anwendung: I, J, K, L werden wesentlich → Matrix leer → Minimalpolynom gefunden.

Petrick's Methode

Wann nötig?

Wenn nach Anwendung aller Reduktionsregeln die Matrix nicht leer ist, liegt ein zyklisches Überdeckungsproblem vor. Petrick's Methode liefert die exakte Lösung.

Verfahren

  1. PIT in Produkt von Summen übersetzen: Für jeden Minterm (Spalte) schreibe die Disjunktion (OR) aller PIs, die ihn überdecken.
  2. Ausmultiplizieren: Das Produkt von Summen wird zu einer Summe von Produkten (DNF).
  3. Minimales Monom wählen: Das Monom mit den wenigsten Literalen (= wenigste PIs) und minimalen Kosten entspricht der optimalen Überdeckung.

Worked Example: Zyklisches Überdeckungsproblem

Aus k342-Berechnung_eines_Minimalpolynoms_Ueberdeckungsproblem:

PI
1 1
1 1
1 1
1 1
1 1
1 1

Kein PI ist wesentlich (jeder Minterm wird von genau 2 PIs überdeckt). Keine Spalten- oder Zeilendominanz. → Zyklisches Überdeckungsproblem.

Schritt 1: Produkt von Summen

Für jede Spalte die überdeckenden PIs als Disjunktion:

Schritt 2: Ausmultiplizieren

Weiter ausmultiplizieren und mit Absorption vereinfachen ():

Schritt 3: Minimale Lösung

Bei gleichen Kosten für alle PIs sind und die minimalen Lösungen (je 3 PIs).

  • Lösung 1: (PIs )
  • Lösung 2: (PIs )

Beide überdecken alle Minterme mit minimaler Anzahl von PIs.

Worked Example: Blatt 08, Aufgabe 2

Gegebene PIT:
1 1
1 1 1
1 1 1
1 1
1 1
1 1

1. Reduktionsregel: wird nur von überdeckt → wesentlich.
Entferne und Minterme .

Restmatrix:
1 1
1 1
1 1
1 1
1 1

Keine wesentlichen PIs. Keine Spaltendominanz. Keine Zeilendominanz (bei gleichen Kosten). → Zyklisches Überdeckungsproblem.

Petrick's Methode:

Minimum finden: Welche 2 PIs überdecken alle 4 Minterme?

  • : ✓
  • : ✓
  • Alle anderen 2-Kombinationen überdecken nicht alle Minterme.

Minimale Lösungen (bei gleichen Kosten): oder .

Greedy-Heuristik

Falls Petrick's Methode zu aufwändig ist:

  1. Wende alle Reduktionsregeln an.
  2. Ist die Matrix leer → fertig.
  3. Sonst: Wähle die Zeile, die die meisten Spalten überdeckt. Lösche diese Zeile und alle überdeckten Spalten. Gehe zu 1.

Achtung: Die Greedy-Heuristik liefert nicht immer die optimale Lösung! (Siehe k342-Berechnung_eines_Minimalpolynoms_Ueberdeckungsproblem: Die M-Zeile überdeckt am meisten, ist aber nicht Teil der optimalen Lösung.)

Wichtige Formeln

Ü

Typische Klausuraufgabe

Die PIT-Aufgabe ist Teil c) von A1 (5P). Der Aufbau:

  1. PIT ausfüllen (leere Tabelle mit Primimplikanten als Zeilen, Mintermen als Spalten)
    • Für jeden PI: prüfe, welche Minterme er überdeckt (Minterm ist Ecke des PI-Würfels)
    • Kurzform-Hilfe: --11 überdeckt alle Minterme, die auf Position 3 und 4 eine 1 haben
  2. Wesentliche PIs bestimmen (Hinweis: 2)
    • Spalte mit nur einem ✓ → entsprechender PI ist wesentlich
  3. Reduzierte Tafel ausfüllen
    • Wesentliche PIs und ihre Minterme streichen
    • Falls leer: "Leer" schreiben + Begründung
  4. Minimales Polynom angeben

Für die Klausurfunktion ist die reduzierte Tafel leer — alle Minterme werden von den 2 wesentlichen PIs überdeckt. Das minimale Polynom ist:

Häufige Fallstricke:

  • PIT falsch ausfüllen: Minterm hat von (MSB = )
  • Wesentliche PIs übersehen: Jede Spalte mit nur einem ✓ bedeutet ein wesentlicher PI
  • Vergessen, überdeckte Minterme zu streichen
  • Bei zyklischem Problem: Petrick nur als Produkt von Summen aufschreiben (nicht ausmultiplizieren, falls zu aufwändig)

Übungsblätter

Blatt Was geübt wird Schwierigkeit Link
Blatt 7 Ein Schritt QM (Vereinheitlichung) Mittel Blatt07
Blatt 8 PIT reduzieren, Reduktionsregeln, Petrick's Methode Schwer Blatt08
Blatt 9 KV → quienny → PIT → Petrick (Produkt von Summen) Schwer Blatt09
Blatt 10 Vollständiger QM-Algorithmus, alle und angeben Schwer Blatt10

Quellen

Priorität

Höchste Priorität — Die PIT ist der zweite Teil von A1 (5P) und direkt an das KV-Diagramm aus T01-KV-Diagramm-und-Logikminimierung angekoppelt. Übe den kompletten Ablauf: KV-Diagramm → Primimplikanten → PIT → wesentliche PIs → reduzierte Tafel → Minimalpolynom. Die Reduktionsregeln und Petrick müssen sitzen, da bei zyklischen Problemen (wie in Blatt 8) Petrick verlangt wird.