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

Аналізуючи пропозиційну логіку на рівні алгебраїчної системи, ми розглядали кожну формулу як вираз, що може прийняти одне із двох значень: «істина» або «хиба». Завдяки цьому засобами даної системи можна було розв’язувати такі задачі:

1) проводити демаркацію між тавтологіями і нета- втологіями;

2) визначати відношення логічного слідування між двома формулами;

3) здійснювати перевірку формул на рівносильність.

Однак складніші задачі засобами S¹ розв’язати немож­ливо. Для цього необхідно залучати більш ефективні логі­чні засоби.

а) Мова аксіоматичного числення логіки висловлювань

Позначається аксіоматичне числення логіки вислов­лювань символом S².

До складу синтаксису (Sin ML) S² входять окрім правил утворення (як уже зазначалося) правила пере­творення (ПП).

Зупинимося на характеристиці правил утворення (ПУ).

Алфавіт S² включає такі самі символи, що й алфавіт S¹:

1) пропозиційні символи: p, q, r, s, p₁, q₁, r₁, s₁,...;

2) логічні символи: &, ∨, ⊃, ∞, 1.

Як бачимо, за назвою це ті ж самі об’єкти, що і в алфа­віті S¹, але у S² вони розглядаються з іншої, більш форма­льної, сторони. Тут p, q, r, s — це вже не сутності, які зда­тні приймати значення «і» (істина) або «х» (хиба) при різних наборах значень, а певні об’єкти, які чітко відріз­няються один від одного, і властивості яких явно не ви­значаються. Стосовно логічних символів зауважимо, що тут уже не йдеться про їх табличне визначення.

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

Дефініція формули така сама, як і в S¹. Але формула в S² характеризується не таблицями істинності, а си­туацією виводу (випливання).

Усередині тотожно-істинних (або тавтологій, або L-i) формул відбувається розшарування на теореми і ак­сіоми.

Вищезазначене можна проілюструвати схемою мови S²:

Ось так можна охарактеризувати ПУ в S². Очевидно, що вони співпадають із ПУ в S¹, але тут вони, природно, на­бувають певної специфіки.

Розглянемо правила перетворення (ПП).

До складу ПП входять:

1. Дефініція аксіоми.

2. Дефініція теореми.

3. Список аксіом.

4. Правила доведення, які включають:

а) правило відділення або правило модус поненс (МР);

б) правило підстановки (п/п).

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

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

Дефініція: «Аксіомою в S² називають підмножину тавтологій, які визначаються вихідними при побудові доведення».

істинні, то В також істинне». Записується правило у вигляді схеми:

¹ Зрозуміло, що тут маються на увазі аксіомні схеми.

Зауважимо, що не треба розглядати аксіому S² у тради­ційному розумінні як «очевидну істину» або як «істину, що не потребує доведення».

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

Дефініція: «Теоремами в S² називають підмножину тавтологій, для яких існує доведення».

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

Набір аксіом у S² може бути різним, але він повинен бути достатнім для доведення теорем у S².

Як зразок візьмемо набір аксіом, запропонований німе­цьким вченим Давидом Гільбертом:

Застосовуючи до наведеного набору аксіом правила до­ведення, можна вивести будь-яку теорему в S².

Визначимо правила доведення.

Дефініція правила відділення (МР): «Якщо

346

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

Дефініція доведення: «Доведенням називається послі­довність формул A₁,... A_n, де кожна із формул є або ак­сіомою, або доказаною раніше формулою, або отримана за правилами доведення; остання формула послідовно­сті А_п є виразом, який потрібно було довести».

Дефініція доказової формули: «Формула А назива­ється доказовою тоді, коли є можливість побудувати доведення, останньою формулою якого є формула А».

Факт, що формула доказова, її записують так: |- А.

Якщо формула не доказова, то: -| А.

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

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

Послідовність удоведенні зліва утворює, власне, дове­дення теоремиПослідовність справа — є аналізом

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

Опишемо хід доведення із аксіом.

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

1) виписати одну із аксіом;

2) послідовно застосувати правило підстановки (п/п) і правило відділення (МР);

3) доведення є закінченим, якщо останнім виразом у послідовності формул буде F.

Розглянемо приклад побудови доведення теореми:

1. Візьмемо аксіому 8:

2. Застосовуємо правило підстановки і підставляємо замість r/q:

3. Беремо аксіому 2:

5. Застосовуємо правило відділення (МР) до 2 і 4 ряд­ків і отримуємо:

6. Візьмемо формулу, раніше доведену в S²:

7. Застосуємо правило підстановки і підсталяємо за­мість p/q:

8. Беремо аксіому 1:

9. Використовуємо правило підстановки і підставляємо замість

10. Застосовуємо правило відділення (МР) до 6 і 8 ряд­ків і отримуємо:

11. Використовуючи правило МР до 9 і 4, отримуємо:

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

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

Дефініція: «Доведенням із гіпотез А1,... А_п формули В називається кінцева послідовність формул В1,... В_п, ко­жна з яких є або аксіома, або гіпотеза, або раніше дове­дена формула в S², або отримана із двох попередніх фо­рмул за правилом МР; причому В_п є В ».

Факт, що формула В доказується із гіпотез А1,... А_п, за­писується так:

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

Наведемо приклад щодо цього виду доведення.

Маємо гіпотези:

Необхідно побудувати доведення із них формули r:

Зауважимо, що треба розрізняти терміни «теорема» і « метатеорема ».

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

До таких фундаментальних властивостей числень відносяться:

— вивідність;

—розв’язуваність;

— несуперечливість;

— повнота;

— незалежність.

Кожна із цих властивостей описується відповідними метатеоремами:

— про дедукцію;

— про несуперечливість;

— про розв’язуваність;

— про повноту;

— про незалежність.

Розглянемо їх по порядку.

2.