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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Предложение 1. Пусть F — формула, составленная из лите-
ралов с применением ∧ и ∨. Пусть F
0
— формула, полученная из F
заменой ∧ на ∨, ∨ на ∧ и каждого литерала на контрарный ему (т.е. A
на ¬A и наоборот). Тогда F
0
∼ ¬F .
Достаточно проследить за применением к ¬F преобразований ви-
да 1) и 4) из доказательства теоремы 1.
Теорема 3. Если F — дизъюнктивная нормальная форма фор-
мулы G, то F
0
— конъюнктивная нормальная форма формулы ¬G.
Очевидно, что из F ∼ G следует ¬F ∼ ¬G. Тогда в силу предло-
жения 1 F
0
∼ ¬G. Если при этом F находится в ДНФ, то F
0
окажется
в КНФ.
Из теоремы 3 вытекает следующее правило: чтобы получить КНФ
некоторой формулы, найдем ДНФ отрицания этой формулы, а затем
совершим преобразование, описанное в предложении 1.
Пример 3. Найдем КНФ формулы A ⇒ B ∧ C. Имеем ¬(A ⇒
⇒ B ∧ C) ∼ A ∧¬(B ∧C) ∼ A ∧(¬B ∨¬C) ∼ (A ∧¬B) ∨(A ∧¬C).
Таким образом, КНФ исходной формулы: (¬A ∨ B) ∧ (¬A ∨ C) .
Иногда ДНФ и КНФ могут совпадать, в этом случае отыскание
одной из этих форм сразу приводит и к другой. Например, в п.1 мы,
преобразовывая формулу ¬(A ⇔ (A ⇒ B)), нашли одну из ее ДНФ
¬A ∨ ¬B (дизъюнкция двух конъюнктов, каждый из которых состоит
из одного литерала), одновременно являющуюся и КНФ (конъюнкция
одного дизъюнкта, состоящего из двух литералов).
Упражнение 2. Найдите различные КНФ для функции голосования.
3. Приведение нормальных форм
к совершенным нормальным формам
Совершенная ДНФ может быть получена из ДНФ, а совершенная
КНФ — из КНФ путем добавления в конъюнкты (дизъюнкты) недоста-
ющих атомов с помощью эквивалентностей
A ∼ A ∧ (B ∨ ¬B), A ∼ A ∨ (B ∧ ¬B).
Пример 4. A ∨ (¬A ∧ B) (в первом члене дизъюнкции отсут-
ствует атом B)
∼ (A ∧ (B ∨ ¬B)) ∨ (¬A ∧ B) ∼ (A ∧ B) ∨ (A ∧ ¬B) ∨ (¬A ∧ B).
Пример 5. A ∧ B (Будьте внимательны — это не СКНФ!)
∼ (A ∨ (B ∧ ¬B)) ∧ (B ∨ (A ∧ ¬A)) ∼
24

Страницы