Математические и логические основы информатики

Математические  и логические основы информатики

Элементы логики высказываний

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

Высказывания, подобные приведенным выше, называют простыми высказываниями. Они не могут быть «разложены» на более элементарные высказывания, относительно которых сохранилась бы объективная возможность оценить их истинность.

Из одних высказываний могут составляться (строиться) другие, более сложные высказывания. Такие  высказывания мы будем называть составными, или сложными высказываниями.

В русском языке (и не только в русском) составные  высказывания строятся из простых с  помощью союзов (и, или), частицы (не) и словосочетаний (если…,то...;…тогда и только тогда, когда…; …если, и  только если…;…необходимо и достаточно для… и т.д.)

Логические  операции над высказываниями

Условимся обозначать простые высказывания большими буквами  начала латинского алфавита: A, B, C (возможно с индексами: A1, A2, A3 и так далее), а значения истинности высказываний - буквами И (истина) и Л (ложь)), которые называют логическими константами.

Определим операции над высказываниями, которые будут  соответствовать союзам (и, или), частице  не, словосочетаниям (если …, то …; …тогда и только тогда, когда ….; …если, и только если …; …необходимо и  достаточно для… и т.д.) русского языка. Часто союзы, частицу не, указанные словосочетания называют связками. Соответствующие им операции называют логическими операциями, или логическими связками.

Союзу и соответствует  операция конъюнкция, обозначаемая нами с помощью символа & и задаваемая таблицей:

A	B	A&B
Л	Л	Л
Л	И	Л
И	Л	Л
И	И	И

Обоснованием такого способа определения (задания) операции конъюнкции является то, что согласно интуитивному пониманию союза и, составное высказывание типа «A и B»  истинно тогда и только тогда, когда истинны оба составляющих его высказывания, на что и указывает  последняя строка таблицы. В остальных  случаях конъюнкция двух высказываний ложна. Операция конъюнкции обозначается также с помощью символов  Ù и × (точка). Иногда знак конъюнкции между высказывания опускают, подобно тому, как в обычной алгебре часто опускают знак операции умножения.

Союзу или соответствует  операция дизъюнкция, обозначаемая нами с помощью символа Ú и задаваемая таблицей:

A	B	AÚB
Л	Л	Л
Л	И	И
И	Л	И
И	И	И

Обоснованием такого способа определения (задания) операции дизъюнкции является то, что согласно интуитивному пониманию союза или, составное высказывание типа «A или B» ложно тогда и только тогда, когда ложны оба составляющие его высказывания, на что и указывает  первая строка таблицы. В остальных  случаях дизъюнкция двух высказываний истинна.

Приведенное определение  операции дизъюнкции соответствует  употреблению союза или в русском  языке в так называемом соединительном смысле. Но часто этот союз употребляется  в разделительном смысле, то есть понимается как «либо A, либо B, но не то и другое вместе». Такому пониманию союза  или отвечает следующая таблица, определяющая операцию строгой дизъюнкции, обозначаемой с помощью символа Å:

A	B	AÅB
Л	Л	Л
Л	И	И
И	Л	И
И	И	Л

Частице не соответствует  операция отрицания, обозначаемая символом и задаваемая таблицей:

A	A
Л	И
И	Л

То есть, высказывание A истинно, если высказывание A ложно, и  наоборот, ложно, если A истинно.

Словосочетанию  «если …, то …» соответствует операция, называемая материальной импликацией и обозначаемая символом É. Материальная импликация задается следующей таблицей:

A	B	AÉB
Л	Л	И
Л	И	И
И	Л	Л
И	И	И

A называется антецедентом (или условием), B – консеквентом (или следствием) материальной импликации.

Определение материальной импликации (мы будем называть ее просто импликацией) весьма условно можно  считать формализацией словосочетания «если …, то …». Дело в том, что  словосочетание «если …, то …» выражает в языке не только логическую, но и причинно-следственную связь, которую  материальная импликация выразить не может. И, тем не менее, это определение  в значительной степени соответствует  интуитивному пониманию словосочетания «если …, то …» в смысле логического  следования. По крайней мере, высказывание, являющееся импликацией двух высказываний, ложно в том и только том  случае, если мы из истины пытаемся сделать (или, как говорят, имплицировать, вывести) ложное заключение (третья строка таблицы).

Словосочетанию  «…тогда и только тогда, когда  …» (синонимы: «… если и только если …», «… эквивалентно…», «… необходимо и достаточно для …») соответствует логическая операция, называемая эквиваленцией и обозначаемая символом ~. Эквиваленция задается следующей таблицей:

A	B	A~B
Л	Л	И
Л	И	Л
И	Л	Л
И	И	И

То есть, эквиваленция двух высказываний истинна тогда и только тогда, когда высказывания либо оба ложны, либо оба истинны.

Примером эквиваленции двух высказываний является высказывание «Четырехугольник является квадратом тогда и только тогда, когда все его стороны и углы равны между собой».

 

Свойства логических операций

Для обозначения  логической равносильности двух высказываний будем использовать символ º. Приведем здесь лишь свойства основных логических операций: конъюнкции, дизъюнкции и  отрицания.

Свойства коммутативности

коммутативность конъюнкции: A&B º B&A,

коммутативность дизъюнкции: AÚB º BÚA.

Свойства ассоциативности

ассоциативность конъюнкции: A&(B&C) º (A&B)&C,

ассоциативность дизъюнкции: AÚ(BÚC) º (AÚB)ÚC.

Свойства дистрибутивности

дистрибутивность  конъюнкции относительно дизъюнкции:

A&(BÚC) º (A&B) Ú(A&C),

дистрибутивность  дизъюнкции относительно конъюнкции:

AÚ(B&C) º (AÚB)& (AÚC).

Свойства логических констант

свойства константы И: A&И º A, AÚИ º A;

свойства константы  Л: A&Л º Л, AÚЛ º A.

Законы Де Моргана: (A&B) º AÚB, (AÚB) º A&ØB.

Закон исключенного третьего

(tertium non datur - третьего не дано): AÚA º И.

Закон противоречия: A&A º Л.

Закон снятия двойного отрицания: A º A.

Законы идемпотентности

идемпотентность конъюнкции: A&AºA,

идемпотентность дизъюнкции: AÚAºA.

Законы поглощения A&(AÚB)ºA, AÚ(A&B)ºA.

Используя теперь приведенные свойства и законы, можно  осуществлять эквивалентные (тождественные) преобразования формул логики высказываний, подобно тому, как мы преобразовывали  формулы теории множеств. Но прежде уточним некоторые понятия и  определения.