| х Р(х) х Р(х) | = і при ϕ .

Отже, формула є виконуваною.

Дефініція невиконуваної формули: «Формула є невико-

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

Візьмемо для прикладу формулу:

х Р(х) Р(а).

Застосуємо міркування від супротивного. Будемо ствер- джувати, що дана формула виконувана. Тоді повинна існу- вати модель <U,I> і приписування ϕ , при яких вона істин- на. Наша формула є кон’юнкцією. А це означає, що

| х Р(х) | = і і | Р(а) | = і при ϕ .

Істинність Р(а) свідчить про те, що І (а) І (Р). А істинність х Р(х) означає хибність х Р(х).

Визнання цього факту означає, що | Р(х) | = х при при- писуванні будь-якого елемента із U, до речі, і того, який функція І співставляє константі а.

Отже, | Р(х) | = х при приписуванні х об’єкта І (а).

Тоді ми повинні визнати, що І(а) І(Р). Але це супере- чить прийнятому раніше твердженню, що: І(а) І(Р).

Отже, припущення про виконуваність формули х Р(х)

Р(а) неправильне. Дана формула не є виконуваною.

5. Логічні відношення між формулами в S4

До фундаментальних відношень у класичній логіці предикатів відносять:

відношення сумісності за істинністю,

відношення сумісності за хибністю і

відношення логічного слідування.

Дефініція І: «Формули Γ сумісні за істинністю, якщо

і тільки якщо існує модель і приписування значень предметним змінним, при яких кожна формула із Γ

приймає значення «істина». У протилежному випадку ці формули несумісні за істинністю».

Дефініція П: «Формули Γ сумісні за хибністю, якщо і

тільки якщо існує модель і приписування змінним, при яких кожна формула із Γ приймає значення «хиба». У

протилежному випадку ці формули несумісні за хибні- стю».

Проілюструємо наведені дефініції на прикладі.

Візьмемо формули:

х R(x,y) i x R(x,y)

іпокажемо, що вони сумісні за істинністю.

Для цього достатньо вибрати конкретну модель <U,I> і конкретне приписування ϕ , при яких обидві формули разом будуть істинні.

За універсум розгляду приймемо множину міст U. Не- хай І співставляє двомісній предикаторній константі R множину таких пар міст, перше із яких південніше друго- го Функція ϕ приписує вільній предметній змінній у місто Київ, а решті змінним – довільні міста.

Розглянемо тепер приписування ϕ , яке у також співставляє Київ, а х Одесу. Оскільки Одеса південніше Києва, то пара < Одеса, Київ> міститься в I(R) і означає | R(x,y) | = i при ϕ .

А звідси випливає, що | х R(x,y) | = i при ϕ . Розглянемо тепер приписування ϕ , яке знову співстав-

ляє у – Київ, a х – Львів. Оскільки Львів розташований не південніше Києва, то пара <Львів, Київ > не міститься в

І(R) i | R(x,y) | = x при ϕ .

Тоді, | R(x,y) | = i при ϕ . Звідси випливає | x R(x,y) | = = i при ϕ .

Отже, формули х R(x,y) i x R(x,y) y моделі <U,I> і при приписуванні ϕ одночасно приймають значення «іс-

тинa», що свідчить про їх сумісність за істинністю.

Візьмемо ту саму модель <U,I> і приписування ϕ . По- кажемо, що формули х R(x,y) i x R(x,y) сумісні за хи-

бністю.

Упопередньому прикладі ми встановили, що | R(x,y) | =

iпри ϕ . Звідси випливає, що | R(x,y) | = x при ϕ .

Тоді x R(x,y) = x при ϕ . Також було встановлено, що | R(x,y) | = x при ϕ . А це означає, що х R|x,y| = x при ϕ .

Виходить, що в даній моделі при даному приписуванні формули

х R(x,y) i x R(x,y) сумісні за хибністю.

За допомогою досить простих міркувань можна показа- ти, що формули:

а) х R(x,y) i x R(x,y) є несумісними за істинністю,

а

б) x R(x,y) i x R(x,y) є несумісними за хибністю.

1.Щоб показати несумісність за істинністю формул

x R(x,y) i x R(x,y),

зробимо припущення про їх сумісність за істинністю. Тоді,

| R(x,y) | = i i | R(x,y) | = i.

Але визнання істинності формули | R(x,y) | змушує вкзати на хибність формули | R(x,y) |. Отже, ми маємо про- тиріччя.

2.Для встановлення несумісності за хибністю формул

х R(x,y) i x R(x,y)

зробимо припущення, що вони сумісні за хибністю при де- якій моделі <U,I> і при приписуванні ϕ .

Якщо це так, то | R(x,y) | = x i | R(x,y) | = x.

Але визнання хибності формули | R(x,y) | приму- шує визнати істинність формули | R(x,y) |. Маємо проти- річчя.

Отже, вихідні формули за хибністю несумісні. Виходить, що формули х R(x,y) i x R(x,y) знахо-

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

R(x,y) i x R(x,y) перебувають у відношенні підпроти-

лежності, оскільки вони сумісні за істинністю і несумісні за хибністю.

Дефініція Ш. Із множини формул Γ логічно слідує формула В (Γ |= В), якщо і тільки якщо не існує моделі і

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

мули В – значення «хиба».

Проілюструємо наведену дефініцію на прикладі.

Покажемо, що із Р(а) і Q(a) логічно слідує x (P(x)

Q(x)).

P(a), Q(a) |= x (P(x) Q(x)).

Припустимо, що Р(а) і Q(a) не слідує із x (P(x) Q(x)): P(a), Q(a) |= x (P(x) Q(x)).

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

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

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

А1, А2, ..., Аn і В.

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

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

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

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

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

Наприклад, для обгрунтування тези «|=А», показують, що припущення хибності А з необхідністю приводить до протиріччя. Для обгрунтування тези «А1, А2,..., Аn |= В»

показують, що припущення істинності А1, А2,..., Аn і хи- бності В приводить до протиріччя.

Введемо деякі пояснення щодо побудови самої аналі-

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

Кожен крок в аналітичній таблиці відображає за-

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

дії відповідних аналітичних правил;кроки позначають римськими цифрами (І, П, Ш

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

нумерація рядків аналітичної таблиці починаєть-

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

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

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

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

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

(«істина») і F («хиба»).

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

Якщо в гілці є формула С із обома індексами Т і F, то

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

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

Аn вважається обгрунтованою.

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

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

T T A(x), TA(a)

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

У відповідності з логічним смислом квантора загально-

сті формула х А(х) істинна якщо і тільки якщо будь-

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

F F A(x), FA(в)

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

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

який не задовольняє умову А(х):

T T xA(x) .

TA(в)

Відповідно до смислу квантора істинність х А(х)

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

F F xA(x) . FA(a)

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

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

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

Дефініція: Формула А загальнозначима |= А, якщо і

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

Дефініція: «Із формули А1, А2,..., Аn логічно слідує фор-

мула В, якщо і тільки якщо існує замкнена аналітична

таблиця, нульовий рядок якої представлений виразом А1, А2,..., Аn |= В.

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

1.Із множини аналітичних правил насамперед засто-

совують пропозиційні аналітичні правила, а потім – кванторні правила Т , F , T , F .

2.Із кванторних правил спочатку застосовують правила F i T , які вимагають введення нових пред- метних констант, а потім – правила Т і F , які не

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

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

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

1 Як і у логіці висловлювань у таких випадках засновки об’єднують через « » і до них через « » приєднують висновок.