Решение задач с помощью алгебры высказываний

Отношение логического следования используется при исследовании рассуждений.

Задача 1. Если $6$ – составное число $(S)$, то $12$ – составное число $(W)$. Если $12$ – составное число, то существует простое число, больше чем $12 (P)$. Если существует простое число больше $12$, то существует составное число больше $12 (C)$. Если $6$ делится на $2 (D)$, то $6$ – составное число. Число $12$ составное. Следовательно, $6$ – составное число.

Посылки: $S\rightarrow W , W\rightarrow P , P\rightarrow C , D\rightarrow S , W$

Заключение: $S$

Решение:

$$( S\rightarrow W )\And ( W\rightarrow P )\And ( P\rightarrow C )\And ( D\rightarrow S )\And W\rightarrow S\equiv \overline { S\rightarrow W } \vee \overline { W\rightarrow P } \vee \overline { P\rightarrow C } \vee $$ $$\vee \overline { D\rightarrow S } \vee \bar W\vee S\equiv ( S\And \bar W )\vee ( W\And \bar P )\vee ( P\And \bar C )\vee ( D\And \bar S )\vee \bar W \equiv S\vee ( \ W\And \bar P )\vee $$ $$\vee (P\And \bar C )\vee ( D\And \bar S )\vee \bar W\equiv ( S\vee D )\vee \bar W\vee \bar P\vee ( P\And \bar C )\equiv S\vee D\vee W\vee P\vee C$$

Данное высказывание тавтологией не является, значит из указанных посылок не следует высказывание «6 – составное число».

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

Посылки: $A\vee B , A\rightarrow C , B\rightarrow D$

Заключение: $C\vee D$

Значит из данных посылок следует $C\vee D$ .

Решение:

$$( A\vee B )\And ( A\rightarrow C )\And ( B\rightarrow D )\rightarrow ( C\vee D )\equiv \overline { A\vee B } \vee \overline { A\rightarrow C } \vee \overline { B\rightarrow D } \vee C\vee D\equiv $$ $$\equiv (\bar A\And \bar B )\vee ( A\And \bar C )\vee ( B\And \bar D )\vee C\vee D\equiv ( \bar A\And \bar B )\vee A\vee C\vee B\vee D\equiv $$ $$\equiv \bar A\vee B\vee C\vee A\vee D\equiv 1$$

Задача 3. Я пойду домой $(H)$ или останусь здесь и выпью стаканчик $(S)$. Я не пойду домой. Следовательно, я останусь и выпью.

Посылки: $H\vee S , \bar H$

Заключение: $S$

Решение:

$$( H\vee S )\And \bar H\rightarrow S\equiv ( \bar H\And \bar S )\vee H\vee S\equiv ( H\vee \bar H )\And ( \bar S\vee H )\vee S\equiv \bar S\vee H ∨ S\equiv 1$$

Значит, высказывание «я останусь и выпью» является логическим следствием из данных посылок.

Задача 4. В некотором царстве-государстве повадился Змей Горыныч разбойничать. Послал царь четырёх богатырей погубить Змея. Награду за то обещал великую. Вернулись богатыри с победой, и спрашивает их царь: «Так кто же из вас главный победитель, кому достанется царёва дочь и полцарства?».

Засмущались, добры молодцы и ответы дали туманные:

Сказал Илья Муромец: «Это всё Алёша Попович, царь-батюшка»;

Алёша Попович возразил: «То был Микула Селянинович»;

Микула Селянинович: «Не прав Алёша, не я то»;

Добрыня Никитич: «И не я, царь-батюшка».

Подвернулась тут Баба-Яга и говорит царю: «А прав-то лишь один из богатырей, видела я всю битву своими глазами».

Кто же из богатырей победил Змея Горыныча?

Решение задачи:

Определяемся с системой обозначений для логических высказываний:

  • $A$ – Алёша Попович;
  • $M$ – Микула Селянинович;
  • $D$ – Добрыня Никитич.

Илья Муромец первым перед царём-батюшкой слово держал, но про него никто ничего не сказал

  • $A$ «Это всё Алёша Попович, царь-батюшка» – это Алёша Попович
  • $M$ «То был Микула Селянинович» – это Микула Селянинович
  • $\bar M$ «Не прав Алёша, не я то» – это не Микула Селянинович
  • $\bar D$ «И не я, царь-батюшка» – это не Добрыня Никитич

Сведём выше сказанное в единое целое { логическая связка «И» } :

$$A\And M\And \bar M \And \bar D$$

Учитывая слова Бабы-Яги: «А прав-то лишь один из богатырей, видела я всю битву своими глазами»:

  • $A\And \bar { M } \And \bar { \bar { M } } \And \bar { \bar { D } } $ Правду сказал Илья Муромец
  • $\bar { A } \And { M } \And \bar { \bar { M } } \And \bar { \bar { D } } $ Правду сказал Алёша Попович
  • $\bar { A } \And \bar { M } \And \bar { M } \And \bar { \bar { D } } $ Правду сказал Микула Селянинович
  • $\bar { A } \And \bar { M } \And \bar { \bar { M } } \And \bar { D } $ Правду сказал Добрыня Никитич

Конструируем итоговую логическую формулу, описывающую логические связи между всеми высказываниями условия задачи. По условию нашей задачи прав только один из богатырей { логическая связка «ИЛИ» } :

$$A \bar { M } \bar { \bar { M } } \bar { \bar { D } } + \bar { A } { M } \bar { \bar { M } } \bar { \bar { D } } + \bar { A } \bar { M } \bar { M } \bar { \bar { D } } + \bar { A } \bar { M } \bar { \bar { M } } \bar { D } $$

Определяем значения истинности логической формулы. Упрощаем формулу.

Используем операции и законы алгебры логики и учитываем, что по условию нашей задачи: $A\And M = 0; A\And D = 0; M\And D = 0$

$$A \bar { M } \bar { \bar { M } } \bar { \bar { D } } + \bar { A } { M } \bar { \bar { M } } \bar { \bar { D } } + \bar { A } \bar { M } \bar { M } \bar { \bar { D } } + \bar { A } \bar { M } \bar { \bar { M } } \bar { D } = $$ $$= A \bar { M } \bar { \bar { M } } \bar { \bar { D } } (A \bar { M } { M } \bar { \bar { D } } = 0) + \bar { A } { M } \bar { \bar { M } } \bar { \bar { D } } (\bar { A } { M } { D } = 0) + $$ $$+ \bar A \bar { M } \bar { M } \bar { \bar { D } } (\bar A\bar { M } { D } ) + \bar { A } \bar { M } \bar { \bar { M } } \bar { D } (\bar { A } \bar { M } { M } \bar { D } = 0) = \bar A\bar M D $$

Ответ: Змея Горыныча победил Добрыня Никитич