Petriks metode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 28. oktober 2021; checks kræver 3 redigeringer .

Petriks metode er en metode til at opnå alle minimale DNF'er fra en tabel med primære implikanter . Det blev foreslået i 1956 af den amerikanske videnskabsmand Stanley Roy Petrik (1931-2006) [1] . Petriks metode er ret svær at anvende til store tabeller, men den er meget nem at implementere programmatisk.

Algoritme

Forenkle tabellen over primære implikanter ved at eliminere de nødvendige implikanter og deres tilsvarende udtryk.
Udpeg rækkerne i den forenklede tabel: osv. ${\displaystyle P_{1},P_{2},P_{3},P_{4))$
Dann en boolesk funktion , der er sand, når alle kolonner er dækket. består af en CNF , hvor hvert konjunkt har formen , hvor hver variabel er en række, der dækker en kolonne . $P$ $P$ $(P_{i0}+P_{i1}+\cdots +P_{iN})$ ${\displaystyle P_{ij))$ $jeg$
Forenkle til minimal DNF ved at multiplicere og anvende og . $P$ $X+XY=X$ $XX=X$ $X+X=X$
Hver klausul i resultatet repræsenterer en løsning, det vil sige et sæt rækker, der dækker alle minterms i tabellen over primære implikanter.
Dernæst skal du for hver løsning fundet i trin 5 tælle antallet af bogstaver i hver prime implikant.
Vælg et udtryk (eller udtryk), der indeholder det mindste antal bogstaver, og skriv resultatet.

Eksempel

Der er en boolsk funktion af tre variable, givet ved summen af minterms:

$f(A,B,C)=\sum m(0,1,2,5,6,7)\,$ Tabel over primære implikanter fra Quine-McCluskey-metoden :

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

Baseret på noterne i tabellen ovenfor skriver vi CNF (rækker tilføjes, deres summer ganges):

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

Ved at bruge fordelingsegenskaben inverterer vi udtrykket i DNF. Vi vil også bruge følgende ækvivalenser til at forenkle udtrykket: , og . $X+XY=X$ $XX=X$ $X+X=X$