Diszjunktív normál forma

A diszjunktív normálforma ( DNF ) a logikai logikában egy olyan normálforma , amelyben a Boole-képlet literálok kötőszóinak diszjunkciója . Bármely Boole-képlet átalakítható DNF-vé. [1] Ehhez használhatja a kettős tagadás törvényét , de Morgan törvényét , az eloszlás törvényét . A diszjunktív normálalak alkalmas az automatikus tételbizonyításra .

Példák

Képletek a DNF-ben :

A\vagy 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

A DNF-ben nem szereplő képletek :

{\overline {(A\vagy B)))

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

De az utolsó két képlet egyenértékű a következő képletekkel a DNF-ben:

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

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

DNF építése

Algoritmus egy DNF létrehozásához

1) Szabaduljon meg a képletben szereplő összes logikai művelettől, és cserélje le őket a főbbekre: konjunkció, diszjunkció, tagadás. Ezt egyenértékű képletekkel lehet megtenni:

A\jobbra nyíl B=\neg A\vee B

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

2) Cserélje ki a teljes kifejezésre utaló tagadójelet tagadójelekre, amelyek az egyes változók állításaira vonatkoznak, a képletek alapján:

\neg (A\vee B)=\neg A\ék \neg B

\neg (A\ék B)=\neg A\vee \neg B

3) Szabadulj meg a kettős negatív előjelektől.

4) Szükség esetén alkalmazza a konjunkció és a diszjunkció műveleteire az eloszlási és abszorpciós képletek tulajdonságait.

Példa DNF létrehozására

Csökkentsük a képletet DNF-re $F=\neg ((X\jobbra Y)\vee \neg (Y\jobbra Z))$

A logikai műveletet → keresztül fejezzük ki $\vee \wedge \neg$

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

A kapott képletben a tagadást átvisszük a változókra, és csökkentjük a kettős tagadásokat:

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

Az eloszlási törvény segítségével a következőket kapjuk:

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

A kötőszó idempotenciáját felhasználva DNF-et kapunk:

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

k -diszjunktív normálforma

A k -diszjunktív normálforma olyan diszjunktív normálforma, amelyben minden kötőszó pontosan k literált tartalmaz .

Például a következő képlet 2-DNF-ben van írva:

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

Átállás DNF-ről SDNF-re

Ha valamilyen egyszerű kötőszóból hiányzik egy változó, például a Z, akkor a kifejezést beillesztjük abba

Z\vee\neg Z=1

ami után kinyitjuk a zárójeleket (ugyanakkor nem írjuk az ismétlődő diszjunkt tagokat, hiszen az idempotencia törvénye szerint ). Például: $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

Így a DNF-ből SDNF -t kaptunk .

A DNF-et leíró formális nyelvtan

A következő formális nyelvtan leírja az összes DNF-re redukált képletet:

ahol a <term> tetszőleges logikai változót jelöl.

Jelölés jellemzői

Meg kell jegyezni, hogy az érzékelés megkönnyítése érdekében az aritmetikai szorzás és összeadás szimbólumait gyakran használják kötő- és diszjunkció jelölésére, míg a szorzás szimbólumát gyakran elhagyják. Ebben az esetben a Boole-algebrai képletek algebrai polinomoknak tűnnek, ami ismerősebb a szem számára, de néha félreértésekhez vezethet.

Például a következő bejegyzések egyenértékűek:

(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\vagy CD\lor B;

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

Emiatt a DNF-et az orosz nyelvű irodalomban néha "termékek összegének" nevezik, amely az angol "sum of products" kifejezésből származó pauszpapír.

Lásd még

Jegyzetek

↑ Pozdnyakov S.N., Rybin S.V. Diszkrét matematika. - S. 303.

Irodalom

Yu.I. Galushkina, A.N. Maryamov: Lecture Notes on Discrete Mathematics - 2. ed., rev. - M.: Iris-press, 2008. - 176 p. - (Felsőoktatás).