И.А. Пушкарев логика

31

Определение 3.2. (1) Множество Р булевых формул называется

совместным, если существует набор значений переменных, входящих в них,

при котором все формулы, входящие в Р, истинны.

(2) В противном случае множество Р называется несовместным.

Это – семантическое определение противоречивости(в формулы

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

противоречить в этом смысле тем, которые случайно оказались истинными;

несовместным. Кроме того, несовместность множества формул можно записать коротко и элегантно: P > O , поскольку О – одна из формул, которые никогда не бывают истинными (то есть, если все формулы семействаР по какому-то недосмотру показались одновременно истинными, то и формулаО окажется истинной, а это невозможно).

тавтологией тогда и только тогда, когда её отрицание не является выполнимой формулой.

(4) Множество формул Р называется противоречивым, если существует формула q, такая, что P f q и P f Øq . Это – синтаксическое определение противоречивости. Как уже отмечалось, из противоречивого множества формул можно в три строчки вывести всё что угодно. Например, формулу О:

Øq ® (q ® O) (аксиома (А9));

q ® O (МР);

О (МР).

утверждения (тривиально используя аксиому (А12)). Поэтому для констатации

противоречивости множества можно использовать запись P f O . Оказывается,

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

Теорема 3.3. P > O Û P f O .

Доказательство непротиворечивости совместного множества совсем

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

Доказательство обратного утверждения существенно сложнее. Пусть Р –

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

соответствующее значение переменной очевидно. Если переменная x такова,

что P f x , то из предыдущего соображения ясно, что эта переменная в хорошем наборе должна быть истинна. Если же P f Øx , то эта переменная должна быть ложна. Осталось:

а) как-то определить значения остальных переменных;

б) после этого не забыть убедиться, что полученный набор действительно

Пункт а исполняется очень радикально J. За счёт увеличения множества

Р удаётся добиться того, чтобы вообще любая формула q обладала свойством:

либо P f q , либо P f Øq (хотя нам-то это свойство, повторимся, нужно только для формул, состоящих из одной-единственной переменнойJ). При этом

33

Определение 3.3. Множество формул называется полным, если для

или P È {Øq} непротиворечиво.

Пусть это не так: оба эти множества противоречивы. Тогда, согласно пункту б доказательства леммы 3.2., из противоречивости множества P È {q}

следует, что P f Øq , а из противоречивости P È {Øq} следует, что P f Ø(Øq),

то есть множество Р оказывается противоречивым (а это не так).

Соответственно, можно выбрать из двух формул ту, добавление которой

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

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

Определение 3.4. Частично-упорядоченное множество (T ,£) называется индуктивным, если в нём любое линейно-упорядоченное подмножество(цепь)

имеет верхнюю грань.

Конкретно, в нашем случае Т есть множество непротиворечивых подмножеств множества L всех формул. Частичный порядок в данном случае(тоже – стандартно) есть просто отношение Í «являться подмножеством», а в качестве

наименьший среди номеров множествUi , в которые эта посылка входит.

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

найдётся максимальный отмеченный элементI, обозначим его k. Поскольку

– цепь, то все использованные посылки суть элементыU k . Отсюда

следует, что U k f О , то есть множество U k противоречиво, а это не так.

35

Оба множества U ¢ È {s} и U ¢ È {Øs} больше, чем само U ¢ , поэтому они не входят в Т, то есть – противоречивы. Но это невозможно, как было показано в начале обсуждения.

QED

Итак, показано, что любое непротиворечивое множество формулР

содержится в некотором непротиворечивом полном множествеР¢, то есть в

таком, что для любой формулыq либо самаq, либо Øq содержится вР. В

частности, этим свойством обладает любая формулаx, состоящая из одной

переменной. Тем самым набор значений переменныхn , который может

оказаться «хорошим», определён (необязательно однозначно: при добавлении

Лемма 3.5. Для любой формулы q равносильны условия:

(1)q(n )=1;

(2)P f q (или, равносильно, q Î P¢ ).

Доказательство снова проводится индукцией по множеству формул с

36

В частности доказано, что "q Î P q(n )=1, то есть набор ν действительно

«хороший».

Ø(Øq)f q .

QED

В качестве бонуса к этому доказательству(недоступного исходя из

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

Теорема 3.6. (Теорема о компактности для исчисления высказываний)

Пусть P – множество формул, всякое конечное подмножество которого совместно. Тогда и само множество Р совместно.

Доказательство. Пусть Р несовместно. Тогда Р противоречиво. Тогда из множества Р можно вывести формулуО. Обозначим символом P0 множество всех посылок, входящих в этот вывод. Тогда P0 f О , т.е. P0 противоречиво,

следовательно – несовместно. Противоречие.

QED

Замечание. Основная идея доказательства состоит в , томчто для выводимости и непротиворечивости теорема компактности тривиальна. И если уж непротиворечивость равносильна совместности, то…

37

3. Общая картина

Что означает теорема о полноте исчисления высказываний? На данный

момент рассмотрены две теории: семантическая – состоящая из всевозможных тавтологий, и синтаксическая – состоящая из теорем исчисления высказываний.

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

синтаксического «близнеца», говорят, что эта теория аксиоматизируема. Итак:

пропозициональная теория аксиоматизируема.

Не будем забывать также, что в действительности была доказана более

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

однозначно и за конечное время, поэтому можно сказать, что мы знаем в этой теории всё. Лучшего, кажется, и желать не стоит J. В действительности (ложка дёгтя в бочке мёда) упомянутое «конечное время» может оказаться слишком велико, чтобы практически пользоваться разрешающим алгоритмом.

Во-вторых, она может оказаться аксиоматизируемой. В этом случае,

рассматриваемую формулу можно попробовать доказать(без гарантии успеха),

38

вооружившись знанием того, что искомое доказательство существует. Эта

поэтому, например, элементарная геометрия (которая, вообще-то разрешима)

практически всегда рассматривается как аксиоматизируемая(точнее –

аксиоматизированная!) теория.

Ну и остаётся вопрос: а бывает ли так, чтобы теория была недоступна обработке обоими этими инструментами? Это – тот самый, вопрос который

(неожиданно, разочаровывающее и одновременно – стимулирующее к новым интеллектуальным подвигам J) решается отрицательно теоремой Гёделя о неполноте арифметики.

40

4. Аксиомы и правила вывода исчисления секвенций

Определение 4.1. (1) Секвенцией называется выражение вида P a Q , где

Р и Q – два множества формул.

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

– входящие в Q. Такой набор будем называтьконтрпримером, поэтому секвенция – ещё один странный аналог импликации: контрпример к секвенции есть одновременно контрпример к импликацииLр ®Vq , где слева стоит конъюнкция всех формул, входящих в Р, а справа – дизъюнкция всех формул,

входящих в Q.

Соответственно, задача поиска контрпримеров к формулеq – секвенция

a q .

(2) Правилами вывода исчисления секвенций называются следующие

Замечание. Предположим, что мы ищем контрпример к секвенции вида

аналогично.