http://www.oelinger.de     Home Maria Oelinger       zurück zur Übersicht     Teil I   Teil II 2.3 Quine & McCluskey   Disjunktive Form Sei n > 6, sonst ist ja auch Karnaugh möglich DF für f: BnB, falls f =  i = 1, …, k Mi mit k > 0, wobei Mi := j = 1, …, m x ij j mit m > 0 mit x  für   B wie folgt: Faustregel: DF ist optimierte DNF vgl. Minterm   Schaltungskosten Sei eine Darstellung einer Booleschen Funktion f in Disjunktiver Form gegeben. Setze K (d) = t – 1,    falls d = x11 … x1t     (t – 1 Multiplikationen) K (d) = (k – 1) +  j = 1, …, k K (µj),    falls d = µ1 + … + µk µj ist Produkt der Form     j=1,…,li xijj     mit li  1 und x  definiert wie beim Minterm. Achtung: '–' ist in B gleich '+' Schaltungskosten für DNF Sei f in DNF. Dann ist K (fDNF) = k – 1 + (n – 1)•k = n•k – 1 Merke:     K (DNF) = n k – 1 Beispiel fDNF = x1 ¬x2 x3 x4 + x1 ¬x2 ¬x3 x4 + x1 x2 x3 x4 + ¬x1 ¬x2 ¬x3 x4 + ¬x1 ¬x2 x3 x4 fRes = ¬x2 x4 + x1 x3 x4     nach Resolution    vgl. 2.2. K (DNF) = 4 • 5 – 1 = 20 – 1 = 19   K (fRes) = K (d) = K (¬x2 x4 + x1 x3 x4) = (k – 1) + (Anzahl Mult. erster Summand) + (Anzahl Mult. zweiter Summand) = (2 – 1) + 1 + 2 = 4   Implikant µ für f: BnB, falls gilt:   µ (x) =1     =>    f (X) = 1 Schreibweise: µ  f Primimplikant Minimaler Implikant, d.h. wenn es keine echte Verkürzung gibt, die noch Implikant ist. Abk. PI Bemerkung Minterme sind Implikanten für f. Im Karnaugh-Diagramm: Rechteckige Blöcke entsprechen Implikanten. Maximale rechteckige Blöcke entsprechen Primimplikanten. Satz Sei f: BnB und d = µ1 + … + µk die Disjunktive Form von f mit minimalen Kosten. Dann sind alle µj Primimplikanten.   weiter...   zurück zur Übersicht Feel free to send me email: maria@oelinger.de
	© 2000 Maria Oelinger cand. math. Schaltungen und Boolesche Algebra (17) Letzte Änderung: 19.11.2000 address: http://www.oelinger.de/maria/schalt/schalt17.htm