Minimierungsverfahren

Created by

Cards (20)

Minimierung
gegeben: f = f ( $x_1$ , ... , $x_n$ )
gesucht : möglichst kleine DNF für eine Boolesche Funktion f
so wenig Konjunktionen wie möglich (Elementarkonjunktionen K ( $x_1$ , ... , $x_n$ ), die zu einer DNF von f gehören)
so wenig Literale wie möglich
Eine DNF, die diesen Bedingungen genügt, ist eine minimale DNF für f.
Relationen zwischen Konjunktionen
K1 ( $x_1$ , ... , $x_n$ ) und K2 ( $x_1$ , ... , $x_n$ ) seien Elementarkonjunktionen. K1 ist in K2 enthalten bzw. ist ein Teilintervall (Teilwürfel) von K2, wenn K1 ≤ K2, d.h. wenn ON(K1) ⊆ ON(K2). Das ist genau dann der Fall, wenn alle Literale von K2 in K1 vorkommen. Anders formuliert: K2 überdeckt K1.
Beispiel:
n = 5
x_1 ¬x_2 x_4 ¬x_5 ist in x_1 ¬x_5 enthalten, denn es gilt: 10–10 ⊆ 1–––0.
x_2 x_4 ist nicht in ¬x_1 x_2 x_3 enthalten, und auch nicht umgekehrt; beide Intervalle überlappen sich. –1–1- / 011––
Implikant
Eine Elementarkonjunktion K ( $x_1$ , ... , $x_n$ ) = $x^{a1}_{i1} x^{a2}_{i2} ··· x^{ak}_{ik}$ heißt ein Implikant der n–stelligen Funktion f ( $x_1$ , ... , $x_n$ ),
wenn K ≤ f,
also wenn für alle $x_1$ , ... , $x_n$ gilt: K ( $x_1$ , ... , $x_n$ ) ≤ f ( $x_1$ , ... , $x_n$ ),
also wenn ON(K) ⊆ ON(f).
Primimplikant
Ein Implikant K von f heißt Primimplikant, wenn es keinen Implikanten K′ von f gibt, der echt größer als K ist, also für den gilt ON(K) ⊂ ON(K′).
Beispiel Implikant und Primimplikant
A) {(1,1,1), (1,1,0), (1,0,1), (1,0,0), (0,0,0)}
B) {010,011}
C) {110}
D) {110,111}
E) {100,101,110,111}
F) {000,100}
G) nein
H) ja
I) ja
J) ja
K) ja
L) nein
M) nein
N) nein
O) ja
P) ja
Implikanten und Primimplikanten
Eine Konjunktion K ist genau dann Implikant von f, wenn das zu K gehörige On–Set ON(K) ein Teilintervall von ON(f) ist. K ist genau dann Primimplikant, wenn ON(K) ein maximales Teilintervall von ON(f) ist. Jeder Implikant von f ist in mindestens einem Primimplikanten enthalten.
Praktische Konsequenzen
Aus einem Implikanten K′ von f kann man einen Primimplikanten K machen, der K′ enthält, indem man Literale aus K′ herausstreicht, solange das zugehörige Intervall von K noch in ON(f) liegt. Zu jeder Booleschen Funktion gibt es eine minimale DNF, in der alle vorkommenden Konjunktionen Primimplikanten sind. Wenn f = $K_1 ∨ K_2 ∨ . . . ∨ K_m$ eine minimale DNF für f ist, dann muss jede Konjunktion Ki darin ein Primimplikant sein.
Verkürzte DNF
Es sei f ( $x_1$ , ... , $x_n$ ) eine Boolesche Funktion und $K_1$ , ... , $K_m$ seien sämtliche Primimplikanten von f. Dann gilt f = K1 ∨ K2 ∨ . . . ∨ Km. Diese DNF, die aus allen Primimplikanten von f besteht, heißt die verkürzte oder gekürzte DNF von f. (im Gegensatz zur VDNF)
Sie ist bis auf die Reihenfolge der Primimplikanten eindeutig bestimmt. Die verkürzte DNF ist also (bis auf die Reihenfolge) eine echte Normalform!
Überdeckung
Die Funktion f wird von den Primimplikanten überdeckt. Es kann aber sein, dass auch eine Teilmenge der Primimplikanten bereits ausreicht, um f zu überdecken.
Zweistufige Minimierung
Schritt 1: Man finde alle Primimplikanten von f. (Ermittlung der verkürzten DNF)
Schritt 2: Aus diesen wähle man eine kleinste Menge von Primimplikanten aus, die ON(f) gemeinsam überdecken.
Streichung derjenigen Primimplikanten, die zur Überdeckung von ON(f) nicht nötig sind, weil andere Primimplikanten dies bereits erledigen.
(im Allgemeinen schwierig und nicht eindeutig)
Karnaugh-Veitch-Diagramme
zweidimensionale Repräsentation des Booleschen Würfels, auch für größere n praktikabel
(auch „Symmetriediagramm“)
A) 00
B) 01
C) 11
D) 10
E) 000
F) 100
G) 101
H) 001
I) 010
J) 110
K) 111
L) 011
M) 0000
N) 0100
O) 0101
P) 0001
Q) 1000
R) 1100
S) 1101
T) 1001
U) 1010
V) 1110
W) 111
X) 1011
Y) 0010
Z) 0110
[) 0111
\) 0011
Bildung von KV-Diagrammen
A) a
B) a
C) b
D) a
E) c
F) b
G) a
H) c
I) b
J) d
K) a
L) c
M) e
N) a
O) b
P) d
Q) a
R) a
S) e
T) b
U) d
V) b
W) d
X) f
Minimierung mit KV-Diagrammen
Intervalle entsprechen im KV-Diagramm Rechtecken, deren Kantenlänge Zweierpotenzen sind:
rechteckige Blöcke von Einsen → Implikanten
maximale derartige Blöcke → Primimplikanten
Gegenüberliegende Ränder und symmetrische Bereiche sind benachbart.
Beispiel:
Funktion vom Rang 4
8 Bereiche von Rang 3
1 Bereich vom Rang 2
Auswahl einer minimalen Überdeckung wie beim Booleschen Würfel
Verfahren von Quine/McClusky
gegeben: Boolesche Funktion f
Ermittlung aller Fundamentalkonjunktionen von f (vollständige DNF)
Ermittlung aller Primimplikanten von f (verkürzte DNF bzw. größtmögliche Intervalle)
Auswahl minimaler Überdeckungen (mit Hilfe einer Überdeckungstabelle)
Quine/McClusky Schritt 1
Ermittlung aller Fundamentalkonjunktionen
Gruppierung nach der Anzahl der vorkommenden negierten Variablen
vertikale Anordnung als erste Spalte einer Tabelle
Vereinfachung:
Verwendung der Intervallschreibweise
0 für negierte
1 für nicht negierte Variablen
– für nicht vorkommende Variablen
A) 01111
B) 10111
C) 11101
D) 00111
E) 01110
F) 10101
G) 00110
H) 01100
I) 00100
Quine/McClusky Schritt 2
Ermittlung aller Primimplikanten
paarweiser Vergleich der Konjunktionen benachbarter Gruppen
Konjunktionen, die sich nur in einer Variable unterscheiden:
Markierung in der alten Spalte
Verschmelzung zu einem Intervall
Übernahme in die nächste Spalte
aus dem Vergleich benachbarter Gruppen entstehende Konjunktionen bilden eine Gruppe der neuen Spalte
Wiederholung bis eine Verschmelzungen mehr möglich ist
→ schrittweiser Aufbau von neuen Spalten der Tabelle
A) 0-111
B) 0111-
C) -0111
D) 101-1
E) 1-101
Verschmelzen von Konjunktionen
Zwei Konjunktionen $K_1$ und $K_2$ können genau dann verschmolzen werden, wenn sie in allen Literalen bis auf eines übereinstimmen. Das Literal $x_i$ , in dem sich $K_1$ und $K_2$ unterscheiden, muss in der einen Konjunktion negiert, in der anderen unnegiert vorkommen. Ergebnis der Verschmelzung ist die Konjunktion, die aus $K_1$ bzw. $K_2$ durch Streichen von $x_i$ entsteht. K $x_i$ ∨ K ¬ $x_i$ = K
Quine/McClusky Schritt 3
Überdeckungstabelle
je eine Zeile für Elemente aus ON(f) (d.h. Fundamentalkonjunktionen)
je eine Spalte für die Primimplikanten
Markierung, wenn Primimplikant eine Belegung überdeckt
Zeilen mit nur einer Markierung enthalten wesentliche Primimplikanten, diese müssen vorkommen
→ diese Zeilen und Spalten aus der Tabelle entfernen
in der Resttabelle eine minimale Überdeckung der Belegungen suchen
(Siehe "minimierungsverfahren" p38ff., zu viele Bilder)
Minimierung mit Don’t Cares
Don’t-Care-Bedingungen:
Die Funktion ist nicht an allen Stellen festgelegt, d.h. es ist “egal”, welcher Funktionswert hier angenommen wird.
n–stellige Boolesche Funktion mit don’t–care Bedingungen:
f : {0, 1}^n → {0, 1, *}
Neben ON(f) und OFF(f) gibt es dann die Menge der Don’t-Care Stellen:
DC (f) := { (x_1 , ... , x_n ) | f (x_1 , ... , x_n ) = * }
Don‘t Cares im KV-Diagramm
Markierungen durch * (auch ‒ oder X) können bei der Zusammenfassung beliebig verwendet werden