Упражнение 2. Следующие высказывания могут быть интерпритированы как составные

Следующие высказывания могут быть интерпритированы как составные. Указать элементарные высказывания их составляющие, написать формулы данных высказываний и построить истинностные таблицы. Указать, какие из высказываний равносильны.

S₁: Х неверно сделал расчет или если Y считал задачу правильно, то и Z сделал это без ошибок.

S₂: Если Х правильно просчитал задачу, то либо Y ошибся, либо Z сделал ее верно.

S₃: Либо Х неверно просчитал задачу, либо Y решил ее верно в том и только в том случае, если Z решил ее верно.

Очевидно, данные сложные высказывания составлены из следующих элементарных.

А: Х правильно просчитал задачу

B: Y правильно просчитал задачу

C: Z правильно просчитал задачу

Используя основные логические связки, запишем формулы данных высказываний.

Составим истинностные таблицы данных высказываний:

Таблица.7

А	В	С	В®С	S1		S2	В«С	S3

Из таблицы 7 видно, что высказывания S₁ и S₂ равносильны: S₁=S₂.

Приведем список основных равносильных формул алгебры высказываний:

	АÚ А=А
	АÙ А=А
	АÚ В=ВÚ А
	АÙ В=ВÙ А
	(АÚ В)Ú С=АÚ (ВÚ С)
	(АÙ В) Ù С=АÙ (ВÙ С)
	АÙ (ВÚ С)=(АÙ В) Ú (АÙ С)
	АÚ (ВÙ С)=(АÚ В) Ù (АÚ С)
	AÚ И=И
	AÙ Л=Л
	AÙ И=A
	AÚ Л=A
	AÚ =И	закон исключенного третьего
	AÙ =Л
	=И
	=Л

Отметим, что операции импликации и двойной импликации можно заменить дизъюнкцией, конъюнкцией, отрицанием, используя следующие равносильные формулы:

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

Высказыванию, истинному во всех логически возможных случаях, т.е. логической константе, обозначаемой 1 или И, будет соответствовать универсальное множество. Высказыванию, ложному во всех логически возможных случаях, т.е. логической константе, обозначаемой 0 или Л,

будет соответствовать пустое множество. Тогда дизъюнкции двух высказываний будет соответствовать объединение (сумма) их множеств истинности, конъюнкции - пересечение их множеств истинности, а отрицанию к высказыванию - дополнение к множеству истинности данного высказывания. Учитывая это и сравнивая список основных равносильных формул алгебра высказываний со списком свойств основных операций над множествами, убеждаемся в том, что операции алгебры высказываний образуют Булеву алгебру.

Заметим следующее: для того, чтобы убедиться в равносильности двух формул, можно построить их истинностные таблицы и убедиться в их совпадении. Равносильность формул можно установить также, убедившись в совпадении множеств истинности рассматриваемых высказываний. Так в справедливости закона дистрибутивности №7 можно убедиться, изобразив на диаграммах Эйлера-Венна множества истинности левой и правой части равенства (рис. 2.1.1).

Рис. 1.

Установить равносильность формул можно также путем их преобразования. Так заменяя импликацию равносильной ей формулой получим равносильность формул S₁ и S₂ упражнения 2.1.2:

Рассмотрим некоторые упражнения на данную тему.