Forma normală disjunctivă perfectă

Forma normală disjunctivă perfectă (PDNF) este una dintre formele de reprezentare a unei funcții a algebrei logicii (funcția booleană) sub forma unei expresii logice. Este un caz special de DNF care îndeplinește următoarele trei condiții [1] :

nu are termeni identici (conjuncții elementare);
nu există variabile care se repetă în fiecare termen;
fiecare termen conține toate variabilele de care depinde funcția booleană (fiecare variabilă poate fi inclusă în termen fie sub formă directă, fie inversă).

Orice formulă booleană care nu este identic falsă poate fi redusă la SDNF, și într-un mod unic, adică pentru orice funcție satisfăcătoare a algebrei logice, există propriul SDNF, și singurul [2] .

Scurtă teorie

DNF este „suma produselor”, iar operația AND (conjuncția) acționează ca operație de „înmulțire”, iar operația SAU (disjuncție) acționează ca operație de „adunare”. Factorii sunt variabile variabile și pot fi incluși în produs atât sub formă directă, cât și inversă.

Mai jos este un exemplu de DNF:

$F(A,B,C,D,E)={\bar {A}}B+A{\bar {B}}E+B{\bar {C}}D.$

În general, un DNF poate conține termeni care se repetă și fiecare termen poate conține factori care se repetă, de exemplu:

$F(A,B,C,D,E)={\bar {A}}B{\bar {B}}+A{\bar {B}}EA+B{\bar {C}} D+B{\bar {C}}D.$

Din punct de vedere matematic, o astfel de clonare este lipsită de sens, deoarece în algebra booleană, înmulțirea oricărei expresii prin ea însăși și adăugarea expresiei la sine nu schimbă rezultatul ( ), ci adăugarea unei expresii cu propriul invers și înmulțirea cu propria sa inversare dă constante ( ). În ultima expresie, puteți elimina termenii și factorii repeți, după cum urmează: $x+x=x;x\cdot x=x$ $x+{\bar {x}}=1;x\cdot {\bar {x}}=0$

$F(A,B,C,D,E)={\bar {A}}B{\bar {B}}+A{\bar {B}}EA+B{\bar {C}} D+B{\bar {C}}D={\bar {A}}\cdot (B{\bar {B)))+(AA)\cdot {\bar {B}}E+B{\bar {C}}D={\bar {A}}\cdot 0+A{\bar {B}}E+B{\bar {C}}D=A{\bar {B}}E+B{\ bara{C}}D.$

Din acest motiv, DNF-urile cu termeni și factori repeți sunt utilizate de obicei doar în scopuri auxiliare, de exemplu, în transformarea analitică a expresiilor.

SDNF este forma canonică de reprezentare a unei funcții booleene ca DNF, în care repetările termenilor și factorilor sunt interzise. În plus, fiecare termen trebuie să conțină toate variabilele (în formă directă sau inversă).

Mai jos este un exemplu de SDNF:

$F(A,B,C,D,E)={\bar {A}}BCDE+A{\bar {B}}C{\bar {D}}E+AB{\bar {C} }D{\bar{E}}.$

Sensul SDNF este că

pentru fiecare funcție specifică, SDNF-ul său este unic și lipsit de ambiguitate;
SDNF are o corespondență unu-la-unu cu tabelul de adevăr al unei funcții. Fiecare termen din SDNF corespunde unui rând din tabelul de adevăr, unde funcția este egală cu unul. Astfel, numărul de termeni din SDNF este egal cu numărul de valori unitare pe care o funcție booleană le ia în domeniul său de definire;
SDNF este obținut elementar din tabelul de adevăr al funcției;
SDNF este convenabil ca expresie de bază pentru minimizarea unei funcții; este deosebit de ușor să găsiți termeni potriviți pentru „lipire” în ea.

Exemplu de găsire a SDNF

Pentru a obține SDNF-ul unei funcții, este necesar să compilați tabelul de adevăr al acesteia . De exemplu, luați unul dintre tabelele de adevăr:

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

În celulele rezultatului sunt marcate doar acele combinații care aduc expresia logică la starea unu. În plus, sunt luate în considerare valorile variabilelor, la care funcția este egală cu 1. Dacă valoarea unei variabile este egală cu 0, atunci se scrie cu inversare. Dacă valoarea variabilei este 1, atunci nicio inversare. $f(x_{1},x_{2},x_{3})$

Prima linie conține 1 în câmpul specificat. Sunt notate valorile tuturor celor trei variabile, acestea sunt:

$x_{1}=0$
$x_{2}=0$
$x_{3}=0$

Valorile zero - aici toate variabilele sunt reprezentate prin zerouri - sunt scrise în expresia finală prin inversul acestei variabile. Primul membru al SDNF al funcției luate în considerare arată astfel: ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$

Variabile ale celui de-al doilea membru:

$x_{1}=0$
$x_{2}=0$
$x_{3}=1$

$x_{3}$ în acest caz vor fi reprezentate fără inversare: ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot x_{3}$

Astfel, toate celulele sunt analizate . DNF perfect al acestei funcții va fi disjuncția tuturor termenilor rezultați ( conjuncții elementare ). $f(x_{1},x_{2},x_{3})$

DNF perfect al acestei funcții este:

$f(x_{1},x_{2},x_{3})=({\overline {x_{1)}}\land {\overline {x_{2})}\land {\overline { x_{3}}})\vee ({\overline {x_{1}}}\land {\overline {x_{2}}}\land x_{3})\vee ({\overline {x_{1} }}\land x_{2}\land {\overline {x_{3}}})\vee (x_{1}\land x_{2}\land {\overline {x_{3}}})$

Vezi și

Note

↑ Vinogradova M.S., Tkachev S.B. Funcții booleene. - M . : Editura MSTU im. N.E. Bauman, 2007. - 32 p.
↑ Logica matematică . - Perm: Editura PSTU, 1998. - 17 p. Arhivat pe 9 aprilie 2016 la Wayback Machine

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

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

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