Упражнение 2.1.2

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

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

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

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

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

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

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

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

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

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

Таблица 2.18

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

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

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

	АÚА=А	идемпотентность
	АÙА=А
	АÚВ=ВÚА	коммутативность
	АÙВ=ВÙА
	(АÚВ)ÚС=АÚ(ВÚС)	ассоциативность
	(АÙВ) ÙС=АÙ (ВÙС)
	АÙ (ВÚС)=(АÙВ) Ú(АÙС)	дистрибутивность
	АÚ (ВÙС)=(АÚВ) Ù(АÚС)
	AÚИ=И
	AÙЛ=Л
	AÙИ=A
	AÚЛ=A
	AÚ =И	закон исключенного третьего
	AÙ =Л
		законы де Моргана
	=И
	=Л

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

,

,

.

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

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

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

.

Рис. 2.1.1

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

.

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