-
Df Věta o reprezentaci
- Každou pravdivostní n-ární funkci fn lze reprezentovat formulí, která obsahuje pouze spojky ¬, ∧, ∨.
- existují i věty o reprezentaci užívající jinou úplnou funkční sadu spojek
-
Df Literál
- Literálem je libovolná atomická formule nebo negace atomické formule.
- například: p2, ¬p1; nikoli ale: p1 ∨ ¬p2
-
Formule A je elementární konjunkcí nad p1, p2, . . . , pn právě tehdy, když ....
- je libovolnou konjunkcí literálů z formulí p1, p2, . . . , pn, přičemž se v této elementární konjunkci vyskytují jakožto literál právě jednou.
- například: p1 ∧ ¬p2; nikoli ale: p1 ∧ ¬p1
-
Formule A je v disjunktivní normální formě nad formulemi p1, p2, . . . , pn právě tehdy, když...
- A je disjunkcí elementárních konjunkcí literálů z formulí p1, p2, . . . , pn.
- například: (¬p1 ∧ p2) ∨ (p1 ∧ ¬p1)
-
Formule B je úplnou disjunktivní normální formou (ÚDNF) formule A právě tehdy, když ...
- B je ekvivalentní A, přičemž B je disjunkcí elementárních konjunkcí literálů z A, přičemž v každém jejím disjunktu se vyskytují všechny literály A právě jednou.
- například: (¬p1 ∧ p2) ∨ (p1 ∧ ¬p2)
-
Věta o reprezentaci pomocí ÚDNF (ÚKNF)
- úplnou konjunktivní normální formu (ÚKNF), a pomocné pojmy, definujeme podobně, ovšem duálně
- Ke každé formuli A, která není kontradikcí (resp. tautologií), lze najít formuli B, která je ve tvaru ÚDNF (resp. ÚKNF) a je ekvivalentní s A.
-
Příklad- převod formule p → (q → p) na ÚDNF
-
ÚDNF lze různými způsoby zjednodušovat; známé jsou Carnaughovy mapy, níže bude uplatněn upravená základní část Quine-McCluskeyho algoritmu. Při minimalizaci ÚDNF se uplatňuje následující tautologie-zákon ...
- (nechť l je nějaký literál a A je nějaká formule)
- ((A ∧ l) ∨ (A ∧ ¬l)) ↔ A
- zkrácený zápis této tautologie uplatněním výše uváděné konvence o vypouštění konjunkce a alternativního označení negace je (Al ∨ Al) ↔ A
- všimněme si, že redukci, resp. expanzi, lze uplatnit jen tehdy, pokud se podformule tvaru konjunkce liší pouze jedním literálem
-
jak sestavíme minimalizační algoritmus?
-
sestavte ÚDNF a minimalizujte ji
daná formule je ((p → (q ∧ ¬q)) → p
-
sestavte ÚDNF a minimalizujte ji
daná formule je ((p → q) → q) → q
-
sestavte ÚDNF a minimalizujte ji
daná formule je (p → (q → p)) → r
-
sestavte ÚDNF a minimalizujte ji
daná formule je (p → q) ∧ (¬q → r)
|
|
