 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Логічні зв’язки
|
|
Розглянемо основні логічні зв’язки:
³ заперечення висловлювання p, його позначають Ø p (або 
) та виражають сполучником «не»;
висловлювання Ø p є істинним лише у випадку, коли p хибне;
³ кон’юнкція двох висловлювань p та q, її позначають p & q або p Ù q та виражають сполучником «і»;
висловлювання p Ù q вважається істинним тоді й лише тоді, коли такими є p та q;
³ диз’юнкція двох висловлювань p та q, її позначають p Ú q та виражають сполучником «або»;
висловлювання p Ú q є істинним тоді й лише тоді, коли таким є принаймні одне з висловлювань p чи q;
³ альтернативне «або» двох висловлювань p та q, його позначають p Å q;
висловлювання p Å q є істинним тоді й лише тоді, коли p та q мають різні логічні значення, і хибним у протилежному випадку;
³ імплікація двох висловлювань p та q, її позначають p ® q та виражають сполучником «… достатньо для …» «якщо…то…»,;
висловлювання p ® q є хибним лише у випадку, коли p істинне, а q хибне;
³ еквівалентність двох висловлювань p та q, її позначають p ~ q та виражають сполучником «тоді й лише тоді»;
висловлювання p ~ q є істинним лише у випадку, коли p та q мають однакові логічні значення, і хибним у протилежному випадку.
Приклад2.3. Розглянемо висловлювання:
1. Я отримав оцінку «відмінно» і мав хороший настрій.
2. Сьогодні весело або падає дощ.
У першому прикладі складне висловлювання утворене з використанням логічної зв’язки – кон’юнкції («і») та атомарних формул: «я отримав оцінку «відмінно»», «я мав хороший настрій».
У другому прикладі складна формула складається з атомів «сьогодні весело», «падає дощ» та диз’юнкції («або»). ▲
Для того, щоб визначити значення істинності формули, зручно використовувати таблиці істинності, що отримують значення істинності формул за значеннями істинності атомарних формул у цих формулах.
Приклад 2.4. Таблиця істинності семантики введених логічних зв’язок:
Таблиця 2.1
Таблиця істинності логічних зв’язок
| p | q | p Ù q | p Ú q | p Å q | Ø p | p ® q | p ~ q |
| T | T | T | T | F | F | T | T |
| T | F | F | T | T | F | F | F |
| F | T | F | T | T | T | T | F |
| F | F | F | F | F | T | T | T |
!Увага. Логічну зв’язку імплікацію варто розглядати як умову достатності. Розглянемо висловлювання p ® q, де p – висловлювання “падає дощ”, а q – “трава мокра”. Трава може бути мокрою із різних причин – через опади роси або полита водою. Тобто можуть бути ситуації, коли трава мокра, але дощ не падає. Тому дощ є лише достатньою умовою для того, щоб трава були мокра (але не необхідною). Якщо подивитись значення істинності p ® q у таблиці вище, то очевидно, що тільки висловлювання “падає дощ і трава не мокра” є хибним. Усі решта висловлювання є істинними, тому що теоретично вони можливі: “Не йде дощ і трава не мокра”, “Йде дощ і трава мокра”, “Не йде дощ і трава мокра” (трава може бути полита водою). Часто імплікацію плутають з еквівалентністю у розмовних реченнях: “Якщо я здам іспити на “відмінно”, то мені куплять велосипед”. Якщо велосипед куплять лише у випадку, коли іспити будуть здані на відмінно, то атоми «я здам іспити на “відмінно”» та «мені куплять велосипед» насправді зв’язані еквівалетністю (мені куплять велосипед тоді і тільки тоді, коли іспити будуть здані на відмінно), а якщо велосипед може бути куплений і без таких значних досягнень, то це зв’язка імплікації.
Заперечення є одномісною (унарною) зв’язкою, а кон’юнкція, диз’юнкція, альтернативне «або», імплікація, еквівалентність є двомісними (бінарними) зв’язками.
Означення 2.4. Формула – це атомарна формула або складне висловлювання, отримане об’єднанням декількох атомарних формул за допомогою логічних зв’язок (логічних операцій).
Приклад2.5. Записати у вигляді формули висловлювання: «Якщо я пізно ляжу спати, то просплю і запізнюсь на роботу».
Розглянемо атоми цієї формули, які позначимо:
p: «я пізно ляжу спати»;
q: «я просплю»;
r: «запізнюсь на роботу».
Отже, формула запишеться як p ®(q Ù r). ▲
Правила побудови формули визначаються таким чином:
1. Атомарна формула є формулою.
2. Якщо р формула, то і (Ø р) теж формула.
3. Якщо р та q формули, то і (р Ú q), (р Ù q), (р ~ q), (р ® q), (р Å q) теж формули.
4. Формули отримуються лише скінченною кількістю застосувань правил 1-3.
Приклад2.6. Вирази (p ® q)® r, (р Ú q) ® q, (р Å q) – формули.
Вирази (p ®), (Ú q), (p ® q)Å – не є формулами.▲
Означення 2.5. Інтерпретація формули – це набір значень істинності (T або F) всіх атомів у заданій формулі.
Для того, щоб знайти значення істинності складного висловлювання для певної інтерпретації, необхідно підставити відповідні значення істинності для всіх атомів цієї інтепретації та спростити її.
Означення 2.6. n-місна формула – це формула, що містить n атомів.
n -місна формула має 2 n інтерпретацій, тобто існує 2 n способів надати значення істинності її атомам.
Приклад 2.7. Нехай маємо формулу (Ø(p ® q))~(p Ù(Ø q))). Атомарними формулами тут є p, q. Отже, формула має 22=4 інтерпретації.
Якщо ми маємо (Ø(p ® q)Ù r)~(s Ù(Ø q)Ú p)). Атомарними формулами тут є p, q, r, s. Отже, формула має 24=16 інтерпретацій. p
Означення 2.7. Виконана формула – це формула, яка має принаймні одну інтерпретацію, у якій вона набуває значення істинності.
Означення 2.8. Тавтологія – формула, що виконується у всіх інтерпретаціях.
Означення 2.9. Протиріччя – формула, що не виконується у жодній інтерпретації.
В інших випадках формула називається ані істинною, ані хибною.
Приклад 2.8. Розглянемо формулу ((p ® q)Ù(p Ú r))~(Ø q). Атомарними формулами тут є p, q, r. Формула має 23=8 інтерпретацій. Значення істинності заданої формули наведено в таблиці 2.2.
Таблиця 2.2
| p | q | r | (p ® q) | (p Ú r) | ((p ® q)Ù(p Ú r)) | Ø q | ((p ® q)Ù(p Ú r))~(Ø q) |
| T | T | F | T | T | T | F | F |
| T | T | T | T | T | T | F | F |
| T | F | F | F | T | F | T | F |
| T | F | T | F | T | F | T | F |
| F | T | F | T | F | F | F | F |
| F | T | T | T | T | T | F | F |
| F | F | F | T | F | F | T | F |
| F | F | T | T | T | T | T | T |
Приклад 2.9. Розглянемо формулу ((Ø p)®(p ® q)). Атомарними формулами тут є p, q. Формула має 22=4 інтерпретації. Значення істинності заданої формули наведено в таблиці 2.3. Задана формула істинна у всіх інтерпретаціях, отже, це тавтологія.
Таблиця 2.3
| p | Q | Ø p | p ® q | (Ø p)®(p ® q) |
| T | T | F | T | T |
| T | F | F | F | T |
| F | T | T | T | T |
| F | F | T | T | T |
Приклад 2.10. Розглянемо формулу (p Ù(Ø(q Ú q)). Атомарними формулами тут є p, q. Формула має 22=4 інтерпретації. Значення істинності заданої формули наведено в таблиці 2.4. Задана формула хибна у всіх інтерпретаціях, отже, це протиріччя.
Таблиця 2.4
| p | Q | q Ú q | Ø(q Ú q) | p Ù(Ø(q Ú q) |
| T | T | T | F | F |
| T | F | T | F | F |
| F | T | T | F | F |
| F | F | F | T | F |
Означення 2.10. Змінна називається фіктивною, якщо значення формул не залежить від значення цієї змінної.
Тобто змінна 
функції 
є фіктивною, якщо 
для довільних x 1,…, xn.
Означення 2.11. Якщо змінна не є фіктивною, то вона називається значимою.
Приклад 2.11. Вказати, які змінні у формулі 
фіктивні, а які – ні.
Складемо таблицю істинності:
| p | q | r | (p Ú q) | 
| 
|
|
| T | T | F | T | T | F | T |
| T | T | T | T | F | F | T |
| T | F | F | T | T | F | T |
| T | F | T | T | F | F | T |
| F | T | F | T | T | F | T |
| F | T | T | T | F | F | T |
| F | F | F | F | T | F | F |
| F | F | T | F | F | F | F |
Отже, як видно з таблиці, значення змінної r не впливає на значення формули, тому вона є фіктивною змінною. Відповідно змінні p, q є значимі.p
Дата публикования: 2015-09-17; Прочитано: 2996 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
