нє безліч Р зване областю інтерпретації. Кожному символу зіставляється елемент з Р, кожному символу предиката зіставляється ставлення. Кожному символу функції р Реальний функція з безлічі G. Формула здійсненна, якщо є інтерпретація, в якій вона істина. p align="justify"> Визначення: Замиканням формул А з параметрами х1, х2, .., хn є формула види: для кожного х1, х2, .. хn А. Формула обчислення предикатів називається загальнозначущої, якщо її замикання істинно в будь інтерпретації. При перевірці загальної значущості формул важливо пам'ятати, що за її параметрами беруться квантори загальності. Наприклад, квадрат дійсного числа позитивний, але воно не загальнозначуще, тому що 0 в квадраті = 0, що не є позитивним числом. Загальнозначущим буде твердження квадрат будь-якого дійсного числа неотрицателен. Формула називається нездійсненним, якщо замикання її заперечення загальнозначуще. Формула здійсненна якщо не вірно, що вона нездійсненна. Загальзначимість формули - це узагальнення тавтології в ІВ. Можна сформулювати це твердження більш формально. Інтерпретація називається моделлю формул або безліччю формул, якщо на ній всі формули тотожно істини. Формули А і В еквівалентні, якщо кожна з них є логічним наслідком іншої. br/>
загальнозначуща тавтологію
Загальнозначущі формули - це узагальнення тавтологію в обчисленні висловлювань. Обчислення висловлювань дозволять виводити всі тавтології з деякого набору базисних тавтологію (названих аксіомами) за допомогою деяких правил виводу (насправді єдиного правила modusponens). p align="justify"> 1) Нехай A - тавтологія, x1,. . . , Xn - набір пропозіціональних змінних, які входять в A, а F1,. . . , Fn - формули ВП. Тоді формула A (F1, ..., Fn) общезначима.
2) Доведемо, що формула ? x ? y A (x, y)? ? y ? x A (x, y) общезначима.
Інтерпретацію бінарного предикатного символу зручно представляти у вигляді орієнтованого графа (бути може, нескінченного). Множествовершін графа збігається з областю інтерпретації, а впорядкована пара (x, y) належить множествуребер графа тоді і тільки тоді, коли пара (x, y) належить відношенню [A]. p align="justify"> При такому розумінні посилка написаної формули означає, що в графі є вершина x, з которойідут ребра в усі інші вершини. Але тоді длялюбой вершини графа знайдеться яке у неї ребро (воно виходить з вершини x). Саме це і утверждаетзаключеніе формули. br/>
Обчислення предикатів 1-го порядку
Кажуть, що задано числення предикатів першого порядку, коли:
) задано алфавіт:
Вѕ рахункового безлічі X символів змінних;
Вѕ рахункового безлічі P предикатних символів;
Вѕ рахункового безлічі F функціональних символів;
Вѕ символів пропозиційних зв'язок? і В¬
Вѕ кванторного символу ? (квантор загальності);
Вѕ службових символів: дужок закриває) і відкриває (, а також символу коми ,.
2) введено поняття формули;
) задані аксіоми числення висловів:
A? (B? A) (A1)
(A? (B? C))? ((A? B)? (A? C)) (A2)
(В¬ B? В¬ A)? ((В¬ B? A)? B) (A3)
і кванторниесхеми аксіом:
? xA? A (x: = t) в умовах (A4)
? x (A? B)? (A? ? xB) в умовах (A5)
) задані правила виведення:
Вѕ modus ponens:
якщо виведені формули A і A? B, то виведена формула B.
Вѕ правилом узагальнення (Gen):
якщо виведена формула A, то виведена формула ? xA .
загальнозначуща для кожного Хa Г A (x: = t)
Теорема. Якщо терм t вільний для змінної x у формулі A, то формула
