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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

Таблица 1.1

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

Таблица 1.2

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

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