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

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

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

351

Вивідність формули на підставі метатеореми про

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

ражаються у вигляді таких правил:

а) із довільних формул А

,... А

вивідна кожна із цих

формул:

,... А

|− А

де n

≥

б) із довільних формул А

,... А

вивідна кожна форму-

ла, яка є вивідною в S

,... А

|− R (R – вивідна формула в S

);

в) якщо із довільних формул А

,... А

вивідна формула

виду МР, то із них також вивідний і консеквент цього

модусу.

Ці особливості вивідності (дедукції) на підставі метатео-

реми про дедукцію стають очевидними на основі таких се-

мантичних міркувань:

1) Особливість а) виражає властивість рефлексивності

слідування:

«Із засновку випливає він сам» А |= А, так як |= А ⊃ А.

2) Особливість б) виражає властивість істинних (вивід-

них) формул. «Кожна істинна формула розглядається

як консеквент L – ⊃ (логічно істинної імплікації) з до-

вільним антецедентом».

3) Особливість в) фіксується таким способом:

«Якщо із А

,... А

|− В′ і із А

,... А

|− В′ ⊃ В′′,

то |= В′ ⊃ В′′, але це можливо, коли |= В′′».

Перейдемо до доведення метатеореми про дедукцію:

|,...,,

BAAA

⊃−

−

І. В може бути однією із формул А

,... А

1) В = А

2) В = А

3) В = А

– при n

≥

Розглянемо послідовно ці випадки.

1). В = А

,... А

n-1,

− А

,... А

n-1

|− А

⊃ А

Доведення. 1. А ⊃ (В ⊃ А) – А х. 1

2. А

⊃ (А

⊃ А

) – за п/п: А/А

, В/А

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

352

3. |− А

– за умовою

4. |− А

⊃ А

– за МР – 2,3.

2) В = А

,..., А

n-1

, A

|− А

,..., А

n-1

|− А

⊃ А

Доведення. 1. А ⊃ А – теоремa в S

2. А

⊃ А

– за п/п А/А

3. |− А

⊃ А

3). В = А

,..., А

n-1

, A

|− А

,..., А

n-1

|− А

⊃ А

Доведення. 1. А ⊃ (В ⊃ А) – А х. 1

2. А

⊃ (А

⊃ А

) – за п/п А/А

, В/А

3. |− А

– за умовою

4. |− А

⊃ А

– за МР – 2,3.

П. В може бути вивідною формулою в S

−

R):

,..., A

n-1,

, A

|− R

,..., A

n-1

|− A

⊃ R

Цей випадок є очевидним.

Ш. В може бути консеквентом вивідної імплікації:

|− [B′ ∧ (B′ ⊃ B′′)] ⊃ B′′

,..., А

n-1

, A

|− В′′

,..., А

n-1

|− А

⊃ В′

..................................…………

,..., А

n-1

|− А

⊃ (В′ ⊃ В′′)

,..., А

n-1

|− А

⊃ В′′

Доведення.

1. А ⊃ (В ⊃ С) ⊃ ((А ⊃ В) ⊃ (А ⊃ С) – А х. 2

2. А

⊃ (В′ ⊃ В′′) ⊃ ((А

⊃ В′) ⊃

⊃ (А

⊃ В′′) – за п/п А/А

3. |−А

⊃ (В′ ⊃ В′′) – за умовою В/В′, C/В′′

4. (А

⊃ В′) ⊃ (А

⊃ В′′) – за МР – 2,3

5. |− А

⊃ В′ – за умовою.

6. |− А

⊃ В′′ – за МР – 4,5.

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

дукцію показують, що вона описує одну із фундаменталь-

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

353

них властивостей числень, суть якої полягає у тому, що

доведена формула із множини засновків, з’єднуючись че-

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

нацією, теж буде доведеною.

3. Металогічні принципи в S

Властивості розв’язання, несуперечливості, повноти

і незалежності називають металогічними принципами.

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

татеорем.

а) Принцип розв’язання

Аналізуючи принцип розв’язання, зауважимо, що ло-

гічна мова повинна мати процедуру, яка дозволяє ефе-

ктивно, тобто кінцевим числом кроків, установити, чи

є дана формула логічним законом, чи ні.

Особливість принципу розв’язання в аксіоматичному

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

тизації логіки висловлювань головним завданням є систе-

матизація логічних законів. Множина законів задається

тут не у вигляді сукупності, а у вигляді виведення їх із

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

Тобто, в аксіоматичному численні висловлювань розв’я-

зуюча процедура для конкретних формул забезпечуєть-

ся побудовою їх доведення.

Опишемо принцип розв’язання через доведення відпові-

дних метатеорем (скорочено – МТ).

Існує усього чотири метатеореми:

МТ

– |− А ⊃ |= А

– (читається: «якщо А доказане, то тотожно-істинне А»);

МТ

–  |= А ⊃  |− А

– (читається: «якщо А не тотожно-істинне, то

і не доказане А»);

МТ

– |= А ⊃ |− А

– (читається: «якщо А тотожно-істинне, то і доказане А»);

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

354

МТ

–  |− А ⊃  |= А

– (читається: «якщо А не доказане, то і не тотожно-

істинне А»).

Розглянемо по черзі кожну з наведених теорем.

МТ

|− А ⊃ |= А.

Із наведеної вище структури S

очевидно, що множина тав-

тологій включає в себе дві підмножини: аксіоми і теореми.

Відомо, що якщо |= А і |= А ⊃ В, то |= В, тобто правило

висновку забезпечує зберігання властивості «бути та-

втологією». Тоді, якщо кожна аксіома – це тавтологія

і правило висновку зберігає властивість «бути тавто-

логією», то в силу визначення поняття доведення кож-

на теорема є тавтологією.

МТ

 |= А ⊃  |− А.

Доведення.

1. (А ⊃ В) ⊃ (В ⊃А) – А х. 10

2. (|− А ⊃ |= А) ⊃ ( |= А ⊃  |− А) – п/п до 1. А / |− А, В /

|= А

3. |− А ⊃ |= А – МТ

4.  |= А ⊃  |− А – МР до 2,3

МТ

|= А ⊃ |− А.

Ця метатеорема приймається як очевидна.

МТ

 |− А ⊃  |= А.

Доведення.

1. (А ⊃ В) ⊃ (В ⊃А) – Ах. 10

2. (|= А ⊃ |− А) ⊃ ( |− А ⊃  |= А) – п/п А/

А, В/

|−

3. |= А ⊃ |− А – МТ

4.  |− А ⊃  |= А – МР до 2,3.

Таким чином, через доведення МТ

1 –

МТ

ми показали,

що в S

множина вивідних формул співпадає з множиною

тавтологій.

б) Принцип несуперечливості

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

1) теорем;

2) правил висновку;

3) елементів алфавіту.

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

355

Дефініція несуперечливості відносно теорем:

«Логічна система несуперечлива,

якщо клас теорем не співпадає із класом

правильно побудованих виразів (ППВ)»

або

«Логічна система несуперечлива,

якщо існує хоча б один ППВ, який не є тавтологією»,

або

«Логічна система несуперечлива,

якщо не всі ППВ є теоремами».

Ми навели різні варіанти дефініції МТ

. За своєю суттю

вони ідентичні, відмінність лише у словесному вираженні.

Доведення МТ

Візьмемо довільну формулу, яка не є тавтологією: А ⊃ В

(що дана формула не є тавтологією, очевидно із її таблиці

істинності).

1. |= А ⊃ В

2.  |= (А ⊃ В) ⊃  |− (А ⊃ В) – МТ

3.  |− (А ⊃ В) – МР до 1,2

4. (A ∧A) ⊃ В – теорема (із хибного ви-

пливає все що завгодно)

5. (A ∧A) ⊃ |− (А ⊃ В) – п/п В/

|−

(А ⊃ В)

6. (А ⊃ В) ⊃ (В ⊃А) – Ах. 10

7. [(A ∧A) ⊃ |− (A ⊃ B)] ⊃

⊃ [  |− (A ⊃ B) ⊃  (A ∧∧A)] – п/п A/A ∧



A, B/

|−

A ⊃ B

8.  |− (A ⊃ B) ⊃  (A ∧A) – МР до 5,7

9.  (A ∧ A) – МР до 3,8.

Отже, в S

неможлива ситуація A ∧A.

Наслідком МТ

є семантичне формулювання несупереч-

ливості:

«Якщо хоча б один ППВ недоказуваний,

то жодна теорема не є логічним протиріччям».

Дефініція несуперечливості S

відносно перетворень

(правил висновку) у S

«У синтаксичному смислі система S

несуперечлива відносно перетворень,

якщо в ній неможливо довести А і довести  А».

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

356

Доведення цього положення дається двома метатео-

ремами:

МТ

(пряма) –

«Якщо вивідне А, то невірно, що вивідне  А»:

|− А ⊃  |−  А.

Доведення.

1. |− А – припущення

2. |− А ⊃ |= А – МТ

3. |= А – МР до 1,2

4. |= А ⊃  |= А – по таблиці істинності для за-

перечення

5.  |=  А – МР до 3,4

6.  |=  А ⊃  |−  А – МТ

7.  |−  А – МР до 5,6.

МТ

(обернена) –

«Якщо в S

вивідне  А, то невірно, що вивід-

не А»:

|−  А ⊃  |− А.

Доведення.

1. |−  А – припущення

2. |−  А ⊃ | – МТ

3. |=  А – МР до 1,2

4.  |= А – по таблиці істинності для за-

перечення

5.  |= А ⊃  |− А – МТ

6.  |− А – МР до 4,5.

У семантичному смислі ці дві метатеореми свідчать про

те, що в S

не має двох таких теорем, одна із яких є за-

переченням іншої. В кінцевому рахунку несуперечливість

обумовлена прийнятими правилами висновку в S

. Це такі

правила, на основі яких здійснювані перетворення із тав-

тологій породжують тавтології.

Дефініція несуперечливості відносно елементів алфа-

віту (пропозиційних змінних):

«а) у синтаксичному розумінні – жодна окрема про-

позиційна змінна не є теоремою та тавтологією, тоб-

то не доказувана;

б) у семантичному розумінні – жодна окрема пропо-

зиційна змінна не є тавтологією».

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

357

Формула, що складається з однієї пропозиційної змінної

набуває значення «і» або «х», тобто є F-істиною, а зна-

чить, не є теоремою, тобто не доказувана.

в) Принцип повноти

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

рмалізованих мов:

а) виразні можливості засобів мови;

б) виразні можливості дедуктивних засобів мови.

Відповідно до цього розрізняють:

1) функціональну повноту мови;

2) дедуктивну повноту мови.

Якщо йдеться про функціональну повноту засобів мови,

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

ників.

Відомо, що в S

група логічних сполучників повинна

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

або множини ППФ, де є ці сполучники. Але, у групі спо-

лучників (∧, ∨, ⊃, ∾, ) виділяють деякі базисні, вихідні, до

яких можна звести решту сполучників. Саме таку групу

називають функціонально повною.

В S

функціонально повними є:

1. (∧, ∨, );

2. (∧, );

3. (∨, );

4. (⊃, )

На відміну від S

у S

функціональна повнота харак-

теризується через групу аксіом і правил висновку. У рі-

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

групи аксіом і ПВ.

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

собів побудови доведення. В S

такими засобами є аксіоми

і правила висновку.

МТ

«Система S

дедуктивно повна, якщо в ній для будь-

якої формули В доказувано, що:

1) або В вивідне |− В;

2) або приєднання В до системи аксіом робить її су-

перечливою».

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

358

Доведення.

1. Припустимо, що В має вид А ⊃ В.

2. За допомогою таблиці істинності показуємо, що А ⊃ В

не є тавтологією:

 |= (А ⊃ В).

3.  |= (А ⊃ В) ⊃  |− (А ⊃ В) – МТ

4.  |− (А ⊃ В) – МР до 2,3.

5. Приєднаємо А ⊃ В до системи аксіом в S

6. Застосуємо до нової аксіоми А ⊃ В правило підстано-

вки так, щоб замість А підставити тавтологію, а замість В –

протиріччя:

А/ А ⊃ А В/ (В ⊃ В)

(А ⊃ А) ⊃  (В ⊃ В).

Позначимо цю формулу символом |− Σ. Вона вважається

доказаною, оскільки отримана за правилом підстановки із

аксіоми.

7. Але відповідно до таблиці істинності вона є тотожно-

хибною.

8. Якщо Σ –  |=, то  Σ – |= (за табличним визначенням

заперечення): |=  Σ.

9. |=  Σ ⊃ |−  Σ – МТ

10. |−  Σ – МР до 8,9.

Отже, виходить, що якщо до нашої системи аксіом до-

дати довільну формулу А ⊃ В, то вивідними будуть Σ і  Σ,

а це свідчить про суперечливість даної системи. Цим са-

мим встановлено, що сама по собі система S

несуперечли-

ва і, значить, дедуктивно повна.

г) Принцип незалежності

Термін «незалежність» вживається в логіці для харак-

теристики відношення між структурними утвореннями

формалізованої мови:

1) стосовно окремих аксіом;

2) стосовно системи аксіом;

3) стосовно правил висновку.

МТ

«Аксіома, яка не є вихідною із прийнятої в S

систе-

ми аксіом, вважається незалежною».

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

359

Проілюструємо, що аксіома (A ∧ B) ⊃ A є незалежною.

1. Припустимо, що A ∧ B ⊃ A не вивідна із аксіом S

Якщо вона не вивідна, то  |=, тобто приймає значення,

відмінне від значень решти аксіом.

2. Надамо цій аксіомі інтерпретацію, відмінну від ін-

терпретації решти аксіом. Для цього обумовимо

кон’юнкцію такою констатацією: A ∧ B = B, тобто яке зна-

чення приймає В, таке значення приймає A ∧ B.

3. Відповідно до цього аксіома набуде вигляду: В ⊃ А.

4. В ⊃ А не є |= (згідно з таблицею істинності для імплі-

кації).

За такої інтерпретації «∧» можна гарантувати, що аксі-

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

тавтологіями.

Нас цікавить, як поводять себе аксіоми, в структурі

яких є «∧«:

а) 1. (A ∧ B) ⊃ B – Ax. – 4

2. |= (B ⊃ B) – A ∧ B/B;

б) 1. A ⊃ (B ⊃ (A ∧ B)) – Ax. – 5

2. |= A ⊃ (B ⊃ B) – A ∧ B/B.

Отже, всі аксіоми окрім (A ∧ B) ⊃ A залишаються тав-

тологіями, незважаючи на ті дефініції, які над ними здій-

снювалися. А це означає, що вона є незалежною.

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

йомство з аксіоматичним численням логіки висловлювань.

3. Натуральне числення логіки висловлювань

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

вається такий вид числення, в якому висновок будуєть-

ся із гіпотез (припущень) у відповідності з певними

правилами.

Позначають цей вид числень символом S

До S

повністю входять засоби S

. Мається на увазі ал-

фавіт, правила утворення, правила інтерпретації не-

логічних і логічних термінів. Окрім цього в S

входять

14 правил висновку.

Якщо в аксіоматичному численні логіки висловлювань

ми маємо набір аксіом і декілька правил висновку, то тут

дедуктику (а це правила перетворення) складають правила

введення і усунення пропозиційних зв’язок.

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

360

Структуру S

можна зобразити такою схемою:

1) ПУ

2) ПП

правила введення

і усунення пропо-

зиційних зв’язок

ПІ

Sem ML

Sin ML

Логічне числення у вигляді натурального висновку

має такі особливості:

а) назва цього числення «натуральне» характеризу-

ється тим, що в ньому процес виведення висновку більш

наближений до звичайних міркувань людини.

Тобто «натуральне» вживається не в смислі «неформа-

льне», «не регламентоване суворими правилами», а в сми-

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

а не із аксіом;

б) перевагою S

над S

вважається те, що тут процес

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

Відомо, що в S

одна й та ж сама формула в структурі

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

ко трапляється в S

;

в) в S

відбувається певна систематизація правил

висновку. З кожною пропозиційною зв’язкою співставля-

ється одне правило введення і усунення конкретної

зв’язки як головного знака формули (наявність двох пра-

вил УК (усунення кон’юнкції), ВД (введення диз’юнкції),

УЕ (усунення еквіваленції) не є суттєвим).

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

позиційних зв’язок є фактично їх визначенням, а група

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

визначень.