Page 78 - 4570

77

3. Формули логіки предикатів
Означення 2.30. Формулою у логіці предикатів називають вираз, який
задовольняє такі індуктивні визначення.
1. Якщо P – символ n-місного предиката, а t , t , ..., t терми, то Р(t , t ,
1 2 n 1 2
..., t ) формула, яку називають атомарною (елементарною). Всі предметні
n
змінні атомарних формул – вільні, пов’язаних змінних немає.
2. Якщо P формула, то P також формула. Вільні і пов’язані змінні
формули P це відповідно вільні та пов’язані змінні формули P.
3. Якщо F і G формули і немає таких предметних змінних, які були б
пов’язаними в одній формулі, але вільними в іншій, тоді (F  G ) , (F  G ) ,
(F  G ), (F ~G ) є теж формулами, в яких статус змінних зберігається.

4. Якщо Р формула, яка містить вільну змінну х, то  x P і x P також є
формулами. Змінна х у цих формулах стає пов’язаною. Статус інших змінних
зберігається.
5. Ніяких інших формул, крім породжених зазначеними вище правилами,
не існує.
Приклад 2.30. Визначити, які із виразів є формулами логіки предикатів:
а) P(x , x , x );
1 3 5
б)  x 1 x 2 P(x 1, x 2, x 3)   x 1 P(x 1, x 4);
x
в) x 1  3 (P(x 1, x 3)  P(x 3, x 4).
Розв’язання. Вираз а) є атомарною формулою, в якій x , x , x вільні
1 3 5
змінні. Вираз б) є формулою, в якій x , x пов’язані змінні, а x , x вільні
1 2 3 4
змінні. Вираз в) не є формулою, оскільки порушене правило 3 означення вище.
Означення 2.31. Інтерпретацією формули логіки предикатів
називається система, що складається з непорожньої множини М  (М 1  М 2 
…  М n), яку називають областю інтерпретації, і відповідності, яка кожному
n
предикатному символу P i зіставляє певний n-місний предикат, заданий на
n
множині М, кожному функціональному символу f i – деяку n-арну алгебраїчну
операцію, кожній константі α i – деякий конкретний елемент із М.
Для кожної інтерпретації на області D формула F може набувати
істинного T, або хибного F значення згідно з такими правилами:
1. Якщо задані значення формул F і G, то значень істинності формул
(F  G ) , (F  G ) , (F  G ), (F ~G ) можна визначити за допомогою таблиць

істинності відповідних логічних операцій.
2. Формула  x F набуває значення T, якщо F набуває значення T для
кожного х із предикатної області D , у протилежному разі F.
3. Формула x F набуває значення T, якщо F набуває значення T для
деякого х із предикатної області D , у протилежному разі T.
Означення 2.32. Формула логіки предикатів називається:
1) істинною в даній інтерпретації, якщо вона виконується на будь-якому
наборі елементів з області інтерпретації;
2) хибною в даній інтерпретації, якщо вона не виконується на жодному
наборі елементів з області інтерпретації;