09 Úplná disjunktivní /konjunktivní normální forma

  1. 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
  2. Df Literál
    • Literálem je libovolná atomická formule nebo negace atomické formule.
    • například: p2, ¬p1; nikoli ale: p1 ∨ ¬p2
  3. 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
  4. 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)
  5. 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)
  6. 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.
  7. Příklad- převod formule p → (q → p) na ÚDNF
    • Image Upload 1
    • Image Upload 2
  8. Ú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
  9. jak sestavíme minimalizační algoritmus?
    • Image Upload 3
    • Image Upload 4
  10. sestavte ÚDNF a minimalizujte ji
    daná formule je ((p → (q ∧ ¬q)) → p
    Image Upload 5
  11. sestavte ÚDNF a minimalizujte ji
    daná formule je ((p → q) → q) → q
    Image Upload 6
  12. sestavte ÚDNF a minimalizujte ji
    daná formule je  (p → (q → p)) → r
    Image Upload 7
  13. sestavte ÚDNF a minimalizujte ji
    daná formule je  (p → q) ∧ (¬q → r)
    Image Upload 8
Author
iren
ID
354245
Card Set
09 Úplná disjunktivní /konjunktivní normální forma
Description
VÝROKOVÁ LOGIKA
Updated