Решение логических задач

11Б. Решение логических задач

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

Дистрибутивность умножения относительно сложения Дистрибутивность сложения относительно умножения

аb + ас = а(b+с) — в алгебре

(А&В)v(A&С)=A&(ВvС) (А v В) & (А v С) = А v (В & С)

Рассмотрим в качестве примера применения законов логики преобразование логического выражения. Пусть нам необходимо упростить логическое выражение:

(А & В) v (А & В).

Воспользуемся законом дистрибутивности и вынесем за скобки А:

(А & В) v (А & В) = А & (В v В).

По закону исключенного третьего В v В =1, следовательно:

А & (В v В) = А & 1 = А.

Условие задачи. В школе-новостройке в каждой из двух аудиторий может находиться либо кабинет информатики, либо кабинет физики. На дверях аудиторий повесили шутливые таблички. На первой повесили табличку «По крайней мере, в одной из этих аудиторий размещается кабинет информатики», а на второй аудитории — табличку с надписью «Кабинет физики находится в другой аудитории». Проверяющему, который пришел в школу, известно только, что надписи на табличках либо обе истинны, либо обе ложны. Помогите проверяющему найти кабинет информатики. Решение задачи. Переведем условие задачи на язык логики высказываний. Так как в каждой из аудиторий может находиться кабинет информатики, то пусть: А = «В первой аудитории находится кабинет информатики»; Б = «Во второй аудитории находится кабинет информатики».

Отрицания этих высказываний:

А= «В первой аудитории находится кабинет физики»; В = «Во второй аудитории находится кабинет физики».

Высказывание, содержащееся на табличке на двери первой аудитории, соответствует логическому выражению:

X = АvВ.

Высказывание, содержащееся на табличке на двери второй аудитории, соответствует логическому выражению:

У = А.

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

(X &Y) v(X & Y) = 1. Подставим вместо X и У соответствующие формулы:

(X & Y) v (X & Y) = ((А v В) & А) v ((А v В) & А). Упростим сначала первое слагаемое. Всоответствии с законом дистрибутивности умножения относительно сложения:

(А v В) & А = А & А v В & А. В соответствии с законом непротиворечия:

А & А v В & А = О v В & А.

Упростим теперь второе слагаемое. В соответствии с первым законом де Моргана и законом двойного отрицания:

(А v В) &А=А&В&А = А&А&В.В соответствии с законом непротиворечия:А&А&В=0&В = 0. В результате получаем:

(О v В & А) v 0 = В & А.

Полученное логическое выражение оказалось простым и поэтому его можно проанализировать без построения таблицы истинности. Для того чтобы выполнялось равенство В&А = 1,В и А должны быть равны 1, то есть соответствующие им высказывания истинны.

Ответ: В первой аудитории находится кабинет физики, а во второй — кабинет информатики.