Normální formy formulí výrokové logiky
Literál je ten nejmenjší výrokový symbol nebo jeho negace. Př.: p, ¬r, ...
Elementární konjunkce (EK) je konjunkce literálů. Př.: p ∧ r, p ∧ ¬p, ...
Elementární disjunkce (ED) je disjunkce literálů. Př.: p ∨ r, p ∨ ¬p, ...
Úplná elementární konjunkce (ÚEK) je elementární konjunkce, ve které se každý symbol z dané množiny výrokových symbolů vyskytuje právě jednou. Př.: p ∧ ¬q
Úplná elementární disjunkce (ÚED) je elementární disjunkce, ve které se každý symbol z dané množiny symbolů vyskytuje právě jednou. Př.: p ∨ ¬q
Disjunktivní normální forma (DNF) dané formule je ekvivalentní tvar formule mající tvar disjunkce elementárních konjunkcí. Př. DNF: (p ∧ p) ∨ (¬p ∧ ¬r), p ∨ ¬p
Konjunktivní normální forma (KNF) dané formule je ekvivalentní tvar formule mající tvar konjunkce elementárních disjunkcí. Př. KNF: (r ∨ p) ∧ (¬p ∨ p)
Úplná disjunktivní normální forma (UDNF) dané formule je ekvivalentní tvar formule mající tvar disjunkce úplných elementárních konjunkcí. Př. UDNF: (p ∧ q) ∨ (¬p ∧ ¬q) ...z množiny {p,q}
Úplná konjunktivní normální forma (UKNF) dané formule je ekvivalentní formule mající tvar konjunkce úplných elementárních disjunkcí. Př. UKNF: (¬p ∨ q) ∧ (¬q ∨ p) ...z množiny {p,q}
ÚDNF a UKNF dané formule nazýváme kanonickými (standardním) tvary této formule.
Jak nalézt UDNF a UKNF?
(1) Buď můžeme tvar vytvořit pomocí ekvivalentních úprav:
Př.: ¬(p É q) ⇔ ¬(¬p ∨ q) ⇔ (p ∧ ¬q) ...UDNF ⇔[p ∨ (q ∧ ¬q)] ∧ [¬q ∨ (p ∧ ¬p)]
⇔ (p ∨ q) ∧ (p ∨ ¬q) ∧ (¬p ∨ ¬q) ...UKNF
(2) Nebo pomocí tabulky:
Př.: ¬(p É q)
- vytvoříme si pro formuli pravdivostní tabulku a na konci vytvoříme další 2 sloupce pro úplnou konjunktivní formu a úplnou disjunktivní formu
- postupujeme tak, že tam kde vyšla 1 (pro model formule) vyplníme do UEK formuli, kterou jsme vytvořili na základě valuací výrokových symbolů v 1. a 2. sloupci a spojili pomocí konjunkce ∧
- při hledání UED, tam kde nám vyšla 0 vyplníme formuli z negovaných valuací výrokových symbolů p a q a spojíme disjunkcí ∨
UDNF: p ∧ ¬q ...vypíšeme všechny UEK spojené disjunkcí
UDNF: (¬p ∨ ¬q) ∧ (p ∨ ¬q) ∧ (p ∨ q) ...vypíšeme všechny UED spojené konjukncí