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

Нормальні форми

Формули 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₁; Ø1=0; Ø0=1;

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 – формули, nÎ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ÎN⁺.

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

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

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

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

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

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

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

Кон’юнкт є кон’юнкція літер або літера.

Наприклад, нехай 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.

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

    Дійсно, для перетворення формули у кнф або днф слід послідовно та за потребою застосувати: співвідношення 1) F₁ « F₂ = (F₁®F₂) Ù (F₂®F₁) для вилучення зв’язки «, співвідношення 2) F₁® F₂ = ØF₁ Ú F₂ для вилучення зв’язки ®, тотожність 11) Ø(ØF₁) = F₁ для спрощення формули, співвідношення 10) Ø(F₁ Ú F₂) = ØF₁ Ù ØF₂; Ø(F₁ Ù F₂) = ØF₁ Ú ØF₂ для того, щоб перенести знак заперечення безпосередньо до атомів (зменшити область дії заперечення), закони комутативності, асоціативності та дистрибутивності, щоб побудувати кнф або днф, тотожності 8,9,12, щоб здійснити спрощення формули.

    Розглянемо приклад. Побудуємо кон’юнктивну нормальну форму для формули 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).

 

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

1. Які формули називаються рівносильними?

2. Що таке літера?

3. Що таке диз’юнкт? r-літерний диз’юнкт? одиничний диз’юнкт? порожній диз’юнкт?

4. Що таке контрарні літери?

5. Що таке тавтологічний диз’юнкт?

6. Що таке кон’юнкт?

7. Що таке кнф? днф?

8. Які формули логіки висловлень можна подати у кнф? у днф?

9. Які тотожності використовуються при побудові кнф (днф) формули?

10. Що таке суперечна множина диз’юнктів?

 

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

I. Подати формули у днф та кнф.

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

3. Ø(PÚØQ)Ù(S®T)                   4. (P®Q)®R

5. Ø(PÙQ)Ù(PÚQ)                                 6. PÚ(ØPÙQÙR)

7. Ø(P®Q)Ú(PÚQ)                      8. Ø(P®Q)

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

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

13. (P«Q)«(P«(Q«P))          14. (P®(Q®S))®((P®Q)®(Q®S))

15. S«P®(ØPÚS)                     16. QÙØS®(P«S)

17. RÙS®(P®ØQÚS)                18. (PÚØQ)ÚR®(SÙØP)

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

II. Довести тотожності 1-12.

ІІІ. Перевірити кожну з поданих рівностей шляхом перетворення обох її частин у одну й ту саму нормальну форму.

1. (P®Q)Ù(P®R) = (P®(QÙR))

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

3. PÙQÙ(ØPÚØQ) = ØPÙØQÙ(PÚQ)

4. PÚ(P®(PÙQ)) = ØPÚØQÚ(PÙQ)

5. (P«Q)«R = P«(Q«R)

 

ЛОГІЧНЕ СЛІДУВАННЯ

Ми бачили, що висловлення можна подавати за допомогою формул логіки висловлень. Часто нас цікавлять не окремі висловлення, а послідовності висловлень, що утворюють міркування, тобто такі послідовності тверджень, у яких останнє твердження є висновком з попередніх тверджень. Наведемо приклад міркування.

Якщо йде дощ, то люди користуються парасольками.

Іде дощ.

Отже, люди користуються парасольками.

Сукупність наведених трьох тверджень утворює міркування, у якому перші два твердження являються посилками, а останнє – висновком. Зазвичай твердження-висновок виділяється у міркуванні за допомогою слова «отже» (а також слів «таким чином», «з цього випливає» і т.п.).

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

Формула F називається логічним наслідком формул F₁,…,F_n (позначається F₁,…,F_n╞═F), якщо при кожній інтерпретації, при якій усі формули F₁,…,F_n  істинні, формула F також істинна. Говорять, що формули F₁,…,F_n є посилками F, а формула F випливає з F₁,…,F_n, або має місце логічне слідування формули F з формул F₁,…, F_n.

З попереднього означення випливає, що формула F є логічним наслідком формул F₁,…,F_n тоді й тільки тоді, коли кожна модель формул F₁,…,F_n є моделлю формули F.

Наведемо приклади логічного слідування.

1. Формула PÚQ є логічним наслідком формул P та Q. Дійсно, існує модель {P,Q} формул Р та Q, причому єдина. При інтерпретації {P,Q} формула PÚQ приймає істинносне значення 1. Отже, кожна модель формул P та Q є моделлю формули PÚQ, а це означає, що PÚQ є логічним наслідком P та Q.

2. Формула P®Q не є логічним наслідком формул ØQ та PÚQ, оскільки існує інтерпретація {P, ØQ}, при якій і ØQ, й PÚQ істинні, а P®Q хибна.

Ми можемо використовувати логічне слідування для подання міркування. Застосовуючи означення поняття логічного слідування ми також можемо перевіряти правильність міркування. Розглянемо приклад. Чи є логічно правильним таке міркування?

Дощ іде або спекотно. Якщо дощ не йде, то спекотно.

Якщо дощ іде, то не спекотно. Отже, якщо спекотно, то дощ не йде.

Можна сформулювати задачу інакше: чи випливає твердження «Якщо спекотно, то дощ не йде» з тверджень: «Дощ іде або спекотно», «Якщо дощ не йде, то спекотно», «Якщо дощ іде, то не спекотно»?

Щоб відповісти на це запитання, спочатку запишемо дані твердження як формули логіки висловлень. Нехай D означає «Дощ іде», а S означає «спекотно». Тоді початкова задача зводиться до перевірки того, чи є формула S®ØD логічним наслідком формул DÚS, ØD®S, D®ØS. Оскільки, як неважко перевірити, формула S®ØD істинна при тих інтерпретаціях, при яких істинні формули DÚS, ØD®S, D®ØS, то S®ØD є логічним наслідком цих формул. Отже, твердження «Якщо спекотно, то дощ не йде» випливає з поданих тверджень.

Поняття логічного слідування, суперечності та тавтологічності пов’язані між собою. Цей зв’язок визначає така теорема.

Теорема 1. Нехай F₁, F₂, …, F_n, F – формули.

1) F₁,F₂…,F_n╞═ F тоді й тільки тоді, коли формула F₁ÙF₂Ù…ÙF_n®F є тотожно істинною (тавтологією).

2) F₁,F₂,…,F_n╞═ F тоді й тільки тоді, коли формула F₁ÙF₂Ù…ÙF_nÙØF тотожно хибна (суперечна).

    Доведемо перше з поданих тверджень. Покажемо спочатку, що якщо F₁,F₂…,F_n╞═ F, то формула F₁ÙF₂Ù…ÙF_n®F є тотожно істинною. Нехай h – деяка інтерпретація формули F₁ÙF₂Ù…ÙF_n®F. Можливі два випадки: 1) h(F₁ÙF₂Ù…ÙF_n)=1, 2) h(F₁ÙF₂Ù…ÙF_n)=0.

Розглянемо перший випадок. З того, що h(F₁ÙF₂Ù…ÙF_n)=1, випливає, що h(F₁)=h(F₂)=…=h(F_n)=1, тобто інтерпретація h є моделлю формул F₁,F₂,…,F_n. Оскільки виконується F₁,F₂…,F_n╞═ F, то h є також моделлю формули F, тобто h(F)=1. Тоді h(F₁ÙF₂Ù…ÙF_n®F)=h(F₁ÙF₂Ù…ÙF_n)®h(F) =1®1=1, отже, формула F₁ÙF₂Ù…ÙF_n®F істинна при інтерпретації h.

У другому випадку маємо:

h(F₁ÙF₂Ù…ÙF_n®F) = h(F₁ÙF₂Ù…ÙF_n)®h(F) = 0®h(F)=1

незалежно від значення виразу h(F), тобто формула F₁ÙF₂Ù…ÙF_n®F приймає значення 1 при інтерпретації h.

Таким чином, за умови F₁,F₂…,F_n╞═ F формула F₁ÙF₂Ù…ÙF_n®F приймає значення 1 при кожній інтерпретації.

Тепер покажемо, що якщо формула F₁ÙF₂Ù…ÙF_n®F тотожно істинна, то F₁,F₂…,F_n╞═ F. Нехай h – модель формул F₁,F₂…,F_n. Тоді h(F₁ÙF₂Ù…ÙF_n) = 1. Оскільки F₁ÙF₂Ù…ÙF_n®F тотожно істинна, то h(F₁ÙF₂Ù…ÙF_n®F) =1. Але h(F₁ÙF₂Ù…ÙF_n®F) = h(F₁ÙF₂Ù…ÙF_n)®h(F) = 1®h(F) = 1, звідки випливає, що h(F)=1. Отже, кожна модель формул F₁,F₂…,F_n є моделлю формули F, тобто, F₁,F₂…,F_n╞═ F. Твердження доведено.

 

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

1. За якої умови можна стверджувати, що формула F є логічним наслідком формул F₁,…,F_n?

2. Сформулюйте достатні умови того, що формула F є логічним наслідком формул F₁,…,F_n.

3. Сформулюйте необхідні умови того, що формула F є логічним наслідком формул F₁,…,F_n.

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

І. Задано сукупність формул. Перевірити, чи є у цій сукупності формула, що являється логічним наслідком інших.

1. P®Q, P®R, Q®R                          2. P®(Q®R), P®R, Q

3. P®Q, RÚP®RÚQ                        4. P®(Q®R), Q®(P®R)

5. P®(Q®R), P®(P®R), P®Q         6. P®Q, P®R, P®(Q®R)

7. Ø(PÙQ), (Q®ØP)                            8. ØP®ØQ, Q®P

9. PÙR®QÙS, P®Q, R®S                 10. P®(Q®R), PÙQ®R.

ІІ. Довести п.2 теореми 1.

 

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

Поделиться: