Konjunktív normál forma - Conjunctive normal form

A Boole-logika , egy általános képletű van konjunktív normál forma ( CNF ) vagy clausal normál forma , ha ez egy együtt egy vagy több kikötések , ahol egy kikötés egy diszjunkcióját a literálok ; másképp fogalmazva, összegek vagy a legkülső régiók ÉS terméke . Ennek kanonikus normál formában , ez hasznos automatizált tételbizonyítás és áramköri elmélet .

A literálok összes kötőszava és a literálok minden disjunkciója a CNF-ben található, mivel tekinthetők az egy-literális záradékok kötőszóinak, illetve egyetlen záradék kötőszóinak. Ahogy a diszjunktív normál forma (DNF), az egyetlen propozicionális konnektívumokban található képlet CNF tartalmazhatnak vannak , és , vagy , és nem . A not operátor csak literál részeként használható, ami azt jelenti, hogy csak egy propozíciós változót vagy egy predikátum szimbólumot előzhet meg .

Az automatizált tételbizonyításban a " clausal normal forma " fogalmat gyakran szűkebb értelemben használják, ami a CNF képletnek a literálok halmazaként meghatározott ábrázolását jelenti.

Példák és nem példák

Az összes következő képlet a változókban , és konjunktív normál formában van: ${\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\lor B)}$
• ${\displaystyle (A)}$

Az egyértelműség kedvéért a szétválasztó záradékok a fenti zárójelbe vannak írva. A diszjunktív normál forma a zárójelbe konjunktív feltételek, az utolsó esetben ugyanaz, de a mellette utoljára . Az igaz és hamis állandókat az üres kötőszó és az üres diszjunktumból álló záradék jelöli, de általában kifejezetten írják. ${\displaystyle (A)\lor (B)}$

A következő képletek nem konjunktív normál formában vannak:

• ${\displaystyle \neg (B\lor C)}$, mivel a VAGY egy NOT -ban van beágyazva
• ${\displaystyle (A\land B)\lor C}$
• ${\displaystyle A\land (B\lor (D\land E))}$, mivel egy ÉS beágyazódik egy VAGY -ba

Minden képlet egyenértékűen írható képletként konjunktív normál formában. A CNF három nem példája:

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

Átalakítás CNF -re

Minden propozíciós képlet átalakítható egy egyenértékű képletre, amely CNF -ben van. Ez az átalakítás a logikai egyenértékűségekre vonatkozó szabályokon alapul : kettős tagadás megszüntetése , De Morgan törvényei és az elosztási törvény .

Mivel minden állítási képlet átalakítható ekvivalens formulává konjunktív normál formában, a bizonyítások gyakran azon a feltételezésen alapulnak, hogy minden képlet CNF. Bizonyos esetekben azonban ez a CNF -re való átalakítás a képlet exponenciális robbanásához vezethet. Például, ha a következő, nem CNF képletet CNF-re fordítja, akkor egy képletet kap, amely záradékokkal rendelkezik: ${\displaystyle 2^{n}}$

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

Különösen a generált képlet a következő:

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

Ez a képlet záradékokat tartalmaz ; valamennyi szakasza tartalmaz sem , vagy az egyes . ${\displaystyle 2^{n}}$${\displaystyle X_{i}}$${\displaystyle Y_{i}}$${\displaystyle i}$

Léteznek olyan átalakulások CNF -vé, amelyek elkerülik a méret exponenciális növekedését azáltal, hogy megőrzik az elégedettséget, nem pedig az egyenértékűséget . Ezek az átalakítások garantáltan csak lineárisan növelik a képlet méretét, de új változókat vezetnek be. Például a fenti képlet átalakítható CNF -be a következő változók hozzáadásával : ${\displaystyle Z_{1},\ldots ,Z_{n}}$

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

Egy értelmezés csak akkor elégíti ki ezt a képletet, ha az új változók közül legalább az egyik igaz. Ha ez a változó , akkor mindkettő és igaz is. Ez azt jelenti, hogy minden modell, amely megfelel ennek a képletnek, kielégíti az eredetit is. Másrészt az eredeti képletnek csak néhány modellje felel meg ennek: mivel a nem szerepel az eredeti képletben, értékeik irrelevánsak annak kielégítése szempontjából, ami az utolsó képletben nem így van. Ez azt jelenti, hogy az eredeti képlet és a fordítás eredménye egyenlő, de nem egyenértékű . ${\displaystyle Z_{i}}$${\displaystyle X_{i}}$${\displaystyle Y_{i}}$${\displaystyle Z_{i}}$

Egy alternatív fordítás, a Tseitin transzformáció , tartalmazza a záradékokat is . Ezekkel a záradékokkal a képlet azt sugallja ; ezt a képletet gyakran úgy tekintik, hogy "definiálja" annak nevét . ${\displaystyle Z_{i}\vee \neg X_{i}\vee \neg Y_{i}}$${\displaystyle Z_{i}\equiv X_{i}\wedge Y_{i}}$${\displaystyle Z_{i}}$${\displaystyle X_{i}\wedge Y_{i}}$

Elsőrendű logika

Az elsőrendű logikában a konjunktív normál formát tovább lehet vinni , hogy logikai képlet clausal normál formáját kapjuk, amelyet aztán fel lehet használni az elsőrendű felbontás végrehajtására . Felbontáson alapuló automatizált tétel-bizonyításban CNF képlet

${\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 )}$

, literálokkal, általában halmazok halmazaként ábrázolják ${\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 \}}$

.

Lásd az alábbi példát.

Számítási komplexitás

A számítási komplexitás egyik fontos problémaköre magában foglalja a konjunktív normál formában kifejezett logikai képlet változóinak hozzárendeléseit, így a képlet igaz. A k -SAT probléma a CNF -ben kifejezett logikai képlet kielégítő hozzárendelésének megkeresése, amelyben minden diszjunkció legfeljebb k változót tartalmaz. 3-SAT jelentése NP-teljes (mint bármely más k -SAT probléma k > 2), míg 2-vel ismert, hogy a megoldások a polinomiális időben . Következésképpen a képlet DNF- vé alakítása , a kielégíthetőség megőrzése NP-nehéz feladat ; kettős , a CNF-re történő átalakítás, az érvényesség megőrzése szintén NP-kemény; ezért az egyenértékűséget megőrző átalakítás DNF-re vagy CNF-re ismét NP-kemény.

A tipikus problémák ebben az esetben a "3CNF" képleteket foglalják magukban: kötőszövegű normál forma, kötőszámonként legfeljebb három változóval. A gyakorlatban előforduló ilyen képletek példái nagyon nagyok lehetnek, például 100 000 változóval és 1 000 000 kötőszóval.

A képlet CNF lehet alakítani egy equisatisfiable képlet „ k CNF” (a k ≥3) helyett az egyes összekapcsolt több mint k változót a két conjuncts és a Z egy új változó, és megismételjük a szükséges gyakorisággal. ${\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}}$

Konvertálás elsőrendű logikából

Az elsőrendű logika konvertálása CNF-re:

1. Konvertálás tagadás normál formába .
   1. Távolítsuk következményeit és ekvivalencia: többször cserélni a ; cserélni a . Végül ez megszünteti a és minden előfordulását .${\displaystyle P\rightarrow Q}$${\displaystyle \lnot P\lor Q}$${\displaystyle P\leftrightarrow Q}$${\displaystyle (P\lor \lnot Q)\land (\lnot P\lor Q)}$${\displaystyle \rightarrow }$${\displaystyle \leftrightarrow }$
   2. Mozgassa a NOT -t befelé a De Morgan -törvény ismételt alkalmazásával . Pontosabban, cserélje ki ; cserélje a ; és cserélje a ; cserélje a ; -val . Ezt követően az a csak közvetlenül egy predikátum szimbólum előtt fordulhat elő.${\displaystyle \lnot (P\lor Q)}$${\displaystyle (\lnot P)\land (\lnot Q)}$${\displaystyle \lnot (P\land Q)}$${\displaystyle (\lnot P)\lor (\lnot Q)}$${\displaystyle \lnot \lnot P}$${\displaystyle P}$${\displaystyle \lnot (\forall xP(x))}$${\displaystyle \exists x\lnot P(x)}$${\displaystyle \lnot (\exists xP(x))}$${\displaystyle \forall x\lnot P(x)}$${\displaystyle \lnot }$
2. Standardizálja a változókat
   1. Az olyan mondatok esetében, amelyek kétszer használják ugyanazt a változónevet, módosítsa az egyik változó nevét. Ezzel elkerülhető a későbbi zűrzavar a kvantorok ejtésekor. Például át van nevezve erre .${\displaystyle (\forall xP(x))\lor (\exists xQ(x))}$${\displaystyle \forall x[\exists y\mathrm {Animal} (y)\land \lnot \mathrm {Loves} (x,y)]\lor [\exists y\mathrm {Loves} (y,x)]}$${\displaystyle \forall x[\exists y\mathrm {Animal} (y)\land \lnot \mathrm {Loves} (x,y)]\lor [\exists z\mathrm {Loves} (z,x)]}$
3. Skolemize a kijelentést
   1. Mozgassa a kvantorokat kifelé: többször cserélje ki ; cserélje a ; cserélje a ; cserélni a . Ezek a cserék megőrzik az egyenértékűséget, mivel az előző változó szabványosítási lépés biztosította, hogy ne forduljon elő . Miután ezek a helyettesítések, a kvantor előfordulhat csak a kezdeti előtag általános képletű, de soha nem belsejében egy , vagy .${\displaystyle P\land (\forall xQ(x))}$${\displaystyle \forall x(P\land Q(x))}$${\displaystyle P\lor (\forall xQ(x))}$${\displaystyle \forall x(P\lor Q(x))}$${\displaystyle P\land (\exists xQ(x))}$${\displaystyle \exists x(P\land Q(x))}$${\displaystyle P\lor (\exists xQ(x))}$${\displaystyle \exists x(P\lor Q(x))}$${\displaystyle x}$${\displaystyle P}$${\displaystyle \lnot }$${\displaystyle \land }$${\displaystyle \lor }$
   2. Ismételten cserélje le , ahol egy új -ar függvény szimbólum található, egy úgynevezett " Skolem függvény ". Ez az egyetlen lépés, amely csak az elégedettséget őrzi meg, nem pedig az egyenértékűséget. Megszünteti az összes létező kvantorokat.${\displaystyle \forall x_{1}\ldots \forall x_{n}\;\exists y\;P(y)}$${\displaystyle \forall x_{1}\ldots \forall x_{n}\;P(f(x_{1},\ldots ,x_{n}))}$${\displaystyle f}$${\displaystyle n}$
4. Dobja el az összes univerzális mennyiségi mutatót.
5. A legkülső részek elosztása befelé az ÉS -ek felett: többször cserélje ki a -ra .${\displaystyle P\lor (Q\land R)}$${\displaystyle (P\lor Q)\land (P\lor R)}$

Példaként a képlet azt mondja : „Aki szereti az összes állatot, viszont szereti valaki” átalakul CNF (és később esetleg záradék formájában az utolsó sorban) a következő (kiemelve csere szabály redexes in ): ${\displaystyle {\color {red}{\text{red}}}}$

${\displaystyle \forall x}$

${\displaystyle (}$

${\displaystyle \forall y}$

${\displaystyle \mathrm {Animal} (}$

${\displaystyle y}$

${\displaystyle )}$

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

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

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle )}$

${\displaystyle \rightarrow }$

${\displaystyle (}$

${\displaystyle \exists }$

${\displaystyle y}$

${\displaystyle \mathrm {Loves} (}$

${\displaystyle y}$

${\displaystyle ,x)}$

${\displaystyle )}$

${\displaystyle \forall x}$

${\displaystyle (}$

${\displaystyle \forall y}$

${\displaystyle \lnot }$

${\displaystyle \mathrm {Animal} (}$

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle \lor }$

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

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle )}$

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

${\displaystyle (}$

${\displaystyle \exists }$

${\displaystyle y}$

${\displaystyle \mathrm {Loves} (}$

${\displaystyle y}$

${\displaystyle ,x)}$

${\displaystyle )}$

1.1

${\displaystyle \forall x}$

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

${\displaystyle (}$

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

${\displaystyle \lnot }$

${\displaystyle \mathrm {Animal} (}$

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle \lor }$

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

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle )}$

${\displaystyle \lor }$

${\displaystyle (}$

${\displaystyle \exists }$

${\displaystyle y}$

${\displaystyle \mathrm {Loves} (}$

${\displaystyle y}$

${\displaystyle ,x)}$

${\displaystyle )}$

1.1

${\displaystyle \forall x}$

${\displaystyle (}$

${\displaystyle \exists y}$

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

${\displaystyle (}$

${\displaystyle \lnot }$

${\displaystyle \mathrm {Animal} (}$

${\displaystyle y}$

${\displaystyle )}$

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

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

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle )}$

${\displaystyle )}$

${\displaystyle \lor }$

${\displaystyle (}$

${\displaystyle \exists }$

${\displaystyle y}$

${\displaystyle \mathrm {Loves} (}$

${\displaystyle y}$

${\displaystyle ,x)}$

${\displaystyle )}$

1.2 -vel

${\displaystyle \forall x}$

${\displaystyle (}$

${\displaystyle \exists y}$

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

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

${\displaystyle \mathrm {Animal} (}$

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle \land }$

${\displaystyle \lnot }$

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

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle )}$

${\displaystyle \lor }$

${\displaystyle (}$

${\displaystyle \exists }$

${\displaystyle y}$

${\displaystyle \mathrm {Loves} (}$

${\displaystyle y}$

${\displaystyle ,x)}$

${\displaystyle )}$

1.2 -vel

${\displaystyle \forall x}$

${\displaystyle (}$

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

${\displaystyle \mathrm {Animal} (}$

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle \land }$

${\displaystyle \lnot }$

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

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle )}$

${\displaystyle \lor }$

${\displaystyle (}$

${\displaystyle \color {red}\exists }$

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

${\displaystyle \mathrm {Loves} (}$

${\displaystyle y}$

${\displaystyle ,x)}$

${\displaystyle )}$

1.2 -vel

${\displaystyle \forall x}$

${\displaystyle (}$

${\displaystyle \exists y}$

${\displaystyle \mathrm {Animal} (}$

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle \land }$

${\displaystyle \lnot }$

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

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle )}$

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

${\displaystyle (}$

${\displaystyle \color {red}\exists }$

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

${\displaystyle \mathrm {Loves} (}$

${\displaystyle z}$

${\displaystyle ,x)}$

${\displaystyle )}$

2 -vel

${\displaystyle \forall x}$

${\displaystyle \exists z}$

${\displaystyle (}$

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

${\displaystyle \mathrm {Animal} (}$

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle \land }$

${\displaystyle \lnot }$

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

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle )}$

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

${\displaystyle \mathrm {Loves} (}$

${\displaystyle z}$

${\displaystyle ,x)}$

3.1

${\displaystyle \forall x}$

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

${\displaystyle \exists y}$

${\displaystyle (}$

${\displaystyle \mathrm {Animal} (}$

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle \land }$

${\displaystyle \lnot }$

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

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle )}$

${\displaystyle \lor }$

${\displaystyle \mathrm {Loves} (}$

${\displaystyle z}$

${\displaystyle ,x)}$

3.1

${\displaystyle \forall x}$

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

${\displaystyle (}$

${\displaystyle \mathrm {Animal} (}$

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle \land }$

${\displaystyle \lnot }$

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

${\displaystyle y}$

${\displaystyle )}$

${\displaystyle )}$

${\displaystyle \lor }$

${\displaystyle \mathrm {Loves} (}$

${\displaystyle g(x)}$

${\displaystyle ,x)}$

3.2

${\displaystyle (}$

${\displaystyle \mathrm {Animal} (}$

${\displaystyle f(x)}$

${\displaystyle )}$

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

${\displaystyle \lnot }$

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

${\displaystyle f(x)}$

${\displaystyle )}$

${\displaystyle )}$

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

${\displaystyle \mathrm {Loves} (}$

${\displaystyle g(x)}$

${\displaystyle ,x)}$

4 által

${\displaystyle (}$

${\displaystyle \mathrm {Animal} (}$

${\displaystyle f(x)}$

${\displaystyle )}$

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

${\displaystyle \mathrm {Loves} (}$

${\displaystyle g(x)}$

${\displaystyle ,x)}$

${\displaystyle )}$

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

${\displaystyle (}$

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

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

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

${\displaystyle )}$

5 által

${\displaystyle \{}$

${\displaystyle \{}$

${\displaystyle \mathrm {Animal} (}$

${\displaystyle f(x)}$

${\displaystyle )}$

${\displaystyle ,}$

${\displaystyle \mathrm {Loves} (}$

${\displaystyle g(x)}$

${\displaystyle ,x)}$

${\displaystyle \}}$

${\displaystyle ,}$

${\displaystyle \{}$

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

${\displaystyle ,}$

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

${\displaystyle \}}$

${\displaystyle \}}$

( záradékábrázolás )

Informálisan a Skolem függvény úgy tekinthető, hogy megadja azt a személyt, akit szeret, míg az állatot (ha van), aki nem szeret. A harmadik utolsó sor alulról így hangzik: " nem szereti az állatot , különben szereti " . ${\displaystyle g(x)}$${\displaystyle x}$${\displaystyle f(x)}$${\displaystyle x}$${\displaystyle x}$${\displaystyle f(x)}$${\displaystyle x}$${\displaystyle g(x)}$

A második utolsó sor felülről,, a CNF. ${\displaystyle (\mathrm {Animal} (f(x))\lor \mathrm {Loves} (g(x),x))\land (\lnot \mathrm {Loves} (x,f(x))\lor \mathrm {Loves} (g(x),x))}$

Megjegyzések

Lásd még

• Algebrai normál forma
• Diszjunktív normál forma
• Kürt záradék
• Quine -McCluskey algoritmus

Hivatkozások

• J. Eldon Whitesitt (2012. május 24.). Logikai algebra és alkalmazásai . Courier Corporation. ISBN 978-0-486-15816-7.
• Hans Kleine Büning; Theodor Lettmann (1999. augusztus 28.). Propozíciós logika: levonás és algoritmusok . Cambridge University Press. ISBN 978-0-521-63017-7.
• Paul Jackson, Daniel Sheridan: Záradékforma konverziók a Boolean Circuits számára . In: Holger H. Hoos, David G. Mitchell (szerk.): Theory and Applications of Satisfiability Testing, 7. nemzetközi konferencia, SAT 2004, Vancouver, BC, Kanada, 2004. május 10–13, Revised Selected Papers. Előadások a számítástechnikából 3542, Springer 2005, 183–198
• GS Cseitin: A deriváció összetettségéről a propozíciós számításban . In: Slisenko, AO (szerk.) Structures in Constructive Mathematics and Mathematical Logic, II. Rész, Seminars in Mathematics (oroszból fordítva), 115–125. Steklov Matematikai Intézet (1968)

Külső linkek

• "Konjunktív normál forma" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Java kisalkalmazás CNF -re és DNF -re konvertáláshoz, a használt törvények bemutatásával