Petrik módszere

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. október 28-án felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A Petrik- módszer egy olyan módszer, amely az összes minimális DNF -et megkapja egy elsődleges implikánsok táblázatából . Stanley Roy Petrik (1931-2006) amerikai tudós javasolta 1956-ban [1] . A Petrik-féle módszer meglehetősen nehezen alkalmazható nagy táblákra, de nagyon egyszerű programszerűen megvalósítani.

Algoritmus

Egyszerűsítse a prímimplikánsok táblázatát a szükséges implikánsok és a hozzájuk tartozó kifejezések kiiktatásával.
Jelölje ki az egyszerűsített táblázat sorait: stb. ${\displaystyle P_{1},P_{2},P_{3},P_{4))$
Hozzon létre egy logikai függvényt , amely akkor igaz, ha minden oszlop le van fedve. egy CNF -ből áll, amelyben minden kötőszó alakja , ahol minden változó egy oszlopot lefedő sor . $P$ $P$ $(P_{i0}+P_{i1}+\cdots +P_{iN})$ ${\displaystyle P_{ij))$ $én$
Egyszerűsítse a minimális DNF értékre a , és a szorzásával és alkalmazásával . $P$ $X+XY=X$ $XX=X$ $X+X=X$
Az eredmény minden tagmondata egy megoldást jelent, vagyis egy sor halmazt, amely lefedi a prímimplikánsok táblázatában szereplő összes mintermet.
Ezután minden, az 5. lépésben talált megoldáshoz meg kell számolnia az egyes prímimplikánsokban lévő literálok számát.
Válassza ki a minimális számú literált tartalmazó kifejezést (vagy kifejezéseket), és írja be az eredményt.

Példa

Három változóból áll egy Boole-függvény, amelyeket a mintermek összege ad meg:

$f(A,B,C)=\sum m(0,1,2,5,6,7)\,$ A Quine-McCluskey módszer elsődleges implikánsainak táblázata :

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

A fenti táblázat megjegyzései alapján kiírjuk a CNF-et (a sorokat összeadjuk, összegeiket megszorozzuk):

${\megjelenítési stílus (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)}$

Az eloszlási tulajdonság segítségével megfordítjuk a kifejezést a DNF-ben. A kifejezés egyszerűsítésére a következő ekvivalenciákat is használjuk: , és . $X+XY=X$ $XX=X$ $X+X=X$