Archiv für den Monat: Januar 2013

Petrick

Petrick’s Methode

Typischer Einsatz:
Wenn man eine Primimplikantentafel vollständig reduziert hat.

z.B. Diese Tafel (OK diese Tafel läßt sich durch hinschauen
auf [`x]2 x4 reduzieren, ist aber nur ein Beispiel … )

0001 0011 1011 1001
[`x]1[`x]2x4 1 1 0 0
[`x]2 [`x]3x4 1 0 0 1
[`x]2x3x4 0 1 1 0
x1[`x]2x4 0 0 1 1

Jetzt werden die Primimplikanten von 1 an durchnummeriert. Und die Minterme mit Buchstaben von A an (alternativ lassen sie sich auch mit Zahlen durchnummerien aber des Beispiels wegen, werden hier Buchstaben genommen).

Es ergibt sich folgenden Primimplikantentafel:

A B C D
1 1 1 0 0
2 1 0 0 1
3 0 1 1 0
4 0 0 1 1

Bilden der Summen:
Um die A Spalte zu überdecken kann man 1 oder 2 benützen,
d.h. (1 + 2)
Bei B (1 + 3), C (3 + 4), und bei D (2 + 4).

Die Produktsumme
(1 + 2) ·(1 + 3) ·(3 + 4) ·(2 + 4)

Da (1 + 2) = (2 + 1) usw. gilt und die Reihenfolgen der Multiplikation
egal ist, formen wir die Produktsumme um zu:
(2 + 1) ·(1 + 3) ·(3 + 4) ·(4 + 2)

(2 + 1) ·(1 + 3) ·(3 + 4) ·(4 + 2) = (21 + 23 + 11 + 13) ·(34 + 32 + 44 + 42)
mit   11 = 1   usw.   21 = 12   usw.
= (12 + 23 + 1 + 13) ·(34 + 23 + 4 + 24)
= (1234 + 1223 + 124 + 1224) + (2334 + 2323 + 234 + 2324) + (134 + 123 + 14 + 124) + (1334 + 1323 + 134 + 1324)
mit 11 = 1 usw. 21 = 12 usw. doppelte streichen z.B. 124 + 124 = 124
= 1234 + 123 + 124 + 234 + 23 + 14 + 134
Bei gleichen Kosten für alle Primimplikanten sind 23 und 14 minimal.

Ungeschickt multipliziert:

(1 + 2) ·(1 + 3) ·(3 + 4) ·(2 + 4) = (11 + 13 + 21 + 23)·(32 + 34 + 42 + 44)
mit   11 = 1   usw.   21 = 12   usw.
= (1 + 13 + 12 + 23)·(23 + 34 + 24 + 4)
= (123 + 134 + 124 + 14) + (1323 + 1334 + 1324 + 134) + (1223 + 1234 + 1224 + 124) + (2323 + 2334 + 2324 + 234)
mit 11 = 1 usw. 21 = 12 usw. doppelte streichen z.B. 124 + 124 = 124
= 123 + 134 + 124 + 14 + 1234 + 23 + 234
Bei gleichen Kosten für alle Primimplikanten sind 23 und 14 minimal.

Aufgaben zu Petrick Methode

Aufgabe 1:
Die boolesche Funktion f: B4 B sei gegeben durch
die Menge ihrer Primimplikanten P(f) mit
P(f) = { x1[`x]2[`x]4, x1[`x]3[`x]4, x1[`x]2[`x]3, x1x2[`x]3, x1 x2 x4, x1x3x4 }
Bestimmen Sie alle Minimalpolynome von f mit Hilfe der Methode
von Petrick. Sie können davon ausgehen, dass alls Primimplikanten
die gleichen Kosten haben.

ON(f) = {(1000),(1010),(1011),(1100),(1101),(1111) }

ON-Menge
PI’s 1000 1010 1011 1100 1101 1111
x1[`x]2[`x]4 1 1 0 0 0 0
x1[`x]3[`x]4 1 0 0 1 0 0
x1[`x]2[`x]3 0 1 1 0 0 0
x1x2[`x]3 0 0 0 1 1 0
x1 x2 x4 0 0 0 0 1 1
x1x3x4 0 0 1 0 0 1

Aufgabe 2:
Die boolesche Funktion f: B4 B sei gegeben durch
die Menge ihrer Primimplikanten P(f) mit
P(f) = { [`x]1[`x]3x4,[`x]1x2x4,x1[`x]2x4, x1x3x4, [`x]2[`x]3x4, x2x3x4 }
Bestimmen Sie alle Minimalpolynome von f mit Hilfe der Methode
von Petrick. Sie können davon ausgehen, dass alls Primimplikanten
die gleichen Kosten haben.

ON(f) = {(0001),(0101),(0111),(1001),(1011),(1111) }

ON-Menge
PI’s 0001 0101 0111 1001 1011 1111
[`x]1[`x]3x4 1 1 0 0 0 0
[`x]1x2x4 0 1 1 0 0 0
x1[`x]2x4 0 0 0 1 1 0
x1x3x4 0 0 0 0 1 1
[`x]2[`x]3x4 1 0 0 1 0 0
x2x3x4 0 0 1 0 0 1

Aufgabe 3:
Die boolesche Funktion f: B4 B sei gegeben durch
die Menge ihrer Primimplikanten P(f) mit
P(f) = {[`x]1x2x3, [`x]1x3x4,x1[`x]2x3,x1x3[`x]4,[`x]2x3x4,x2x3[`x]4}
Bestimmen Sie alle Minimalpolynome von f mit Hilfe der Methode
von Petrick. Sie können davon ausgehen, dass alls Primimplikanten
die gleichen Kosten haben.

ON(f) = {(0011),(0110),(0111),(1010),(1011),(1110) }

ON-Menge
PI’s 0011 0110 0111 1010 1011 1110
[`x]1x2x3 0 1 1 0 0 0
[`x]1x3x4 1 0 1 0 0 0
x1[`x]2x3 0 0 0 1 1 0
x1x3[`x]4 0 0 0 1 0 1
[`x]2x3x4 1 0 0 0 1 0
x2x3[`x]4 0 0 1 0 0 1

Aufgabe 4:
Die boolesche Funktion f: B4 B sei gegeben durch
die Menge ihrer Primimplikanten P(f) mit
P(f) = {[`x]2x3x4, x1[`x]2x4, x1[`x]3x4, x2[`x]3x4, [`x]1x2x4, [`x]1x3x4 }
Bestimmen Sie alle Minimalpolynome von f mit Hilfe der Methode
von Petrick. Sie können davon ausgehen, dass alls Primimplikanten
die gleichen Kosten haben.

ON(f) = {(0011),(0101),(0111),(1001),(1011),(1101) }

ON-Menge
PI’s 0011 0101 0111 1001 1011 1101
[`x]2x3x4 1 0 0 0 1 0
x1[`x]2x4 0 0 0 1 1 0
x1[`x]3x4 0 0 0 1 0 1
x2[`x]3x4 0 1 0 0 0 1
[`x]1x2x4 0 1 1 0 0 0
[`x]1x3x4 1 0 1 0 0 0

Aufgabe 5:
Die boolesche Funktion f: B4 B sei gegeben durch
die Menge ihrer Primimplikanten P(f) mit
P(f) = {x1x3[`x]4, x1x2[`x]4,x1x2[`x]3, x1[`x]2x3, x1[`x]3x4, x1[`x]2x4 }
Bestimmen Sie alle Minimalpolynome von f mit Hilfe der Methode
von Petrick. Sie können davon ausgehen, dass alls Primimplikanten
die gleichen Kosten haben.

ON(f) = {(1001),(1010),(1011),(1100),(1101),(1110) }

ON-Menge
PI’s 1001 1010 1011 1100 1101 1110
x1x3[`x]4 0 1 0 0 0 1
x1x2[`x]4 0 0 0 1 0 1
x1x2[`x]3 0 0 0 1 1 0
x1[`x]2x3 0 1 1 0 0 0
x1[`x]3x4 1 0 0 0 1 0
x1[`x]2x4 1 0 1 0 0 0

Aufgabe 6:
Die boolesche Funktion f: B4 B sei gegeben durch
die Menge ihrer Primimplikanten P(f) mit
P(f) = { x2x3[`x]4,[`x]1x2x3, x1x2[`x]4, x1x2[`x]3, x2[`x]3x4, [`x]1x2x4 }
Bestimmen Sie alle Minimalpolynome von f mit Hilfe der Methode
von Petrick. Sie können davon ausgehen, dass alls Primimplikanten
die gleichen Kosten haben.

ON(f) = {(0101),(0110),(0111),(1100),(1101),(1110) }

ON-Menge
PI’s 0101 0110 0111 1100 1101 1110
x2x3[`x]4 0 1 0 0 0 1
[`x]1x2x3 0 1 1 0 0 0
x1x2[`x]4 0 0 0 1 0 1
x1x2[`x]3 0 0 0 1 1 0
x2[`x]3x4 1 0 0 0 1 0
[`x]1x2x4 1 0 1 0 0 0

Lösungen zu Petrickmethode

Aufgabe 1:
Bei gleichen Kosten für alle PIs sind 146 und 235 minimal.
Minipoly: x1[`x]2[`x]4 + x1x3x4 + x1x2[`x]3  oder  x1[`x]3[`x]4 + x1[`x]2x3+ x1x2x4

Aufgabe 2:
Bei gleichen Kosten für alle PIs sind 245 und 136 minimal.
Minipoly: [`x]1x2x4 + [`x]2[`x]3x4+ x1x3x4  oder  [`x]1[`x]3x4 x1[`x]2x4 + x2x3x4

Aufgabe 3:
Bei gleichen Kosten für alle PIs sind 145 und 236 minimal.
Minipoly: [`x]1x2x3 + x1x3[`x]4 + [`x]2x3x4  oder  [`x]1x3x4 + x1[`x]2x3 + x2x3[`x]4

Aufgabe 4:
Bei gleichen Kosten für alle PIs sind 135 und 246 minimal.
Minipoly: [`x]2x3x4 + x1[`x]3x4 + [`x]1x2x4  oder  x1[`x]2x4 + x2[`x]3x4+ [`x]1x3x4

Aufgabe 5:
Bei gleichen Kosten für alle PIs sind 136 und 245 minimal.
Minipoly: x1x3[`x]4 + x1x2[`x]3 + x1[`x]2x4  oder  x1x2[`x]4 + x1[`x]2x3 + x1[`x]3x4

Aufgabe 6:
Bei gleichen Kosten für alle PIs sind 146 und 235 minimal.
Minipoly: x2x3[`x]4 + x1x2[`x]3 + [`x]1x2x4  oder  [`x]1x2x3 + x1x2[`x]4+ x2[`x]3x4

 

Primimplikantentafel

Typischer Einsatz um die Ergebnisse die man nach der Reduzierung mit Quine-McCluskey erhalten hat weiter zu reduzieren.

1. Reduktionsregel
Entferne aus der Primimplikantentafel PIT(f) alle wesentliche Primimplikanten und alle Minterme, die von diesen überdeckt werden. Wesentlich ist dann gegeben wenn ein Minterm nur durch einen Primimplikanten überdeckt wird.

Tabelle 1.1: Beispiel für wesentlichen Primimplikant

0001 0011 1011
[`x]1[` x]2x4 1 1 0
[`x]2[`x]3x4 1 0 0
x3x4 0 1 1

Wie man im obigen Beispiel sieht, wird der Minterm 1011 nur durch
den dritten Primimplikanten (x3x4) abgedeckt, deswegen ist er ein wesentlicher Primimplikant (wesentlich bedeutet, der ist in jedem
Fall Teil des Minimalpolymons, da ohne ihn nicht alle Minterme überdeckt werden können.)

Nach dem Streichen erhält man folgende Tafel:

Tabelle 1.2: Beispiel 2 für wesentlichen Primimplikant

0001
[`x]1[`x]2x4 1
[`x]2[`x]3x4 1

Das Minmalpolynom MP ist,
MP = x3x4 + [`x]1[`x]2x4 oder MP = x3x4 + [`x]2[`x]3x4

2. Reduktionsregel
Entferne aus der Primimplikantentafel PIT(f) alle Minterme, die einen
anderen Minterm in PIT(f) dominieren.

Spaltendominanz liegt dann vor, wenn der dominierende Minterm (Spalte) folgendes erfüllt:

 

      a)der dominierende hat mehr einser in der Spalte

 

    b)und hat in jeder Zeile in der der dominierte ein Eins hat auch eine Eins

Da die dominierte Minterm (Spalte) in jedem Fall überdeckt werden muss,
wird damit auch die dominierende überdeckt.

Tabelle 1.3: Beispiel für Spaltendominanz

0001 0011 1011
[`x]1[`x]2x4 1 1 0
[`x]2[`x]3x4 1 0 0
x3x4 0 1 1

Der Minterm 0011 dominiert den Minterm 1011. Deshalb kann
er (0011) gestrichen werden.

Nach dem streichen der dominierende Spalte erhält man:

Tabelle 1.4: Beispiel 2 für Spaltendominanz

0001 1011
[`x]1[`x]2x4 1 0
[`x]2[`x]3x4 1 0
x3x4 0 1

Wie man sieht ist der dritte Primimp. wesentlich, daher ergibt sich für
das MP = x3x4 + [`x]1[`x]2x4 oder MP = x3x4 + [`x]2[`x]3x4

3. Reduktionsregel
Entferne aus PIT(f) alle Primimplikanten, die durch einen anderen nicht teureren Primimplikanten dominiert werden.

Im Gegensatz zur 2.Regel werden hier die Primimplikanten betrachtet.
Ein Primimplikant (Zeile) dominiert einen anderen Primimplikanten, wenn er

 

      a)in jeder Spalte in der der dominierte eine Eins hat, auch eine Eins hat, und

 

    b)er insgesamt mehr Einser seiner Zeile hat

Tabelle 1.5: Beispiel für Zeilendominanz

0001 0011 1011
[`x]1[`x]2x4 1 1 0
[`x]2[`x]3x4 1 0 0
x3x4 0 1 1

Der Primimplikant [`x]1[`x]2x4 dominiert den Primimplikat [`x]2[`x]3x4, deshalb kann dieser gestrichen werden.

Nach dem streichen der dominierten Zeile erhält man:

Tabelle 1.6: Beispiel für Zeilendominanz

0001 0011 1011
[`x]1[`x]2x4 1 1 0
x3x4 0 1 1

Die übriggeblieben Primimplikanten sind beide wesentlich,
daher ist
das MP = [`x]1[`x]2x4 + x3x4

Allgemeine Hinweise:

Die Reihenfolge in der die Regeln angewandt werden, haben keinen Einfluss
auf das Ergebniss. Man findet immer ein gleiches Minimalpolymon.

Es gibt auch Tafeln die durch diese drei Regeln nicht weiter reduziert
werden können:

Tabelle 1.7: Beispiel für nicht reduzierbare Primimplikanten-Tafel

0001 0011 1011 1001
[`x]1[`x]2x4 1 1 0 0
[`x]2[`x]3x4 1 0 0 1
[`x]2x3x4 0 1 1 0
x1[`x]2x4 0 0 1 1

Fehlerhinweis:
Bei Spaltendominanz wird die dominierende Spalte gestrichen
Bei Zeilendominanz wird die dominierte Zeile gestrichen.

Diesen Post verdanken wir den Jungs von baby-lik.com mit ihrem Autobett TT Racer schwarz

Quine-McCluskey Aufgaben und Lösungen

Aufgaben zu Quine-McCluskey

Aufgabe 1:
Eine Funktion f S(B4) sei gegeben durch:

ON(f) (x1,x2,x3,x4) = { (0010), (0100), (0101), (0110), (0111),(1010) }

 

      a)Bestimmen Sie alle Primimplikanten von f mithilfe des Verfahrens

 

      von Quine-McCluskey.

 

      b)Stellen Sie die Primimplikantentafel für f auf und bestimmen Sie

 

    damit ein Minimalpolynom von f.

Aufgabe 2:
Eine Funktion f S(B4) sei gegeben durch:

ON(f) (x1,x2,x3,x4) = { (0001),(0011), (0110),(1001),(1011),(1100), (1110) }

Bestimmen Sie alle Primimplikanten von f mithilfe des Verfahrens
von Quine-McCluskey.

Aufgabe 3:
Eine Funktion f S(B4) sei gegeben durch:
ON(f) (x1,x2,x3,x4) = { (0000), (0011), (0100),(0111),(1000),
(1001), (1011), (1100), (1101), (1111) }
Bestimmen Sie alle Primimplikanten von f mithilfe des Verfahrens
von Quine-McCluskey.

Aufgabe 4:
Eine Funktion f S(B4) sei gegeben durch:
ON(f) (x1,x2,x3,x4) = { (0000),(0110),(0111),(1011),(1110),(1111)

 

      a)Bestimmen Sie alle Primimplikanten von f mithilfe des Verfahrens

 

      von Quine-McCluskey.

 

      b)Stellen Sie die Primimplikantentafel für f auf und bestimmen Sie

 

    damit ein Minimalpolynom von f.

Lösungen zu Quine-McCluskey

Aufgabe 1
a.

ON(f) (x1,x2,x3,x4) = { (0010), (0100), (0101), (0110), (0111),(1010) }

L0 = { ([`(x1)][`(x2)]x3[`(x4)]), ([`(x1)]x2[`(x3)][`(x4)]),([`(x1)]x2[`(x3)][`(x4)]),([`(x1)]x2x3[`(x4)]),([`(x1)]x2x3x4), (x1[`(x2)]x3[`(x4)]) }

L1 = {([`(x1)]x3[`(x4)]),([`(x2)]x3[`(x4)]), ([`(x1)]x2[`(x3)]),([`(x1)]x2[`(x4)]),([`(x1)]x2x4),([`(x1)]x2x3)

PI1 = {     }

L2 = { ([`(x1)]x2) ([`(x1)]x2) } = { ([`(x1)]x2) }

PI2 = { ([`(x1)]x3[`(x4)]),([`(x2)]x3[`(x4)]) }

L3 = {     }

PI3 = { ([`(x1)]x2) }

PI = PI1 PI2 PI3 = { ([`(x1)]x3[`(x4)]),([`(x2)]x3[`(x4)]), ([`(x1)]x2) }

b.

ON(f)
PI 0010 0100 0101 0110 0111 1010
[`(x1)]x2 0 1 1 1 1 0
[`(x1)]x3[`(x4)] 1 0 0 1 0 0
[`(x2)]x3[`(x4)] 1 0 0 0 0 1

Min Prim = {([`(x1)]x2),([`(x2)]x3[`(x4)]) }

Aufgabe 2

ON(f) (x1,x2,x3,x4) = { (0001),(0011), (0110),(1001),(1011),(1100), (1110) }

L0 = { ([`(x1)][`(x2)][`(x3)]x4), ([`(x1)][`(x2)]x3x4),([`(x1)]x2x3[`(x4)]),(x1[`(x2)][`(x3)]x4),(x1[`(x2)]x3x4),(x1x2[`(x3)][`(x4)]),(x1x2x3[`(x4)]) }

L1 = { ([`(x1)][`(x2)]x4),([`(x2)][`(x3)]x4),([`(x2)]x3x4),(x2x3[`(x4)]),(x1[`(x2)]x4),(x1x2[`(x4)]) }

PI1 = {     }

L2 = { ([`(x2)]x4),([`(x2)]x4) } = { ([`(x2)]x4) }

PI2 = { (x2x3[`(x4)]),(x1x2[`(x4)]) }

L3 = {     }

PI3 { ([`(x2)]x4) }

PI = PI1 PI2 PI3 = { ([`(x2)]x4),(x2x3[`(x4)]),(x1x2[`(x4)]) }

Aufgabe 3
ON(f) (x1,x2,x3,x4) = { (0000), (0011), (0100),(0111),(1000),
(1001), (1011), (1100), (1101), (1111) }

L0 = { ([`(x1)][`(x2)][`(x3)][`(x4)]), ([`(x1)][`(x2)]x3x4), ([`(x1)]x2[`(x3)][`(x4)]), (x1[`(x2)][`(x3)][`(x4)]), (x1[`(x2)][`(x3)]x4),
(x1[`(x2)]x3x4),(x1x2[`(x3)][`(x4)]),(x1x2x3[`(x4)]),(x1x2x3x4) }

L1 = { ([`(x1)][`(x3)][`(x4)]) ,([`(x2)][`(x3)][`(x4)]),([`(x1)]x3x4),([`(x2)]x3x4),(x2[`(x3)][`(x4)]),(x2x3x4),
(x1[`(x2)][`(x3)]), (x1[`(x3)][`(x4)]),(x1[`(x2)]x4), (x1[`(x3)]x4),(x1x3x4),(x1x2x3),(x1x2x4) }
PI1 = {     }

L2 = { ([`(x3)][`(x4)]), ([`(x3)][`(x4)]),(x3x4),(x3x4),(x1[`(x3)]), (x1[`(x3)]), (x1x4), (x1x4) }
L2 = {([`(x3)][`(x4)]),(x3x4),(x1[`(x3)]),(x1x4) }

PI2 = {     }

L3 = {     }

PI3 = {([`(x3)][`(x4)]),(x3x4),(x1[`(x3)]),(x1x4) } = PI

Aufgabe 4:

ON(f) = { (0000), (0110), (0111), (1011), (1110), (1111) }
a.
L0 = { ([`(x1)][`(x2)][`(x3)][`(x4)]), ([`(x1)]x2x3[`(x4)]),([`(x1)]x2x3x4),(x1[`(x2)]x3x4),(x1x2x3[`(x4)]),(x1x2x3x4) }

L1 = { ([`(x1)]x2x3), (x2x3[`(x4)]),(x2x3x4),(x1x3x4),(x1x2x3) }

PI1 = { ([`(x1)][`(x2)][`(x3)][`(x4)] ) }

L2 = { (x2x3),(x2x3) } = { (x2x3) }

PI2 = { (x1x3x4 ) }

L3 = {     }

PI3 = { (x2x3) }

PI = PI1 PI2 PI3 = { ([`(x1)][`(x2)][`(x3)][`(x4)]),(x1x3x4),(x2x3) }

b.

ON(f)
PI 0000 0110 0111 1011 1110 1111
[`(x1)][`(x2)][`(x3)][`(x4)] 1 0 0 0 0 0
x1x3x4 0 0 0 1 0 1
x2x3 0 1 1 0 1 1

Alle werden benötigt
Min Poly : x2x3 + x1x3x4 + [`(x1)][`(x2)][`(x3)][`(x4)]

Quine-McCluskey

Quine/McCluskey dient dazu die Primimplikanten zu berechnen, die Brechnung selbst ist ein sich wiederholender Algorithmus.

Es werden nur Monome (Wörter) die die gleichen Variablen enthalten
und sich ihre Anzahl der positiven Literale (Buchstaben)
um 1 unterscheidet, miteinander verglichen.

Bedingung 1
Ein Monom das die Variablen x1x2x3 enthält kann
nur mit Monomen verglichen werden, die auch x1x2x3 enthalten (Das bedeutet nicht, dass die Belegung gleich sein muß. Wenn die Variablen und die Belegung gleich ist, ist es ein und daselbe Monom) .

z.B. x1[`x]2x3 (101) kann mit [`x]1 [`x]2x3 (001)
verglichen werden, aber nicht x1x2x4

Bedingung 2

Da die Monome die gleichen Variablen enthalten müssen nach Bed. 1,
haben sie die gleiche Länge (Formell ausgedrückt, Monome
die die gleichen Variablen enthalten, besitzen die gleiche Mächtigkeit)
und diese Länge entspricht der Summe der positiven und negativen
Literale.

Es können nur Monome mit einander verglichen werden,
der Anzahl an positiven Literal um 1 unterscheidet. Anders ausgedrückt,
Monome die gleiche Anzahl an Einsen (bzw. Nullen) haben können nicht
verglichen werden, die Anzahl muß sich um genau 1 unterscheiden.

Kurzfassung: Ihre Belegung unterscheidet sich nur in einem Literal!

Beispiel:

z.B. x1[`x]2x3 (101) kann mit [`x]1 [`x]2x3
verglichen werden, aber nicht [`x]1 [`x]2[`x]3

Die Monome die nicht weiter mit anderen verglichen und reduziert werden
können, sind dann Prim.

Zu Beginn der Berechnung kann man davon ausgehen, daß Bedingung 1
erfüllt ist. Angenommen man hat folgende Funktion:

 

ON(f) (x1,x2,x3,x4) = { (0001), (0010), (0110),(1010), (1110), (0101) }

Im ersten Schritt werden die Monome nach der Anzahl der Einser die sie
enthalten sortiert (d.h. sie sind zusätzlich noch mit aufsteigendem Wert
sortiert worden).

0001
0010 (I)
0101
0110 (II)
1010
1110 (III)

2. Schritt
Die Monome der Gruppe I werden mit denen der Gruppe II verglichen,
die Monome der Gruppe II werden mit Gruppe III verglichen.

Gruppe I mit II

0001 mit 0101 001
0001 mit 0110 geht nicht (Bed. 2)
0001 mit 1010 geht nicht (Bed. 2)

0010 mit 0101 geht nicht (Bed. 2)
0010 mit 0110 010
0010 mit 1010 010

Gruppe II mit III
0101 mit 1110 geht nicht (Bed. 2)
0110 mit 1110 -110
1010 mit 1110 110

Jedes Monome konnte verglichen und reduziert werden, also
keine Prim’s dabei.

3. Schritt
Die Monome müssen jetzt nach Variablen sortiert werden.
L1(x1x3x4) = { (001), (010) , (110) }
L1(x2x3x4) = { (010), (110) }

4. Schritt
die Monome wieder nach der Anzahl der Einser sortieren, für L1(x1x3x4) und L1(x2x3x4) getrennt.

L1(x1x3x4)
001
010
110

Gruppe I‘ mit II“
0-01 mit 1-10 geht nicht (Bed. 2)
0-10 mit 1-10 -10

L1(x2x3x4)
(010)
(110)

Gruppe I‘ mit II“
-010 mit -110 -10

PI1 = { (001) }

Wieder Schritt 3 (nach Variablen sortieren)
L2(x3x4) = { (-10), (-10) }
Kein weiteres vergleich mehr möglich.
PI2 = { (-10) }

5. Schritt
Um die Primimplikanten der Funktion f zu bekommen, werden die Prim’s
die während der Rechnung gefunden wurden (PI1, PI2 ) vereinigt.
PI(f) = PI1 PI2 = { (001), (-10) }