Iti0210ex72

Konjunktiivne normaalkuju (CNF)

Teisendame konjunktiivsele normaalkujule:

1. A <=> (B v C)

Ekvivalentsus <=> tähendab, et seos kehtib mõlemat pidi:

2a. A => (B v C)
2b. (B v C) => A

Asendame mõlemas valemis implikatsioonitehte =>:

3a. -A v (B v C)
3b. -(B v C) v A

Esimeses (3a) võib lihtsalt sulud ära jätta, teisel juhul (3b) tuleb aga DeMorgani seadust rakendada:

4b. (-B & -C) v A

Peale sulgude avamist saame:

5b. (-B v A) &  (-C v A)

Ehk siis kokku saime disjunktid (clause), mis kõik samal ajal kehtivad (mõtle, et ridade vahel on "&"):

-A v B v C
-B v A
-C v A

Ülesanne

Tee nüüd ise sama teisendus kollimaailma reegliga B₂₂ <=> (P₁₂ v P₂₁ v P₂₃ v P₃₂).

CNF teisendus on toodud ka slaididel, lk 68.