(4) AÙA º A, AÚA º A – закони ідемпотентності
(5) AÚ(AÙB) º A, AÙ(AÚB) º A
(6) Ø(AÚB) º ØAÙØB, Ø(AÙB) º ØAÚØB – закони Де Моргана
(7) ØØA º A – закон подвійного заперечення
(8) AÙ0 º 0, AÙ1 º A, AÚ0 º A, AÚ1 º 1 – закони поглинання
(9) AÚØA º 1 – закон виключеного третього
(10) AÙØA º 0 – закон суперечності
(11) A®B º ØB®ØA – закон контрапозиції
Корисно також пам'ятати ще два закони:
(12) A®B º ØAÚB
(13) A«B º (A®B)Ù(B®A).
На законах грунтуються так звані рівносильні перетворення формул, коли формула або її підформула заміняється на рівносильну їй. В результаті одержується формула, рівносильна початковій. Такі перетворення бувають потрібні для спрощення формул. Наприклад, формула AÚ(ØA®B) має рівносильні формули AÚ(ØØAÚB), AÚ(AÚB), (AÚA)ÚB, AÚB, що одержуються послідовним застосуванням законів (12), (7), (2), (4).
3. Нормальні форми висловлень
Розглянемо два різновиди формул, що мають певні структурні особливості. Саме структура цих формул зумовлює їх використання у таких важливих галузях застосування математичної логіки, як автоматизація доведення тверджень і логічне програмування.
Закони (2) стверджують асоціативність зв'язок кон'юнкції. Звідси формула вигляду ((…((A1ÙA2)ÙA3)Ù…)ÙAn) має еквівалентний запис A1ÙA2ÙA3Ù…ÙAn. Формула в такому записі називається кон'юнкцією формул A1, A2, A3, …, An.
Означення. Елементарною кон'юнкцією називається кон'юнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A1ÙØA2ÙA3.
Означення. Диз'юнктивною нормальною формою (скорочено ДНФ) називається диз'юнкція елементарних кон'юнкцій. Наприклад, формула AÙBÚBÙCÚD. Зауважимо, що її структуру краще видно в записі A×BÚB×CÚD або в записі .
Будь-яка формула може бути перетворена до ДНФ. Ми не будемо доводити це твердження, а лише опишемо потрібні рівносильні перетворення. Застосуванням законів (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)
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
Очевидно, що заперечення будь-якої тавтології є суперечністю, і навпаки. На відміну від тавтологій, підстановка висловлень у суперечності породжує хибні висловлення.
Тепер розглянемо поняття логічного висновку. У математиці, як і у звичайному житті, доводиться з'ясовувати, чи випливає деяке твердження з одного або кількох інших, тобто чи є це твердження їх логічним висновком.
Приклад. Припустимо, що купівельна спроможність грошей падає, якщо зростають податки, і що люди незадоволені, коли падає купівельна спроможність грошей. Припустимо також, що податки зростають. Звідси можна дійти висновку, що люди незадоволені.
Для цього позначимо висловлення літерами:
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 називається логічним висновком формул X1, X2, …, Xn, якщо з істинності X1ÙX2Ù…ÙXn випливає істинність формули Y. Формули X1, X2, …, Xn називаються засновками Y.