Человеческое мышление



Исчисление предикатiв. Теорiя первого порядка

Исчисление предикатiв, то есть формальная теорiя предикатiв строится по вышеприведенной классической схеме построения формальных математических теорiй.

1. Алфавiт исчисление предикатiв, то есть множество вихiдних символiв состоит из Предметных iндивiдних змiнних X1, X2,.. Предметных iндивiдних констант A1, A2,.. Предикатних букв P11, P21.., Pkj,.. i Функцiональних букв F11, F21.., Fkj,.., а также знакiв логiчних операцiй, кванторiв, $ i роздiлових знакiв, запятая.

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

2. Понятия формулы значат в два этапа.

Сначала означают понятие Терма.

А. Предметнi змiннi i предметнi константы являются термами.

Б. Если Fn - функцiональна буква, а T1, T2.., Tn - термы, то Fn T1, T2.., Tn - терм.

В. Iнших термiв, крiм образованных по правилам а i бы, нет.

Вiдтак, формулируют определение Формулы.

А. Если Pn предикатна буква, а T1, T2.., Tn - термы, то Pn T1, T2.., Tn - формула, которая называется Элементарной. Усi вхождения предметных змiнних в формулу Pn T1, T2.., Tn называют Вiльними.

Б. Если F1, F2 - формулы, то выражения F1, F1 F2, F1 F2, F1 F2 тоже являются формулами. Усi вхождения змiнних, вiльнi в F1 i F2, есть вiльними и в усiх четырех видах формул.

В. Если F X - формула, что мiстить вiльнi вхождения змiнної X, то XF X i $ XF X - формулы.

В этих формулах усi вхождения змiнної X называют Связанными. Вхождение остальная змiнних в F остаются вiльними.

Г. Iнших формул, нiж построенных по правилам а, бы i в, нет.

Замечание. Функцiональнi буквы i термы введены в определение для потенцiйних потребностей рiзноманiтних конкретных прикладных исчислений предикатiв. В прикладных исчислениях предметная область M есть, как правило, носiєм определенной системы алгебраизма, потому в численнi доцiльно иметь средства для описания операцiй i вiдношень, заданных на M. Чистое исчисление предикатiв строится для довiльної предметной областi; структура цiєї областi i связки вiдношення мiж ее элементами не берутся к вниманию, потому в нем вводить функцiональнi буквы i термы не обязательно.

3. Аксiоми исчисления предикатiв образуют двi группы аксiом.

А. Первую группу складывают аксiоми довiльного исчисления высказываний например, можно взять любую из вышеприведенных двух систем A1 - A10 или S1 - S3. Как правило, цi аксiоми являются схемами аксiом.

Б. Во вторую группу входят так званi Предикатнi аксiоми:

P1. XF X F Y,

P2. F Y$ XF X.

В этих аксiомах F X - любая формула, какая мiстить вiльнi вхождения X, причем ни одно из них не находится в областi дiї квантора по Y. Формулу F Y получаем из F X замiною всiх вiльних вхождений змiнної X на Y.

Последнее замечание значит, что формула F X не может иметь, например, вид $ YA X, Y или Y A X B Y и тому подобное.

4. Правилами выведения в численнi предикатiв есть такi правила.

А. Правило Выводу modus ponens - то же, что и у численнi высказываний.

Б. Правило Обобщение правило введения квантора : из A B X выводится A XB X.

В. Правило введения квантора $: из B X A выводятся $ XB X A.

В обоих останнiх правилах формула B X мiстить вiльнi вхождения X, а A их не мiстить.

Правило пiдстановки в нашем численнi вiдсутнє. Следовательно, из двух возможных методiв построения исчисления избраны метод зi схемами аксiом. Построение исчисления предикатiв с правилом пiдстановки возможно, однако она есть существенно бiльш громiздкою через необхiднiсть розрiзняти при пiдстановках вiльнi i зв' язанi вхождения предметных змiнних. Поэтому частiше в логiцi используют пiдхiд зi схемами аксiом.

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

Теорема 5.7. Любая вивiдна формула теорема исчисления предикатiв есть тождественно iстиною логiчно общезначимой формулой.

Эта теорема приходится аналогiчно теоремi 5.5. Сначала непосредственно перевiряється, что всi аксiоми являются лзз формулами. Вiдтак, придется, что усi правила выведения зберiгають властивiсть лзз.

Теорема 5.8. Любая тождественно iстинна предикатна формула является вивiдною теоремой в численнi предикатiв.

Доказательство цiєї теоремы достаточно сложное i здесь не будет наводиться.

Из останнiх теорем выплывает утверждение, подiбне к утверждению теоремы 5.1.

Теорема 5.9. Предикатнi формулы A i B рiвносильнi тодi i тiльки тодi, когда формула A B B A есть вивiдною в численнi предикатiв, то есть есть лзз.

Как i ранiше, для сокращения выражения A B B A вводят операцiю ~ i записывают данное выражение в виглядi A~ B. Следовательно, последнюю теорему можно переформулировать так: формулы A i B рiвносильнi A= B тодi i тiльки тодi, когда формула A~ B есть вивiдною в численнi предикатiв.

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

Построенное исчисление предикатiв называют Исчислением предикатiв первого порядка, или Теорiєю первого порядка. В такiй теорiї аргументами фунцiй i предикатiв, а также змiнними, что связываются кванторами, могут быть лишь предметнi змiннi. В исчислениях второго i высших порядкiв аргументами предикатiв могут быть i предикаты, а кванторы могут связывать i предикатнi змiннi, то есть допустимi выражения, например, вида P P X. Применение таких исчислений зустрiчається значительно рiдше, потому в математичнiй логiцi им придiляють меньше внимания.