Page 37 - 6109

істинні формули, які називають тавтологіями. Приклад тавтології:
~~АА.
Поняття формули вводиться рекурсивно:
– атом є формула;
– якщо А – формула то і ~A – фомула;
– якщо А формула то А  В, А  В, АВ, АВ теж формули;
– якщо А – формула і х – змінна, то хА, хА – формули.
Формули логіки предикатів можна будувати виходячи з трьох множин: F
– символи (імена функцій; P – символи (імена) предикатів; V – змінні.

Об’єднання АР називається сигнатурою, вона визначається змістом
вирішуваної задачі.
Змінна в формулі можуть бути зв’язаними та вільними. Входження
змінної у формулу є зв’язаним, якщо змінна знаходиться за квантором або
входить в область дії квантора по цій змінній. В іншому випадку входження –
вільне.
Наприклад, t(x)  y[s(x,y) x(r(x,y) t(y))]
Змінна є вільною, якщо є хоча б одне вільне входження змінної в
формулу.
Співставлення формулі логіки предикатів предикату є інтерпретацією.
Інтерпретацією формули на не порожній множині М називається функція, яка
задана на сигнатурі , що ставить у відповідність:
1) константі – елемент з М;
2) символу n–містної функції – деяку n–містну функцію, що визначається
на М;
3) символу n–містного предикату – n–містний предикат, заданий на М;
Наприклад, задана сигнатура (P,D), яка визначає одномісний предикат
Р(х) та двомісний предикат D(x,y) та формулу F=P(x)& y(P(y) D(x,y)) на
множині М={2,3,6,9,12,15}
Нехай – «непарне число» та – «х поділяє у». В цьому випадку F отримає у
відповідність х=3.
Якщо  – інтерпретація, то предикат, що відповідає формулі F
позначається, як (F).
Формули F(x 1,…,x n) та G(x 1,…,x n) рівносильні, якщо для любої
інтерпретації  з областю М вирази (F)(а 1,…,а n) та (G)(а 1,…,а n) при будь-
яких а 1,…,а n з М одночасно істинні або хибні.

Формула F(x 1,…,x n) тотожно істинна, якщо для любої інтерпретації  з
областю М вирази (F)(а 1,…,а n) при будь-яких а 1,…,а n з М є істинні.
Поняття рівносильності та тотожної істинності є рівними. Так, формули
F(x 1,…,x n) та G(x 1,…,x n) рівносильні тоді і тільки тоді коли формули
F(x 1,…,x n)G(x 1,…,x n) тотожно істинні.
4.2.2 Поняття логічного наслідку
Формула G(x 1,…,x n) називається логічним наслідком формул F 1(x 1,…,x n),
…, F k(x 1,…,x n), якщо для любої інтерпретації  з областю М та при будь-яких
а 1,…,а n  М, із істинності виразів (F 1)(а 1,…,а n), …, (F k)(а 1,…,а n) слідує

37