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

туацією виводу (випливання). Тому тут відбувається диференціація формул не на тавтології, протиріччя і нейтральні (виконувані), а на теореми і аксіоми. Маєть-

ся на увазі, що саме ця типологія висувається на передній план, а не те, що в об’єкт-мові S2 відсутні тотожно-хибні (або протиріччя, або L-x) формули і нейтральні (або вико- нувані, або F – i) формули.

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

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

L-i

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

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

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

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

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

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

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

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

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

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

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

Зауважимо, що не треба розглядати аксіому S2 у тради-

ційному розумінні як «очевидну істину» або як «істину, що не потребує доведення».

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

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

Аксіоми і теореми вичерпують всю множину тавто-

логій в S2. Враховуючи це, аксіоматичні числення будують так, щоб клас теорем співпадав із класом тавтологій. Іншими словами, S2 своїми засобами забезпечує можливість охарак- теризувати всю множину тавтологій. Саме цій змістовній вимозі підпорядкований вибір аксіом і правил висновку у S2.

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

Як зразок візьмемо набір аксіом, запропонований німе-

цьким вченим Давидом Гільбертом:

3.(А В) А

4.(А В) В

5. А (В (А В))

6.А (А В)

7.В (А В)

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

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

Дефініція правила відділення (МР): «Якщо А і А В істинні, то В також істинне». Записується правило у вигляді схеми:

A

A B .

B

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

Дефініція правила підстановки (п/п): «Нехай А, фор- мула, яка містить змінні х1, х2, ... хn. Тоді, якщо А – істинна формула в численні висловлювань, то, заміня- ючи в ній змінні x1, x2, ... xn всюди, де вони входять дові- льними змінними x1′, x2′, ... xn′, отримаємо формулу А′,

яка також буде істинною».

Це правило має вигляд:

A(x1 , x2 , ..., xn ) . A′(x1′, x′2 , ..., xn′ )

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

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

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

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

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

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

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

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

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

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

1) виписати одну із аксіом; 2) послідовно застосувати правило підстановки (п/п)

і правило відділення (МР); 3) доведення є закінченим, якщо останнім виразом у

послідовності формул буде F.

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

|− (p q) ((p q) q).

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

(p r) ((q r) ((p q) r)).

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

(p q) ((q q) ((p q) q)).

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

(p (q r)) ((p q) (p r)).

4.За правилом підстановки підставляємо замість p/p

q, замість q/q q, замість r/(p q) q:

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

(q q) ((p q) (q q)).

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

ків і отримуємо:

(p q) (q q).

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

|− (p q) ((p q) q).

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

Наведені доведення є доведеннями із аксіом. Ці дове-

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

або гіпотезами.

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

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

А1, ..., Аn |− В.

Іноді в науковій літературі зустрічається, що доведен-

ням із гіпотез називають дедукцію (вивідність) із гіпотез,

залишаючи термін «доведення» для позначення доведення із порожньої множини гіпотез, або доведення із аксіом.

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

Маємо гіпотези: p q, p (q r).

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