Forma normală disjunctivă

Forma normală disjunctivă ( DNF ) în logica booleană este o formă normală în care o formulă booleană are forma unei disjuncții de conjuncții de literali . Orice formulă booleană poate fi convertită într-un DNF. [1] Pentru a face acest lucru, puteți folosi legea dublei negații , legea lui de Morgan , legea distributivității . Forma normală disjunctivă este convenabilă pentru demonstrarea automată a teoremei .

Exemple

Formule în DNF :

A\lor B

(A\land B)\lor {\overline {A)}

(A\land B\land {\overline {C))}\lor ({\overline {D))\land E\land F)\lor (C\land D)\lor B

Formule care nu sunt în DNF :

{\overline {(A\lor B)))

A\lor (B\land (C\lor D))

Dar ultimele două formule sunt echivalente cu următoarele formule din DNF:

{\overline {A}}\land {\overline {B}}

A\lor (B\land C)\lor (B\land D).

Construirea unui DNF

Algoritm pentru construirea unui DNF

1) Scăpați de toate operațiile logice conținute în formulă, înlocuindu-le cu cele principale: conjuncție, disjuncție, negație. Acest lucru se poate face folosind formule echivalente:

A\rightarrow B=\neg A\vee B

A\leftrightarrow B=(A\wedge B)\vee (\neg A\wedge \neg B)

2) Înlocuiți semnul de negație, referitor la întreaga expresie, cu semne de negație, referitor la declarații de variabile individuale, pe baza formulelor:

\neg (A\vee B)=\neg A\wedge \neg B

\neg (A\wedge B)=\neg A\vee \neg B

3) Scapa de semnele negative duble.

4) Aplicați, dacă este necesar, la operațiile de conjuncție și disjuncție proprietățile formulelor de distributivitate și absorbție.

Un exemplu de construire a unui DNF

Să reducem formula la DNF $F=\neg ((X\rightarrow Y)\vee \neg (Y\rightarrow Z))$

Exprimăm operația logică → prin $\vee \wedge \neg$

F=\neg ((\neg X\vee Y)\vee \neg (\neg Y\vee Z))

În formula rezultată, transferăm negația la variabile și reducem negațiile duble:

F=(\neg \neg X\wedge \neg Y)\wedge (\neg Y\vee Z)=(X\wedge \neg Y)\wedge (\neg Y\vee Z)

Folosind legea distributivității obținem:

F=(X\wedge \neg Y\wedge \neg Y)\vee (X\wedge \neg Y\wedge Z)

Folosind idempotenta conjuncției, obținem un DNF:

F=(X\penă \neg Y)\vee (X\penă \neg Y\penă Z)

k -forma normală disjunctivă

O formă normală k -disjunctivă este o formă normală disjunctivă în care fiecare conjuncție conține exact k literale .

De exemplu, următoarea formulă este scrisă în 2-DNF:

(A\land B)\lor (\neg B\land C)\lor (B\land \neg C)

Trecerea de la DNF la SDNF

Dacă o variabilă, de exemplu, Z, lipsește într-o conjuncție simplă, inserăm expresia în ea

Z\vee\neg Z=1

după care deschidem parantezele (în același timp, nu scriem termenii disjuncți care se repetă, deoarece conform legii idempotității ). De exemplu: $Z\vee Z=Z$

X\vee \neg Y\neg Z=X(Y\vee \neg Y)(Z\vee \neg Z)\vee (X\vee \neg X)\neg Y\neg Z=

XYZ\vee X\neg YZ\vee XY\neg Z\vee X\neg Y\neg Z\vee X\neg Y\neg Z\vee \neg X\neg Y\neg Z=

=XYZ\vee X\neg YZ\vee XY\neg Z\vee X\neg Y\neg Z\vee \neg X\neg Y\neg Z

Astfel, de la DNF am primit SDNF .

Gramatică formală care descrie DNF

Următoarea gramatică formală descrie toate formulele reduse la DNF:

unde <term> denotă o variabilă booleană arbitrară.

Caracteristici de notație

Trebuie remarcat faptul că, pentru comoditatea percepției, simbolurile înmulțirii și adunării aritmetice sunt adesea folosite ca desemnare pentru conjuncție și disjuncție, în timp ce simbolul înmulțire este adesea omis. În acest caz, formulele de algebră booleană arată ca polinoame algebrice, ceea ce este mai familiar pentru ochi, dar poate duce uneori la neînțelegeri.

De exemplu, următoarele intrări sunt echivalente:

(A\land B\land {\overline {C))}\lor ({\overline {D))\land E\land F)\lor (C\land D)\lor B;

(A\cdot B\cdot {\overline {C)))\lor ({\overline {D))\cdot E\cdot F)\lor (C\cdot D)\lor B;

AB{\overline {C}}\lor {\overline {D}}EF\lor CD\lor B;

AB{\overline {C}}+{\overline {D}}EF+CD+B.

Din acest motiv, DNF în literatura de limbă rusă este uneori numit „sum of products”, care este o hârtie de calc din termenul englez „sum of products”.

Vezi și

Note

↑ Pozdnyakov S.N., Rybin S.V. Matematică discretă. - S. 303.

Literatură

Yu.I. Galușkina, A.N. Maryamov: Note de curs despre matematică discretă - ed. a II-a, rev. - M.: Iris-press, 2008. - 176 p. - (Educatie inalta).