РЕФЕРАТ

На тему:

Застосування лог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вностi) i (порядку), а функцiональних букв - знаки арифметичних операцiй +, , , / тощо та iнших популярних математичних функцiй. Як предметнi областi найчастiше виступають множина N натуральних чисел, множина Z цiлих чисел, множина R дiйсних чисел, булеан (A) деякої множини A та iн.

Бiльшiсть прикладних числень мiстить предикат рiвностi  i аксiоми, що його визначають. Наприклад, аксiомами для рiвностi можуть бути такi:

E1. x(x x)

E2. (x y)(F(x,x)F(x,y)),

де F(x,y) отримано з F(x,x) шляхом замiни деяких (не обов’язково всiх) входжень x на y за умови, що y у цих входженнях також залишається вiльним.

Будь-яка теорiя, в якiй E1 i E2 є аксiомами або теоремами, називається теорiєю (або численням) з рiвнiстю.

З аксiом E1 i E2 неважко вивести теореми, що описують основнi властивостi рiвностi - рефлексивнiсть, симетричнiсть i транзитивнiсть:

t (t t)

(x y)(y x)

(x y)((y z)(x z)).

Аналогiчно можуть бути введенi три аксiоми, що задають бiльш загальний предикат - предикат еквiвалентностi E(x,y):

Q1. xE(x,x)

Q2. xy(E(x,y)E(y,x))

Q3. xyz((E(x,y)E(y,z))E(x,y)).

Iншим прикладним численням є теорiя часткового порядку, яка мiстить три конкретнi аксiоми для предиката :

O1. x(xx)

O2. xy(((xy)(yx))(x y))

O3. xyz((xy)((yz)(xz))).

Приєднавши до цих аксiом аксiому

O4. xy((xy)(yx)(x y)),

дiстанемо теорiю лiнiйного (строгого) порядку.

Ще одна аксiома (аксiома щiльностi)

O5. xy((xy)z((xz)(zy)))

формалiзує вiдношення лiнiйного (строгого) порядку у щiльних множинах (див.роздiл 1.8), наприклад, у множинi рацiональних або множинi дiйсних чисел.

Найбiльш дослiдженою на сьогоднi формальною теорiєю, яка вiдiграє визначальну роль для аналiзу проблеми обгрунтування засад математики, є так звана формальна арифметика [.......].

У формальнiй арифметицi використовують три функцiональнi букви +, , . Є також одна предикатна буква - символ бiнарного предиката рiвностi  i одна предметна константа 0.

Дев’ять схем спецiальних аксiом задають основнi закони формальної арифметики.

A1. F(0)x(F(x)F(x ))F(x) (принцип iндукцiї)

A2. (t1 t2 )(t1 t2)

A3. (t1 )

A4. (t1 t2)((t1 t3)(t2 t3))

A5. (t1 t2)(t1 t2 )

A6. t1+0 t1

A7. t1+t2t1+t2)

A8. t10 

A9. t1t2 t1t2+t1.

Зауважимо, що формальна арифметика припускає так звану стандартну iнтерпретацiю, в якiй символ  ототожнюється зi звичним знаком рiвностi, 0 - з числом нуль, + i - з традицiйними знаками арифметичних бінарних операцiй додавання i множення, а - з унарною операцiєю «безпосередньо слiдує за». Така iнтерпретацiя відповідає звичній змістовній арифметиці. Кожен терм вiдповiдає деякому натуральному числу, а формула - твердженню про певну властивiсть натуральних чисел або числових змiнних.

Ретельнi дослiдження формальної арифметики дозволили видатному австрiйському математику i логiку Курту Гьоделю i його послiдовникам отримати у 30-х роках ХХ столiття фундаментальнi