Disjunktivní normální forma - Disjunctive normal form
![]() | Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto problémech na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)
|
v logická logika, a disjunktivní normální forma (DNF) je kanonická normální forma logického vzorce skládajícího se z disjunkce spojek; lze jej také popsat jako NEBO AND, a součet produktů, nebo (v filozofická logika ) a koncept klastru.[Citace je zapotřebí ] Jako normální forma, to je užitečné v automatizované dokazování věty.
Definice
Logický vzorec je považován za v DNF, pokud je a disjunkce jednoho nebo více spojky jednoho nebo více literály.[1]:153 Vzorec DNF je v plná disjunktivní normální forma pokud se každá z jejích proměnných objeví v každé konjunkci přesně jednou. Jako v konjunktivní normální forma (CNF), jedinými výrokovými operátory v DNF jsou a (∧), nebo (∨) a ne (¬). The ne operátor lze použít pouze jako součást literálu, což znamená, že může předcházet pouze a výroková proměnná.
Toto je a bezkontextová gramatika pro DNF:
- disjunkce → (spojení ∨ disjunkce)
- disjunkce → spojení
- spojení → (doslovný ∧ spojení)
- spojení → doslovný
- doslovný → ¬proměnná
- doslovný → proměnná
Kde proměnná je libovolná proměnná.
Například všechny následující vzorce jsou v DNF:
Následující vzorce jsou však ne v DNF:
- , protože OR je vnořené do NOT
- , protože AND je vnořeno do NOT
- , protože OR je vnořené do AND
Vzorec je v DNF, ale ne v plném DNF; ekvivalentní plná verze DNF je .
Převod na DNF


Převod vzorce na DNF zahrnuje použití logické ekvivalence, jako eliminace dvojí negace, De Morganovy zákony a distribuční právo.
Všechny logické vzorce lze převést do ekvivalentní disjunktivní normální formy.[1]:152–153V některých případech však může převod na DNF vést k exponenciální explozi vzorce. Například DNF logického vzorce následujícího formuláře má 2n podmínky:
Nějaké konkrétní Booleovská funkce může být reprezentován pouze jedním[poznámka 1] úplný disjunktivní normální forma, jedna z kanonické formy. Naproti tomu dva různé prostý disjunktivní normální tvary mohou označovat stejnou booleovskou funkci, viz obrázky.
Výpočetní složitost
The Booleovský problém uspokojivosti na konjunktivní normální forma vzorce je NP-tvrdé; podle princip duality, stejně tak i problém s padělatelností u vzorců DNF. Proto je co-NP-tvrdý rozhodnout, zda je vzorec DNF a tautologie.
Varianty
Důležitá variace použitá při studiu výpočetní složitost je k-DNF. Vzorec je v k-DNF pokud je v DNF a každá spojka obsahuje maximálně k literálů.
Viz také
- Algebraická normální forma - jiné běžné tvary logických vzorců
- Výroková logika
- Algoritmus Quine – McCluskey - získá minimální DNF pro danou booleovskou funkci
- Pravdivá tabulka
Poznámky
- ^ Ignorování variací založených na asociativitě a komutativitě AND a OR.
Reference
- David Hilbert; Wilhelm Ackermann (1999). Principy matematické logiky. American Mathematical Soc. ISBN 978-0-8218-2024-7.
- J. Eldon Whitesitt (24. května 2012). Booleova algebra a její aplikace. Courier Corporation. ISBN 978-0-486-15816-7.
- Colin Howson (11. října 2005). Logika se stromy: Úvod do symbolické logiky. Routledge. ISBN 978-1-134-78550-6.
- David Gries; Fred B. Schneider (22. října 1993). Logický přístup k diskrétní matematice. Springer Science & Business Media. str. 67–. ISBN 978-0-387-94115-8.