Disjunktiivinen normaalimuoto

Disjunktiivinen normaalimuoto ( DNF ) Boolen logiikassa on normaalimuoto , jossa Boolen kaava on muodoltaan literaalien konjunktioiden disjunktio . Mikä tahansa Boolen kaava voidaan muuntaa DNF:ksi. [1] Voit tehdä tämän käyttämällä kaksoisnegaation lakia , de Morganin lakia , distributiivisuuden lakia . Disjunktiivinen normaalimuoto on kätevä automaattiseen lauseen todistamiseen .

Esimerkkejä

Kaavat DNF:ssä :

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

Kaavat , jotka eivät ole DNF :ssä :

{\overline {(A\tai B)))

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

Mutta kaksi viimeistä kaavaa vastaavat seuraavia DNF:n kaavoja:

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

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

DNF:n rakentaminen

Algoritmi DNF:n muodostamiseksi

1) Päästä eroon kaikista kaavan sisältämistä loogisista operaatioista korvaamalla ne tärkeimmillä: konjunktiolla, disjunktiolla, negaatiolla. Tämä voidaan tehdä vastaavilla kaavoilla:

A\rightarrow B=\neg A\vee B

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

2) Korvaa koko lausekkeeseen viittaava kieltomerkki kieltomerkeillä, jotka viittaavat yksittäisiin muuttujalauseisiin kaavojen perusteella:

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

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

3) Päästä eroon kaksinkertaisista negatiivisista merkeistä.

4) Käytä tarvittaessa konjunktio- ja disjunktiooperaatioihin distributiivisuus- ja absorptiokaavojen ominaisuuksia.

Esimerkki DNF:n muodostamisesta

Pelkistetään kaava muotoon DNF $F=\neg ((X\rightarrow Y)\vee \neg (Y\rightarrow Z))$

Ilmaisemme loogisen operaation → kautta $\vee \wedge \neg$

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

Tuloksena olevassa kaavassa siirrämme negaation muuttujiin ja vähennämme kaksoisnegatiointeja:

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

Jakavuuslakia käyttämällä saamme :

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

Konjunktion idempotenssia käyttämällä saamme DNF:n:

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

k -disjunktiivinen normaalimuoto

K -disjunktiivinen normaalimuoto on disjunktiivinen normaalimuoto, jossa jokainen konjunktio sisältää tarkalleen k literaalia .

Esimerkiksi seuraava kaava on kirjoitettu 2-DNF:ssä:

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

Siirtyminen DNF:stä SDNF:ään

Jos muuttuja, esimerkiksi Z, puuttuu jostain yksinkertaisesta konjunktiosta, lisäämme lausekkeen siihen

Z\vee\neg Z=1

jonka jälkeen avaamme sulut (samaan aikaan emme kirjoita toistuvia disjunktteja, koska idempotenssilain mukaan ). Esimerkiksi: $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

Siten DNF:stä saimme SDNF:n .

Muodollinen kielioppi, joka kuvaa DNF:ää

Seuraava muodollinen kielioppi kuvaa kaikkia kaavoja, jotka on pelkistetty DNF:ksi:

jossa <termi> tarkoittaa mielivaltaista loogista muuttujaa.

Merkintäominaisuudet

On huomattava, että havainnoinnin helpottamiseksi aritmeettisen kertolasku- ja yhteenlaskumerkkejä käytetään usein konjunktion ja disjunktion nimityksinä, kun taas kertolasymboli jätetään usein pois. Tässä tapauksessa Boolen algebrakaavat näyttävät algebrallisilta polynomeilta, mikä on silmälle tutumpaa, mutta voi joskus johtaa väärinkäsityksiin.

Esimerkiksi seuraavat merkinnät ovat vastaavia:

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

Tästä syystä venäjänkielisessä kirjallisuudessa DNF:ää kutsutaan joskus "tuotteiden summaksi", joka on englanninkielisestä termistä "tuotteiden summa".

Katso myös

Muistiinpanot

↑ Pozdnyakov S.N., Rybin S.V. Diskreetti matematiikka. - S. 303.

Kirjallisuus

Yu.I. Galushkina, A.N. Maryamov: Lecture Notes on Discrete Mathematics - 2nd ed., rev. - M.: Iris-press, 2008. - 176 s. - (Korkeampi koulutus).