Алгебра Логики

РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ

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

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

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

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

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

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

    Содержащееся в условии задачи утверждение о том, что надписи на табличках либо одновременно истинные, либо одновременно ложные в соответствии с законом исключенного третьего записывается следующим образом:
        (Х&Y)v(¬Х& ¬Y) = 1.

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

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

В соответствии с законом непротиворечия:
        А&¬А v В & А = 0 v В&¬А.
Упростим теперь второе слагаемое. В соответствии с первым законом де Моргана и законом двойного отрицания:
        ¬(А v В) & ¬¬А = ¬А & ¬В & А =¬А & А & ¬В

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

В результате получаем:
        (0 v В & ¬А) v 0 = В & ¬А.

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

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