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

Простые высказывания:

• $A = $ капиталовложения останутся постоянными;
• $B = $ возрастут правительственные расходы;
• $C = $ возрастет безработица;
• $D = $ налоги будут снижены.

На основе простых высказываний построим сложные высказывания:

• $\mathcal A = A\supset (B\vee C)$,
• $\mathcal B = \neg B\supset D$,
• $\mathcal C = (D\wedge A)\supset\neg C$.

Здесь высказывание $\mathcal A$ можно прочитать как "если капиталовложения останутся постоянными, то возрастут правительственные расходы, или возрастет безработица" . Аналогично можно читать и другие сложные высказывания.

Замечание

Для определенности здесь и далее простые высказывания будем обозначать большими латинскими буквами $A$, $B$, $C$,..., а сложные высказывания округлыми большими латинскими буквами $\mathcal A$, $\mathcal B$, $\mathcal C$,...

Здесь $A$, $B$, $C$ — пропозициональные буквы, $\mathcal A$, $\mathcal B$, $\mathcal C$ — пропозициональные формы, построенные из пропозициональных букв с помощью связок $\{\neg, \vee, \wedge, \supset, \equiv\}$ по правилам построения формул алгебры логики.

Рассмотрим следующее рассуждение: [math]\displaystyle{ \begin{array}{cl} \begin{array}{c} \mathcal A, \mathcal B, \mathcal C, A \\ \hline B \end{array} & \begin{array}{l} - \textrm{ посылки} \\ - \textrm{ заключение} \end{array} \end{array} }[/math]

Определение:

Высказывание $\mathcal A$ логически влечет высказывание $\mathcal B$ ($\mathcal B$ — следствие $\mathcal A$), если пропозициональная форма $\mathcal A \supset \mathcal B$ — тавтология.

Определение:

$\mathcal A$ логически эквивалентно $\mathcal B$, если $\mathcal A\equiv \mathcal B$ — тавтология.

Итак, нам необходимо проверить, будет ли тавтологией следующая пропозициональная форма: [math]\displaystyle{ \underbrace{ \mathcal A\wedge \mathcal B\wedge \mathcal C\wedge A }_{\textrm{конъюнкция посылок}} \supset \underbrace{B}_{\textrm{заключение}} =1  ? }[/math]

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

Кроме того, по определению импликации, если $\mathcal A=0$, то $\mathcal A\supset \mathcal B=1$ для любых значений $\mathcal B$, что совсем не будет свидетельствовать о правильном рассуждении. Это согласуется с одним из интуитивных логических законов: исходя из ложных посылок можно вывести как истинное, так и ложное заключение.

Проверим, выполнима ли формула $\mathcal A\wedge \mathcal B\wedge \mathcal C\wedge A$. Такую проверку для посылок нужно выполнять каждый раз.

[math]\displaystyle{ \begin{align} &(A\supset(B\vee C))(\overline B\supset D)(DA\supset\overline C)A = \\ &= (\overline A\vee B\vee C)(B\vee D) (\overline D\vee \overline A \vee \overline C)A = \\ &= (\overline A B\vee \overline A D \vee B \vee B D \vee C B\vee C D) (\overline D A\vee \overline C A)= \\ &= \overline A B \overline D A \vee \overline A B \overline C A \vee \overline A D \overline D A \vee \overline A D \overline C A \vee B \overline D A \vee B \overline C A \vee B D \overline D A \vee B D \overline C A \vee C B \overline D A \vee C B \overline C A \vee C D \overline D A \vee C D \overline C A = \\ &= B \overline D A \vee B \overline C A \vee B D \overline C A \vee C B \overline D A = A B \overline D \vee A B \overline C \end{align} }[/math]

Легко убедиться, что, например, на наборе значений $A=1$, $B=1$, $C=1$, $D=0$ полученное выражение обращается в единицу. Таким образом, $\mathcal A\wedge \mathcal B\wedge \mathcal C\wedge A$ — выполнимая функция, т.е. посылки непротиворечивы.

Рис. 1. Посылки истинны ровно на трёх наборах, и на всех трёх [math]\displaystyle{ B=1 }[/math] — поэтому формула «конъюнкция посылок [math]\displaystyle{ \supset B }[/math]» является тавтологией. Проверять остальные пять наборов не нужно: там посылки ложны.

Вычислим теперь значение выражения $\mathcal A\wedge \mathcal B\wedge \mathcal C\wedge A \supset B$, воспользовавшись результатами предыдущих выкладок:

[math]\displaystyle{ \begin{align} &(A B \overline D \vee A B \overline C) \supset B = \overline{A B \overline D \vee A B \overline C} \vee B =\\ &= \overline{A B \overline D} \cdot \overline{A B \overline C}\vee B = (\overline A \vee \overline B \vee D) (\overline A\vee \overline B\vee C)\vee B = \\ &= \overline A \vee \overline A \overline B \vee \overline A C\vee \overline B \vee \overline B C\vee D\overline A \vee D\overline B \vee D C \vee B=\\ &=(\overline A\vee \overline B\vee DC)\vee B= 1 \end{align} }[/math]

Исследуемая формула оказалась тавтологией. Значит, высказывание $B$ действительно оказалось логическим следствием посылок $\mathcal A$, $\mathcal B$, $\mathcal C$ и $A$.

При этом мы нигде не обсуждаем истинность самих высказываний $\mathcal A$, $\mathcal B$, $\mathcal C$, $A$; возможно они неверны. Тем не менее, если они истинны, то верным окажется и заключение.

Заметим, что мы рассматривали истинность только логики рассуждений независимо от смысла, который мы приписываем элементарным высказываниям $A$, $B$, $C$, $D$. Если мы определим отличные значения для элементарных высказываний, истинность или ложность логики рассуждений останется неизменной. Если при новых определениях будут верны посылки, верным будет и заключение.

Конспект: Дискретная математика