Тавтології, суперечності та логічні висновки

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

Наприклад, A ÚØ A чи (A ® B)Ú(B ® A). Неважко також переконатися, що заміною знаків º на зв'язку «у законах (1)-(13), наведених у п.1.1, одержуються саме тавтології.

Тавтології характерні тим, що коли всі входження тієї самої літери замінити на будь-яке, але одне й те саме висловлення, то нове висловлення буде істинним. Наприклад, підставимо у тавтологію ((A Ú B)ÙØ B)® A замість літери A висловлення "світить сонце", а замість літери B – "світять зорі". Одержане висловлення "Якщо світить сонце або світять зорі, і не світять зорі, то світить сонце" є істинним. Підкреслимо, що сама по собі структура цього висловлення вже забезпечує його істинність.

Неважко переконатися, що якщо тавтологіями є деяка формула X і формула X ® Y, то Y також є тавтологією.

Означення. Формула називається тотожньо хибною, або суперечністю, якщо має значення 0 при всіх можливих значеннях пропозиційних змінних.

Одним із характерних прикладів суперечності є висловлення A ÙØ A. Ця суперечність використовується у доведенні тверджень вигляду A ® B методом " від супротивного ". Припускають істинність заперечення Ø(A ® B), тобто істинність A ÙØ B. З істинності Ø B виводять Ø A, одержуючи суперечність A ÙØ A. Вона свідчить про хибність A ÙØ B, тобто істинність A ® B.

Зауважимо, що для доведення істинності A ® B достатньо з Ø B вивести Ø A, тобто довести істинність протилежного твердження Ø B ®Ø A. Адже за законом контрапозиції (11) A ® B º Ø B ®Ø A

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

Тепер розглянемо поняття логічного висновку. У математиці, як і у звичайному житті, доводиться з'ясовувати, чи випливає деяке твердження з одного або кількох інших, тобто чи є це твердження їх логічним висновком.

Приклад. Припустимо, що купівельна спроможність грошей падає, якщо зростають податки, і що люди незадоволені, коли падає купівельна спроможність грошей. Припустимо також, що податки зростають. Звідси можна дійти висновку, що люди незадоволені.

Для цього позначимо висловлення літерами:

A – "податки зростають",

B – "купівельна спроможність грошей падає",

C – "люди незадоволені".

Припущення прикладу висловимо формулою:

(A ® B)Ù(B ® C)Ù A.

Доведемо, за істинності такої умови істинним буде висловлення C. Перетворимо (A ® B)Ù(B ® C)Ù A до ДНФ:

(A ® B)Ù(B ® C)Ù A º (Ø A Ú B)Ù(Ø B Ú C)Ù A º A Ù(Ø A Ú B)Ù(Ø B Ú C) º

º (A ÙØ A)Ù(A Ù B)Ù(Ø B Ú C) º (A Ù B)Ù(Ø B Ú C) º

º (A Ù B ÙØ B)Ú(A Ù B Ù C) º A Ù B Ù C.

Отже, маємо, що істинною є формула A Ù B Ù C. Але вона істинна лише тоді, коли кожний співмножник істинний. Звідси висловлення C є істинним.

Таким чином, з істинності формул (A ® B), (B ® C) і A випливає істинність C. У такому випадку C називається логічним висновком цих формул.

Означення. Формула Y називається логічним висновком формул X ₁, X ₂, …, X_n, якщо з істинності X ₁Ù X ₂Ù…Ù X_n випливає істинність формули Y. Формули X ₁, X ₂, …, X_n називаються засновками Y.

Перевірити, чи є одна формула логічним висновком інших, можна за допомогою порівняння таблиць істинності цієї формули та кон'юнкції інших. Але можна діяти зовсім іншим способом на основі двох наступних тверджень.

Теорема 1. Формула Y є логічним висновком формул X ₁, X ₂, …, X_n тоді й тільки тоді, коли формула (X ₁Ù X ₂Ù…Ù X_n)® Y є тавтологією.

Доведення. 1 (Необхідність). Припустимо, що формула Y є логічним висновком формул X ₁, X ₂, …, X_n. Якщо за деяких значень літер у формулах X ₁, X ₂, …, X_n хоча б одна з них хибна, то за означенням імплікації (X ₁Ù X ₂Ù…Ù X_n)® Y істинна. Якщо ж за деяких значень літер у формулах X ₁, X ₂, …, X_n всі вони істинні, X ₁Ù X ₂Ù…Ù X_n також істинна. Але формула Y є логічним висновком формул X ₁, X ₂, …, X_n, тому вона також істинна. Тоді істинна і формула (X ₁Ù X ₂Ù…Ù X_n)® Y. Отже, за будь-яких значень літер (X ₁Ù X ₂Ù…Ù X_n)® Y істинна, тобто є тавтологією.

2 (Достатність). Припустимо, що (X ₁Ù X ₂Ù…Ù X_n)® Y є тавтологією. Тоді якщо за якихось значень літер у формулах X ₁, X ₂, …, X_n всі вони істинні, то Y також істинна, тобто є їх логічним висновком.

Теорема 2. Формула Y є логічним висновком формул X ₁, X ₂, …, X_n тоді й тільки тоді, коли формула (X ₁Ù X ₂Ù…Ù X_n ÙØ Y) є суперечністю.

Доведення. За теоремою 1, формула Y є логічним висновком формул X ₁, X ₂, …, X_n тоді й тільки тоді, коли формула (X ₁Ù X ₂Ù…Ù X_n)® Y є тавтологією. Звідси Y є логічним висновком формул X ₁, X ₂, …, X_n тоді й тільки тоді, коли заперечення Ø((X ₁Ù X ₂Ù…Ù X_n)® Y)є суперечністю. Але

Ø((X ₁Ù X ₂Ù…Ù X_n)® Y) º Ø(Ø(X ₁Ù X ₂Ù…Ù X_n)Ú Y) º

º Ø(Ø(X ₁Ù X ₂Ù…Ù X_n))ÙØ Y º X ₁Ù X ₂Ù…Ù X_n ÙØ Y.

Таким чином, твердження теореми істинне.

Розглянемо приклад застосування наведених теорем. Доведемо, що формула B є логічним висновком формул A ® B і A. Перетворимо формулу (A ® B)Ù A ÙØ B:

(A ® B)Ù A ÙØ B º (Ø A Ú B)Ù A ÙØ B º (Ø A Ù A ÙØ B)Ú(B Ù A ÙØ B) º 0Ú0 º 0.

Отже, формула (A ® B)Ù A ÙØ B суперечлива, і за теоремою 2 формула B є логічним висновком формул A ® B і A.

Той факт, що формула B є логічним висновком формул A ® B і A, відіграє в математиці дуже важливу роль. Він дозволяє з уже відомих істинних тверджень A ® B і A одержати нове істинне твердження B. Зауважимо, що такий спосіб одержання, або виведення нових тверджень у математичній логіці є одним із основних. Таке виведення задається спеціальним правилом виведення, яке має вигляд  і назву modus ponens (правило відокремлення). Воно дозволяє одержати висновок B твердження A ® B як окреме висловлення, тобто відокремити його вид засновку A. У математичній логіці існують і інші правила виведення, але тут ми їх не розглядаємо.

Підіб'ємо невеличкий неформальний підсумок. Ми познайомилися з двома принципово різними способами одержання нових висловлень. Перший полягає в тому, що ми будуємо складні висловлення з простіших за допомогою логічних зв'язок, а також "перебудовуємо" їх, виконуючи рівносильні перетворення на основі законів. Описані способи побудови та перетворення висловлень складають основу алгебри висловлень.

Другий спосіб одержання нових істинних висловлень полягає в застосуванні згаданих правил виведення до вже відомих істинних висловлень. При цьому формулюється система висловлень-тавтологій, що складає основу для виведення інших. Вони називаються аксіомами, а висловлення, що виводяться, – теоремами. Прикладом аксіоми може служити висловлення AÚØA, яке називається законом виключеного третього. Такий спосіб породження висловлень називається численням висловлень.

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