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

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

Основы логики и логические основы компьютера

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

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

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

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

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

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

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

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

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

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

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