DNF, KNF
Tak jako se matematika snaží vyjádřit složité výrazy v nějaké přehlednější formě (například číslo 0,000 000 3 je přehlednější ve tvaru 3 ×10-7 ), podobně i v logice se formule pro speciální účely vyjadřují v tzv. normálních formách. Pro tyto speciální formy formule je charakteristické, že využívají jen spojek .
Každou pravdivostní n-ární funkci f lze reprezentovat formulí výrokové logiky, která obsahuje pouze spojky negace a konjunkce, resp. disjunkce, . Učiňme dohodu, že výrazem konjunkce, resp. disjunkce, rozumíme formuli, která spojuje spojkou konjunkce, resp. disjunkce, n atomických formulí.
Literály jsou atomické formule a negace atomických formulí.
Formule A je disjunktivní normální formou (DNF) nad atomickými formulemi , je-li A tvaru disjunkce, jejíž každý člen je konjunkcí nějakých literálů z
nebo literálem. Úplná disjunktivní normální forma formule A je její disjunktivní normální forma, v níž každý disjunkt obsahuje literály všech výrokových proměnných vyskytujících se ve formuli A.
Příkladem formule v DNF je
.
Formule A je konjunktivní normální formou (KNF) nad atomickými formulemi , je-li A tvaru konjunkce, jejíž každý člen je disjunkcí nějakých literálů z
nebo literálem. Úplná konjunktivní normální forma formule A je její konjunktivní normální forma, v níž každý konjunkt obsahuje literály všech výrokových proměnných vyskytujících se ve formuli A.
Příkladem formule v CNF je
.
Ke každé formuli A výrokové logiky, která není tautologií (kontradikcí), lze najít formuli B, která je ve tvaru DNF (KNF) a je ekvivalentní s A (DNF nelze zkonstruovat pro kontradikce a KNF tedy nelze zkonstruovat pro tautologie).
Příklad:
Najděte úplnou NDF formule
.
Vyjdeme z pravdivostní tabulky této formule:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
Víme, že každý řádek pravdivostní tabulky odpovídá jednomu pravdivostnímu ohodnocení proměnných a příslušné hodnotě formule pro toto ohodnocení.
Aby tato tabulka byla pravdivostní tabulkou hledané formule A´ekvivalentní s A, musí být formule A´pravdivá ve všech ohodnoceních, kde má formule A v daném řádku hodnotu 1 a nepravdivá ve všech ostatních ohodnoceních.
Je zřejmé, že hodnota uvedené formule A je rovna 1 v jednom z těchto případů:
1. 2. 3. Totéž musí platit i o formuli A´. Toho dosáhneme tak, že formule A´ bude disjunkcí (má nastat alespoň jedna z možností ) formulí, které přesně popisují situaci řádku tabulky, kde má formule A hodnotu 1 (což jsou případy 1. až 3., které jsme získali z 2., 5., a 6. řádku ). První případ odpovídá ohodnocení, kdy proměnné a, b jsou nepravdivé a proměnná c je pravdivá - to popíšeme formulí
. Druhý případ odpovídá ohodnocení, kdy proměnná a je pravdivá a proměnné b, c jsou nepravdivé - tuto situaci popisuje formule
.
Zjistili jsme tedy, že přesně tentýž průběh hodnot jako formule
má v závislosti na ohodnocení proměnných formule
. Jedná se tedy o úplnou disjunktivní normální formu logicky ekvivalentní s původní formulí.
Příklad:
Najděte KNF formule
.
Vyjdeme opět z pravdivostní tabulky této formule:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
|
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
|
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
Podle výše uvedeného postupu je prvním krokem vytvoření negace formule A, ta je vytvořena v posledním sloupci tabulky
. Druhým krokem je vytvoření úplné disjunktivní normální formy formule
. Formule
je úplnou disjunktivní normální formou negace původní formule. Další negací a s využitím De Morganova pravidla lze pak tuto formuli převést do úplné konjunktivní normální formy formule původní:
V tomto případě je úplná konjunktivní normální forma konjunkcí tří klauzulí. Vhodnými úpravami pomocí ekvivalencí lze tuto formuli značně zjednodušit (na úkor její úplnosti).
