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

Учение о высказываниях является первой из формальных логических теорий. Алгебра высказываний представляет самостоятельный интерес и имеет приложения в других отраслях науки и техники. Она применяется, например, при синтезе релейно-контактных и электронных схем.

Под высказыванием будем понимать различные суждения, предполагая при этом, что они удовлетворяют закону исключенного третьего и закону противоречия, т.е. высказывание - это такое утверждение (предложение), относительно которого можно говорить, что оно истинно или ложно, более того, оно обязательно является или истинным или ложным. Тогда высказывание можно рассматривать как величину, которая может принимать два значения: "истина" и "ложь".

Пример 1.1. Даны суждения: "собака-животное"; "Париж столица Италии", " "; "в каждом треугольнике биссектриса делит противоположную сторону на равные части".

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

венно третьему, а второе - четвертому.

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

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

Будем обозначать высказывания большими латинскими буквами , а их значения, т.е. истину и ложь, соответственно и . В обычной речи употребляются связки и между высказываниями: и, или и др. Эти связки позволяют, соединяя между собой различные высказывания, получать новые высказывания. Например, связка и. Пусть даны высказывания " больше " и высказывание " меньше "; из этих высказываний можно образовать новое " больше и меньше ". Высказывание " если целое, то дробное" получается связыванием двух высказываний связкой если - то. Наконец, можно получить из данного высказывания новое, отрицая его.

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

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

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

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

Третья операция: ; это высказывание ложно тогда и только тогда, когда истинно, а ложно. называется посылкой, - следствием, а высказывание сле дованием. В обычной речи эта операция соответствует связке если - то. Но в нашем определении это высказывание при ложном всегда истинно независимо от высказывания . Т.е. "из ложного следует все, что угодно".

Четвертая операция: - это высказывание, которое ложно, когда истинно, и истинно, когда ложно. Это высказывание называется отрицанием .

Пятая операция: есть высказывание истинное тогда и только тогда, когда и оба истинны или оба ложны, оно называется эквивалентностью.

При помощи перечисленных операций можно образовать новые сложные высказывания:

.

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

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

Пример 1.2. a) Пусть есть , - , - . Тогда сложное высказывание может быть записано в виде . Значение этого высказывания . Действительно, есть , также .

b) Пусть есть , - , - , - , - и - . Рассмотрим сложное высказывание , его можно переписать в виде: . Но есть , тогда есть . Рассмотрим правую часть конъюнкции , имеем: есть , тогда есть тоже и, наконец, есть . Коньюнкция двух истинных высказываний есть высказывание истинное, т.е есть , но отрицание истинного высказывания есть ложь и, следовательно ысказывание есть .

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

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

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

Таблица 1.1

Таблицы значений основных логических операций

Таблица 1.2

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

Рассмотрим теперь другую логическую систему - логику предикатов.