Элементы математической логики. Фролов И.С. - 24 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

При наличии в ДНФ контрарных литералов бывает полезно пра-
вила дистрибутивности и поглощения применять в обратном направ-
лении.
Например, продолжая преобразование ДНФ из примера 1, мы
можем получить более простое выражение: ¬A ∨ (A ∧ ¬ B) ∼
∼ (¬A ∨(¬A ∧¬B)) ∨(A ∧¬B) ∼ ¬A ∨((¬A ∨A) ∧¬B) ∼ ¬A ∨¬B.
Другой пример:
(¬A ∧ ¬B) ∨ (A ∧ ¬B) ∼ (¬A ∨ A) ∧ ¬B ∼ 1 ∧¬B ∼ ¬B.
Вот тот случай, о котором мы говорили: ДНФ состоит из одного конъ-
юнкта, в котором имеется лишь один литерал.
Очевидно, что представление в виде ДНФ не единственно, в от-
личие от СДНФ. Различные дизъюнктивные нормальные формы отли-
чаются одна от другой по числу конъюнктов, числу литералов в конъ-
юнктах, общему числу связок и т.д.
Упражнение 1. Найдите различные ДНФ для функции голосования, опреде-
ленной в § 2.
2. Конъюнктивная нормальная форма
Определение 2. Дизъюнктом (или элементарной дизъюнкци-
ей) называется формула вида L
1
∨ . . . ∨ L
n
(n > 1), где L
1
, . . . , L
n
—
литералы (например, A ∨ ¬B, B ∨ ¬C ∨ ¬A).
Говорят, что формула находится в конъюнктивной нормальной
форме (сокращенно КНФ), если она имеет вид D
1
∧. . . ∧D
m
(m > 1),
где D
1
, . . . , D
m
— дизъюнкты (например, (A ∨ ¬B) ∧(B ∨ ¬C ∨ ¬A)).
Теорема 2. Любая формула эквивалентна некоторой формуле в
конъюнктивной нормальной форме.
Процесс приведения к конъюнктивной нормальной форме анало-
гичен рассмотренному в теореме 1 — следует лишь использовать другой
закон дистрибутивности
(A ∧ B) ∨ C ∼ (A ∨ C) ∧ (B ∨ C).
Пример 2. ¬(A ⇔ (B ⇒ C)) ∼
∼ ¬((A ∧ (B ⇒ C)) ∨ (¬A ∧ ¬(B ⇒ C))) ∼
∼ (¬A ∨ ¬(B ⇒ C)) ∧ (A ∨ (B ⇒ C)) ∼
∼ (¬A ∨ (B ∧ ¬C)) ∧ (A ∨ ¬B ∨ C) ∼
∼ (¬A ∨ B) ∧ (¬A ∨ ¬C) ∧ (A ∨ ¬B ∨ C).
Рассмотрим другой способ получения КНФ.
23

Страницы