Spójna forma normalna - Conjunctive normal form

W operacji logicznych , A wzór jest spojówek postaci normalnej ( CNF ) lub clausal postaci normalnej , jeśli jest to połączenie jednej lub większej liczby klauzul , w którym punkt JeSt alternatywą z literałach ; inaczej mówiąc, jest to iloczyn sum lub AND z OR . Jako kanoniczna forma normalna jest użyteczna w automatycznym dowodzeniu twierdzeń i teorii obwodów .

Wszystkie koniunkcje literałów i wszystkie alternatywy literałów są w CNF, ponieważ można je postrzegać odpowiednio jako koniunkcje klauzul jednoliterowych i koniunkcje pojedynczej klauzuli. Podobnie jak w dysjunktywnej postaci normalnej (DNF), jedynymi spójnikami zdaniowymi, które może zawierać formuła w CNF, są i , lub , i nie . Operator not może być używany tylko jako część literału, co oznacza, że ​​może poprzedzać tylko zmienną zdaniową lub symbol predykatu .

W automatycznym dowodzeniu twierdzeń pojęcie „ klauzalna forma normalna ” jest często używane w węższym znaczeniu, oznaczającym konkretną reprezentację formuły CNF jako zbiór zbiorów literałów.

Przykłady i nieprzykłady

Wszystkie poniższe formuły w zmiennych , i są w spójnej postaci normalnej: ${\displaystyle A,B,C,D,E}$${\ Displaystyle F}$

• ${\ Displaystyle (A \ lor \ neg B \ lor \ neg C) \ ziemia (\ neg d \ lor e \ lor f)}$
• ${\displaystyle (A\lub B)\ziemia (C)}$
• ${\ Displaystyle (A\lub B)}$
• ${\ Displaystyle (A)}$

Dla jasności zdania rozłączne są napisane w nawiasach powyżej. W rozłącznej formie normalnej ze zdaniami łączącymi w nawiasach, ostatni przypadek jest taki sam, ale przedostatni to . Stałe prawda i fałsz są oznaczone pustą koniunkcją i jedną klauzulą ​​składającą się z pustej koniunkcji, ale zwykle są napisane wprost. ${\ Displaystyle (A) \ lub (B)}$

Poniższe formuły nie są połączone w normalnej postaci:

• ${\ Displaystyle \ neg (B \ lub C)}$, ponieważ OR jest zagnieżdżony w NOT
• ${\ Displaystyle (A \ ziemia B) \ lub C}$
• ${\displaystyle A\land (B\lor (D\land E))}$, ponieważ AND jest zagnieżdżony w OR

Każdą formułę można równoważnie zapisać jako formułę w postaci normalnej. Trzy nieprzykłady w CNF to:

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

Konwersja do CNF

Każdą formułę zdaniową można przekształcić w równoważną formułę, która jest w CNF. Przekształcenie to opiera się na regułach dotyczących równoważności logicznych : eliminacji podwójnej negacji , prawach De Morgana i prawie dystrybutywnym .

Ponieważ wszystkie formuły zdaniowe mogą być przekształcone w równoważne formuły w spójnej formie normalnej, dowody często opierają się na założeniu, że wszystkie formuły są CNF. Jednak w niektórych przypadkach ta konwersja do CNF może prowadzić do wykładniczej eksplozji formuły. Na przykład przetłumaczenie następującej formuły innej niż CNF na CNF daje formułę z klauzulami: ${\ Displaystyle 2 ^ {n}}$

${\ Displaystyle (X_ {1} \ klin Y_ {1}) \ vee (X_ {2} \ klin Y_ {2}) \ vee \ kropki \ vee (X_ {n} \ klin Y_ {n}).}$

W szczególności wygenerowana formuła to:

${\ Displaystyle (X_ {1} \ Vee X_ {2} \ Vee \ cdots \ Vee X_ {n}) \ klin (Y_ {1} \ Vee X_ {2} \ Vee \ cdots \ Vee X_ {n}) \ klin (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}).}$

Ta formuła zawiera klauzule; każda klauzula zawiera albo albo dla każdego . ${\ Displaystyle 2 ^ {n}}$${\ Displaystyle X_ {i}}$${\ Displaystyle Y_ {i}}$${\displaystyle i}$

Istnieją przekształcenia w CNF, które unikają wykładniczego wzrostu rozmiaru poprzez zachowanie spełnialności, a nie równoważności . Te przekształcenia gwarantują tylko liniowy wzrost rozmiaru formuły, ale wprowadzają nowe zmienne. Na przykład powyższy wzór można przekształcić w CNF, dodając zmienne w następujący sposób: ${\ Displaystyle Z_ {1}, \ ldots, Z_ {n}}$

${\ Displaystyle (Z_ {1} \ Vee \ cdots \ Vee Z_ {n}) \ klin (\ neg Z_ {1} \ vee X {1}) \ klin (\ neg Z_ {1} \ vee Y_ {1} )\wedge \cdots \wedge (\neg Z_{n}\vee X_{n})\wedge (\neg Z_{n}\vee Y_{n}).}$

Interpretacja spełnia ten wzór tylko wtedy, gdy co najmniej jeden z nowych zmiennych jest prawdą. Jeśli ta zmienna to , to oba i również są prawdziwe. Oznacza to, że każdy model, który spełnia tę formułę, spełnia również wymagania oryginalnego. Z drugiej strony, tylko niektóre modele oryginalnej formuły spełniają ten warunek: ponieważ nie są one wymienione w oryginalnej formule, ich wartości są nieistotne dla jej spełnienia , co nie ma miejsca w ostatniej formule. Oznacza to, że oryginalna formuła i wynik tłumaczenia są równoważne, ale nie równoważne . ${\ Displaystyle Z_ {i}}$${\ Displaystyle X_ {i}}$${\ Displaystyle Y_ {i}}$${\ Displaystyle Z_ {i}}$

Alternatywne tłumaczenie, transformacja Tseitina , zawiera również klauzule . Z tych klauzul formuła implikuje ; ta formuła jest często uważana za „definicję” jako nazwę dla . ${\ Displaystyle Z_ {i} \ vee \ neg X_ {i} \ vee \ neg Y_ {i}}$${\ Displaystyle Z_ {i} \ równoważny X_ {i} \ klin Y_ {i}}$${\ Displaystyle Z_ {i}}$${\ Displaystyle X_ {i} \ klin Y_ {i}}$

Logika pierwszego rzędu

W logice pierwszego rzędu, spójna forma normalna może być dalej rozwijana, aby uzyskać klasyczną formę normalną formuły logicznej, która może być następnie użyta do wykonania rozwiązania pierwszego rzędu . W automatycznym dowodzeniu twierdzeń w oparciu o rozdzielczość, formuła CNF

${\styl wyświetlania (}$

${\ Displaystyle l_ {11}}$

${\displaystyle \lor}$

${\displaystyle \ldots}$

${\displaystyle \lor}$

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

${\ Displaystyle )}$

${\displaystyle \land}$

${\displaystyle \ldots}$

${\displaystyle \land}$

${\styl wyświetlania (}$

${\ Displaystyle l_ {m1}}$

${\displaystyle \lor}$

${\displaystyle \ldots}$

${\displaystyle \lor}$

${\ Displaystyle l_ {mn_ {m}}}$

${\ Displaystyle )}$

, z literałami, jest powszechnie reprezentowany jako zbiór zbiorów ${\displaystyle l_{ij}}$

${\ Displaystyle \ {}$

${\ Displaystyle \ {}$

${\ Displaystyle l_ {11}}$

${\styl wyświetlania,}$

${\displaystyle \ldots}$

${\styl wyświetlania,}$

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

${\ Displaystyle \}}$

${\styl wyświetlania,}$

${\displaystyle \ldots}$

${\styl wyświetlania,}$

${\ Displaystyle \ {}$

${\ Displaystyle l_ {m1}}$

${\styl wyświetlania,}$

${\displaystyle \ldots}$

${\styl wyświetlania,}$

${\ Displaystyle l_ {mn_ {m}}}$

${\ Displaystyle \}}$

${\ Displaystyle \}}$

.

Zobacz poniżej przykład.

Złożoność obliczeniowa

Ważny zestaw problemów związanych ze złożonością obliczeniową polega na znalezieniu przypisań do zmiennych formuły logicznej wyrażonej w Spójnej Formie Normalnej, tak aby formuła była prawdziwa. Problem k- SAT polega na znalezieniu satysfakcjonującego przypisania do formuły logicznej wyrażonej w CNF, w której każda alternatywa zawiera co najwyżej k zmiennych. 3-SAT jest NP-zupełny (jak inne k problemu -sat z k > 2) w czasie 2-SAT jest znane są rozwiązania, w czasie wielomianowym . W konsekwencji zadanie przekształcenia formuły w DNF z zachowaniem spełnialności jest NP-trudne ; podwójnie konwersja do CNF z zachowaniem ważności jest również NP-trudna; stąd konwersja z zachowaniem równoważności do DNF lub CNF jest znowu NP-trudna.

Typowe problemy w tym przypadku dotyczą formuł w „3CNF”: spójna postać normalna z nie więcej niż trzema zmiennymi na spójnik. Przykłady takich formuł spotykanych w praktyce mogą być bardzo duże, na przykład ze 100 000 zmiennych i 1 000 000 koniunkcji.

Formuła z nanowłókien można przekształcić w equisatisfiable wzorze, w „ k CNF” (dla k ≥3) zastępując co koniunkcji z więcej niż k zmiennych dwóch conjuncts i z Z nowej zmiennej i powtarzając tak często, jak to konieczne. ${\ 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}}$

Konwersja z logiki pierwszego rzędu

Aby przekonwertować logikę pierwszego rzędu na CNF:

1. Konwertuj na postać normalną negacji .
   1. Wyeliminować implikacji i równoważności: wielokrotnie zastąpić z ; wymienić z . Ostatecznie wyeliminuje to wszystkie wystąpienia i .${\displaystyle P\rightarrow Q}$${\ Displaystyle \ nie P \ lub Q}$${\displaystyle P\leftrightarrow Q}$${\ Displaystyle (p \ lor \ nie Q) \ ziemia (\ nie P \ lor Q)}$${\displaystyle \rightarrow}$${\displaystyle \leftrightarrow}$
   2. Przenieś NIE do wewnątrz, wielokrotnie stosując Prawo De Morgana . W szczególności należy wymienić w ; zastąpić z ; i wymienić z ; zastąpić z ; z . Po tym, a może wystąpić tylko bezpośrednio przed symbolem predykatu.${\ Displaystyle \ lnot (P \ lub Q)}$${\ Displaystyle (\ nie P) \ ziemia (\ nie Q)}$${\ Displaystyle \ lnot (P \ ziemia Q)}$${\ Displaystyle (\ nie P) \ lub (\ nie Q)}$${\ Displaystyle \ nie \ nie P}$${\displaystyle P}$${\displaystyle \lnot (\forall xP(x))}$${\ Displaystyle \ istnieje x \ nie P (x)}$${\displaystyle \lnot (\istnieje xP(x))}$${\ Displaystyle \ dla wszystkich x \ nie P (x)}$${\ Displaystyle \ nie}$
2. Standaryzuj zmienne
   1. W przypadku zdań, które używają tej samej nazwy zmiennej dwukrotnie, zmień nazwę jednej ze zmiennych. Pozwala to uniknąć późniejszych nieporozumień podczas upuszczania kwantyfikatorów. Na przykład zmieniono nazwę na .${\displaystyle (\forall xP(x))\lor(\istnieje xQ(x))}$${\ Displaystyle \ forall x [\ istnieje r \ operatorname {zwierzę} (y) \ ziemia \ nie \ operatorname {miłość} (x, y)] \ lub [\ istnieje r \ operatorname {miłość} (y, x)] }$${\ Displaystyle \ forall x [\ istnieje r \ operatorname {zwierzę} (y) \ ziemia \ nie \ operatorname {miłość} (x, y)] \ lub [\ istnieje z \ operatorname {miłość} (z, x)] }$
3. Skolemizuj oświadczenie
   1. Poruszać kwantyfikatorów zewnątrz: niejednokrotnie zastąpić z ; zastąpić z ; zastąpić z ; wymienić z . Te zastąpienia zachowują równoważność, ponieważ poprzedni krok standaryzacji zmiennej zapewniał, że nie występuje w . Po tych wymian kwantyfikator może występować tylko w początkowej prefiksu wzoru, ale nie Wewnątrz , lub .${\displaystyle P\land (\forall xQ(x))}$${\ Displaystyle \ forall x (P \ land Q (x))}$${\displaystyle P\lor (\forall xQ(x))}$${\ Displaystyle \ forall x (P \ lub Q (x))}$${\displaystyle P\land (\istnieje xQ(x))}$${\ Displaystyle \ istnieje x (P \ ziemi Q (x))}$${\displaystyle P\lor (\istnieje xQ(x))}$${\ Displaystyle \ istnieje x (P \ lub Q (x))}$${\displaystyle x}$${\displaystyle P}$${\ Displaystyle \ nie}$${\displaystyle \land}$${\displaystyle \lor}$
   2. Wielokrotnie zastąpić z , gdzie jest to nowy symbol funkcja -ary, tak zwany „ funkcja Skolem ”. To jedyny krok, który zachowuje tylko satysfakcję, a nie równoważność. Eliminuje wszystkie kwantyfikatory egzystencjalne.${\ Displaystyle \ forall x_ {1} \ ldots \ forall x_ {n} \; \ istnieje y \; P (y)}$${\ Displaystyle \ forall x_ {1} \ ldots \ forall x_ {n} \; P (f (x_ {1}, \ ldots, x_ {n}))}$${\displaystyle f}$${\ Displaystyle n}$
4. Usuń wszystkie uniwersalne kwantyfikatory.
5. Rozpowszechniać RNO do wewnątrz nad AND: wielokrotnie zastąpić z .${\displaystyle P\lor (Q\land R)}$${\ Displaystyle (P \ lor Q) \ ziemia (P \ lor R)}$

Na przykład formuła mówiąca „Każdy, kto kocha wszystkie zwierzęta, jest z kolei kochany przez kogoś” jest przekształcana w CNF (a następnie w formę klauzuli w ostatnim wierszu) w następujący sposób (podkreślając przekształcenia reguły zastępowania w ): ${\ Displaystyle {\ kolor {czerwony} {\ tekst {czerwony}}}}$

${\displaystyle \forall x}$

${\styl wyświetlania (}$

${\displaystyle \forall y}$

${\displaystyle \mathrm {zwierzę} (}$

${\displaystyle y}$

${\ Displaystyle )}$

${\displaystyle \kolor {czerwony}\rightarrow}$

${\displaystyle \mathrm {miłość} (x,}$

${\displaystyle y}$

${\ Displaystyle )}$

${\ Displaystyle )}$

${\displaystyle \rightarrow}$

${\styl wyświetlania (}$

${\displaystyle \istnieje}$

${\displaystyle y}$

${\displaystyle \mathrm {miłość} (}$

${\displaystyle y}$

${\displaystyle ,x)}$

${\ Displaystyle )}$

${\displaystyle \forall x}$

${\styl wyświetlania (}$

${\displaystyle \forall y}$

${\ Displaystyle \ nie}$

${\displaystyle \mathrm {zwierzę} (}$

${\displaystyle y}$

${\ Displaystyle )}$

${\displaystyle \lor}$

${\displaystyle \mathrm {miłość} (x,}$

${\displaystyle y}$

${\ Displaystyle )}$

${\ Displaystyle )}$

${\displaystyle \kolor {czerwony}\rightarrow}$

${\styl wyświetlania (}$

${\displaystyle \istnieje}$

${\displaystyle y}$

${\displaystyle \mathrm {miłość} (}$

${\displaystyle y}$

${\displaystyle ,x)}$

${\ Displaystyle )}$

o 1,1

${\displaystyle \forall x}$

${\ Displaystyle \ kolor {czerwony} \ nie}$

${\styl wyświetlania (}$

${\displaystyle {\kolor {czerwony}{\forall y}}}$

${\ Displaystyle \ nie}$

${\displaystyle \mathrm {zwierzę} (}$

${\displaystyle y}$

${\ Displaystyle )}$

${\displaystyle \lor}$

${\displaystyle \mathrm {miłość} (x,}$

${\displaystyle y}$

${\ Displaystyle )}$

${\ Displaystyle )}$

${\displaystyle \lor}$

${\styl wyświetlania (}$

${\displaystyle \istnieje}$

${\displaystyle y}$

${\displaystyle \mathrm {miłość} (}$

${\displaystyle y}$

${\displaystyle ,x)}$

${\ Displaystyle )}$

o 1,1

${\displaystyle \forall x}$

${\styl wyświetlania (}$

${\displaystyle \istnieje y}$

${\ Displaystyle \ kolor {czerwony} \ nie}$

${\styl wyświetlania (}$

${\ Displaystyle \ nie}$

${\displaystyle \mathrm {zwierzę} (}$

${\displaystyle y}$

${\ Displaystyle )}$

${\displaystyle \kolor {czerwony}\lub}$

${\displaystyle \mathrm {miłość} (x,}$

${\displaystyle y}$

${\ Displaystyle )}$

${\ Displaystyle )}$

${\ Displaystyle )}$

${\displaystyle \lor}$

${\styl wyświetlania (}$

${\displaystyle \istnieje}$

${\displaystyle y}$

${\displaystyle \mathrm {miłość} (}$

${\displaystyle y}$

${\displaystyle ,x)}$

${\ Displaystyle )}$

o 1,2

${\displaystyle \forall x}$

${\styl wyświetlania (}$

${\displaystyle \istnieje y}$

${\ Displaystyle \ kolor {czerwony} \ nie}$

${\ Displaystyle \ kolor {czerwony} \ nie}$

${\displaystyle \mathrm {zwierzę} (}$

${\displaystyle y}$

${\ Displaystyle )}$

${\displaystyle \land}$

${\ Displaystyle \ nie}$

${\displaystyle \mathrm {miłość} (x,}$

${\displaystyle y}$

${\ Displaystyle )}$

${\ Displaystyle )}$

${\displaystyle \lor}$

${\styl wyświetlania (}$

${\displaystyle \istnieje}$

${\displaystyle y}$

${\displaystyle \mathrm {miłość} (}$

${\displaystyle y}$

${\displaystyle ,x)}$

${\ Displaystyle )}$

o 1,2

${\displaystyle \forall x}$

${\styl wyświetlania (}$

${\displaystyle {\kolor {czerwony}{\istnieje y}}}$

${\displaystyle \mathrm {zwierzę} (}$

${\displaystyle y}$

${\ Displaystyle )}$

${\displaystyle \land}$

${\ Displaystyle \ nie}$

${\displaystyle \mathrm {miłość} (x,}$

${\displaystyle y}$

${\ Displaystyle )}$

${\ Displaystyle )}$

${\displaystyle \lor}$

${\styl wyświetlania (}$

${\ Displaystyle \ kolor {czerwony} \ istnieje}$

${\displaystyle \kolor {czerwony}y}$

${\displaystyle \mathrm {miłość} (}$

${\displaystyle y}$

${\displaystyle ,x)}$

${\ Displaystyle )}$

o 1,2

${\displaystyle \forall x}$

${\styl wyświetlania (}$

${\displaystyle \istnieje y}$

${\displaystyle \mathrm {zwierzę} (}$

${\displaystyle y}$

${\ Displaystyle )}$

${\displaystyle \land}$

${\ Displaystyle \ nie}$

${\displaystyle \mathrm {miłość} (x,}$

${\displaystyle y}$

${\ Displaystyle )}$

${\ Displaystyle )}$

${\displaystyle \kolor {czerwony}\lub}$

${\styl wyświetlania (}$

${\ Displaystyle \ kolor {czerwony} \ istnieje}$

${\ Displaystyle \ kolor {czerwony} z}$

${\displaystyle \mathrm {miłość} (}$

${\displaystyle z}$

${\displaystyle ,x)}$

${\ Displaystyle )}$

o 2

${\displaystyle \forall x}$

${\ Displaystyle \ istnieje z}$

${\styl wyświetlania (}$

${\displaystyle {\kolor {czerwony}{\istnieje y}}}$

${\displaystyle \mathrm {zwierzę} (}$

${\displaystyle y}$

${\ Displaystyle )}$

${\displaystyle \land}$

${\ Displaystyle \ nie}$

${\displaystyle \mathrm {miłość} (x,}$

${\displaystyle y}$

${\ Displaystyle )}$

${\ Displaystyle )}$

${\displaystyle \kolor {czerwony}\lub}$

${\displaystyle \mathrm {miłość} (}$

${\displaystyle z}$

${\displaystyle ,x)}$

o 3,1

${\displaystyle \forall x}$

${\displaystyle {\kolor {czerwony}{\istnieje z}}}$

${\displaystyle \istnieje y}$

${\styl wyświetlania (}$

${\displaystyle \mathrm {zwierzę} (}$

${\displaystyle y}$

${\ Displaystyle )}$

${\displaystyle \land}$

${\ Displaystyle \ nie}$

${\displaystyle \mathrm {miłość} (x,}$

${\displaystyle y}$

${\ Displaystyle )}$

${\ Displaystyle )}$

${\displaystyle \lor}$

${\displaystyle \mathrm {miłość} (}$

${\displaystyle z}$

${\displaystyle ,x)}$

o 3,1

${\displaystyle \forall x}$

${\displaystyle {\kolor {czerwony}{\istnieje y}}}$

${\styl wyświetlania (}$

${\displaystyle \mathrm {zwierzę} (}$

${\displaystyle y}$

${\ Displaystyle )}$

${\displaystyle \land}$

${\ Displaystyle \ nie}$

${\displaystyle \mathrm {miłość} (x,}$

${\displaystyle y}$

${\ Displaystyle )}$

${\ Displaystyle )}$

${\displaystyle \lor}$

${\displaystyle \mathrm {miłość} (}$

${\displaystyle g(x)}$

${\displaystyle ,x)}$

o 3.2

${\styl wyświetlania (}$

${\displaystyle \mathrm {zwierzę} (}$

${\displaystyle f(x)}$

${\ Displaystyle )}$

${\ Displaystyle \ kolor {czerwony} \ ziemia}$

${\ Displaystyle \ nie}$

${\displaystyle \mathrm {miłość} (x,}$

${\displaystyle f(x)}$

${\ Displaystyle )}$

${\ Displaystyle )}$

${\displaystyle \kolor {czerwony}\lub}$

${\displaystyle \mathrm {miłość} (}$

${\displaystyle g(x)}$

${\displaystyle ,x)}$

o 4

${\styl wyświetlania (}$

${\displaystyle \mathrm {zwierzę} (}$

${\displaystyle f(x)}$

${\ Displaystyle )}$

${\displaystyle \kolor {czerwony}\lub}$

${\displaystyle \mathrm {miłość} (}$

${\displaystyle g(x)}$

${\displaystyle ,x)}$

${\ Displaystyle )}$

${\ Displaystyle \ kolor {czerwony} \ ziemia}$

${\styl wyświetlania (}$

${\ Displaystyle \ nie \ operatorka {miłość} (x, f (x))}$

${\displaystyle \kolor {czerwony}\lub}$

${\ Displaystyle \ operatorname {Miłość} (g (x), x)}$

${\ Displaystyle )}$

o 5

${\ Displaystyle \ {}$

${\ Displaystyle \ {}$

${\displaystyle \mathrm {zwierzę} (}$

${\displaystyle f(x)}$

${\ Displaystyle )}$

${\styl wyświetlania,}$

${\displaystyle \mathrm {miłość} (}$

${\displaystyle g(x)}$

${\displaystyle ,x)}$

${\ Displaystyle \}}$

${\styl wyświetlania,}$

${\ Displaystyle \ {}$

${\ Displaystyle \ nie \ operatorka {miłość} (x, f (x))}$

${\styl wyświetlania,}$

${\ Displaystyle \ operatorname {Miłość} (g (x), x)}$

${\ Displaystyle \}}$

${\ Displaystyle \}}$

( reprezentacja klauzuli )

Nieformalnie, funkcja Skolema może być traktowana jako oddanie osoby, przez którą jest kochana, a jednocześnie oddanie zwierzęcia (jeśli w ogóle), które nie kocha. Trzecia linijka od dołu brzmi " nie kocha zwierzęcia , albo jest kochany przez " . ${\displaystyle g(x)}$${\displaystyle x}$${\displaystyle f(x)}$${\displaystyle x}$${\displaystyle x}$${\displaystyle f(x)}$${\displaystyle x}$${\displaystyle g(x)}$

Druga ostatnia linia od góry , to CNF. ${\ Displaystyle ( \ operatorname {zwierzę} (f (x)) \ lub \ operatorname {miłość} (g (x), x)) \ ziemi (\ nie \ operatorname {kocha} (x, f (x))\ lor \mathrm {Miłość} (g(x),x))}$

Uwagi

Zobacz też

• Algebraiczna postać normalna
• Rozdzielna forma normalna
• Klauzula róg
• Algorytm Quine'a-McCluskeya

Bibliografia

• J. Eldon Whitesitt (24 maja 2012). Algebra Boole'a i jej zastosowania . Korporacja kurierska. Numer ISBN 978-0-486-15816-7.
• Hansa Kleine Buninga; Theodor Lettmann (28 sierpnia 1999). Logika zdań: dedukcja i algorytmy . Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 978-0-521-63017-7.
• Paul Jackson, Daniel Sheridan: Konwersje formularzy klauzul dla obwodów logicznych . W: Holger H. Hoos, David G. Mitchell (red.): Theory and Applications of Satisfiability Testing, 7. Międzynarodowa Konferencja, SAT 2004, Vancouver, BC, Kanada, 10–13 maja 2004, Revised Selected Papers. Notatki z wykładu z informatyki 3542, Springer 2005, s. 183–198
• GS Tseitin: O złożoności wyprowadzania w rachunku zdań . W: Slisenko, AO (red.) Structures in Constructive Mathematics and Mathematical Logic, część II, Seminaria z matematyki (przetłumaczone z rosyjskiego), s. 115–125. Instytut Matematyczny Steklov (1968)

Zewnętrzne linki

• „Spójna forma normalna” , Encyklopedia Matematyki , EMS Press , 2001 [1994]
• Aplet Java do konwersji do CNF i DNF, pokazujący zastosowane prawa