Материал: discrete_mathematics

3) застосування побудованого уніфікатора до висновків секвенційного правила, що дає висновок для об'єктної секвенції.

Наприклад, маємо об'єктну секвенцію

1 A → (B → C), 0(A → B) → C.

Проаналізувавши її, застосуємо правило 0→ до другої формули секвенції. Правило запишемо у вигляді

Тепер побудуємо уніфікатор. У засновках правила прописано змінні (краще навіть називати їх метазмінними, оскільки їх значен-

нями будутьпропозиційнізмінні чиформули) A, B, Σ.

Тут A та B – пропозиційні метазмінні (оскільки вони будуть

замінюватися на пропозиційні формули), Σ – секвенційна метазмінна (оскільки замінюватиметься на секвенцію). Виокремлю-

ємо формулу

0 (A → B) → C,

яку перетворюватимемо. Другу формулу 1 A → (B → C) наразі

не перетворюватимемо. Тому секвенційній метазмінній Σ відповідатиме формула 1 A → (B → C) (записуємо у вигляді

а формулі 0 A → B із засновків правила відповідатиме формула

0 (A → B) → C

з об'єктної секвенції. В об'єктній формулі головною операцією є друга імплікація, тому при уніфікації метазмінній A з правила відповідає формула A → B (записуємо у вигляді A/ A → B), а

метазмінній В – формула С (записуємо у вигляді В/С). Це означає, про побудовано уніфікатор

Тепер застосовуємо отриманийуніфікатор до висновківправила

1 A, 0 B, ∑,

56

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

1 A → (B → C), 1 A → B, 0C.

Завдання для самостійної роботи

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

(є) ¬a b, ¬b ¬ c Ba → ¬ c; (ж) ¬ (a b) B ¬ a c; (з) a, c → ¬ (a b) B ¬c;

(и) (a → b) → c, a → (b → c) Bb → c; (і) a ¬ c, a → d, b → c, ¬ b → d B d;

(ї) a → (b c), d → a B (¬ b ¬ c) → ¬ d.

2. Визначити, чи є правильною наслідковість:

(ж) a b, a → c, b → c B¬ c → ¬ a.

3. Знайти логічні наслідки із засновків:

4. Знайти засновки, логічними наслідками яких є такі формули: (а) a → b; (б) a b; (в) a → b c; (г) a b→ a b.

57

1.7. Логіка предикатів. Квантори

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

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

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

що дістала назву числення предикатів.

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

Наприклад, в істинному висловленні 3 – просте число підмет 3 – це об'єкт, а присудок просте число виражає певну його властивість.

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

Наприклад, замінюючи в наведеному вище висловленні 3 на числа 1, 5, 9 або 12, матимемо відповідно такі висловлення: 1 –

просте число, 5 – просте число, 9 – просте число, 12 – просте число, з яких друге істинне, а решта – хибні висловлення.

Це дозволяє розглянути вираз x – просте число не як елемен-

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

58

мість параметра (змінної) x об'єктів (значень) із певної множини M дістаємо висловлення.

Аналогічно можна трактувати, наприклад, пропозиційні фор-

ми a – українець, b і c – однокурсники, c важче, ніж d або точка x лежить між точками y та z. До перших двох із них можна підставляти замість параметрів a, b і c прізвища конкретних людей, до третьої – замість c і d назви будь-яких об'єктів (предметів), що мають вагу. Для четвертої множиною M значень змінних x, y та z може бути множина точок певної прямої.

Перша із цих пропозиційних форм задає, як і в наведеній раніше формі, певну властивість для об'єкта a. Інші три форми описують деякі відношення між відповідними об'єктами.

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

n місним предикатом P(x1, x2, …, xn) на якійсь множині M

називають довільну функцію, яка впорядкованому набору елементів (a1, a2, …, an) множини M ставить у відповідність логічне значення 1 або 0.

Множину M називають предметною областю, або універсальною множиною, а x1, x2, …, xn – предметними змінними предиката P.

Множина наборів (a1, a2, …, an) таких, що P(a1, a2, …, an) = 1,

називається областю істинності (або характеристичною мно жиною) предиката P.

Якщо P(a1, a2, …, an) = 1, то згідно із логічною інтерпретацією казатимемо, що предикат P є істинним на (a1, a2, …, an). В іншому разі казатимемо, що предикат P є хибним.

Вираз P(x1, x2, …, xn), що перетворюється на висловлення після заміни всіх його змінних x1, x2, …, xn на елементи певної предметної області M, називають пропозиційною (висловлю вальною) формою.

Приклад 1.18. Нехай предметною областю є множина N натуральних чисел, тоді вирази x – просте число, x ділить y, x + y = z, x < 5 тощо є пропозиційними формами. ◄

Пропозиційна форма є одним зі способів задання предиката.

59

Для n = 1 предикат P(x) називається одномісним, або унар ним, для n = 2 P(x, y) – двомісним, або бінарним, для n = 3 P(x, y, z) – тримісним, або тернарним предикатом.

Якщо в n-арному предикаті P(x1, x2, …, xn) зафіксувати значення деяких m змінних (тобто надати їм певних значень із множини M), то отримаємо (n – m)-місний предикат на множині M. Тому можна вважати висловлення нульмісними предикатами, які утворено з багатомісних предикатів підстановкою замість усіх їх параметрів певних значень із предметної області. Отже, висловлення можна розглядати як окремий випадок предиката.

Як з елементарних висловлень за допомогою логічних операцій можна утворювати складені висловлення, так і, використовуючи прості (елементарні) предикати й логічні зв'язки (операції), можна будувати складені предикати, або предикатні

формули.

Зазвичай основні логічні операції , , ←, →, ~ означають для предикатів, що задані на тій самій предметній області M і залежать від тих самих змінних.

Нехай P(x1, x2, …, xn) і Q(x1, x2, …, xn) – n-місні предикати на множині M.

Кон'юнкцією P(x1, x2, …, xn) Q(x1, x2, …, xn) називають пре-

дикат R(x1, x2, …, xn), що набуває значення 1 на тих і тільки тих наборах значень змінних, на яких обидва предикати

P(x1, x2, …, xn) і Q(x1, x2, …, xn) дорівнюють 1. Зауважимо, що на інших наборах значень змінних предикат набуває значення 0.

Диз'юнкцією P(x1, x2, …, xn) Q(x1, x2, …, xn) називають пре-

дикат T(x1, x2, …, xn), що набуває значення 1 на тих і тільки тих наборах значень змінних, на яких принаймні один із предикатів P(x1, x2, …, xn) або Q(x1, x2, …, xn) дорівнює 1. Відповідно на інших наборах значень змінних предикат набуває значення 0.

Запереченням ←P(x1, x2, …, xn) предиката P(x1, x2, …, xn) на-

зивають предикат S(x1, x2, …, xn), що дорівнює 1 на тих і лише тих наборах значень термів, на яких предикат P(x1, x2, …, xn) дорівнює 0.

Аналогічно вводять також інші логічні операції: →, ~ тощо.

60