Проблема розв’язання

Визначення поняття закону класичної логіки предика­тів (загальнозначимої формули) і логічного слідування в логіці предикатів передбачає відповідь на такі запитання:

а) За допомогою якої процедури можна встановити чи є деяка формула А законом чи ні?

б) За яких умов із формул А₁, A₂,..., A_n слідує формула В ?

У класичній логіці висловлювань самі визначення логі­чного закону і логічного слідування містять вказівку на перевірочну процедуру, яка дозволяє встановити чи є дана формула законом, і чи слідує із формули A₁, A₂,..., A_n фо­рмула В.

Тобто, щоб встановити чи є формула А законом, необ­хідно у відповідності з визначенням тотожно-істинної фор­мули побудувати таблицю істинності для А і з’ясувати, чи приймає А значення «і» в усіх рядках таблиці.

А для відповіді на запитання чи слідує формула В із А₁, А₂,..., А_п, необхідно у відповідності з визначенням логічно­го слідування в класичній логіці висловлювань, побудува­ти спільну таблицю істинності для формул А₁, А₂,..., А_п і В і з’ясувати, чи є в цій таблиці рядок, коли А₁, А₂,..., А_п приймає значення «і», а для В значення «х».

Оскільки процес побудови таблиць істинності є алгори­тмічним, то перевірити, чи є довільна формула логіки ви­словлювань її законом (а також чи має місце відношення логічного слідування між формулами А₁, А₂,..., А_п і В), мо­жна кінцевою кількістю кроків. Ті логічні теорії, в яких це можна здійснити, називаються розв’язуваними.

Дефініція: «Логічна теорія називається розв’язуваною, якщо існує ефективна процедура (алгоритм), що дозво­ляє для будь-якої формули кінцевим числом кроків ви­рішити питання про те, чи є ця формула законом тео­рії чи ні».

Класична логіка висловлювань є розв’язуваною.

Справді, щоб встановити загальнозначимість формули А, необхідно розглянути всі моделі і всі приписування зна­чень предметним змінним і переконатися, що в кожному випадку А приймає значення «істина». А для того, щоб показати, що А1, А₂,..., А_п |= В слід розглянути всі моделі і всі приписування і переконатися, що відсутня ситуація, коли А1, А₂,..., А_п приймають значення «істина», а В — значення «хиба».

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

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

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

Суть цього методу полягає в тому, що теза про за- гальнозначимість формули А і теза про слідування фо­рмули В із А1, А₂,...,А_п обгрунтовуються способом мір­кування від супротивного.

Наприклад, для обгрунтування тези, показують, що припущення хибності А з необхідністю приводить до протиріччя. Для обгрунтування тези показують, що припущення істинності A₁, A₂,..., A_n і хи­бності В приводить до протиріччя.

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

— Кожен крок в аналітичній таблиці відображає за­стосування відповідного аналітичного правила;

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

— кроки позначають римськими цифрами (І, П, Ш тощо);

— рядки — арабськими цифрами (1, 2, 3 тощо);

— нумерація рядків аналітичної таблиці починаєть­ся з нуля (0). Цим підкреслюється, що ми починаємо будувати аналітичну таблицю із антитези;

— вся таблиця від нульового рядка до останнього розбивається на гілки;

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

— кожному із цих правил приписується індекс Т («істина») і F («хиба»).

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

Якщо в гілці є формула С із обома індексами Т і F, то така гілка вважається замкненою. A якщо в кожній гі­лці зустрічається деяка формула із індексами Т і F, то вся таблиця є замкненою.

При отриманні такого результату теза про загальнозна- чимість формули А або ж про слідування В із А₁, А₂,..., А_п вважається обгрунтованою.

Визначення аналітичних правил

Аналітичні правила для V і ∃ супроводимо деякими по­ясненнями.

де а — будь-яка предметна змінна.

У відповідності з логічним смислом квантора загально­сті формула Vx А(х) істинна якщо і тільки якщо будь- який індивід предметної області задовольняє умові А(х).

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

Хибність формули Vx А(х) означає існування об’єкта, який не задовольняє умову А(х):

Відповідно до смислу квантора ∃ істинність ∃x А(х) означає існування об’єкта, що задовольняє умову А(х).

Хибність формулиозначає, що будь-який ін­

дивід предметної області не задовольняє умову А(х).

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

Дефініція: Формула А загальнозначимаякщо і тільки якщо існує замкнена аналітична таблиця, нульо­вий рядок якої представлений антитезою.

Дефініція: «Із формули А1, А₂,..., А_п логічно слідує фор­мула В, якщо і тільки якщо існує замкнена аналітична таблиця, нульовий рядок якої представлений виразом

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

містять обмежень на терм, що підставляється на міс­це підкванторної змінної.

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

І. Необхідно методом аналітичних таблиць обгрунтувати тезу:

¹ Як і у логіці висловлювань у таких випадках засновки об’єднують через «А» і до них через перетворює Р(х) в істинне висловлювання, то

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

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

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

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

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

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

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

392

А. Є. Конверський. Логіка

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

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

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

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

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

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

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

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

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

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

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

Якщо замість р підставити Р(х), замість, за­

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

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

Із кожного предикатуі т.д. підстанов­

кою конкретних значень вільним предметним змінним отримаємо прості висловлювання, які є елементами даного складного висловлювання. Те, що отримане складне висло­влювання:

є істинним, випливає із того, що

є законом.

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

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

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

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

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

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

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

б) при зв’язуванні вільних індивідних змінних кван­тором Ух і заміщенні вільних предметних змінних кон­кретними предикаторами отримують істинні вислов­лювання.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8. Закон введення 3 для «у»:

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

9. Закон введення ∀ для знайти інтерпретацію, при якій антецедент був би істинним, а консеквент — хибним. Відомо, що кон- секвент буде хибним, якщо, в крайньому випадку, один із кон’юнктів хибний. Неможливо припустити, що висловлю­ванняхибне, інакше весь антецедент буде хибним.

Залишається висловлюванняРозглянемо імплі­

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

Відповідно до закону 14 воно еквівалентнеЦе

означає, що висловлювання

Тоді висловлюваннятеж повинно бути істин-

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

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

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

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

Щоб проінтерпретувати дану формулу таким чином, ко­ли антецедент буде істинним, а консеквент — хибним, не­обхідно припустити, що обидва екзистенційні висловлю-

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

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

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

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

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

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

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

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

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

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

а) виписати всі висловлювання без заперечення;

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

в) зняти заперечення перед кванторами.

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

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

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

Маємо вираз:

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

За законом 14 у вихідному виразі загальне висловлю­вання заміним екзестенційним.

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

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

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

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

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

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