Konjunktiivinen normaalimuoto

Konjunktiivinen normaalimuoto ( CNF ) Boolen logiikassa on normaalimuoto , jossa Boolen kaava on muodoltaan literaalien disjunktioiden konjunktio . Konjunktiivinen normaalimuoto on kätevä automaattiseen lauseen todistamiseen . Mikä tahansa Boolen kaava voidaan muuntaa CNF:ksi. [1] Tähän voit käyttää: kaksoisnegaation lakia , de Morganin lakia , distributiivisuutta .

Esimerkkejä ja vastaesimerkkejä

Kaavat CNF:ssä :

\neg A\kiila (B\vee C),

(A\vee B)\kiila (\neg B\vee C\vee \neg D)\kiila (D\vee \neg E),

A\kiila B.

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

\neg (B\vee C),

(A\kiila B)\vee C,

A\kiila (B\vee (D\kiila E)).

Mutta nämä 3 kaavaa eivät vastaa CNF:n seuraavia kaavoja:

\neg B\kiila \neg C,

(A\vee C)\kiila (B\vee C),

A\kiila (B\vee D)\kiila (B\vee E).

CNF:n rakentaminen

Algoritmi CNF:n rakentamiseen

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=(\neg A\vee B)\kiila (A\vee \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 CNF:n rakentamisesta

Pelkistetään kaava muotoon CNF

F=(X\nuoli oikealle Y)\kiila ((\neg Y\oikeanuoli Z)\oikeanuoli \neg X).

Muunnetaan kaava kaavaksi, joka ei sisällä : $F$ $\nuoli oikealle$

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

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

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

Jakelulain mukaan saamme CNF:

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

k -konjunktiivinen normaalimuoto

K -konjunktiivinen normaalimuoto on konjunktiivinen normaalimuoto, jossa jokainen disjunktio sisältää tarkalleen k literaalia .

Esimerkiksi seuraava kaava on kirjoitettu 2-CNF:llä:

(A\tai B)\land (\neg B\tai C)\maa (B\tai \neg C).

Siirtyminen KNF:stä SKNF :ään

Jos jokin muuttuja puuttuu yksinkertaisesta disjunktiosta (esimerkiksi z), lisäämme siihen lausekkeen: (tämä ei muuta itse disjunktiota), jonka jälkeen avataan hakasulkeet jakautumislain avulla : $Z\kiila \neg Z=0$

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

Siten SKNF saadaan CNF:stä.

Muodollinen kielioppi, joka kuvaa CNF:ää

Seuraava muodollinen kielioppi kuvaa kaikki CNF:ksi pelkistetut kaavat:

jossa <termi> tarkoittaa mielivaltaista loogista muuttujaa.

CNF:n kaavan tyydyttävyysongelma

Laskennallisen monimutkaisuuden teoriassa tärkeä rooli on Boolen kaavojen tyydyttävyyden ongelmalla konjunktiivisessa normaalimuodossa. Cooken lauseen mukaan tämä ongelma on NP-täydellinen , ja se pelkistyy 3-CNF:n kaavojen tyydyttävyysongelmaksi, joka pienentää ja johon muut NP-täydelliset ongelmat puolestaan vähenevät .

2-CNF-kaavojen tyydyttävyysongelma voidaan ratkaista lineaarisessa ajassa.

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\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E);

(A\vee B)\wedge ({\overline {B}}\vee C\vee {\overline {D}})\wedge (D\vee {\overline {E}});

(A\vee B)\cdot ({\overline {B}}\vee C\vee {\overline {D}})\cdot (D\vee {\overline {E}});

(A\vee B)({\overline {B}}\vee C\vee {\overline {D}})(D\vee {\overline {E}});

(A+B)({\overline {B}}+C+{\overline {D}})(D+{\overline {E}}).

Tästä syystä venäjänkielisessä kirjallisuudessa CNF:ää kutsutaan joskus "summien tuotteeksi", joka on piirrospaperi englanninkielisestä termistä "summien tuote".

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)

Linkit

Disjunktiiviset ja konjunktiiviset normaalimuodot