Metoda Quine

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 7 februarie 2020; verificările necesită 6 modificări .

Metoda lui Quine este o modalitate de a reprezenta o funcție în DNF sau CNF cu un număr minim de membri și un set minim de variabile. [1] [2] [3]
Conversia funcției poate fi împărțită în doi pași:

în prima etapă se realizează trecerea de la forma canonică ( KDNF sau KKNF ) la așa-numita formă prescurtată ;
la a doua etapă - trecerea de la forma prescurtată la forma minimă .

Prima etapă (obținerea unei forme prescurtate)

Să ne imaginăm că funcția dată este reprezentată în SDNF . Pentru a implementa prima etapă, transformarea trece prin două etape: $f$

Operatie de lipire ;
operațiune de preluare .

Operația de lipire se reduce la găsirea de perechi de termeni corespunzători formei sau , și transformarea acestora în următoarele expresii: . Rezultatele lipirii joacă acum rolul unor termeni suplimentari. Este necesar să găsiți toate perechile posibile de termeni (fiecare termen cu fiecare). $w \cdot x$ $w \cdot \overline{x}$ $w \cdot x \lor w \cdot \overline{x} = w \cdot (x \lor \overline{x}) = w$ $w$

Apoi se efectuează operația de absorbție . Se bazează pe egalitate (termenul absoarbe expresia ). Ca urmare a acestei acțiuni, toți membrii absorbiți de alte variabile, ale căror rezultate sunt obținute în operația de lipire , sunt șterse din expresia logică . Ambele operații ale primei etape pot fi efectuate atâta timp cât se poate face. Aplicarea acestor operații este prezentată în tabel: $w \lor w \cdot z = w \cdot (1 \lor z) = w$ $w$ $w\cdotz$

$x_{1}$	$x_{2}$	$x_{3}$	$f(x_{1},x_{2},x_{3})$
0	0	0	0
0	0	unu	0
0	unu	0	unu
0	unu	unu	0
unu	0	0	unu
unu	0	unu	unu
unu	unu	0	unu
unu	unu	unu	unu

SDNF arată astfel:

f(x_1, x_2, x_3) = \overline{x_1} \cdot x_2 \cdot \overline{x_3} \lor x_1 \cdot \overline{x_2} \cdot \overline{x_3} \lor x_1 \cdot \overline{x_2 } \cdot x_3 \lor x_1 \cdot x_2 \cdot \overline{x_3} \lor x_1 \cdot x_2 \cdot x_3

Rezultatul operației de lipire este necesar pentru a transforma funcția în a doua etapă (absorbție)

f(x_1, x_2, x_3) = \cancel{\overline{x_1} \cdot x_2 \cdot \overline{x_3}} \vee \cancel{x_1 \cdot \overline{x_2} \cdot \overline{x_3}} \ vee \cancel{x_1 \cdot \overline{x_2} \cdot x_3} \vee \cancel{x_1 \cdot x_2 \cdot \overline{x_3}} \vee \cancel{x_1 \cdot x_2 \cdot x_3} = x_2 \cdot \overline{x_3} \vee x_1 \cdot \overline{x_2} \vee x_1 \cdot \overline{x_3} \vee x_1 \cdot x_3 \vee x_1 \cdot x_2

Membrii rezultatului lipirii sunt

x_2 \cdot \overline{x_3} \vee x_1 \cdot \overline{x_2} \vee x_1 \cdot \overline{x_3} \vee x_1 \cdot x_3 \vee x_1 \cdot x_2

Membrul absoarbe acei membri ai expresiei originale care conțin , adică primul și al patrulea. Acești membri sunt șterși. Termenul absoarbe al doilea și al treilea, iar termenul absoarbe al cincilea termen al expresiei originale. $x_2 \cdot \overline{x_3}$ $x_2 \cdot \overline{x_3}$ $x_1 \cdot \overline{x_2}$ $x_1\cdot x_3$

Repetând ambele operații rezultă următoarea expresie:

f(x_1, x_2, x_3) = x_2 \cdot \overline{x_3} \vee \cancel{x_1 \cdot \overline{x_2}} \vee \cancel{x_1 \cdot \overline{x_3}} \vee \cancel{ x_1 \cdot x_3} \vee \cancel{x_1 \cdot x_2} \vee x_1

Aici, o pereche de termeni și sunt lipiți împreună (lipirea unei perechi de termeni și duce la același rezultat), rezultatul lipirii absoarbe cei 2-, 3-, 4-, 5-lea termeni ai expresiei. Operațiunile ulterioare de lipire și absorbție se dovedesc a fi imposibile, o formă prescurtată a expresiei funcției date (în acest caz, coincide cu forma minimă) $x_1 \cdot \overline{x_2}$ $x_1\cdot x_2$ $x_1 \cdot \overline{x_3}$ $x_1\cdot x_3$ $x_{1}$

f(x_1, x_2, x_3) = x_2 \cdot \overline{x_3} \lor x_1

Termenii scurtați (în cazul nostru, acesta este și ) sunt numiți implicanți simpli ai funcției. Ca rezultat, am obținut cea mai simplă expresie în comparație cu versiunea inițială - SDNF . Schema bloc a unui astfel de element este prezentată în figura din dreapta. $x_2 \cdot \overline{x_3}$ $x_{1}$

A doua etapă (tabulară) (obținerea formei minime)

Ca și în prima etapă, egalitatea rezultată poate conține termeni a căror eliminare nu va afecta în niciun fel rezultatul final. Următoarea etapă de minimizare este eliminarea unor astfel de variabile. Tabelul de mai jos conține valorile de adevăr ale funcției. Potrivit acestuia, următorul SDNF va fi colectat .

$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$f(x_{1},x_{2},x_{3},x_{4})$
0	0	0	0	unu
0	0	0	unu	unu
0	0	unu	0	unu
0	0	unu	unu	0
0	unu	0	0	0
0	unu	0	unu	0
0	unu	unu	0	unu
0	unu	unu	unu	0
unu	0	0	0	0
unu	0	0	unu	0
unu	0	unu	0	0
unu	0	unu	unu	0
unu	unu	0	0	0
unu	unu	0	unu	0
unu	unu	unu	0	unu
unu	unu	unu	unu	unu

SDNF compilat din acest tabel arată astfel:

f(x_1, x_2, x_3, x_4) = \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot \overline{x_4} \vee \overline{x_1} \cdot \overline{x_2 } \cdot \overline{x_3} \cdot{x_4} \vee \overline{x_1} \cdot \overline{x_2} \cdot{x_3} \cdot \overline{x_4} \vee \overline{x_1} \cdot x_2 \ cdot x_3 \cdot \overline{x_4} \vee x_1 \cdot x_2 \cdot x_3 \cdot \overline{x_4} \vee x_1 \cdot x_2 \cdot x_3 \cdot x_4

\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \vee \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4} \vee \overline{x_1} \cdot x_3 \cdot \overline{x_4} \vee x_2 \cdot x_3 \cdot \overline{x_4} \vee x_1 \cdot x_2 \cdot x_3

Termenii acestei expresii sunt implicanti simpli ai expresiei. Trecerea de la forma redusă la minimă se realizează folosind matricea implicantă .

Matrice implicanta

Membrii SDNF ai unei anumite funcții se potrivesc în coloane și în rânduri - implicanți simpli, adică membri ai unei forme abreviate. Coloanele de termeni PDNF sunt marcate , care sunt absorbite de implicanții primi individuali. În tabelul următor, implicantul simplu absoarbe termenii și (crucile sunt plasate în prima și a doua coloană). ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$ $\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot \overline{x_4}$ $\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot x_4$

Implicant simplu	$\overline{x_1} \cdot \overline{x_2} \cdot\overline{x_3} \cdot \overline{x_4}$	$\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot x_4$	$\overline{x_1} \cdot \overline{x_2} \cdot x_3 \cdot \overline{x_4}$	$\overline{x_1} \cdot x_2 \cdot x_3 \cdot \overline{x_4}$	$x_1 \cdot x_2 \cdot x_3 \cdot \overline{x_4}$	$x_1 \cdot x_2 \cdot x_3 \cdot x_4$
${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$	$\times$	$\times$
$\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$	$\times$		$\times$
$\overline{x_1} \cdot x_3 \cdot \overline{x_4}$			$\times$	$\times$
$x_2 \cdot x_3 \cdot \overline{x_4}$				$\times$	$\times$
$x_1 \cdot x_2 \cdot x_3$					$\times$	$\times$

Al doilea implicant absoarbe primul și al treilea membru al SDNF (indicat prin cruci), etc. Implicanții care nu sunt supuși excluderii formează miezul . Astfel de implicanți sunt determinați de matricea de mai sus. Pentru fiecare dintre ele există cel puțin o coloană care este acoperită doar de acest implicant.

În exemplul nostru, implicanții și (se suprapun coloanei a doua și a șasea) formează nucleul. Este imposibil să se excludă simultan din forma redusă a tuturor implicanților care nu sunt incluși în nucleu, întrucât excluderea unuia dintre implicanți îl poate transforma pe celălalt într-un membru inutil. Pentru a obține forma minimă, este suficient să alegeți dintre implicanții neincluși în nucleu, un astfel de număr minim dintre ei cu un număr minim de litere în fiecare dintre acești implicanți, ceea ce va asigura suprapunerea tuturor coloanelor neacoperite de membri ai nucleului. În exemplul luat în considerare, este necesar să se acopere a treia și a patra coloană a matricei cu implicanți neincluși în nucleu. Acest lucru poate fi realizat în diferite moduri, dar deoarece este necesar să se aleagă numărul minim de implicanți, este evident că implicantul ar trebui să fie ales pentru a se suprapune acestor coloane . ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$ $x_1 \cdot x_2 \cdot x_3$
$\overline{x_1} \cdot x_3 \cdot \overline{x_4}$

Forma normală disjunctivă minimă (MDNF) a unei funcții date este:

f(x_1, x_2, x_3, x_4) = \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \vee x_1 \cdot x_2 \cdot x_3 \vee \overline{x_1} \cdot x_3 \ cdot\overline{x_4}

(A)

Diagrama bloc corespunzătoare acestei expresii este prezentată în figura din stânga. Trecerea de la schema redusă la MDNF a fost realizată prin eliminarea termenilor suplimentari - implicant și . Să arătăm admisibilitatea unei astfel de excluderi a membrilor dintr-o expresie logică. $\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$ $x_2 \cdot x_3 \cdot \overline{x_4}$

Implicanții și devin egali cu log. 1 , respectiv pentru următoarele seturi de valori ale argumentelor: , , și , , . $\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$ $x_2 \cdot x_3 \cdot \overline{x_4}$ $x_{1}=0$ $x_{2}=0$ $x_4 = 0$ $x_{2}=1$ $x_{3}=1$ $x_4 = 0$

Rolul acestor implicanți în exprimarea formei prescurtate a funcției este doar acela de a atribui funcției valoarea 1 pe seturile date de valori argument.Totuși, cu aceste mulțimi, funcția este egală cu 1 din cauza celorlalți implicanți. a expresiei. Într-adevăr, înlocuind setul de valori indicat mai sus în formula (a) , obținem: $f(x_{1},x_{2},x_{3},x_{4})$

la , , $x_{1}=0$ $x_{2}=0$ $x_4 = 0$

$f(0, 0, x_3, 0) = 1 \cdot 1 \cdot \overline{x_3} \vee 0 \cdot 0 \cdot x_3 \vee 1 \cdot x_3 \cdot 1 = \overline{x_3} \vee x_3 = unu$ ;

la , , $x_{2}=1$ $x_{3}=1$ $x_4 = 0$

$f(x_1, 1, 1, 0) = \overline{x_1} \cdot 0 \cdot 0 \vee x_1 \cdot 1 \cdot 1 \vee \overline{x_1} \cdot 1 \cdot 1 = x_1 \vee \overline {x_1} = 1$ ;

Folosind metoda pentru a obține CNF minim

Pentru a obține forma normală conjunctivă minimă (MCNF) folosind metoda lui Quine, sunt introduse următoarele criterii:

pentru minimizare, luăm funcțiile nu SDNF , ci SKNF ;
perechile de termeni de lipit sunt modificate în: sau ; $w\vee x$ $w\vee\overline{x}$
Regula de absorbție arată astfel:

$z \cdot (z \vee y) = z \vee z \cdot y = z \cdot (1 \vee y) = z$

Vezi și

Note

↑ Scurtă descriere a metodei Quine Arhivat 20 februarie 2009 la Wayback Machine www.ptca.narod.ru
↑ Prelegere: Minimizarea FAL Arhivat 14 aprilie 2009 la Wayback Machine www.works.tarefer.ru
↑ Un exemplu de minimizare a unei funcții de comutare prin metoda Quine Arhivat 17 aprilie 2010 la Wayback Machine matri-tri-ca.narod.ru

$x_{1}$	$x_{2}$	$x_{3}$	$f(x_{1},x_{2},x_{3})$
0	0	0	0
0	0	unu	0
0	unu	0	unu
0	unu	unu	0
unu	0	0	unu
unu	0	unu	unu
unu	unu	0	unu
unu	unu	unu	unu

$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$f(x_{1},x_{2},x_{3},x_{4})$
0	0	0	0	unu
0	0	0	unu	unu
0	0	unu	0	unu
0	0	unu	unu	0
0	unu	0	0	0
0	unu	0	unu	0
0	unu	unu	0	unu
0	unu	unu	unu	0
unu	0	0	0	0
unu	0	0	unu	0
unu	0	unu	0	0
unu	0	unu	unu	0
unu	unu	0	0	0
unu	unu	0	unu	0
unu	unu	unu	0	unu
unu	unu	unu	unu	unu

$x_{1}$	$x_{2}$	$x_{3}$	$f(x_{1},x_{2},x_{3})$
0	0	0	0
0	0	unu	0
0	unu	0	unu
0	unu	unu	0
unu	0	0	unu
unu	0	unu	unu
unu	unu	0	unu
unu	unu	unu	unu

$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$f(x_{1},x_{2},x_{3},x_{4})$
0	0	0	0	unu
0	0	0	unu	unu
0	0	unu	0	unu
0	0	unu	unu	0
0	unu	0	0	0
0	unu	0	unu	0
0	unu	unu	0	unu
0	unu	unu	unu	0
unu	0	0	0	0
unu	0	0	unu	0
unu	0	unu	0	0
unu	0	unu	unu	0
unu	unu	0	0	0
unu	unu	0	unu	0
unu	unu	unu	0	unu
unu	unu	unu	unu	unu

$x_{1}$	$x_{2}$	$x_{3}$	$f(x_{1},x_{2},x_{3})$
0	0	0	0
0	0	unu	0
0	unu	0	unu
0	unu	unu	0
unu	0	0	unu
unu	0	unu	unu
unu	unu	0	unu
unu	unu	unu	unu

$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$f(x_{1},x_{2},x_{3},x_{4})$
0	0	0	0	unu
0	0	0	unu	unu
0	0	unu	0	unu
0	0	unu	unu	0
0	unu	0	0	0
0	unu	0	unu	0
0	unu	unu	0	unu
0	unu	unu	unu	0
unu	0	0	0	0
unu	0	0	unu	0
unu	0	unu	0	0
unu	0	unu	unu	0
unu	unu	0	0	0
unu	unu	0	unu	0
unu	unu	unu	0	unu
unu	unu	unu	unu	unu