Елементи логіки

Будь-яка формула може бути перетворена до ДНФ. Ми не будемо доводити це твердження, а лише опишемо потрібні рівносильні перетворення. Застосуванням законів (13) і (12) можна позбутися зв'язок і , тобто перетворити формулу до рівносильної, у якій є лише зв'язки і . Далі, якщо у формулі є заперечення диз'юнкцій чи кон'юнкцій, то вони "спускаються" до пропозиційних змінних застосуванням законів Де Моргана (6). Далі, якщо у формулі є множники-диз'юнкції, то їх можна позбутися застосуванням першого з законів дистрибутивності (3). В результаті всі множники у кон'юнкціях формули є елементарними, і вона являє собою ДНФ. Застосування законів (1), (2), (4), (5), (7)-(10) може скоротити цей процес.

Приклад. Розглянемо перетворення (AB)(CB). Після знаків у дужках указано номери законів, застосованих при черговому перетворенні:За законами (2) зв'язки диз'юнкції також асоціативні, звідки формули ((…((A1A2) A3) …)An) і A1A2A3…An також є еквівалентними. Остання з них називається диз'юнкцією формул A1, A2, A3, …, An.

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

Означення. Кон'юнктивною нормальною формою (скорочено КНФ) називається кон'юнкція елементарних диз'юнкцій. Наприклад, формула (AB)(BCD), яку можна подати також у вигляді .

Будь-яка формула перетворюється до рівносильної їй КНФ з використанням тих самих законів, тільки замість першого з законів дистрибутивності (3) вживається другий: A(BC) (AB)(AC).

Приклад. Розглянемо перетворення формули (AB)(CB) після одержання формули (ABCB)(BCAB):

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

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

Наприклад, AA чи (AB)(BA). Неважко також переконатися, що заміною знаків на зв'язку у законах (1)-(13), наведених у п.1.1, одержуються саме тавтології.

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

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

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

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

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

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

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