Тема „Логіка і числення предикатів”

Одним із важливих понять математичної логіки є поняття предиката.

Означення 1. Предикатом від n змінних x₁, …, x_n (n-місним предикатом) називається вираз p(x₁, …, x_n), який стає висловлюванням при підстановці значень змінних x₁, …, x_n із множини M₁, …, M_n.

Отже, предикат – це функція p(x₁, …, x_n), змінні якої набувають значень із деякої множини M, а сама вона набуває двох значень: 1 (істинне) та 0 (хибне).

Приклади предикатів: p(x) = „x – просте число, x  N”; g(x, y) = „x < y, (x, y)  R  R”.

Довільний n-місний предикат p(x₁, …, x_n) можна формально розглядати як одномісний предикат, визначений на множині M – декартовому добутку множин M₁  …  M_n.

Оскільки при конкретних значеннях змінних x₁, …, x_n предикат p(x₁, …, x_n) перетворюється у висловлювання, а для висловлювань визначені операції заперечення, кон’юнкції, диз’юнкції, імплікації, еквівалентності, то можна природно поширити всі ці операції і на предикати.

Наприклад, запереченням (x) предиката p(x) називається предикат, область визначення якого збігається з областю визначення предиката p(x), а істинні значення визначаються так: якщо p(x) = 1, то (x) = 0; якщо p(x) = 0, то (x) = 1.

Приклад 1. Нехай p₁(x) позначає предикат „x ділиться на два”, q₁(x) – предикат „x ділиться на три”. Тоді вираз p₁(x)  q₁(x) позначає предикат „x ділиться на два та x ділиться на три”, тобто позначає предикат ділення на 6.

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

Квантор загальності. Нехай P(x) – деякий предикат, який набуває значення 1 або 0 для кожного елемента x множини M. Тоді під виразом (x)P(x) матимемо на увазі істинне висловлювання, коли P(x) – істинне для кожного елемента x із множини M, і хибне – в іншому випадку. Читається цей вираз так: „для всіх x P(x)” або „для будь-якого x P(x)”.

Це висловлювання вже не залежить від x. Символ  називається квантором загальності.

Квантор існування. Нехай P(x) – деякий предикат. Під виразом (x)P(x) будемо розуміти істинне висловлювання, коли існує елемент множини M, для якого P(x) – істинне, та хибне – в іншому випадку. Читається цей вираз так: „існує x таке, що P(x)” або „існує x, для якого P(x)”. Символ  називається квантором існування.

Приклад 2. Для предикатів, наведених у прикладі 1, маємо (x)(p₁(x) q₁(x)) – істинне висловлення, а (x)( p₁(x) q₁(x)) – хибне висловлення.

Уведемо поняття формули логіки предикатів. Алфавіт цієї логіки містить такі символи:

• предметних змінних x₁, x₂, …, x_n, …;

• предикатів , , …, , …, де t = 0, 1, 2, …;

• логічні , , , , ~;

• кванторів , ;

• дужки ( ) і кому „ ,”.

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

Означення 2. Слово в алфавіті логіки предикатів називається формулою, якщо вона задовольняє таке індуктивне означення (одночасно визначаються поняття вільної та зв’язаної змінних у формулі):

1. Якщо - символ предиката, , , …, - символи предметних змінних, не обов’язково різних, то ( , , …, ) – формула, яка називається атомарною. Всі предметні змінні атомарних формул є вільними, зв’язаних змінних немає.

2. Нехай А – формула. Тоді – також формула. Вільні й зв’язані змінні формули – це відповідно вільні та зв’язані змінні формули А.

3. Нехай А і В – формули, причому немає таких предметних змінних, які були б зв’язаними в одній формулі, але вільними в іншій. Тоді (A  B), (A  B), (A  B), (A ~ B) є формулами, в яких вільні змінні формул А і В залишаються вільними, а зв’язані змінні формул А і В – зв’язаними.

4. Нехай А – формула, яка містить вільну змінну x. Тоді

(x)A, (x)A (1)

також є формулою. Змінна x у них – зв’язана. Інші ж змінні, які у формулі А є вільними, залишаються вільними й у формулах (1). У першій із формул (1) формула А називається областю дії квантора , а в другій – областю дії квантора 

5. Слово в алфавітній логіці предикатів є формулою тільки в тому випадку, якщо це випливає з правил 1 – 4. Зазначимо, що за означенням формули жодна змінна не може бути одночасно вільною та зв’язаною.

Приклад 3. (x₁)(x₂) (x₁, x₂, x₃)  (x₁) (x₁, x₄) – формула, в якій x₁, x₂ – зв’язані, а x₃, x₄ – вільні змінні.

Значення формули визначено лише тоді, коли задано яку-небудь інтерпретацію символів, що входять до неї.

Означення 3. Під інтерпретацією розуміють систему M_f = (M, f), яка складається з непорожньої множини M і відповідності f, що зіставляє з кожним предикативним символом певний t-місний предикат (будемо позначати предикати, поставлені у відповідність предикатним символам, тими самими символами).

Приклад 4. Нехай f(x) – довільна фіксована функція, задана на відрізку [a, b]. Розглянемо інтерпретацію M_f = (M, f₁), де M – множина дійсних чисел, f₁ – відповідність, що зіставляє із предикатними символами P(x, ), Q(x, ) та R() предикати P(x, ): |x – x₀| < , Q(x, ): |f(x) – A| < , R():  > 0. Тут x₀ – фіксований елемент відрізка [a, b], A – фіксоване дійсне число. Тоді твердження про те, що число A = , записується формулою

()()(x)((R()  P(x, ))  Q(x, )).

Розглянемо інтерпретацію M_f = (M, f₂), де M – множина дійсних чисел, f₂ – відповідність, що зіставляє з предикатними символами P₁(x, x₁, ), R(), S₁(x, x₁, ), D(x) предикати P₁(x, x₁, ): |x – x₁| < , R(): > 0, S₁(x, x₁, ): |f(x) – f(x₁)| < , D(x): x  [a, b]. Тоді твердження про те, що функція f(x) є неперервною на відрізку [a, b], записується формулою

(x₁)()()(x)((D(x₁)  R()  P₁(x, x₁, ))  S₁(x, x₁, )).