Конверський А. Є. Логіка (традиційна та сучасна)

Подождите немного. Документ загружается.

Книга друга. СУЧАСНА ЛОГІКА

391

ІІІ. 5. F R(c)

6. F P(a) F ∨ до 2

ІV. 7. Т Р(а) 7′. Т Q(в) Т ∨ до 3

V. 8. F Q(в) 8′. T R(c) 8′′.F Q(в) 8′′′. T R(c).

+ + + +

Факт замкненості гілки позначається знаком «+».

П. Встановити чи є логічним законом вираз:

[ ∀x P(x) ⊃ ∃x P(x)] ∾ [∀xP(x) ⊃ ∃xP(x)].

0. F [ ∀x P(x) ⊃ ∃x P(x)] ∾ [∀x



P(x) ⊃ ∃xP(x)]

І. 1. T (∀x P(x) ⊃ ∃x P(x)) 1′. F (∀x P(x) ⊃ ∃x P(x))

2. F (∀xP(x) ⊃ ∃xP(x)) 2′.T (∀xP(x) ⊃ ∃xP(x)) F∾ до 0

ІІ. 3. F (P(в) ⊃



Р(в)) 3′. F (P(в) ⊃ P(в)) F ∀ до 2,1′

ІІІ. 4. T (P(в) ⊃ P(в)) 4′. T (P(в) ⊃P(в)) Т ∀ до 1,2′

ІV. 5. ТР(в) 5′. Т Р(в) ′

6. FP(в) 6′. F P(в) F ⊃ до 3 і 3′

V. 7. F P(в) 7′. Т Р(в) 7′′. FP(в) 7′′′. ТР(в) Т ⊃ 4 і 4′

VІ. 8. F



P(в) 8′. F



P(в) 8′′. T P(в) 8′′′. F P(в)

+ +

VII. 9. Т Р(в) 9′. Т Р(в).

+ +

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

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

Після того, як ми дали визначення логічного закону і

описали одну із процедур його розв’язання зупинимося на

деяких змістовних міркуваннях відносно природи законів

логіки предикатів і на характеристиці списку найбільш

важливих законів логіки предикатів.

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

При розгляді визначення закону логіки висловлювань

вказувалося, що це такий вираз, який при будь-якому

розподілі значень істинності своїх пропозиційних змінних

приймає значення «і».

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

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

А. Є. Конверський. ЛОГІКА

392

логіки предикатів є вираз із якого при будь-якій підста-

новці значень вільних змінних отримують істинне ви-

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

ніж у логіці висловлювань.

Візьмемо формулу Р(х) і перекладемо природною мовою:

«х є джерелом інформації». Від конкретного значення х

залежить, чи перетвориться Р(х) у істинне висловлювання:

Р(х) = і.

Якщо за U візьмемо множину книг і ϕ буде приписува-

ти х конкретного індивіда із U, то ми отримаємо істинне

висловлювання.

Оскільки існує хоча б одне значення х, яке перетворює

Р(х) в істинне висловлювання, то |∃х Р(х)| = «і».

Чи буде ∀х Р(х) істинним висловлюванням, залежить від

того, чи перетворюватиметься Р(х) в істинне висловлюван-

ня при будь-якому значенні х.

Це безпосередньо підводить до питання, які ж імена ін-

дивідів треба підставляти замість х. Іншими словами, що

повинно бути універсумом міркування U. Якщо за U (в

нашому прикладі) взяти множину книг, то ∀х Р(х) буде іс-

тинним висловлюванням, а якщо взяти більш широкий

клас, то істинність ∀х Р(х) буде проблематичною.

Залежність перетворення формули Р(х) в істинне висло-

влювання від предметної області U зумовлює те, що зако-

ни логіки предикатів треба шукати серед таких виразів,

які не залежать від спеціальної області індивідів, а значи-

мі для будь-яких непустих індивідних областей.

Цим фактично відрізняються закони логіки від законів

конкретних наук, істинність яких детермінована конкрет-

ними предметними областями.

Розглянута вище формула Р(х) окрім предметної змінної

має предикаторну константу «джерело інформації». Треба

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

тами взагалі, тобто в ній також мало говориться про конк-

ретні висловлювання, як і в логіці висловлювань.

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

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

сту. Тому в ній оперують предикаторними змінними. Зро-

зуміло, що у виразі «Сократ є Р» від значення Р залежить

чи буде цей вираз істинним висловлюванням. Якщо Р за-

мінити предикатором «філософ», то отримаємо істинне ви-

словлювання, а якщо Р замінити предикатором «фізик», то

Книга друга. СУЧАСНА ЛОГІКА

393

висловлювання буде хибним. Очевидно, що в цьому випад-

ку істинність формули Р(х) залежить від інтерпретації

предикатної змінної.

Виходить, що закони логіки предикатів треба шукати

серед таких виразів, які не залежать ні від конкретних ін-

дивідуальних областей, ні від конкретних значень преди-

катних змінних.

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

∀х (Р(х) ∨Р(х)).

Тут при будь-якому значенні індивідної змінної х і при

будь-якому значенні предикатної змінної Р матимемо іс-

тинне висловлювання, оскільки для будь-якого індивіда

вірно, що йому притаманна певна властивість чи ні.

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

словлювань

р ∨р.

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

на дати таке визначення закону логіки предикатів:

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

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

катних змінних приймає значення «істина».

При цьому треба мати на увазі, що коли індивідна об-

ласть порожня, то не всі закони логіки предикатів дійсні.

Як і у логіці висловлювань, у логіці предикатів центральне

місце посідають закони, процедури їх знаходження і отриман-

ня. Тобто, можливо отримати нові закони, перетворюючи уже

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

логіки висловлювань шляхом підстановки.

Суть отримання законів логіки предикатів із законів

логіки висловлювань шляхом підстановки полягає в за-

міщенні у законі логіки висловлювань пропозиційних

змінних предикатами. Замість однієї і тієї самої про-

позиційної змінної підставляють один і той самий пре-

дикат.

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

((p ∧ q) ⊃ r) ∾ ((p ∧



r) ⊃q).

Якщо замість р підставити Р(х), замість q – Q(x), за-

мість r – R(x), то отримаємо закон логіки предикатів:

((Р(х) ∧ Q(x)) ⊃ R(x)) ∾ ((P(x) ∧



R(x)) ⊃



Q(x)).

А. Є. Конверський. ЛОГІКА

394

Можна легко переконатися, що обидва вирази є законами.

Із кожного предикату Р(х), 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))]

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

а) вирази, які містяться в квадратних дужках, при

кожному наборі значень вільних предметних змінних

перетворюються в істинні висловлювання;

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

тором ∀х і заміщенні вільних предметних змінних кон-

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

лювання.

Це говорить про те, що кожен вираз логіки предикатів,

загальнозначимий у логіці висловлювань, є загальнозна-

чимим і в логіці предикатів. Із цього слідує, що якщо зве-

сти вираз логіки предикатів до виразу логіки висловлю-

вань, то цим самим полегшиться проблема розв’язання

виразів логіки предикатів.

Книга друга. СУЧАСНА ЛОГІКА

395

Але не кожен загальнозначимий вираз логіки предика-

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

У протилежному випадку проблему розв’язання в логіці

предикатів можна було б звести до процедур розв’язання

характерних для логіки висловлювань.

Візьмемо виконувані вирази логіки предикатів і логіки

висловлювань і перевіримо, чи існує між ними однозначна

відповідність, як між тавтологіями логіки висловлювань і

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

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

підстановки із виконуваного, але не загальнозначимого ви-

разу логіки висловлювань можна отримати протиріччя ло-

гіки предикатів.

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

p ∧ q.

Підставимо замість р формулу ∃х (Р(х) ∧



Р(х)), а замість

q – ∀x Q(x). У результаті отримаємо протиріччя:

∃х (Р(х) ∧Р(х)) ∧ ∀х Q(x).

Те, що даний вираз при будь-якому наборі значень буде

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

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

знову приводить до закону.

Якщо у вираз р ∨



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

∃х (Р(х) ∧Р(х)),

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

∃х (Р(х) ∧Р(х)) ∨∃х (Р(х) ∧Р(х)).

Загальнозначимість цього виразу визначається тепер за-

гальнозначимістю формули: ∃х (Р(х) ∧Р(х)).

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

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

катів, яка невиконувана в логіці висловлювань, в логіці

предикатів буде також невиконуваною. Але невикону-

вана формула є протиріччям. Це дає змогу (як у випадку

із тавтологіями) здійснювати розв’язання таких виразів за-

собами логіки висловлювань.

Окрім законів логіки предикатів, які можливо отримати

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

А. Є. Конверський. ЛОГІКА

396

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

на перегляді яких ми і зупинимося.

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)].

Книга друга. СУЧАСНА ЛОГІКА

397

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

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).

Для цього закону також не властива оберненість, тобто

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

нозначимості.

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

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

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

прибічник реформ.

8. Закон введення ∃ для «∨»:

∃х [P(x) ∨ Q(x)] ∾ [∃x P(x) ∨ ∃x Q(x)].

Із цього закону випливає, що індивіди із властивістю

Р(х) або Q(x) існують тоді і тільки тоді, коли існують інди-

віди з властивістю Р(х) або індивіди з властивістю Q(x).

Оскільки диз’юнкція істинна, коли один із її членів істин-

ний, то для істинності ∃х [Р(х) ∨ Q(х)

]

не має значення, чи

буде істинне ∃х Р(х), чи ∃х Q(x), або обидва будуть істинні.

А. Є. Конверський. ЛОГІКА

398

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. ∃х Р(х) ∾ ∀хР(х).

Названі закони використовуються при побудові доведень

у логіці предикатів, а також при здійсненні процедур

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

Одна із процедур розв’язання в логіці предикатів роз-

глядалася вище. Вона зводилася до застосування методу

аналітичних таблиць. А тепер зупинимося на інших про-

цедурах.

Книга друга. СУЧАСНА ЛОГІКА

399

8. Процедури для розв’язання

виразів логіки предикатів

У логіці предикатів, на відміну від логіки висловлю-

вань, немає універсального способу для розв’язання будь-

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

розв’язання полягає у тому, щоб вираз, який потрібно

розв’язати, звести до виразу логіки висловлювань і вже

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

висловлювань.

Для досить великої групи виразів логіки предикатів

можна встановити їх загальнозначимість за допомогою за-

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

Основна ідея тут та сама, що й при розв’язанні ви-

разів логіки висловлювань. Спочатку припускаємо, що

вираз, який потрібно розв’язати, не загальнозначимий.

Здійснюємо відповідні кроки, щоб знайти такий розпо-

діл значень істинності або інтерпретацію, при якій да-

ний вираз буде хибним. Якщо з’ясовується, що такого

розподілу значень або такої інтерпретації не існує, то-

ді вираз вважається загальнозначимим.

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

[∀x (M(x) ⊃



P(x)) ∧ ∀x (S(x) ⊃ M(x))] ⊃ ∀x (S(x) ⊃



P(x))

і перевіримо, чи є він загальнозначимим.

Застосуємо закон 9 :

∀х (P(x) ⊃ Q(x)) ∾ [∀x P(x) ⊃ ∀x Q(x)].

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

не складні предикати, а прості.

[(∀x M(x) ⊃ ∀x



P(x)) ∧ (∀x S(x) ⊃

⊃ ∀x M(x))] ⊃ (∀x S(x) ⊃ ∀x



P(x)).

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

Припустимо, що вона не загальнозначима, тобто хоча б

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

коли антецедент – істинний, а консеквент – хибний.

Консеквент буде хибним коли висловлювання ∀х S(x) –

істинне, а ∀х Р(х) – хибне. Нехай буде так. Тоді ці вира-

зи в антецеденті приймають такі значення:

А. Є. Конверський. ЛОГІКА

400

[(∀x M(x) ⊃ ∀xP(x)) ∧ (∀x S(x) ⊃ ∀x M(x))]

↓ ↓

х і

Оскільки антецедент є істинною кон’юнкцією, то

обидва кон’юнкти повинні бути істинними. Тому у першо-

му кон’юнкті висловлюванню ∀х М(х) треба надати зна-

чення «хиба», інакше (∀х М(х) ⊃ ∀х



Р(х)) буде хибним, а

у другому кон’юнкті висловлюванню ∀х М(х) треба надати

значення «істина», інакше вираз (∀x S(x) ⊃ ∀x M(x)) –

буде хибним.

Але зрозуміло, що одному і тому самому елементарному

висловлюванню в межах конкретного складного висловлю-

вання не можна одночасно приписувати значення «істи-

на» і «хиба».

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

значимий не вірне.

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

[∀x (P(x) ⊃



M(x)) ∧ ∃x (S(x) ∧ M(x)] ⊃ ∃x (S(x) ∧P(x))

Застосуємо окрім закону 9 ще й закон 5:

([∃x (P(x) ∧ Q(x))] ∾ [∃x P(x) ∧ ∃x Q(x)])

[(∀x P(x) ⊃ ∀x



M(x)) ∧ ∃x S(x) ∧ ∃x M(x)] ⊃

⊃ (∃x S(x) ∧ ∃x



P(x)).

Спробуємо знайти інтерпретацію, при якій антецедент

був би істинним, а консеквент – хибним. Відомо, що кон-

секвент буде хибним, якщо, в крайньому випадку, один із

кон’юнктів хибний. Неможливо припустити, що висловлю-

вання ∃х S(x) хибне, інакше весь антецедент буде хибним.

Залишається висловлювання ∃х

(х). Розглянемо імплі-

кацію в антецеденті. Згідно з припущенням висловлю-

вання ∃х

(х) – хибне.

Відповідно до закону 14 воно еквівалентне ∀х Р(х). Це

означає, що висловлювання ∀х Р(х) – істинне.

Тоді висловлювання ∀х



М(х) теж повинно бути істин-

ним, оскільки за припущенням імплікація (∀хР(х) ⊃

⊃∀хМ(х)) – істинна.

Але ∀х



М(х) еквівалентне ∃х М(х). Тоді хибним є

∃х М(х).