ІНТЕРПРЕТАЦІЇ ФОРМУЛИ ЛОГІКИ ВИСЛОВЛЕНЬ

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

Нехай 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 несуперечна, але не є тавтологією.

 

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

1. Як визначаються операції Ø, Ù, Ú, ®, « на множині істинносних значень {0,1}?

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

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

4. Яка формула називається тотожно істинною? тотожно хибною?

5. Що таке тавтологія?

6. За якої умови формула логіки висловлень має модель?

7. Скільки інтерпретацій має формула, що містить n попарно різних атомів?

8. Чи може формула логіки висловлень мати непарну кількість: а) моделей, б) інтерпретацій?

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

І. Для кожної з поданих формул визначити, чи є вона: а) тотожно істинна, б) тотожно хибна, в) несуперечна. Обчислити кількість моделей для кожної з формул.

1. Ø(ØP)®P                          2. P®(PÙQ)

3. Ø(PÚQ)ÚØQ                      4. (PÚQ)®P

5. (P®Q)®(ØQ®ØP)          6. (P®Q)®(Q®P)

7. P®ØP                               8. ØP®P

9. PÚ(P®Q)                          10. (PÙ(Q®P))®P

11. PÚ(Q®ØP)                      12. (PÚØQ)Ù(ØPÚQ)

13. ØPÙ(Ø(P®Q))                14. (P«Q)®(PÙQ)

15. (PÚQ)®(PÙQ)                          16. (PÙQ)®(PÚQ)

17. P®(Q®R)«(PÙQ)®R     18. ((PÚQ)Ù(P®R)Ù(Q®R))®R

19. RÙS®(P®ØQÚS)           20. (PÚØQ)ÚR®(SÙØP).

ІІ. Нехай при інтерпретації h формула F приймає значення 1. Що можна сказати про істинносне значення формули F₁ при інтерпретації h?

1. F = P®Q, F₁= ØPÙQ«PÚQ

2. F = P«Q, F₁= P«ØQ

3. F = Ø(P«Q), F₁= ØP«Q

4. F = PÙQ, F₁= (PÚQ)®(ØP®ØQ)

5. F = PÚQ, F₁= P«Q.

III. Довести твердження.

1. Формула F є тавтологією тоді й тільки тоді, коли формула ØF тотожно хибна.

2. Формула F тотожно хибна тоді й тільки тоді, коли формула ØF є тавтологією.

3. Якщо формула тотожно істинна, то вона несуперечна, але не навпаки.

4. Якщо формула суперечна, то вона не є тавтологією, але не навпаки.

IV. Записати детальне доведення твердження 1.

V. Нехай формули F₁ та F₁®F₂ є тотожно істинними. Довести, що F₂ тотожно істинна.

VІ. Нехай формула F є тавтологією, A₁, A₂,…,A_n – атоми, що входять у F. Нехай формула F₀ утворюється у результаті підстановки у F деяких формул F₁,F₂,…,F_n замість атомів A₁,A₂,…,A_n. Довести, що F₀ є тавтологією.

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: