Элементы логики

3. Нормальные формы высказываний

Рассмотрим две разновидности формул, которые имеют определены структурные особенности. Именно структура этих формул предопределяет их использование в таких важных отраслях применения математической логики, как автоматизация доведения утверждений и логическое программирование.Законы (2) утверждают ассоциативность связок конъюнкции. Отсюда формула вида ((.((A1A2)A3).)An) имеет эквивалентную запись A1A2A3.An. Формула в такой записи называется конъюнкцией формул A1, A2, A3, ., An.

Определение. Элементарной конъюнкцией называется конъюнкция формул, каждая из которых является или пропозицийною переменной, или отрицанием такой. Например, A1A2A3.

Определение. Дизъюнктивной нормальной формой (сокращенно ДНФ) называется дизъюнкция элементарных конъюнкций. Например, формула ABBCD. Заметим, что ее структуру лучше видно в записи ABBCD или в записи .

Любая формула может быть преобразована к ДНФ. Мы не будем доводить это утверждение, а лишь опишем нужные равносильные превращения. Применением законов (13) и (12) можно избавиться от связок  и , то есть превратить формулу к равносильной, в которой есть лишь связки ,  и . Дальше, если в формуле есть отрицание дизъюнкций или конъюнкций, то они "спускаются" к пропозицийних переменным применением законов Где Моргана (6). Дальше, если в формуле есть множители-дизъюнкции, то от них можно избавиться применением первого из законов дистрибутивности (3). В результате все множители в конъюнкциях формулы являются элементарными, и она являет собой ДНФ. Применение законов (1), (2) (4) (5) (7) -(10) может сократить этот процесс.

Пример. Рассмотрим превращение (AB)(CB). После знаков  в скобках указаны номера законов, примененных при дежурном превращении, :

(AB)(BC) (13, 12)

((AB)(CB))((CB)(AB)) (6, 7, 2)

 (ABCB)(BCAB) (3)

 ABBCABAABBCBCCACB

BBCBABB (1, 4, 9, 8)

 ABCACBCBAB (5)

 ABCACB

За законами (2) связки дизъюнкции также ассоциативные, откуда формулы ((.((A1A2) A3) .)An) и A1A2A3.An также является эквивалентными. Последняя из них называется дизъюнкцией формул A1, A2, A3, ., An.

Определение. Элементарной дизъюнкцией называется дизъюнкция формул, каждая из которых является или пропозицийною переменной, или отрицанием такой. Например, A1A2A3.

Определение. Конъюнктивной нормальной формой (сокращенно КНФ) называется конъюнкция элементарных дизъюнкций. Например, формула (AB)(BCD)которую можно подать также в виде .

Любая формула превращается к равносильной ей КНФ с использованием тех же законов, только вместо первого из законов дистрибутивности (3) употребляется второй: A(BC)  (AB)(AC).

Пример. Рассмотрим превращение формулы (AB)(CB) после получения формулы (ABCB)(BCAB):



Вернуться назад