Page 79 - 4570

78

3) виконуваною в даній інтерпретації, якщо вона виконується хоча б на
одному наборі елементів з області інтерпретації;
4) спростовною в даній інтерпретації, якщо вона не виконується хоча б
на одному наборі елементів з області інтерпретації.
Приклад 2.31. Побудувати інтерпретацію формул:
P(x , x );  x P(x , x ); х 2  х 1 Р(х , х ).
1 2 2 1 2 1 2
Розв’язання. Введемо область інтерпретації – множину цілих додатних
+
чисел Z , а замість P(x 1, x 2) введемо предикат «x 1 ≥ x 2». Перша формула – це
+
саме предикат, побудований на Z . Вона є виконуваною і спростовною. Друга
формула буде виражати одномісний предикат, вона є хибною. Третя формула –
це істинне висловлювання, яке стверджує про існування найменшого цілого
додатного числа.

ЛЕКЦІЯ 16. ЛОГІКА ПРЕДИКАТІВ ПЕРШОГО ПОРЯДКУ

1. Рівносильність формул логіки предикатів

Нехай формули F і G мають одну й ту саму множину вільних змінних
(зокрема порожню).
Означення 2.33. Формули F і G є рівносильними в заданій інтерпретації,
якщо на будь-якому наборі значень вільних змінних вони набувають однакових
значень. Формули F і G є рівносильними на множині М, якщо вони
рівносильні у всіх інтерпретаціях, заданих на множині М. Формули F і G є
рівносильними в логіці предикатів, якщо вони рівносильні на всіх множинах,
тоді F  G .
Приклад 2.32. Визначити рівносильність формул F = P(x ,x )  P(x ,x ) і
1 2 1 3
G = P(x ,x )  P(x ,x ), які задані на множині M = {a, b} предикатами Q (x, y)
1 2 2 3 1
та Q (x, y), наведеними в таблиці.
2

х у Q 1 ( , )х у х у Q 2 ( , )х у

a b T b b T

b b F b b T
b b F b b F
b b T b b F

Розв’язання. Якщо областю інтерпретації є множина М, а у формулах F і
G предикатному символу P зіставляється предикат Q (x,y), то формули F і G
1
рівносильні в заданій інтерпретації, тому що вони набувають значення T тільки
на двох наборах змінних (a, a, a) та (b, b, b), на інших наборах – F.
Якщо областю інтерпретації є множина M, а P інтерпретується як предикат
Q (x, y), то формули F і G нерівносильні в заданій інтерпретації, тому що
2
формула F в наборі (a, b, b) набуває значення T, а формула G значення F.