Disjunktivní normální forma

Disjunktivní normální forma ( DNF ) v booleovské logice je normální forma , ve které má booleovská formule formu disjunkce konjunkcí literálů . Jakýkoli booleovský vzorec lze převést na DNF. [1] K tomu můžete použít zákon dvojí negace , de Morganův zákon , zákon distributivity . Disjunktivní normální forma je vhodná pro automatické dokazování věty .

Příklady

Vzorce v 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

Vzorce , které nejsou v DNF :

{\overline {(A\nebo B)))

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

Ale poslední dva vzorce jsou ekvivalentní následujícím vzorcům v DNF:

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

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

Budování DNF

Algoritmus pro konstrukci DNF

1) Zbavte se všech logických operací obsažených ve vzorci a nahraďte je těmi hlavními: konjunkce, disjunkce, negace. To lze provést pomocí ekvivalentních vzorců:

A\rightarrow B=\neg A\vee B

A\leftrightarrow B=(A\klín B)\vee (\neg A\klín \neg B)

2) Nahraďte znaménko negace odkazující na celý výraz za znaménko negace odkazující na jednotlivé výroky proměnných na základě vzorců:

\neg (A\vee B)=\neg A\klín \neg B

\neg (A\klín B)=\neg A\vee \neg B

3) Zbavte se dvojitých negativních znamének.

4) Aplikujte, je-li to nutné, na operace konjunkce a disjunkce vlastnosti vzorců distributivity a absorpce.

Příklad konstrukce DNF

Zredukujeme vzorec na DNF $F=\neg ((X\šipka doprava Y)\vee \neg (Y\šipka doprava Z))$

Vyjádříme logickou operaci → skrz $\vee \klín \neg$

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

Ve výsledném vzorci převedeme negaci na proměnné a snížíme dvojité negace:

F=(\neg \neg X\klín \neg Y)\klín (\neg Y\vee Z)=(X\klín \neg Y)\klín (\neg Y\vee Z)

Pomocí zákona distributivity dostaneme:

F=(X\klín \neg Y\klín \neg Y)\vee (X\klín \neg Y\klín Z)

Pomocí idempotence konjunkce získáme DNF:

F=(X\klín \neg Y)\vee (X\klín \neg Y\klín Z)

k -disjunktivní normální tvar

K -disjunktivní normální forma je disjunktivní normální forma, ve které každá spojka obsahuje přesně k literálů .

Například následující vzorec je napsán v 2-DNF:

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

Přechod z DNF na SDNF

Pokud v nějaké jednoduché spojce chybí proměnná, například Z, vložíme výraz do ní

Z\vee\neg Z=1

za kterým otevřeme závorky (zároveň nepíšeme opakující se disjunktní členy, protože podle zákona idempotence ). Například: $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

Z DNF jsme tedy dostali SDNF .

Formální gramatika popisující DNF

Následující formální gramatika popisuje všechny vzorce redukované na DNF:

kde <term> označuje libovolnou booleovskou proměnnou.

Vlastnosti zápisu

Je třeba poznamenat, že pro usnadnění vnímání jsou symboly aritmetického násobení a sčítání často používány jako označení pro konjunkci a disjunkci, zatímco symbol násobení je často vynechán. V tomto případě vzorce Booleovské algebry vypadají jako algebraické polynomy, což je oku známější, ale někdy to může vést k nedorozuměním.

Například následující položky jsou ekvivalentní:

(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.

Z tohoto důvodu se DNF v ruskojazyčné literatuře někdy nazývá „součet produktů“, což je pauzovací papír z anglického termínu „součet produktů“.

Viz také

Poznámky

↑ Pozdnyakov S.N., Rybin S.V. Diskrétní matematika. - S. 303.

Literatura

Yu.I. Galushkina, A.N. Maryamov: Poznámky k přednáškám o diskrétní matematice - 2. vyd., rev. - M.: Iris-press, 2008. - 176 s. - (Vysoké vzdělání).