Disjunctive normal form

A disjunctive normal form ( DNF ) in Boolean logic is a normal form in which a Boolean formula has the form of a disjunction of conjunctions of literals . Any Boolean formula can be reduced to DNF. ^[1] To do this, you can use the law of double negation , the law of de Morgan , the law of distributivity . The disjunctive normal form is convenient for the automatic proof of theorems .

Content

Examples

Formulas in DNF :

A\lor B

{\ displaystyle A \ lor B}

(A\land B)\lor \neg A

{\ displaystyle (A \ land B) \ lor \ neg A}

(A\land B\land \neg C)\lor (\neg D\land E\land F)\lor (C\land D)\lor B

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

Formulas not in DNF :

\neg (A\lor B)

{\ displaystyle \ neg (A \ lor B)}

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

{\ displaystyle A \ lor (B \ land (C \ lor D))}

But the last two formulas are equivalent to the following formulas in DNF:

\neg A\land \neg B

{\ displaystyle \ neg A \ land \ neg B}

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

{\ displaystyle A \ lor (B \ land C) \ lor (B \ land D).}

Building DNFs

DNF Construction Algorithm

1) Get rid of all logical operations contained in the formula, replacing them with the basic ones: conjunction, disjunction, negation. This can be done using equivalent formulas:

A\rightarrow B=\neg A\vee B

{\ displaystyle A \ rightarrow B = \ neg A \ vee B}

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

{\ displaystyle A \ leftrightarrow B = (A \ wedge B) \ vee (\ neg A \ wedge \ neg B)}

2) Replace the negation sign relating to the entire expression with the negation signs relating to individual variable utterances based on the formulas:

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

{\ displaystyle \ neg (A \ vee B) = \ neg A \ wedge \ neg B}

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

{\ displaystyle \ neg (A \ wedge B) = \ neg A \ vee \ neg B}

3) Get rid of double negation signs.

4) Apply, if necessary, distributive properties and absorption formulas to conjunction and disjunction operations.

DNF Construction Example

We bring to the DNF formula $F=\neg ((X\rightarrow Y)\vee \neg (Y\rightarrow Z))$ ${\ displaystyle F = \ neg ((X \ rightarrow Y) \ vee \ neg (Y \ rightarrow Z))}$

Express the logical operation → through $\vee \wedge \neg$ ${\ displaystyle \ vee \ wedge \ neg}$

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

{\ displaystyle F = \ neg ((\ neg X \ vee Y) \ vee \ neg (\ neg Y \ vee Z))}

In the resulting formula, we transfer the negation to the variables and reduce the double negations:

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

{\ displaystyle F = (\ neg \ neg X \ wedge \ neg Y) \ wedge (\ neg Y \ vee Z) = (X \ wedge \ neg Y) \ wedge (\ neg Y \ vee Z)}

Using the law of distributivity , we obtain:

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

{\ displaystyle F = (X \ wedge \ neg Y \ wedge \ neg Y) \ vee (X \ wedge \ neg Y \ wedge Z)}

Using idempotency of the conjunction, we get DNF:

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

{\ displaystyle F = (X \ wedge \ neg Y) \ vee (X \ wedge \ neg Y \ wedge Z)}

k is a disjunctive normal form

A k- disjunctive normal form is a disjunctive normal form in which each conjunction contains exactly k literals .

For example, the following formula is written in 2-DNF:

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

{\ displaystyle (A \ land B) \ lor (\ neg B \ land C) \ lor (B \ land \ neg C)}

Transition from DNF to SDNF

If a variable, for example, Z, is missing in some simple conjunction, we insert the expression

Z\vee \neg Z=1

{\ displaystyle Z \ vee \ neg Z = 1}

,

after which we open the brackets (in this case, we do not write repeated disjoint terms, since $Z\vee Z=Z$ ${\ displaystyle Z \ vee Z = Z}$ according to the law of idempotency ). For example:

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

{\ displaystyle 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=

{\ displaystyle 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

{\ displaystyle = XYZ \ vee X \ neg YZ \ vee XY \ neg Z \ vee X \ neg Y \ neg Z \ vee \ neg X \ neg Y \ neg Z}

Thus, from DNF received SDNF .

DNF Formal Grammar

The following formal grammar describes all the formulas reduced to DNF:

<conjunct> → (<conjunct> ∧ <literal>)

where <term> denotes an arbitrary Boolean variable.

Notes

↑ Pozdnyakov S.N., Rybin S.V. Discrete Math. - S. 303.

Literature

Yu.I. Galushkina, A.N. Maryamov: Lecture notes on discrete mathematics - 2nd ed., Rev. - M .: Iris-press, 2008 .-- 176 p. - (Higher education).

Links

[nf-1] Pozdnyakov S.N., Rybin S.V. Discrete Math. - S. 303.