Исчисление предикат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 константы являются термами.

б). Если f n - функцiональна буква, а t1, t2,...,tn - термы, то f n(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).



Вернуться назад