Логіка висловлень. Алфавіт і формули. Інтерпретація формул ЛВ. Нормальні форми в ЛВ. Логічні наслідки в ЛВ

3.2 1 Мета заняття

Повторити базові поняття логіки висловлень, побудови та інтерпретації ППФ, приведення до нормальних форм у ЛВ, опрацювати поняття логічного наслідку шляхом вирішення задач засобами ЛВ.

3.2.2 Методичні вказівки з організації самостійної роботи студентів

При вивченні теми рекомендуємо використовувати наступну літературу: [4, c.49-57; 6, c.16-34, 9, c.165-170, 8, 20,21].

Математична логіка розглядає мови, основна ціль яких - забезпечити символізм (систему формальних позначень) для міркувань, що зустрічаються не тільки в математиці, але й у повсякденному житті. Найпростішою математичною логікою є логіка висловлювань, більш загальною системою - логіка предикатів або логіка першого порядку. Висловлення - це оповідальна пропозиція, що може бути або істинною, або хибною, але не тим і іншим одночасно. Приклади висловлень: ”Сніг білий”, ”Цукор - вуглеводень”. ”Істина” або ”хибність”, приписана деякому висловленню, називається істинним значенням цього висловлення. Звичайно “істину” позначають через 1, ”хибність” - через 0. Висловлення можуть позначатися: P Сніг білий; Q Цукор - вуглеводень.

Символи P, Q і т.д., що використовуються для позначення висловлень, називаються атомарними формулами або атомами. З атомарних висловлень будують складні висловлення, використовуючи п'ять логічних зв’язок: (не), заперечення; (і), кон’юнкція (а, але, а також); (або), диз'юнкція; (якщо,..., то), імплікація; (тоді і тільки тоді, коли), еквівалентність. Іноді може вживатися (або... або), строга диз'юнкція або додавання по модулю 2 (mod2). Ці зв’язки можна використовувати для побудови більш складних складених висловлень шляхом повторного застосування зв’язок до вже наявних висловлень.

У ЛВ правильно побудовані формули (ППФ) визначаються рекурсивно в такий спосіб [6]:

1) атом це формула (P,Q,....);

2) якщо P-формула, то () - також формула;

3) якщо P і Q -формули, то також

формули;

4) ніяких формул, крім породжених застосуванням зазначених вище правил, немає.

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

і вимагаючи, щоб зв’язка з більшим рангом завжди мала більшу область дії. Таким чином, означає .
Нехай G і H - дві атомарні формули. Тоді істинностні значення формул пов'язані з істинностними значеннями формул G і H так, як це показано у табл.3.1:

Таблиця 3.1 - Істинностні значення для , , , , ,

G H
0 0
0 1
1 0
1 1

Ґрунтуючись на цій таблиці, зручно описувати способи обчислення істинностних значень формули за істинними значеннями атомів, що входять у цю формулу.

Наприклад, для формули маємо: нехай Р=1,Q=0,R=0, тоді

Приписування істинностних значень атомам, що входять у формулу, називається інтерпретацією формули. Кожному з атомів можна приписати 0 або 1. Тоді, якщо у формулі є n атомів, то вона має інтерпретацій. Таблицю 5.1, у якій зазначені істинностні значення формули Р при вселяких істинностних значеннях атомів, що зустрічаються в Р, називають істинностною таблицею формули Р.

Кажуть, що формула Р істинна при деякій інтерпретації, тоді і тільки тоді, коли Р одержує значення 1 у цій інтерпретації, у противному випадку говорять, що Р хибна при цій інтерпретації. Формула ЛВ загальнозначуща тоді і тільки тоді, коли вона істинна при всіх можливих інтерпретаціях. Формула ЛВ суперечлива (або нездійсненна) тоді і тільки тоді, коли вона хибна при всіх своїх інтерпретаціях. Формула несуперечлива (або здійсненна) тоді і тільки тоді, коли вона не є суперечливою.

Якщо формула F істинна при інтерпретації I, то кажуть, що I задовольняє F, або F виконана в інтерпретації I. З іншого боку, якщо формула F хибна при інтерпретації I, то кажуть, що I спростовує F, або F спростовується в I. Наприклад, формула виконана в інтерпретації але спростовується в інтерпретації Коли інтерпретація I задовільняє формулі F, I називається також моделлю F.

Доведення загальнозначимості або суперечливості формул - дуже важлива задача. У ЛВ через кінцевість числа інтерпретацій шляхом повного перебору всіх можливих інтерпретацій завжди можна вирішити, загальнозначуща (суперечлива) формула чи ні.

Часто буває, необхідно перетворити формули логіки висловлень із однієї форми в іншу, особливо в так звану “нормальну форму”. Це досягається шляхом еквівалентних перетворень формул. Кажуть, що дві формули F і G еквівалентні або, що F еквівалентна G (позначається F=G), тоді і тільки тоді, коли істинностні значення F і G збігаються при всіх інтерпретаціях. Для здійснення еквівалентних перетворень довільних формул логіки висловлень використовуються наступні тотожності (законі логіки висловлень):

1)

2)

3) закони комутативності:

4) закони асоціативності:

5) закони дистрибутивності:

6) закони ідемпотентності:

7) закони елімінації:

8) закон подвійного заперечення:

9) закон виключеного третього:

де U будь-яка загальнозначуща формула;

10) закон суперечності

11) тотожності з константами

12) закони де Моргана

Закони де Моргана узагальнюються на випадок n атомів:

_.

Варто пам'ятати, що у формулюванні перерахованих еквівалентних співвідношень (законів логіки висловлень) змінні А,В, і т.д. позначають не конкретні висловлення, а формули. У зазначені тотожності можна підставляти будь-які формули, і тотожності будуть справедливі. Зазначені закони і тотожності використовуються для еквівалентних перетворень формул з метою їхнього спрощення або одержання так званих нормальних форм.

Літера є атом або заперечення атома. Формула F перебуває в кон’юнктивній нормальній формі (КНФ), якщо вона має вигляд: F=F₁ÙF₂Ù...ÙF_n, де кожна з F₁, F₂,..., F_n є диз'юнкція літер. Формула F перебуває в диз'юнктивній нормальній формі (ДНФ), якщо вона має вигляд: F=F₁ÚF₂Ú...ÚF_n, де кожна з F₁,F₂,...,F_n є кон’юнкція літер. Будь-яка формула може бути перетворена в нормальну форму. Це легко досягається використанням законів ЛВ. Процедура перетворення формул у нормальні форми описується наступним алгоритмом:

Крок 1. Використовуємо закони:

F G=(F G)Ù(G F),

F G=ØFÚG;

щоб усунути (елімінувати) логічні зв’язки , .

Крок 2. Кілька разів використовуємо закон ØØF=F та закони де Моргана:

Ø(FÚG)=ØFÙØG,

Ø(FÙG)=ØFÚØG,

щоб перенести знак заперечення безпосередньо до атомів.
Крок 3. Кілька разів використовуємо дистрибутивні закони:

FÚ(GÙH)=(FÚG)Ù(FÚH),

FÙ(GÚH)=(FÙG)Ú(FÙH)

та інші законі, щоб одержати нормальну форму.

Поряд із задачею переходу від формули висловлення до його таблиці істинності найчастіше потрібно виконати зворотне: по заданій таблиці істинності записати формулу, яка передавала б ту ж відповідність. Для цього використовується досконаладиз'юнктивна нормальна форма (ДДНФ) і досконала кон’юнктивна нормальна форма (ДКНФ).

Конституента 1 - це кон’юнкція, у якій по одному разу присутні літери всіх атомів, наявних у формулі. Властивості конституенти1:1) конституента 1 дорівнює одиниці при єдиній інтерпретації, при якій і початкова формула також приймає одиничне значення; 2) кон’юнкція будь-якої кількості конституент 1 від тих самих змінних дорівнює нулю. Конституента 0 - це диз'юнкція, у яку входять по одному разу літери всіх атомів, наявних у формулі. Властивості конституенты 0:1) конституента 0 приймає нульове значення при єдиній інтерпретації, при якій початкова формула також дорівнює нулю;
2) диз'юнкція будь-якого числа конституент 0 дорівнює 1.

ДДНФ формули G - це диз'юнкція всіх її конституент 1. ДКНФ формули G - це кон’юнкція всіх її конституент нуля. Позначимо через , де запис атома, узятого іззапереченням, або без нього, тобто: при s= 1 .Справедливе наступне правило запису ДДНФ по таблиці істинності:

1) для кожної інтерпретації, де формула дорівнює одиниці, виписуємо відповідну конституенту одиниці. Як показники при атомах беремо істинні значення атомів у даній інтерпретації;

2) поєднуємо отримані значення конституенти одиниць диз'юнкцією. Одержуємо ДДНФ. Бажано виписувати конституенти 1 у порядку зростання номерів відповідних їм інтерпретацій.

Правило запису ДКНФ по таблиці істинності формулюється аналогічно. Однак, на першому кроці, при формуванні конституент в якості показників при атомах беруть заперечення істинних значень атомів у відповідній інтерпретації.

Для доведеннялогічних наслідків у логіці висловлень необхідно засвоїти наступні основні поняття. У математиці, як і у звичайному житті, часто потрібно вирішити, чи випливає одне твердження з декількох інших. Це приводить до поняття “логічний висновок”. Нехай дано формули і формула G. Говорять, що G є логічний наслідок формул (або G логічно випливає з ) тоді і тільки тоді, коли для всякої інтерпретації I, у якій істинна, G також істинна. називаються аксіомами (або постулатами або посилками) G.

Варто знати й уміти користуватись наступними теоремами про виведення логічного наслідку [6].

Теорема 1. Нехай дано формули і формула G. Тоді G є логічним наслідком тоді і тільки тоді, коли загальнозначуща.

Теорема 2. Нехай дано формули і формула G. Тоді G є логічним наслідком тоді і тільки тоді, коли суперечлива.

Теореми 1 і 2 дуже важливі. З них випливає: доведення того, що окрема формула є логічним наслідком кінцевої множини формул, еквівалентне доведенню того, що деяка пов'язана з ними формула загальнозначуща або суперечлива. Якщо G є логічним наслідком формул , то формула називається теоремою, а G називається також логічним висновком теореми. У математиці, так само, як і в інших областях, багато проблем можуть бути сформульовані як проблеми доведення теорем.

3.2.3 Контрольні запитання і завдання

1. Логіка висловлень.

2. Висловлення, логічні зв’язки, логічні парадокси.

3. Складені висловлення.

4. Істинностні значення і функції.

5. Формули ЛВ. Інтерпретації формул ЛВ. Таблиці істинності формул ЛВ.

6. Загальнозначущі, суперечливі та здійсненні формули ЛВ.

7. Навести приклад утворення складного висловлення із простих на прикладі якої-небудь теореми.

8. Записати наступні висловлення за допомогою формул:

− “Дане відношення є відношення еквівалентності тоді і тільки тоді, коли воно рефлексивне, симетричне і транзитивне”;

− “Якщо вологість настільки велика, то або після обіду, або ввечері буде дощ”.

9. Дано атомарні висловлення: P Йому потрібен лікар, Q Йому потрібен адвокат, R З ним стався нещасний випадок, S Він хворий, U Він поранений. Записати у вигляді тверджень української мови наступні формули:

a)

b)

c)

d)

e)

10. Для кожної з наступних формул визначіть, чи вірно, що вона загальнозначуща, незагальнозначуща, суперечлива, несуперечлива або має деяку комбінацію цих властивостей:

a)

b)

c)

d)

e)

f)

g)

h)

i)

j)

k)

l)

m)

11.Еквівалентні співвідношення в логіці висловлень.

12. Закони ЛВ.

13. Конституенти одиниці. Конституенти нуля.

14. ДНФ, ДДНФ, КНФ, ДКНФ.

15. Перевірте еквівалентність наступних формул, перетворюючи формули по обидва боки від знака = до однієї й тієї ж нормальної форми:

16. Визначити, чи є наступні формули висловлень загальнозначущими, суперечливими або здійсненними:

17. Перейти від формули булевої функції до її ДДНФ.

18. Перейти від формули до таблиці булевої функції через ДДНФ та ДКНФ.

Логічний висновок в ЛВ.

19. Теореми 1 і 2 про встановлення логічного висновку.

20. Методи встановлення істинності або суперечливості формул ЛВ.

21. Доведіть, що (ØQ ØP) є логічним висновком (P Q).

22. Якщо конгрес відмовляється прийняти нові закони, то страйк не закінчиться, крім випадку, коли він триває більше року і президент фірми піде у відставку. Припустимо, що конгрес відмовляється діяти, страйк закінчується і президент фірми не йде у відставку. Чи тривав страйк більше року?

23. Дано ствердження:

F₁: P S,

F₂: S U,

F₃: P,

G: U.

Чи є G логічним висновком F₁,F₂ і F₃?

24. Покажіть, що Q є логічний висновок (P Q) і P. Це так зване правило модус поненс (modus ponens).

3.2.4 Приклади аудиторних і домашніх задач

Приклад 1. Формалізувати засобами ЛВ речення: ”Якщо вологість велика і температура висока, то ми не почуваємо себе добре”.

Розв’язання. Виділимо в даному реченні атомарні висловлення:

Р Вологість велика; Q Температура висока; C Ми почуваємо себе добре. Тоді почасткове речення можна записати у вигляді складеного висловлення: або

Приклад 2. Записати у вигляді формули ЛВ наступну теорему: ”Якщо неперервна на інтервалі I, і якщо то тоді на існує хоча б одна точка така, що

Розв’язання. Виділимо атомарні висловлення:

X неперервна на інтервалі I;

Y

Z

T на існує хоча б одна точка ;

K

Формула даного складного висловлення запишеться: .

Приклад 3. Заповніть таблицю істинності для формули ЛВ:

Розв’язання. Атоми цієї формули ¾ Р і Q. Отже, формула має інтерпретації. Істинностні значення G при всіх її інтерпретаціях наведені в табл.3.2.:

Таблиця 3.2 – Таблиця істинності для

P Q
0 0
0 1
1 0
1 1

Як бачимо, формула G істинна при всіх інтерпретаціях, тобто загальнозначуща. Таку формулу ще називають тавтологією.

Приклад 4. Отримати ДНФ для формули .

Розв’язок. Скористаємося алгоритмом приведення довільної формули ЛВ до нормальної форми:

Крок 1. Позбуваємося від операції імплікації:

Крок 2. Використовуючи закони де Моргана, наближаємо всі заперечення безпосередньо до атомів:

Крок 3. Використовуємо дистрибутивний закон, розкриваємо дужки, використовуємо закон подвійного заперечення, зводимо подібні члени, отримуємо ДНФ:

Приклад 5. Отримати КНФ для формули

Розв’язок. Застосовуємо той же алгоритм.

Крок 1.

Крок 2.

Крок 3.

Приклад 6. Представити дану формулу в ДКНФ:

Розв’язок.

Приклад 7. По даній таблиці істинності записати ДДНФ і ДКНФ формули висловлення.

A B C	F(A,B,C)
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Розв’язок. Використовуємо правило одержання ДНФ по таблиці істинності:

Крок 1. Виписуємо всі конституенти 1 для кожної інтерпретації, де F=1. Як показники при атомах беремо істинні значення атомів у даній інтерпретації. Одержуємо наступні конституенты 1:

Крок 2. Об'єднуючи отримані конституенти 1 диз'юнкціями, одержуємо ДДНФ:

Тепер одержимо подання тієї ж формули ЛВ у вигляді ДКНФ:

Крок 1. Виписуємо всі конституентни 0 для кожної інтерпретації, де F=0. Як показники при атомах беремо заперечення значень атомів у даній інтерпретації. Одержуємо наступні конституенти 0:

Крок 2. Об'єднуючи отримані конституенты 0 кон’юнкціями, одержуємо СКНФ:

Приклад 8. Дано формули логіки висловлень: F₁

Показати, що G є логічним висновком F₁ і F₂.

Розв’язок. Метод 1. Використовуємо метод таблиць істинності, щоб показати, що G істинна в кожній моделі формули (Коли інтерпретація I задовільняє формулі F, I називається моделлю F). Із табл. 3.3 бачимо, що є тільки одна модель для а саме {ØP, ØQ}.

Таблиця 3.3 - Таблиця істинності і ØP.

P Q	P Q	ØQ		ØP
0 0 0 1 1 0 1 1

Формула ØP істинна в цій моделі. Таким чином, по визначенню логічного виведення робимо заключення, що ØР є логічний висновок Метод 2. Використовуємо теорему 1. Це можна зробити шляхом розширення таблиці істинності в табл. 3.3, тобто шляхом обчислення істинностних значень формули Табл. 3.5 показує, що

істинна при всіх інтерпретаціях.

Таблиця 3.4 - Таблиця істинності для (

P Q		ØQ
0 0 0 1 1 0 1 1

Отже, загальнозначуща і, відповідно до теореми 1, ØP є логічним висновком і ØQ.

Ми можемо також довести загальзначимість формули шляхом перетворення її в кон’юнктивну нормальну форму:

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

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

=Ø((ØPÙØQ)ÚЛ)ÚØP=Ø(ØPÙØQ)ÚØP=(PÚQ)ÚØP=

=QÚ (PÚØP)=QÚU=U.

Таким чином, P загальнозначуща.

Метод 3. Використовуємо теорему 2. У цьому випадку ми доведемо, що формула ((P Q)ÙØQ)Ù(Ø(ØP))=(P Q)ÙØQÙP суперечлива. Як і в методі 2, можна використовувати метод таблиць істинності, щоб показати, що (P Q)ÙØQÙP хибна в кожній інтерпретації. Із табл.5.5 бачимо, що (P Q)ÙØQÙP суперечлива і, відповідно до теореми 2, ØP є логічним висновком формул (P Q) і ØQ.

Таблиця 3.5 – Таблиця істинності для (P Q)ÙØQÙP

P Q	P Q	ØQ	(P Q)ÙØQÙP
0 0 0 1 1 0 1 1

Ми можемо також довести суперечливість формули (P Q)ÙØQÙP шляхом її перетворення в диз'юнктивну нормальну форму:

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

=(ЛÙØQ)Ú(ЛÙP)=ЛÚЛ=Л. Таким чином, (P Q)ÙØQÙP суперечлива.

Приклад 9. Покажемо застосування логіки висловлювань при розв’язанні задач у словесному формулюванні. Припустимо, що якщо конгрес відмовляється прийняти нові закони, то страйк не закінчиться, якщо тільки він не триває більше року і президент фірми не йде у відставку. Чи закінчиться страйк, якщо конгрес відмовляється діяти і страйк тільки що почався?

Розв’язок. Спочатку перетворимо ствердження в символи:

Р: Конгрес відмовляється діяти.

Q: Страйк закінчується.

R: Президент фірми йде у відставку.

S: Страйк триває більше року.

Тоді факти, дані в прикладі, можуть бути представлені наступними формулами:

F₁: (P (ØQÚ(RÙS))) Якщо конгрес відмовляється прийняти нові закони, то страйк не закінчиться, якщо він не триває більше року і президент фірми не йде у відставку.

F₂: P Конгрес відмовляється діяти.

F₃: ØS Страйк тільки що почався.

Чи можна з фактів F₁, F₂ і F₃ зробити висновок, що страйк не закінчиться, тобто чи можна показати, що ØQ є логічним висновком F₁, F₂ і F₃? По теоремі 1 це еквівалентно тому, що ((P (ØQÚ(RÙS)))ÙPÙØS) ØQ - загальнозначуща формула. Істинностні значення зазначеної формули при всіх інтерпретаціях наведені в табл.3.6.

Таблиця 3.6 – Істинностна таблиця для (F₁ Ù F₂ Ù F₃) ØQ,

де F₁ (P (ØQÚ(RÙS))), F₂ Р, F₃ ØS

P	Q	R	S	F1	F2	F3	ØQ	(F1ÙF2ÙF3) ØQ

Із табл 3.6 бачимо, що не існує інтерпретації, при якій дана формула хибна. Отже, формула ((P (ØQÚ(RÙS)))ÙPÙØS) ØQ загальнозначуща. Тому ØQ є логічним висновком F₁,F₂ і F₃, тобто ми можемо отримати заключення ØQ з F₁,F₂ і F₃. Отже, страйк не закінчиться.

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

Ми показали використання методу істинностних таблиць і методу множення для доведення загальзначимості (або суперечливості).