Автор Тема: Лекция 6. Следование формул логики высказываний  (Прочитано 1456 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний


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

***

Пусть \(  \large F_1,F_2, \ldots , F_k, G  \) - формулы классической логики высказываний, зависящие от переменных \(  \large P_1,P_2, \ldots , P_n  \).

Определение 6.1. Формула \(  \large G  \) называется следствием формул \(  \large F_1, F_2, \ldots , F_k  \), если для любых высказываний \(  \large A_1, A_2, \ldots , A_n  \) истинность высказываний \(  \large F_i (A_1,A_2, \ldots ,A_n), \ i=1,2, \ldots, k  \) влечёт истинность высказывания \(  \large G(A_1,A_2, \ldots, A_n)  \).

Замечание 6.1. При этом формулы \(  \large F_1,F_2, \ldots , F_k  \) называются посылками для следствия \(  \large G  \).

Замечание 6.2. Если формула \(  \large G  \) есть следствие формул \(  \large F_1,F_2, \ldots , F_k  \), то говорят, что \(  \large G  \) следует из \(  \large F_1,F_2, \ldots , F_k  \).

Замечание 6.3. Формула \(  \large G  \) не следует из формул \(  \large F_1,F_2, \ldots , F_k  \), если существуют такие высказывания \(  \large A_1,A_2, \ldots, A_n  \), что высказывания \(  \large F_i (A_1,A_2, \ldots ,A_n), \ i=1,2, \ldots, k  \), истинны, а высказывание \(  \large G(A_1,A_2, \ldots , A_n)  \) ложно.

Замечание 6.4. Если формула \(  \large G  \) является следствием формул \(  \large F_1,F_2, \ldots , F_k  \), то пишут

\(  \large F_1, F_2, \ldots , F_k \models G  \),

если не является -

\(  \large F_1, F_2, \ldots , F_k \not \models G  \).

Замечание 6.5. Некоторые пропозициональные переменные могут отсутствовать в любой из формул \(  \large F_1, F_2, \ldots , F_k, G  \).

Замечание 6.6. Рассмотрим некоторые формулы логики высказываний \(  \large F_1,F_2, \ldots, F_k, G  \). Составим для них общую таблицу истинности. Определение следования говорит о том, что если во всех строках данной таблицы, где каждая формула \(  \large F_1,F_2, \ldots, F_k  \) принимает значение "истина", формула \(  \large G  \) также принимает значение "истина", то

\(  \large F_1,F_2, \ldots, F_k \models G  \).

Если найдётся хотя бы одна строка, где формулы \(  \large F_1,F_2, \ldots, F_k  \) принимают значение "истина", а формула \(  \large G  \) принимает значение "ложь", то

\(  \large F_1,F_2, \ldots, F_k \not \models G  \).

По сути это алгоритм проверки формул логики высказываний на следование. Рассмотрим его на примерах.
 
Сказали спасибо: Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #1 : Ноябрь 20, 2016, 06:45:22 pm »
Пример 6.1. Докажем, что

\(  \large (P_1 \to P_2) \to P_3 \models (P_1P_2) \to P_3  \).

Составим общую истинностную таблицу для этих формул:

\( \begin{array}{|c|c|}
\hline
P_1 &  P_2 &  P_3 & P_1 \to P_2 &  (P_1 \to P_2) \to P_3 & P_1P_2 & (P_1P_2) \to P_3  \\
\hline
0 &  0 &  0 &1  & 0 &  0 & 1 \\
\hline
0 & 0 & 1 & 1  & 1 & 0 & 1 \\
\hline
0 & 1 & 0 &  1 & 0 & 0 & 1 \\
\hline
0 & 1 & 1 &  1 & 1 & 0 & 1 \\
\hline
1 & 0 & 0 & 0 & 1 & 0 & 1  \\
\hline
1 & 0 & 1 & 0 & 1 & 0 & 1  \\
\hline
1 & 1 & 0 & 1& 0 & 1 & 0 \\
\hline
1 & 1 & 1 &  1 &1 & 1 & 1  \\
\hline
\end{array}  \)

Мы видим, что всегда если \(  \large (P_1 \to P_2) \to P_3=1  \), то и \(  \large (P_1P_2) \to P_3=1  \). Это, согласно определению следования, означает, что из формулы \(  \large (P_1 \to P_2) \to P_3  \) следует формула \(  \large (P_1P_2) \to P_3  \).

Пример 6.2. Докажем, что

\(  \large P \to Q \not \models Q \to P  \).

Снова составляем таблицу истинности для обеих формул:

\( \begin{array}{|c|c|}
\hline
P &  Q &  P \to Q &  Q \to P  \\
\hline
0 &  0 & 1 & 1 \\
\hline
0 & 1 & 1 & 0 \\
\hline
1 & 0 & 0  &  1  \\
\hline
1 & 1 & 1  & 1  \\
\hline
\end{array}  \)

Посмотрим на вторую строку этой таблицы. Здесь \(  \large P \to Q=1  \), но \(  \large Q \to P =0  \). Значит, из формулы \(  \large P \to Q  \) не следует формула \(  \large Q \to P  \). Этот пример был выбран нами не случайно. Здесь продемонстрирована распространённая логическая ошибка, которая заключается в том, что из справедливости прямой теоремы выводят справедливость обратной теоремы.
 
Сказали спасибо: Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #2 : Ноябрь 20, 2016, 06:46:55 pm »
Замечание 6.7. Пусть даны произвольные формулы логики высказываний \(  \large F_1,F_2, \ldots , F_k,G  \), зависящие от переменных \(  \large P_1,P_2, \ldots , P_n  \). При числе пропозициональных переменных, большем трёх, таблицы истинности формул логики высказываний громоздки. Например, таблица истинности для формулы от четырёх переменных будет иметь \(  \large 2^4=16  \) строк, а в случае пяти переменных - \(  \large 2^5=32  \) строки. Поэтому для проверки следования формул классической логики высказываний лучше использовать другой алгоритм, который, как и табличный, вытекает из определения следования. Предположим, что найдутся такие высказывания \(  \large A_1,A_2, \ldots , A_n  \), что высказывания

\(  \large F_1(A_1,A_2, \ldots , A_n), F_2(A_1,A_2, \ldots , A_n), \ldots , F_k (A_1,A_2, \ldots , A_n)  \)

истинны, а высказывание

\(  \large G(A_1,A_2, \ldots , A_n)  \)

ложно. Если при этом не удаётся обнаружить противоречия, то

\(  \large F_1 , F_2, \ldots , F_k \not \models G  \).

Если же противоречие есть, то предположение неверно, значит,

\(  \large F_1 , F_2, \ldots , F_k \models G  \).

Покажем на примерах, как работает данный алгоритм.

Пример 6.3. Выясним, верно ли, что

\(  \large (PQ) \vee R \models P \vee (Q \to R)  \).

Пусть \(  \large A,B,C  \) - некоторые высказывания. Предположим, что высказывание

\(  \large (AB) \vee C  \)

истинно, а высказывание

\(  \large A \vee (B \to C)  \)

ложно. Дизъюнкция, согласно определению, ложна тогда и только тогда, когда оба её члена ложны. Значит,

\(  \large A=B \to C=0  \).

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

\(  \large A=C=0, B=1  \).

Тогда, учитывая определения логических связок,

\(  \large (AB) \vee C=(0 \cdot 1) \vee 0 = 0 \vee 0=0  \).

Но, в силу нашего предположения, высказывание

\(  \large (AB) \vee C  \)

истинно. Получили противоречие. Значит, какими бы ни были высказывания \(  \large A,B,C  \), если высказывание

\(  \large (AB) \vee C  \)

истинно, то и высказывание

\(  \large A \vee (B \to C)  \)

истинно. Следовательно,

\(  \large (PQ) \vee R \models P \vee (Q \to R)  \).

Пример 6.4. Докажем, что

\(  \large P \to Q \not \models P' \to Q'  \).

Этот пример, как и пример 6.3, выбран намеренно. Он демонстрирует другую распространённую логическую ошибку: нередко из справедливости прямой теоремы выводят справедливость теоремы противоположной. Переходим к доказательству. Рассмотрим произвольные высказывания \(  \large A  \) и \(  \large B  \). Предположим, что высказывание \(  \large A \to B  \) истинно, а высказывание \(  \large A' \to B'  \) ложно. Последняя импликация ложна тогда и только тогда, когда высказывание \(  \large A'  \) истинно, а высказывание \(  \large B'  \) ложно. Значит, высказывание \(  \large A  \) ложно, а высказывание \(  \large B  \) истинно. Тогда и высказывание \(  \large A \to B  \) истинно как импликация с ложной посылкой и истинным заключением. Противоречия нет. Следовательно,

\(  \large P \to Q \not \models P' \to Q'  \).
 
Сказали спасибо: Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #3 : Ноябрь 20, 2016, 06:49:46 pm »
Рассмотренный выше алгоритм проверки следования формул логики высказываний напоминает алгоритм проверки формул на тождественную истинность, и это не случайно. Как и в случае с равносильностью, существует признак следования формул логики высказываний. Данный признак позволяет свести проверку следования к проверке на тождественную истинность некоторой формулы. Эта теорема связывает понятия "следование", "тавтология" и "импликация".

***

Теорема 6.1. Формула логики высказываний \(  \large G  \) является следствием формул \(  \large F_1,F_2, \ldots , F_k  \) тогда и только тогда, когда формула \(  \large (F_1F_2 \cdots F_k) \to G  \) является тавтологией.

Доказательство аналогично доказательству признака равносильности формул. Это тоже цепочка равносильностей по определению.

Формула  \(  \large G(P_1,P_2, \ldots , P_n)  \) следует из формул \(  \large F_i(P_1,P_2, \ldots , P_n), i=1,2, \ldots , k , \) тогда и только тогда, когда для всяких высказываний \(  \large A_1,A_2, \ldots , A_n  \) истинность высказываний \(  \large F_i (A_1,A_2, \ldots , A_n), \ i=1,2, \ldots , k  \) влечёт истинность высказывания \(  \large G(A_1,A_2, \ldots , A_n)  \) (в силу определения следования формул). Согласно определению конъюнкции, для любых высказываний \(  \large A_1,A_2, \ldots , A_n  \) истинность высказываний \(  \large F_i (A_1,A_2, \ldots , A_n), \ i=1,2, \ldots , k  \) влечёт истинность высказывания \(  \large G(A_1,A_2, \ldots , A_n)  \), если и только если истинность высказывания \(  \large F_1(A_1,A_2, \ldots, A_n) \cdots F_k(A_1,A_2, \ldots , A_n)  \) влечёт истинность высказывания \(  \large G(A_1,A_2, \ldots , A_n)  \), какими бы ни были высказывания \(  \large A_1,A_2, \ldots, A_n  \). Используя определение импликации, заключаем, что для любых высказываний \(  \large A_1,A_2, \ldots, A_n  \) истинность высказывания \(  \large F_1(A_1,A_2, \ldots, A_n) \cdots F_k(A_1,A_2, \ldots , A_n)  \) влечёт истинность высказывания \(  \large G(A_1,A_2, \ldots , A_n)  \) тогда и только тогда, когда высказывание \(  \large (F_1(A_1,A_2, \ldots , A_n) \cdots F_k(A_1,A_2, \ldots , A_n)) \to G(A_1,A_2, \ldots , A_n)  \) истинно, какими бы ни были высказывания \(  \large A_1,A_2, \ldots , A_n  \). Согласно определению тавтологии, высказывание \(  \large (F_1(A_1,A_2, \ldots , A_n) \cdots F_k(A_1,A_2, \ldots , A_n)) \to G(A_1,A_2, \ldots , A_n)  \) истинно для любых высказываний \(  \large A_1,A_2, \ldots, A_n  \), если и только если формула \(  \large  (F_1 F_2 \cdots F_k) \to G  \) является тавтологией. Теорема доказана.

Замечание 6.8. Всякий закон логики высказываний, имеющий вид \(  \large (F_1F_2 \cdots F_k) \to G  \), даёт нам правило дедуктивного умозаключения вида \(  \large F_1, F_2, \ldots , F_k \models G  \). В этом состоит ещё одно важное значение законов логики высказываний (наряду с тем, что эквиваленции дают нам правила равносильных преобразований).

Замечание 6.9. Закон противоположности позволяет нам получить из этой теоремы ещё одну - необходимое и достаточное условие отсутствия следования: формула логики высказываний \(  \large G  \) не является следствием формул \(  \large F_1,F_2, \ldots , F_k  \) тогда и только тогда, когда формула \(  \large (F_1F_2 \cdots F_k) \to G  \) не является тавтологией.

Замечание 6.10. Признак следования формул логики высказываний, конечно же, справедлив и для случая, когда \(  \large k=1  \): \(  \large F \models G   \) тогда и только тогда, когда \(  \large \models F \to G  \).
 
Сказали спасибо: Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #4 : Ноябрь 20, 2016, 06:51:47 pm »
В самом начале настоящей лекции говорилось, что понятия "следование" и "равносильность" тесно связаны. Характер этой связи раскрывается в теореме, которую мы сформулируем и докажем ниже.

***

Теорема 6.2. Формулы \(  \large F  \) и \(  \large G  \) равносильны тогда и только тогда, когда формула \(  \large G  \) следует из формулы \(  \large F  \) и формула \(  \large F  \) следует из формулы \(  \large G  \).

Доказательство. Пусть \(  \large F   \) и \(  \large G  \) - некоторые формулы, зависящие от пропозициональных переменных \(  \large P_1,P_2, \ldots, P_n  \).

1) Пусть \(  \large F \simeq G  \). Согласно определению, это означает, что какими бы ни были высказывания \(  \large A_1,A_2, \ldots , A_n  \), истинностные значения высказывания \(  \large F(A_1,A_2, \ldots , A_n)  \) и \(  \large G(A_1,A_2, \ldots, A_n)  \) совпадают. Отсюда, в частности, вытекает: если высказывание \(  \large F(A_1, A_2, \ldots , A_n)  \) истинно, то и высказывание \(  \large G(A_1, A_2, \ldots, A_n)  \) истинно, и наоборот (для любых высказываний \(  \large A_1,A_2, \ldots, A_n  \)). А это и означает, учитывая определение следования, что \(  \large F \models G  \) и \(  \large G \models F   \).

2) Пусть теперь  \(  \large F \models G  \) и \(  \large G \models F   \). В силу определения следования формул логики высказываний, это означает, что истинность высказывания \(  \large F(A_1,A_2, \ldots , A_n)  \) влечёт истинность высказывания \(  \large G(A_1,A_2, \ldots, A_n)  \), и наоборот, какими бы ни были высказывания \(  \large A_1,A_2, \ldots, A_n  \). Тогда и ложность высказывания \(  \large F(A_1,A_2, \ldots , A_n)  \) влечёт ложность высказывания \(  \large G(A_1,A_2, \ldots, A_n)  \), и наоборот. Следовательно, для любых высказываний \(  \large A_1,A_2, \ldots, A_n  \) значения истинности высказываний \(  \large F(A_1,A_2, \ldots , A_n)  \) и \(  \large G(A_1,A_2, \ldots, A_n)  \) совпадают. Следовательно, согласно определению равносильности, \(  \large F \simeq G  \).
 
Теорема доказана.

Замечание 6.11. Данная теорема имеет следующую структуру:

\(  \large A \leftrightarrow (BC)  \),

где \(  \large A  \) обозначает \(  \large F \simeq G  \), \(  \large B  \) обозначает \(  \large F \models G  \), \(  \large C  \) обозначает \(  \large G \models F  \).

Учитывая закон противоположности и первый закон де Моргана, имеем:

\(  \large A \leftrightarrow (BC)  \simeq A' \leftrightarrow  (BC)'  \simeq  A' \leftrightarrow  (B' \vee C') \).

Итак, формула \(  \large F  \) не равносильна формуле \(  \large G  \) тогда и только тогда, когда формула \(  \large G  \) не следует из формулы \(  \large F  \) или формула \(  \large F  \) не следует из формулы \( G  \).
 
Сказали спасибо: Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #5 : Ноябрь 20, 2016, 06:54:05 pm »
В первой лекции мы говорили, что умозаключения бывают индуктивными и дедуктивными, а математическая логика интересуется лишь последними, поскольку только они при истинных посылках всегда приводят к истинным заключениям. В основе любого дедуктивного умозаключения лежит логический закон. Теперь, когда введено понятие "следование" и доказан признак следования формул логики высказываний, легко понять, что в основе схемы дедуктивного умозаключения вида

\(  \large F_1, F_2, \ldots , F_k \models G  \)

лежит закон логики высказываний вида

\(  \large (F_1F_2 \ldots F_k) \to G  \).

Далее будут рассмотрены некоторые правила дедуктивных умозаключений. Для их доказательства будем использовать признак следования формул логики высказываний. Кроме того, напомним, что любая равносильность вида \(  \large F_1 \simeq F_2  \), учитывая теорему 6.2, даёт два правила умозаключений: \(  \large F_1 \models F_2 \) и \(  \large F_2 \models F_1  \). Мы рассмотрим только правила, не следующие из основных равносильностей, доказанных в лекции 4.

***

Теорема 6.3. Правило modus ponens.

\(  \large P, P \to Q \models Q  \)

Доказательство элементарно: оно сводится к проверке на тождественную истинность формулы

\(  \large (P(P \to Q)) \to Q  \).

Будем снова использовать равносильные преобразования. Сначала избавимся от внутренней импликации:

\(  \large (P(P \to Q)) \to Q \simeq (P(P' \vee Q)) \to Q  \).

Применим один из законов дистрибутивности:

\(  \large (P(P' \vee Q)) \to Q \simeq ((PP') \vee (PQ)) \to Q  \).

Вспомним про закон противоречия:

\(  \large ((PP') \vee (PQ)) \to Q \simeq (0 \vee (PQ)) \to Q  \).

Используя одно из правил действий с константой "нуль", получим:

\(  \large (0 \vee (PQ)) \to Q \simeq (PQ) \to Q  \).

Снова избавляемся от импликации:

\(  \large (PQ) \to Q \simeq (PQ)' \vee Q  \).

Пришла очередь для первого закона де Моргана:

\(  \large (PQ)' \vee Q \simeq P' \vee Q' \vee Q  \).

Используем закон исключённого третьего:

\(  \large P' \vee Q' \vee Q \simeq P' \vee 1   \).

Применим одно из правил действий с логическими константами:

\(  \large P' \vee 1 \simeq 1  \).

Получили константу \(  \large 1  \), значит, теорема доказана.

Теорема 6.4. Правило modus tollens.

\(  \large P \to Q, Q' \models P'  \)

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

\(  \large ((P \to Q)Q') \to P' \simeq ((P' \vee Q)Q') \to P' \simeq ((P'Q') \vee (QQ')) \to P' \simeq   \)

\(  \large  \simeq ((P'Q') \vee 0) \to P' \simeq (P'Q') \to P' \simeq (P'Q')' \vee P' \simeq  \)

\(  \large P'' \vee Q'' \vee P' \simeq   P \vee Q \vee P' \simeq 1 \vee Q \simeq 1  \).

Выше были использованы только основные равносильности классической логики высказываний. Сначала избавились от внутренней импликации, затем использовали дистрибутивный закон, закон противоречия и одно из правил действий с константой "нуль", потом выразили оставшуюся импликацию через дизъюнкцию и отрицание и применили первый закон де Моргана и закон двойного отрицания, наконец, использовали закон исключённого третьего и одно из правил действий с константой "единица". Теорема доказана.

Пример 6.5. Схемы умозаключений наподобие modus ponens и modus tollens шокируют человека, не искушённого в логике. Дабы избавить читателя от этого шока, приведём пару примеров. Сначала modus ponens. Пусть известно, что истинны следующие высказывания:

1) если идёт дождь (\(  \large A  \)), то дорога мокрая (\(  \large B  \));

2) идёт дождь (\(  \large A  \)).

Посылки имеют вид \(  \large A \to B  \) и \(  \large A  \). Значит, используя правило modus ponens, делаем вывод: дорога мокрая (\(  \large B  \)).

Теперь modus tollens:

1) если горит дерево (\(  \large A  \)), то идёт дым (\(  \large B  \));

2) дым не идёт (\(  \large B'  \)).

Значит, дерево не горит (\(  \large A'  \)).
 
Сказали спасибо: Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #6 : Январь 14, 2017, 01:11:24 pm »
Теорема 6.5. Правило "истина из чего угодно".

\(  \large P \models Q \to P  \)

Доказательством является следующая цепочка равносильных преобразований:

\(  \large P \to (Q \to P) \simeq P' \vee (Q \to P) \simeq P' \vee Q' \vee P \simeq 1 \vee Q' \simeq 1  \).

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

Теорема 6.6. Правило "из лжи что угодно".

\(  \large P' \models P \to Q  \)

Доказательство. Имеем:

\(  \large P' \to (P \to Q) \simeq P'' \vee (P \to Q) \simeq P'' \vee P' \vee Q \simeq P \vee P' \vee Q \simeq 1 \vee Q \simeq 1  \).

Здесь, как и в предыдущей теореме, последовательно выразили две импликации через другие операции логики высказываний, затем использовали законы двойного отрицания и исключённого третьего. Не обошлось и без одного из логических законов, касающихся пропозициональных констант. Теорема доказана.

Теорема 6.7. Правило силлогизма (цепного заключения).

\(  \large P \to Q, Q \to R \models P \to R  \)

Доказательство. Снова будем использовать основные равносильности классической логики высказываний:

\(  \large ((P \to Q)(Q \to R)) \to (P \to R) \simeq ((P' \vee Q)(Q' \vee R)) \to (P' \vee R) \simeq  \)

\(  \large \simeq ((P' \vee Q)(Q' \vee R))' \vee P' \vee R \simeq (P' \vee Q)' \vee (Q' \vee R)' \vee P' \vee R \simeq  \)

\(  \large \simeq (P'' Q') \vee (Q''R') \vee P' \vee R \simeq  (PQ') \vee P' \vee (QR') \vee R \simeq  \)

\(  \large \simeq ((P \vee P')(Q' \vee P')) \vee ((Q \vee R)(R' \vee R)) \simeq (1 \cdot (Q' \vee P')) \vee ((Q \vee R) \cdot 1) \simeq  \)

\(  \large \simeq Q' \vee P' \vee Q \vee R \simeq 1 \vee P' \vee R \simeq 1  \).

Прокомментируем выполненные выше преобразования. Сначала избавились от внутренних, а потом и от внешней импликации, затем применили оба закона де Моргана и закон двойного отрицания, после этого воспользовались дистрибутивностью дизъюнкции относительно конъюнкции, законом исключённого третьего, правилом \(  \large P \cdot 1 \simeq P  \), потом снова применили закон исключённого третьего и правило \(  \large P \vee 1 \simeq 1  \). Теорема доказана.

Пример 6.6. В курсе элементарной геометрии доказываются такие теоремы: "Если все стороны треугольника равны, то все его углы равны" (\(  \large A \to B  \)), "Если все углы треугольника равны, то все они составляют \(  \large 60^o  \)" (\(  \large B \to C  \)). Используя правило силлогизма, получаем ещё одну теорему, являющуюся следствием первых двух: "Если все стороны треугольника равны, то все его углы составляют \(  \large 60^o  \)" (\(  \large A \to C  \)).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #7 : Сентябрь 15, 2017, 09:43:03 pm »
Теорема 6.8. Правило перестановки посылок.

\(  \large P \to (Q \to R) \models Q \to (P \to R)  \)

Данная теорема элементарно доказывается с помощью равносильных преобразований:

\(  \large P \to (Q \to R) \simeq P' \vee Q' \vee R \simeq Q' \vee P' \vee R \simeq Q \to (P \to R)  \).

Итак, формулы равносильны, значит, одна следует из другой, и наоборот. Здесь дважды использовали равносильность \(  \large P \to Q \simeq P' \vee Q    \), закон коммутативности дизъюнкции, а затем снова применили равносильность, выражающую импликацию через дизъюнкцию и отрицание.

Теорема доказана.

Теорема 6.9. Правило разбора случаев.

\(  \large P \to R, Q \to R \models (P \vee Q) \to R  \)

Доказательство. Легко показать, что

\(  \large \models ((P \to R)(Q \to R)) \to ((P \vee Q) \to R)  \).

Преобразуем лишь посылку данной импликации:

\(  \large (P \to R)(Q \to R) \simeq (P' \vee R)(Q' \vee R) \simeq (P'Q') \vee R \simeq (P \vee Q)' \vee R \simeq (P \vee Q) \to R  \).

Мы последовательно выразили обе импликации через другие пропозициональные связки, использовали дистрибутивность дизъюнкции относительно конъюнкции, второй закон де Моргана и закон \(  \large P' \vee Q \simeq P \to Q  \). Итак, формулу

\(  \large ((P \to R)(Q \to R)) \to ((P \vee Q) \to R)  \).

можно представить в виде

\(  \large ((P \vee Q) \to R) \to ((P \vee Q) \to R)  \).

Теперь докажем, что

\(  \large \models P \to P  \)

и сошлёмся на правило подстановки. Имеем:

\(  \large P \to P \simeq P' \vee P \simeq 1  \).

Здесь использовали закон исключённого третьего. На этом теорема доказана.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #8 : Сентябрь 15, 2017, 11:34:51 pm »
Теорема 6.10. Правило объединения посылок.

\(  \large P \to (Q \to R) \models (PQ) \to R  \)

Теорема 6.11. Правило разъединения посылок.

\(  \large (PQ) \to R \models P \to (Q \to R)  \)

Докажем разом обе теоремы, доказав, что

\(  \large P \to (Q \to R) \simeq (PQ) \to R  \),

поскольку, как известно, \(  \large F \simeq G  \) тогда и только тогда, когда \(  \large F \models G  \) и \(  \large G \models F  \). Для этого преобразуем левую часть равносильности:

\(  \large P \to (Q \to R) \simeq P' \vee Q' \vee R \simeq (P' \vee Q') \vee R \simeq (PQ)' \vee R \simeq (PQ) \to R  \).

Здесь сначала избавились от обеих импликаций, использовали ассоциативность дизъюнкции, первый закон де Моргана и равносильность \(  \large P \to Q \simeq P' \vee Q  \).

Обе теоремы доказаны.

Теорема 6.12. Правило приведения к абсурду.

\(  \large P' \to Q, P' \to Q' \models P  \)

Снова проведём доказательство с помощью признака следования и равносильных преобразований:

\(  \large ((P' \to Q)(P' \to Q')) \to P \simeq ((P'' \vee Q)(P'' \vee Q')) \to P \simeq ((P \vee Q)(P \vee Q')) \to P \simeq  \)

\(  \large \simeq (P \vee (QQ')) \to P \simeq (P \vee 0) \to P \simeq P \to P  \).

Мы выразили обе импликации через дизъюнкцию и отрицание, воспользовались законом двойного отрицания и одним из дистрибутивных законов, затем применили закон противоречия и правило \(  \large P \vee 0 \simeq P  \). После этого получили формулу \(  \large P \to P  \), тождественная истинность которой была доказана в ходе доказательства теоремы 6.9. На этом правило приведения к абсурду доказано.

Замечание 6.12. Во всех правилах дедуктивных умозаключений вместо пропозициональных переменных \(  \large P,Q,R  \) можно подставить произвольные формулы логики высказываний \(  \large F,G,H  \). Это следует из правила подстановки и признака следования.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #9 : Сентябрь 15, 2017, 11:38:47 pm »
Рассмотрим такую задачу: найти все формулы логики высказываний, зависящие от данных пропозициональных переменных, которые являются следствиями некоторого набора формул. Есть и обратная задача: найти все формулы, из которых данная формула следует (искомые формулы зависят от тех же переменных). Алгоритмы для решения этих задач дают следующие теоремы. Важно отметить, что тут на помощь снова приходят совершенные нормальные формы.

***

Теорема 6.13. Формула \(  \large G  \) следует из формул \(  \large F_1, F_2, \ldots , F_k  \) тогда и только тогда тогда, когда все элементарные дизъюнкции, входящие в формулу \(  \large G  \), входят в формулу \(  \large F_1F_2 \cdots F_k  \).

Доказательство. Пусть \(  \large F_1, F_2, \ldots , F_k, G  \) - формулы, зависящие от пропозициональных переменных \(  \large P_1, P_2, \ldots , P_n  \) и представленные в совершенной конъюнктивной нормальной форме. Поскольку формулы логики высказываний представлены в СКНФ, то речь идёт лишь об опровержимых формулах. И пусть \(  \large D_1,D_2, \ldots , D_p, D_{p+1}, \ldots , D_l  \) - элементарные дизъюнкции, зависящие от тех же переменных.

1) Пусть

\(  \large F_1, F_2, \ldots, F_k \models G  \).

Предположим, что хотя бы одной элементарной дизъюнкции, образующей формулу \(  \large G  \) нет в формуле \(  \large F_1F_2 \cdots F_k  \). Пусть, например, элементарная дизъюнкция \(  \large D_1  \) входит в \(  \large G  \), но не входит в \(  \large F_1F_2 \cdots F_k  \):

\(  \large F_1F_2 \cdots F_k \simeq D_2 \cdots D_p \cdot D_{p+1} \cdots D_l  \),

\(  \large G \simeq D_1 \cdot D_2 \cdots D_p  \).

В силу определения следования, для любых высказываний \(  \large A_1,A_2, \ldots , A_n  \) если

\(  \large D_2(A_1, A_2, \ldots , A_n) \cdots D_l (A_1,A_2, \ldots , A_n)=1  \),

то

\(  \large D_1 (A_1,A_2, \ldots , A_n) \cdot D_2(A_1, A_2, \ldots , A_n) \cdots D_p (A_1,A_2, \ldots , A_n)=1  \).

Из первого, согласно определению конъюнкции,

\(  \large D_2(A_1, A_2, \ldots , A_n) = \ldots  = D_l (A_1,A_2, \ldots , A_n)=1  \).

Значит,

\(  \large D_1 (A_1,A_2, \ldots , A_n) \cdot D_2(A_1, A_2, \ldots , A_n) \cdots D_p (A_1,A_2, \ldots , A_n) \simeq  \)

\(  \large   \simeq D_1(A_1,A_2, \ldots , A_n) \cdot 1 \cdots 1 \simeq D_1(A_1, A_2, \ldots , A_n) \).

Однако это высказывание может быть как истинным, так и ложным. Но оно должно быть истинным, иначе

\(  \large D_1 (A_1,A_2, \ldots , A_n) \cdot D_2(A_1, A_2, \ldots , A_n) \cdots D_p (A_1,A_2, \ldots , A_n)=0  \).

Получили противоречие. Следовательно, все элементарные дизъюнкции, входящие в формулу \(  \large G  \), входят и в \(  \large F_1F_2 \cdots F_k  \).

2) Пусть

\(  \large F \simeq D_1 \cdot D_2 \cdots D_p \cdot D_{p+1} \cdots D_l  \),

\(  \large G \simeq D_1 \cdot D_2 \cdots D_p   \).

Предположим, что

\(  \large F_1,F_2, \ldots , F_k \not \models G  \).

Значит, существуют такие высказывания \(  \large A_1,A_2, \ldots , A_n  \), что

\(  \large D_1(A_1,A_2, \ldots , A_n)  \cdots D_l(A_1,A_2, \ldots, A_n)=1  \),

и

\(  \large D_1(A_1,A_2, \ldots , A_n)  \cdots D_p(A_1,A_2, \ldots, A_n)=0  \).

Из первого, в силу определения дизъюнкции,

\(  \large D_1(A_1,A_2, \ldots , A_n)  = \ldots =D_l(A_1,A_2, \ldots, A_n)=1  \).

Следовательно,

\(  \large D_1(A_1,A_2, \ldots , A_n)  \cdots D_p(A_1,A_2, \ldots, A_n)=1  \).

Противоречие. Значит,

\(  \large F_1,F_2, \ldots , F_k \models G  \).

Теорема доказана.

Замечание 6.13. Учитывая закон противоположности \(  \large P \leftrightarrow Q \simeq P' \leftrightarrow Q'  \), получим ещё одну теорему, равносильную теореме 6.13: формула \(  \large \models G  \) не следует из формул \(  \large F_1, F_2, \ldots, F_k  \) тогда и только тогда, когда существуют элементарные дизъюнкции, входящие в формулу \(  \large G  \) и не входящие в формулу \(  \large F_1F_2 \cdots F_k  \).

Замечание 6.14. Из теоремы 6.13 вытекают два алгоритма.

1) Пусть \(  \large F_1,F_2, \ldots, F_k  \) - формулы, зависящие от пропозициональных переменных \(  \large P_1,P_2, \ldots, P_n  \). Чтобы найти все следствия этих формул-посылок, зависящие от тех же переменных, нужно:

а) составить конъюнкцию формул \(  \large F_1,F_2, \ldots, F_k  \);

б) представить её в совершенной конъюнктивной нормальной форме;

в) выписать всевозможные элементарные дизъюнкции, образующие СКНФ, и всевозможные их конъюнкции.

Эти дизъюнкции и их конъюнкции являются искомыми следствиями (в том числе и формула \(  \large F_1F_2 \cdots  F_k  \)).

2) Пусть \(  \large G  \) - формула логики высказываний, которая зависит от переменных \(  \large P_1,P_2, \ldots, P_n  \). Чтобы найти все формулы-посылки (зависящие от тех же переменных), из которых следует эта формула, нужно:

а) найти СКНФ формулы \(  \large G  \);

б) найти все элементарные дизъюнкции, отсутствующие в СКНФ;

в) составить всевозможные конъюнкции формулы \(  \large G  \) с недостающими элементарными дизъюнкциями.

Сама формула \(  \large G  \) и данные конъюнкции являются искомыми посылками.

Замечание 6.15. В теореме 6.13 говорится лишь об опровержимых формулах. Но как быть с тождественно истинными формулами? Пусть \(  \large G  \) - тождественно истинная формула. Тогда

\(  \large F_1,F_2, \ldots, F_k \models G  \),

какими бы ни были формулы \(  \large F_1,F_2 , \ldots , F_k  \). Это вытекает из признака следования и определения импликации:

\(  \large  (F_1F_2 \cdots F_k) \to G \simeq  (F_1F_2 \cdots F_k) \to 1 \simeq 1 \).

Значит, тождественно истинная формула следует из любых формул логики высказываний.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #10 : Сентябрь 23, 2017, 10:53:28 am »
Для решения поставленной выше задачи можно использовать и совершенную дизъюнктивную нормальную форму. Сформулируем и докажем теорему, аналогичную теореме 6.13.

***

Теорема 6.14. Формула \(  \large G  \) следует из формул \(  \large F_1, F_2, \ldots , F_k  \) тогда и только тогда тогда, когда все элементарные конъюнкции, входящие в формулу \(  \large F_1F_2 \cdots F_k  \), входят в формулу \(  \large G  \).

Доказательство. Пусть \(  \large F_1,F_2, \ldots, F_k, G  \) - формулы, зависящие от переменных \(  \large P_1,P_2, \ldots, P_n  \) и представленные в СДНФ. Мы говорим лишь о выполнимых формулах, так как они представлены в совершенной дизъюнктивной нормальной форме. И пусть \(  \large K_1,K_2, \ldots , K_p, K_{p+1}, \ldots , K_l  \) - элементарные дизъюнкции, зависящие от переменных \(  \large P_1,P_2, \ldots, P_n  \).

1) Пусть

\(  \large F_1,F_2, \ldots, F_k \models G  \).

Предположим, что хотя бы одной элементарной конъюнкции, образующей формулу \(  \large F_1F_2 \ldots F_k  \), нет в формуле \(  \large G  \). Пусть, например,

\(  \large F \simeq K_1 \vee K_2 \vee  \ldots \vee K_p  \),

\(  \large G \simeq K_2 \vee  \ldots \vee  K_p \vee K_{p+1} \vee \ldots \vee K_l  \).

Учитывая определение следования, для любых высказываний \(  \large A_1,A_2, \ldots , A_n  \) если

\(  \large K_1(A_1, A_2, \ldots , A_n) \vee \ldots \vee K_p (A_1,A_2, \ldots , A_n)=1  \),

то

\(  \large K_2 (A_1,A_2, \ldots , A_n) \vee \ldots \vee K_l(A_1, A_2, \ldots , A_n)=1  \).

Из первого, в силу определения дизъюнкции, получаем, что хотя бы одно из высказываний

\(  \large K_1(A_1, A_2, \ldots , A_n), \ldots, K_p (A_1,A_2, \ldots , A_n)  \)

истинно. Пусть, например,

\(  \large K_1(A_1,A_2, \ldots , A_n)=1  \), \(  \large K_2(A_1,A_2, \ldots , A_n) = \ldots = K_p(A_1,A_2, \ldots , A_n)=0  \).

Значит,

\(  \large  K_2 (A_1,A_2, \ldots , A_n) \vee \ldots \vee K_l(A_1, A_2, \ldots , A_n) \simeq   \)

\(  \large \simeq 0 \vee 0 \vee \ldots \vee 0 \vee K_{p+1} (A_1,A_2, \ldots , A_n) \vee \ldots \vee K_l(A_1,A_2, \ldots , A_n) \simeq \)

\(  \large  \simeq K_{p+1} (A_1,A_2, \ldots , A_n) \vee \ldots \vee K_l(A_1,A_2, \ldots , A_n)    \).

Но все эти высказывания могут быть ложными. Однако они должны быть истинными, в противном случае

\(  \large  K_2(A_1,A_2, \ldots , A_n) \vee  \ldots \vee   K_l(A_1, A_2, \ldots , A_n)=0  \).

Противоречие. Значит, все элементарные конъюнкции, входящие в формулу \(  \large F_1F_2 \cdots F_k  \) входят и в формулу \(  \large G  \).

2) Пусть

\(  \large F \simeq K_1 \vee K_2 \vee \ldots \vee K_p  \),

\(  \large G \simeq  K_1 \vee K_2 \vee \ldots \vee K_p \vee K_{p+1} \vee \ldots \vee K_l \).

Предположим, что

\(  \large F_1,F_2, \ldots , F_k \not \models G  \).

Значит, существуют такие высказывания \(  \large A_1,A_2, \ldots , A_n  \), что

\(  \large K_1(A_1, A_2, \ldots , A_n) \vee \ldots \vee K_p(A_1,A_2, \ldots , A_n)=1  \)

и

\(  \large K_1(A_1, A_2, \ldots , A_n) \vee \ldots \vee K_l(A_1,A_2, \ldots , A_n)=0  \).

Из второго, согласно определению дизъюнкции,

\(  \large K_1(A_1, A_2, \ldots , A_n) = \ldots = K_l(A_1,A_2, \ldots , A_n)=0  \).

Значит,

\(  \large K_1(A_1, A_2, \ldots , A_n) \vee \ldots \vee K_p(A_1,A_2, \ldots , A_n)=0  \).

Снова получили противоречие. Следовательно,

\(  \large F_1,F_2, \ldots , F_k  \models G  \).

Теорема доказана.

Замечание 6.16. Снова воспользуемся законом противоположности, чтобы получить другую форму теоремы 6.14. Формула \(  \large G  \) не следует из формул \(  \large F_1, F_2, \ldots, F_k  \), если и только если существуют элементарные конъюнкции, входящие в формулу \(  \large F_1F_2 \cdots F_k  \) и не входящие в формулу \(  \large G  \).

Замечание 6.17. Из доказанной выше теоремы, как и из теоремы 6.13, следуют два алгоритма.

1) Рассмотрим формулы логики высказываний \(  \large F_1,F_2, \ldots, F_k  \), зависящие от переменных \(  \large P_1,P_2, \ldots, P_n  \). Чтобы найти все следствия этих посылок, которые зависят от тех же переменных, нужно:

а) составить конъюнкцию формул \(  \large F_1,F_2, \ldots, F_k  \);

б) найти совершенную дизъюнктивную нормальную форму этой формулы;

в) выписать все элементарные конъюнкции, которые отсутствуют в СДНФ, и составить всевозможные дизъюнкции этих конъюнкций с формулой \(  \large F_1F_2 \cdots F_k  \).

Сама формула \(  \large F_1F_2, \cdots F_k  \) и указанные выше дизъюнкции являются искомыми следствиями.

2) Рассмотрим формулу \(  \large G  \), которая зависит от переменных \(  \large P_1,P_2, \ldots, P_n  \). Чтобы найти все посылки (зависящие от тех же переменных), из которых следует эта формула, нужно:

а) найти СДНФ формулы \(  \large G  \);

б) выписать все элементарные конъюнкции, содержащиеся в совершенной дизъюнктивной нормальной форме;

в) составить дизъюнкции из этих конъюнкций (какие только возможно).

Данные конъюнкции и их дизъюнкции есть искомые посылки (в их число, естественно, войдёт и сама формула \(  \large G  \)).

Замечание 6.18. В теореме 6.14 речь идёт лишь о выполнимых формулах. Пусть хотя бы одна из формул \(  \large F_1,F_2, \ldots , F_k  \) является тождественно ложной. Тогда

\(  \large F_1,F_2, \ldots , F_k \models G  \),

какой бы ни была формула \(  \large G  \), так как, согласно определениям конъюнкции и импликации,

\(  \large  \models (F_1F_2 \cdots F_k) \to G  \).

Таким образом, из набора формул, где хотя бы одна является противоречием, следует любая формула.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #11 : Сентябрь 23, 2017, 10:54:47 am »
Рассмотрим задачи на нахождение посылок и следствий, где применяются обе доказанные выше теоремы, задачу, где нужно выяснить, следуют ли формулы друг из друга, основываясь на тех же теоремах, и задачу, где требуется доказать, что одна формула не следует из другой. Кроме того, докажем без использования равносильных преобразований правило силлогизма (уже известное нам) и закон Пирса.

***

Задача 6.1. Найти все зависящие от переменных \(  \large P  \) и \(  \large Q  \) формулы логики высказываний, которые являются следствиями данных формул:

\(  \large P \leftrightarrow Q, P'  \).

Полученные формулы упростить, используя основные равносильности классической логики высказываний.


Решение. Сначала используем СКНФ. Составим конъюнкцию формул и представим в совершенной конъюнктивной нормальной форме:

\(  \large (P \leftrightarrow Q)P' \simeq (P \to Q)(Q \to P)P' \simeq P' (P' \vee Q)(Q' \vee P)  \simeq   P' (Q' \vee P) \simeq  \)

\(  \large \simeq (P' \vee 0)(Q' \vee P) \simeq (P' \vee (QQ'))(Q' \vee P) \simeq (P' \vee Q)(P' \vee Q')(P \vee Q') \).

Выше мы избавились от эквиваленции и импликации, применили один из законов поглощения, правило \(  \large P \vee 0 \simeq P  \), закон противоречия и дистрибутивность дизъюнкции относительно конъюнкции.

Итак, в СКНФ присутствуют такие дизъюнкции:

\(  \large P' \vee Q,  \ P' \vee Q' , \ P \vee Q'  \).

Значит, следствиями формул \(  \large P \leftrightarrow Q  \) и \(  \large P'  \) являются формулы:

1) \(  \large P' \vee Q \simeq P \to Q  \);

2) \(  \large P \vee Q' \simeq Q \to P  \);

3) \(  \large P' \vee Q' \simeq P \to Q'  \);

4) \(  \large (P' \vee Q)(P \vee Q') \simeq P \leftrightarrow Q  \);

5) \(  \large (P' \vee Q)(P' \vee Q') \simeq P' \vee (QQ') \simeq P' \vee 0 \simeq P'  \);

6) \(  \large (P \vee Q')(P' \vee Q') \simeq Q' \vee (PP') \simeq Q' \vee 0 \simeq Q'  \);

7) \(  \large (P' \vee Q)(P' \vee Q')(P \vee Q') \simeq P' (Q' \vee P) \simeq (P'Q') \vee (P'P) \simeq (P'Q') \vee 0 \simeq P'Q' \).

Также к следствиям относится \(  \large 1  \), обозначающая произвольную тождественно истинную формулу, поскольку тождественно истинная формула следует из любой формулы.

Есть основания надеяться, что внимательный читатель сам разберётся, какие именно равносильности были использованы при упрощении формул, заглянув при необходимости в лекцию 4. Поэтому далее комментировать равносильные преобразования не будем.

Решим задачу другим способом, применяя СДНФ. Заметим, что совершенная дизъюнктивная нормальная форма формулы \(  \large (P \leftrightarrow Q) P'  \) уже найдена выше. Она состоит из одной-единственной элементарной конъюнкции: \(  \large P'Q'  \). Значит, в СДНФ отсутствуют такие конъюнкции:

\(  \large PQ, \ P'Q , \ PQ'  \).

Тогда следствиями будут такие формулы логики высказываний:

1) \(  \large (P'Q') \vee (PQ) \simeq (P' \vee P)(Q' \vee P)(P' \vee Q)(Q' \vee Q) \simeq (Q' \vee P)(P' \vee Q) \simeq P \leftrightarrow Q  \)

2) \(  \large (P'Q') \vee (P' Q) \simeq P' \vee (Q'Q) \simeq P' \vee 0 \simeq P'  \);

3) \(  \large (P'Q') \vee (PQ') \simeq Q' \vee (P'P) \simeq Q' \vee 0 \simeq Q'  \);

4) \(  \large (P'Q') \vee (PQ) \vee (P'Q) \simeq (PQ) \vee P' \simeq (P \vee P')(Q \vee P') \simeq P \to Q  \);

5) \(  \large (P'Q') \vee (PQ) \vee (PQ') \simeq Q' \vee (PQ) \simeq (Q' \vee P)(Q' \vee Q) \simeq Q \to P  \);

6) \(  \large (P'Q') \vee (P'Q) \vee (PQ') \simeq P' \vee (PQ') \simeq (P' \vee P)(P' \vee Q') \simeq P \to Q'  \);

7) \(  \large P'Q'  \);

8) \(  \large (P'Q') \vee (P'Q) \vee (PQ') \vee (PQ) \simeq P' \vee P \simeq 1   \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #12 : Ноябрь 08, 2017, 04:38:48 pm »
Задача 6.2. Найти все формулы логики высказываний, зависящие от переменных \(  \large P_1  \) и \(  \large P_2 \), для которых формула

\(  \large (P_1 \vee P_2) \to (P_1P_2)  \)

является следствием. Упростить полученные формулы.

Решение. Представим формулу в СДНФ:

\(  \large (P_1 \vee P_2) \to (P_1P_2) \simeq  \)

\(  \large (P_1 \vee P_2)' \vee (P_1P_2) \simeq (P_1'P_2') \vee (P_1P_2)   \).

Значит, посылками будут:

1) \(  \large P_1'P_2'  \);

2) \(  \large P_1P_2  \);

3) \(  \large (P_1'P_2') \vee (P_1P_2) \simeq (P_1' \vee P_1)(P_2' \vee P_1)(P_1' \vee P_2)(P_2' \vee P_2) \simeq   \)

\(  \large \simeq (P_2 \to P_2)(P_1 \to P_2) \simeq P_1 \leftrightarrow P_2  \).

Кроме того, в число посылок входит и \(  \large 0  \) (произвольная тождественно ложная формула), так как тождественно ложная формула является посылкой для любой формулы классической логики высказываний.

Решим задачу другим способом. Для этого представим исходную формулу в совершенной конъюнктивной нормальной форме:

\(  \large (P_1'P_2') \vee (P_1P_2) \simeq (P_1' \vee P_1)(P_2' \vee P_1)(P_1' \vee P_2)(P_2' \vee P_2) \simeq   \)

\(  \large \simeq (P_1 \vee P_2')(P_1' \vee P_2)  \).

В СКНФ отсутствуют такие элементарные дизъюнкции:

\(  \large P_1 \vee P_2, \ P_1' \vee P_2'  \).

Значит, посылками будут:

1) \(  \large (P_1  \vee P_2') (P_1' \vee P_2) \simeq P_1 \leftrightarrow P_2 \);

2) \(  \large (P_1  \vee P_2') (P_1' \vee P_2)(P_1 \vee P_2) \simeq (P_1 \vee P_2')P_2 \simeq P_1P_2  \);

3) \(  \large (P_1  \vee P_2') (P_1' \vee P_2)(P_1' \vee P_2') \simeq (P_1 \vee P_2')P_1' \simeq P_1'P_2'  \);

4) \(  \large (P_1  \vee P_2') (P_1' \vee P_2)(P_1' \vee P_2') (P_1 \vee P_2) \simeq P_1P_1' \simeq 0  \)
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #13 : Ноябрь 10, 2017, 02:38:02 pm »
Задача 6.3. Используя совершенные нормальные формы, выяснить, следует ли одна формула из другой, и наоборот:

\(  \large (P \to Q)(Q' \to P), \ P' \to Q  \).

Решение. Представим обе формулы в СКНФ:

1) \(  \large (P \to Q)(Q' \to P) \simeq (P' \vee Q)(P \vee Q'') \simeq (P' \vee Q)(P \vee Q)  \);

2) \(  \large P' \to Q \simeq P'' \vee Q \simeq P \vee Q  \).

Тогда

\(  \large (P \to Q)(Q' \to P) \models P' \to Q, \ P' \to Q \not \models (P \to Q)(Q' \to P)  \).

Теперь решим ту же задачу с помощью СДНФ:

1) \(  \large  (P' \vee Q)(P \vee Q) \simeq (P'P) \vee (QP) \vee (P'Q) \vee (QQ) \simeq (P'Q) \vee Q \simeq (P'Q) \vee (PQ) \);

2) \(  \large P \vee Q \simeq (P (Q \vee Q')) \vee ((P' \vee P)Q) \simeq (PQ) \vee (PQ') \vee (P' Q)  \).

Снова получим тот же самый ответ

\(  \large (P \to Q)(Q' \to P) \models P' \to Q, \ P' \to Q \not \models (P \to Q)(Q' \to P)  \).

Итак, формула \(  \large P' \to Q  \) следует из формулы \(  \large (P \to Q)(Q' \to P)  \), но обратное неверно.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #14 : Ноябрь 10, 2017, 02:38:48 pm »
Задача 6.4. Доказать, что формула \(  \large P \to Q  \) не следует из формулы \(  \large (P \to Q) \to P  \)".

Решение. Согласно признаку следования формул, высказывание \(  \large P \to Q \models (P \to Q) \to P  \) эквивалентно высказыванию \(  \large \models (P \to Q) \to ((P \to Q) \to P)  \). Проверим истинность последнего высказывания, используя законы алгебры высказываний. Сначала избавимся от внутренних импликаций, выразив их через дизъюнкцию и отрицание:

\(  \large (P \to Q) \to ((P \to Q) \to P) \simeq (P' \vee Q) \to ((P' \vee Q)' \vee P) \).

Теперь избавимся от внешней импликации и используем идемпотентность дизъюнкции:

\(  \large (P' \vee Q) \to ((P' \vee Q)' \vee P) \simeq (P' \vee Q)' \vee (P' \vee Q)' \vee P \simeq (P' \vee Q)' \vee P \).

Далее применим один из законов де Моргана и закон двойного отрицания:
 
\(  \large (P' \vee Q)' \vee P \simeq (P'' Q') \vee P \simeq (PQ') \vee P  \).

Осталось воспользоваться одним из законов поглощения:

\(  \large (PQ') \vee P \simeq P  \).

Итак, формула  \(  \large (P \to Q) \to ((P \to Q) \to P)  \) равносильна формуле \(  \large P  \), которая опровержима. Итак, формула \(  \large P \to Q  \) не следует из формулы \(  \large (P \to Q) \to P  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #15 : Ноябрь 10, 2017, 02:39:59 pm »
Задача 6.5. Не используя равносильные преобразования, доказать правило силлогизма:

\(  \large P \to  Q, \ Q \to R \models P \to R \).

Решение. Данная задача эквивалентна задаче о доказательстве тождественной истинности формулы

\(  \large  ((P \to  Q)(Q \to R)) \to (P \to R) \).

Предположим, что данная формула логики высказываний не является тождественно истинной. Значит, найдутся такие высказывания \(  \large A \), \(  \large B \) и \(  \large C \), что высказывание

\(  \large ((A \to B)(B \to C)) \to (A \to C) \)

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

\(  \large (A \to B)(B \to C)=1 \), \(  \large A \to C=0 \).

Тогда

\(  \large A=1 \), \(  \large C=0 \).

Конъюнкция, согласно определению, истинна, если и только если истинны оба её члена. Значит,

\(  \large A \to B=1 \), \(  \large B \to C=1 \).

Нам известно, что

\(  \large A=1 \), \(  \large C=0 \).

Тогда

\(  \large 1 \to B=1 \), \(  \large B \to 0=1 \).

Первое возможно только в случае, если высказывание \(  \large B \) истинно, а второе - если то же самое высказывание ложно. Получили противоречие, которое доказывает, что рассматриваемая формула логики высказываний тождественно истинна.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #16 : Ноябрь 10, 2017, 04:32:08 pm »
Задача 6.6. Доказать закон Пирса, не используя равносильные преобразования:

\(  \large (P \to Q) \to P \models P \).

Решение. Это следование выполняется тогда и только тогда, когда формула

\(  \large ((P \to Q) \to P) \to P \)

является тавтологией. Чтобы доказать это, нужно знать определения импликации и тавтологии, а также тот факт, что в классической логике каждое высказывание принимает в точности одно логическое значение - истина или ложь. Пусть \(  \large A \) и \(  \large B \) - некоторые высказывания. Рассмотрим составное высказывание

\(  \large ((A \to B) \to A ) \to A \).

Предположим, что оно ложно. Импликация, как известно, ложна только в одном случае: истинная посылка и ложное заключение. Итак, высказывание \(  \large A \) ложно, а высказывание \(  \large (A \to B) \to A \) истинно. Поскольку  последнее высказывание истинно, то, учитывая, что высказывание \(  \large A \) ложно, делаем вывод о ложности высказывания \(  \large A \to B \) (снова использовали определение импликации). Значит, высказывание \(  \large A \) истинно, а высказывание \(  \large B \) ложно. Но высказывание \(  \large A \) ложно. Противоречие. Следовательно, высказывание \(  \large ((A \to B) \to A ) \to A \) не может принимать логическое значение "ложь", какими бы ни были высказывания \(  \large A  \) и \(  \large B  \). Итак, формула логики высказываний \(  \large ((P \to Q) \to P ) \to P  \) является тавтологией.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #17 : Ноябрь 12, 2017, 01:23:38 pm »
Задача 6.7. Проверить правильность умозаключения. Анатолий и Аделина одного возраста, или Анатолий старше Аделины. Если Анатолий и Адедина одного возраста, то Ника и Аделина не одного возраста. Если Анатолий старше Аделины, то Аделина старше Ферапонта. Следовательно, Ника и Аделина не одного возраста или Аделина старше Ферапонта.

Решение. Введём обозначения: \(  \large P  \) - Анатолий и Аделина одного возраста, \(  \large Q  \) - Анатолий старше Аделины, \(  \large R    \) - Ника и Аделина одного возраста, \(  \large S  \) - Аделина старше Ферапонта. Значит, задача сводится к проверке, следует ли из формул \(  \large P \vee Q  \), \(  \large P \to \overline{R}  \), \(  \large Q \to S  \) формула \(  \large \overline{R} \vee S  \). Предположим, что умозаключение неправильно (следование не выполняется). Значит, найдутся такие высказывания \(  \large A, \ B, \ C, \ D  \), что

\(  \large A \vee B =A \to \overline{C}= B \to D=1  \), \(  \large \overline{C} \vee D=0  \).

Легко показать, что наше предположение ошибочно. Ложность дизъюнкции \(  \large \overline{C} \vee D  \) означает ложность высказываний \(  \large \overline{C}  \) и \(  \large D  \). Тогда

\(  \large A \to 0=1, B \to 0=1  \).

А это возможно тогда и только тогда, когда \(  \large A=B=0  \). Но в этом случае \(  \large A \vee B=0  \). Противоречие. Значит, следование выполняется, а умозаключение правильно.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #18 : Ноябрь 12, 2017, 02:34:18 pm »
Задача 6.8. Проверить правильность умозаключения. Если Джон болен, то у него болит голова. Если у него болит голова, то он пьет лекарство от головной боли. Джон пьёт лекарство от головной боли. Следовательно, Джон болен.

Решение. Формализуем посылки и следствие данного умозаключения. Пусть \(  \large P  \) обозначает "Джон болен", \(  \large Q  \) - "У Джона болит голова", \(  \large R  \) - "Джон пьёт лекарство от головной боли". Тогда задача сводится к проверке следования

\(  \large P \to Q, \ Q \to R, \ R \models P  \).

А эта задача, как известно, эквивалентна задаче о проверке тождественной истинности формулы

\(  \large ((P \to Q) ( Q \to R)  R) \to P  \).

Предположим, что рассматриваемая формула логики высказываний опровержима. Значит, найдутся такие высказывания \(  \large A, \ B, \ C  \), что высказывание

\(  \large ((A \to B)(B \to C)C) \to A  \)

ложно. Учитывая определения логических связок, оно ложно тогда и только тогда, когда высказывание \(  \large (A \to B)(B \to C)C  \) истинно, а высказывание \(  \large A  \) ложно. Высказывание  \(  \large (A \to B)(B \to C)C  \) истинно, если и только если все члены конъюнкции истинны. Итак, высказывания \(  \large A \to B, \ B \to C, \ C  \) истинны. Поскольку \(  \large A  \) ложно,а \(  \large C  \) истинно, то \(  \large B  \) может быть как истинным, так и ложным:

\(  \large A \to B= 0 \to 0=1, \ A \to B= 0 \to 1 =1  \);

\(  \large B \to C= 0 \to 1=1, \ B \to C = 1 \to 1 =1  \).

Значит, существуют такие высказывания \(  \large A, \ B, \ C  \), что высказывание

\(  \large ((A \to B)(B \to C)C) \to A  \)

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

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 6. Следование формул логики высказываний
« Ответ #19 : Декабрь 05, 2017, 09:02:32 pm »
Задача 6.9. Выяснить, является ли умозаключение логически правильным. Если капиталовложения останутся постоянными, то возрастут правительственные расходы или возрастёт безработица. Если правительственные расходы не возрастут, то налоги будут снижены. Если налоги будут снижены и капиталовложения останутся постоянными, то безработица не возрастёт. Безработица не возрастёт Следовательно, правительственные расходы возрастут.

Решение. Введём обозначения. Пусть буквой \(  \large P  \) обозначено высказывание "Капиталовложения останутся постоянными", буквой \(  \large Q  \) - высказывание "Возрастут правительственные расходы", буквой \(  \large R  \) - "Возрастёт безработица", буквой \(  \large S  \) - "Налоги будут снижены". Значит, нам нужно проверить, выполняется ли следование

\(  \large P \to (Q \vee R), Q' \to S, (SP) \to R', R' \models Q  \).

Предположим, что данное следование не выполняется. Тогда найдутся такие высказывания \(  \large A,B,C,D  \), что

\(  \large A \to (B \vee C) =1, B' \to D=1, (DA) \to C'=1, C'=1,B=0  \).

Выясним, приводит ли наше предположение к противоречию. Если приводит, то оно неверно (и следование выполняется). Если не приводит, то предположение верно (и следование не выполняется). Поскольку

\(  \large C'=1,B=0  \),


то

\(  \large B=C=0  \).

Значит, во-первых,

\(  \large A \to (B \to C)=A \to (0 \vee 0)=A \to 0  \).

Учитывая, что

\(  \large A \to (B \vee C)=1  \),

получаем:

\(  \large A=0  \).

Во-вторых,

\(  \large B' \to D=0' \to D=1 \to D  \).

Зная, что

\(  \large B' \to D=1  \),

получаем:

\(  \large D=1  \).

Наконец, в-третьих,

\(  \large (DA) \to C'=(1 \cdot 0) \to 1 =0 \to 1 =1  \).

Но мы и так знаем, что

\(  \large (DA) \to C'=1  \).

Противоречия нет. Следование, умозаключение логически правильно.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 6. Следование формул логики высказываний
« Ответ #20 : Февраль 16, 2018, 04:33:44 pm »
Задача 6.10. Проверить, следует ли заключение из посылок. Если исходные данные корректны и программа работает правильно, то получается верный результат. Результат неверен. Следовательно, исходные данные некорректны или программа работает неправильно.

Решение. Введём обозначения: \(  \large P_1  \) - "Исходные данные корректны", \(  \large P_2   \) - "Программа работает правильно", \(  \large P_3  \) - "Получается верный результат". Тогда первая посылка записывается, как

\(  \large (P_1 P_2) \to P_3  \),

вторая посылка -

\(  \large P_3'  \),

а заключение -

\(  \large P_1' \vee P_2'  \).

Проверим, выполняется ли следование

\(  \large (P_1  P_2) \to P_3, P_3' \models P_1' \vee P_2'  \).

Данная задача эквивалентна задаче о проверке тождественной истинности формулы алгебры высказываний

\(  \large (((P_1 P_2) \to P_3) P_3') \to  (P_1' \vee P_2' )  \).

Упростим формулу, используя равносильные преобразования:

\(  \large (((P_1 P_2) \to P_3) P_3') \to  (P_1' \vee P_2' ) \simeq ((P_1' \vee P_2' \vee P_3)P_3') \to (P_1' \vee P_2') \simeq  \)

\(  \large \simeq (P_1P_2P_3') \vee P_3 \vee P_1' \vee P_2' \simeq (P_1 \vee P_3 \vee P_1' \vee P_2' )(P_2 \vee  P_3 \vee P_1' \vee P_2' )(P_3' \vee   P_3 \vee P_1' \vee P_2' ) \simeq  \)

\(  \large \simeq (1 \vee P_3 \vee P_2')(1 \vee P_3 \vee P_1')(1 \vee P_1' \vee P_2') \simeq 1  \).

Итак, формула тождественно истинна, значит, заключение следует из посылок.