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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

(заметим, что последние две формулы являются, соответственно, со-
вершенной дизъюнктивной и совершенной конъюнктивной нормальны-
ми формами эквиваленции);
4) ввести знаки отрицания внутрь скобок (по законам Де Морга-
на):
¬(A ∨ B) ∼ ¬B ∧ ¬A, ¬(A ∧ B) ∼ ¬B ∨ ¬A,
причем продолжать их применение до тех пор, пока все отрицания не
окажутся стоящими непосредственно перед атомами.
При проведении преобразований типа 2)–4) вновь может возник-
нуть необходимость неоднократного применения устранения двойного
отрицания. В результате получится формула, составленная из лите-
ралов, соединенных знаками дизъюнкции и конъюнкции. Теперь нам
остается
5) раскрыть скобки по закону дистрибутивности:
(A ∨ B) ∧ C ∼ (A ∧ C) ∨ (B ∧ C).
Это преобразование напоминает процедуру перемножения многочленов
в элементарной алгебре, если число членов дизъюнкции равно двум
или более, например: (A ∨ B) ∧ (C ∨ D) ∼ (A ∧ C) ∨ (B ∧ C)∨
∨(A ∧ D) ∨ (B ∧ D).
В конце концов получится формула, представляющая собой дизъ-
юнкцию элементарных конъюнкций.
При приведении формул к ДНФ полезно иметь в виду, что из двух
одинаковых членов в конъюнкции или в дизъюнкции один можно вы-
черкнуть (в силу законов идемпотентности A ∧ A ∼ A, A ∨ A ∼ A).
Кроме того, можно воспользоваться правилами поглощения и правила-
ми оперирования с константами (см. эквивалентности (a)–(d) в конце
§ 1). Это позволяет упростить ДНФ и, в частности, избежать конъюнк-
тов, содержащих литералы вида A и ¬A (такие литералы называются
контрарными).
Пример 1. ¬(A ⇔ (A ⇒ B)) ∼ ¬(A ⇔ (¬A ∨ B)) ∼ ¬((A∨
∨¬(¬A ∨B)) ∧(¬A ∨¬A ∨B)) ∼ (¬A ∧¬¬(¬A ∨B)) ∨(A ∧A ∧¬B) ∼
∼ (¬A ∧ (¬A ∨ B)) ∨ (A ∧ ¬B) ∼ ¬A ∨ (A ∧ ¬B).
Заметим, что некоторые члены дизъюнкции могут оказаться не
конъюнктами, а просто литералами: будем считать их в таком слу-
чае конъюнктами из одного литерала. Кроме того, вместо дизъюнкции
конъюнктов может получиться один конъюнкт, и в этой ситуации мы
будем говорить о дизъюнкции из одного конъюнкта.
22

Страницы