Disjunktiv normalform

Disjunktiv normalform ( DNF ) i boolesk logik är en normalform där en boolesk formel har formen av en disjunktion av konjunktioner av bokstaver . Vilken boolesk formel som helst kan omvandlas till en DNF. [1] För att göra detta kan du använda lagen om dubbel negation , de Morgans lag , lagen om distribution . Den disjunktiva normalformen är lämplig för automatisk satsbevisning .

Exempel

Formler i 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

Formler som inte finns i DNF :

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

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

Men de två sista formlerna är ekvivalenta med följande formler i DNF:

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

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

Bygga en DNF

Algoritm för att konstruera en DNF

1) Bli av med alla logiska operationer som finns i formeln, ersätt dem med de viktigaste: konjunktion, disjunktion, negation. Detta kan göras med hjälp av motsvarande formler:

A\högerpil B=\neg A\vee B

A\vänsterhögerpil B=(A\kil B)\vee (\neg A\kil \neg B)

2) Ersätt negationstecken, med hänvisning till hela uttrycket, med negationstecken, med hänvisning till individuella variabelsatser, baserat på formlerna:

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

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

3) Bli av med dubbla negativa tecken.

4) Tillämpa, om nödvändigt, egenskaperna för fördelnings- och absorptionsformler på operationerna av konjunktion och disjunktion .

Ett exempel på att konstruera en DNF

Låt oss reducera formeln till DNF $F=\neg ((X\högerpil Y)\vee \neg (Y\högerpil Z))$

Vi uttrycker den logiska operationen → genom $\vee \kil \neg$

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

I den resulterande formeln överför vi negationen till variablerna och reducerar de dubbla negationerna:

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

Med hjälp av distributionslagen får vi:

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

Genom att använda konjunktionens idempotens får vi en DNF:

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

k -disjunktiv normalform

En k -disjunktiv normalform är en disjunktiv normalform där varje konjunktion innehåller exakt k literals .

Till exempel är följande formel skriven i 2-DNF:

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

Övergång från DNF till SDNF

Om en variabel, till exempel Z, saknas i någon enkel konjunktion, infogar vi uttrycket i den

Z\vee\neg Z=1

varefter vi öppnar parenteserna (samtidigt skriver vi inte de upprepade disjunkta termerna, eftersom enligt lagen om idempotens ). Till exempel: $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

Från DNF fick vi alltså SDNF .

Formell grammatik som beskriver DNF

Följande formella grammatik beskriver alla formler reducerade till DNF:

där <term> anger en godtycklig boolesk variabel.

Notationsfunktioner

Det bör noteras att för att underlätta uppfattningen används ofta symbolerna för aritmetisk multiplikation och addition som en beteckning för konjunktion och disjunktion, medan multiplikationssymbolen ofta utelämnas. I det här fallet ser booleska algebraformler ut som algebraiska polynom, vilket är mer bekant för ögat, men ibland kan leda till missförstånd.

Till exempel är följande poster likvärdiga:

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

Av denna anledning kallas DNF i ryskspråkig litteratur ibland för "summan av produkter", vilket är ett spårningspapper från den engelska termen "summa av produkter".

Se även

Anteckningar

↑ Pozdnyakov S.N., Rybin S.V. Diskret matematik. - S. 303.

Litteratur

Yu.I. Galushkina, A.N. Maryamov: Lecture Notes on Discrete Mathematics - 2nd ed., rev. - M.: Iris-press, 2008. - 176 sid. - (Högre utbildning).