5 Основы математической логики

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

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

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

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

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

3. Я лгу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сделаем некоторые замечания.

Импликация. Высказывания типа (если то ) или ( влечет ) носят объясняющий характер. Оно разъясняет нам, почему имеет место событие - потому, что имело место событие . Это свойство ценно для логики высказываний. Объясняющий характер импликации тесно связан с причинно-следственным отношением, при котором выступает в роли причины, а - следствия.

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

,

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

.

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

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

. (5.1)

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

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

Рассмотрим истинностную таблицу формул , ,,,.

Таблица 12

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

Х	Y
0 0 1 1	0 1 0 1	0 0 0 1	0 1 1 1	1 1 0 1	1 0 0 1	1 1 0 0

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

, и (см. табл.)

Таблица 13

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

0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	1 1 0 1 1 1 0 1	1 1 1 1 1 1 0 1

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

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

1. отрицание,

2. конъюнкция,

3. дизъюнкция,

4. импликация,

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

Например, формулу следует понимать как .