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

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

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

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

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

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

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

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

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

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

(AB)(BC)A.

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

(AB)(BC)A (AB)(BC)A A(AB)(BC)

(AA)(AB)(BC) (AB)(BC)

(ABB)(ABC) ABC.

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

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

Означення. Формула Y називається логічним висновком формул X1, X2, …, Xn, якщо з істинності X1X2…Xn випливає істинність формули Y. Формули X1, X2, …, Xn називаються засновками Y.

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

Теорема 1. Формула Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли формула (X1X2…Xn)Y є тавтологією.

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

2 (Достатність). Припустимо, що (X1X2…Xn)Y є тавтологією. Тоді якщо за якихось значень літер у формулах X1, X2, …, Xn всі вони істинні, то Y також істинна, тобто є їх логічним висновком.

Теорема 2. Формула Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли формула (X1X2…XnY) є суперечністю.

Доведення. За теоремою 1, формула Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли формула (X1X2…Xn)Y є тавтологією. Звідси Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли заперечення ((X1X2…Xn)Y)є суперечністю. Але

((X1X2…Xn)Y) ((X1X2…Xn)Y)

((X1X2…Xn))Y X1X2…XnY.

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

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

(AB)AB (AB)AB (AAB)(BAB) 00 0.

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

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

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

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

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

5. Неформальне знайомство з кванторами

У математиці, як і у повсякденному житті, виникають твердження зі специфічною структурою. Ця структура робить можливими міркування, які не можна відтворити виведенням висловлень. Класичним прикладом таких міркувань є:

Кожна людина смертна.

Сократ – людина.

Звідси випливає, що Сократ смертний.

Очевидно, що висловлення "Сократ смертний" не є логічним висновком засновків "Кожна людина смертна" і "Сократ – людина". Проте коректність наведених