Материал: discrete_mathematics

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

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

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

Наприклад, формула P1(x) (← P3(x, z) → P2(y, x, z)) задає деякий предикат Q(x, y, z). Значення предиката Q неважко обчис-

лити для будь-якого набору значень його змінних x, y, z, виходячи зі значень предикатів P1, P2, P3 на цьому наборі.

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

Найпопулярнішими й найуживанішими виразами в математиці є фрази або формулювання типу для всіх та існує. Вони входять до більшості математичних міркувань і доведень, висновків, лем і теорем. Наприклад: Для всіх дійсних чисел x вико-

нується рівність sіn2x + cos2x = 1; Для заданих натуральних a та b завжди існує натуральне число d, яке ділить числа a та b; Для всіх натуральних n справедливе твердження: якщо n ділиться на 6 і на 15, то n ділиться на 30 тощо.

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

Нехай P(x) – предикат на множині M. Тоді квантор загаль ності (із параметром x) – це операція, що ставить у відповідність P(x) висловлення для всіх x із M P(x) істинне; для позначення цієї операції використовують знак , записують xP(x) (чита-

ють для всіх x P від x).

Іншу операцію називають квантором існування та позначають її знаком . Якщо Q(x) – деякий предикат на множині M, то висловлення існує в множині M елемент x такий, що Q(x) іс-

тинне записують у вигляді xQ(x) і читають існує такий x, що Q

від x або є такий x, що Q від x.

Походження обраних позначень пояснюється тим, що символ– це перевернута велика перша літера німецького слова alle або англійського слова all, що перекладають як усі. А символ відповідає першій літері слів exіstіeren (нім.) або exіst (англ.)

– існувати.

61