Математична логіка (стр. 3 из 8)
Таблиця 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 | | g | (p→g)~( 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 |
Приклад 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. | Закони комутативності | а) р g=g pб) р g=g p |
| 2. | Закони асоціативності | а) (р g) r=р (g r)б) (р g) r=р (g r) |
| 3. | Закони дистрибутивності | а) р (g r)=(p g) (p r)б) р (g r)=(p g) (p r) |
| 4. | Закон протиріччя | р =F |
| 5. | Закон виключеного третього | р =T |
| 6. | Закон подвійного заперечення |  =р |
| 7. | Закони ідемпотентності | а)р p=pб) p p=p |
| 8. | Закони де Моргана | а)  = б)  = |
| 9. | Закони поглинання | а) (р g) р=рб) (р g) p=р |
| 10. | Співвідношёення для сталих | а) p T=Tб) p T=pв) р F=pг) p F=F |
Наведені еквівалентності можна перевірити побудовою таблиць істинності. Приклад 1.14 свідчить, що імплікація не комутативна. Покажемо, як застосувати закони логіки висловлювань для доведення еквівалентності формул.
Приклад 1.15. Застосуванням законів логіки висловлювань доведемо еквівалентність формул р→(g
r) та (p→g) (p→r). Випишемо послідовність перетворень та запишемо біля кожного рядка назву застосованого закону або правила.1.
(g r) - правило вилучення імплікації з першої із заданихформул.2. (
g) ( r) - закон дистрибутивності 9б для формули 1.3. (р→g)
(p→r) - правило введення імплікації для формули 2.Отже, задані формули еквівалентні: р→(g
r) та (p→g) (p→r).Приклад 1.16. Застосуванням законів логіки висловлювань доведемо еквівалентність формул р→gта
→ . Цю еквівалентність називають правилом контрапозиції.