Конверський А. Є. Логіка (традиційна та сучасна)

Подождите немного. Документ загружается.

Книга друга. СУЧАСНА ЛОГІКА

421

із того, що одна із них тотожно-істинна слідує, що і

друга теж тотожно-істинна».

Дійсно, нехай А* і В* – дедуктивно еквівалентні фор-

мули і А* – тотожно-істинна формула. А правила чис-

лення такі, що забезпечують отримання тотожно-істинних

формул із тотожно-істинних формул.

Завдяки дедуктивній еквівалентності В* вивідна із аксі-

ом числення предикатів і формули А*. А це означає, що

В* є тотожно-істинною формулою.

Окрім того, якщо А* і В* дедуктивно еквівалентні і А* –

вивідна формула в численні предикатів, В* також є ви-

відною формулою.

Отже, проблема повноти числення предикатів у широ-

кому смислі розв’язується позитивно.

Розглядом металогічних принципів завершується зна-

йомство із побудовою аксіоматичного числення преди-

катів.

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

Поряд із аксіоматичним численням у логіці предикатів

застосовують і такий засіб дослідження, як натуральне чи-

слення або систему натурального висновку.

На відміну від аксіоматичного числення, в якому разом

із деяким необхідним мінімумом правил висновку в числі

вивідних постулатів містяться аксіоми, натуральне чис-

лення містить тільки правила висновку.

Усю множину правил висновку в натуральному

численні предикатів (S

)

поділяють на дві підмно-

жини:

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

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

За цими підмножинами правил зберігаються визначен-

ня, які їм давалися при формулюванні натурального чис-

лення висловлювань.

Тобто, правила першого виду дозволяють із одних вира-

зів виводити нові вирази, а правила другого виду регламе-

нтують виведення із тверджень про логічне слідування но-

вих тверджень про логічне слідування.

Натуральне числення логіки предикатів позначають символом S

А. Є. Конверський. ЛОГІКА

422

Прямі правила висновку у S

()

;

ВК

∧

()

;, 1УК

BA∧

()

;, 2УК

BA∧

()

;ЗК

∨

∧

()

;, 1ВД

∨

()

;, 2ВД

∨

()

1УД

ABA∨

()

2УД

BBA∨

()

;ЗД

∧

∨

()

1УІ

ABA ⊃

()

2УІ

BBA ⊃

()

;ЗІ

∧

⊃

()

;

ВЕ

ABBA ⊃⊃

()

1УЕ

⊃

()

2УЕ

⊃

()

;ВЗП

()

;УЗП

()

;∀

∃

∀

XAx

xxA

()

;∃

∀

∃

xAx

xxA

()

;

...,,,

...,,,/

∀

γγαα

де β – абс. обм.,

γγ ...,,

– обм.

()

;

∀

αα∀

()

;

∃

αα∃

()

;

...,,,/

...,,,

∃

γγβα

∃

де β – абс. обм.,

γγ ...,,

– обм.

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

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

деякі пояснення до кванторних правил висновку.

Це, перш за все, стосується виразу А(α / t) і його част-

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

А(α /β

,..., γ

Книга друга. СУЧАСНА ЛОГІКА

423

Під виразом А(α / t) мається на увазі результат прави-

льної підстановки у формулу А(α) замість усіх вільних

входжень предметної змінної α терму t.

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

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

∃ у (х < у ∧ х = z).

У цій формулі змінна х має два вільних входження. За-

мість х будемо підставляти один із таких термів: «5» або

«z» або (x+z)

•

Внаслідок підстановки вираз А(х / t) у кожному конк-

ретному випадку приймає вигляд:

1. ∃у (5< у ∧ 5 = z) – x / 5

2. ∃y (z < y ∧ z = z) – x / z

3. ∃y ((x + z) • 5 < y ∧ (x + z) • 5 = z) – x / (x + z)•5.

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

льно. Оскільки жодна змінна, яка входить у терм t, не

стала зв’язаною на місцях, де з’явився в результаті підста-

новки терм t.

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

них наслідків.

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

∃у (х < у ∧ х = z).

За семантичною типологією виразів логіки предикатів

даний вираз є виконуваним. Приймемо за область визна-

чення для змінних, що входять в даний вираз, універсум

натуральних чисел.

При х / у+2 отримаємо:

∃ у (у′ + 2 < у ∧ у′ + 2) = z.

Оскільки терм t містить змінну у, то після підстановки

вона виявилася зв’язаною ∃ на тих місцях, де t з’явився у

результаті підстановки. Графічно це зображено штрихом.

З точки зору семантики даний вираз є тотожно-хибним.

Дійсно, які б значення не вибиралися для індивідних

змінних із множини натуральних чисел, вираз х + 2 < у

ніколи не буде істинним. А це означає, що вся кон’юнкція

буде завжди хибною.

Отже, ми порушили правило підстановки, яке (як і всі

правила висновку) гарантує отримання із істинних твер-

джень знову ж таки істинні твердження.

А. Є. Конверський. ЛОГІКА

424

Щодо виразу А(α / β

..., γ

, який фігурує в правилах

В∀ і У∃, то він є метамовним записом часткового випадку

результату правильної підстановки у вираз А(α / β

,...,γ

замість усіх вільних входжень індивідної змінної α і інди-

відної змінної β.

Тепер опишемо правила У∀ і В∃.

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

формули

∀α А(α) до формули А(α / t).

Щоб здійснити цей перехід, необхідно усунути ∀, а в

залишковій формулі А(α) зробити правильну підстанов-

ку замість α терму t. Оскільки в А(α) можуть входити

квантори, то необхідно бути уважними, здійснюючи

процедуру підстановки.

Наприклад, маємо вираз ∀х ∃ у (х < у).

Якщо за область визначення для змінних х і у береться

множина натуральних чисел, то даний вираз cтверджує

про відсутність найбільшого числа. За значенням цей ви-

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

отримаємо із цього істинного твердження хибне:

∃ у (у < у).

Тут терм у виявився зв’язаним ∃ на тому місці, де він

був підставлений замість х.

Правило введення квантору існування дозволяє пере-

йти від формули

А(α / t) до формули ∃ α А(α).

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

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

висновок.

Візьмемо предикат «6 < у». Якщо невірно застосуємо

правило В∃, то отримаємо хибне твердження: ∃у (у < у).

Що ж тут насправді відбулося? Справа в тому, що у

цьому застосуванні В∃ предикат 6 < у трактувався як ніби-

то результат вірної підстановки терму 6 замість змінної у.

Але результатом такої підстановки повинен бути вираз 6 <

6, а не 6 < у, оскільки підстановка завжди здійснюється

замість всіх входжень вільної індивідної змінної.

Отже, вираз 6 < у не можна розуміти як А(у / 6), а тому

перехід до ∃у А(у) невірний.

Книга друга. СУЧАСНА ЛОГІКА

425

З іншого боку 6 < у можна розуміти як А(х / 6), як ре-

зультат тепер вірної підстановки у х < у замість всіх віль-

них входжень змінної х терму 6. У цьому випадку ми

отримаємо ∃ х (х < у).

При записі правил В∀ і У∃ фігурує додаткова інформація у

вигляді скорочених вказівок: «β – абс. обм.; γ

,..., γ

–

обм.». Розглянемо смисл цієї інформації.

З семантичної точки зору змінні трактуються як такі,

що пробігають по деякій предметній області і набувають

тут будь-яких значень. Саме в цьому полягає основна суть

вільних змінних. Але в складі формул вільні змінні не

завжди виконують цю роль, тобто не завжди розглядають-

ся як знаки, що можуть позначати будь-який (довільний)

об’єкт області визначення. Тут можливі варіанти.

У тому випадку, коли вільна предметна змінна в

складі формули позначає будь-який об’єкт із універсуму

розгляду, вважається, що вона застосована в цій фор-

мулі в інтерпретації всезагальності.

Наприклад, у виразі «х • у = у • х» змінні у і х вжи-

ваються в інтерпретації всезагальності, оскільки їх спі-

відношення при будь-яких значеннях х і у буде істинним.

У тому випадку, коли твердження справедливе для

якогось (фіксованого), можливо і невідомого предмета із

області значень х, то маємо умовну інтерпретацію.

Так, наприклад, у виразі 3х + 6 = 0 змінна х уже не

використовується у інтерпретації всезагальності, так як не

позначає довільний об’єкт із універсуму. Навпаки, можли-

ві значення для х суворо фіксовані, тобто обмежені умовою

даного твердження. А це значить, що х використана в

умовній інтерпретації.

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

У виразі х + 6 < у нехай х і у взяті в умовній інтер-

претації.

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

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

для у.

Дійсно, змінна у не може тепер прийняти в якості зна-

чень числа, менші ніж 9. Але вибір числа 2 як значення х

довільний. Нам нічого не заважало б вибрати в якості зна-

чення для х число 23. Цей вибір відразу ж по-новому об-

межить множину можливих значень для у. Тепер значен-

ням для у повинно бути число, не менше як 30.

А. Є. Конверський. ЛОГІКА

426

Отже, у випадку умовної інтерпретації змінних ви-

бір значення для однієї змінної обмежує вибір значення

для інших вільних змінних, які входять у конкретний

вираз.

Проілюструємо правила В∀ і У∃.

Відповідно до правила У∃ дозволяється перехід від фор-

мули ∃α (α

,..., γn) до формули А (α / β

,..., γ

Зрозуміло, цей перехід регламентується вимогами пра-

вильної підстановки.

Засновок даного правила ∃α А (α

,..., γ

) стверджує,

що в універсумі розгляду існує деякий об’єкт, що задово-

льняє вимозі А (α / γ

,..., γ

Тоді правило У∃ дозволяє вважати цим об’єктом пред-

мет, що позначається змінною β. Буквально це звучить

так:

«Якщо існує предмет, що задовольняє умові А, то

нехай ним буде предмет β». Цим самим здійснюється та-

кий вибір значення для β, що предикат А (β

,...,γ

) стає

істинним висловлюванням.

У цьому випадку β береться в умовній інтерпретації, а

це означає, що вона абсолютно обмежена, тобто виступає

іменем якогось чітко визначеного предмета, що задоволь-

няє умові А (β

, ..., γ

Але цим самим вибір значення для β обмежує можли-

вість вибору значення для решти вільних змінних γ

,...,γ

Саме ця інформація і фіксується у правилі усунення кван-

тора існування вказівкою на те, що β – абсолютно об-

межена змінна (абс.обм.), а γ

,...,γ

– обмежені змінні

(обм.)

. При цьому в правилі У∃ змінні γ

,...,γ

– це вільні

змінні, які входять у вираз ∃ α А (α, γ

,...,γ

Проілюструємо дію У∃ на прикладі.

Маємо вираз: ∃ х (х + 6 = 9).

Цей вираз стверджує про наявність у множині натура-

льних чисел такого числа, яке задовольняє умові х + 6 =

= 9.

Припустимо, що таким числом буде значення змінної у.

У цьому випадку відповідно до правила У∃ отримаємо ви-

раз у + 6 = 9, де у є обсолютно обмеженою змінною, оскі-

Тут необхідно зробити зауваження. Коли вживається термін «абсолютно об-

межена змінна», то не у розумінні «неповноцінна», а обмежена у розумінні ви-

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

межити предметні змінну – це означає визначити для неї характер інтерпретації.

Книга друга. СУЧАСНА ЛОГІКА

427

льки у позначає тепер вибраний об’єкт із універсуму (у да-

ному випадку він єдиний).

Розглянемо ще такий вираз: ∃ х (х + 6 < у).

Вибиремо у множині натуральних чисел предмет, який

задовольняє умові х + 6 < у. Що такий об’єкт є, свідчить

висловлювання

∃ х (х + 6 < у).

Нехай таким об’єктом буде предмет, позначений індиві-

дною змінною х. Застосовуючи тепер правило У∃, отрима-

ємо вираз:

х + 6 < у,

де змінна х абсолютно обмежена, змінна у відносно об-

межена, або просто обмежена.

Подібну інформацію несе і вираз «β – абс. обм.; γ

,..., γ

–

обм.», який є приміткою до правила В∀.

Суть цього правила полягає в дозволі переходу від

виразу

А (α / β

,..., γ

) до ∀α А (α

,..., γ

Прокоментуємо цей перехід.

У даному випадку є дві можливості.

Вираз А (β / α, γ

,..., γ

) може, по-перше, при деяких фі-

ксованих значеннях γ

, ..., γ

приймати значення «істина»

на певній області визначення при будь-яких значеннях β.

Іншими словами, змінна β при відповідних фіксованих

значеннях γ

, ..., γ

входить у вираз А (β

, ..., γ

) в інтер-

претації всезагальності.

У даному випадку перехід від цього виразу за правилом

В∀ до виразу ∀α А(α

, ..., γ

) є цілком правомірним.

По-друге, вираз А (β

, ..., γ

) може виявитися і таким,

що при певних фіксованих значеннях γ

, ..., γ

на відповід-

ній області міркувань буде при деяких значеннях β при-

ймати валентність «хибa».

Тоді виберемо це значення для β. Внаслідок цього β стає аб-

солютно обмеженою змінною, а решта вільних змінних –

обмеженими.

Зрозуміло, що вираз А (β

,..., γ

) при такому виборі

значень для змінних буде хибним. Але з хибного вислов-

лювання слідує все, що завгодно. Тому правомірним є ви-

раз ∀α (α

,..., γ

А. Є. Конверський. ЛОГІКА

428

Після того, як ми виписали прямі правила висновку в

з їх короткою характеристикою, ознайомимося з не-

прямими правилами висновку S

До непрямих правил висновку S

відносять:

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

BAГ

BАГ

⊃

−

;

б) правило введення заперечення, або правило спрос-

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

AГ

BBАГ

;

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

AГ

BBАГ

−

Окрім правил висновку дедуктика, або дедуктивна логі-

ка S

, включає в себе низку дефініцій:

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

«Висновком в S

називається непорожня кінцева по-

слідовність формул С

,..., С

, яка задовольняє таким

вимогам:

а) кожна С

є або засновок, або отримана із попере-

дніх формул за правилами висновку;

б) якщо у висновку застосовувалися правила ВІ або

ВЗ, то всі формули, починаючи з останнього засновку

аж до результату застосування даного правила, ви-

ключаються із подальших кроків побудови висновку

;

Властивість «виключеності» деяких формул із подальшої побудови вис-

новку означає, що до даних формул у подальших кроках уже не можна більше

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

будови висновку. У подальшому такі формули будемо називати виключеними

формулами, або виключеними засновками. Той факт, що деякі засновки є вик-

люченими, при запису висновка графічно позначають вертикальною рискою.

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

Нехай потрібно обгрунтувати метатвердження про вивідність формули R із

засновків P ⊃ Q, Q ⊃ R i P.

Книга друга. СУЧАСНА ЛОГІКА

429

в) жодна індивідна змінна у висновку не обмежується

абсолютно більше одного разу;

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

себе».

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

співпадала б з формулою R, а засновками були б формули – P

⊃

Q, Q

⊃

R i P.

Тобто, йдеться про таку послідовність:

1. P

⊃

Q – засновок

2 Q

⊃

R – засновок

3. P – засновок

4. Q – УІ до 1,3

5. R – УІ до 2,4

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

графічно з R, а формули P ⊃ Q, Q ⊃ R i P є невиключеними засновками. Цим

самим побудовано висновок, який обгрунтовує метатвердження про вивідність

|− P ⊃ Q, Q ⊃ R, P |− R.

Розглянемо ще одне метатвердження: |− (P ⊃ Q) ⊃ ((Q ⊃ R) ⊃ (P ⊃ R)).

Це метатвердження фіксує той факт, що формула, яка стоїть справа від знака |−,

є теоремою. Побудуємо послідовність, яка обгрунтовує дане метатвердження.

1. P

⊃

Q – засновок

2. Q

⊃

R – засновок

3. P – засновок

4 Q – УІ, до 1, 3

5. R – УІ, до 2, 4

6. P

⊃

R – ВІ, до 3, 5

7. (Q

⊃

R) – ВІ, до 2, 6

8. (P

⊃

((Q

⊃

R)) – ВІ, до 1, 7.

Отже, оскільки рядок 8 послідовності графічно співпадає із тією формулою,

яку потрібно було отримати, то ми маємо висновок. Окрім того, усі засновки

включені, тому множина невиключених засновків порожня. У зв’язку з цим дана

послідовність згідно з дефініцією доведення є доведенням формули

(P ⊃ Q) ⊃ ((Q ⊃ R) ⊃ (P ⊃ R)),

тобто дана формула є теоремою.

Якщо порівняти дану послідовність із попередньою, то легко побачити подіб-

ність їх п’яти кроків. Коли ми призупинили доведення формули (P ⊃ Q) ⊃ ((Q ⊃ R) ⊃

⊃ (P ⊃ R)) на п’ятому кроці , то мали б вивідність вигляду (P ⊃ Q), (Q ⊃ R),

P |− R. Однак, побудова послідовності була продовжена 6-м кроком. На 6-му

кроці було застосовано правило ВІ до 3,5 рядків. Відповідно до цього правила

дозволяється отримати формулу P ⊃ R , де Р – останній засновок, а R – 5-та

формула. Саме ця формула і записана на 6-му кроці.

У дефініції висновку зазначено, що при застосуванні правила ВІ із подаль-

ших кроків висновку виключаються усі формули, починаючи із останнього за-

сновку аж до результату застосування цього правила, тобто, у нашому випадку з

3-ї до 6-ї формули. Якщо висновок був би обірваний на 6-му кроці, то цим самим

була б обгрунтована вивідність такого роду: P ⊃ Q, Q ⊃ R |− P ⊃ R. Але оскільки

процес виведення був продовжений у результаті застосування правила ВІ до 6-го

кроку, то на 7-му кроці була отримана формула (Q

⊃

R) і внаслідок

цього були виключені рядки з 2-го по 7-й.

Якщо б виведення закінчилося на 7-му кроці, то була б обгрунтована

вивідність (P ⊃ Q) |− ((Q ⊃ R) ⊃ (P ⊃ R)). Застосувавши до 7-го кроку правило ВІ,

отримуємо на 8-му кроці обгрунтування вивідності із порожньої множини

засновків формули (P ⊃ Q) |− ((Q ⊃ R) ⊃ (P ⊃ R)).

А. Є. Конверський. ЛОГІКА

430

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

«Доведенням у S

є висновок із порожньої множини не

виключених засновків».

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

«Завершеним називається висновок у якому ніяка

змінна, що абсолютно обмежувалася у процесі висновку,

не зустрічається вільно ні у не виключених засновках,

ні у наслідку».

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

«Завершеним доведенням у численні предикатів є за-

вершений висновок із порожньої множини не виключених

засновків».

Якщо проаналізувати чотири наведені дефініції, то оче-

видно, що основною є дефініція висновку.

Порівняно з поняттям висновку в численні висловлю-

вань у S

поняття висновку збагачується ще двома ви-

могами.

Перша вимога зводиться до того, що позначка про аб-

солютну обмеженість деякої змінної означає, що в процесі

побудови висновку вона стає знаком якогось конкретного

предмета, а тому друге її абсолютне обмеження може вка-

зувати на те, що вона стала знаком якогось іншого пред-

мета. Така ситуація повинна бути заборонена, оскільки во-

на веде до протиріччя.

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

міркуваннями. В основі кванторних правил У∀ і В∃ ле-

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

Іншими словами, для У∀ це означає, що перехід від фо-

рмули ∀α А(α) до А(α / t) виправданий відношенням логі-

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

∀α А(α) |= А(α / t),

а для В∃ перехід від А(α / t) до ∃α

(α) виправданий від-

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

А(α / t) |= ∃α

(α).

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

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

Тут ми зупинимося на особливості правил В

∃

і У

∀

більш детально, ніж у

§ 2 цього розділу.