СЕМАНТИКА ЛОГІКИ ПРЕДИКАТІВ

Під семантикою мови логіки предикатів маються на увазі правила перекладу термів і формул цієї мови на змістовний, наприклад російський, мовою або іншою формальну мову. Завдяки такому перекладу термам ставляться у відповідність певні об'єкти предметної області, а формулами ставляться у відповідність твердження про об'єкти предметної області. Тим самим з'ясовується, які формули формального мови логіки предикатів відповідають дійсним твердженнями, а які формули - хибним твердженням про об'єкти предметної області.

Деякі теореми логіки предикатів, що грають в ній важливу роль, називають законами логіки предикатів. Ясно, що законами логіки предикатів є перераховані вище закони I-VIII логіки висловлювань. Доповнимо їх тими законами логіки предикатів, які дозволяють все квантори довільної формули виносити в початок цієї формули.

IX. И ^ Л (х))) МЕх (-Л (*))),

M3xrf (x))) - (Vx (-u4 (*))).

X. ((Vx4 (x)) v *) «(Vy (/ l (y) v *)),

• ((3xA (x)) vB) = (3y (A (y) vS)),
• ((VxA (х)) ЛВ) = (Vy (А (у) ЛВ)),
• ((Луни (х)) ЛВ) = (Еу (А (у) ЛВ)).

Тут вважається, що змінна у не міститься у формулі В.

XI. ((VxA (х)) v (VxB (х))) = (VxVy (A (x) vB (у))), де змінна у не міститься ні в формулі А (х), ні у формулі В (х) ,

• ((Луни (х)) v (ЕхВ (х))) = (Ех (A (x) vB (х))),
• ((VxA (х)) л (VxB (х))) s (Vx (А (х) ЛВ (х))),
• ((Ех / 1 (х)) л (ЕхВ (х))) = (ехе у (А (х) ЛВ (у))), де змінна у не міститься ні в формулі А (х), ні у формулі В (х).

Ці закони дозволяють будь-яку формулу логіки предикатів перетворити до наступного вигляду:

де будь-який Q, - це або квантор спільності, або квантор існування, a F (х |, х ₂ , ..., х ") - формула, що не містить кванторів. У формулі такого виду можна введенням сколемовскіх констант і функції видалити всі квантори існування. При цьому слід користуватися наступними законами логіки предикатів:

XII. (Ех) (0, у,) ... (Q _m y _m ) F (y _{ , y ₂ , ..., y _m ) = (Q _f y _i ) ... (Q _m y _m ) F (a, y _l , ..., у, "), де 0 ,, ..., Q," - довільні квантори, а символ константи а вводиться в алфавіт як саме тієї константи, яка існує у відповідності з виразом ( Ех), що стоять на початку формули; константу а називають сколемовской константою.

XIII. (Vx,) (Vx ₂ ) ... (Vx *) (Еу) (C?, Z,) ... (Q, "z _m ) F (x _u x ₂ , ..., x _k , y , zj =

= (Vx,) (Vx ₂ ) ... (Vx *) (Q _X Z). ~ (Q _m z ") F (x _b x ₂ , ..., x *, / (x" x ₂ , ..., x _k ), z _u ..., zj, де Q i, ..., Q, " - довільні квантори, а ^ місний функціональний символ / вводиться в алфавіт як саме того функціонального символу, який позначає функцію, відповідну висловом (Vx,) (Vx ₂ ) ... (Vx *) (Еу), що стоїть на початку формули; цю функцію / (х ,, х ₂ , ..., х *) називають сколемовской функцією.

XIV. ЕхЖх) = А (а), де а - сколемовская константа.

Закони XI-XIV забезпечують перетворення будь-якої формули логіки предикатів до сколемовской формі. Так називають формулу виду Vx, Vx ₂ ... Vx "A, в якій формула А взагалі не містить кванторів, а містить змінні, константи, сколемовскіе константи і сколемовскіе функції. Сколемовская форма VX] Vx ₂ ... Vx ", 4, в якій формула А є КНФ, називається клаузальной формою. Клаузальная форма має наступний загальний вид:

Тут D _h D ₂ , ..., D _m - диз'юнкт, які називають Клаузен, або пропозиціями.

Приклад. перетворимо формулу

Vx ((Л (х) л-! Fi (x)) -> 3_у (С (х, у) ЛД (у))) в клаузальную форму.

• 1. Vx (-i (/ l (х) л-, й (х)) лЗу (С (х, у) Ло (у))) виходить за допомогою теореми (wi-> w ₂ ) = (-1 т ^ / т ₂ ).
• 2. Vx ((- ^ 4 (x) v- ₁ -i5 (x)) v3> '(С (х, y) / D (y))) випливає з закону подвійності для кон'юнкції.
• 3. Vx (- ^ 4 (x) v5 (x) v3y (С (х, y) / D (y))) випливає із закону подвійного заперечення.
• 4. Vx3z (-v4 (x) v? (X) v (C (x, z) aD (z))) випливає із закону X.
• 5. Vx (- ^ 4 (x) vfi (x) v (C (x, / (x)) A /) (/ '(x)))) випливає з закону XIII,

тут / (х) - сколемовская функція. Ця формула є сколемов- ської формою.

6. Vx ((-i / l (x) vi? (X) vC (x, / (x))) л (-'4 (x) vfi (x) v /) (/ '(x)))) випливає з закону дистрибутивности. Ця формула є клаузальной формою.

Саме клаузальние форми використовуються в мові логічного програмування PROLOG для представлення знань і міркувань. Клауз в цій мові, перш ніж будуть представлені у формі прологовскіх пропозицій, перетворюються в хорновскіе пропозиції. Хорновскіе пропозиції - це клауз, що не містять позитивних членів взагалі або містять тільки один позитивний член. Хорновскіе пропозиції (диз'юнкт, клауз) мають одні з наступних трьох видів:

• -iH, v-u4 ₂ v ... v-iA "vA - правило,
• -u4, vi / 1 ₂ v ... zA "- питання,

А - факт.

Ці види хорновскіх пропозицій на мові PROLOG записуються в формі відповідно:

Характеризуючи числення предикатів в цілому, відзначимо, що ця формальна система є несуперечливої і нерозв'язною. Що стосується повноти, то для логіки предикатів справедлива наступна теорема.

Теорема Геделя про повноту. У численні предикатів першого порядку всі теореми є тавтологія.

Це означає, що в численні предикатів першого порядку всі теореми є істинними у всіх інтерпретаціях.