Petriks metod

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 oktober 2021; kontroller kräver 3 redigeringar .

Petriks metod är en metod för att erhålla alla minimala DNF från en tabell med primära implikanter . Det föreslogs 1956 av den amerikanske vetenskapsmannen Stanley Roy Petrik (1931-2006) [1] . Petriks metod är ganska svår att tillämpa för stora tabeller, men den är väldigt enkel att implementera programmatiskt.

Algoritm

Förenkla tabellen över främsta implikanter genom att eliminera nödvändiga implikanter och deras motsvarande termer.
Ange raderna i den förenklade tabellen: , etc. ${\displaystyle P_{1},P_{2},P_{3},P_{4))$
Bilda en boolesk funktion som är sann när alla kolumner är täckta. består av en CNF där varje konjunkt har formen , där varje variabel är en rad som täcker en kolumn . $P$ $P$ $(P_{i0}+P_{i1}+\cdots +P_{iN})$ ${\displaystyle P_{ij))$ $i$
Förenkla till minimal DNF genom att multiplicera och tillämpa och . $P$ $X+XY=X$ $XX=X$ $X+X=X$
Varje sats i resultatet representerar en lösning, det vill säga en uppsättning rader som täcker alla minterms i tabellen över primära implikanter.
Därefter, för varje lösning som finns i steg 5, måste du räkna antalet bokstaver i varje prime implikant.
Välj en term (eller termer) som innehåller det minsta antalet bokstaver och skriv resultatet.

Exempel

Det finns en boolesk funktion av tre variabler, som ges av summan av minterms:

$f(A,B,C)=\summa m(0,1,2,5,6,7)\,$ Tabell över främsta implikanter från Quine-McCluskey-metoden :

	0	ett	2	5	6	7
K ( ) ${\bar {a}}{\bar {b}}$	✓	✓
L ( ) ${\bar {a}}{\bar {c}}$	✓		✓
M ( ) ${\bar {b}}c$		✓		✓
N ( ) $b{\bar {c))$			✓		✓
P ( ) $ac$				✓		✓
Q ( ) $ab$					✓	✓

Baserat på anteckningarna i tabellen ovan skriver vi ut CNF (rader läggs till, deras summor multipliceras):

$(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)$

Med hjälp av fördelningsegenskapen inverterar vi uttrycket i DNF. Vi kommer också att använda följande ekvivalenser för att förenkla uttrycket: , och . $X+XY=X$ $XX=X$ $X+X=X$