Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Московская финансово-юридическая академия

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

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

.pdf

Скачиваний:

Добавлен:

10.05.2015

Размер:

729.77 Кб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 1112 / 1612 13 14 15 16 > Следующая >>>

			111
Замечание.		Понятие	полной	теории	полезно	прокомментировать.
Полную	теорию	можно, например, получить, взяв			некоторую		конкретную
интерпретацию и		включив в теорию те и только те				замкнутые формулы,
которые истинны в этой интерпретации. Собственно, из теоремы о полноте
исчисления предикатов следует, что по-другому					полную	теорию получить
нельзя J. В понятии полноты крайне существенно, что рассматриваются
только замкнутые формулы, иначе для определения истинности требуется
обратиться к конкретным оценкам, и истинность начнёт зависеть от оценки.
Так же	важно	требование ограничиваться			формулами		рассматриваемой

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

Теорему 10.2 можно переформулировать следующим образом.

Теорема 11.1. (теорема адекватности, переформулировка)

Любая совместная	теория непротиворечива. Это можно	записать
формулой: T f O Þ T > O .
Доказательство. Пусть	Т – совместная теория. Допустим,	что она

противоречива, т.е. Т f O . Тогда существует вывод формулы0 из теории Т. В


этом выводе	используется лишь		конечное		число	формул Т,ихобозначим
множество	этих	посылокTk = {t1, ..., tk };		вообще		введём	обозначения
Ti = {t1, ..., ti }	"i Î[1, ..., k]. Согласно		лемме	о	дедукции, следующая		цепочка

состоит из равносильных утверждений, т.е. истинных, так как первое из них

истинно: Tk f O Û Tk -1 È tk	f O Û Tk -1 f (tk ® O) Û Tk -2 f (tk -1 ® (tk ® O))
Û … Û f t1 ® (t2 ® (...(tk	® O)...)). Формула из последней цепочки есть

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

общезначима.	Однако в	интерпретацииМ все	формулыt j	являются
истинными, а	формула О	– ложной, поэтому	в этой	интерпретации
рассматриваемая формула ложна. Полученное противоречие				доказывает
теорему.
				QED

112

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

11.1.

Теорема 11.2. (Теорема Гёделя о полноте исчисления предикатов;

сильная форма)

Любая непротиворечивая теория совместна. Это можно записать

формулой: T > O Þ T f O .

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

же, как доказательство теоремы 3.3 (второе доказательство теоремы о полноте

исчисления высказываний).
Лемма 11.3.		Пусть Т – непротиворечивая		теория.	Тогда существует
полная непротиворечивая теория U (T )Ê T .
Доказательство этой леммы буквально повторяет доказательство леммы
3.4 (выводы	в	исчислении	высказываний	переносятся		в	исчислен
предикатов).
						QED
Рассмотрим		непротиворечивую	теорию. Требуется		построить	для	неё

интерпретацию. В качестве носителя этой интерпретации предполагается

использовать	множество	замкнутых		термов(то	есть		не		содержащих
переменные, а только константы) рассматриваемой теории.
Очевидное препятствие на этом пути– возможная нехватка (вплоть до
отсутствия) замкнутых термов.
Определение 11.2. Теория Т называется экзистенциально									замкнутой,
если для любой формулы вида Ex p(x), выводимой из этой теории T f Ex p(x),
(или, не умаляя общности, принадлежащей ей Ex p(x)ÎT )								существует
замкнутый терм	t ÎT , такой что T f p(t		x) (соответственно,			p(t	x)ÎT ).

			113
Лемма 11.4. Пусть Т – непротиворечивая					теория		сигнатурыs .
Существует		расширение s ¢	сигнатуры s		новыми		константами		и
непротиворечивая экзистенциально полная теорияQ(T ) над							сигнатуройs ¢,
такая, что T Í Q(T ).
Доказательство. Первым			шагом	добавим		для	каждой	формулы
Ex p(x)ÎT «свою собственную» константу с и одновременно добавим в теорию
формулу	p(с	x). Заметим, что новых формул вида Ey q(y)				к рассматриваемой

теории	не	добавилось, поэтому	она	после	этой		операции	окажется

экзистенциально полной. Проблема в том, что она могла стать ещё и противоречивой.

Противоречивость – свойство синтаксическое. Любое появившееся после

описанной операции доказательство формулыО содержит лишь конечное число посылок вида p(с x). Поэтому если доказать, что добавление одной такой

посылки не может сделать теорию противоречивой, то (отсюда автоматически последует, что добавление конечного числа посылок не сделает теорию противоречивой) её не сделает противоречивой добавление какого угодно множества таких посылок.

Пусть

добавление

формулыp(с

x) сделало теорию

противоречивой.

Тогда, как

обычно, из

теории

выводима

формулаØ p(с

x),

доказуемо

эквивалентная

формуле p(с

x)® O .

Согласно

лемме

дедукции(как в

доказательстве

теоремы 11.1)

существует

конечное

семейство

формул

{t1 , ..., tk }Í T ,

такое, что f t1 ® (t2 ® (...(tk ® Ø p(с

x))...)). Константа с – свежая,

поэтому, по лемме о свежих

константахf t1 ® (t2 ® (...(tk

® Ø p(x))...)).

Этой

формуле

доказуемо

эквивалентна

формулаt Ù t

Ù ... Ù t

® Ø p(x).

Контрапозиция даёт формулу p(x)® Øt1 Ù t2 Ù ... Ù tk . Применяя ПБ2, получаем

формулу Exp(x)® Øt1 Ù t2 Ù ... Ù tk . Однако формула Exp(x)

выводима из Т, как

и формула t1 Ù t2 Ù ... Ù tk . Следовательно теория Т противоречива. Полученное

противоречие доказывает лемму.

			114
					QED
Далее	можно	рассмотреть	возрастающую	последовательность		теорий
T Í U (T )Í Q(U (T ))Í U (Q(U (T )))Í ...,			и, взяв объединение		входящих	в неё
теорий, получить, как в доказательстве леммы 9.6, доказательство следующего
утверждения.
Лемма 11.5. Пусть Т – непротиворечивая				теория	сигнатурыs .
Существует расширение s ¢ сигнатуры s новыми константами и одновременно
непротиворечивая, полная и экзистенциально				полная	теорияUQ(T )	над
сигнатурой s ¢, такая, что T Í UQ(T ).
					QED
Теперь	можно	приступать к	доказательству теоремы11.2. Носителем

требуемой интерпретации назовём множество замкнутых термов построенной сигнатуры. Константы интерпретируются само собой. Функциональный символ валентности m интерпретируется как функция на носителе, переводящая набор

замкнутых	термов t1, ..., tk в	терм f (t1, ..., tk ). Если s – m-местный символ
отношения,	то s(t1, ..., tk )=1	Û s(t1, ..., tk )ÎT . Тем самым интерпретация
задана.

Остаётся проверить, что она действительно является интерпретацией, то есть все формулы теории Т в этой интерпретации истинны. В действительности

мы докажем больше: что формула в этой интерпретации истинна тогда и только тогда, когда принадлежит теории. Доказательство этого факта проведём

индукцией по множеству формул.
Для логических связок рассуждение проводится						буквально	как в
доказательстве леммы 3.5. (и даже проще, поскольку к нашим услугам теперь
теорема	о	полноте	исчисления	высказываний	с	обычным	спосо
эксплуатации пропозициональных тавтологий).
Осталось		рассмотреть	только формулы видаAx p(x)		и	Ex p(x) при
условии, что для формулы р утверждение уже доказано.

115

Пусть Ex p(x)ÎT . Тогда существует константас, такая, что p(c x)ÎT .

Последняя формула проще исходной, поэтому эта формула истинна в рассматриваемой интерпретации. Поэтому на оценке, придающей переменной х значение с, формула p(x) истинна, поэтому истинна и формула Ex p(x).

Обратно, пусть формула Ex p(x)

истинна в нашей интерпретации. Тогда

(по

определению

истинности) существует

замкнутый

термt

нашей

интерпретации, такой, что p(t

x) – истинна. Следовательно,

p(t

x)ÎT . Осталось

вспомнить

аксиому p(t

x)® Ex p(x)

и правилом МР, и

вывести

формулу

Ex p(x) из теории Т.

Пусть

Ax p(x)ÎT .

Тогда, используя аксиому Ax p(x)® p(t

x) и правило

МР,

из теории Т можно

вывести формулу p(t

x),

которая

проще

исходной, и

поэтому – истинна в рассматриваемой интерпретации, причём для любого терма t. Отсюда по определению истинности следует истинность исходной формулы.

Наконец, пусть Ax p(x)ÏT . Тогда, в			силу полноты, Ø Ax p(x)ÎT ,	а эта
формула	доказуемо	эквивалентна	формулеEx Ø p(x), следовательно
Ex Ø p(x)ÎT . В силу экзистенциальной полноты существует константа с,				такая,
что Ø p(c	x)ÎT . Следовательно, в рассматриваемой интерпретации			истинна

формула Ø p(c x), и, значит, ложна формула p(c x). Поэтому формула Ax p(x)

ложна в рассматриваемой интерпретации.

QED

Стандартным усилением теоремы 11.2 является следующее утверждение.

Теорема 11.6. T > p Þ T f p .

Доказательство. Пусть T > p . Тогда T , Ø p > O . Следовательно по теореме 11.2 T , Ø p f O , откуда, по лемме о дедукции T f (Ø p ® O). Формула

Ø p ® O доказуемо эквивалентна формуле р.

QED

116

В частности, из теоремы 11.6 следует, что всякая общезначимая формула выводима в исчислении предикатов, что является точным аналогом теоремы

3.1.

Другим важным следствием теоремы 11.2 является аналог теоремы 3.6.

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

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

Доказательство. Существование модели равносил непротиворечивости. Но противоречивость есть просто выводимость формулы

О, а любой вывод содержит лишь конечное число посылок. Следовательно, у

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

QED

Гибридом теорем 11.6 и 11.7 является следующий (теперь – очевидный)

результат.

Теорема 11.8. Пусть T > p . Тогда существует конечное подмножество

T0 Í T , такое, что T0 > p .

Пусть, например, Т есть «наивная» теория групп с символами умножения

и равенства,	и некоторая формула р верна во всех бесконечных группах. Тогда
T È Q > p ,	где	Q	–	множество	формул	ти
Ck = Ex1...Exk (x1 ¹ x2 )Ù ... Ù (xk -1 ¹ xk ),				выражающих	свойство «в группе	не

менее k различных элементов». Согласно теореме компактности, для вывода р достаточно только конечного подмножества множестваQ, которое содержит формулу с максимальным номеромN. Следовательно, для всех достаточно больших групп (в которых не менее N элементов) формула р тоже верна.

117

§12. Работа с кванторами 1. Переименование переменных в общем случае

Мы видели, что формулы Ax p(x) и Ay p(y) доказуемо эквивалентны.

Ясно, что так же точно должно обстоять дело и с более сложными формулами.

Однако тут требуется довольно аккуратная формулировка.

Определение 12.1. Нарисуем (прямо «поверх формулы») полные графы,

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

стоят одинаковые кванторы и получившиеся			графы	одинаковы. Другими
словами, подобные	формулы	отличаются	только	буквами, которыми

обозначены различные связанные переменные.

Теорема 12.1. Подобные формулы доказуемо эквивалентны.

Доказательство. Важное продвижение в доказательстве этой теоремы

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

переменную. Иными словами, доказать доказуемую эквивалентность формул

Axp(x) и	Ayp(y	x) (соответственно Exp(x) и Eyp(y	x)),	если формула p(x)	не

содержит переменной y.
Но	это совсем просто: достаточно заметить,			что в этом	случае

подстановка корректна, поэтому формула Axp(x)® p(y x) является аксиомой.

Заметив, что левая часть импликации не содержит переменнойy, можно применить к этой формуле 1, ПБполучив Axp(x)® Ayp(y x). Обратная импликация доказывается точно так же в силу симметричности формул.

Доказуемая эквивалентность формул с другим квантором доказывается абсолютно аналогично.

118

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

QED

2. Предварённая нормальная форма

Определение 12.2.

(1)

Формула

называется предварённой

нормальной

формой (ПНФ), если имеет вид Q1x1Q2 x2 ...Qn xn p(x1, x2 , ..., xn ), где:

а)

p(x1, x2 , ..., xn ) –

бескванторная

формула (у

которой,

возможно,

есть

свободные параметры);

б) Qi Î{A, E} – один из двух кванторов.

(2) Скажем, что предварённая нормальная форма принадлежит классу

а)

P 0 = S0 , если она бескванторная;

p(x1 , x2 , ..., xm

);

б)

P1 , если имеет вид A1 x1 A2 x2 ...Am xm

в) S1 , если имеет вид E1x1E2 x2 ...Em xm

p(x1, x2 , ..., xm ).

(3) Далее,

определим классы P k и Sk

"k Î N

индуктивно. Скажем, что

формула

A1 x1 A2 x2 ...Am

p(x1, x2 , ..., xm ),

где

p(x1, x2 , ..., xm

)ÎS k-1

принадлежит

классу P k .

Аналогично,

скажем,

что

формула

E1x1E2 x2

...Em

p(x1, x2 , ..., xm ),

принадлежит

классу Sk ,

если

формула

p(x1, x2 , ..., xm

)

принадлежит классу P k -1 .

Замечание. Построенная иерархия классов аналогична арифметической

иерархии,

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

для «непрямого»

теорем Тарского и Гёделя о

неполноте. Два существенных отличия этой иерархии от той: во-первых, она не

обязательно

арифметическая (формулы

произвольные),

и,

во-вторых,

последовательности одноимённых кванторов не склеиваются. Эти отличия,

очевидно,

не

являются

принципиальными, поэтому

неудивительно,

что

материал этого пункта во многом аналогичен описанию

арифметической

иерархии.

(Ax p(x))Ù (Ay q(y))

119

Теорема 12.2. Любая формула доказуемо эквивалентна некоторой ПНФ.

Доказательство представляет собой цепочку простых заключений.

а) Отрицание формулы класса Sk принадлежит классу P k , и наоборот,

отрицание формулы классаP k принадлежит классуSk . Действительно,

формулы Ø Axp(x) и ExØp(x) доказуемо эквивалентны, и отрицание, сохраняя

доказуемую	эквивалентность, можно		«протащить»		сквозь	всю	цепочку
кванторов, от чего каждый квантор изменится на противоположный.
б) Покажем, что конъюнкция двух формул классаP1						есть	формула
класса P1 .	Точнее, формула	(Ax p(x))Ù (Ay q(y))			доказуемо	эквивалентна
формуле AxAy(p(x)Ù q(y)). При		этом	можно	считать, что переменная x не
входит свободно в формулу q(y)		и переменная y не входит свободно в формулу
p(x) (иначе – переименуем переменные).
Вывод	формулы AxAy(p(x)Ù q(y)) из			формулы(Ax p(x))Ù (Ay q(y))
представляет собой следующую последовательность:

(посылка);

(Ax p(x))Ù (Ay q(y))® Axp(x) (аксиома);

Axp(x) (МР);

Axp(x)® p(x) (аксиома);

p(x) (МР);

(Ax p(x))Ù (Ay q(y))® Ayq(y) (аксиома);

Ayq(y) (МР);

Ayq(y)® q(y) (аксиома);

q(y) (МР);

p(x)® (q(y)® (p(x)Ù q(y))) (аксиома);

q(y)® (p(x)Ù q(y)) (МР);

p(x)Ù q(y) (МР);

(первая очевидна, вторая получается

			120
Теперь можно		заметить, что	переменные x и y	не	входят свободно в
посылку, поэтому можно дважды, по обеим переменным, применить правило
обобщения,	доказав	требуемую	формулу. Вывод	в	обратную сторону
совершенно аналогичен (упражнение).
Совершенно аналогично доказывается, что дизъюнкция двух формул
класса S1	есть формула классаS1 . Впрочем, проще применить отрицание к
доказанной доказуемой эквивалентности и воспользоваться пунктом а.
в) Ещё два утверждения: «дизъюнкция двух формул класса P1 есть
формула класса P1 » и «конъюнкция двух формул класса S1					есть формула

класса S1 » следуют из общезначимости (следовательно – доказуемости в исчислении предикатов) эквивалентностей

(Ex p(x))Ù (Ey q(y))« ExEy(p(x)Ù q(y)) и

(Ax p(x))Ú (Ay q(y))« AxAy(p(x)Ú q(y))

из первой применением отрицания).

г) Из пунктов б и в очевидно вытекает, что дизъюнкция и конъюнкция формул класса P k есть формула класса P k , и что аналогичное утверждение справедливо и для всех классов Sm . Например, рассуждение

(AxEy p(x, y))Ù (AzEt q(z, t ))« AxAz(Eyp(x, y)Ù Etq(z, t ))«

« AxAz(EyEt (p(x, y)Ù q(z, t ))) показывает, почему дизъюнкция формул класса

P 2 является формулой класса P 2 .

д) Далее, заметим, что использование фиктивных кванторов позволяет


доказать	вложение Sk È P k Í Sk +1 Ç P k +1 . Например, эквивалентности
Ax p(x)« AxEy (p(x)Ù (y = y))« EyAx (p(x)Ù (y = y))		показывают,	что

P1 Í S 2 Ç P 2 . Следовательно, в пункте г необязательно, чтобы обе формулы р

иq принадлежали бы одному классу.

е) Осталось только отметить, что описанные преобразования позволяют

доказуемо эквивалентно преобразовать любую формулу к ПНФ.

QED

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 1112 / 1612 13 14 15 16 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
10.05.2015261.12 Кб9Земельное право.doc
#
10.05.2015306.69 Кб10Земельное право.doc
#
10.05.201557.35 Кб7Земельное право_51-60.docx
#
22.04.2019344.58 Кб3Земцева_Е.М._Реорганизация_юридических_лиц_2011....doc
#
10.12.2018155.14 Кб1ЗП.doc
#
10.05.2015729.77 Кб32И.А. Пушкарев логика.pdf
#
16.03.2016489.98 Кб82ИГиПЗС. Ответы к дифференцированному зачету.doc
#
10.05.201534.82 Кб21ИГПЗС (Балаклеец) ЭКЗАМЕН.doc
#
10.05.201531.23 Кб68ИГПЗС Зачет.doc
#
10.05.201516.38 Кб10ИГПР Кочешков.doc
#
10.05.2015247.3 Кб4ИЗЛ.doc