Математична логіка (стр. 2 из 8)
Приклад 1.8. Знайдемо кон'юнкцію висловлювань pта g, де р є висловлюванням "Сьогодні п'ятниця", а g - висловлюванням "Сьогодні падає дощ". Кон'юнкцією цих висловлювань є висловлювання "Сьогодні п'ятниця і сьогодні падає дощ". Це висловлювання істинне у дощову п'ятницю і фальшиве не в п'ятницю або у не дощову п'ятницю.
Приклад 1.9. Що є диз'юнкцією висловлюваньg та p, які визначені у прикладі 1.8? Диз'юнкцією висловлювань p та g, є висловлювання p
g "Сьогодні п'ятниця або падає дощ". Це висловлювання істинне в будь-яку п'ятницю або в дощовий день. Дощова п'ятниця також долучається. Це висловлювання фальшиве тільки в одному випадку - у недощову п'ятницю.Логічна зв'язка "диз'юнкція" відповідає одному з двох способів уживання слова "або" в українській мові. Диз'юнкція істинна, якщо істинне принаймні одне з двох висловлювань. Наприклад, її використовують у реченні "Лекції з логіки можуть відвідувати студенти, які прослухали курси математичного аналізу або дискретної математики". Зміст цього речення полягає в тому, що лекції можуть відвідувати як студенти, які прослухали обидва курси, так і ті студенти, які прослухали тільки один з цих курсів. Інший спосіб використання диз'юнкції- це альтернативне "або". Для прикладу, така диз'юнкція відповідає реченню "Лекціїз логіки можуть відвідувати студенти, які прослухали один з двох курсів — математичний аналіз або дискретну математику". Зміст цього речення полягає в тому, що студенти, які прослухали обидва ці курси, вже не повинні слухати лекцій з логіки. Аналогічно, якщо в меню вказано "Закуску або салат подають з першою стравою", то це майже завжди означає, що з першою стравою подадуть або закуску, або салат, але не обидві страви. Тобто, це альтернативне, а не звичайне "або", його позначають "
". Значення істинності альтернативного "або" наведено у табл. 1.2.Таблиця 1.2
| p | g | p g |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
Імплікацію, як логічну зв'язку, ще називають умовним реченням. Щоб зрозуміти значення істинності імплікації, треба розуміти її як зв'язок обов'язкового та очікуваного. Для цього розглянемо речення "Якщо ви виконаєте всі завдання, то отримаєте відмінну оцінку". Це означає, що якщо студенти виконали всі завдання, то вони отримають відмінну оцінку. Якщо ж студенти не виконали всіх завдань, то вони можуть отримати оцінку "відмінно", а можуть і не отримати її, залежно від інших обставин. Однак, якщо студенти зробили всі завдання, але викладач не поставив оцінку "відмінно", то студенти відчуватимуть себе ображеними. Останній випадок відповідає ситуації, коли p істинне, а g фальшиве в імплікації p→g , де p- припущення імплікації "Ви виконаєте всі завдання", а g - її висновок "Ви отримаєте відмінну оцінку".
Визначення імплікації дещо інше від розуміння її в природній мові, де її вживають для вказання причинно-наслідкового зв'язку. Для прикладу, речення "Якщо буде сонячно, то ми підемо на пляж" -умовне, яке вживають у звичайній мові. Це речення залишається істинним до того моменту, коли настане сонячний день, але ми не підемо на пляж. За означенням імплікації умовне речення "Якщо сьогодні п'ятниця, то 2+3=5" істинне, оскільки її висновок істинний. При цьому значення істинності припущення імплікації тут не має відношення до висновку. Імплікація "Якщо сьогодні п'ятниця, то 2+3=6" істинна щодня, крім п'ятниці, хоча 2+3=6 фальшиве. Останні дві імплікації ми не вживаємо у природній мові (хіба що, як жарт), оскільки немає змістовного зв'язку між припущенням та висновком у кожному з наведених умовних речень.
Конструкція IF-THEN, яку використовують в алгоритмічних мовах, відрізняється від імплікації у логіці. В алгоритмічних мовах цю конструкцію використовують у вигляді "ІF р ТНЕNS ", де р висловлювання, а S- програмний сегмент, що складається з одного або багатьох операторів. Програмний сегмент S виконують, якщо р істинне, та не виконують, якщоp фальшиве.
Для знаходження значення істинності складного висловлювання потрібно надати значення істинності всім атомам, які містить формула. Надання значень істинності всім атомам формули називаютьїї інтерпретацією. У разі обчислення значень істинності формул, які зображають складні висловлювання, потрібно знаходити значення логічних зв'язок згідно з правилами, визначеними в табл. 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 g) | (р~ ) | (р g)→(р~ ) |
| 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 |
Приклад 1.11. Розглянемо формулу ((р→g)
p)→g. Атомами в цій формулі є р та g, а формула має 22=4 інтерпретації. Значення істинності заданої формули наведено в табл. 1.4. Задана формула істинна в усіх її інтерпретаціях, тобто вона-тавтологія.Таблиця 1.4
| p | g | (р→g) | (р→g) p | ((р→g) p)→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 робимо висновок, що задана формула фальшива в усіх інтерпретаціях, тобто заперечувана.