Аксіоматичне числення предикатів

Аксіоматичне числення логіки предикатів — це така формально-логічна теорія, яка є розширенням числення висловлювань.

Мається на увазі, що аксіоми S² і правила висновку ак­сіоматичного числення висловлювань зберігаються в аксі­оматичному численні предикатів.

До аксіом S⁵ відносяться такі вирази:

Із переліку аксіом очевидно, що до списку аксіом S⁵ включаються всі 11 аксіом S² і до них додаються ще дві аксіоми 12 і 13, де F(x) — будь-яка формула логіки преди­катів, в якій маються вільні входження предметної змінної х і одне із цих входжень знаходиться в області дії кванто­ра по предметній змінній у, а формула F(y), отримана із F(x), заміною всіх вільних входжень х на у.

Метабукви А, В, С у записі аксіомних схем представля­ють будь-яку формулу логіки предикатів.

Наприклад, аксіому 1 можна записати мовою логіки предикатів таким чином:

Окрім цього правила тут застосовуються правила введення і усунення кванторів, на яких ми зараз і зупинимося.

Але перш ніж сформулювати ці правила, дамо деякі по­яснення. Введемо поняття «правильної підстановки».

Під правильною підстановкою розуміють таку під­становку, у результаті якої із істинних формул отри­мують тільки істинні формули.

Щоб досягти цієї мети, необхідно дотримуватися таких вимог:

а) вираз, який підставляють, повинен належати до тієї самої предметної області, на якій визначена змінна х.

Наприклад, не можна у вираз «Існує х, який є ровесни­ком у» замість змінної у підставляти ім’я предмета із об­ласті хімічних елементів;

б) підстановка значень замість змінної х можлива лише там, де вона вільна.

Неможливо, наприклад, у виразі «Для будь-якого х, як­що х — планета, то х має природний супутник» зв’язану змінну х замінити іменем конкретної планети. Порушення цієї вимоги веде до нісенітниці. Для прикладу замість х візьмемо ім’я «Юпітер». Отримаємо вираз «Для будь-якого Юпітера», який не має смислу;

в) підстановка деякого значення замість вільної змін­ної х здійснюється скрізь, де зустрічається змінна х у даному виразі;

г) в результаті підстановки жодна вільна змінна не повинна виявитися зв’язаною^[XLII].

Пояснимо це на прикладах.

Нехай вираз ∃x R(x,y) означає фразу «Існує ціле число х, яке не дорівнює довільному числу у».

Це висловлювання буде залишатися істинним при будь- якій підстановці, окрім випадку, коли замість змінної у підставимо зв’язану предметну змінну х:

Отримаємо недоречне висловлювання. «Існує таке ціле число х, яке не дорівнює самому собі».

Або ж візьмемо цю формулу, але R буде представляти двомісний предикатор «батько», а х і у змінні, які визна­чені на області людей. Формуле _x _ _r буде представля­ти істинне висловлювання до тих пір, поки замість вільної змінної у не підставимо зв’язану змінну х. Така підстанов­ка приводить до недоречного висловлювання: «Існує люди­на, яка є батьком самого себе».

Після цих зауважень перейдемо до формулювання пра­вил введення і усунення кванторів.

Правило усунення квантора загальності (Y∀):

Буквально це правило означає, що якщо всі предмети універсуму міркування мають певну ознаку, то з цього можна зробити висновок, що будь-який довільний або ви­значений предмет даної області має цю ознаку.

Суть цього правила полягає в тому, що якщо із деяких засновків і додаткових припущень А із зв’язаною змінною

408

А.

х виводиться пропозиційна функція (предикат) В(х), то із А виводиться Ух В(х).

Іншими словами, якщо в процесі виведення отримує­мо твердження про те, що довільний предмет із якоїсь області має певну ознаку, то можна стверджувати, що всі предмети цієї області мають цю ознаку.

Зауважимо, що правило (ВУ) застосовується лише в то­му випадку, коли х в А є зв’язаною змінною. У тому випа­дку, коли х не зв’язана в А, то В(х), будучи виведеною із А, перетвориться в істинне висловлювання лише для тих зна­чень х, для яких А — істинне. Однак такою властивістю можуть володіти не всі значення змінної х і пропозиційна функція В(х) не буде перетворюватися в істинне висловлю­вання для довільного значення змінної х. У цьому випадку висловлювання Ух В(х) виявиться хибним.

Правило введення квантора існування (ВЗ):

Із цього правила випливає, якщо будь-який довільно взятий або визначений предмет має якусь ознаку, то це означає, що існує, в крайньому разі, один предмет, який має цю ознаку.

Правило усунення квантора існування (УЗ):

Інша ситуація для правил (BV) і (УЗ). В їх основі відсу­тнє відношення логічного слідування. Не зважаючи на це, у численні логіки предикатів ці правила все ж таки є при­йнятними.

Але щоб не допустити можливості виведення із іс­тинних засновків хибних висновків, необхідно дотриму­ватися двох формальних вимог:

1) Перша формальна вимога полягає в тому, що жо­дна індивідна змінна не обмежує себе у висновку.

Наприклад, дана вимога дозволяє виключити переходи такого виду:

тобто переходи від істинних (виконуваних) тверджень до хибних.

2) Друга формальна вимога полягає в розрізненні по­няття висновку і поняття завершеного висновку.

Тільки при здійсненні завершеного висновку гаранту­ється, що між засновками і висновком має місце відно­шення логічного слідування.

Правило перейменування вільних змінних:

«Якщо формула числення предикатів А(х) містить вільні входження предметної змінної х і жодне із цих входжень не міститься в області дії квантора по пред­метній змінній у, то із |- А(х) слідує |- А(у), де А(у) — отримана змінною в А(х) всіх вільних входжень х на у».

Правило перейменування зв’язаних змінних:

«Якщо формула числення предикатів А(х) не міс­тить вільних входжень предметної змінної у і містить вільні входження предметної змінної х, ні одне із яких не знаходиться в області дії квантора по змінній у, то із |- σ х А(х) слідує |- σ у А(у), де σ — будь-який із кван­торів V,?, а формула А(у) отримана із А(х) заміною всіх вільних входжень х на у».

Дамо визначення процедури доведення і доведеної фор­мули.

Дефініція доведення.

«Доведенням формули В називається послідовність формул В₁, В₂,... В_п, в якій В_п = В і кожна із формул по­слідовності B_i (і = 1,..., n.) є або аксіомою, або отрима­ною за яким-небудь із правил висновку з попередніх фо­рмул». При цьому число n називається довжиною дове­дення.

Дефініція доказової формули.

«Формула В у численні предикатів називається дока­зовою, або теоремою, якщо для неї існує доведення».

Зауважимо, що множина всіх доказових формул у чис­ленні предикатів не розшириться, якщо при побудові дове­дення ми будемо використовувати не тільки аксіоми, а й будь-які доказові формули. Врахування цього факту часто дозволяє значно спрощувати доведення формул. Цій же меті слугують багато допоміжних правил висновку.

Побудуємо доведення формул логіки предикатів.

Доведення.

2.