Алгебра высказываний

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

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

Примеры. 1. Волга впадает в Каспийское море.

2. Два больше трёх.

3. Я лгу.

Примеры 1, 2 являются высказываниями (1 – истинно, 2 – ложно). 3 – не высказывание (если предположить, что оно истинно, то в силу его смысла оно одновременно ложно и, наоборот, из ложности этого предложения вытекает его истинность).

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

Высказывания будем обозначать буквами A, B, C,..., а их значения, то есть истину или ложь, соответственно цифрами 1 или 0.

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

Примеры. 1. Светит солнце, и идёт дождь.

2. Шесть делится на два или шесть делится на три.

3. Если контакт замкнут, то лампа горит.

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

Пусть даны два произвольных высказывания А и В.

1. Выражение А ۸ В (читается: «А и В») означает высказывание, истинное только в том случае, когда А и В истинны. Такое высказывание называют конъюнкцией высказываний А и В. Символом ۸ обозначают операцию конъюнкции. Эта операция соответствует союзу «и» в обычной речи. Однако в повседневной речи не принято соединять союзом «и» два высказывания, далекие по содержанию. В алгебре же высказываний операция конъюнкции может быть применена к любым двум высказываниям. Так, например, для высказываний «пять больше трех» и «трава зеленая» их конъюнкция «пять больше трех и трава зеленая» является истинным высказыванием.

2. Выражение А ٧ В (читается: «А или В») означает высказывание, истинное, если хотя бы одно из высказываний А или В является истинным. Такое высказывание называют дизъюнкцией высказываний А и В. Символ ٧ обозначает операцию дизъюнкции. Эта операциясоответствует союзу или обычной речи, применяемому в неисключающем смысле.

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

3. Выражение А ® В (читается: «если А, то В» или «А влечет В») означает высказывание, которое ложно тогда и только тогда, когда А истинно, а В ложно. Такое высказывание называют импликацией высказываний А и В. Высказывание А называется условием или посылкой, высказывание В – заключением или следствием импликации. Символ ® обозначает операцию импликации. В обычной речи операции импликации соответствует связка если..., то. Отличие состоит в том, что связка предполагает смысловую зависимость соединяемых высказываний, а для операции ® смысловая связь несущественна. Так, например, высказывания «если 2*2 = 5, то трава синяя» и «если два больше трех, то восемь делится на четыре» являются истинными, так как у первого из них ложная посылка, а у второго – истинное следствие. Импликация «если 2*2 = 4, то 5<2» ложна, поскольку ее условие истинно, а заключение ложно.

4. Выражение А ~ В (читается: «А эквивалентно В», «для того, чтобы А, необходимо и достаточно, чтобы В», «А тогда и только тогда, когда В», «А равносильно В») означает высказывание, которое истинно тогда и только тогда А и В оба истинны или оба ложны. Такое высказывание называют эквивалентностью высказываний А и В. Символ ~ означает операцию эквивалентности. В обычной речи этой операции соответствует связка тогда и только тогда, когда. Примером эквивалентности может служить высказывание «Треугольник АВС равнобедренный тогда и только тогда, когда угол при вершине В равен углу при вершине С».

5. Выражение`А (читается: «не А») означает высказывание, которое истинно, когда А ложно и ложно, когда А истинно. Такое высказывание называют отрицанием высказывания А. Символ` над буквой обозначает операцию отрицания. В обычной речи этой операции соответствует частица не. Например, для истинного высказывания «восемь делится на четыре» отрицанием является ложное высказывание «неверно, что восемь делится на четыре» или «восемь не делится на четыре».

Если А, В, С – произвольные высказывания, которые рассматриваются как величины, принимающие одно из двух значений 1 или 0, то, применяя к ним операции конъюнкции, дизъюнкции, импликации, эквивалентности и отрицания, можно получить новые сложные высказывания, например:

((А ٧ В) ٨`С) ® A ® B. (3)

В обычной речи не всегда удается однозначно определить истинность или ложность сложного высказывания по истинности или ложности его составных частей. В алгебре высказываний значение сложного высказывания полностью определяется значениями его составляющих. Предположим, что А – ложное высказывание, В – истинное, С – ложное. Тогда высказывание (3) является ложным в силу определения логических операций.

Наряду с высказываниями, принимающими определенные и постоянные значения 1, 0 и называемыми определенными высказываниями, в алгебре высказываний рассматривают переменные высказывания, которые не имеют определённого значения. Если X, Y, Z – переменные высказывания, то, применяя к ним операции конъюнкции, дизъюнкции, импликации, эквивалентности и отрицания, можно получить формулы алгебры высказываний. При задании значений переменных высказываний формула принимает определенное значение. Таким образом, каждая формула определяет некоторую функцию, переменными которой являются переменные высказывания. Переменные и функции принимают только два значения: истина или ложь, поэтому функции можно описать конечной таблицей, которую называют истинностной таблицей или таблицей истинности данной формулы.

Приведём истинностную таблицу формул X ٨ Y, X ٧ Y, X ® Y,

X ~ Y,`X (табл.3.1).

Таблица 3.1 – Истинностная таблица для операций над высказываниями

X	Y	X ٨ Y	X ٧ Y	X ® Y	X ~ Y	`X

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

((X ٧ Y) ٨`Z) ® (X ® Y) (табл. 3.2).

Запись формул можно упростить, опуская некоторые скобки и считая, что если их нет, то выполнять операции нужно в следующем порядке:

1) отрицание;

2) конъюнкция;

3) дизъюнкция;

4) импликация;

5) эквивалентность.

Например, формулу X ٨ Y ٧ Z следует понимать как (X ٨ Y) ٧ Z.

Таблица 3.2 – Истинностная таблица для равносильных формул

X	Y	Z	`Y ٧ Z	((X ٧ Y) ٨`Z) ® (X ® Y)

Если все значения формулы в истинностной таблице равны 1, то формула называется тождественно истинной или тавтологией. Тавтологии называют также законами логики. В обычном языке рассуждение имеет импликативную форму «если то-то и то-то, то то-то и то-то». При этом заботятся не об истинности или ложности посылок и заключений, а о правильности рассуждений. Рассуждения должны быть правильными, то есть соответствующие им импликации должны быть тождественно истинными. С этой точки зрения задачей логики можно считать исследование тавтологий. Тавтологичность формулы можно всегда обнаружить с помощью таблиц истинности.