Konjunktivní normální forma

Konjunktivní normální forma ( CNF ) v booleovské logice  je normální forma , ve které má booleovská formule formu konjunkce disjunkcí literálů . Konjunktivní normální forma je vhodná pro automatické dokazování věty . Jakýkoli booleovský vzorec lze převést na CNF. [1] K tomu můžete použít: zákon dvojí negace , de Morganův zákon , distributivita .

Příklady a protipříklady

Vzorce v CNF :

Vzorce , které nejsou v CNF :

Ale tyto 3 vzorce nejsou v CNF ekvivalentní následujícím vzorcům v CNF:

Konstrukce CNF

Algoritmus pro konstrukci CNF

1) Zbavte se všech logických operací obsažených ve vzorci a nahraďte je těmi hlavními: konjunkce, disjunkce, negace. To lze provést pomocí ekvivalentních vzorců:

2) Nahraďte znaménko negace odkazující na celý výraz za znaménko negace odkazující na jednotlivé výroky proměnných na základě vzorců:

3) Zbavte se dvojitých negativních znamének.

4) Aplikujte, je-li to nutné, na operace konjunkce a disjunkce vlastnosti vzorců distributivity a absorpce.

Příklad konstrukce CNF

Zredukujeme vzorec na CNF

Převedeme vzorec na vzorec, který neobsahuje :

Ve výsledném vzorci převedeme negaci na proměnné a snížíme dvojité negace:

Podle zákona distributivity dostaneme CNF:

k -konjunktivní normální tvar

K -konjunktivní normální forma je konjunktivní normální forma, ve které každá disjunkce obsahuje přesně k literálů .

Například následující vzorec je napsán v 2-CNF:

Přechod z KNF na SKNF

Pokud v jednoduché disjunkci nějaká proměnná chybí (například z), pak k ní přidáme výraz: (tím se samotná disjunkce nemění), načež závorky otevřeme pomocí distribučního zákona :

SKNF se tedy získává z CNF.

Formální gramatika popisující CNF

Následující formální gramatika popisuje všechny vzorce redukované na CNF:

<CNF> → <disjunkt> <CNF> → <CNF> ∧ <disjunkt> <disjunkt> → <doslovný>; <disjunkt> → (<disjunct> ∨ <literal>) <doslovný> → <termín> <doslovný> → ¬<termín>

kde <term> označuje libovolnou booleovskou proměnnou.

Problém splnitelnosti pro vzorec v CNF

V teorii výpočetní složitosti hraje důležitou roli problém splnitelnosti booleovských formulí v konjunktivním normálním tvaru. Podle Cookova teorému je tento problém NP-úplný a redukuje se na problém splnitelnosti pro vzorce v 3-CNF, který se redukuje a na který se postupně redukují další NP-úplné problémy .

Problém splnitelnosti pro vzorce 2-CNF lze vyřešit v lineárním čase.

Vlastnosti zápisu

Je třeba poznamenat, že pro usnadnění vnímání jsou symboly aritmetického násobení a sčítání často používány jako označení pro konjunkci a disjunkci, zatímco symbol násobení je často vynechán. V tomto případě vzorce Booleovské algebry vypadají jako algebraické polynomy, což je oku známější, ale někdy to může vést k nedorozuměním.

Například následující položky jsou ekvivalentní:

Z tohoto důvodu se CNF v ruskojazyčné literatuře někdy nazývá „součin součtů“, což je pauzovací papír z anglického výrazu „produkt součtů“.

Viz také

Poznámky

  1. ↑ Pozdnyakov S.N., Rybin S.V. Diskrétní matematika. - S. 303.

Literatura

Odkazy