Реферат на тему Числення предикат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ом. Поняття виведення (доведення) формули, поняття теореми, виведення формули з множини г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 = тод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ляють менше уваги.
1 2 3 4 5 Категория: Логіка \| Добавил: Aspirant (22.07.2013)
Просмотров: 505 \| Рейтинг: 0.0/0

Всего комментариев: 0


Имя *:
Email *:

Код *: