Автор работы: Пользователь скрыл имя, 26 Мая 2013 в 23:50, курсовая работа
Якщо числення висловлювань дає змогу доводити теореми для внутрішніх потреб логіки, то числення предикатів забезпечує можливість описувати й доводити теореми для конкретних розділів математики. Логіка предикатів дає змогу формулювати співвідношення між елементами реального світу і виводити подібні відношення або теореми в математиці. Числення висловлювань – досить вузька логічна система. Існують, наприклад, такі типи логічних міркувань, які не можуть бути здійснені в межах логіки висловлювань:
Кожний друг Івана є другом Петра. Сидір не є другом Івана. Отже, Сидір не є другом Петра.
Просте число два – парне. Отже існують прості парні числа.
Міністерство освіти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Інститут прикладної математики та фундаментальних наук
Кафедра прикладної математики
Курсова робота
з курсу «Дискретна математика»
на тему
«Алгебра предикатів. Квантори»
виконав:
студент групи ІФ-31
Купіч Андрій
прийняла:
Тесак Ірина Євгенівна
Львів 2013
В цій роботі розглянуто поняття предиката та квантора, а також їх формули логіки та рівносильність цих формул. Для практичного досвіду роботи з кванторами та предикатами було наведено декілька прикладів. Також було реалізовано програму на перевірку істинності предиката.
This work discusses the concept of predicate and quantifier, and their formulas and logic equivalence these formulas. For practical experience with quantifiers and predicates were given a few examples. Also the program was implemented to test the truth of predicate.
Зміст
Алгебра висловлювань i як формальна (аксiоматична) теорiя, є важливою i невiд’ємною складовою частиною всiх числень математичної логiки. Однак вона є занадто бiдною для опису та аналiзу найпростiших логiчних міркувань.
Однiєю з причин цього є те, що у численнi висловлювань будь-яке просте висловлення розглядається як вихiдний об’єкт дослiдження, неподiльне цiле, позбавлене частин i внутрiшньої структури, яке має лише одну властивiсть - бути або iстинним, або хибним.
Для того, щоб побудувати систему правил, яка дозволяла б проводити логiчнi мiркування для виведення нетривiальних правильних висновкiв з урахуванням будови i змiсту простих висловлень, використовується формальна теорiя, що дiстала назву числення предикатiв.
Якщо числення висловлювань дає змогу доводити теореми для внутрішніх потреб логіки, то числення предикатів забезпечує можливість описувати й доводити теореми для конкретних розділів математики. Логіка предикатів дає змогу формулювати співвідношення між елементами реального світу і виводити подібні відношення або теореми в математиці. Числення висловлювань – досить вузька логічна система. Існують, наприклад, такі типи логічних міркувань, які не можуть бути здійснені в межах логіки висловлювань:
Коректність цих висновків ґрунтується на внутрішній структурі самих речень і значень слів “кожний” та “існують”.
Існують такі види логічних формул, які не можна записати у вигляді формул числення висловлювань. Наприклад:
Коректність таких висновків базується не тільки на істинності відповідних функціональних відношень, а також і на розумінні таких слів, як “всі”, “всякий” і т.д.
Для того щоб зробити зрозумілішою структуру складних висловлювань, користуються спеціальною мовою – мовою числення предикатів першого порядку.
Теорiя предикатiв починається з аналiзу граматичної будови простих висловлювань i базується на такому висновку: простi висловлювання виражають той факт, що деякi об’єкти (або окремий об’єкт) мають певнi властивостi, або що цi об’єкти знаходяться мiж собою у певному вiдношеннi.
Наприклад, в iстинному висловлюванні «3 є просте число» пiдмет «3» - це об’єкт, а присудок «є просте число» виражає деяку його властивiсть.
У латинськiй граматицi присудок називається предикатом, звiдси цей термiн i увiйшов у математичну логiку. Головним для логiки предикатiв є саме друга складова речення-висловлення - присудок-властивiсть. Вона фiксується, а значення об’єкта пропонується змiнювати так, щоб кожен раз отримувати осмисленi речення, тобто висловлення.
Розглянемо речення, що залежить від параметрів, наприклад «х – парне число», «х менше у», «х + у = z», «х – батько у», «х та у – брати» тощо. Якщо х, у, z у перших трьох реченнях замінити деякими числами, то матимемо певні висловлення, які можуть бути істинними або хибними. Наприклад, «3 – парне число», «2 менше 5», «3 + 2 = 7». Останні два речення виражають родинні відносини між членами сім’ї і перетворюються на певні висловлення, істинні або хибні, при заміні х та у іменами членів сім’ї: «Іван – батько Петра», «Іван і Олег брати».
Речення такого типу називаються предикатами. Точніше предикатом Р(х1,...,хn) називається функція, змінні якої набувають значень із деякої множини М, а сама вона набуває двох значень: 1 (істинне) і 0 (хибне), тобто Р(х1,...,хn): Мn → {1, 0}.
Множина M називається предметною областю, або унiверсальною множиною, а x1,x2,...,xn - предметними змiнними, або термами предиката P.
Множина елементiв (a1,a2,...,an)ÎMn таких, що P(a1,a2,...,an) = 1 називається областю iстинностi (або характеристичною множиною) предиката P.
Якщо P(a1,a2,...,an) = 1, то згiдно з логiчною iнтерпретацiєю будемо говорити, що предикат P є iстинним на (a1,a2,...,an). У супротивному разi, стверджуємо, що предикат P є хибним.
Предикат n аргументів називається n-місним. Множина М значень змінних визначається математичним контекстом. Наприклад, основне співвідношення елементарної геометрії «будь-які дві точки х, у лежать на одній прямій» можна виразити предикатом змінних х, у; а «будь-які три точки лежать в одній площині» - предикатом трьох змінних х, у, z.
Для n = 1 предикат P(x) називається одномiсним або унарним, для n = 2 P(x,y) - двомiсним або бiнарним, для n = 3 P(x,y,z) - трьохмiсним або тернарним предикатом.
Очевидно, що коли в n-арному предикатi P(x1,x2,...,xn) зафiксувати деякi m змiнних (тобто надати їм певних значень з множини M), то отримаємо (n-m)-мiсний предикат на множинi M. Це дозволяє вважати висловлення нульмiсними предикатами, якi утворено з багатомiсних предикатiв пiдстановкою замiсть усiх їхнiх параметрів певних значень з предметної областi. Таким чином, висловлення можна розглядати як окремий випадок предиката.
Для довiльної множини M i довiльного n iснує взаємно однозначна вiдповiднiсть мiж сукупнiстю всiх n-мiсних предикатiв на M i множиною всiх n-арних вiдношень на M. А саме, будь-якому предикату P(x1,x2,...,xn) вiдповiдає вiдношення R таке, що (a1,a2,...,an)ÎR тодi i тiльки тодi, коли P(a1,a2,...,an) = 1. Очевидно, що при цьому R є областю iстинностi предиката P.
Зокрема, будь-якiй функцiональнiй вiдповiдностi або функцiї f: Mn®M можна поставити у вiдповiднiсть (n+1)-мiсний предикат P на M такий, що P(a1,a2,...,an,an+1) = 1 тодi i тiльки тодi, коли f(a1,a2,...,an) = an+1.
Отже, такi фундаментальнi математичнi поняття як вiдповiднiсть (зокрема, функцiя), вiдношення, висловлювання можна розглядати як окремi випадки бiльш загального поняття предиката.
Предикати позначають великими літерами латинського алфавіту. Іноді буває зручно вказувати число змінних предикатів. У таких випадках символи предикатів доповнюють верхнім індексом, який вказує число аргументів, наприклад Р(n)(х1,...,хn) – n-місний предикат. Висловлення вважається нуль- місним предикатом.
Над предикатами можна виконувати звичайні логічні операції. У підсумку утворюються нові предикати.
Як з елементарних висловлень за допомогою логiчних операцiй можна утворювати складенi висловлення, так i, використовуючи простi (елементарнi) предикати i логiчнi зв’язки (операцiї), можна будувати складенi предикати або предикатнi формули.
Як правило, основнi логiчнi операцiї Ù, Ú, Ø, ®, ~ встановлюють для предикатiв, що заданi на однiй i тiй самiй предметнiй областi M i залежать вiд тих самих змiнних.
Нехай P(x1,x2,...,xn) i Q(x1,x2,...,xn) - n-мiснi предикати на множинi M.
Кон’юнкцiєю P(x1,x2,...,xn)ÙQ(x1,x2,...,xn
Очевидно, що область
iстинностi предиката R(x1,x2,...,xn) = P(
Диз’юнкцiєю P(x1,x2,...,xn)ÚQ(x1,x2,...,xn
Областю iстинностi предиката T(x1,x2,...,xn) буде об’єднання областей iстинностi предикатiв P(x1,x2,...,xn) i Q(x1,x2,...,xn).
Запереченням ØP(x1,x2,...,xn) предиката P(x1,x2,...,xn) називають предикат S(x1,x2,...,xn), який дорiвнює 1 на тих i лише тих значеннях термiнів, на яких предикат P(x1,x2,...,xn) дорiвнює 0.
Область iстинностi предиката S(x1,x2,...,xn) = ØP
Аналогiчним чином вводять й iншi логiчнi операцiї ®, ~ тощо. Як правило, кожнiй iз цих операцiй вiдповiдає певна теоретико-множинна операцiя над областями iстинностi предикатiв-операндiв. Неважко узагальнити означення всiх введених операцiй для предикатiв P(x1,x2,...,xn) i Q(y1,y2,...,ym), що залежать вiд рiзних змiнних i мають рiзну мiснiсть.
Знаючи, як виконуються окремi операцiї, можна утворювати вирази або формули, операндами яких є предикати. Наприклад розглянемо формулу P1(x)Ú(ØP3(x,z)®P2(y,x,z)), що задає деякий предикат Q(x,y,z). Значення предиката Q неважко обчислити для будь-якого набору значень його термiв x, y, z, виходячи зi значень предикатiв P1, P2, P3 на цьому наборi.
Приклад: Нехай, Р(1)(х) позначає предикат “х ділиться на два”, Q(1)(х) – предикат “х ділиться на три”. Тоді вираз Р(1)(х) & Q(1)(х) позначає предикат “х ділиться на два та х ділиться на три”, тобто позначає предикат ділення на шість.
Крім операцій логіки висловлень будемо ще застосовувати операції зв’язування квантором.
Додатково в логiцi предикатiв використовують двi спецiальнi операцiї, якi називають кванторами. За допомогою цих операцiй теорiя предикатiв стає значно гнучкiшою, глибшою i багатшою, нiж теорiя висловлень. Саме тому логiку предикатiв iнодi називають теорiєю квантифiкацiї.
Найпопулярнiшими
i найбiльш часто вживаними
Квантор загальності
Нехай, Р(х) – деякий предикат, який набуває значень 1 або 0 для кожного елемента х множини М. Тоді під виразом (" х) Р(х) матимемо на увазі істинне висловлення, коли Р(х) – істинне для кожного елемента х із множини М, і хибне – в іншому випадку. Читається цей вираз так: «для всіх х Р(х)» або «для будь-якого х Р(х)». Це висловлення вже не залежить від х. Символ " називається квантором загальності.
Історія вивчення кванторів
Квантори вживаються в будь-якому осмисленому тексті. Однак, протягом тисячоліть їхнє вживання було чисто інтуїтивним і не до кінця усвідомленим навіть в математиці; кванторні вирази формулювалися словами, спеціальних символів для їхнього позначення не було. Як теоретичні об'єкти квантори вперше введені Ґ. Фреґе в роботі Begriffsschrift 1879 р. разом із теорією їхнього застосування (див.: Теорія квантифікації). Терміни «квантор» і «квантифікація» ввів у 1885 р. Чарлз Пірс, який перевідкрив тоді квантори.
Сучасна символіка на позначення кванторів належить Б. Расселу, який модифікував відповідні позначення Дж. Пеано. Сучасні математики, на відміну від логіків, продовжують формулювати кванторні вирази переважно словами, однак вивчають теорію квантифікації з метою уникнення помилок при навішуванні кванторів.
Символіка й термінологія
Якщо предикат не містить інших змінних, окрім , вирази та є реченнями, що виражають істинні або хибні висловлювання. Перше називається універсальним висловлюванням (або висловлюванням загальності), а друге — екзистенціальним висловлюванням (або висловлюванням існування). Універсальне висловлювання означає, що властивість мають всі індивіди (предмети) з обраної індивідної області; екзистенціальне висловлювання означає, що властивість має бодай один індивід з розглядуваної індивідної області. Коли висловлюватися в теоретико-множинних термінах, універсальне висловлювання говорить, що область істинності предиката є універсальною (збігається з індивідною областю), а екзистенціальне висловлювання говорить, що область істинності предиката непорожня.