Корисник:ВисњаНоваковиц/Конјуктивна нормална форма

Конјуктивна нормална форма

Конјуктивна нормална форма је начин изражавања формуле у Буловој логици. Формула је у КНФ ако представља конјукцију клаузула, где свака клаузула представља дисјункцију литерала. Једини искази које КНФ може да садржи су И (∧), ИЛИ (∨) и НЕ (¬). Има примену у аутоматском доказивању теорема.

Примери КНФ

Примери формула у КНФ:

• (A∨B)∧(¬A∨C)
• (A∨B∨C)∧(¬A∨¬B)∧(C∨¬C)
• ¬A∧(B∨C)

Конверзија формуле у КНФ

Свака исказна формула може да се трансформише у КНФ.

Кораци у конверзији формуле у КНФ:

• Елиминисање импликација, еквиваленција и искључивих дисјункција

A→B прелази у ¬A∨B
A↔B прелази у (A∧B)∨(¬A∧¬B)
A⊕B прелази у (A∨B)∧¬(A∧B)

• Негације се померају унутар заграда како би се јављале само као део литерала. Елиминишу се двоструке негације и примењују се Де Морганови закони.
• Сколемизација формуле
• Елиминација универзалних квантификатора
• Примена закона дистрибутивности на конјукције и дисјункције

Дистрибутивност преко дисјункције: A∨(B∧C)≡(A∨B)∧(A∨C)
Дистрибутивност преко конјукције: A∧(B∨C)≡(A∧B)∨(A∧C)

Пример конверзије формуле у КНФ

Дата је следећа формула:

¬((¬A→¬B)∧¬C)

Елиминише се импликација:

¬((¬¬A∨¬B)∧¬C)

Елиминишу се двоструке негације:

¬((A∨¬B)∧¬C)

Негација се помера унутар заграде применом Де Морганових закона:

¬(A∨¬B)∨¬¬C

Елиминишу се двоструке негације:

¬(A∨¬B)∨C

Негација се помера унутар заграде применом Де Морганових закона:

(¬A∧¬¬B)∨C

Елиминишу се двоструке негације:

(¬A∧B)∨C

Примена закона дистрибутивности преко дисјункције:

(¬A∨C)∧(B∨C)

Добијена формула је у конјуктивној нормалној форми.