Konjunktiivinen normaali muoto - Conjunctive normal form

On Boolen logiikan , joka on kaavan on konjunktiivisessa normaalissa muodossa ( CNF ) tai Clausal normaali muodossa , jos se on yhdessä yhden tai useamman lausekkeita , jossa lauseke on Ulkopuolelle on literaaleja ; muuten se on summien tai syrjäisimpien alueiden tulo . Koska kanoninen normaali muoto , se on käyttökelpoinen automatisoitu lause todistaminen ja piiri teoria .

Kaikki literaalien yhdistämiset ja kaikki literaalien dissjunktiot ovat CNF: ssä, koska ne voidaan nähdä yhden kirjaimen lausekkeiden ja yhden lausekkeen konjunktioina. Kuten Disjunktiivinen Normaalimuoto (DNF), vain propositionaalinen konnektiivit kaavaa, CNF voi sisältää ovat ja , tai , ja ei . Ei -operaattoria voidaan käyttää vain osana literaalia, mikä tarkoittaa, että se voi edeltää vain ehdotusmuuttujaa tai predikaattisymbolia .

Automaattisessa lausevarmennuksessa käsitettä " clausal normal form " käytetään usein suppeammassa merkityksessä, mikä tarkoittaa tiettyä CNF -kaavan esitystä kirjainsarjoina .

Esimerkkejä ja ei-esimerkkejä

Kaikki seuraavat kaavat muuttujat , ja ovat konjunktiivisessa normaalissa muodossa: ${\ displaystyle A, B, C, D, E}$${\ displaystyle F}$

• ${\ displaystyle (A \ lor \ neg B \ lor \ neg C) \ land (\ neg D \ lor E \ lor F)}$
• ${\ displaystyle (A \ lor B) \ land (C)}$
• ${\ displaystyle (A \ l tai B)}$
• ${\ displaystyle (A)}$

Selvyyden vuoksi erottavat lausekkeet on kirjoitettu yllä oleviin sulkeisiin. Vuonna Disjunktiivinen Normaalimuoto kanssa suluissa konjunktiivista lausekkeita, viimeinen asia on sama, mutta vieressä viimeinen on . Vakioita tosi ja epätosi merkitään tyhjällä sidoksella ja yhdellä lauseella, joka koostuu tyhjästä disjunktiivista, mutta ne kirjoitetaan yleensä nimenomaisesti. ${\ displaystyle (A) \ lor (B)}$

Seuraavat kaavat eivät ole yhdistävässä normaalimuodossa:

• ${\ displaystyle \ neg (B \ l tai C)}$, koska TAI on sisäkkäin NOT: n sisällä
• ${\ displaystyle (A \ maa B) \ lor C}$
• ${\ displaystyle A \ land (B \ lor (D \ land E))}$, koska AND on sisäkkäin OR: n sisällä

Jokainen kaava voidaan kirjoittaa vastaavasti kaavaksi konjunktiivisessa normaalimuodossa. Kolme ei-esimerkkiä CNF: ssä ovat:

• ${\ displaystyle (\ neg B) \ land (\ neg C)}$
• ${\ displaystyle (A \ lor C) \ land (B \ lor C)}$
• ${\ displaystyle (A) \ land (B \ lor D) \ land (B \ lor E).}$

Muuntaminen CNF: ksi

Jokainen ehdotuskaava voidaan muuntaa vastaavaksi kaavaksi, joka on CNF: ssä. Tämä muutos perustuu sääntöihin, jotka koskevat loogisia vastaavuuksia : kaksinkertaisen kieltämisen poistaminen , De Morganin lait ja jakelulaki .

Koska kaikki lausekaavat voidaan muuntaa vastaavaksi kaavaksi konjunktiivisessa normaalimuodossa, todisteet perustuvat usein oletukseen, että kaikki kaavat ovat CNF -kaavoja. Joissakin tapauksissa tämä muuntaminen CNF: ksi voi kuitenkin johtaa kaavan räjähdysmäiseen räjähdykseen. Esimerkiksi seuraavan ei-CNF-kaavan kääntäminen CNF: ksi tuottaa kaavan, jossa on lausekkeita: ${\ displaystyle 2^{n}}$

${\ displaystyle (X_ {1} \ kiila Y_ {1}) \ vee (X_ {2} \ kiila Y_ {2}) \ vee \ dots \ vee (X_ {n} \ kiila Y_ {n}).}$

Erityisesti luotu kaava on:

${\ displaystyle (X_ {1} \ vee X_ {2} \ vee \ cdots \ vee X_ {n}) \ wedge (Y_ {1} \ vee X_ {2} \ vee \ cdots \ vee X_ {n}) \ kiila (X_ {1} \ vee Y_ {2} \ vee \ cdots \ vee X_ {n}) \ kiila (Y_ {1} \ vee Y_ {2} \ vee \ cdots \ vee X_ {n}) \ kiila \ cdots \ kiila (Y_ {1} \ vee Y_ {2} \ vee \ cdots \ vee Y_ {n}).}$

Tämä kaava sisältää lausekkeita; jokainen lauseke sisältää joko tai kunkin . ${\ displaystyle 2^{n}}$${\ displaystyle X_ {i}}$${\ displaystyle Y_ {i}}$${\ displaystyle i}$

On olemassa muutoksia CNF: ksi, jotka välttävät eksponentiaalisen koon kasvun säilyttämällä tyydyttävyyden eikä vastaavuuden . Nämä muunnokset lisäävät kaavan kokoa vain lineaarisesti, mutta ottavat käyttöön uusia muuttujia. Esimerkiksi yllä oleva kaava voidaan muuntaa CNF: ksi lisäämällä muuttujia seuraavasti: ${\ displaystyle Z_ {1}, \ ldots, Z_ {n}}$

${\ displaystyle (Z_ {1} \ vee \ cdots \ vee Z_ {n}) \ kiila (\ neg Z_ {1} \ vee X_ {1}) \ kiila (\ neg Z_ {1} \ vee Y_ {1} ) \ kiila \ cdots \ kiila (\ neg Z_ {n} \ vee X_ {n}) \ kiila (\ neg Z_ {n} \ vee Y_ {n}).}$

Tulkinta täyttää tämän kaavan vain, jos vähintään yksi uusia muuttujia on totta. Jos tämä muuttuja on , niin molemmat ja ovat myös totta. Tämä tarkoittaa, että jokainen malli, joka täyttää tämän kaavan, täyttää myös alkuperäisen. Toisaalta vain jotkut alkuperäisen kaavan malleista täyttävät tämän: koska niitä ei mainita alkuperäisessä kaavassa, niiden arvoilla ei ole merkitystä sen tyydyttämiselle, mikä ei pidä paikkaansa viimeisessä kaavassa. Tämä tarkoittaa, että alkuperäinen kaava ja käännöksen tulos ovat tyydyttäviä, mutta eivät vastaavia . ${\ displaystyle Z_ {i}}$${\ displaystyle X_ {i}}$${\ displaystyle Y_ {i}}$${\ displaystyle Z_ {i}}$

Vaihtoehtoinen käännös, Tseitin -muunnos , sisältää myös lausekkeet . Näiden lausekkeiden mukaan kaava merkitsee ; tämän kaavan katsotaan usein "määrittelevän" nimen . ${\ displaystyle Z_ {i} \ vee \ neg X_ {i} \ vee \ neg Y_ {i}}$${\ displaystyle Z_ {i} \ equiv X_ {i} \ kiila Y_ {i}}$${\ displaystyle Z_ {i}}$${\ displaystyle X_ {i} \ kiila Y_ {i}}$

Ensimmäisen asteen logiikka

Ensimmäisen asteen logiikassa konjunktiivinen normaalimuoto voidaan viedä pidemmälle, jotta saadaan loogisen kaavan clausal-normaalimuoto , jota voidaan sitten käyttää suorittamaan ensimmäisen asteen päätöslauselma . Erottelupohjaisessa automaattisessa lauseen todistuksessa CNF-kaava

${\ displaystyle (})$

${\ displaystyle l_ {11}}$

${\ displaystyle \ lor}$

${\ displaystyle \ ldots}$

${\ displaystyle \ lor}$

${\ displaystyle l_ {1n_ {1}}}$

${\ displaystyle)}$

${\ displaystyle \ land}$

${\ displaystyle \ ldots}$

${\ displaystyle \ land}$

${\ displaystyle (})$

${\ displaystyle l_ {m1}}$

${\ displaystyle \ lor}$

${\ displaystyle \ ldots}$

${\ displaystyle \ lor}$

${\ displaystyle l_ {mn_ {m}}}$

${\ displaystyle)}$

, kirjaimilla, on yleisesti esitetty joukkona joukkoja ${\ displaystyle l_ {ij}}$

${\ displaystyle \ {}$

${\ displaystyle \ {}$

${\ displaystyle l_ {11}}$

${\ displaystyle,}$

${\ displaystyle \ ldots}$

${\ displaystyle,}$

${\ displaystyle l_ {1n_ {1}}}$

${\ displaystyle \}}$

${\ displaystyle,}$

${\ displaystyle \ ldots}$

${\ displaystyle,}$

${\ displaystyle \ {}$

${\ displaystyle l_ {m1}}$

${\ displaystyle,}$

${\ displaystyle \ ldots}$

${\ displaystyle,}$

${\ displaystyle l_ {mn_ {m}}}$

${\ displaystyle \}}$

${\ displaystyle \}}$

.

Katso esimerkki alla .

Laskennallinen monimutkaisuus

Tärkeä laskennallisen monimutkaisuuden ongelmasarja sisältää tehtävien etsimisen konjunktiivisessa normaalimuodossa ilmaistun boolen kaavan muuttujille siten, että kaava on totta. K -la ongelma on ongelma löytää täyttävän toimeksiannon boolean kaava ilmaistaan CNF, joissa kukin disjunktio sisältää enintään k muuttujia. 3-SAT on NP-täydellinen (kuten mikä tahansa muu k -SAT - ongelma, jonka k > 2), kun taas 2-SAT: llä tiedetään olevan ratkaisuja polynomiajassa . Tämän seurauksena kaavan muuttaminen DNF: ksi ja tyydyttävyyden säilyttäminen on NP-vaikeaa ; kaksinkertaisesti , muuntaminen CNF: ksi, voimassaolon säilyttäminen , on myös NP-kovaa; näin ollen vastaavuutta säilyttävä muuntaminen DNF: ksi tai CNF: ksi on jälleen NP-kovaa.

Tyypillisiä ongelmia tässä tapauksessa ovat kaavat "3CNF": konjunktiivinen normaalimuoto, jossa on enintään kolme muuttujaa konjunktiota kohden. Esimerkkejä tällaisista kaavoista käytännössä voi olla hyvin suuria, esimerkiksi 100 000 muuttujaa ja 1 000 000 konjunktiota.

Kaava on CNF voidaan muuntaa equisatisfiable kaavan " k CNF" (for k ≥3) korvaamalla kukin yhtymä, joissa on enemmän kuin k muuttujaa kaksi conjuncts ja jossa Z uuden muuttujan, ja toistamalla niin usein kuin on tarpeen. ${\ displaystyle X_ {1} \ vee \ cdots \ vee X_ {k} \ vee \ cdots \ vee X_ {n}}$${\ displaystyle X_ {1} \ vee \ cdots \ vee X_ {k-1} \ vee Z}$${\ displaystyle \ neg Z \ vee X_ {k} \ cdots \ vee X_ {n}}$

Muuntaminen ensimmäisen asteen logiikasta

Muuntaa ensimmäisen kertaluokan logiikka on CNF:

1. Muunna kielteiseksi normaalimuotoon .
   1. Poistaa vaikutuksia ja vastaavuudet: toistuvasti vaihda kanssa ; vaihda kanssa . Lopulta tämä poistaa kaikki esiintymät ja .${\ displaystyle P \ oikea nuoli Q}$${\ displaystyle \ lnot P \ lor Q}$${\ displaystyle P \ leftrightarrow Q}$${\ displaystyle (P \ lor \ l ei Q) \ land (\ l not P \ lor Q)}$${\ displaystyle \ rightarrow}$${\ displaystyle \ leftrightarrow}$
   2. Siirry NOTs sisäänpäin soveltamalla toistuvasti De Morganin lakia . Korvaa nimenomaan ; korvata kanssa ; ja korvata kanssa ; korvata kanssa ; kanssa . Tämän jälkeen a voi esiintyä vain välittömästi ennen predikaattisymbolia.${\ displaystyle \ lnot (P \ l tai Q)}$${\ displaystyle (\ lnot P) \ land (\ l not Q)}$${\ displaystyle \ lnot (P \ land Q)}$${\ displaystyle (\ lnot P) \ lor (\ l not Q)}$${\ displaystyle \ lnot \ l not P}$${\ displaystyle P}$${\ displaystyle \ lnot (\ koko xP (x))}$${\ displaystyle \ olemassa x \ l ei P (x)}$${\ displaystyle \ lnot (\ olemassa xP (x))}$${\ displaystyle \ koko x \ l ei P (x)}$${\ displaystyle \ lnot}$
2. Standardoi muuttujat
   1. Jos lauseet käyttävät samaa muuttujanimeä kahdesti, muuta jonkin muuttujan nimi. Näin vältetään sekaannus myöhemmin pudotettaessa kvanttoreita. Esimerkiksi on nimetty uudelleen .${\ displaystyle (\ forall xP (x)) \ lor (\ olemassa xQ (x))}$${\ displaystyle \ forall x [\ olemassa y \ mathrm {Animal} (y) \ land \ lnot \ mathrm {Loves} (x, y)] \ lor [\ olemassa y \ mathrm {Loves} (y, x)] }$${\ displaystyle \ forall x [\ olemassa y \ mathrm {Animal} (y) \ land \ lnot \ mathrm {Loves} (x, y)] \ lor [\ olemassa z \ mathrm {Loves} (z, x)] }$
3. Skolemize lausunto
   1. Siirrä kvanttorit ulospäin: toistuvasti vaihda kanssa ; korvata kanssa ; korvata kanssa ; vaihda kanssa . Nämä korvaukset säilyttävät vastaavuuden, koska edellinen muuttujan standardointivaihe varmisti, että sitä ei tapahdu . Kun nämä vaihdot, kvantisointi voi tapahtua vain ensimmäisen etuliite, jolla on kaava, mutta ei koskaan sisällä , tai .${\ displaystyle P \ land (\ koko xQ (x))}$${\ displaystyle \ koko x (P \ maa Q (x))}$${\ displaystyle P \ lor (\ koko xQ (x))}$${\ displaystyle \ forall x (P \ l tai Q (x))}$${\ displaystyle P \ land (\ olemassa xQ (x))}$${\ displaystyle \ olemassa x (P \ land Q (x))}$${\ displaystyle P \ lor (\ olemassa xQ (x))}$${\ displaystyle \ olemassa x (P \ l tai Q (x))}$${\ displaystyle x}$${\ displaystyle P}$${\ displaystyle \ lnot}$${\ displaystyle \ land}$${\ displaystyle \ lor}$
   2. Toistuvasti korvaa kanssa , jossa on uusi aarisen funktion symboli, niin sanottu " Skolem toiminto ". Tämä on ainoa askel, joka säilyttää vain tyydytyksen eikä vastaavuuden. Se poistaa kaikki eksistentiaaliset kvantorit.${\ displaystyle \ forall x_ {1} \ ldots \ forall x_ {n} \; \ olemassa y \; P (y)}$${\ displaystyle \ forall x_ {1} \ ldots \ forall x_ {n} \; P (f (x_ {1}, \ ldots, x_ {n}))}$${\ displaystyle f}$${\ displaystyle n}$
4. Pudota kaikki yleismittarit.
5. Jakaa syrjäisimmät alueet sisäänpäin yli JAtoiminnon: toistuvasti vaihda kanssa .${\ displaystyle P \ lor (Q \ land R)}$${\ displaystyle (P \ lor Q) \ land (P \ lor R)}$

Esimerkiksi kaavan sanonta "Joka rakastaa kaikkia eläimiä, on puolestaan rakastama joku" muunnetaan CNF (ja tämän jälkeen lauseke muotoon viimeisellä rivillä) seuraavasti (korostus korvaava sääntö redexes vuonna ): ${\ displaystyle {\ color {red} {\ text {red}}}}$

${\ displaystyle \ forall x}$

${\ displaystyle (})$

${\ displaystyle \ forall y}$

${\ displaystyle \ mathrm {Eläin} (}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle \ color {red} \ rightarrow}$

${\ displaystyle \ mathrm {Rakastaa} (x,}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle)}$

${\ displaystyle \ rightarrow}$

${\ displaystyle (})$

${\ displaystyle \ olemassa}$

${\ displaystyle y}$

${\ displaystyle \ mathrm {Rakastaa} (}$

${\ displaystyle y}$

${\ displaystyle, x)}$

${\ displaystyle)}$

${\ displaystyle \ forall x}$

${\ displaystyle (})$

${\ displaystyle \ forall y}$

${\ displaystyle \ lnot}$

${\ displaystyle \ mathrm {Eläin} (}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle \ lor}$

${\ displaystyle \ mathrm {Rakastaa} (x,}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle)}$

${\ displaystyle \ color {red} \ rightarrow}$

${\ displaystyle (})$

${\ displaystyle \ olemassa}$

${\ displaystyle y}$

${\ displaystyle \ mathrm {Rakastaa} (}$

${\ displaystyle y}$

${\ displaystyle, x)}$

${\ displaystyle)}$

1.1

${\ displaystyle \ forall x}$

${\ displaystyle \ color {red} \ lnot}$

${\ displaystyle (})$

${\ displaystyle {\ color {red} {\ forall y}}}$

${\ displaystyle \ lnot}$

${\ displaystyle \ mathrm {Eläin} (}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle \ lor}$

${\ displaystyle \ mathrm {Rakastaa} (x,}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle)}$

${\ displaystyle \ lor}$

${\ displaystyle (})$

${\ displaystyle \ olemassa}$

${\ displaystyle y}$

${\ displaystyle \ mathrm {Rakastaa} (}$

${\ displaystyle y}$

${\ displaystyle, x)}$

${\ displaystyle)}$

1.1

${\ displaystyle \ forall x}$

${\ displaystyle (})$

${\ displaystyle \ olemassa y}$

${\ displaystyle \ color {red} \ lnot}$

${\ displaystyle (})$

${\ displaystyle \ lnot}$

${\ displaystyle \ mathrm {Eläin} (}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle \ color {red} \ lor}$

${\ displaystyle \ mathrm {Rakastaa} (x,}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle)}$

${\ displaystyle)}$

${\ displaystyle \ lor}$

${\ displaystyle (})$

${\ displaystyle \ olemassa}$

${\ displaystyle y}$

${\ displaystyle \ mathrm {Rakastaa} (}$

${\ displaystyle y}$

${\ displaystyle, x)}$

${\ displaystyle)}$

1.2

${\ displaystyle \ forall x}$

${\ displaystyle (})$

${\ displaystyle \ olemassa y}$

${\ displaystyle \ color {red} \ lnot}$

${\ displaystyle \ color {red} \ lnot}$

${\ displaystyle \ mathrm {Eläin} (}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle \ land}$

${\ displaystyle \ lnot}$

${\ displaystyle \ mathrm {Rakastaa} (x,}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle)}$

${\ displaystyle \ lor}$

${\ displaystyle (})$

${\ displaystyle \ olemassa}$

${\ displaystyle y}$

${\ displaystyle \ mathrm {Rakastaa} (}$

${\ displaystyle y}$

${\ displaystyle, x)}$

${\ displaystyle)}$

1.2

${\ displaystyle \ forall x}$

${\ displaystyle (})$

${\ displaystyle {\ color {red} {\ olemassa y}}}$

${\ displaystyle \ mathrm {Eläin} (}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle \ land}$

${\ displaystyle \ lnot}$

${\ displaystyle \ mathrm {Rakastaa} (x,}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle)}$

${\ displaystyle \ lor}$

${\ displaystyle (})$

${\ displaystyle \ color {red} \ olemassa}$

${\ displaystyle \ color {red} y}$

${\ displaystyle \ mathrm {Rakastaa} (}$

${\ displaystyle y}$

${\ displaystyle, x)}$

${\ displaystyle)}$

1.2

${\ displaystyle \ forall x}$

${\ displaystyle (})$

${\ displaystyle \ olemassa y}$

${\ displaystyle \ mathrm {Eläin} (}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle \ land}$

${\ displaystyle \ lnot}$

${\ displaystyle \ mathrm {Rakastaa} (x,}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle)}$

${\ displaystyle \ color {red} \ lor}$

${\ displaystyle (})$

${\ displaystyle \ color {red} \ olemassa}$

${\ displaystyle \ color {red} z}$

${\ displaystyle \ mathrm {Rakastaa} (}$

${\ displaystyle z}$

${\ displaystyle, x)}$

${\ displaystyle)}$

2

${\ displaystyle \ forall x}$

${\ displaystyle \ olemassa z}$

${\ displaystyle (})$

${\ displaystyle {\ color {red} {\ olemassa y}}}$

${\ displaystyle \ mathrm {Eläin} (}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle \ land}$

${\ displaystyle \ lnot}$

${\ displaystyle \ mathrm {Rakastaa} (x,}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle)}$

${\ displaystyle \ color {red} \ lor}$

${\ displaystyle \ mathrm {Rakastaa} (}$

${\ displaystyle z}$

${\ displaystyle, x)}$

mennessä 3.1

${\ displaystyle \ forall x}$

${\ displaystyle {\ color {red} {\ olemassa z}}}$

${\ displaystyle \ olemassa y}$

${\ displaystyle (})$

${\ displaystyle \ mathrm {Eläin} (}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle \ land}$

${\ displaystyle \ lnot}$

${\ displaystyle \ mathrm {Rakastaa} (x,}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle)}$

${\ displaystyle \ lor}$

${\ displaystyle \ mathrm {Rakastaa} (}$

${\ displaystyle z}$

${\ displaystyle, x)}$

mennessä 3.1

${\ displaystyle \ forall x}$

${\ displaystyle {\ color {red} {\ olemassa y}}}$

${\ displaystyle (})$

${\ displaystyle \ mathrm {Eläin} (}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle \ land}$

${\ displaystyle \ lnot}$

${\ displaystyle \ mathrm {Rakastaa} (x,}$

${\ displaystyle y}$

${\ displaystyle)}$

${\ displaystyle)}$

${\ displaystyle \ lor}$

${\ displaystyle \ mathrm {Rakastaa} (}$

${\ displaystyle g (x)}$

${\ displaystyle, x)}$

3.2

${\ displaystyle (})$

${\ displaystyle \ mathrm {Eläin} (}$

${\ displaystyle f (x)}$

${\ displaystyle)}$

${\ displaystyle \ color {red} \ land}$

${\ displaystyle \ lnot}$

${\ displaystyle \ mathrm {Rakastaa} (x,}$

${\ displaystyle f (x)}$

${\ displaystyle)}$

${\ displaystyle)}$

${\ displaystyle \ color {red} \ lor}$

${\ displaystyle \ mathrm {Rakastaa} (}$

${\ displaystyle g (x)}$

${\ displaystyle, x)}$

4

${\ displaystyle (})$

${\ displaystyle \ mathrm {Eläin} (}$

${\ displaystyle f (x)}$

${\ displaystyle)}$

${\ displaystyle \ color {red} \ lor}$

${\ displaystyle \ mathrm {Rakastaa} (}$

${\ displaystyle g (x)}$

${\ displaystyle, x)}$

${\ displaystyle)}$

${\ displaystyle \ color {red} \ land}$

${\ displaystyle (})$

${\ displaystyle \ lnot \ mathrm {Rakastaa} (x, f (x))}$

${\ displaystyle \ color {red} \ lor}$

${\ displaystyle \ mathrm {Rakastaa} (g (x), x)}$

${\ displaystyle)}$

5

${\ displaystyle \ {}$

${\ displaystyle \ {}$

${\ displaystyle \ mathrm {Eläin} (}$

${\ displaystyle f (x)}$

${\ displaystyle)}$

${\ displaystyle,}$

${\ displaystyle \ mathrm {Rakastaa} (}$

${\ displaystyle g (x)}$

${\ displaystyle, x)}$

${\ displaystyle \}}$

${\ displaystyle,}$

${\ displaystyle \ {}$

${\ displaystyle \ lnot \ mathrm {Rakastaa} (x, f (x))}$

${\ displaystyle,}$

${\ displaystyle \ mathrm {Rakastaa} (g (x), x)}$

${\ displaystyle \}}$

${\ displaystyle \}}$

( lausekkeen esitys)

Epämuodollisesti Skolem -funktion voidaan ajatella tuottavan sen henkilön, jota rakastetaan, samalla kun se tuottaa eläimen (jos sellainen on), joka ei rakasta. Kolmas viimeinen rivi alhaalta kuuluu sitten " ei rakasta eläintä tai muuten hän rakastaa " . ${\ displaystyle g (x)}$${\ displaystyle x}$${\ displaystyle f (x)}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle f (x)}$${\ displaystyle x}$${\ displaystyle g (x)}$

Toinen viimeinen rivi ylhäältä , on CNF. ${\ displaystyle (\ mathrm {Animal} (f (x)) \ lor \ mathrm {Loves} (g (x), x)) \ land (\ lnot \ mathrm {Loves} (x, f (x)) \ lor \ mathrm {Rakastaa} (g (x), x))}$

Huomautuksia

Katso myös

• Algebrallinen normaalimuoto
• Disjunktiivinen normaali muoto
• Sarvilauseke
• Quine -McCluskey -algoritmi

Viitteet

• Eldon Whitesitt (24. toukokuuta 2012). Boolen algebra ja sen sovellukset . Courier Corporation. ISBN 978-0-486-15816-7.
• Hans Kleine Büning; Theodor Lettmann (28. elokuuta 1999). Ehdotuslogiikka: Vähennys ja algoritmit . Cambridge University Press. ISBN 978-0-521-63017-7.
• Paul Jackson, Daniel Sheridan: Lauseke muunnokset Boolen piirille . Julkaisussa: Holger H. Hoos, David G. Mitchell (toim.): Theory and Applications of Satisfiability Testing, 7. International Conference, SAT 2004, Vancouver, BC, Kanada, 10. -13. Toukokuuta 2004, Revised Selected Papers. Luentohuomautuksia tietojenkäsittelytieteessä 3542, Springer 2005, s. 183–198
• GS Tseitin: Johtamisen monimutkaisuudesta ehdotuslaskennassa . Julkaisussa: Slisenko, AO (toim.) Structures in Constructive Mathematics and Mathematical Logic, Osa II, Seminaarit in Mathematics (käännetty venäjästä), s. 115–125. Steklovin matemaattinen instituutti (1968)

Ulkoiset linkit

• "Yhdistävä normaali muoto" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Java -sovelma muuntamiseen CNF- ja DNF -muotoon, näytetään käytetyt lait