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

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

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

Інтерпретацією формули логіки предикатів називається:

1) визначення значень усіх її нелогічних термінів;

2) з’ясування значень її істинності в даному універсумі.

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

Розширенням (або значенням)

- предметної константи в універсумі U називається той предмет, чиїм власним ім’ям вона виступає;

, - предметної змінної (вільної та зв’язаної) в універсумі U називається довільний предмет U;

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

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

Тоді можна побудувати наступну таблицю істинності для формул

Неважко помітити, що значенняспівпадають зі значен­нямиа значення- зі значеннями

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

Формула логіки предикатів отримує інтерпретацію, якщо:

1) заданий універсум інтерпретації U;

2) визначено розширення кожного її нелогічного символу в IJ;

3) формуліголовний знак якої - квантор спільності,

приписано значення «істина», якщо формулаістинна при підстановці на місце змінної х будь-якого предмета з універсуму U; і приписано значення«хиба» - у протилежному випадку;

4) формуліголовний знак якої - квантор існування,

приписано значення «істина», якщо формулаістинна при підстановці на місце змінної х по крайній мірі одного предмета із універсуму U; і приписано значення «хиба» - у протилежному випадку;

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

Формула логіки предикатів може бути істинною по крайній мірі в одній інтерпретації, істинною у всіх інтерпретаціях або хибною у всіх інтерпретаціях.

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

Формула логіки предикатів

- виконувана, якщо і тільки якщо вона істинна хоча б в одній інтерпретації;

- логічно істинна, якщо і тільки якщо вона істинна у всіх інтерпретаціях;

- логічно хибна або невиконувана, якщо і тільки якщо вона хибна у всіх інтерпретаціях.

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

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

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

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

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

Список формул вважається замкненим, якщо він містить формулу та її заперечення. Аналітична таблиця вважається замкненою, якщо кожний список формул в останньому рядку замкнений. Замкнені списки позначаються символами N, N_p N₂ і т.д.

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

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

Усі правила редукції поділяють на:

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

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

Розглянемо правила редукції, виходячи із наведного поділу.

Правила побудови дерев у логіці висловлювань

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

Правило записується у вигляді двох рядків, розділених горизонтальною рискою: у верхньому рядку пишуться вихідні формулиу нижній рядок переносяться формули W, а замість

ставляться формули А, В:

де W - формули решти частини ряду, вони можуть бути й відсутніми.

Приклад:

1

Правила дерев у логіці предикатів

Кожна формула логіки предикатів може бути представлена у вигляді дерева, яке відображає її логічну структуру.

Перевірка формули А на загальнозначимість за допомогою методу аналітичних таблиць полягає в наступному. Будується аналітична таблиця, в якій в якості першого рядка записується формула-А. Якщо вдасться побудувати замкнену таблицю, це означає, що формула -A містить в собі протиріччя, тому хибна. Звідси випливає, що вихідна формула А істинна незалежно від значень своїх предметних змінних, тобто загальнозначима, що й потрібно було довести. Якщо таблицю не вдається замкнути, тоді загальнозначимість формули А не доведена. Як бачимо, при побудові аналітичної таблиці застосовується хід думки, який відповідає способу міркування від протилежного: теза визнається істинною, якщо доведено, що протилежна їй антитеза - хибна.

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

107

Останній рядок незамкнений, у той же час до цих формул не можна застосувати правила редукції. Тому таблиця не може бути замкнена. Логічне випливання формулуі із формули| не доведено.

2.3.4.