85764 (612568), страница 2
Текст из файла (страница 2)
Для знаходження значення істинності складного висловлювання потрібно надати значення істинності всім атомам, які містить формула. Надання значень істинності всім атомам формули називають її інтерпретацією. У разі обчислення значень істинності формул, які зображають складні висловлювання, потрібно знаходити значення логічних зв'язок згідно з правилами, визначеними в табл. 1.1. Послідовність обчислень визначають парами дужок, які містить складне висловлювання. Якщо формула має n атомів, то існує 2n способів надати значення істинності її атомам, тобто така формула має 2n інтерпретацій, а всі її значення можна звести в таблицю істинності з 2n рядками. Формулу, яка містить n атомів, називають n-місною. У разі n=1 формула одномісна.
Формулу f називають виконаною , якщо існує принаймні одна інтерпретація, у якій f набуває значення Т. У такому разі кажуть, що формула f виконується (або виконана) у цій інтерпретації.
Приклад 1.10. Розглянемо формулу (р
g)→(р~
). Оскільки кожному з атомів р, g та r можна надати 2 значення - F або Т, то задана формула має 23=8 інтерпретацій. Для прикладу, обчислимо значення істинності заданої формули для значень істинності атомів p, g та r, які дорівнюють F, Т та F, відповідно. Це задає одну з інтерпретацій формули. Тоді (р g) має значення F, оскільки р фальшиве; має значення Т, оскільки r фальшиве; (р~r) фальшиве, оскільки р фальшиве, а істинне; нарешті ((р g)→(р~ )) істинне, оскільки (р g) фальшиве. Отже, задана формула виконується у цій інтерпретації, оскільки набуває значення Т. Значення істинності формули (р g)→(р~ ) у всіх її інтерпретаціях наведено в табл. 1.3.
Формулу f логіки висловлювань називають загальнозначущою, або тавтологією, якщо вона виконується в усіх інтерпретаціях (позначають ╞f). Формулу, фальшиву в усіх її інтерпретаціях, називають заперечуваною, невиконанною, або протиріччям.
Оскільки кожна формула логіки висловлювань має скінченну кількість інтерпретацій, то завжди можна перевірити її загально-значущість чи заперечуваність знаходженням її значень істинності в усіх інтерпретаціях.
Таблиця 1.3
| p | g | r | | (p | (р~ | (р |
| T | T | T | F | T | F | F |
| T | T | F | T | T | T | T |
| T | F | T | F | F | F | T |
| T | F | F | T | F | T | T |
| F | T | T | F | F | T | T |
| F | T | F | T | F | F | T |
| F | F | T | F | F | T | T |
| F | F | F | T | F | F | T |
g) Приклад 1.11. Розглянемо формулу ((р→g) p)→g. Атомами в цій формулі є р та g, а формула має 22=4 інтерпретації. Значення істинності заданої формули наведено в табл. 1.4. Задана формула істинна в усіх її інтерпретаціях, тобто вона - тавтологія.
Таблиця 1.4
| p | g | (р→g) | (р→g) | ((р→g) |
| T | T | T | T | T |
| T | F | F | F | T |
| F | F | T | F | T |
| F | F | T | F | T |
Приклад 1.12. Розглянемо формулу (р→g) (р 
). З табл. 1.5 робимо висновок, що задана формула фальшива в усіх інтерпретаціях, тобто заперечувана.
Таблиця 1.5
| p | g | (р→g) | | р | (р→g) |
| T | T | T | F | F | F |
| T | F | F | T | T | F |
| F | T | T | F | F | F |
| F | F | T | T | F | F |
1.2. Закони логіки висловлювань
Формули f та g еквівалентні, або рівносильні, тотожні (позначають f=g), якщо значення істинності формул f та g збігаються в усіх інтерпретаціях цих формул. Властивість еквівалентності формул f та g можна сформулювати у вигляді такого твердження.
Теорема 1.1. Формули f та g еквівалентні тоді й лише тоді, коли формула (f~g) загальнозначуща, тобто ╞f~g.
Приклад 1.13. За допомогою таблиці істинності покажемо, що p→g=
g. Результат розв'язування задачі наведено у таблиці 1.6.
Таблиця 1.6
| p | g | p→g | | | (p→g)~( |
| T | T | T | F | T | T |
| T | F | F | F | F | T |
| F | T | T | T | T | T |
| F | F | T | T | T | T |
gПриклад 1.14. За допомогою таблиці істинності покажемо, що p→g≠g→p. Результат розв'язування задачі наведено у табл. 1.7.
Таблиця 1.7
| p | g | p→g | g→p | (p→g)~(g→p) |
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | T | F | F |
| F | F | T | T | T |
Розглянемо еквівалентні формули, які визначають правила перетворень. Такі еквівалентності називають законами логіки висловлювань. Перетворення виконують заміною деякої формули у складі іншої формули на еквівалентну їй формулу. Цю процедуру повторюють доти, поки не буде отримано формулу в потрібній формі. Основні закони логіки висловлювань наведено у табл. 1.8.
Наступні два правила дозволяють вилучати зв'язки еквівалентності та імплікації з формул і перетворювати їх у формули, які таких зв'язок не містять: р~g=(p→g) (g→p) та p→g= g (див. приклад 1.13). Ці правила також можна використовувати для введення імплікації та еквівалентності.
Таблиця 1.8
| Назва законів | Формулювання законів | |
| 1. | Закони комутативності | а) р б) р |
| 2. | Закони асоціативності | а) (р б) (р |
| 3. | Закони дистрибутивності | а) р б) р |
| 4. | Закон протиріччя | р |
| 5. | Закон виключеного третього | р |
| 6. | Закон подвійного заперечення | |
| 7. | Закони ідемпотентності | а) р б) p |
| 8. | Закони де Моргана | а) б) |
| 9. | Закони поглинання | а) (р б) (р |
| 10. | Співвідношёення для сталих | а) p б) p в) р г) p |
=р
=
=Наведені еквівалентності можна перевірити побудовою таблиць істинності. Приклад 1.14 свідчить, що імплікація не комутативна. Покажемо, як застосувати закони логіки висловлювань для доведення еквівалентності формул.
Приклад 1.15. Застосуванням законів логіки висловлювань доведемо еквівалентність формул р→(g r) та (p→g) (p→r). Випишемо послідовність перетворень та запишемо біля кожного рядка назву застосованого закону або правила.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
