Числення предикатiв. Теорiя першого порядку, Детальна інформація

Реферат на тему:

Числення предикат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).

У цих акс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ом.