Page 39 - 6109
P. 39
твердження не каже, що є певна відповідність, а лише стверджує, що є така
відповідність існує. Може виявитись, що “с 1” пов'язана з якимось іншим
константним символом, але ця інформація не надається даним твердженням.
Коли у формулі використовуються квантори узагальнення, сколемізація
стає не такою простою. Наприклад yх(Р(х, у)) переходимо до y Р(h(y), у).
Дія 4. Переміщення квантора узагальнення назовні.
Ця дія дуже проста. Квантор узагальнення переміщується назовні, при
цьому формула зберігає свій попередній зміст. Наприклад,
x(P(x) y(G(y) F(x,y))) перетворюється на xy(P(x) (G(y)
F(x,y))).
Оскільки кожна змінна тепер зв'язана квантором узагальнення ззовні
формули, то квантори узагальнення більше не несуть додаткової інформації.
Отже, можна скоротити формули, опустивши ці квантори. Ми просто мусимо
пам'ятати, що кожна змінна зв'язана кванторами узагальнення, які ми опустили.
Дія 5. Перенесення “” через “”.
Логічна формула повинна бути зведена до особливої форми – нормальної
кон'юнктивної формули, в якій кон'юнкції не з'являються посеред диз'юнкцій.
Для цього існують два правила:
(a b) c дорівнює (a c) (b c),
a (b c) дорівнює (a b) (a c).
Наприклад, фразу P(x) (G(y,x) (F(x) D(x)) можна перетворити на
фразу (P(x) (G(y, x)) (P(x) F(x) D(x)).
Дія 6. Перехід до фраз.
Тепер наша формула є набором атомарних формул, розділених “” або
пов'язаних “”. Якщо не брати до уваги “”, в нас може вийти наступне:
(A B) (C (D E)),
де змінні можуть заміщати складні твердження, але без "" всередині. По-
перше, тепер дужки не потрібні, оскільки для "" вони не мають значення, і
наш вираз еквівалентний до
A B C D E.
По-друге, порядок теж не має значення. По-третє, нам не потрібні і "",
оскільки ми знаємо, що наша формула – це послідовність тверджень, з'єднаних
“”, і останні можна опустити, сказавши, що це є множина {А, В, С, D, Е}.
Кажучи, що це множина, ми наголошуємо на тому, що порядок не суттєвий.
Елементи цієї множини називаються фразами. Отже, будь-яка формула
предикатного числення еквівалентна (в певному розумінні) до множини фраз.
Повернемося до самої фрази. Оскільки елементами фрази є або точні, або
розділені точно “” твердження, то їх загальний вигляд може набувати кого
вигляду:
((F W) X ) (Y Z),
змінні є точними. Тому можна знову перейти до множини розділених
фраз {F, W, X, Y, Z}.
Тепер формула остаточно досягла фразової форми. Підсумуємо дещо.
Отже, фразова форма логіки предикатів задає такий спосіб запису фор-
39