Petrikin menetelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 28.10.2021 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Petrikin menetelmä on menetelmä, jolla saadaan kaikki minimaaliset DNF : t alkuimplikanttien taulukosta . Sen ehdotti vuonna 1956 amerikkalainen tiedemies Stanley Roy Petrik (1931-2006) [1] . Petrikin menetelmää on melko vaikea soveltaa suurille taulukoille, mutta se on erittäin helppo toteuttaa ohjelmallisesti.

Algoritmi

Yksinkertaista alkuimplikanttien taulukko poistamalla tarvittavat implikantit ja niitä vastaavat termit.
Nimeä yksinkertaistetun taulukon rivit: jne. ${\displaystyle P_{1},P_{2},P_{3},P_{4))$
Muodosta boolen funktio , joka on tosi, kun kaikki sarakkeet on peitetty. koostuu CNF :stä , jossa jokaisella konjunktiolla on muoto , jossa jokainen muuttuja on sarakkeen peittävä rivi . $P$ $P$ $(P_{i0}+P_{i1}+\cdots +P_{iN})$ ${\displaystyle P_{ij))$ $i$
Yksinkertaista minimaaliseen DNF:ään kertomalla ja käyttämällä , ja . $P$ $X+XY=X$ $XX=X$ $X+X=X$
Jokainen tuloksen lause edustaa ratkaisua, toisin sanoen rivijoukkoa, joka kattaa kaikki alkuimplikanttien taulukon mintermit.
Seuraavaksi jokaisessa vaiheessa 5 löydetyssä ratkaisussa sinun on laskettava kunkin alkuimplikantin literaalien määrä.
Valitse termi (tai termit), joka sisältää vähimmäismäärän literaaleja ja kirjoita tulos.

Esimerkki

On olemassa kolmen muuttujan Boolen funktio, jotka saadaan mintermien summalla:

$f(A,B,C)=\summa m(0,1,2,5,6,7)\,$ Taulukko Quine-McCluskey-menetelmän pääimplikanteista :

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

Yllä olevan taulukon huomautusten perusteella kirjoitamme CNF:n (rivit lisätään, niiden summat kerrotaan):

${\näyttötyyli (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)}$

Distributiivisuusominaisuuden avulla käännämme lausekkeen DNF:ssä. Käytämme myös seuraavia ekvivalensseja lausekkeen yksinkertaistamiseksi: , ja . $X+XY=X$ $XX=X$ $X+X=X$