Металогічні принципи в S2

Властивості розв’язання, несуперечливості, повноти і незалежності називають металогічними принципами. Аналізують ці принципи через доведення відповідних ме­татеорем.

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

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

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

Опишемо принцип розв’язання через доведення відпові­дних метатеорем (скорочено — МТ).

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

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

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

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

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

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

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

Із наведеної вище структури S² очевидно, що множина тав­тологій включає в себе дві підмножини: аксіоми і теореми.

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

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

Доведення

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

Таким чином, через доведення MT₁ _ MT₄ ми показали, що в S² множина вивідних формул співпадає з множиною тавтологій.

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

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

1) теорем;

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

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

354

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

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

«Логічна система несуперечлива, якщо клас теорем не співпадає із класом правильно побудованих виразів (ППВ)» або

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

«Логічна система несуперечлива, якщо не всі ППВ є теоремами».

Ми навели різні варіанти дефініції МТ₅. За своєю суттю вони ідентичні, відмінність лише у словесному вираженні.

Доведення MT₅

Візьмемо довільну формулу, яка не є тавтологією: А ⊃ В (що дана формула не є тавтологією, очевидно із її таблиці істинності).

Отже, в S² неможлива ситуація A л A.

Наслідком MT₅ є семантичне формулювання несупереч- ливості:

«Якщо хоча б один ППВ недоказуваний, то жодна теорема не є логічним протиріччям».

Дефініція несуперечливості S² відносно перетворень (правил висновку) у S/:

«У синтаксичному смислі система S² несуперечлива відносно перетворень, якщо в ній неможливо довести А і довести 1 А».

Доведення цього положення дається двома метатео­ремами:

У семантичному смислі ці дві метатеореми свідчать про те, що в S² не має двох таких теорем, одна із яких є за­переченням іншої.

Дефініція несуперечливості відносно елементів алфа­віту (пропозиційних змінних):

«а) у синтаксичному розумінні — жодна окрема про- позиційна змінна не є теоремою та тавтологією, тоб­то не доказувана;

б) у семантичному розумінні — жодна окрема пропо- зиційна змінна не є тавтологією».

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

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

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

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

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

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

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

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

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

Відомо, що в S¹ група логічних сполучників повинна бути достатньою для вираження всіх з п’яти сполучників або множини ППФ, де є ці сполучники. Але, у групі спо­лучників (∧, V, ⊃, ∞, виділяють деякі базисні, вихідні, до яких можна звести решту сполучників. Саме таку групу називають функціонально повною.

На відміну від S¹ у S² функціональна повнота харак­теризується через групу аксіом і правил висновку. У рі­зних аксіоматичних системах можуть бути прийняті різні групи аксіом і ПВ.

Дедуктивна повнота характеризує властивості за­собів побудови доведення. В S² такими засобами є аксіоми і правила висновку.

MT₈ :

«Система S² дедуктивно повна, якщо в ній для будь- якої формули В доказувано, що:

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

2) або приєднання В до системи аксіом робить її су­перечливою».

Доведення.

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

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

Позначимо цю формулу символом |- Σ. Вона вважається доказаною, оскільки отримана за правилом підстановки із аксіоми.

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

а це свідчить про суперечливість даної системи. Цим са­мим встановлено, що сама по собі система S² несуперечли- ва і, значить, дедуктивно повна.

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

Термін «незалежність» вживається в логіці для харак­теристики відношення між структурними утвореннями формалізованої мови:

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

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

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

МТ9:.

«Аксіома, яка не є вихідною із прийнятої в S² систе­ми аксіом, вважається незалежною».

тологіями, незважаючи на ті дефініції, які над ними здій­снювалися. А це означає, що вона є незалежною.

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

3.