РЕФЕРАТ
На тему:
Числення предикат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ом.
Поняття виведення (доведення) формули, поняття теореми, виведення
формули з множини г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ляють менше уваги.
Нашли опечатку? Выделите и нажмите CTRL+Enter
