Úplné konjunktivní a disjunktivní normální formy

• Nechť $V$ je množina výrokových symbolů, pak:

  • literál nad $V$ = libovolný výrokový symbol z $V$ nebo jeho negace

  • úplná elementární konjunkce nad $V$ = libovolná konjunkce literálů, ve které se každý výrokový symbol z $V$ vyskytuje právě v jednom literálu

  • úplná elementární disjunkce nad $V$ = libovolná disjunkce literálů, ve které se každý výrokový symbol z $V$ vyskytuje právě v jednom literálu

  • úplná konjunktivní normální forma nad $V$ = je konjunkce úplných elementárních disjunkcí

  • úplná disjunktivní normální forma nad $V$ = je disjunkce úplných elementárních konjunkcí

  • ÚDNF se nedá vytvořit pokud se jedná o kontradikci a ÚKNF se nedá vytvořit pokud se jedná o tautologii

Vytvoření ÚDNF

• Pro každý řádek tabulky odpovídající ohodnocení $e$, při kterém má funkce $f$ hodnotu $1$ sestrojíme ÚEK, tak že
  • $p_i$ pro $e(p_i)=1$
  • $\neg p_i$ pro $e(p_i)=0$
• Výsledná ÚDNF je disjunkcí ÚEK z předchozího kroku

Vytvoření ÚKNF

• Pro každý řádek tabulky odpovídající ohodnocení $e$, při kterém má funkce $f$ hodnotu $0$ sestrojíme ÚED, tak že
  • $p_i$ pro $e(p_i)=0$
  • $\neg p_i$ pro $e(p_i)=1$
• Výsledná ÚKNF je konjunkcí ÚED z předchozího kroku

Příklad

Navigace

Předchozí: Booleovské funkce, funkčně úplné systémy Následující: Množiny, množinové operace, potenční množina, kartézský součin, číselné množiny, spočetné a nespočetné množiny Celý okruh: Výroková logika, formule, pravdivost, vyplývání