Добавил:

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

Вуз:

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

Предмет:

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

Файл:

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

.pdf

Скачиваний:

Добавлен:

10.05.2015

Размер:

729.77 Кб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 67 / 167 8 9 10 11 12 13 14 15 16 > Следующая >>>

§7. Выразимость предикатов 1. Выразимые предикаты

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

Определение 7.1. Пусть S = S(x1, x2 , ..., xk ) – k-местный предикат. Назовём

его выразимым		в рассматриваемой интерпретации, если существует формула
p(x1, x2 , ..., xk )ÎФ с k параметрами x1, x2 , ..., xk , такая что для любой оценкиξ
[p](x )=1	Û	S (x1, x2 , ..., xk )=1.		В	этом	случае	говорят, что		формула
p(x1, x2 , ..., xk ) выражает предикат S.
Замечание.		Формула	имеет		фиксированный			набор	переменных,
являющихся её параметрами. Предикат – не имеет, они имеет только арность,
она же –	местность (количество			аргументов).		Соответственно, выразимый
предикат выражается не одной только формулой. Впрочем, возможно, что
предикат	выражается		вообще		несколькими		принципиально		различными
формулами. Собственно, не возможно, а – наверняка J!

Примеры. Важнейшей из выразимостей для нас является выразимость в арифметике. Соответствующая сигнатура состоит из двух двухместных

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

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

арифметическими. Их важность связана с теоремой Гёделя о неполноте,

которая уже обсуждалась. Арифметическими, например, являются следующие предикаты:

(1)x £ y : Ez(x + z = y);

(2)x = 0 : x + x = x ;

(3)x =1: x ´ x = x ;

			62
(4)	x = n	для	любого	фиксированного	натуральногоn:
EyEz2 Ez3...Ezn (y =1)Ù (y + y = z2 )Ù (z2 + y = z3 )... Ù (zn-1 + y = zn )Ù (zn = x)					–

при фиксированном n это «настоящая» формула;

(5)x y : Ez(x ´ z = y);

(6)«x – простое число»: Ay((y x)® ((y =1)Ú (y = x)));


(7)		«x	является			степенью		»:
Ay(((y	x)Ù N (y =1))® Ez((z = 2)Ù (z			y))), то	есть:	«любой	делитель,	не

являющийся единицей, является чётным числом», не						вполне тривиально,		что
это равносильно тому, что число является двойкой.
(8)		Предикат «x является степенью четверки» является

арифметическим, хотя приём из предыдущего примера тут явно не проходит.

Могла бы выручить «формула» вида

EnEzEy1Ey2 ...Eyn (z = 4)Ù (y1 =1)Ù (y2 = z ´ y1 )Ù ... Ù (yn = z ´ yn-1 )Ù (x = yn ), но

она не является настоящей формулой, так как количество переменных в ней заранее неизвестно. К счастью, в точности для таких случаев у нас есть β-

функция Гёделя (есть и другой приём). Аналогично показывается, что арифметическим является двухместный предикат x = 4 y .

2. Невыразимые предикаты: автоморфизм

Было бы удивительно, если бы все предикаты оказались выразимыми.

Доказывать	невыразимость	предикатов	можно	различными	способами.
Например, если интерпретация «симметрична», а			предикат «несимметричен»,

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

помощью понятия автоморфизма интерпретации.
Определение 7.2. Перестановка a : W ® W	предметного множества

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

рассматриваемой		сигнатуры устойчивы относительно этой перестановки, то
есть	для	любойk-местной	функции f	выполняется	свойство

63
f (a(x1 ), a(x2 ), ..., a(xn ))= a(f (x1, x2 , ..., xn )),	а	для	любогоm-местного
предиката А – свойство А(a(x1 ), a(x2 ), ..., a(xn ))=1		Û А(x1, x2 , ..., xn )=1.
Теорема 7.1. Предикат, выразимый в	данной интерпретации, устойчив

относительно её автоморфизмов.

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

QED

Примеры.

(1)Рассмотрим сигнатуру из двух бинарных отношений= и < на предметном множестве Z целых чисел, интерпретация естественная. Тогда предикат x = 0 невыразим. Автоморфизм x a x +1.

(2)Рассмотрим сигнатуру из функции сложения+ и бинарных отношений

=и < на предметном множестве Q рациональных чисел, интерпретация снова естественная. Предикат x = 0 выразим (есть сложение). Однако предикаты вида

x= c при c ¹ 0 невыразимы. Автоморфизм x a 2x .

(3)Рассмотрим сигнатуру из функции сложения, отношения равенства и двух констант (функций без переменных) 0 и 1 на предметном множествеR

действительных чисел, интерпретация естественная. Предикат x = c					выразим
при с ÎQ и невыразим приc ÏQ . Выразимость для натуральных, целых и
рациональных (по	очереди) с	очевидна. Для	построения	рассмотримR		как
(бесконечномерное)	линейное	пространство	надQ. Пусть	с1 и	с2 –	два

различных иррациональных числа, с1 ¹ q × c2	"q ÎQ . Не умаляя общности, эти
числа входят в базисR над Q. Линейное преобразование, переставляющее эти
числа, и не меняющее остальные	элементы базиса есть подходящи
автоморфизм.

3. Невыразимые предикаты: элиминация кванторов

Иногда всё не так просто. Просто – но не такJ. Бывают сигнатуры, у

которых просто нет ни одного автоморфизма. Но это отнюдь не означает, что в них выразимы все предикаты. Другой способ доказательства невыразимости– указать некоторое семействоΞ предикатов, содержащее все выразимые предикаты, но не содержащее рассматриваемого. Очень часто семействоΞ состоит из предикатов, выразимых бескванторными формулами. Для этого следует показать, что любая формула задаёт предикат, который можно задать и другой формулой, которая не содержит кванторов (формулы, задающие один и тот же предикат, назовём эквивалентными). Соответствующая процедура преобразования формул называетсяэлиминацией (постепенным удалением)

кванторов.

Пример 1. Плотный линейный порядок

Рассмотрим предметное множествоQ с сигнатурой{<, =} и обычной

интерпретацией.

Теорема 7.2. Любая формула в этой интерпретации эквивалентна некоторой бескванторной формуле.

Доказательство. (а) Достаточно элиминировать один квантор: если их

несколько, их можно элиминировать по одному изнутри. Можно считать, что

этот квантор Е, потому что формулы Axq(x) и NExNq(x)				эквивалентны. Итак,
рассмотрим	формулу	видаЕxq(x, x1, ..., xn ),	выражающую некоторый n-
местный	предикат. При	этом атомарные	формулы	имеют видy = z или

y < z . Можно считать, что формула q записана в дизъюнктивной нормальной

форме, то	есть –	в виде	дизъюнкции конъюнкций		формул видаy = z ,			y < z ,
N (y = z )	и N (y < z).		Можно	заменить N (y	= z )	на	эквивалентную
(y < z)Ú (z < y), а		N (y < z) – на		эквивалентную (y	= z)Ú (z < y).		После	этого

можно воспользоваться дистрибутивностью, получив ДНФ уже без отрицаний.

(б) Заметим,

что

формулы Ex(q1 Ú q2 Ú ... Ú qm )

и Exq1 Ú Exq2 Ú ... Ú Exqm

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

«бесконечная дизъюнкция»!), поэтому достаточно научиться элиминировать

квантор

из

формул

видаEx(p1 Ù p2 Ù ... Ù pk ),

где

все pi

–

суть

атомарные

формулы

следующих видов:

x = xi ,

x < xi ,

xi < x ,

= x j ,

< x j .

Два

последних типа атомарных формул не содержат переменнуюx, поэтому могут

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

что все формулы pi содержат переменную x.

(в)

Если

среди

атомарных

формул

есть

формула

x вида= x ,

то

рассматриваемая

формула

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

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

фо

Ù ...

где

получается

из

формулыpi

заменой

Ù p2

Ù pk ,

формула pi

переменной x на переменную xi , так как во всех оценках, на которых истинна

эта формула, переменные x

xi должны принимать

одинаковые

значения.

Поэтому можно считать, что все атомарные формулы pi

имеют вид x < xi

или

xi < x .

(г) Переобозначим (для

простоты)

переменные,

так,

чтобы

рассматриваемая

формула

приобрела

Ex(x1 < x)Ù (x2 < x)Ù ... Ù (xn < x)Ù (x < y1 )Ù (x < y2 )Ù ... Ù (x < yk ).

Если

все

неравенства одного знака, то формула тождественно истинна(в Q нет

наибольшего и наименьшего элементов). Если же присутствуют оба вида

неравенств, то рассматриваемая формула означает, что существует некоторое

число x, которое больше всех чисел xi

и меньше всех чисел y j . Поскольку тех

других –

конечное

число, то (для

рациональных

чисел) это

означает,

что

любое число xi

меньше любого числа y j

(потому что между любыми двумя

рациональными

числами

найдётся

ещё

, однонапример

–

их

среднее

арифметическое).

Поэтому

рассматриваемая

формула

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

(бескванторной!) конъюнкции всех формул вида xi < y j .

QED

		66
Замечания. (1) Заменив Q		на R, мы не	почувствуем разницы. В
действительности	рассматривать R	даже удобнее: в нужный момент можно
просто сослаться	на аксиому	полноты. Вообще	подойдёт любое плотное

линейно упорядоченное множество без наибольшего и наименьшего элементов.

Во всех этих интерпретациях истинны одни и те же формулы. Немного позднее мы назовём такие интерпретации элементарно эквивалентными.

(2) Бескванторная формула есть, по сути, формула пропозициональной

логики (в которой простые высказывания – суть атомарные формулы). Поэтому

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

рассмотренных интерпретациях, разрешима (как часть пропозициональной теории).

(3) Если добавить к рассматриваемой сигнатуре сложение и рациональные

константы, то ситуация, как ни странно, не усложнится. Здесь поможет приём,

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

Теорема 7.3. Любая формула в сигнатуре{+, <, =, 1, -1} эквивалентна

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

Доказательство. Как уже (вскользь) отмечалось, квантор существования

есть, по сути, «бесконечная дизъюнкция». Точнее, утверждение $x ÎQ : p(x)

равносильно «псевдоформуле» (V (x = c))Þ p(x) , где слева стоит дизъюнкция всех формул вида x = c при c ÎQ . Вполне возможно, что нет необходимости

рассматривать «вот так прямо» все рациональные числа, а можно ограничиться

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

сконструировать таковой набор, но появления сложения и констант± 1 такую

				67
возможность	предоставляет.			Правда	при	этом	увеличивается	и	набор
атомарных формул, но это обстоятельство оказывается непринципиальным.
Действительно,		атомарные				формулы приобретут			вид
li (x, x1, ..., xn ) = l j (x, x1 , ..., xn )				или li (x, x1, ..., xn ) < l j (x, x1 , ..., xn ) ,				где
li (x, x1, ..., xn )	–	суть	линейные		комбинации		переменных	с	целыми
коэффициентами и, возможно, свободным членом, равным такой же линейной
комбинации разрешённых			констант. Откуда			возьмутся	целые коэффициенты
(умножения-то	нет)? Они		возникнут		из	сумм видаx + x + ... + x , которые
							14243

естественно заменить на n × x .

Любая такая атомарная формула эквивалентна«разрешённой» формуле

вида x = l j (x1, ..., xn ) , x < l j (x1, ..., xn ) или l j (x1, ..., xn ) < x : в формуле можно

«по-школьному» выразить переменную x через остальные, получив линейную комбинацию, вообще говоря, с рациональными коэффициентами. Это не совсем

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

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

следует

рассмотреть «представительный

набор

термов», состоящий из всех

получившихся

термов l j (x1, ..., xn ) ,

их

средних

арифметических

l j (x1, ..., xn ) + l j (x1 , ..., xn )

, и сдвигов l

(x , ..., x

) ±1

(или какие там

у нас

окажутся

константы

разных

знаков…). Обозначим

этот

набор

термов

t1 , t2 , ..., tN . Теперь, очевидно, фрагмент формулы Ex можно заменить на более

длинный,

зато

–

бескванторный

эквивалентн

(x = t1 )Ú (x < t1 )Ú (t1 < x)Ú (x = t2 )Ú ...

QED

Теорема 7.3. имеет любопытное следствие.

Теорема 7.4. Пусть единичный квадрат разрезан на несколько меньших

квадратов. Тогда все они имеют рациональные стороны.

Доказательство. Пусть дано такое разрезание на n квадратов. Опишем его

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

формула с n параметрами F (x1, ..., xn ), которая истинна тогда и только тогда,

когда единичный квадрат можно разрезать на квадраты со сторонами x1, ..., xn .

Согласно теореме 7.3, эту формулу можно подвергнуть элиминации

кванторов, после чего из неё получится бескванторная формулаG(x1, ..., xn ) –

логическая комбинация линейных уравнений и линейных неравенств(строгих:

у нас есть только отношение<). На этом использование логических

соображений заканчивается J.

Рассмотрим произвольное разрезание, пусть стороны квадратов этого

разрезания – суть	действительные числа y1, ..., yn . Тогда G(y1, ..., yn )=1. При
этом некоторые	равенства, которые входят вG становятся верными, а

некоторые – нет. Рассмотрим те из них, которые оказались верными в этом случае, как систему линейных уравнений. Если эта система имеет ровно одно решение, то оно рационально (ну там – формула Крамера, метод исключения,

любые подобные соображения…). Осталось показать, что это так и есть, то есть

– эти уравнения «достаточно разнообразны».

Пусть это не так. Тогда существует целая прямая, состоящая из решений

этой системы. Пусть (h1, ..., hn ) – направляющий вектор этой прямой. Тогда

существует достаточно малое числоε, такое,	G(y1 + e h1, ..., yn + e hn )=1.
Действительно, ε можно выбрать настолько малым, чтобы все		неравенства,
которые верны для набораy1, ..., yn остались	бы верными	и для набора

					69
y1 + e h1, ..., yn + e hn .	Поэтому			«с	точки зрения»	формулы	G		второй	набор
окажется неотличим от первого.
Итак, получается, что единичный квадрат можно разрезать и на квадраты
со сторонами y + e h , ..., y		n	+ e h .		Поэтому (y + e h )2 + ... + (y			n	+ e h )2 º1 на
1	1	n		n	1	1		n	n
небольшом отрезке,	но	всё-таки – ненулевой				длины. Левая			часть	этого

равенства – квадратичный трёхчлен от ε. Он может быть тождественно равен

константе		только	если его коэффициент	2
константе		только	если его коэффициент	eприравен нулю, то есть
h2	+ ... + h2	= 0 , но	это противоречит тому, что	вектор (h , ..., h )		ненулевой.
1	n			1	n

Полученное противоречие завершает доказательство.

QED

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

Но всё-таки – почему такую систему можно написатьвсегда? Потому что трудно представить себе разрезание, для которого её нельзя написать, что ли

J? Слабый аргумент…

Пример 2. Теория равенства Случается, что все кванторы элиминировать невозможно. Например,

рассмотрим сигнатуру {=}. Теорией равенства назовём множество всех формул этой сигнатуры, истинных во всех нормальных интерпретациях. Совершенно ясно, что формула ExEyEz(Ø(x = y)Ù Ø(x = z)Ù Ø(y = z)) выражает свойство «(в

рассматриваемом множестве) существует не менее трёх различных элементов».

Записать это свойство без кванторов невозможно(в рассматриваемой теории вообще мало что можно записать без кванторов).

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

бессмысленно? Нет. Можно разделить все кванторы на«ручные», без которых

невозможно обойтись, и которые ведут себя «контролируемо» и «не мешают»,

и «дикие», которые следует элиминировать. После этого (на самом деле – до J)

за счёт расширения сигнатуры можно устранить и «ручные» кванторы.

Обозначим приведённую формулу символом С3

и определим аналогично

счётное

множество

нульарных

отношенийС

расширив

тем

самым

рассматриваемую

сигнатуру.

Далее,

будем

рассматривать

только

те

интерпретации, на которых символы Сk

означают то же, что они означали до

своего появления J. Произведённое расширение не меняет класса выразимых

предикатов. Уменьшить его оно не может, не может и увеличить: все

добавленные символы являются символами выразимых отношений.

Теорема 7.5. Рассматриваемая теория допускает элиминацию кванторов.

Доказательство. Как и в теореме7.2, достаточно избавиться от одного

квантора существования вида Exp(x, y1, ..., yn ),

где р есть конъюнкция формул

(x = y j ),

Ø(x = y j ),

(yi

= y j ),

Ø(yi = y j ).

Теперь

элиминация

кванторов

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

а) Наличие формулы (x = y j )

позволяет сразу заменить рассматриваемую

формулу эквивалентной бескванторной p(y j ,

y1, ..., yn ).

б) Аналогично, формулы вида (yi = y j )

можно удалить,

просто уменьшив

число

переменных,

если

это

не

противоречит какой-то

формуле

вида

Ø(yi = y j ). Если

же

такое

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

обнаружилось, формула

является

тождественно ложной.

в) Формулы

вида Ø(yi

= y j )

не содержат подкванторной переменной и

могут

быть

вынесены

перед

квантором. Это

приведёт

формуле вида

R Ù ExØ(x = yi

)Ù ... Ù Ø(x = yi ).

<<< < Предыдущая 1 2 3 4 5 67 / 167 8 9 10 11 12 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