++

Очевидно, що ця аналітична таблиця замкнена, отже

теза є загальнозначимим виразом.

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

7. Закони логіки предикатів

При розгляді визначення закону логіки висловлювань вказувалося, що це такий вираз, який при будь-якому розподілі значень істинності своїх пропозиційних змінних приймає значення «і».

Те саме за кінцевим результатом, мається на увазі, коли говориться про закон логіки предикатів. Тобто, законом

логіки предикатів є вираз із якого при будь-якій підста- новці значень вільних змінних отримують істинне ви-

словлювання. Але тут йдеться про інші набори значень, ніж у логіці висловлювань.

Візьмемо формулу Р(х) і перекладемо природною мовою: «х є джерелом інформації». Від конкретного значення х залежить, чи перетвориться Р(х) у істинне висловлювання:

Р(х) = і.

Якщо за U візьмемо множину книг і ϕ буде приписува- ти х конкретного індивіда із U, то ми отримаємо істинне висловлювання.

Оскільки існує хоча б одне значення х, яке перетворює Р(х) в істинне висловлювання, то | х Р(х)| = «і».

Чи буде х Р(х) істинним висловлюванням, залежить від того, чи перетворюватиметься Р(х) в істинне висловлюван- ня при будь-якому значенні х.

Це безпосередньо підводить до питання, які ж імена ін- дивідів треба підставляти замість х. Іншими словами, що повинно бути універсумом міркування U. Якщо за U (в нашому прикладі) взяти множину книг, то х Р(х) буде іс- тинним висловлюванням, а якщо взяти більш широкий клас, то істинність х Р(х) буде проблематичною.

Залежність перетворення формули Р(х) в істинне висло- влювання від предметної області U зумовлює те, що зако- ни логіки предикатів треба шукати серед таких виразів, які не залежать від спеціальної області індивідів, а значи- мі для будь-яких непустих індивідних областей.

Цим фактично відрізняються закони логіки від законів конкретних наук, істинність яких детермінована конкрет- ними предметними областями.

Розглянута вище формула Р(х) окрім предметної змінної має предикаторну константу «джерело інформації». Треба мати на увазі, що логіка предикатів займається предика- тами взагалі, тобто в ній також мало говориться про конк- ретні висловлювання, як і в логіці висловлювань.

Логіку предикатів головним чином цікавлять стру- ктури висловлювань незалежно від їх конкретного змі-

сту. Тому в ній оперують предикаторними змінними. Зро- зуміло, що у виразі «Сократ є Р» від значення Р залежить чи буде цей вираз істинним висловлюванням. Якщо Р за- мінити предикатором «філософ», то отримаємо істинне ви- словлювання, а якщо Р замінити предикатором «фізик», то

висловлювання буде хибним. Очевидно, що в цьому випад- ку істинність формули Р(х) залежить від інтерпретації предикатної змінної.

Виходить, що закони логіки предикатів треба шукати серед таких виразів, які не залежать ні від конкретних ін- дивідуальних областей, ні від конкретних значень преди- катних змінних.

Прикладом є вираз:

х (Р(х) Р(х)).

Тут при будь-якому значенні індивідної змінної х і при будь-якому значенні предикатної змінної Р матимемо іс- тинне висловлювання, оскільки для будь-якого індивіда вірно, що йому притаманна певна властивість чи ні.

Даний вираз нагадує тавтологію із класичної логіки ви-

словлювань

р р.

Підсумовуючи наведені вище загальні зауваження, мож- на дати таке визначення закону логіки предикатів:

«Законом логіки предикатів є вираз логіки предика-

тів, який при будь-якому значенні індивідних і преди- катних змінних приймає значення «істина».

При цьому треба мати на увазі, що коли індивідна об- ласть порожня, то не всі закони логіки предикатів дійсні.

Як і у логіці висловлювань, у логіці предикатів центральне місце посідають закони, процедури їх знаходження і отриман- ня. Тобто, можливо отримати нові закони, перетворюючи уже існуючі, можна отримувати закони логіки предикатів із законів логіки висловлювань шляхом підстановки.

Суть отримання законів логіки предикатів із законів логіки висловлювань шляхом підстановки полягає в за- міщенні у законі логіки висловлювань пропозиційних змінних предикатами. Замість однієї і тієї самої про- позиційної змінної підставляють один і той самий пре- дикат.

Наприклад, візьмемо закон логіки висловлювань:

((p q) r) ((p r) q).

Якщо замість р підставити Р(х), замість q – Q(x), за- мість r – R(x), то отримаємо закон логіки предикатів:

((Р(х) Q(x)) R(x)) ((P(x) R(x)) Q(x)).

Можна легко переконатися, що обидва вирази є законами. Із кожного предикату Р(х), Q(x), R(x) і т.д. підстанов- кою конкретних значень вільним предметним змінним отримаємо прості висловлювання, які є елементами даного складного висловлювання. Те, що отримане складне висло-

влювання:

((Р(а) Q(a)) R(a)) ((P(a) R(a)) Q(a))

є істинним, випливає із того, що ((p q) r) ((p r) q) є законом.

Із цього ж закону логіки висловлювань можна отримати також інші закони логіки предикатів, користуючись кван- тором х.

Для цього необхідно:

1) у законі логіки висловлювань замість пропозицій- них змінних підставити предикати так, щоб замість кожного входження однієї і тієї самої пропозиційної змінної стояв один і той самий предикат і

2) всі вільні предметні змінні зв’язувати квантором загальності.

Отже, при тих самих підстановках, що й раніше, із

((p q) r) ((p r) q)

отримаємо закон логіки предикатів:

x [((P(x) Q(x)) R(x)) ((P(x) R(x)) Q(x))]

Смисл цієї процедури полягає у тому, що:

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

б) при зв’язуванні вільних індивідних змінних кван- тором х і заміщенні вільних предметних змінних кон-

кретними предикаторами отримують істинні вислов- лювання.

Це говорить про те, що кожен вираз логіки предикатів, загальнозначимий у логіці висловлювань, є загальнозна- чимим і в логіці предикатів. Із цього слідує, що якщо зве- сти вираз логіки предикатів до виразу логіки висловлю- вань, то цим самим полегшиться проблема розв’язання виразів логіки предикатів.

Але не кожен загальнозначимий вираз логіки предика- тів буде загальнозначимим виразом логіки висловлювань. У протилежному випадку проблему розв’язання в логіці предикатів можна було б звести до процедур розв’язання характерних для логіки висловлювань.

Візьмемо виконувані вирази логіки предикатів і логіки висловлювань і перевіримо, чи існує між ними однозначна відповідність, як між тавтологіями логіки висловлювань і логіки предикатів.

Виявляється, що такої відповідності немає. У результаті підстановки із виконуваного, але не загальнозначимого ви- разу логіки висловлювань можна отримати протиріччя ло- гіки предикатів.

Для прикладу візьмемо вираз логіки висловлювань: p q.

Підставимо замість р формулу х (Р(х) Р(х)), а замість q – x Q(x). У результаті отримаємо протиріччя:

х (Р(х) Р(х)) х Q(x).

Те, що даний вираз при будь-якому наборі значень буде хибний, залежить від формули, яку підставляють замість р.

Але та сама підстановка в законі логіки висловлювань знову приводить до закону.

Якщо у вираз р р замість р підставити нашу формулу

х (Р(х) Р(х)),

то ми отримаємо тавтологію:

х (Р(х) Р(х)) х (Р(х) Р(х)).

Загальнозначимість цього виразу визначається тепер за- гальнозначимістю формули: х (Р(х) Р(х)).

Стосовно такої характеристики формул як «невикону-

ваність» зауважимо, що кожна формула логіки преди-

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

Окрім законів логіки предикатів, які можливо отримати із законів логіки висловлювань шляхом вказаних перетво-

рень, існує група своєрідних законів у цій логічній теорії, на перегляді яких ми і зупинимося.

1. Закон усунення :

х Р(х) Р(t),

де P(t) – результат заміни всіх вільних входжень змінної х на замкнений терм t.

Цей закон стверджує, що якщо кожен індивід х володіє властивістю Р, то і конкретно визначений індивід t має цю властивість.

2. Закон введення :

Р(t) x P(x)

Цей закон фіксує той факт, що якщо деякий конкрет- ний індивід має властивість Р, то існує, в крайньому випа- дку, один індивід із такою властивістю.

Якщо взяти обидва ці закони як засновки, то отримаємо третій закон, закон підпорядкування:

х Р(х) Р(t)

P(t) x P(x)

x P(x) x P(x).

Тут застосовується правило транзитивності імплікації.

3.Закон підпорядкування:

х Р(х) х Р(х).

4.Закон введення квантора загальності для « »:

х [(P(x) Q(x)] [ x P(x) x Q(x)]

Згідно з цим законом кожен індивід володіє певною влас- тивістю Р(х) і Q(х) тоді і тільки тоді, коли кожен індивід має властивість Р(х) і кожен індивід має властивість Q(x).

Наприклад, кожний квадрат має рівні сторони і прямі кути тоді і тільки тоді, коли кожний квадрат має рівні сторони і кожний квадрат має прямі кути.

5.Закон введення квантора існування для « »:

х [P(x) Q(x)] [ x P(x) x Q(x)].

Якщо існують об’єкти, які мають властивість Р(х) і Q(x), то існують об’єкти, які мають властивість Р(х) і іс- нують об’єкти, які мають властивість Q(x).

Наприклад, якщо є книги, які мають пізнавальний і ме- тодичний характер, то існують книги, які мають пізнава- льний характер і книги, які мають методичний характер.

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

6. Закон введення для « »:

х (Р(х) Q(x)) [ x P(x) x Q(x)].

7. Закон виведення для « »:

[ x P(x) x Q(x)] x [P(x) Q(x)].

Якщо всі індивіди мають властивість Р(х), або всі інди- віди мають властивість Q(x), то всі індивіди мають власти- вість Р(х) або Q(x).

Для цього закону також не властива оберненість, тобто переміна місцями членів імплікації веде до втрати загаль- нозначимості.

Наприклад, вірно, що кожен депутат або прибічник ре- форм, або не прибічник реформ, але не вірно ні те, що ко- жен депутат прибічник реформ, ні те, що кожен депутат не

Із цього закону випливає, що індивіди із властивістю Р(х) або Q(x) існують тоді і тільки тоді, коли існують інди- віди з властивістю Р(х) або індивіди з властивістю Q(x). Оскільки диз’юнкція істинна, коли один із її членів істин- ний, то для істинності х [Р(х) Q(х)] не має значення, чи буде істинне х Р(х), чи х Q(x), або обидва будуть істинні.

9. Закон введення для « »:

х [Р(х) Q(x)] [ x P(x) x Q(x)].

Якщо всі х мають властивість Р(х), то вони мають власти- вість Q(x), тоді вірно, що якщо кожен х має властивість Р(х), то кожен х має властивість Q(x). Конкретизувати зазначене мож-

на так: «Якщо для кожного студента, який успішно складе сесію, вірно, що він отримає стипендію, тоді вірно, якщо ко- жен студент складе сесію, то кожен отримає стипендію».

У законах 1-9 використовуються лише одномісні предика- тори. Але так само як шляхом підстановки ми із законів логі- ки висловлювань отримували закони логіки предикатів, мож-

на отримувати закони багатомісної логіки предикатів. Для цього необхідно замість одномісних предикатів

поставити багатомісні і ввести стільки кванторів, щоб усі предметні змінні були зв’язані.

Наприклад, із 9 закону можна отримати закон 9′:

9′. х у [K(x,y) S(x,y)] [ x y K(x,y) x y S(x,y)].

Закони перестановки кванторів:

10.x y R(x,y) y x R(x,y)

11.x y R(x,y) y x R(x,y)

12.x y R(x,y) y x R(x,y).

Закони заперечення кванторів:

13. Р(х) х Р(х) 14. Р(х) х Р(х).

Закони взаємовираженості кванторів:

15.х Р(х) х Р(х)

16.х Р(х) х Р(х).

Названі закони використовуються при побудові доведень у логіці предикатів, а також при здійсненні процедур розв’язання для виразів логіки предикатів.

Одна із процедур розв’язання в логіці предикатів роз- глядалася вище. Вона зводилася до застосування методу аналітичних таблиць. А тепер зупинимося на інших про- цедурах.

8.Процедури для розв’язання виразів логіки предикатів

Улогіці предикатів, на відміну від логіки висловлю- вань, немає універсального способу для розв’язання будь- яких виразів логіки предикатів. Тому один із способів

розв’язання полягає у тому, щоб вираз, який потрібно розв’язати, звести до виразу логіки висловлювань і вже до нього застосувати процедури розв’язання із логіки висловлювань.

Для досить великої групи виразів логіки предикатів можна встановити їх загальнозначимість за допомогою за- собів процедури розв’язання логіки висловлювань.

Основна ідея тут та сама, що й при розв’язанні ви- разів логіки висловлювань. Спочатку припускаємо, що вираз, який потрібно розв’язати, не загальнозначимий. Здійснюємо відповідні кроки, щоб знайти такий розпо- діл значень істинності або інтерпретацію, при якій да- ний вираз буде хибним. Якщо з’ясовується, що такого розподілу значень або такої інтерпретації не існує, то- ді вираз вважається загальнозначимим.

Наприклад, візьмемо вираз:

Цим досягається, що в області квантора знаходяться не складні предикати, а прості.

[( x M(x) x P(x)) ( x S(x)x M(x))] ( x S(x) x P(x)).

Наша формула має вид імплікації.

Припустимо, що вона не загальнозначима, тобто хоча б при одному наборі значень вона хибна. Але це можливо тоді,

коли антецедент – істинний, а консеквент – хибний. Консеквент буде хибним коли висловлювання х S(x) –

істинне, а х Р(х) – хибне. Нехай буде так. Тоді ці вира- зи в антецеденті приймають такі значення:

[( x M(x) x P(x)) ( x S(x) x M(x))]

↓↓

хі

Оскільки антецедент є істинною кон’юнкцією, то обидва кон’юнкти повинні бути істинними. Тому у першо- му кон’юнкті висловлюванню х М(х) треба надати зна- чення «хиба», інакше ( х М(х) х Р(х)) буде хибним, а у другому кон’юнкті висловлюванню х М(х) треба надати значення «істина», інакше вираз ( x S(x) x M(x)) – буде хибним.

Але зрозуміло, що одному і тому самому елементарному висловлюванню в межах конкретного складного висловлю- вання не можна одночасно приписувати значення «істи-

на» і «хиба».

Отже, припущення, що вихідний вираз є не загально- значимий не вірне.

Візьмемо наступний приклад:

[( x P(x) x M(x)) x S(x) x M(x)]( x S(x) x P(x)).

Спробуємо знайти інтерпретацію, при якій антецедент був би істинним, а консеквент – хибним. Відомо, що кон- секвент буде хибним, якщо, в крайньому випадку, один із кон’юнктів хибний. Неможливо припустити, що висловлю- вання х S(x) хибне, інакше весь антецедент буде хибним.

Залишається висловлювання хP (х). Розглянемо імплі- кацію в антецеденті. Згідно з припущенням висловлю-

вання хP (х) – хибне.

Відповідно до закону 14 воно еквівалентне х Р(х). Це означає, що висловлювання х Р(х) – істинне.

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

гальнозначимим.

Але ця процедура не є ефективною для всіх формул ло- гіки предикатів.

Розглянемо формулу:

[ x (M(x) P(x)) x (S(x) M(x))] x (S(x) P(x)).

Застосуємо до цього виразу закони 9 і 5:

Щоб проінтерпретувати дану формулу таким чином, ко- ли антецедент буде істинним, а консеквент – хибним, не- обхідно припустити, що обидва екзистенційні висловлю- вання в антецеденті – істинні і цим самим х S(x) істинне в консеквенті, а хP (х) – хибне в ньому.

Із хибності х Р(х) випливає хибність х Р(х). Із попе- редніх припущень нічого не випливає стосовно значення висловлювання х М(х):

[( x M(x) x P(x)) x S(x) x M(x)]

З передбачуваною істинністю х М(х) сумісна як істин- ність, так і хибність х М(х). При істинності х М(х) імплікація буде хибною, а при хибності х М(х) – вона буде істинною.

Процедуру розв’язання, яку ми щойно застосували до наведених виразів (позначимо її літерою «А»), можна описати так:

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

2) знайти інтерпретацію для отриманого виразу, виходячи із припущення про те, що цей вираз хибний.

Розглянемо ще одну процедуру розв’язання (позначимо її літерою «В»). Як процедура «А» так і процедура «В» спрямовані на розв’язання виразів, які в традиційній логі- ці представляють різновиди умовиводів. Тому ці вирази

мають вид імплікації, де антецедентом є кон’юнкція засновків, а консеквентом – висновок.

Ця процедура складається з таких кроків:

1.Використовуючи відповідні закони, перетворити всі наявні у вихідній формулі загальні висловлювання в екзи- стенційні.

2.Перетворити екзистенційні висловлювання так, щоб в області дії квантора були тільки кон’юнкція і заперечення, яке б відносилося до простих предикатів.

3.Замінити консеквент вихідного виразу його запере- ченням, а імплікацію – на кон’юнкцію.

4.Перевірити, чи немає в отриманій кон’юнкції хоча б одного кон’юнкта із запереченням і без нього.

5.Якщо в цьому виразі є висловлювання із заперечен- ням і без нього, тоді необхідно виконати такі дії:

а) виписати всі висловлювання без заперечення; б) приєднати до них через імплікацію диз’юнкцію ви-

словлювань, які мають заперечення; в) зняти заперечення перед кванторами.

6.Зняти квантори і предметні змінні.

7.Отриманий вираз перевірити або за допомогою табли- ці істинності або зведенням до КНФ.

Звернемося до прикладу.

Маємо вираз:

[ x M(x) P(x)) x (S(x) M(x)] x (S(x) P(x)).

Перевіримо його на загальнозначимість.

1. [ x (M(x) P(x)) x (S(x) M(x))] x (S(x) P(x))

За законом 14 у вихідному виразі загальне висловлю-

вання заміним екзестенційним.

2. x (M(x) P(x)) x (S(x) M(x)) x (S(x) P(x)).

Замінимо консеквент його запереченням, а імплікацію

– кон’юнкцією.

3. x (S(x) M(x)) [ x (M(x) P(x)) x (S(x) P(x))].

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

4. (S M) [(M P) (S P)]

Усуваємо квантори і предметні змінні.

Фактично ми звели вихідний вираз до виразу логіки ви- словлювань, тому є можливість привести його до КНФ.