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

41

(3) Объяснение. Аксиомой исчисления секвенций естественно счесть любую секвенцию, которой не соответствует никаких контрпримеров. Таковыми,

например, являются секвенции, для которых P Ç Q ¹ Æ .

Итак,

аксиомой

исчисления

секвенций

называется

любая

секвенция

P a Q , такая, что P Ç Q ¹ Æ .

(4) В результате обработки формулы исчисление секвенций формулы

получается своеобразное «дерево вывода».

p a p, q

; p a p

a (p ® q), p

Примеры. (1)

(p ® q)® p a p

. Обе секвенции p a p и p a p, q –

a ((p ® q)® p)® p

аксиомы, поэтому

формула ((p ® q)® p)® p

есть тавтология(ибо к

ней не

существует

контрпримеров). В

этом

случае

говорят, что

рассмотренная

формула есть теорема исчисления секвенций.

a p, q;

q a q

(2)

(p ® q)a q

. Секвенция

a p, q

имеет контрпример: р

и q –

a (p ® q)® q

ложны. Следовательно, он будет и контрпримером к формуле (p ® q)® q . Это

так и есть J.
Следующая теорема очевидна.
Теорема 4.1. (Корректность и полнота исчисления секвенций)
Секвенция	выводима тогда	и только , тогдакогда она	не имеет
контрпримера.
Замечание. Из этой теоремы можно получить ещё одно доказательство
теоремы о	полноте исчисления	высказываний. Это немного	хлопотно,

поскольку секвенции – это всё-таки не формулы и доказательство в исчислении секвенций формально не имеет ничего общего с доказательством в исчислении высказываний. Тем не менее, родство двух исчислений несомненно существует,

и доказательства в них, в содержательном смысле, всё-таки примерно одно и то

же J.

42

§5. Интуиционистская пропозициональная логика 1. Обсуждение

Одна из аксиом пропозициональной логики(да, собственно, и всей

классической математики), конкретно – аксиома (А11), стала однажды в истории предметом нешуточного обсуждения, чтобы не сказать– конфликта.

Один из крупнейших математиковXX века Л.Э.Я. Брауэр увидел в её использовании причину появления странных математических результатов,

подобных теореме Банаха-Тарского(эти два математика однажды объяснили миру, что шар можно разрезать на конечное множество частей, из которых

можно сложить два таких же ).шараБрауэр					на основании кажущейся
абсурдности подобных результатов(в действительности						теорема Банаха-
Тарского	отнюдь не абсурдна: части, на которые делится шар, не имеют
никакого	объёма, поэтому	объём	и	не	обязан	сохраняться	при

перекладывании в другом порядке) счёл, что математические рассуждения

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

утверждение может быль либо истинным, либо ложным, подтверждается, в

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

меньшей мере один результат(недоказуемость и неопровержимость

континуум-гипотезы: «существует несчётное подмножество R, неравномощное

R»), который можно (при желании) счесть подтверждением противоположной точки зрения. Поэтому – вполне допустима такой взгляд на вещи: существуют утверждения, не являющиеся ни истинными, ни ложными. «Неизвестно» J.

Может быть, континуум-гипотеза – не истинная и не ложная, «никакая»!

Итак, возможно, что аксиома (А11) «в действительности места не имеет»,

и от её использования следует воздерживаться. С другой стороны, Брауэр

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

43

Естественно предположить, что от этого они и умерли. Сахар – белая смерть

двадцатого века!»

То, что остаётся от классической математической логики в результате

такого «воздержания от употребления

сахара», называется интуиционистской

(или конструктивистской) логикой. Почему вообще что-то остаётся? Потому

что даже

в

рассмотренных

примерах

упомянутая

аксиома

использовалась

далеко не всегда.

Противоположный

вопрос

тоже

уместен: а

почему, собственно,

исключение аксиомы (А11), хоть что-то меняет? Может быть эта аксиома

выводится из остальных?

Теорема

5.1.

Формула a Ú Øa

невыводима

в

интуиционистской

пропозициональной логике.

Доказательство.

Изменим

смысл всех символов(научно говоря,

построим

другую

модель аксиоматики).

Предположим,

что

истинность

высказывания

бывает не двух, а

трёх типов: «истинно»

(1), «ложно» (0) и

«неизвестно»

(? или 1

2

).

Далее,

истинность сложных

высказываний можно

задать таблицей (любой, лишь бы остальные аксиомы выдержали предлагаемые

изменения).

x

Øx

0

1

?

0

1

0

		44
x	y	x Ù y	x Ú y	x ® y
0	0	0	0	1
0	?	0	?	1
0	1	0	1	1
?	0	0	?	0
?	?	?	?	1
?	1	?	1	1
1	0	0	1	0
1	?	?	1	?
1	1	1	1	1

Почему именно так? Некоторые правила	хорошо	понятны: (0 ® x)=1,
(1 ® x)= x , (x Ù y)= min{x, y}, (x Ú y)= max{x, y}	(считая,	что 0<?<1), Ø0 =1,

Ø1 = 0 . По поводу остальных правил можно сказать: делать можно как угодно,

лишь бы результат получился нужныйJ. Отметим, однако, что ожидаемое

Ø? = ? неприемлемо: аксиома (А9) Øa ® (a ® b) при a = ? и b = 0 становится ложной.

Формулу назовём 3-тавтологией, если на любом наборе аргументов она

принимает значение 1. Теперь нужно проверить две вещи. Во-первых – то, что

все аксиомы,		кроме (А11) являются 3-тавтологиями.						Это длинная		рутинная
процедура,	и	она	оставляется		читателю		в	качестве		самостоятельного,
обязательного		для	исполнения		упражнения. Во-вторых –				состоятельность
правила МР.	Она очевидна: если a =1 и (a ® b)=1,						то обязательно b =1, так
как (1 ® x)= x .
Следовательно,			любая	выводимая		формула		является3-тавтологией.
Осталось	заметить,		что	аксиома (А11)		3-тавтологией			не	является:

?Ú (Ø?)= ?Ú 0 = ? .

QED

				45
Замечание.			Формула (Øa)Ú Ø(Øa),		которая		тоже	невыводима		в
интуиционистской			логике (почему?), тем		не	менее, является 3-тавтологией
(проверьте). Можно сказать, что нам просто повезло с законом исключённого
третьего:		его невыводимость доказалась			так	легкоJ.	В общем		же случае
потребуется какой-то более мощный инструмент.
2.	Модели Крипке
Определение 5.1. (1) Пусть (W , £) – частично-упорядоченное множество,
называемое множеством миров. Каждый мир wÎW есть разбиение множества
V всех пропозициональных переменных на два подмножества: истинных и
ложных (в		этом	мире) переменных. Истинность переменной x					(и	формулы
тоже) в	мире w		символически	записывается		формулойw µ x .		Этот объект
называется шкалой Крипке, если выполнено условие:
–	"u, v ÎW ,		"x ÎV u £ v ,	u µ x Þ v µ x – истинность				наследуется
вверх по шкале.
(2) Пусть (W , £) – шкала				Крипке, p –		пропозициональная			формула.
Истинность формулы р в мире w этой шкалы определяется индуктивно:
а) формула О ложна, а I – истинна во всех мирах;
б)	формула x, где x ÎV , истинна в мире w тогда						и только тогда, когда
w µ x ;
в) w µ (p Ù q) Û w µ p и w µ q ;
г)	w µ (p Ú q) Û w µ p или w µ q ;
д)	w µ (p ® q) Û "u ³ w если u µ p , то u µ q ;
е)	w µ Ø p Û ни в одном мире u ³ w формула р не является истинной.
(3) Множество всех миров шкалы, на которых истинна формула,
называется областью истинности этой формулы.

46

Лемма 5.2. Область истинности любой формулы– двойственный идеал частично-упорядоченного множества (W , £), то есть "u ÎW "p Î L если u µ p , v ³ u , то v µ p .

Доказательство. Индукция по построению формул. База содержится в определении. Переход для импликации и отрицания– тоже. Дизъюнкции и конъюнкции соответствуют объединение и пересечение идеалов, которые тоже,

очевидно, являются идеалами.

QED

Шкалы Крипке имеют простой наглядный«философский» смысл.

Множество W можно понимать как множество всевозможных логически

непротиворечивых ступеней развития некой цивилизации. Неравенство					u £ v
означает, что	ступень v может		получиться из ступениu в процессе развития
этой цивилизации. При этом уж если формула доказана, то она так и останется
истинной (то	есть –	цивилизация не совершает		ошибок). Но, наверное,	есть
какие-то обстоятельства, которые так и останутся от неё сокрыты…
Теорема	5.3.	(О	корректности	интуиционистского	исчисления

высказываний относительно шкал Крипке)

Формула, выводимая в интуиционистском исчислении высказываний,

истинна во всех мирах всех шкал Крипке.

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

всех мирах, а правило МР это свойство сохраняет. Второе очевидно следует из определения импликации, и миры и шкалы тут вообще ни при чём.

Проверим аксиому (А1). Если формула р истина в некотором мире, то во всех бòльших мирах истинна и формулаq ® p , а, следовательно – и формула

p ® (q ® p). Если же р ложна, то импликация истинна в любом случае.

Проверим		аксиому (А2).			Аналогично			предыдущему, достаточно
рассмотреть только те миры,				в которых		истинна		формула p ® (q ® r ). Итак,
пусть	u µ p ® (q ® r ).		Покажем,		что	в	этом	случаеv µ (p ® q)® (p ® r )
"v ³ u .	Это означает,		что	w µ p ® q			Þ w µ p ® r "w ³ v . В силу

47

произвольности v это то же самое, что v µ p ® q Þ v µ p ® r "v ³ u . При

этом снова достаточно рассмотреть только те миры, в которых v µ p ® q . Итак,

достаточно рассмотреть только те миры, в которых v µ p ® (q ® r ), среди них

– только те, в которых v µ p , и только те из них, в которых v µ p ® q . Из

первого условия следует, что во всех таких мирах v µ q ® r , из третьего – что в

них v µ q , следовательно, в них v µ r . Итак, из v µ p всегда следует v µ r ,

значит во всех рассматриваемых мирах v µ p ® r , что и требовалось доказать.

Остальные аксиомы разбираются аналогично.

		QED
Примеры. (1) Шкала Крипке, в одном из миров которой ложна формула
p Ú (Ø p) строится	легко. Возьмём два	мира, первый меньше второго. Пусть
формула p истинна	только во втором	мире. Тогда формула Ø p не истинна

нигде, а p Ú (Ø p) истинна только во втором мире. В действительности – это уже приведённое рассуждение: 0 – значение формулы, ложной в обоих мирах, 1

–истинной в обоих мирах, ? – истинной только во втором мире.

(2)Аналогичная шкала Крипке для формулы(Ø p)Ú Ø(Ø p) устроена

немного сложнее. Рассмотрим три мира: u, v, w, такие что u £ v , u £ w , а миры v

и w несравнимы. Далее, пусть формула р (и, следовательно, ØØ p , так как импликация p ® ØØ p выводима в интуиционистской логике) истинна только в мире v, а формула Ø p – только в мире w. В итоге получается, что в мире u

обе формулы Ø p и ØØ p ложны, следовательно – ложна и исходная формула.

3.	Полнота	интуиционистского		исчисления	высказываний
относительно шкал Крипке
Хорошо. С формулой (Ø p)Ú Ø(Ø p)			справились J. Но		с любой ли
формулой	можно	справиться подобным	образом? Существует		ли формула,

невыводимая в интуиционистском исчислении высказываний, истинная во всех

48

мирах всех шкал, невыводимость которой, соответственно, надо доказывать

как-то по-другому? Или шкалы Крипке являются окончательным ответом?

Теорема 5.4. (Полнота интуиционистского исчисления высказываний относительно шкал Крипке)

Для любой формулы, невыводимой в интуиционистском исчислении

высказываний, существует шкала Крипке, в некотором мире которой эта

формула ложна.
Доказательство	следует	начать	с	определения		предполагаемого
стандартного вида миров.
Определение 5.2. (1) Пусть Р и Q –				два	конечных	множества
пропозициональных	формул.	Пару (P, Q)		назовём совместной, если
существуют шкала Крипке и мир в ней, в котором все формулы из Р истинны, а
все формулы из Q ложны.
(2) Пару (P, Q)	назовём	противоречивой, если			в интуиционистском

исчислении высказываний выводима формула Lp ®Vq .

Замечания. (1) Понятно, что противоречивая пара совместной быть не может. Оказывается, что верно и обратное, причём это «обратное» есть переформулировка обсуждаемой теоремы.

(2)Немного похоже на секвенции, нет?

(3)Эти пары (при одном дополнительном предположении) и будут играть роль миров в конструируемых шкалах.

Аналогом начала доказательства леммы 3.4. для данного случая является следующее утверждение.

Лемма 5.5. Пусть пара (P, Q) не является противоречивой, r –

произвольная формула. Тогда хотя бы одна из пар(P È {r}, Q) или (P, Q È {r})

также не является противоречивой.

49

Доказательство. Введём обозначение (с небольшой коллизией) P = Lp ,

Q = Vq . Если	обе	пары	противоречивы, то в				интуиционистском исчислении
высказываний	выводимы			обе	импликации: (P Ù r )® Q			и	P ® (Q Ú r ).
Достаточно показать, что в этом случае выводима и импликацияP ® Q . Для
этого достаточно (по лемме о дедукции)						P f Q . Поскольку, по той же лемме о
дедукции, выводимость			P f (Q Ú r )		у	нас уже есть, остаётся			доказать, что
P f ((Q Ú r )® Q).		Для	доказательства			этого,	в свою	очередь, достаточно
установить, что		P f (Q ® Q)		и P f (r ® Q).			Первое	очевидно, второе –
равносильно выводимости (P Ù r )® Q .

QED

Замечание. Принята такая терминология: лемма 5.5. показывает, что в интуиционистской логике допустимо правило сечения, позволяющее «иссечь» формулу r из импликаций(P Ù r )® Q и P ® (Q Ú r ), после чего от них остаётся только P ® Q .

Теперь зафиксируем некоторое конечное множество формулF,

содержащее вместе с любой формулой и все её подформулы(научно говоря –

замкнутое относительно перехода к подформулам).

Определение 5.3. Пусть X , Y Í F . Пару (X , Y ) будем называть полной,

если она не является противоречивой и X È Y = F .

Следующее утверждение – точный аналог леммы 3.4. очевидно следует из леммы 5.5.

Лемма 5.6. Для любой непротиворечивой пары (P, Q) существует полная непротиворечивая пара (X , Y ), такая, что P Í X и Q Í Y (её естественно называть расширением исходной пары).

50

Мирами шкалы Крипке, которую мы будем строить, являются полные

непротиворечивые пары (X , Y ). При этом (X1, Y1 )£ (X 2 , Y2 ) тогда и только тогда, когда X1 Í X 2 . Интуитивный смысл этого понятен: предполагается, что в мире (X , Y ) формулы множества X истинны, а формулы множества Y ложны.

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

Лемма 5.7. В построенной шкале в мире (X , Y ) истинны все формулы из

X и ложны все формулы из Y.

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

осталось только провести восемь вариантов индукционного перехода(четыре

связки помноженные на две множества из пары).

Случай Ù X . Пусть формула s Ù t входит в X. Тогда формулы s и t не могут входить в Y (иначе пара противоречива), поэтому они тоже входят вX

(так как пара полна), и, по индукционному предположению, в мире (X , Y ) они обе истинны. Поэтому в этом мире истинна и формула s Ù t .

Случай ÙY . Пусть формула s Ù t входит в Y. Тогда по крайней мере одна из формул s или t не должна входить в X (непротиворечивость), то есть одна из

них должна входить в Y (полнота). Пусть, не умаляя общности, s ÎY . Тогда она

ложна в этом мире и вместе с ней ложна формула s Ù t .

Связка Ú рассматривается аналогично (упражнение).

Случай ®X . Пусть формула s ® t входит в X. Проверим, что она истинна в этом мире. Это означает, что в любом мире (X ¢, Y ¢), таком, что X Í X ¢, из

истинности s следует истинность t. Итак, пусть s истинна в некотором таком

мире. По индукционному предположениюs Î X ¢.			С		другой	стороны,
(s ® t )Î X Í X	¢	. Если бы в этом случае оказалось, что	t ÎY	¢		¢ ¢	)
					, то пара (X , Y

оказалась бы противоречивой, а это не так. Поэтому t Î X ¢ и по индукционному предположению она истинна в мире (X ¢, Y ¢).