Контрольні питання

1. Що таке висловлення?

2. Що таке атомарна формула?

3. Що таке формула логіки висловлень?

4. Що таке мова логіки висловлень?

Задачі та вправи

І. Подати висловлення формулами логіки висловлень.

1. Для того, щоб ціле число х було непарним, достатньо, щоб х було простим.

2. Якщо число х додатне, то х³ додатне.

3. Дане відношення є відношенням еквівалентності тоді й тільки тоді, коли воно рефлексивне, симетричне та транзитивне.

4. Для того, щоб число х було додатним, необхідно, щоб додатним було число х+1.

5. Якщо увечері буде дощ, то Петро або залишиться вдома й буде нудьгувати, або поїде на концерт на таксі.

6. Якщо Марійка стомлена чи зголодніла, вона не може працювати.

7. Ні «Зоря», ні «Карпати» не виграли чемпіонат з футболу минулого року.

8. Множини А та В рівні тільки тоді, коли А є підмножиною В.

9. Якщо х – ціле число, то х парне або непарне.

10. Петро любить подорожувати, але намагається не користуватися повітряним транспортом.

ІІ. Нехай для позначення висловлень уведені атоми. Записати подані формули українською мовою.

1. P: «Йому потрібен лікар»

Q: «Йому потрібен адвокат»

R: «З ним трапився нещасний випадок»

S: «Він хворий»

T: «Він поранений».

а) (SP)(RQ), б) P(ST),

в) (PQ)R, г) (PQ)(ST),

д) (ST)P, є) R(PQ).

2. С: «Сьогодні ясно»

R: «Сьогодні дощить»

S: «Сьогодні падає сніг»

Y: «Вчора було похмуро».

а) С(RS), б) YC,

в) (YR)C, г) C(RS)Y,

д) (CR)(SY), є) Y(CR).

Інтерпретації формули логіки висловлень

Оскільки з кожним висловленням зв’язане істинносне значення, а для подання висловлення можна використати формули логіки висловлень, то з формулами логіки висловлень теж доцільно зв’язувати істинносні значення.

Нехай F, F₁, F₂ – формули. Зв’язок між істинносними значеннями F, F₁, F₂ й істинносними значеннями формул F, F₁F₂, F₁F₂, F₁F₂, F₁F₂ визначається такими таблицями істинності:

F₁ F₂ F₁  F₂ F₁  F₂ F₁  F₂ F₁  F₂ F F

-------------------------------------------------------------------------------

0 0 0 0 1 1 0 1

0 1 0 1 1 0 1 0

1 0 0 1 0 0

1 1 1 1 1 1

Користуючись таблицями істинності, можна обчислити істинносне значення будь-якої формули, виходячи з істинносних значень атомів, що входять в неї. Розглянемо, наприклад, формулу F: QPQR. Атомами у ній є Q, P, R. Якщо істинносними значеннями Q, P й R є відповідно 0, 0 й 1, то, за таблицями істинності, Q=1, QP=0, QR=1, а F приймає значення 1. Якщо атомам Q, P й R приписати значення 1, 1, 0, то F приймає значення 0.

Зазначимо, що таблиці істинності задають операції , , , ,  на множині істинносних значень {0,1}.

Нехай F – формула, A₁,…, A_n – усі попарно різні атоми, що входять у F. Інтерпретацією формули F називається таке відображення h множини атомів A₁,…, A_n у множину істинносних значень 0,1, що для будь-яких формул F₁ та F₂, що містять атоми A₁,…, A_n, h(F₁F₂)=h(F₁)h(F₂), h(F₁F₂)=h(F₁)h(F₂), h(F₁F₂)=h(F₁)h(F₂), h(F₁F₂)=h(F₁)h(F₂), h(F₁)=h(F₁).

Якщо A₁,…, A_n – усі атоми, що входять у деяку формулу, зручно подавати інтерпретацію цієї формули у вигляді множини {m₁,…,m_n}, де m_i – це A_i, якщо A_i приймає значення 1 при даній інтерпретації, або A_i, якщо A_i приймає значення 0 при даній інтерпретації. Наприклад, множина {P, Q, R} представляє інтерпретацію, при якій атомам P й Q приписано значення 0, а атому R – значення 1.

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

Моделлю формули F називається така інтерпретація формули F, при якій F приймає значення 1. Якщо існує інтерпретація, при якій формула F приймає значення 1, то будемо говорити, що формула F має модель.

Наприклад, формула F=АВС має модель {A,B,C}. Перевіримо це. Для цього обчислимо істинносне значення формули F при інтерпретації {A,B,C}, підставивши значення 1 замість атомів А, В, С у F та скориставшись таблицями істинності. Маємо: 111=011=11=1. Оскільки формула F приймає значення 1 при інтерпретації {A,B,C}, то дана інтерпретація є моделлю F, й, відповідно, F має модель.

Твердження 1. Якщо формула містить n різних атомів, то вона має 2ⁿ різних інтерпретацій.

Доведення грунтується на застосуванні означення n-арної функції з множини Х у множину Y.

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

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

Наприклад, формула PP є тавтологією; формула PP суперечна; формула PQ несуперечна, але не є тавтологією.