Елементи логіки, Детальна інформація

Закони (2) стверджують асоціативність зв'язок кон'юнкції. Звідси формула вигляду ((…((A1(A2)(A3)(…)(An) має еквівалентний запис A1(A2(A3(…(An. Формула в такому записі називається кон'юнкцією формул A1, A2, A3, …, An.

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

.

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

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

(A(B)((B(C) ((13, 12)

(((((A(B)(((C(B))(((((C(B)(((A(B)) ((6, 7, 2)

( (A((B((C(B)(((B(C((A(B) ((3)

( A((B((B(C(A((B((A(A((B(B((C((B(C((C((A((C(B(

(B((B(C(B((A(B(B ((1, 4, 9, 8)

( A((B(C((A((C(B((C(B((A(B ((5)

( A((B(C((A((C(B

За законами (2) зв'язки диз'юнкції також асоціативні, звідки формули ((…((A1(A2)( A3)( …)(An) і A1(A2(A3(…(An також є еквівалентними. Остання з них називається диз'юнкцією формул A1, A2, A3, …, An.

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

.

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

Приклад. Розглянемо перетворення формули (A(B)((C(B) після одержання формули (A((B((C(B)(((B(C((A(B):

(A((B((C(B)(((B(C((A(B) ((3)

( (A((B((C)(A((B(B)(((B(C((A)(((B(C(B) ((3)

( (A((C)(((B((C)((A(B)(((B(B)(((B((A)((C((A)(

(((B(B)((C(B) ((9)

( (A((C)(((B((C)((A(B)(((B((A)((C((A)((C(B)

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

Означення. Формула називається тотожньо істинною, або тавтологією, якщо має значення 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