1 PrimimplikantentafelTypischer Einsatz um die Ergebnisse die man nach der Reduzierung mit Quine-McCluskeyerhalten hat weiter zu reduzieren.1. Reduktionsregel Entferne aus der Primimplikantentafel PIT(f) alle wesentlichen Pri-mimplikanten und alle Minterme, die von diesen uberdeckt werden. Wesentlich ist danngegeben wenn ein Minterm nur durch einen Primimplikanten uberdeckt wird.

Tabelle 1: Beispiel fur wesentlichen Primimplikant0001 0011 1011

x1x2x4 1 1 0x2x3x4 1 0 0x3x4 0 1 1

Wie man im obigen Beispiel sieht, wird der Minterm 1011 nur durch den dritten Primim-plikanten (x3x4) abgedeckt, deswegen ist er ein wesentlicher Primimplikant1.Nach dem Streichen erhalt man folgende Tafel:

Tabelle 2: Beispiel 2 fur wesentlichen Primimplikant0001

x1x2x4 1x2x3x4 1

Das Minmalpolynom MP ist, MP = x3x4 + x1x2x4 oder MP = x3x4 + x2x3x42. Reduktionsregel Entferne aus der Primimplikantentafel PIT(f) alle Minterme, die einenanderen Minterm in PIT(f) dominieren.Spaltendominanz liegt dann vor, wenn der dominierende Minterm (Spalte) folgendeserfullt:

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 uberdeckt werden muß, wird damitauch die dominierende uberdeckt.

Tabelle 3: Beispiel fur Spaltendominanz0001 0011 1011

x1x2x4 1 1 0x2x3x4 1 0 0x3x4 0 1 1

Der Minterm 0011 dominiert den Minterm 1011. Deshalb kann er (0011) gestrichen wer-den.Nach dem streichen der dominierende Spalte erhalt man:

1wesentlich bedeutet, der ist in jedem Fall Teil des Minimalpolymons, da ohne ihn nicht alle Mintermeuberdeckt werden konnen.

Tabelle 4: Beispiel 2 fur Spaltendominanz0001 1011

x1x2x4 1 0x2x3x4 1 0x3x4 0 1

Wie man sieht ist der dritte Primimp. wesentlich, daher ergibt sich fur das MP = x3x4 +x1x2x4 oder MP = x3x4 + x2x3x43. Reduktionsregel Entferne aus PIT(f) alle Primimplikanten, die durch einen anderennicht 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 5: Beispiel fur Zeilendominanz0001 0011 1011

x1x2x4 1 1 0x2x3x4 1 0 0x3x4 0 1 1

Der Primimplikant x1x2x4 dominiert den Primimplikat x2x3x4, deshalb kann dieser ge-strichen werden.Nach dem streichen der dominierten Zeile erhalt man:

Tabelle 6: Beispiel fur Zeilendominanz0001 0011 1011

x1x2x4 1 1 0x3x4 0 1 1

Die ubriggeblieben Primimplikanten sind beide wesentlich,daher ist das MP = x1x2x4 + x3x4

Allgemeine Hinweise:

Die Reihenfolge in der die Regeln angewandt werden, haben keinen Einfluss auf das Er-gebniss. Man findet immer ein gleiches Minimalpolymon.Es gibt auch Tafeln die durch diese drei Regeln nicht weiter reduziert werden konnen:Fehlerhinweis:Bei Spaltendominanz wird die dominierende Spalte gestrichenBei Zeilendominanz wird die dominierte Zeile gestrichen.

Tabelle 7: Beispiel fur nicht reduzierbare PTafel0001 0011 1011 1001

x1x2x4 1 1 0 0x2x3x4 1 0 0 1x2x3x4 0 1 1 0x1x2x4 0 0 1 1

1.1 Aufgaben zu Primimplikantentafel

Aufgabe 1:Die Boolesche Funktion f sei durch folgende Primimplikantentafel beschrieben:

ON(f)PI 0000 0001 0011 1000 1001 1011 1100 1101 1110 1111x1x2 0 0 0 0 0 0 1 1 1 1x1x3 0 0 0 1 1 0 1 1 0 0x1x4 0 0 0 0 1 1 0 1 0 1x2x3 1 1 0 1 1 0 0 0 0 0x2x4 0 1 1 0 1 1 0 0 0 0

Bestimmen Sie alle Minimalpolynome fur die Funktion f.

Aufgabe 2:ON(f)

PI 0000 0010 0100 0101 0111 1000 1010 1101 1111x2x4 1 1 0 0 0 1 1 0 0x2x4 0 0 0 1 1 0 0 1 1x1x4 0 0 0 0 0 0 0 1 1x1x2x4 1 1 0 0 0 0 0 0 0x1x3x4 1 0 1 0 0 0 0 0 0x1x2x3 0 0 1 1 0 0 0 0 0

Bestimmen Sie alle Minimalpolynome fur die Funktion f.

Aufgabe 3:ON(f)

PI 0001 0010 0011 0100 0101 1000 1001 1010 1100 1101x3x4 1 0 0 0 1 0 1 0 0 1x2x3 0 0 0 1 1 0 0 0 1 1x1x3 0 0 0 0 0 1 1 0 1 1x1x2x4 1 1 0 0 0 0 0 0 0 0x1x2x3 0 1 1 0 0 0 0 0 0 0x2x3x4 0 1 0 0 0 0 0 1 0 0x1x2x4 0 0 0 0 0 1 0 1 0 0x1x2x3 0 0 0 0 0 0 0 0 1 1

Bestimmen Sie alle Minimalpolynome fur die Funktion f.

1.2 Losungen zu Primimplikantentafeln

Aufgabe 1:Die Boolesche Funktion f sei durch folgende Primimplikantentafel beschrieben:

ON(f)PI 0000 0001 0011 1000 1001 1011 1100 1101 1110 1111x1x2 0 0 0 0 0 0 1 1 1 1x1x3 0 0 0 1 1 0 1 1 0 0x1x4 0 0 0 0 1 1 0 1 0 1x2x3 1 1 0 1 1 0 0 0 0 0x2x4 0 1 1 0 1 1 0 0 0 0

Bestimmen Sie alle Minimalpolynome fur die Funktion f.

1. Reduktionsregel anwenden x1x2 ist wesentlich.ON(f)

PI 0000 0001 0011 1000 1001 1011x1x3 0 0 0 1 1 0x1x4 0 0 0 0 1 1x2x3 1 1 0 1 1 0x2x4 0 1 1 0 1 1

1. Reduktionsregel anwenden x2x3 ist wesentlich.ON(f)

PI 0011 1011x1x3 0 0x1x4 0 1x2x3 0 0x2x4 1 1

x1x3 & x2x3 fallen weg

ON(f)PI 0011 1011x1x4 0 1x2x4 1 1

3. Reduktionsregel anwenden (Zeile) x2x4 dominiert x1x4

Min Prim : {(x1x2), (x2x3), (x2x4)}min Poly : x1x2 + x2x3 + x2x4

Aufgabe 2:ON(f)

PI 0000 0010 0100 0101 0111 1000 1010 1101 1111x2x4 1 1 0 0 0 1 1 0 0x2x4 0 0 0 1 1 0 0 1 1x1x4 0 0 0 0 0 0 0 1 1x1x2x4 1 1 0 0 0 0 0 0 0x1x3x4 1 0 1 0 0 0 0 0 0x1x2x3 0 0 1 1 0 0 0 0 0

Bestimmen Sie alle Minimalpolynome fur die Funktion f.

1. Reduktionsregel anwenden x2x4 ist wesentlichON(f)

PI 0100 0101 0111 1101 1111x2x4 0 1 1 1 1x1x4 0 0 0 1 1x1x2x4 0 0 0 0 0x1x3x4 1 0 0 0 0x1x2x3 1 1 0 0 0

1. Reduktionsregel anwenden x2x4 ist wesentlichON(f)

PI 0100x1x4 0x1x2x4 0x1x3x4 1x1x2x3 1

x1x4 & x1x2x4 fallen weg

ON(f)PI 0100x1x3x4 1x1x2x3 1

Min Poly: x2x4 + x2x4 + x1x3x4 bzw. x2x4 + x2x4 + x1x2x3

Aufgabe 3:Die Boolesche Funktion f sei durch folgende Primimplikantentafel beschrieben:

ON(f)PI 0001 0010 0011 0100 0101 1000 1001 1010 1100 1101x3x4 1 0 0 0 1 0 1 0 0 1x2x3 0 0 0 1 1 0 0 0 1 1x1x3 0 0 0 0 0 1 1 0 1 1x1x2x4 1 1 0 0 0 0 0 0 0 0x1x2x3 0 1 1 0 0 0 0 0 0 0x2x3x4 0 1 0 0 0 0 0 1 0 0x1x2x4 0 0 0 0 0 1 0 1 0 0x1x2x3 0 0 0 0 0 0 0 0 1 1

Bestimmen Sie alle Minimalpolynome fur die Funktion f.

1. Reduktionsregel anwenden x2x3 ist wesentlichON(f)

PI 0001 0010 0011 1000 1001 1010x3x4 1 0 0 0 1 0x1x3 0 0 0 1 1 0x1x2x4 1 1 0 0 0 0x1x2x3 0 1 1 0 0 0x2x3x4 0 1 0 0 0 1x1x2x4 0 0 0 1 0 1x1x2x3 0 0 0 0 0 0

x1x2x3 fallt raus.1. Reduktionsregel anwenden x1x2x3 ist wesentlich

ON(f)PI 0001 1000 1001 1010x3x4 1 0 1 0x1x3 0 1 1 0x1x2x4 1 0 0 0x2x3x4 0 0 0 1x1x2x4 0 1 0 1

3. Reduktionsregel anwenden Zeile x3x4 dominiert x1x2x4

ON(f)PI 0001 1000 1001 1010x3x4 1 0 1 0x1x3 0 1 1 0x2x3x4 0 0 0 1x1x2x4 0 1 0 1

3. Reduktionsregel anwenden Zeile x1x2x4 dominiert x2x3x4

ON(f)PI 0001 1000 1001 1010x3x4 1 0 1 0x1x3 0 1 1 0x1x2x4 0 1 0 1

1. Reduktionsregel anwenden x3x4 ist wesentlichON(f)

PI 1000 1010x1x3 1 0x1x2x4 1 1

3. Reduktionsregel anwenden (Zeile) x1x2x4 dominiert x1x3.Min Poly : x3x4 + x2x3 + x1x2x3 + x1x2x4

Quelle: PrimimplikantentafelMit freundlicher Unterstutzung von: www.baby-lik.com