Disjunktiv normalform

Disjunktiv normalform ( DNF ) i boolsk logik er en normal form , hvor en boolsk formel har form af en disjunktion af konjunktioner af bogstaver . Enhver boolsk formel kan konverteres til en DNF. [1] For at gøre dette kan du bruge loven om dobbelt negation , de Morgans lov , loven om distributivitet . Den disjunktive normalform er praktisk til automatisk sætningsbevis .

Eksempler

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 ikke i DNF :

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

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

Men de sidste to formler svarer til følgende formler i DNF:

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

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

Opbygning af en DNF

Algoritme til at konstruere en DNF

1) Slip af med alle de logiske operationer, der er indeholdt i formlen, og erstat dem med de vigtigste: konjunktion, disjunktion, negation. Dette kan gøres ved hjælp af tilsvarende formler:

A\højrepil B=\neg A\vee B

A\venstrehøjrepil B=(A\kile B)\vee (\neg A\kile \neg B)

2) Erstat negationstegnet, der refererer til hele udtrykket, med negationstegn, der henviser til individuelle variable udsagn, baseret på formlerne:

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

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

3) Slip af med dobbelte negative fortegn.

4) Anvend om nødvendigt fordelings- og absorptionsformlernes egenskaber på operationerne af konjunktion og disjunktion .

Et eksempel på at konstruere en DNF

Lad os reducere formlen til DNF $F=\neg ((X\højrepil Y)\vee \neg (Y\højrepil Z))$

Vi udtrykker den logiske operation → gennem $\vee \kile \neg$

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

I den resulterende formel overfører vi negationen til variablerne og reducerer de dobbelte negationer:

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

Ved at bruge distributionsloven får vi:

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

Ved at bruge konjunktionens idempotens opnår vi en DNF:

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

k -disjunktiv normalform

En k -disjunktiv normalform er en disjunktiv normalform, hvor hver konjunktion indeholder nøjagtigt k literaler .

For eksempel er følgende formel skrevet i 2-DNF:

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

Overgang fra DNF til SDNF

Hvis en variabel, for eksempel Z, mangler i en simpel konjunktion, indsætter vi udtrykket i den

Z\vee\neg Z=1

hvorefter vi åbner parenteserne (samtidigt skriver vi ikke de gentagne disjunkte udtryk, da ifølge loven om idempotens ). For eksempel: $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

Således fik vi SDNF fra DNF .

Formel grammatik, der beskriver DNF

Følgende formelle grammatik beskriver alle formler reduceret til DNF:

hvor <term> angiver en vilkårlig boolesk variabel.

Notationsfunktioner

Det skal bemærkes, at for at lette opfattelsen, bruges symbolerne for aritmetisk multiplikation og addition ofte som en betegnelse for konjunktion og disjunktion, mens multiplikationssymbolet ofte udelades. I dette tilfælde ligner boolske algebraformler algebraiske polynomier, som er mere velkendte for øjet, men nogle gange kan føre til misforståelser.

For eksempel er følgende poster tilsvarende:

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

Af denne grund kaldes DNF i russisksproget litteratur undertiden "sum of products", som er et sporingspapir fra det engelske udtryk "sum of products".

Se også

Noter

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

Litteratur

Yu.I. Galushkina, A.N. Maryamov: Lecture Notes on Discrete Mathematics - 2. udgave, rev. - M.: Iris-press, 2008. - 176 s. - (Videregående uddannelse).