Закони логіки висловлювань

ОСНОВИ ЛОГІКИ

МЕТОДИЧНІ ВКАЗІВКИ

до виконання практичних завдань

з дисципліни „Комп’ютерна дискретна математика”

для студентів базового напряму

„Програмна інженерія”

Львів – 2013

Основи логіки.: Методичні вказівки до виконання практичних занять з дисципліни „Комп’ютерна дискретна математика” для студентів базового напряму „Програмна інженерія” / Укл.: П. В. Сердюк, О.О. Нитребич – Львів: Видавництво Національного університету „Львівська політехніка”, 2013. – 28 с.

Укладачі

Сердюк. П. В., к. т. н., доц. кафедри програмного забезпеченння національного університету “Львівська політехніка”

Нитребич О. О., асист. кафедри програмного забезпеченння національного університету “Львівська політехніка”

Відповідальний за випуск

Федасюк Д. В., д-р тех. наук, проф., завідувач кафедрою програмного забезпечення, проректор з науково-педагогічної роботи національного університету “Львівська політехніка”

Рецензенти

Гавриш В. І., к.ф.-м.н., доц. кафедри програмного забезпеченння національного університету “Львівська політехніка”

Огородник Н. П., к.ф.-м.н., асис. кафедри теорії оптимальних процесів Львівського національного університету ім. І. Франка

Зміст

1. Вступ. 4

2. Логіка висловлювань. 4

3. Закони логіки висловлювань. 9

4. Способи доведення логічних тверджень. 10

5. Логіка предикатів. 13

6. Закони логіки першого ступеня. 17

7. Випереджена нормальна форма. 18

8. Завдання до виконання. 20

9. Контрольні запитання. 26

ОСНОВИ ЛОГІКИ

Мета роботи: Ознайомитись на практиці із основними поняттями та законами логіки висловлювань, навчитись доводити логічні твердження шляхом побудови таблиць істинності і використовувати закони логіки.

Теоретичні відомості

Вступ

Логіка – наука про правильні міркування, про прийоми та методи пізнання за допомогою міркувань. Слово «логіка» походить з давньогрецького «logos» – «поняття», «розум», «міркування». Логіка як наука про правильні міркування була закладена у Стародавній Греції Аристотелем та на протязі багатьох століть розвивалась як частина філософії. Починаючи із середини вісімсотих років минулого тисячоліття логіка стає предметом дослідження математики, а після появи ЕОМ – і інформатики. На сьогоднішній день розрізняють формальну логіку, яка вивчає правила логічного виведення і аналізу та неформальну логіку, яка займається вивченням арґументації у природній мові. Формальна логіка, в свою чергу, містить багато інших логічних систем: логіку висловлювань, предикатну логіку, модальну логіку, темпоральну логіку та ін.

Логіка висловлювань

Означення 2.1. Висловлювання – розповідне речення, про яке можна сказати, що воно хибне або істинне, але не те й інше водночас.

Приклад 2.1.

1. Львів – обласний центр Волинської області.

2. 2+3=5.

3. х +2=5.

4. Сиди спокійно!

Перші два речення є висловлювання, а останні два – ні. З курсу географії відомо, що перше речення хибне, а з арифметики зрозуміло, що друге – істинне. Третє речення, в залежності від значення змінної х, набуває значення хибності або істинності, а четверте речення не є розповідним. ▲

Означення 2.2. Істина або хибність, яка приписана деякому висловленню, називається істиннісним значенням цього висловлення. Позначення:

«Істина» –Т, І, True або 1;

«Хибність» – F, Х, False або 0.

У цих методичних вказівках ми будемо використовувати позначення T для істини і F для хибності.

Означення 2.3. Атомарна формула (атом) – елементарне неподільне висловлювання. Множина усіх атомів складає пропозиційну сигнатуру, тобто множину всіх висловлювань, якими ми оперуємо в контексті даної задачі.Атоми позначають малими латинськими буквами.

Приклад 2.2

1. Падає дощ – атом.

2. Я отримав гарну оцінку – атом.

3. Я забув вивчити логіку і отримав двійку. Якщо пропозиційна сигнатура містить два висловлювання: «я забув вивчити логіку», «я отримав двійку», то це висловлювання не буде атомом. p

Логічні зв’язки

Розглянемо основні логічні зв’язки:

³ заперечення висловлювання 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 у таблиці вище, то очевидно, що тільки висловлювання “падає дощ і трава не мокра” є хибним. Усі решта висловлювання є істинними, тому що теоретично вони можливі: “Не йде дощ і трава не мокра”, “Йде дощ і трава мокра”, “Не йде дощ і трава мокра” (трава може бути полита водою). Часто імплікацію плутають з еквівалентністю у розмовних реченнях: “Якщо я здам іспити на “відмінно”, то мені куплять велосипед”. Якщо велосипед куплять лише у випадку, коли іспити будуть здані на відмінно, то атоми «я здам іспити на “відмінно”» та «мені куплять велосипед» насправді зв’язані еквівалетністю (мені куплять велосипед тоді і тільки тоді, коли іспити будуть здані на відмінно), а якщо велосипед може бути куплений і без таких значних досягнень, то це зв’язка імплікації.

Заперечення є одномісною (унарною) зв’язкою, а кон’юнкція, диз’юнкція, альтернативне «або», імплікація, еквівалентність є двомісними (бінарними) зв’язками.

Означення 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 ⁿ інтерпретацій, тобто існує 2 ⁿ способів надати значення істинності її атомам.

Приклад 2.7. Нехай маємо формулу (Ø(p ® q))~(p Ù(Ø q))). Атомарними формулами тут є p, q. Отже, формула має 2²=4 інтерпретації.

Якщо ми маємо (Ø(p ® q)Ù r)~(s Ù(Ø q)Ú p)). Атомарними формулами тут є p, q, r, s. Отже, формула має 2⁴=16 інтерпретацій. p

Означення 2.7. Виконана формула – це формула, яка має принаймні одну інтерпретацію, у якій вона набуває значення істинності.

Означення 2.8. Тавтологія – формула, що виконується у всіх інтерпретаціях.

Означення 2.9. Протиріччя – формула, що не виконується у жодній інтерпретації.

В інших випадках формула називається ані істинною, ані хибною.

Приклад 2.8. Розглянемо формулу ((p ® q)Ù(p Ú r))~(Ø q). Атомарними формулами тут є p, q, r. Формула має 2³=8 інтерпретацій. Значення істинності заданої формули наведено в таблиці 2.2.

Таблиця 2.2

Приклад 2.9. Розглянемо формулу ((Ø p)®(p ® q)). Атомарними формулами тут є p, q. Формула має 2²=4 інтерпретації. Значення істинності заданої формули наведено в таблиці 2.3. Задана формула істинна у всіх інтерпретаціях, отже, це тавтологія.

Таблиця 2.3

Приклад 2.10. Розглянемо формулу (p Ù(Ø(q Ú q)). Атомарними формулами тут є p, q. Формула має 2²=4 інтерпретації. Значення істинності заданої формули наведено в таблиці 2.4. Задана формула хибна у всіх інтерпретаціях, отже, це протиріччя.

Таблиця 2.4

Означення 2.10. Змінна називається фіктивною, якщо значенняформул не залежить від значення цієї змінної.

Тобто змінна функції є фіктивною, якщо для довільних x _1,…, x_n.

Означення 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

Закони логіки висловлювань

Означення 3.1 Еквівалентні формули, що визначають правила перетворень, називають законами логіки висловлювань.

Основні закони логіки висловлювань:

³ закон комутативності, який означає, що під час множення (кон’юнкції) та додавання (диз’юнкції) результат не залежить від порядку змінних;

³ закон асоціативності, який говорить про те, що під час використання однакових знаків (лише кон’юнкції або лише диз’юнкції) дужки можна ставити в будь-якому порядку або ж взагалі упускати;

³ закон дистрибутивності, що виражає правило виносу спільного висловлювання за дужки;

³ закон протиріччя, який говорить про неможливість набуття значень істинності суперечливих (протилежних за значенням) висловлювань;

³ закон виключення третього, який означає, що із двох протилежних висловлювань на однакову тему одне завжди істинне, а друге – хибне; третього не буває;

³ закон ідемпотентності, який означає, що добуток (кон’юнкція) двох висловлювань чи їхня сума (диз’юнкція) еквівалентні самому висловлюванню;

³ закон подвійного заперечення, який говорить, що подвійне заперечення виключає заперечення;

³ закони де Моргана, що зв'язують заперечення з операціями кон'юнкції і диз'юнкції.

Основні закони логіки висловлювань наведено у табл. 3.3.

Таблиця 3.3

Закони логіки висловлювань

Назва законів	Формулювання законів
Закони комутативності	p Ú q = q Ú p
p Ù q = q Ù p
Закони асоціативності	(p Ú q)Ú r = p Ú (q Ú r)
(p Ù q) Ù r = p Ù (q Ù r)
Закони дистрибутивності	p Ú(q Ù r) =(p Ú q) Ù (p Ú r)
p Ù(q Ú r) =(p Ù q) Ú (p Ù r)
Закон протиріччя	p Ù(Ø p)=F
Закон подвійного заперечення	Ø (Ø p)= p
Закон виключення третього	p Ú (Ø p)=T
Закони ідемпотентності	p Ú p = p
p Ù p = p
Закони де Моргана
Закони поглинання	(p Ú q) Ù p = p
(p Ù q) Ú p = p
Співвідношення для сталих	p ÚT=T
p ÙT= p
p ÚF= p
p ÙF=F

Наведені закони можна перевірити побудовою таблиць істинності.

Поиск по сайту: