Висновок в обчисленні предікатов- це не порожня і кінцева послідовність формул, кожна з яких є або посилкою, або отримана з попередніх формул відповідно до одного з дедуктивних принципів так, що після застосування правилÉвіØввсе формули, починаючи з останньої посилки і аж до результату застосування даного правила, не використовуються в подальших кроках побудови виведення, при цьому жодна змінна не обмежує сама себе і жодна індивідуальна змінна не обмежується абсолютно більш ніж один раз. У тому випадку, якщо жодна абсолютно обмежується у висновку змінна не зустрічається вільно в неісключённих посилках і укладанні, має місце завершений висновок.
Визначення докази в класичному численні предикатів ідентичне визначенню докази в класичному численні висловлювань, тому завершене доказ розуміється як завершений висновок з порожньої множини неісключённих посилок.
Покроковий перехід від однієї формули до іншої здійснюється в численні предикатів за допомогою виконання всіх правил виведення, що застосовуються в обчисленні висловлювань, до яких додаються кванторние правила виведення. а саме: 1) введення. 2) виключення кванторів.
До дедуктивним принципам введення кванторів відносяться правила:
1.1. - введення квантора спільності (позначимо символом «" в "), яке виражається схемою:
______________________. гдеy- абсолютне обмеження, z1. ..., zn - обмеження.
1.2. - введення квантора існування (позначимо символом «$ в»), яке виражається схемою:
2.1.- виключення квантора спільності (позначимо символом «" і "), яке виражається схемою:
2.2. - виключення квантора існування (позначимо символом «$ і»), яке виражається схемою:
______________________. гдеy- абсолютне обмеження, z1. ..., zn - обмеження.
У правилах «введення квантора існування» і «виключення квантора спільності» запис A (x / t) означає результат правильного заміщення термо t всіх наявних у формулі A (x) вільних входжень предметної змінної x.
Нехай формула A (x) є записом виразу $ x (P 2 (x, y)ÉQ 2 (x, z)). Припустимо, що універсумом міркування є безліч міст, замість вільної змінної y підставляється терм - предметна постійна, що має значення «Омськ», замість z - предметна постійна, що має значення «Тара», і P 2 - предікаторная постійна, що має значення «старше», а Q 2 - предікаторная постійна, що має значення «молодший», тоді ми отримуємо правильну підстановку, оскільки судження «Існують міста, такі що вони старше Омська, але молодше Тари» істинно.
Але в силу того, що розглянута формула $ x (P 2 (x, y)ÉQ 2 (x, z)). будучи здійсненним, не є загальнозначущої формулою логіки предикатів, можна здійснити і таку підстановку термів замість вільних змінних y і z. що дана формула матиме завжди помилкове значення.
Припустимо, що універсумом міркування є безліч людей, замість вільної змінної y підставляється складний функціональний терм, що має значення «бути батьком людини», замість z - складний функціональний терм, що має значення «бути предком людини», і P 2 - предікаторная постійна, що має значення «молодше», а Q 2 - предікаторная постійна, що має значення «старше», тоді отримуємо неправильну підстановку, оскільки судження «Існують люди, такі що вони старше батьків, але молодше нащадків» є хибним завжди.
В даному випадку вільно входить в підставляються складні функціональні терми змінна «людина» виявилася в результаті цієї підстановки пов'язаної (потрапила в область дії квантора), що зумовило семантичну некоректність формули.
Правільнойназивается така підстановка термаtвместо всіх вільних входжень предметної переменнойxформулиА (x), при якій жодна входить в цей терм змінна не виявиться пов'язаної на місцях, де цей терм з'являється в результаті підстановки.
Запис А (x / y, z1. ..., zn) в правилах «введення квантора спільності» і «виключення квантора існування» є фіксація окремого випадку правильної підстановки предметної змінної y на місце всіх вільних входжень предметної змінної x в вираженні А (x, z1 . ..., zn).
Вміщені в правилах «введення квантора спільності» і «виключення квантора існування» вказівки виду «y - абсолютне обмеження; z1. ..., zn - обмеження »обумовлені тим, що з змістовної точки зору вільні предметні змінні є пробігають по універсуму міркування (деякого безлічі предметів), приймаючи в обраному универсуме будь-які значення (в такому випадку вони використовуються в інтерпретації загальності). Але будучи включеними до складу формул логіки предикатів предметні змінні іноді не виконують цю роль, оскільки не виступають в якості знаків, що позначають саме будь-який об'єкт універсуму міркування (т. Е. Використовуються в інтерпретації загальності). Таким чином, мають місце два можливих випадки функціонування предметної змінної в складі формул.
Вільна індивідуальна переменнаяіспользуется у формулі в інтерпретації загальності тоді і тільки тоді, коли в складі цієї формули дана предметна змінна трактується як знак, що позначає будь-який об'єкт з універсуму міркування.
У вираженні x + y = y + x, що представляє собою закон перестановки складання, змінні x і y вжиті в інтерпретації загальності, так як це співвідношення істинно при будь-яких значеннях x і y.
Іншу ситуацію маємо в тому випадку, коли змінні входять до складу, наприклад, математичних рівнянь. Так, у виразі x + 5 = 8 змінна x вже не використовується в інтерпретації загальності, оскільки не позначає довільний об'єкт з універсуму. Навпаки, можливі значення для x строго фіксовані, т. Е. Обмежені умовою цього твердження. У цьому випадку говорять, що змінна використана в умовній інтерпретації.
Використовуючи вищезазначений перелік і тлумачення правил виведення, звернемо увагу на той факт, що поняття виведення і докази в класичній логіці предикатів залишаються формально тими ж, що і в класичній логіці висловлювань, тому в логіці предикатів працюють всі правила виведення числення висловлень, але до них додаються правила квантификации.
З цих же причин в якості евристик в обчисленні логіки предикатів використовуються всі евристики обчислення логіки висловлювань, але до них додається ще одна, четверта евристика.
Четверта евристика полягає в застосуванні першої і другої евристик для вибору посилок після того, як застосування всіх кроків по першій евристиці призвело до формули виду "xA або $ xA.
Обгрунтуванням твердження про виводимості | - Ø $ xØP (x, y, a)É"XP (x, y, a) буде:
1. Ø $ xØP (x, y, a) - сел. (1 евристика). 2. ØP (x, y, a) - сел. (4 евристика). 3. $ xØP (x, y, a) - $ ст. 2. 4. ØØP (x, y, a) - Øв. 1, 3. 5. P (x, y, a) - Øі. 4. 6. "xP (x, y, a) -" в. 5, x - абс. огр .; y - огр. 7. Ø $ xØP (x, y, a)É"XP (x, y, a) - Éв. 6.
I. Які функції пропозіціональних 1) змінних і 2) зв'язок?
II. Що є законом класичної логіки висловлювань?
III. У чому полягають загальні принципи побудови істиннісних таблиць?
V. На які види поділяються правила виведення числення висловлень?
VI. Які евристики і в якій послідовності застосовують у висновках логіки предикатів?
VII. Чи можливо формалізувати засобами логіки висловлювань судження «Для будь-якого предмета з безлічі металів існує такий предмет цієї множини, що ці предмети знаходяться в відношенні подібності» і чому?
VIII. Що називається інтерпретацією, моделлю, зв'язаною і вільною змінними, здійсненним і нездійсненним формулами в класичній логіці предикатів?
IX. Чим схожі й чим відрізняються класичні обчислення логіки предикатів і логіки висловлювань?
Варіанти домашнього завдання по розділу
«Логіка висловлювань і предикатів»
I. Визначте табличним способом значення істинності суджень:
1. Якби тролейбус №1 затримувався на зупинках або їхав повільно, Олег неодмінно запізнився б до початку семінару; але він встиг, значить, тролейбус їхав швидко і не затримувався.
2. Дане число парне, і число, більше його на одиницю, парне.
3. Ейфелева вежа знаходиться в Парижі або вона знаходиться в Лондоні.
II. Підберіть по два приклади всіх можливих модусів умовиводів:
3. Чисто розділових.
III. Які з наступних дилем є правильними?
1. Якщо будеш під час суцільного пожежі на нижніх поверхах хмарочоса спускатися по сходах, то згориш, якщо ж вистрибнеш в вікно, то розіб'єш. Виходить, що, чи не спускаючись по сходах під час сильної пожежі на нижніх поверхах хмарочоса або НЕ вистрибуючи у вікно, чи не згориш або НЕ розіб'єш.
2. Якщо філософ дуаліст, то він не матеріаліст. Якщо філософ діалектик, то він не метафізик. Цей філософ матеріаліст або метафізик. Значить, він не дуаліст або НЕ діалектик.
IV. Визначте тип формули і вирішите методом «від супротивного», чи є дані формули тотожно-істинними:
V. Здійсніть доказ формул: