Сторінка
3

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

Будь-яка формула може бути перетворена до ДНФ. Ми не будемо доводити це твердження, а лише опишемо потрібні рівносильні перетворення. Застосуванням законів (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.

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

Будь-яка формула перетворюється до рівносильної їй КНФ з використанням тих самих законів, тільки замість першого з законів дистрибутивності (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)

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

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