Исчисление высказываний

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

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

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

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

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

Сформулируем теперь совокупность синтаксических правил для исчисления высказываний.

1. Всякое элементарное высказывание является правильной совокупностью (будем говорить далее правильной формулой).

2. Если ? и ? являются правильными формулами, то правильными формулами являются также

?, (?&?), (?

?) и (?

?).

3. Других правильных формул в исчислении высказываний нет.

Между знаками логических связок

, &,

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

Там Анна пела с самого утра

И что-то шила или вышивала.

И песня, долетая со двора,

Ему невольно сердце волновала.

В этом четверостишии можно выделить четыре элементарных высказывания: a – «Там Анна пела с самого утра», b – «Что-то (Анна) шила», с – «Что-то (Анна) вышивала», d – «Песня, долетая со двора, ему невольно сердце волновала». В скобках мы ввели субъект, отсутствующий во второй строке приведенного отрывка. Общая логическая структура всего четверостишия может быть описана следующим образом: (а И (b ИЛИ c) И d). Большими буквами мы выделили союзы, которые в явной форме присутствуют в тексте Д. Самойлова. Можно ли от этой записи перейти к логическим связкам?

Вспомним, что такое конъюнкция и дизъюнкция. Во второй главе, определяя эти связки, мы говорили, что ?&? является истинным, если истинны оба утверждения ? и ?, а ?

? является истинным, если истинно хотя бы одно из утверждений ? или ?. Такое определение связок позволяет перейти от структуры, в которой используются союзы И и ИЛИ, к записи ((a&(b

c))&d), которая согласно синтаксическим правилам исчисления высказываний является правильной формулой этого исчисления. Правда, внимательные читатели могут усмотреть в этом переходе некоторую некорректность. Дело в том, что выражение ?

? является истинным и тогда, когда одновременно ? и ? истинны. Но подобный случай в нашем примере невозможен. Анна либо шила, либо вышивала. Одновременно делать то и другое она не могла. Другими словами, одновременная истинность ? и ? должна была бы давать сигнал о ложности такого утверждения, а дизъюнкция утверждает, что оно истинно. Эту ситуацию можно исправить, введя связку, называемую разделительной дизъюнкцией. Но мы этого делать не будем, так как такая связка есть комбинация более простых связок, которые мы уже ввели: (

?&?)

(?&

?).

Проверим, достигаем ли мы нужной цели с помощью данной комбинации. Если ? и ? ложны, то ложны правильные формулы (

?&?) и (?&

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

b&c)

(b&

c)))&d).

Рассмотрим еще одну цитату из того же стихотворения: «…Если трон находится в стране в руках деспо?та, тогда дворянства первая забота сменить основы власти и закон». Введем два элементарных высказывания: g – «Трон находится в стране в руках деспо?та» и h – «Дворянства первая забота сменить основы власти и закон». Тогда логическая структура всего высказывания может быть представлена в виде (ЕСЛИ g ТОГДА h). Для перехода к правильной формуле исчисления высказываний воспользуемся импликацией. Раньше она не встречалась. По определению выражение ?

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

Исследуем запись (g

h). Если g истинно, то h должно быть истинно, если фраза, которая вложена Д. Самойловым в уста Пестеля, является истинной. Это хорошо, но что будет в случае, когда утверждение g ложно? Для импликации это означает, что как при истинности h, так и при его ложности вся фраза в целом остается истинной. Другими словами, если неверно, что «Трон находится в стране в руках деспо?та», то дворянство может менять основы власти и закона, а может этого и не делать. Всё равно сложное высказывание будет сохранять свою истинность. Если же мы потребуем, чтобы при ложности g всегда было бы ложным и все высказывание целиком, сохраняя остальные свойства импликации, то мы опять вернемся к конъюнкции.

Наверное, самым разумным с точки зрения здравого смысла было бы вообще отказаться от определения истинности или ложности выражения (ЕСЛИ ? ТОГДА ?), когда ? является ложным. Ибо для выводов в этом случае нет никакой информации. Во второй главе мы использовали знак выводимости

. Вот с его-то помощью и можно формализовать случай, когда в записи g

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

И еще одно замечание, касающееся импликации. Эта связка, как и разделительная дизъюнкция, может быть сведена к комбинации других связок, имеющихся в исчислении. Читатели легко могут убедиться в справедливости замены ?

? на

?. Однако по ряду причин в исчислении высказываний в его классической форме импликация сохраняется как самостоятельная связка[5].

Не нужно думать, что переход от фраз на естественном языке к соответствующим им правильным формулам исчисления высказываний столь прост. На этом пути стоит немало трудностей, И прежде всего потому, что частицы и союзы языка типа НЕ, И, ИЛИ, ТО, ЕСЛИ и т.п. не являются однозначными свидетельствами наличия похожих на них связок. Цитата из стихотворения «Смерть поэта» Д. Самойлова иллюстрирует это положение:

И не ведал я, было ли это

Отпеванием времени года,

Воспеваньем страны и народа

Или просто кончиной поэта.

Встречающиеся здесь И и ИЛИ не являются прямыми аналогами связок исчисления высказываний.

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

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

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

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

?)) вместо ? подставить любую формулу, например (?&?), то формула ((?&?)

((?&?)

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

Второе правило называется модус поненс (лат. modus ponens) или правило заключения и выглядит следующим образом: если ? и (?

?) являются истинными формулами, то формула ? также истинна. Если ? является истинной, то истинность (?

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

Мы полностью описали исчисление высказываний. Заметим еще раз, что оно устроено так, что в результате выводов из аксиом получаются лишь тождественно истинные формулы. Можно показать, что система логических аксиом может быть выбрана таким образом, что для любой тождественно истинной формулы всегда найдется цепочка выводов (логических рассуждений), с помощью которой она будет выведена из системы аксиом путем применения правил подстановки и заключения. Другими словами, может быть построена полная система аксиом, из которой будут выводиться все тождественно истинные формулы и только они. Как показали исследования логиков, таких полных систем аксиом существует много. Система из четырех аксиом, которую мы только что рассмотрели является полной. Ее предложил известный немецкий математик и логик Д. Гильберт.

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

Пусть, например, надо узнать, выводима ли в исчислении высказываний формула ((

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

? ложно. Но тогда истинна и вся формула, ибо импликация истинна, когда истинны ее левая и правая части. Если же ? ложно, то первая скобка является ложной, так как левая часть импликации (

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

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

Проиллюстрируем эту процедуру еще на одном примере. Проверим, является ли выводимой формула ((?

((

?)&?)). В этой формуле (будем обозначать ее ?) имеется три высказывания, что приводит к необходимости рассмотрения истинного значения ? на 2³=8 комбинациях. Эти комбинации и соответствующие шаги по определению истинностного значения ? на них даны в табл. 3, в которой И и Л означают соответственно значения «истина» и «ложь».

Таблица 3

Появление в пятой строке в столбце ? значения Л свидетельствует о невыводимости исследуемой формулы. На этом шаге процесс вывода можно прекратить. Остальные строки в таблице приведены лишь для полноты картины.