Petrikova metoda

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. října 2021; kontroly vyžadují 3 úpravy .

Petrikova metoda je metoda pro získání všech minimálních DNF z tabulky hlavních implikantů . Navrhl jej v roce 1956 americký vědec Stanley Roy Petrik (1931-2006) [1] . Petrikova metoda je poměrně obtížně aplikovatelná pro velké tabulky, ale je velmi snadno implementovatelná programově.

Algoritmus

Zjednodušte tabulku primárních implikantů odstraněním nezbytných implikantů a jim odpovídajících termínů.
Označte řádky zjednodušené tabulky: atd. ${\displaystyle P_{1},P_{2},P_{3},P_{4))$
Vytvořte booleovskou funkci , která je pravdivá, když jsou pokryty všechny sloupce. sestává z CNF , ve kterém má každá konjunkce tvar , kde každá proměnná je řádek pokrývající sloupec . $P$ $P$ $(P_{i0}+P_{i1}+\cdots +P_{iN})$ ${\displaystyle P_{ij))$ $i$
Zjednodušte na minimální DNF násobením a aplikací a . $P$ $X+XY=X$ $XX=X$ $X+X=X$
Každá klauzule ve výsledku představuje řešení, tedy sadu řádků pokrývajících všechny mintermy v tabulce hlavních implikantů.
Dále pro každé řešení nalezené v kroku 5 musíte spočítat počet literálů v každém primárním implikantu.
Vyberte termín (nebo termíny) obsahující minimální počet literálů a napište výsledek.

Příklad

Existuje booleovská funkce tří proměnných, daná součtem mintermů:

$f(A,B,C)=\sum m(0,1,2,5,6,7)\,$ Tabulka hlavních implikantů z metody Quine-McCluskey :

	0	jeden	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$					✓	✓

Na základě poznámek v tabulce výše vypíšeme CNF (řádky se sečtou, jejich součty se vynásobí):

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

Pomocí vlastnosti distributivity invertujeme výraz v DNF. Pro zjednodušení výrazu použijeme také následující ekvivalence: , a . $X+XY=X$ $XX=X$ $X+X=X$