Натуральне числення предикатів

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

На відміну від аксіоматичного числення, в якому разом із деяким необхідним мінімумом правил висновку в числі вивідних постулатів містяться аксіоми, натуральне чис­лення містить тільки правила висновку.

Усю множину правил висновку в натуральному численні предикатів (S⁶) ^[XLV] поділяють на дві підмно- жини:

1) прямі правила і

2) непрямі правила.

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

Тобто, правила першого виду дозволяють із одних вира­зів виводити нові вирази, а правила другого виду регламе­нтують виведення із тверджень про логічне слідування но­вих тверджень про логічне слідування.

Правила введення пропозиційних зв’язок зрозумілі із тих пояснень, які давалися у попередніх розділах. Дамо деякі пояснення до кванторних правил висновку.

Це, перш за все, стосується виразуі його част­

кового випадку

Під виразом A(α I t) мається на увазі результат прави­льної підстановки у формулу A(α) замість усіх вільних входжень предметної змінної α терму t.

Звернемося до прикладу.

Нехай А(х) представляє формулу:

У цій формулі змінна х має два вільних входження. За­мість х будемо підставляти один із таких термів: «5» або «z» або (x+z) • 5.

Внаслідок підстановки вираз А(х / t) у кожному конк­ретному випадку приймає вигляд:

В усіх трьох випадках ми здіснили підстановку прави­льно.

Порушення цієї вимоги веде до некоректних семантич­них наслідків.

Візьмемо той самий вираз:

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

Оскільки терм t містить змінну у, то після підстановки вона виявилася зв’язаною ∃ на тих місцях, де t з’явився у результаті підстановки. Графічно це зображено штрихом.

З точки зору семантики даний вираз є тотожно-хибним. Дійсно, які б значення не вибиралися для індивідних змінних із множини натуральних чисел, вираз х + 2 < у ніколи не буде істинним. А це означає, що вся кон’юнкція буде завжди хибною.

Отже, ми порушили правило підстановки, яке (як і всі правила висновку) гарантує отримання із істинних твер­джень знову ж таки істинні твердження.

Щодо виразуякий фігурує в правилах

то він є метамовним записом часткового випадку результату правильної підстановки у вираз замість усіх вільних входжень індивідної змінної α і інди- відної змінної β.

Тепер опишемо правила

Правило y∀ представляє собою дозвіл перейти від формули

Щоб здійснити цей перехід, необхідно усунути ∀, а в залишковій формулі А(а) зробити правильну підстанов­ку замість α терму t. Оскільки в А(а) можуть входити квантори, то необхідно бути уважними, здійснюючи процедуру підстановки.

Наприклад, маємо вираз

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

Тут терм у виявився зв’язаним З на тому місці, де він був підставлений замість х.

Правило введення квантору існування дозволяє пере­йти від формули

Тут також необхідно дотримуватися вимог правильної підстановки. У протилежному випадку матимемо хибний висновок.

Візьмемо предикат «6 < у». Якщо невірно застосуємо правило ВЗ, то отримаємо хибне твердження: ^_

Що ж тут насправді відбулося? Справа в тому, що у цьому застосуванніпредикат 6 < у трактувався як ніби­то результат вірної підстановки терму 6 замість змінної у. Але результатом такої підстановки повинен бути вираз 6 < 6, а не 6 < у, оскільки підстановка завжди здійснюється замість всіх входжень вільної індивідної змінної.

Отже, вираз 6 < у не можна розуміти як А(у / 6), а тому перехід до Зу А(у) невірний.

424

А. Є. Конверський. Логіка

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

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

Наприклад, у виразі «х • у = у • х» змінні у і х вжи­ваються в інтерпретації всезагальності, оскільки їх спі- відношення при будь-яких значеннях х і у буде істинним.

У тому випадку, коли твердження справедливе для якогось (фіксованого), можливо і невідомого предмета із області значень х, то маємо умовну інтерпретацію.

Так, наприклад, у виразі 3х + 6 = 0 змінна х уже не використовується у інтерпретації всезагальності, так як не позначає довільний об’єкт із універсуму. Навпаки, можли­ві значення для х суворо фіксовані, тобто обмежені умовою даного твердження. А це значить, що х використана в умовній інтерпретації.

Звернемося ще до прикладу.

У виразі х + 6 < у нехай х і у взяті в умовній інтер­претації.

Виберемо для х значення 2. Вибір цього значення для х відразу ж накладає обмеження на вибір можливих значень для у.

Дійсно, змінна у не може тепер прийняти в якості зна­чень числа, менші ніж 9. Але вибір числа 2 як значення х довільний. Нам нічого не заважало б вибрати в якості зна­чення для х число 23. Цей вибір відразу ж по-новому об­межить множину можливих значень для у. Тепер значен­ням для у повинно бути число, не менше як 30.

^[I] Тут необхідно зробити зауваження. Коли вживається термін «абсолютно об­межена змінна», то не у розумінні «неповноцінна», а обмежена у розумінні ви­значення, встановлення межі, відділення одного предмету від іншого. Тобто, об­межити предметні змінну — це означає визначити для неї характер інтерпретації.

Після того, як ми виписали прямі правила висновку в S⁶ з їх короткою характеристикою, ознайомимося з не­прямими правилами висновку S⁶.

До непрямих правил висновку S⁶ відносять:

а) правило введення імплікації (ВІ):

б) правило введення заперечення, або правило спрос­тування «шляхом зведення до абсурду» (ВЗ) або (Зв.А):

в) правило доведення від противного (ДВП):

Окрім правил висновку дедуктика, або дедуктивна логі­ка S⁶, включає в себе низку дефініцій:

1. Дефініція висновку:

«Висновком в S⁶ називається непорожня кінцева по­слідовність формул C₁,..., C_n, яка задовольняє таким вимогам:

а) кожна C_i є або засновок, або отримана із попере­дніх формул за правилами висновку;

б) якщо у висновку застосовувалися правила ВІ або ВЗ, то всі формули, починаючи з останнього засновку аж до результату застосування даного правила, ви­ключаються із подальших кроків побудови висновку¹;

в) жодна індивідна змінна у висновку не обмежується абсолютно більше одного разу;

г) жодна індивідна змінна не обмежує у висновку сама себе».

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

«Доведенням у S⁶ є висновок із порожньої множини не виключених засновків».

3.Дефініція завершеного висновку:

«Завершеним називається висновок у якому ніяка змінна, що абсолютно обмежувалася у процесі висновку, не зустрічається вільно ні у не виключених засновках, ні у наслідку».

4.Дефініція завершеного доведення:

«Завершеним доведенням у численні предикатів є за­вершений висновок із порожньої множини не виключених засновків».

Якщо проаналізувати чотири наведені дефініції, то оче­видно, що основною є дефініція висновку.

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

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

Відносно другої вимоги, то вона пов’язана з такими міркуваннями. В основі кванторних правил ле­

жить відношення логічного слідування¹.

Іншими словами, дляце означає, що перехід від фо­рмуливиправданий відношенням логі­

чного слідування:

а длявиправданий від­

ношенням логічного слідування типу:

Інша ситуація виникає з правиламиоскільки в

їх основі не лежить відношення логічного слідування:

¹ Тут ми зупинимося на особливості правил ВЗ і V∀ більш детально, ніж у § 2 цього розділу.

430

А. Є. Конверський. Логіка

Незважаючи на цю обставину, в численні предикатів все ж таки приймаються ці правила. Але з певними умовами.

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

Це досягається завдяки двом формальним умовам.

Перша формальна умова представлена пунктом г) дефініції висновку.

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

Тут мається на увазі, що відношення «х обмежує у» є транзитивним, тобто для нього вірним є співвідношення: «якщо α обмежує β, а β обмежує γ, то α обмежує у».

Це пояснює ситуацію самообмеження деякої змінної в процесі побудови висновку, скажімо змінної х, таким чи­ном: в одному кроці висновку змінна х, будучи абсолют­но обмеженою, обмежує змінну у, а в другому кроці — змінна у, будучи абсолютно обмеженою, обмежує х. То­ді, згідно з відношенням транзитивності, змінна х буде обме­жувати сама себе.

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

Наявність завершеного висновку гарантує відношення логічного слідування між засновками і наслідком.

Перед тим, як розглянути конкретні варіанти побудови висновку і доведення в S⁶, зупинимося ще на одному пи­танні.

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

Для того, щоб вибір потрібних засновків для побудови висновку не носив випадкового характеру і не був прос­тим перебиранням різних можливостей, необхідно описати деякі способи або прийоми вибору засновків.

Назвемо прийом вибору засновків для побудови про­цедури висновку методикою вибору засновків. Скорочено позначається буквами МЗ. Розглянемо основні з них.

Нехай шляхом побудови висновку необхідно обгрунту­вати метатвердження про вивідність:

Спочатку в якості засновків беремо формули, які стоять до знакаПодальший вибір засновків здійснюється за такими методиками.

Перша МЗ: «Якщо формула, що стоїть після знака |-, є імплікацією, то антецедент даної імплікації береться за засновок, а метою виведення стає консеквент. Тоб­то, до уже вибраних засновків Λ₁, A₂..., A_n додається новий засновок C₁.

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

Якщо побудова висновку відбувається, то, послідовно застосовуючи правило ВІ для виключення додаткових за­сновків, можна отримати обгрунтування даного висновку:

Друга МЗ: «Якщо послідовне застосування першої МЗ привело до формули В як мети побудови висновку, але висновок не вдається побудувати, то необхідно взяти в якості додаткового засновку заперечення формули В;

Метою висновку тепер стає отримання в його складі протиріччя.

Зупинимося на декількох варіантах побудови висновків і доведень в S⁶.

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

Побудуємо висновок для виразу:

На четвертому кроці висновок повинен бути призупине­ний, оскільки послідовність 1—-4 суперечить пункту г) де­фініції висновку. Згідно з цим пунктом жодна змінна не повинна обмежувати сама себе. У нашому прикладі на 3­му кроці z обмежує х, а на 4-му х обмежує z. Тому згідно з відношенням транзитивності виходить, що z обмежує z.

Обійти цю ситуацію неможливо навіть при заміні змін­ної при застосуванні правила УЗ.

Отже, дана вивідність не може бути обгрунтованою.

Побудуємо доведення виразу:

Даний висновок є завершеним доведенням, а тому це іетатвердження є обгрунтованим.

Ця послідовність — завершене доведення, оскільки є єдина х, яка обмежується. На 6-му кроці висновку змінна х не входить вільно в наслідок (множина невиключених засно­вків порожня).

Суть застосування МЗ-4 на 2-му кроці полягала в то­му, що був розглянутий предикат Р(х,у,а), який не мав ви­гляду імплікації, а тому згідно з МЗ-2 для переходу від побудови висновку від протилежного було взято в ролі зас­новку заперечення цієї формули.

Наведені варіанти побудови висновків технічно розкри­вають специфіку натурального числення предикатів порів­няно з аксіоматичним численням.