Методи перевірки тотожної хибнОсті й тОтожної істинНості формул логіки висловлень

Різноманітні задачі у математиці та у інших галузях можуть бути сформульовані як задачі встановлення того, чи випливає деяке твердження з заданої сукупності інших тверджень. Теорема 1, що сформульована вище, дає можливість замінити перевірку логічного слідування формули F з формул F₁,…,F_n перевіркою тавтологічності або суперечності формул, побудованих з F₁,…,F_n, F. Для установлення тавтологічності (суперечності) деякої формули P логіки висловлень можна використати таблиці істинності й перевіряти істинносні значення формули P при кожній інтерпретації. Ми розглянемо інші методи перевірки тавтологічності та суперечності, які ґрунтуються на поданні формул у спеціальному вигляді, а саме у вигляді тієї чи іншої нормальної форми. Для подання формули у нормальній формі виконуються перетворення даної формули, які зберігають її істинносне значення при кожній інтерпретації.

Еквівалентні формули логіки висловлень

Формули F₁ й F₂ називаються еквівалентними (позначається F₁ = F₂ ), якщо істинносні значення F₁ й F₂ збігаються при кожній інтерпретації F₁ й F₂.

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

1) F₁  F₂ = (F₁F₂)  (F₂F₁);

2) F₁ F₂ = F₁  F₂;

3) F₁  F₂ = F₂  F₁; F₁  F₂ = F₂  F₁; (закони комутативності)

4) F₁  (F₂  F₃) = (F₁  F₂)  F₃; (закони

5) F₁  (F₂  F₃) = (F₁  F₂)  F₃; асоціативності)

6) F₁  (F₂  F₃) = (F₁  F₂)  (F₁  F₃); (закони

7) F₁  (F₂  F₃) = (F₁  F₂)  (F₁  F₃); дистрибутивності)

8) F₁  F₁ = F₁; F₁  F₁ = F₁; (закони ідемпотентності)

9) F₁  (F₁  F₂) = F₁; F₁  (F₁  F₂) = F₁; (закони поглинання)

10) (F₁  F₂) = F₁  F₂; (F₁  F₂) = F₁  F₂;

11) (F₁) = F₁;

12) 1F₁=1; 1  F₁ = F₁; 0  F₁ =F₁; 0F₁=0, F₁F₁=0, F₁F₁=1.

Внаслідок законів асоціативності дужки у формулах виду F₁  (F₂  F₃) або (F₁  F₂)  F₃, а також у F₁  (F₂  F₃) або (F₁  F₂)  F₃ можна опускати й писати F₁  F₂  F₃ та F₁  F₂  F₃. Отже, якщо F₁, F₂, …, F_n – формули, будемо писати F₁ F₂ … F_n й F₁  F₂  …  F_n замість F₁  (F₂  (…  F_n)…) й F₁  (F₂  (… F_n)…). Вираз F₁  … F_n (F₁  …  F_n) називається диз’юнкцією (кон’юнкцією) формул F₁,…, F_n.

Літерою називається формула, що має вигляд A або A, де A – атом. Літера, що не містить знак “”, називається позитивною, інакше – негативною.

Формула F є у кон’юнктивній нормальній формі (кнф), якщо F=F₁…F_n, де F₁,…,F_n – формули, кожна з яких є літерою або диз’юнкцією літер, n1.

Диз’юнкт є диз’юнкція літер або літера.

Надалі будемо іноді вважати вирази “множина літер” та “диз’юнкт” синонімами. Наприклад, QPR={Q,P,R}. Диз’юнкт, що містить r літер, називається r-літерним диз’юнктом. Однолітерний диз’юнкт називається одиничним диз’юнктом. Диз’юнкт, що не містить жодної літери, називається пустим (порожнім) диз’юнктом (позначається ). Оскільки  не містить літер, які могли б бути істинними при якихось інтерпретаціях, то він є тотожно хибним.

Нехай A – атом. Будемо називати літери A та A контрарними, а множину {A, A} – контрарною парою.

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

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

Формула F є у диз’юнктивній нормальній формі (днф), якщо F=F₁…F_n, де F₁,…,F_n – формули, кожна з яких є літерою або кон’юнкцією літер, n1.

Приклад 3. Нехай P, Q, R – атоми. Тоді (PR)  (Q  R  P) є формула у диз’юнктивній нормальній формі. Для цієї формули F₁ = P  R, F₂ = Q  R  P; F₁ є кон’юнкція літер P й R, а F₂ є кон’юнкція літер Q, R, P. (Q  R  P)  (R  Q) – формула у кон’юнктивній нормальній формі. Для цієї формули F₁ = Q  R P, F₂ = R  Q; F₁ – диз’юнкція літер Q, R, P, а F₂ – диз’юнкція літер R та Q.

Будь-яка формула логіки висловлень може бути перетворена у кнф та днф за допомогою співвідношень 1-12.

Приклад 4. Побудуємо кон’юнктивну нормальну форму для форму-ли Q(P(RS)). Використовуючи співвідношення 1-12, маємо: Q(P(RS))=Q(P(RS))=Q(P(RS))=(QP)(Q (RS)) = (QP)(QR)(QS). Отже, кнф формули Q(P(RS)) є формула (QP)(QR)(QS).