Алгоритм приведения формул к СДНФ и СКНФ.

1. Все логические операции в формуле выражаются через операции отрицания, конъюнкции и дизъюнкции.

2. С помощью закона де Моргана формула преображается к такому виду, чтобы знак операции отрицания встречался только перед переменными, то есть вносят знак отрицания в скобки.

3. На основе закона дистрибутивности конъюнкции относительно дизъюнкции (дистрибутивность дизъюнкции относительно конъюнкции) формула сводится к нормальной форме.

4. Полученные формы упрощаются с использованием основных формул равносильности.

5. Для преобразования ДНФ (КНФ) к совершенной форме недостающие переменные вводятся в элементарные конъюнкции (дизъюнкции) с помощью следующих правил:

Á eq ( Á & x i ) Ú ( Á & ù x i )

Á eq ( Á Ú x i ) & ( Á Ú ù x i )

Существует еще один метод получения КНФ, использующий понятие двойственности.

Для некоторой формулы Á находится двойственная формула Á*.

Á ® Á*.

Для Á* находится ДНФ: ДНФ(Á*)=Â.

Двойственная к найденной ДНФ формула является КНФ исходной формулы: Â* eq КНФ(Á).

Пример 1: Привести к СДНФ формулу ù ( x Ú y ) « x & y.

ù( x Ú y) « x & y eq ( ù( ù( x Ú y)) & ù ( x & y ) Ú ( ù ( x Ú y ) & ( x & y)) eq (( x Ú y) & ( ù x Ú ù y )) Ú (( ù x & ù y ) & ( x & y )) eq ( x & ù x Ú y & ù x Ú x & ù y Ú y & ù y) Ú ( ù x & ù y & x & y ) eq ( y & ù x) Ú ( x & ù y)- ДНФ и СДНФ.

Пример 2: Преобразовать к СКНФ формулу ( x & y Ú ù y & z ) & ( y ® x )

( x & y Ú ù y & z ) & ( y ® x ) eq ( x & y Ú ù y & z) & ( ù y Ú x ) eq (( x Ú ù y) &( y Ú ù y) & ( x Ú z) &( y Ú z ) & ( ù y Ú x) eq (( x Ú ù y) &( x Ú z) & ( y Ú z )) &( ù y Ú x) eq ( x Ú ù y) &( x Ú z) & ( y Ú z ) &( ù y Ú x) eq ( x Ú ù y) &( x Ú z) & ( y Ú z )- КНФ.

Преобразуем к СКНФ.

(x & y Ú ù y & z ) & ( y ® x ) eq (x Ú ù y) & (x Ú z) & ( y Ú z ) eq

(x Ú ù y Ú z) & (x Ú ù y Ú ù z) & (x Ú y Ú z) & (x Ú ù y Ú z) & (x Ú y Ú z) & ( ù x Ú y Ú z) eq (x Ú ù y Ú z) & (x Ú ù y Ú ù z) & (x Ú y Ú z) & ( ù x Ú y Ú z).

1.7 Логическое следование

Одна из основных задач логики - дать принципы рассуждения, которые могут быть общепризнанны правильными. Другими словами, необходимо иметь критерий для решения формальным путем вопроса о том, можно ли некоторую последовательность (цель) рассуждений считать правильной, основываясь на ее формальной структуре.

Цель рассуждений представляет собой конечную последовательность высказываний (составных, но, может быть, и простых предложений), приводимых в обоснование некоторого утверждения. Мы должны понять, действительно ли предлагаемый вывод (заключительной утверждение - заключение) можно сделать из указанных предпосылок начальных высказываний. Их называют посылками. Посылки считаются истинными. И, исходя из истинности посылок, мы должны вывести заключение.

Исчисление высказываний дает критерий вместе с практическими формами его использования для ответа на вопрос: «Правильно ли делается вывод о том, что заключение будет выполняться (иметь значение «истина»), если все посылки имеют значение «истина»»?

Высказывание B есть логическое следствие высказываний A 1,…, A n, что символически записывается в виде A 1, …, A n ᅣ В, если для всякого распределения истинностных значений, приписываемых каждой из простых формул P 1 , …, P m, входящих в одну или несколько формул A 1, …, A n, и В, формула В получает значение «истина» всякий раз, когда значение «истина» получают все формулы A 1, …, A n.

1а) ( A ᅣ B)↔( ᅣ A→ B)

1 б ) (A 1 , A 2 , … , A n ᅣ B)↔( ᅣ ( A 1 &A 2 & … &A n →B))

2 а ) (A 1 , A 2 , … , A n-1 , A n ᅣ B)↔ (A 1 , A 2 , … , A n-1 ᅣ A n ® B)

2 б ) (A 1 , A 2 , … ,A n-1 , A n ᅣ B)↔ ( ᅣ A 1 ® (A 2 ® ( … (A n-1 ® (A n ® B))))

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: