Міністерство освіти і науки України
Херсонський державний університет
Факультет фізики, математики та інформатики
Методичне забезпечення розділу
“Математична логіка”
курсу дистанційного навчання дисципліни дискретна математика
Курсова робота
Науковий керівник
Доцент
Шишко Л.C.
Виконавець студент денної
Рибакін В.В.
форми навчання 421 групи
Херсон 2008
План
Вступ
Розділ І. Логіка висловлювань.
1.1. Основні поняття логіки висловлювань.
1.2. Закони логіки висловлювань.
1.3. Нормальні форми логіки висловлювань.
Розділ ІІ. Логіка предикатів.
2.1. Основні поняття логіки предикатів.
2.2. Закони логіки предикатів.
2.3. Випереджена нормальна форма логіки предикатів.
Література.
Вступ
Математична логіка займає одне з найважливіших місць у сучасній математичній науці. Вона знайшла широке застосування в найрізноманітніших галузях наукових досліджень. Математична логіка з великим успіхом використовується в теорії релейно-контактних схем і в теорії автоматів, тобто в кібернетиці, в лінгвістиці, в економічних дослідженнях, у фізіології мозку і психології тощо.
Актуальність. Математична логіка дуже важлива для вчителів математики. Вона дає можливість краще зрозуміти структурно-логічну схему шкільного курсу математики, глибше вникнути в суть поняття доведення, з’ясувати зміст поняття логічного слідування, встановити зв’язки між різного роду теоремами тощо. З цих причин Я й обрав дану тему для написання курсової роботи. На мою думку ця тема є важливою в математиці. Тому що розвиток математичної логіки як науки дав значний вплив у розвитку математичної науки. Значну внесок у розвиток математичної логіки зробили такі вчені як: Платон, Аристотель, Лейбніц, Буль, Гільберт.
Об’єктом дослідження є основні поняття математичної логіки.
Історично математична логіка будувалась як алгебраїчна теорія, у якій зв’язки між різними поняттями логіки виражалися за допомогою операцій. Така побудова математичної логіки згодом дістала назву алгебри висловлень і алгебри предикатів, причому алгебра висловлень уходить як частина в алгебру предикатів. Вона називається також змістовною побудовою математичної логіки і нею часто вичерпується виклад математичної логіки, причому апарату логіки предикатів достатньо, щоб ставити і розв’язувати досить важливі й складні задачі. Поряд з потребою змістовної побудови математичної логіки виникла потреба будувати математичну логіку як формально-аксіоматичну теорію, для якої алгебра предикатів є однією з можливих інтерпретацій.
У першому розділі розглянуто змістовні поняття й елементи логіки висловлень. Разом із цим, уже в першому розділу курсової роботи вводиться проблематика множин і логіки, яка істотно використовується в штучному інтелекті. А в другому розділі описано логіку предикатів.
Розділ І. Логіка висловлювань.
1.1. Основні поняття логіки висловлювань
Висловлюванням називають розповідне речення, про яке можна сказати, що воно або істинне, або фальшиве, але не одне й інше разом. Розділ логіки, що вивчає висловлювання та їхні властивості, називають пропозиційною логікою, або логікою висловлювань. Уперше систематичне викладення логіки було зроблене грецьким ученим Аристотелем понад 2300 років тому.
Приклад 1.1. Наведемо приклади речень.
1. Сніг білий.
2. Київ - столиця України.
3. х+1=3.
4. Котра година?
5. Читай уважно!
Два перших речення є висловлюваннями, останні три - ні. Третє речення набуває істинне або фальшиве значення залежно від значення змінної х, четверте та п'яте речення - не розповідні.
Значення "істина" або "фальш", які надані деякому висловлюванню, називають значенням істинності цього висловлювання. Значення "істина" позначають літерою Т (від англійського truth), а "фальш" - літерою F (від false). Для позначення висловлювань використовують малі латинські букви як з індексами, так і без них. Символи, що використовують для позначення висловлювань, називають атомарними формулами, або атомами.
Приклад 1.2.
1. р: "Сніг білий".
2. g: "Київ - столиця України".
Тут символи р, g атомарні формули.
Багато речень утворюють об'єднанням одного або декількох висловлювань. Отримане висловлювання називають складним висловлюванням. Його утворюють із наявних висловлювань застосуванням логічних зв'язок. Такі побудови вперше розглянуто 1845 р. у книзі англійського математика Д.Буля "TheLawsofTruth".
Розглянемо питання побудови нових висловлювань з тих, що ми вже маємо. Для цього в логіці висловлювань використовують п'ять логічних зв'язок: заперечення (читають "не" та позначають "¬"), кон'юнкцію (читають "і" та позначають ""), диз'юнкцію (читають "або" та позначають ""), імплікацію (читають "якщо..., то" та позначають "→") та еквівалентність (читають "тоді й лише тоді" та позначають "~").
Приклад 1.3.
1. Сніг білий і небо теж біле.
2. Якщо хороша погода, то ми їдемо відпочивати.
У наведених прикладах логічні зв'язки - це "і" та "якщо..., то".
Приклад 1.4. Розглянемо прості висловлювання, які позначимо:
р: "Висока вологість", g: "Висока температура", r: "Ми почуваємо себе добре". Тепер речення "Якщо висока вологість та висока температура, то ми не почуваємо себе добре" можна записати у вигляді складного висловлювання ((pg)→(¬r)).
У логіці висловлювань атомp або складне висловлювання називають правильно побудованою формулою, або формулою. При вивченні формул розглядають їх два аспекти — синтаксис та семантику.
Синтаксис - це сукупність правил, які дозволяють будувати формули та розпізнавати правильні формули серед послідовностей символів.
Формули у логіці висловлювань визначають за такими правилами:
1. Атом є формулою.
2. Якщо р формула, то (¬p) - теж формула.
3. Якщор та g - формули, то (рg), (рg), (р→g), (¬g) - формули.
4. Жодних інших формул, крім породжених застосуваннямвказаних вище правил, немає.
Формули, так само як і атоми, позначають малими латинськими буквами з індексами або без них.
Приклад 1.5. Вирази (р→), (р), (р¬), (g) - не формули.
Якщо не виникає непорозумінь, то деякі пари круглих дужок можуть бути випущені.
Приклад 1.6. Вирази рg, р→g є формулами (рg) та (р→g), відповідно.
Семантика - це сукупність правил, які надають формулам значення істинності.
Нехайpта g — формули. Тоді значення істинності формул (¬p), (рg), (рg), (р→g) та (р~g) так пов'язані зі значеннями істинності формул р та g.
1. Формула (¬р) істинна, коли р фальшива, і фальшива, коли рістинна. Її читають "не р", або "це не так, що р" та називаютьзапереченням р. Замість (¬р) заперечення р позначають також. У такому разі знак заперечення одночасно відіграє рольдужок.
2. Формула (рg) істинна, якщо р та g одночасно істинні. У всіх інших випадках (рд) фальшива. Формулу (рg) читають "р і g" та називають кон’юнкцією формул р та g.
3. Формула (рg) істинна, якщо істинна принаймні одна з формулр або g. В іншому випадку (рg) - фальшива. Формулу (рg) читають "р або g" та називають диз'юнкцією формул р та g.
4. Формула (р→g) фальшива, якщо р істинна, а g - фальшива. Увсіх інших випадках (р→g) істинна. Формулу (р→g) читають "якщо р, то g", "з р випливає g", або "р лише, якщо g" та називають імплікацією. Тут атом р називають припущенням імплікації, а g - висновком імплікації.
5. Формула (р~g) істинна, якщо р та g мають однакові значенняістинності. У всіх інших випадках (р~g) - фальшива. Формулу (р~g) читають "р тоді й лише тоді, коли g" або ″р еквівалентне g" та називають еквівалентністю формул р та g.
Семантику логічних зв'язок зручно задавати за допомогою таблиць, якими визначають значення істинності формул за значеннями істинності атомів у цих формулах. Такі таблиці називають таблицями істинності. Семантику введених логічних зв'язок у формітаблиць істинності надано у табл. 1.1.
Таблиця 1.1
| р | g | (¬p) | (pg) | (рg) | (p→g) | (p~g) |
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
Приклад 1.7. Знайдемо заперечення висловлювання "Сьогодні п'ятниця". Таке заперечення - "Це не так, що сьогодні п'ятниця". Це речення також можна сформулювати як "Сьогодні не п'ятниця" або "П'ятниця не сьогодні". Зауважимо, що речення, які пов'язані з часовою змінною, не є висловлюваннями доти, доки не визначений момент часу. Це ж стосується й змінних у реченнях, які характеризують місце або особу, до вказування відповідного місця або конкретної особи.
Приклад 1.8. Знайдемо кон'юнкцію висловлювань pта g, де р є висловлюванням "Сьогодні п'ятниця", а g - висловлюванням "Сьогодні падає дощ". Кон'юнкцією цих висловлювань є висловлювання "Сьогодні п'ятниця і сьогодні падає дощ". Це висловлювання істинне у дощову п'ятницю і фальшиве не в п'ятницю або у не дощову п'ятницю.
Приклад 1.9. Що є диз'юнкцією висловлюваньg та p, які визначені у прикладі 1.8? Диз'юнкцією висловлювань p та g, є висловлювання pg "Сьогодні п'ятниця або падає дощ". Це висловлювання істинне в будь-яку п'ятницю або в дощовий день. Дощова п'ятниця також долучається. Це висловлювання фальшиве тільки в одному випадку - у недощову п'ятницю.
Логічна зв'язка "диз'юнкція" відповідає одному з двох способів уживання слова "або" в українській мові. Диз'юнкція істинна, якщо істинне принаймні одне з двох висловлювань. Наприклад, її використовують у реченні "Лекції з логіки можуть відвідувати студенти, які прослухали курси математичного аналізу або дискретної математики". Зміст цього речення полягає в тому, що лекції можуть відвідувати як студенти, які прослухали обидва курси, так і ті студенти, які прослухали тільки один з цих курсів. Інший спосіб використання диз'юнкції- це альтернативне "або". Для прикладу, така диз'юнкція відповідає реченню "Лекціїз логіки можуть відвідувати студенти, які прослухали один з двох курсів — математичний аналіз або дискретну математику". Зміст цього речення полягає в тому, що студенти, які прослухали обидва ці курси, вже не повинні слухати лекцій з логіки. Аналогічно, якщо в меню вказано "Закуску або салат подають з першою стравою", то це майже завжди означає, що з першою стравою подадуть або закуску, або салат, але не обидві страви. Тобто, це альтернативне, а не звичайне "або", його позначають "". Значення істинності альтернативного "або" наведено у табл. 1.2.
Таблиця 1.2
| p | g | pg |
| 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 | (pg) | (р~) | (р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 робимо висновок, що задана формула фальшива в усіх інтерпретаціях, тобто заперечувана.
Таблиця 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=gp б) рg=gp |
| 2. | Закони асоціативності | а) (рg)r=р(gr) б) (рg)r=р(gr) |
| 3. | Закони дистрибутивності | а) р(gr)=(pg)(pr) б) р(gr)=(pg)(pr) |
| 4. | Закон протиріччя | р=F |
| 5. | Закон виключеного третього | р=T |
| 6. | Закон подвійного заперечення | =р |
| 7. | Закони ідемпотентності | а)рp=p б) pp=p |
| 8. | Закони де Моргана | а) = б) = |
| 9. | Закони поглинання | а) (рg)р=р б) (рg)p=р |
| 10. | Співвідношёення для сталих | а) pT=T б) pT=p в) рF=p г) pF=F |
Наведені еквівалентності можна перевірити побудовою таблиць істинності. Приклад 1.14 свідчить, що імплікація не комутативна. Покажемо, як застосувати закони логіки висловлювань для доведення еквівалентності формул.
Приклад 1.15. Застосуванням законів логіки висловлювань доведемо еквівалентність формул р→(gr) та (p→g)(p→r). Випишемо послідовність перетворень та запишемо біля кожного рядка назву застосованого закону або правила.
1.(gr) - правило вилучення імплікації з першої із заданихформул.
2. (g)(r) - закон дистрибутивності 9б для формули 1.
3. (р→g)(p→r) - правило введення імплікації для формули 2.
Отже, задані формули еквівалентні: р→(gr) та (p→g)(p→r).
Приклад 1.16. Застосуванням законів логіки висловлювань доведемо еквівалентність формул р→gта →. Цю еквівалентність називають правилом контрапозиції.
1. g - правило вилучення імплікації у першій із заданихформул.
2. g -закон комутативності 1а для формули 1.
3. - закон подвійного заперечення 6 для формули 2.
4.→ - правило введення імплікації для формули 3.
Отже, задані формули еквівалентні: р→g=→.
1.3. Нормальні форми логіки висловлювань.
Літералом називатимемо атом або заперечення атома. Прикладами літералів єр, , r. Літерал називають позитивним, якщо він не має знака заперечення, та негативним, якщо він має знак заперечення. Пару літералів {p, } називають контрарною парою.
Кажуть, що формулу f записано у кон'юнктивній нормальній формі (КНФ), якщо вона має вигляд f=f1
f2
…fn
(n≥1) і всі fi
(i=1,2,...,n) різні. Тут кожна з формул f1
,f2
,…,fn
є диз'юнкцією літералів, у якій всі атоми різні.
Приклад 1.17. Нехай p, g та r — атоми. Тодіf=(р)(g) -формула, записана в кон'юнктивній нормальній формі. У цій формулі f1
=(р) та f2
=(g), тобто f1
- диз'юнкція літералівp, , , а f2
- диз'юнкція літералів таg.
Кажуть, що формулу f записано у диз'юнктивній нормальній формі (ДНФ), якщо вона має вигляд f=f1
f2
…fn
(n≥1) і всі fi
(i=1,2,...,n) різні. Тут кожна з формул f1
,f2
,…,fn
є кон'юнкцією літералів, у якій всі атоми різні.
Приклад 1.18. Нехай p, g та r - атоми. Тодіf=(g)(p) -формула, записана у диз'юнктивній нормальній формі. У цій формулі f1
=(g) та f2
=( p), де f1
- кон'юнкція літералів та g, а f2
- кон'юнкція літералівp, та .
Довільну формулу можна перетворити в одну з нормальних форм застосуванням законів логіки висловлювань. Для побудови нормальних форм необхідно виконати таку послідовність кроків еквівалентних перетворень.
Крок 1. Використати правила f→g=gта f~g=(f→g)(g→f) (див. параграф 1.2) для усунення логічних зв'язок "→" та "~".
Крок 2. Використати закон подвійного заперечення та закони де Моргана для перенесення знаку заперечення безпосередньо до атомів.
Крок 3. Використати відповідні закони дистрибутивності закони для побудови нормальної форми. Для побудови кон'юнктивної нормальної форми використати закон дистрибутивності для диз'юнкції відносно кон'юнкції (закон 3а з табл. 1.8). Для побудови диз'юнктивної нормальної форми використати закон дистрибутивності для кон'юнкції відносно диз'юнкції (закон 3 б з табл. 1.8).
Приклад 1.19. Побудуємо диз'юнктивну нормальну форму формули ((p)→r)(→s). Наведемо послідовність кроків для побудови ДНФ та застосовані закони.
1. (r)() - усунення логічної зв'язки "→" із заданої формули.
2. (()r)()- закон де Моргана 8а до формули з рядка 1.
3. ((g)r)(rs) - закон подвійного заперечення 6 до формули 2.
4. ((g)(rs))(r(rs)) - закон дистрибутивності 3б до формули 3.
5. ((gr)(gs))((rr)(rs)) -закон дистрибутивності 3б до формули 4.
6. (gr)(gs)(rr)(rs) - асоціативний закон 2а доформули 5.
7. (gr)(gs)r(rs) - закон ідемпотентності 7б доформули 6.
Ми одержали ДНФ. Звернемо увагу, що її можна спростити, якщо двічі використати закон поглинання 9б: диз'юнктивний член к поглинає члени (gr) та (rs). Отже, ДНФ заданої формули ((p)→r)(→s) також буде (gs)r. Останні міркування свідчать, що ДНФ певної формули, якщо казати загалом, не єдина.
Приклад 1.20. Побудуємо кон’юнктиву нормальну форму формули (р(g→r))→s. Наведемо послідовність кроків побудови КНФ і застосовані закони та правила.
1. -усунення логічної зв'язки"→" із заданої формули.
2. s- закон де Моргана 8б до формули 1.
3. ()s -закон де Моргана 8а до формули 2.
4. (g)s - закон подвійного заперечення 6 до формули 3.
5. s(g) - закон комутативності 1а до формули 4.
6. (s)(g) - закон асоціативності 2а до формули 5.
7. (gs)(s) - закон дистрибутивності За до формули 6.
Формула (gs)(s) є КНФ формули (р(g→r))→s.
Розділ ІІ: Логіка предикатів.
2.1. Основні поняття логіки предикатів.
Як уже відзначалось під час вивчення логіки висловлювань, існують речення, які не є висловлюваннями та містять змінні. Був наведений приклад речення "х+1=3". Речення зі змінними не є висловлюваннями, але перетворюються в них, якщо надати значення змінним. Речення зі змінними дуже поширені. Вони містяться в математичних формулах та комп'ютерних програмах. Зокрема, у мовах програмування зустрічаються оператори такого змісту "повторювати цикл доти, поки змінні х та у не стануть рівними, або припинити обчислення циклу після 100 повторень". Якщо позначити через і лічильник повторень, то умова закінчення програми задаватиметься виразом "(x=y)(i>100)", а сам оператор матиме вигляд "повторювати, якщо (¬((x=y)(i>100)))"
Приклад 2.1. Прикладами речень, які містять змінні є "х>3", "x=y+3", "x+у=z". Ці речення ні істинні, ні фальшиві доти, поки змінні не одержать значення.
У наведеному прикладі речення "х>3", або, в іншій формі, "х більше 3" складається з двох частин: першу, змінну х, називають предметом, другу - "більше 3", - яка вказує властивість предмета, називають предикатом. Часто предикатом називають все речення.
Уведемо логіку першого ступеня (логіку предикатів), в якій до понять логіки висловлювань додано нові поняття. Для формулювання складних думок у логіці висловлювань уведено атоми як основні елементи, з яких будують формули. Атом розглядався як неподільне ціле - його структура та склад не аналізувались. У той же час існує багато міркувань, які неможливо описувати лише за допомогою висловлювань. Тому введемо поняття атома у логіці першого ступеня. Для запису атомів логіки першого ступеня використовують такі типи символів:
1) Індивідні символи або сталі - це імена об'єктів, які починаються з великої букви: Іван, Марія та сталі: Т, F або 3.
2) Предметні символи - імена змінних, які позначають малимибуквами, можливо, з індексами: х,у,z,vi
,wj
.
3) Предикатні символи — імена, якими позначають предикатита записують великими буквами: Р,Q, R, або змістовними словами,які записують великими буквами БІЛЬШЕ, ЛЮБИТЬ тощо.
Приклад 2.2. Позначимо речення "х більше 3" через Р(х), де предикатний символ Р позначає предикат "більше 3", ах - змінна, або предметний символ. Вираз Р(х) у цілому теж називають предикатом. Щоб записати твердження "х більше 3" як предикат, можна поступити інакше - визначити предикат БІЛЬШЕ(х,у), який означає "х більшеy". Тоді речення "х більше 3" можна записати за допомогою предиката БІЛЬШЕ(х, 3).
Загалом, предикат, який містить nзмінних: x1
, x2
, x3
,…,xn
, записують Р(х1
,х2
,...,хn
) та називають n-місним. Змінну xi
Di
(i=1,2,..,n) називають предметною, множину Di
- її предметною областю, а символ Р - n-місним предикатним символом. Замість терміну "предикат" іноді використовують "пропозиційна функція".
Щойно змінна х дістає значення з предметної області, предикат Р(х) набуває значення Т або F та перетворюється у висловлювання. Аналогічно, якщо всі змінні багатомісного предиката одержать значення, то він набуде значення істинності й теж перетвориться у висловлювання.
Атом логіки першого ступеня має вигляд Р(х1
, х2
,...,хn
), де Р- предикатний символ, аx1
,x2
,…,xn
- предметні або індивідні символи.
Приклад 2.3. Нехай вираз "x+у=2" задано предикатом Q(х,у). Тоді Q(1,2) - фальшиве висловлювання, а Q(2,0) - істинне. Позначимо це так: Q(1,2)=F, Q(2,0)=Т. Задамо речення "х любитьy" предикатом ЛЮБИТЬ(х,у). Тоді істинне речення "Іван любить Марію" подається істинним висловлюванням ЛЮБИТЬ (Іван, Марія).
Приклад 2.4. Якщо БІЛЬШЕ(х,у) - предикат, визначений у прикладі 2.2, то БІЛЬШЕ(5,3) - істинне висловлювання, а БІЛЬШЕ (1,3) - фальшиве висловлювання.
Існує інший шлях перетворення предиката у висловлювання -квантифікація. Нехай Р(х) — предикат, D — задана предметна область та хD. Використаємо два спеціальні символи та , які називають: - квантором загальності, - квантором існування. Якщо х - змінна, то вираз (х) читають "для всіх х", "для кожного х" або "для будь-якого х". Запис (х)Р(х) означає "Р(х) істинний для всіх значень х з предметної області" та читають "Р(х) для всіх х". Вираз (х) читають "існує х", "для деяких х" або "принаймні для одного х". Запис (х)Р(х) має зміст "в області D існує таке х, що Р(х) - істинний", або "в області D існує принаймні одне х таке, що Р(х) - істинний" або "Р(х) істинний для деякого х з області D. У подальшому в записі квантора будемо випускати дужки, записуючи х та х замість (х) та (х), відповідно.
Правильно побудовані формули логіки першого ступеня, або формули визначають так.
1.Атом є формулою.
2.Якщо Hта G- формули, то (¬H),(HG),(HG),(H→G) та (H~G) - формули.
3.Якщо Hформула, ах- змінна у формулі H, то хHта хH- формули.
4.Формули одержують лише скінченною кількістю застосуваньправил 1-3.
Наведемо приклади висловлювань, одержаних із застосуванням кванторів.
Приклад 2.5. Позначимо речення "х просте число" через P(х), "х раціональне число" - через Q(х), "хдійсне число" - через R(х) та "х меншеy" - через МЕНШЕ(х,у). Розглянемо такі істинні речення.
1. Кожне раціональне число є дійсним.
2. Існує число, яке є простим.
3. Для кожного числа х існує таке число у, що х<у.
Наведені речення записують такими формулами.
1.x (Q(x)→R(x)).
2.x P(x)
3.xyМЕНШЕ(x,y)
Перехід від Р(х) до хР(х) або хР(х) називають зв'язуванням змінноїx, а змінну х—зв'язаною. Не зв'язану змінну називають вільною. У формулах хР(х) та хР(х) предикат Р(х) перебуває в області дії відповідного квантора.
Приклад 2.6. У формулі хР(х,у) зміннах зв'язана, а змінна у - вільна, оскільки перед формулою відсутній квантор, який містить цю змінну.
У разі знаходження значення істинності висловлювання, отриманого з пропозиційної функції зв'язуванням її змінних кванторами, важливе значення має предметна область.
Зв'язування частини змінних багатомісного предиката перетворює його в предикат меншої місності. Зміст зв'язаних і вільних змінних у предикатах різний. Вільні змінні - це звичайні змінні, які можуть приймати різні значення з предметної області D: значення виразу Р(х) залежить відзначення х. Формули х Р(х) і х Р(х) не залежать від змінної х та при визначених Р і D мають конкретні значення. Це, зокрема, означає, що перейменування зв'язаних змінних, а саме, заміна х Р(х) на уР(у), не змінює значення істинності формули.
2.2 Закони логіки предикатів.
Еквівалентні формули логіки висловлювань залишаються правильними й у логіці першого ступеня. Однак, у логіці першого ступеня є низка еквівалентностей, або законів, пов'язаних із специфікою визначення об'єктів логіки першого ступеня.
Аналогічно до попереднього, формули логіки першого ступеня називають еквівалентними, якщо вони приймають однакові значення істинності при довільних значеннях вільних змінних. Зокрема, якщо формули Р та Q еквівалентні, то формула Р~Q - тавтологія. Еквівалентність формул Р та Q будемо записувати Р-Q.
Проблема побудови законів логіки першого ступеня полягає у доведенні логічної еквівалентності формул Р та Q. У логіці висловлювань перевірку логічної еквівалентності можна виконати побудовою відповідних таблиць істинності. Аналогічна процедура у логіці першого ступеня стикається з великими труднощами, оскільки предметні змінні мають у загальному випадку нескінченні предметні області.
Наведемо основні закони логіки першого ступеня. Зауважимо, що у наведених нижче формулах указані лише зв'язані змінні і не вказані вільні змінні, які можуть набувати довільні значення із предметної області.
1. ¬(x P(x))=x(x).
2. ¬(x P(x))=x(x).
3. x(P(x)Q(x))=x P(x)x Q(x).
4. x(P(x)Q(x))=x P(x)x Q(x).
5.x(P(x)Q)=x P(x)Q
6.x(P(x)Q)=x P(x)Q
7. x(P(x)Q)=x P(x)Q
8.x(P(x)Q)=x P(x)Q
9.хуР(х,у)=ухР(х,у).
10.хуР(х,у)= ухР(х,у).
Процедура доведення законів вимагає використання спеціальних прийомів. Проілюструємо це на прикладі доведення еквівалентності ¬(xP(х))=x(x). Нехай для деякого предикатногосимволу Р та предметної області D ліва частина цієї еквівалентності істинна. Тоді не існує такого аD для якого Р(а) істинне. Отже Р(а) фальшиве для довільного а, а (а) - істинне, та істинна права частина еквівалентності. Якщо ліва частина еквівалентності фальшива, то існує таке аD для якого Р(а) істинне, тобто й права частина фальшива. Аналогічно доводять ¬(x P (х))=x(x).
Приклад 2.7. Розглянемо заперечення речення "Кожний студент університету вивчає математичний аналіз". Це речення записують з використанням квантора загальності як хР(х) де Р(х) -речення "х вивчає математичний аналіз". Запереченням заданого речення є речення "Це не так, що кожний студент університету вивчає математичний аналіз", яке еквівалентне реченню "Існує такій студент університету, який не вивчає математичний аналіз". Останнє доводить заперечення початкової формули: х(х). Цей приклад ілюструє еквівалентність ¬(хР(х))=х(х).
Приклад 2.8. Розглянемо речення "В університеті є студент, який вивчає математичний аналіз". Це речення можна записати із використанням квантора існування як хР(х), де Р(х) речення "х вивчає математичний аналіз". Запереченням заданого речення є речення "Це не так, що є студент в університеті, який вивчає математичний аналіз", яке еквівалентне реченню "Кожний студент університету не вивчає математичний аналіз". Останнє отримують квантифікацією квантором загальності заперечення заданого речення: хР(х). Цей приклад ілюструє еквівалентність ¬(хР(х))=х(х).
Доведемо закон x(Р(х)Q(х))=хР(х)хQ(х). Нехай ліва частина істинна для деяких Р та Q, тобто для довільного аDістинне Р(а)Q(а). Тому Р(а) та Q(а) одночасно істинні для довільного а, тобто хР(х)хQ(х) істинне. Якщо ж ліва частина фальшива, то для деякого аD фальшиве Р або Q. Це означає, що фальшиве хР(х) або хQ(х), тобто фальшива й права частина. Аналогічно доводять еквівалентність.
У законах 9 та 10 змінні в предикатах зв'язані однаковими кванторами, що дозволяє переставляти їх без порушення еквівалентності. У випадку різних кванторів така еквівалентність виконується незавжди, тобто, загалом хуР(х,у)≠ухР(х,у). Наведемо приклад, який ілюструє це зауваження.
Приклад 2.9. Розглянемо двомісний предикат Р(х,у) зі змістом "х≥y" на різних предметних областях. Формула хуР(х,у) стверджує, що в предметній області існує єдиний максимальний елемент. Ця формула істинна на предметній області, яка є будь-якою скінченною множиною цілих чисел, але фальшива, наприклад, на такій множині {1/2, 2/3, 3/4,...,n/(n+1),...}. Формула ухР(х,у) істинна на довільній непорожній множині. Отже, цей приклад ілюструє той факт, що переставлення кванторів існування та загальності може змінити зміст формули та її істинність.
Якщо D={а1
, a2
, ..., аn
} - скінченна предметна область змінноїх у предикаті Р(х), то можна скористатись логічними еквівалентностями хР(х)=Р(а1
)Р(а2
)...Р(аn
) та хР(х)=Р(а1
)Р(а2
)...Р(аn
). У такому разі заперечення квантифікованої формули дає той самий результат, що й застосування відповідного закону де Моргана. Це випливає з того, що
¬(хP(х))=¬(P(а1
)Р(а2
)...P(аn
))=(а1
)(а2
...(аn
), а це, у свою чергу, еквівалентне х(х).
Аналогічно, ¬(хР(х))=¬(Р(а1
)Р(а2
)...Р(аn
))=(а1
)(а2
)...(а), що еквівалентне х(х).
2.3. Випереджена нормальна форма логіки предикатів
Формула логіки першого ступеня записана у випередженій нормальній формі, якщо вона має вигляд Q1
x1
Q2
x2
…Qn
xn
M, де кожне Qi
xi
(i=1,2,...,n) - це або xi
, або хi
, а формула М не містить кванторів. Вираз Q1
x1
Q2
x2
…Qn
xn
називають префіксом, а М - матрицею формули, записаної у випередженій нормальній формі.
Приклад 2.10. Наступні формули записані у випередженій нормальній формі:
1)xy(P(x, y)Q(y));
2)xy((x, y)→Q(y));
3)xyz(Q(x, y)→R(z)).
Наведемо послідовність кроків зведення довільної формули логіки першого ступеня до випередженої нормальної форми.
Крок 1. Виключити з формул логічні зв'язки "~" та "→" застосуванням правил Р~Q=(Р→Q)(Q→Р) та Р→Q=Q.
Крок 2. Внести знак заперечення всередину формули, для чоговикористати закони:
- подвійного заперечення = Р;
- деМоргана=, =
- ¬(хР(х))=х(х) та ¬(хР(х))=х(х).
Перейменувати зв'язані змінні, якщо це потрібно.
Крок 3. Винести квантори у префікс, для чого скористатись законами 3 - 8 з підпункту 2.2.
Література
1. Капітонова Ю. В., Кривий С. Л., Летичевський О. А.,Луцький Г. М., Печурін М. К. Основи дискретної математики. -К.: Наукова думка, 2002.
2. Середа В. Ю., Математична логіка в шкільному курсі математики. – К.: Радянська школа, 1984.
3. Мендельсон 3. Введение в математическую логику. - М.:Наука, 1971.
4. Новиков П. С. Элементы математической логики. - М.:Наука, 1973.
5. Столл Р. Множества. Логика. Аксиоматические теории. —М: Просвещение, 1968.
6. Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. Дискретна математика. – В: Магнолія плюс, 2005.