25. Квантори . Кванторні операції над предикатами.

Змінна, не зв'язана ніяким квантором, називається вільною.

В ід того, чи є змінна зв'язаною або вільною, залежить значення предиката. Вільна змінна - це предметна змінна, яка може приймати різні значення з множини М, і значення предиката Р (х) залежить від значення змінної х. Навпаки, вираз Vx Р(х) не залежить від змінної х і при заданих Р і М має визначене значення; тут х — зв'язана змінна.

Визначення

Н ехай Р(х) — предикат, визначений на М. Висловлення «для всіх х є М, Р(х) істинне» позначається Vx Р(х). Знак V називається квантором загальності.

Квантори керують областю значення змінної, наступної за символом квантора. Якщо застосовується квантор загальності, то ми говоримо, що висловлення істинне для всіх х з деякої множини.

Визначення

Висловлення «існує таке х є М, що Р(х) істинне» по­значається Ǝх Р(х), де знак називається квантором існування.

Квантор існування застосовується, коли треба вказати, що існує хоча б одне значення змінної, для якого істинне це висловлення.

В логіці предикатів снує таке об­меження: не можна застосовувати квантори до предикатів.

Визначення

Якщо Р — n-місний предикат і t₁, t₂ ,…,t_n — терми, то Р(t₁, t₂ ,…,t_n) називається атомом або елементарною фор­мулою логіки предикатів.

Визначення

Правильно побудованими формулами логіки предикатів називаються формули, які можна рекурсивно визначити таким чином:

1. Атом є формулою.

2. Якщо Р і Є — формули, то (-,*"), (Р ˅ в), (Р ˄ Є), (Р → Є), (Р↔Є) також є формулами.

3. Якщо Р— формула, а х — вільна змінна, то (˅х)Р і (Зх)Р теж формули.

4. Ніяких формул, крім породжених вказаними вище правилами, не існує.

Визначення

Частина формули, на яку поширюється дія квантора, називається областю дії квантора.

Оскільки дія квантора може поширюватися не на всю фор­мулу, а тільки на її частину, то змінна може бути зв'язаною в одній частині формули і вільною в другій. У цьому випадку вважають, що змінна є і зв'язаною, і вільною одночасно.

26. Формули логіки предикатів.

У побудові формул будемо використовувати такі символи :

1. X,y,z,u,v,w , а також ці букви з індексами для позначення предметних змінних.

2. Якщо ми позначаємо а,в,с, або ці букви з індексом то то є позначення предметних констант.

3. F,h,g можуть бути з індексами для позначення функціональних символів.

4. P, G, R, S, T можуть бути з індеkсом для позначення предикатних змінних.

5. ⌐, ∞, →, ˅, ˄, Ǝ, ∀ для позначення знаків логічних операцій.

6. (), допоміжні символи.(терми, терма).

Зробимо визначення терма.

1. Предметні змінні і предметні константи є терми.

2. Якщо t₁, t_2, t_3,…, t_n - терми , а fⁿ , gⁿ, hⁿ функціональні змінні , то fⁿ (t₁, t_2, t_3,…, t_n) також є термом.

3. Інших термів крім тих що визначенні в пунктах 1 – 2 немає.

Формули логіки предикатів визначаємо рекурсивно. У логіці висловлень елементним об’єктом є атомарне висловлення. У логіці предикатів таким елементним об’єктом, якому притаманне значення істинності є атомарна формула, такі формули називаються елементарними. Атомарна форма записується , як позначення предиката Рⁿ (t₁, t_2, t_3,…, t_n), Рⁿ - предикатний символ, t₁, t_2, t_3,…, t_n - терми Р⁰ – атомарна форма і просте висловлення.

Означення :

1. Атомарна формула є формулою логіки предикатів;

2. Я кщо α і β формули логіки предикатів (α), (α˄β), (α˅β), (α→β), (α∞β) також формули логіки предикатів.

3. Якщо α(х) формула логіки предикатів, ∀_х( α(х)), Ǝ_х (α(х)) – також формули логіки предикатів.

4. Інших формул логіки предикатів в зазначених пунктах вище не існує.

Формули логіки предикатів часто називаються правильно побудованими формулами (ППФ).

Означення: у формулі логіки предикатів можуть ходити , як вільні так і зв’язані змінні.

∀_х( α(х) →Q(х; у)) формули які не містять жодної вільної змінної називають замкненими , або реченнями. Ті що містять вільні предметні змінні називаються відкритими.

Ǝ_х ∀_х( α(х) →Q(х; у)) формула називається значущою , якщо існує хоча б одна інтерпретація на якій формула істина.

Формула логічно загально значуща , якщо при довільній інтерпретації вона істина.

Формула хибна при довільній інтерпретації називається протиріччя.

Означення: логічно загально значущі формули являються вільними формулами предикатів. Оскільки область визначення предикатів може бути нескінчена , то таблиця істинності не може служити алгоритмом для визначення істинності предикатів. Можна побудувати таблицю істинності на обмежених областях.

Ǝ_х Ǝ_у (Р(х)˄Р(у)→Q(f(x; y) формула замкнена. Тому будь – яка її інтерпретація є висловлення. Якщо за область інтерпретації взяти множину цілих чисел , а Р_z інтерпретувати , як (z- просте число ) Q(z) – будемо інтерпретувати z =2 (f(u; v)) - значення u v , то інтерпретація формули є істинне висловлення .

Ǝ_х Ǝ_у (х – просте число і у – просте число → х – у = 0). Якщо за областю інтерпретації взяти множину цілих чисел Р_z z- непарне число, Qz – будемо інтерпретувати z – не ділиться націло на 2 R(u; v) u – v ,то формула набуватиме хибного значення.

Серед формул логіки предикатів особливе місце приймають тотожно – істині формули. ЛЗЗ – абріатура логіки предикатів.