Курсовая работа: Математична логіка
Формулу 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)
)
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 |
p
p)→gПриклад 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
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 |
g=g
p
g=g
p
g)
r=р
(g
r)
g)
r=р
(g
r)
(g
r)=(p
g)
(p
r)
(g
r)=(p
g)
(p
r)
=F
=T
=р
p=p
p=p
=
=
g)
р=р
g)
p=р
T=T
T=p
F=p
F=F
