1.5 Дизъюнкты и нормальные формы

Бывает полезно преобразовать заданную формулу в эквивалентную ей, имеющую вид «нормальной» или «канонической» формы.

Дизъюнктом называется дизъюнкция конечного числа высказываний, то есть формула вида

P₁Ú P₂ Ú…Ú P_N или или Ú{P_i | i=1,…,N}

Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа дизъюнктов.

Теорема. Любая формула имеет логически эквивалентную ей КНФ.

Алгоритм нормализации:

Исключение связок эквивалентности и импликации;

Необходимое число раз применяются правила преобразования из законов де Моргана, чтобы отрицания перевести на уровень элементарных выска-зываний.

Необходимое число раз применяются законы дистрибутивности (раскрыть все скобки).

Дизъюнкты, содержащие противоположности (т.е. высказывание и его отрицание), общезначимы и могут быть опущены. Можно опускать повторения в пределах одного дизъюнкта. Полученная таким способом нормальная форма называется приведённой. В ней в каждый дизъюнкт любое элементарное высказывание входит не более одного раза.

Дизъюнкт общезначим тогда и только тогда, когда он содержит пару противоположных высказываний. Нормальная форма общезначима тогда и только тогда, когда все ее дизъюнкты общезначимы.

Понятие дизъюнкта важно для практики. Описание задач и алгоритмов в терминах дизъюнктов составляет основу логического программирования.

Двойственным понятием к дизъюнкту является конъюнкт. Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция конечного числа конъюнктов. Можно показать, что любая формула приводима к логически эквивалентной ей ДНФ.

Контрольное задание. Привести формулы к КНФ

1. r Û Ø(P  S),

2. (r & S)  (q & r);

3. (P  q) Þ (Øq  ØS),

4. (r & q)Û (ØP Ú S)

5. (P & r) (P Ú r)

6. (P & (r Ú Øq)) Ú (ØP & r) Ú ((P Ú Øq) &Ør)

1.6. Логический вывод

Высказывание C есть логическое следствие высказываний H1, H2, ¼H_N, что записывается в виде { H1, H2, ¼, H_N}½= C,

если всякий раз, когда все H_i равны Тrue, значение C тоже равно Тrue. Здесь H_i могут быть формулами элементарных высказываний.

Говорят, что C следует из H={H1, H2, ¼, H_N}.

Выражения H1, H2, ¼, H_N называются посылками или аксиомами, а C – выводом из этих посылок или теоремой.

Фундаментальная проблема логики, называемая проблемой вывода, состоит в следующем: определить, является ли формула С логическим следствием множества формул H. Решение этой задачи называют выводом теоремы из аксиом.

Выводу сопоставляется цепочка высказываний С1, С2,¼, СK, где СK = С, а каждое высказывание Сi либо является тавтологией, либо следует из аксиом и высказываний, предшествующих данному.

1.6.1. Прямой вывод

В прямом выводе используется знание семантики тех операторов, через которые строятся аксиомы. Так, если аксиома утверждает, что A&B, то из смысла этого утверждения следует, что истинными будут высказывния A и B, которые войдут в цепочку вывода. Если известно, что истинным являются высказывания {AvB, `A}, то истинным будет высказывание B именно исходя из смысла этих высказываний. В прямом выводе строится цепочка высказываний, обозначенная выше как C1, C2, …,CK, которая и является выводом.

Пример. Доказать или опровергнуть следствие:

B®`A, A&D, BvC ½= D&C.

Пронумеруем аксиомы: B®`A (1), A&D (2), BvC (3). Вывод. Из (2) Þ A (4), из (2) Þ D (5), из (4) и (1) Þ`B (6), из (6) и (3) ÞС (7), из (5) и (7) следует D&C. Здесь используется свойство связок И, ИЛИ и СЛЕДУЕТ. Действительно, A&B истинна, если истинны A и B одновременно (вывод 4 и 5) . Если A= T, то `A = F, значит B не может быть T, т.е. B=F (вывод 6). Если B=F и BvC истинно, то C должно быть равно T (вывод 7). Наконец, из (7) и (5) следует искомый вывод.