Лекція 6. Логіка предикатів #

Огляд #

У Лекції 5 ми вивчали логіку висловлень. Там найменшою неподільною одиницею був атом — ціле розповідне речення, якому приписують одне значення істинності: «Дніпро впадає в Чорне море» ($=1$), «Дніпро впадає в Азовське море» ($=0$). Висловлення поєднували зв’язками $\neg, \wedge, \vee, \to, \leftrightarrow$ й вивчали таблицями істинності. Ця мова напрочуд груба: вона бачить речення лише ззовні, як чорну скриньку зі значенням $0$ або $1$, і геть не бачить його внутрішньої будови.

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

• «$2$ ділиться на $2$»;
• «кожне парне число ділиться на $2$»;
• «існує парне просте число».

Перше — звичайне висловлення. Але щойно з’являються слова «кожне» та «існує», а всередині речень — змінні («число ділиться на $2$»), логіка висловлень безсила: вона мусила б позначити кожне таке речення окремою буквою $P$, $Q$, $R$ і забути про будь-який зв’язок між ними, хоча всі троє говорять про ту саму властивість «ділитися на $2$».

Логіка предикатів (її ще звуть логікою першого порядку) усуває цю ваду. Вона вводить два нові засоби:

1. Предикати — «речення зі змінними», значення істинності яких залежить від того, які об’єкти підставити замість змінних (§6.1–6.3);
2. Квантори $\forall$ («для всіх») та $\exists$ («існує») — засоби сказати «щось виконано для всіх об’єктів області» або «принаймні для одного» (§6.4).

Далі ми вивчимо закони алгебри предикатів (§6.5), навчимося зводити будь-яку формулу до стандартного вигляду — випередженої нормальної форми (§6.6) — і, нарешті, побачимо, як усе це працює в реальній мові програмування Prolog (§6.7), яка є прямою інженерною реалізацією логіки предикатів. Останнє готує ґрунт до Лабораторної роботи 2, де ви власноруч збудуєте базу знань про генеалогічне дерево.

Про строгість. Як і в попередніх лекціях, ключові закони оформлені як теореми й твердження та супроводжуються доведенням до позначки $\blacksquare$. Доведення в цій лекції — семантичні: рівносильність двох формул означає, що вони набувають однакового значення істинності за будь-якого вибору області $M$ та значень предикатів. Тому типова схема доведення тут — «обчислити умову істинності лівої частини й переконатися, що вона дослівно збігається з умовою істинності правої».

6.1 Від висловлень до предикатів #

Мотивація #

Речення «$x$ ділиться на $5$» саме по собі не є висловленням: воно ще не істинне й не хибне, бо невідомо, чим є $x$. Але щойно ми підставимо конкретне число, воно стає висловленням: «$10$ ділиться на $5$» істинне, «$7$ ділиться на $5$» хибне. Отже, речення зі змінною — це не одне висловлення, а ціла сім’я висловлень, занумерована значеннями змінної. Саме таку сім’ю й називають предикатом.

Означення предиката #

Означення (предикат). Нехай $M$ — деяка непорожня множина, яку називають областю визначення. Предикатом (одномісним) на $M$ називають правило $P$, що кожному елементу $x \in M$ ставить у відповідність рівно одне значення з області значень $\{0, 1\}$ (хиба / істина). Коротко:

$$P \colon M \to \{0, 1\}.$$

Запис $P(x)$ читають «предикат $P$ від $x$»; $P(a) = 1$ означає, що на елементі $a$ предикат істинний, а $P(a) = 0$ — що хибний.

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

• область визначення $M$ — множина, з якої беруть значення змінної (числа, студенти, кольори, символи шрифту — будь-що);
• область значень $\{0, 1\}$ — завжди та сама двоелементна множина істиннісних значень (у курсі також уживають позначення І / Х);
• правило зіставлення — механізм, який кожному $x \in M$ однозначно приписує $0$ або $1$.

Зауваження (предикат — це відображення). Означення дослівно збігається з означенням функції (відображення) з Лекції 1, у якої областю прибуття є двоелементна множина $\{0,1\}$. Тому предикат іноді називають характеристичною функцією: він «характеризує» ті елементи $M$, на яких істинний.

Область істинності #

Кожному предикатові природно відповідає множина тих елементів, де він істинний.

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

$$I_P = \{\, x \in M \mid P(x) = 1 \,\}.$$

Це рівно та сама конструкція «задання множини характеристичною властивістю» $\{x \in M \mid P(x)\}$, яку ми ввели в §1.2. Отже, предикати й підмножини — це два погляди на той самий об’єкт: підмножина $A \subseteq M$ задає предикат «належати $A$», а предикат $P$ задає підмножину $I_P$. Ця відповідність — місток між Лекцією 1 й цією лекцією, і ми ще ним скористаємося.

Приклад 6.1 (ПАРНЕ). На $M = \{1,2,3,4,5\}$ означимо предикат ПАРНЕ$(x) = 1$ саме тоді, коли $x$ парне. Тоді

$$\text{ПАРНЕ}(2) = \text{ПАРНЕ}(4) = 1, \qquad \text{ПАРНЕ}(1) = \text{ПАРНЕ}(3) = \text{ПАРНЕ}(5) = 0,$$

а область істинності — $I_{\text{ПАРНЕ}} = \{2, 4\}$ (див. рисунок вище).

Приклад 6.2 (ПРОСТЕ). На $M = \mathbb{N}$ означимо ПРОСТЕ$(x) = 1$ саме тоді, коли $x$ — просте число. Тоді ПРОСТЕ$(2) =$ ПРОСТЕ$(3) =$ ПРОСТЕ$(5) = 1$, а ПРОСТЕ$(1) =$ ПРОСТЕ$(4) = 0$. Область істинності — множина всіх простих чисел $\{2, 3, 5, 7, 11, \dots\}$; перелічити її неможливо, тож без задання предикатом тут не обійтися.

Зауваження (висловлення — окремий випадок). Якщо предикат не має жодної змінної, він постійний і збігається зі звичайним висловленням з Лекції 5. Тому логіка висловлень — це «логіка предикатів без змінних і без кванторів», а нинішня лекція — її повноцінне узагальнення.

6.2 Багатомісні предикати. Місність #

Властивості бувають не лише в одного об’єкта, а й відношення між кількома. «$x$ ділиться на $y$» стосується двох чисел; «точка $x$ лежить між $y$ і $z$» — трьох. Щоб це формалізувати, дозволимо предикатові кілька аргументів.

Означення ($n$-місний предикат). Нехай $M_1, M_2, \dots, M_n$ — області визначення (найчастіше всі однакові, $M_1 = \dots = M_n = M$). $n$-місним предикатом називають правило

$$P \colon M_1 \times M_2 \times \dots \times M_n \to \{0, 1\},$$

яке кожному впорядкованому набору $(x_1, x_2, \dots, x_n)$ ставить у відповідність одне значення з $\{0, 1\}$. Число аргументів $n$ називають місністю (або порядком, арністю) предиката.

Отже, за місністю предикати класифікують так:

Приклад 6.3 (ДІЛИТЬСЯ). Двомісний предикат ДІЛИТЬСЯ$(x, y)$ на $M = \mathbb{N}$ істинний саме тоді, коли $x$ ділиться на $y$ націло. Тоді ДІЛИТЬСЯ$(10, 5) = 1$, ДІЛИТЬСЯ$(9, 5) = 0$, ДІЛИТЬСЯ$(7, 7) = 1$. Порядок аргументів суттєвий: ДІЛИТЬСЯ$(10, 5) = 1$, але ДІЛИТЬСЯ$(5, 10) = 0$.

Предикат — це відношення #

Область істинності двомісного предиката вже не підмножина $M$, а підмножина $M \times M$, тобто бінарне відношення у сенсі Лекції 2:

$$I_P = \{\, (x, y) \in M \times M \mid P(x, y) = 1 \,\} \subseteq M \times M.$$

Тому «двомісний предикат» і «бінарне відношення» — це синоніми, лише під різними кутами зору: предикат наголошує на правилі (істинно / хибно), відношення — на множині пар. Усе, що ми знаємо про відношення (рефлексивність, симетричність, транзитивність, зображення орієнтованим графом), негайно переноситься на предикати.

Приклад 6.4 (БАТЬКО як відношення). Нехай $M = \{$Іван, Петро, Олена, Микола, Софія$\}$, а двомісний предикат БАТЬКО$(x, y)$ істинний, коли $x$ — батько $y$. Область істинності — множина пар

$$\{(\text{Іван}, \text{Петро}),\ (\text{Іван}, \text{Олена}),\ (\text{Петро}, \text{Микола}),\ (\text{Петро}, \text{Софія})\},$$

яку зручно зобразити орієнтованим графом: вершини — елементи $M$, стрілка веде від батька до дитини.

Саме цей предикат ми оживимо на Пролозі в §6.7, а розширимо — у Лабораторній роботі 2.

6.3 Функціональні символи і терми #

Функціональні символи #

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

Означення (функціональний символ). $n$-місним функціональним символом називають правило

$$f \colon M^n \to M,$$

що набору об’єктів ставить у відповідність знову об’єкт області $M$ (а не значення істинності!).

Це головна відмінність:

$$\underbrace{P \colon M^n \to \{0,1\}}_{\text{предикат: об'єкти} \to \text{істинність}} \qquad\text{проти}\qquad \underbrace{f \colon M^n \to M}_{\text{функція: об'єкти} \to \text{об'єкт}}.$$

Приклад 6.5 (арифметичні функціональні символи). На $M = \mathbb{Z}$: двомісний символ мінус$(x, y)$ повертає число $x - y$; одномісний символ плюс$(x, 1)$ повертає наступне число $x + 1$. Так, мінус$(7, 5) = 2$, плюс$(7, 1) = 8$ — результат щоразу є числом, а не істинністю.

Приклад 6.6 (нечисловий функціональний символ). На множині вчителів школи символ вчитель$(x)$ може повертати вчителя, який викладає предмет $x$: вчитель(математика) $=$ (конкретна людина). Знову ж таки, результат — об’єкт області, а не $0$/$1$.

Терми #

Комбінуючи змінні, сталі й функціональні символи, дістаємо терми — синтаксичні вирази, що позначають об’єкти. Означення рекурсивне — точно в дусі §1.2.

Означення (терм). Множину термів будують за трьома правилами: база — кожна змінна ($x, y, z, \dots$) і кожна стала ($a, b, 0, 1, \dots$) є термом; індуктивне правило — якщо $t_1, \dots, t_n$ — терми, а $f$ — $n$-місний функціональний символ, то $f(t_1, \dots, t_n)$ теж терм; замикання — інших термів немає.

Терми можна вкладати один в одний: мінус(плюс$(x, 1)$, $y$) — цілком коректний терм, що позначає об’єкт $(x + 1) - y$.

Означення (атомарна формула). Якщо $P$ — $n$-місний предикат, а $t_1, \dots, t_n$ — терми, то $P(t_1, \dots, t_n)$ називають атомарною формулою. Це найпростіша формула логіки предикатів; її значення — знову $0$ або $1$.

Різниця «терм проти атомарної формули» — це знову різниця «об’єкт проти істинності». Наочно її показує дерево розбору: у корені стоїть предикат (він «дивиться назовні» на $\{0,1\}$), а нижче — терми-аргументи (вони «залишаються» в $M$).

Формалізація прикладів #

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

Приклад 6.7 (студенти складають сесію). Речення «студенти складають сесію» формалізують двомісним предикатом

$$\text{СКЛАДАТИ}(\text{студенти}, \text{сесія}).$$

Тут «студенти» й «сесія» — сталі (конкретні об’єкти), а СКЛАДАТИ — предикат «$x$ складає $y$».

Приклад 6.8 (число, більше за $x$). Речення «$x + 1$ більше за $x$» містить і функціональний символ, і предикат. Спершу терм плюс($x$, 1) будує об’єкт $x + 1$; потім предикат БІЛЬШЕ порівнює його з $x$:

$$\text{БІЛЬШЕ}(\text{плюс}(x, 1),\ x).$$

Саме цю формулу зображено на дереві розбору вище: корінь — предикат БІЛЬШЕ, його лівий аргумент — терм плюс($x$, 1), правий — змінна $x$.

Типова помилка (плутати предикат із функцією). Записавши «плюс$(x, 1)$» там, де потрібне твердження, студент отримує не $0$/$1$, а число — таку формулу не можна заперечувати чи сполучати зв’язками. Пам’ятайте: сполучати $\neg, \wedge, \vee$ можна лише формули (те, що набуває значення $0$/$1$), а не терми (те, що позначає об’єкт). «плюс$(x, 1) \wedge x$» — синтаксична нісенітниця.

6.4 Квантори: загальності та існування #

Атомарні формули й зв’язки з Лекції 5 — це ще не вся сила логіки предикатів. Її серце — квантори, що дають змогу висловлюватися про всі або про деякі елементи області одразу.

Квантор загальності #

Означення (квантор загальності $\forall$). Нехай предикат $P(x)$ визначений на області $M$. Формула $\forall x\, P(x)$ (читають «для всіх $x$ виконано $P(x)$») істинна саме тоді, коли $P(a) = 1$ для кожного елемента $a \in M$:

$$\forall x\, P(x) = 1 \iff P(a) = 1 \ \text{для всіх}\ a \in M.$$

Відповідно $\forall x\, P(x) = 0$ саме тоді, коли існує хоча б один $a \in M$ з $P(a) = 0$; такий елемент називають контрприкладом.

Квантор існування #

Означення (квантор існування $\exists$). За тих самих умов формула $\exists x\, P(x)$ (читають «існує $x$, для якого $P(x)$») істинна саме тоді, коли $P(a) = 1$ принаймні для одного $a \in M$:

$$\exists x\, P(x) = 1 \iff P(a) = 1 \ \text{для деякого}\ a \in M.$$

Такий елемент $a$ називають свідком. Відповідно $\exists x\, P(x) = 0$ саме тоді, коли $P(a) = 0$ для всіх $a \in M$.

Квантори як узагальнені кон’юнкція та диз’юнкція #

Коли область скінченна, $M = \{a_1, a_2, \dots, a_k\}$, квантори перетворюються на вже знайомі зв’язки:

$$\forall x\, P(x) \equiv P(a_1) \wedge P(a_2) \wedge \dots \wedge P(a_k),$$

$$\exists x\, P(x) \equiv P(a_1) \vee P(a_2) \vee \dots \vee P(a_k).$$

Отже, $\forall$ — це «велика кон’юнкція» (істинна, лише коли істинні всі доданки), а $\exists$ — «велика диз’юнкція» (істинна, коли істинний хоч один). Ця точка зору особливо корисна: багато законів §6.5 — це просто закони алгебри висловлень, узяті по всій області.

Зауваження (порожня область). На порожній області $\forall x\, P(x)$ істинна (порожня кон’юнкція $= 1$: заперечити нічим), а $\exists x\, P(x)$ хибна (порожня диз’юнкція $= 0$: свідка немає). Це той самий «порожньо-істинний» ефект, що дав $\varnothing \subseteq A$ у Твердженні 1.10.

Як читати квантори #

Українська мова багата на звороти, що ховають квантори. Корисно тримати перед очима такий словничок:

Приклад 6.9 (формалізація загальних тверджень). На $M = \mathbb{N}$:

• «Кожне число ділиться на $1$» $\rightsquigarrow \forall x\, \text{ДІЛИТЬСЯ}(x, 1)$ — істинно.
• «Існує парне просте число» $\rightsquigarrow \exists x\, \big(\text{ПАРНЕ}(x) \wedge \text{ПРОСТЕ}(x)\big)$ — істинно (свідок $x = 2$).
• «Кожне просте число непарне» $\rightsquigarrow \forall x\, \big(\text{ПРОСТЕ}(x) \to \neg\,\text{ПАРНЕ}(x)\big)$ — хибно (контрприклад $x = 2$).

Зауваження (типовий зв’язок квантора зі зв’язкою). Зверніть увагу на приклад: «кожен, хто…, той…» майже завжди перекладають як $\forall x\,(A(x) \to B(x))$ (з імплікацією), а «існує, хто… і…» — як $\exists x\,(A(x) \wedge B(x))$ (з кон’юнкцією). Поставити навпаки (наприклад $\forall x\,(A(x)\wedge B(x))$ для «кожен $A$ є $B$») — поширена й груба помилка: така формула стверджувала б, що всі об’єкти області є одночасно $A$ і $B$.

Вільні та зв’язані змінності. Область дії #

Означення (зв’язана й вільна змінна). Входження змінної $x$ у формулу називають зв’язаним, якщо воно потрапляє в область дії квантора $\forall x$ або $\exists x$ (тобто у ту підформулу, до якої квантор застосовано), і вільним інакше. Формулу без вільних змінних називають замкненою (реченням): вона вже має конкретне значення істинності.

Наприклад, у формулі $\big(\exists x\, P(x, y)\big) \wedge Q(x)$ перше входження $x$ зв’язане квантором $\exists x$, а $x$ у $Q(x)$ — вільне (воно поза областю дії квантора); змінна $y$ теж вільна. Ім’я зв’язаної змінної несуттєве — це лише «робочий» позначник, як індекс підсумовування; ім’я вільної змінної суттєве, бо від неї залежить значення формули.

Порядок кванторів має значення #

Коли предикат багатомісний, поряд стоять кілька кванторів, і їхній порядок годі переставляти безкарно.

Твердження 6.10 (нерівноправність $\forall\exists$ та $\exists\forall$). Для будь-якого двомісного предиката $P$ справджується імплікація

$$\exists y\, \forall x\, P(x, y) \ \Rightarrow\ \forall x\, \exists y\, P(x, y),$$

але обернена, взагалі кажучи, хибна.

Доведення (пряма частина). Нехай $\exists y\, \forall x\, P(x, y) = 1$. Тоді існує конкретний свідок $b \in M$ такий, що $\forall x\, P(x, b) = 1$, тобто $P(a, b) = 1$ для всіх $a$. Візьмемо тепер довільний $a \in M$: для нього той самий $b$ є свідком того, що $\exists y\, P(a, y) = 1$. Оскільки $a$ довільний, маємо $\forall x\, \exists y\, P(x, y) = 1$. $\blacksquare$

Приклад 6.11 (обернене хибне). Візьмемо $M = \mathbb{N}$ і $P(x, y) = \text{БІЛЬШЕ}(y, x)$, тобто «$y > x$». Тоді:

• $\forall x\, \exists y\, (y > x)$ — істинно: для кожного $x$ знайдеться більше число (наприклад $y = x + 1$);
• $\exists y\, \forall x\, (y > x)$ — хибно: не існує числа $y$, більшого за всі натуральні одразу.

Отже, «для кожного свій $y$» (порядок $\forall\exists$) — це зовсім не те саме, що «один спільний $y$ на всіх» (порядок $\exists\forall$). Плутанина цих двох тверджень — джерело безлічі помилок у математиці та в специфікаціях програм.

6.5 Закони алгебри предикатів #

Формули логіки предикатів, як і формули логіки висловлень, підпорядковані алгебраїчним законам. Дві формули називають рівносильними ($\equiv$), якщо вони набувають однакового значення істинності за будь-якого вибору області $M$ та значень предикатів. Нижче — основні закони, що керують кванторами.

Перейменування зв’язаної змінної #

Закон (перейменування, $\alpha$-перетворення). Якщо змінна $y$ не входить у формулу $P$, то

$$\forall x\, P(x) \equiv \forall y\, P(y), \qquad \exists x\, P(x) \equiv \exists y\, P(y).$$

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

Перестановка однойменних кванторів #

Закон (комутативність однойменних кванторів).

$$\forall x\, \forall y\, P(x, y) \equiv \forall y\, \forall x\, P(x, y), \qquad \exists x\, \exists y\, P(x, y) \equiv \exists y\, \exists x\, P(x, y).$$

Два поспіль однакові квантори переставні. Але різнойменні — ні: як показано у Прикладі 6.11, $\forall x\, \exists y$ не рівносильне $\exists y\, \forall x$.

Дистрибутивні закони #

Твердження 6.12 (дистрибутивність $\forall$ щодо $\wedge$).

$$\forall x\, \big(P(x) \wedge Q(x)\big) \equiv \forall x\, P(x) \wedge \forall x\, Q(x).$$

Доведення. Обчислимо ліву частину. $\forall x\,(P(x) \wedge Q(x)) = 1$ саме тоді, коли для кожного $a \in M$ виконано $P(a) \wedge Q(a) = 1$, тобто одночасно $P(a) = 1$ і $Q(a) = 1$. Це рівносильно тому, що (для кожного $a$: $P(a) = 1$) і (для кожного $a$: $Q(a) = 1$) — адже вимога «для всіх $a$ обидві властивості» рівносильна двом окремим вимогам «для всіх $a$ перша» та «для всіх $a$ друга». А це в точності $\forall x\, P(x) = 1$ і $\forall x\, Q(x) = 1$, тобто права частина істинна. Обидві частини істинні за однакової умови, отже рівносильні. $\blacksquare$

Двоїсто (за симетрією $\wedge \leftrightarrow \vee$, $\forall \leftrightarrow \exists$) справджується:

Твердження 6.13 (дистрибутивність $\exists$ щодо $\vee$).

$$\exists x\, \big(P(x) \vee Q(x)\big) \equiv \exists x\, P(x) \vee \exists x\, Q(x).$$

А от «перехресні» варіанти рівносильностями не є — лише односторонні імплікації:

Типова помилка (квантор не проходить крізь «чужу» зв’язку).

$$\forall x\,\big(P(x) \vee Q(x)\big) \ \not\equiv\ \forall x\, P(x) \vee \forall x\, Q(x), \qquad \exists x\,\big(P(x) \wedge Q(x)\big) \ \not\equiv\ \exists x\, P(x) \wedge \exists x\, Q(x).$$

Контрприклад до першого. Нехай $M$ — усі люди, $P(x) =$ ЧОЛОВІК$(x)$, $Q(x) =$ ЖІНКА$(x)$. Ліворуч: $\forall x\,(\text{ЧОЛОВІК}(x) \vee \text{ЖІНКА}(x))$ — істинно (кожен є чоловіком або жінкою). Праворуч: $\forall x\,\text{ЧОЛОВІК}(x) \vee \forall x\,\text{ЖІНКА}(x)$ — хибно (не всі чоловіки; не всі жінки). Справджується лише слабша імплікація $\forall x P(x) \vee \forall x Q(x) \Rightarrow \forall x(P(x) \vee Q(x))$.

Закони де Моргана для кванторів #

Це, безперечно, найважливіші закони цієї лекції: вони показують, як заперечення проходить крізь квантор.

Теорема 6.14 (закони де Моргана для кванторів). Для будь-якого предиката $P$ на області $M$:

$$\neg\, \forall x\, P(x) \equiv \exists x\, \neg P(x), \qquad \neg\, \exists x\, P(x) \equiv \forall x\, \neg P(x).$$

Доведення (першої рівносильності). Обчислимо ліву частину. За означенням квантора загальності, $\forall x\, P(x) = 1$ саме тоді, коли $P(a) = 1$ для всіх $a \in M$. Отже, $\neg\,\forall x\, P(x) = 1$ саме тоді, коли це не так — тобто коли існує принаймні один $a \in M$, для якого $P(a) = 0$, рівносильно $\neg P(a) = 1$. Але «існує $a \in M$ з $\neg P(a) = 1$» — це дослівно умова істинності правої частини $\exists x\, \neg P(x)$. Обидві частини істинні за однакової умови, тож рівносильні. Другу рівносильність дістають, застосувавши першу до предиката $\neg P$ і скориставшись подвійним запереченням. $\blacksquare$

Зауваження (це справді де Морган). На скінченній області закон миттєво випливає зі «звичайного» де Моргана з Лекції 5:

$$\neg\,\forall x\, P(x) \equiv \neg\big(P(a_1) \wedge \dots \wedge P(a_k)\big) \equiv \neg P(a_1) \vee \dots \vee \neg P(a_k) \equiv \exists x\, \neg P(x).$$

Заперечення «великої кон’юнкції» — це «велика диз’юнкція» заперечень; квантор загальності обертається на квантор існування.

Приклад 6.15. Заперечимо твердження «кожне натуральне число парне»:

$$\neg\, \forall x\, \text{ПАРНЕ}(x) \equiv \exists x\, \neg\,\text{ПАРНЕ}(x),$$

тобто «існує непарне число» — і саме це, звісно, істинно.

Винесення сталого множника #

Якщо квантор зв’язує змінну, якої в підформулі $Q$ немає, то $Q$ можна винести за квантор — це знадобиться при побудові префікса.

Закон (винесення підформули без змінної). Якщо $x$ не входить у $Q$, то

$$\forall x\, \big(P(x) \wedge Q\big) \equiv \forall x\, P(x) \wedge Q, \qquad \exists x\, \big(P(x) \vee Q\big) \equiv \exists x\, P(x) \vee Q,$$

і аналогічно для інших зв’язок.

Зведена таблиця законів #

6.6 Випереджена (пренексна) нормальна форма #

Як у булевій алгебрі будь-яку функцію зводять до ДДНФ чи ДКНФ, так у логіці предикатів будь-яку формулу зводять до єдиного стандартного вигляду, де всі квантори винесено вперед.

Означення (випереджена нормальна форма, ВНФ). Формула перебуває у випередженій (пренексній) нормальній формі, якщо має вигляд

$$(Q_1 x_1)(Q_2 x_2)\dots(Q_n x_n)\, \underbrace{M}_{\text{матриця}},$$

де кожен $Q_i$ — квантор ($\forall$ або $\exists$), а матриця $M$ — безкванторна формула (містить лише предикати, сталі, терми, зв’язки $\neg, \wedge, \vee$). Частину $(Q_1 x_1)\dots(Q_n x_n)$ називають префіксом.

Алгоритм побудови ВНФ #

Будь-яку формулу можна звести до ВНФ (рівносильної їй) за чотири кроки — точно за схемою зі слайдів курсу.

Крок 1. Усунути $\leftrightarrow$ та $\to$. Замінюємо їх на $\neg, \vee, \wedge$ за тотожностями

$$F \to G \ \equiv\ \neg F \vee G, \qquad F \leftrightarrow G \ \equiv\ (F \wedge G) \vee (\neg F \wedge \neg G).$$

Крок 2. Занести заперечення до предикатів. Проштовхуємо кожне $\neg$ усередину, застосовуючи закони де Моргана — і для зв’язок (Лекція 5), і для кванторів (Теорема 6.14) — та закон подвійного заперечення $\neg\neg F \equiv F$:

$$\neg(F \wedge G) \equiv \neg F \vee \neg G, \quad \neg(F \vee G) \equiv \neg F \wedge \neg G, \quad \neg\forall x\, F \equiv \exists x\, \neg F, \quad \neg\exists x\, F \equiv \forall x\, \neg F.$$

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

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

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

Зауваження (виправлення до слайда). На слайді курсу елімінацію еквівалентності записано як $F \leftrightarrow G = \neg F \wedge G \vee F \wedge \neg G$; це насправді формула для виключного «або» $F \oplus G \equiv \neg(F \leftrightarrow G)$, а не для самої еквівалентності. Правильна тотожність — $F \leftrightarrow G \equiv (F \wedge G) \vee (\neg F \wedge \neg G)$ (обидві частини істинні саме тоді, коли $F$ і $G$ мають однакове значення). Її й використовуйте.

Повний приклад #

Приклад 6.16. Звести до ВНФ формулу

$$\varphi \ =\ \forall x\, P(x) \ \to\ \forall x\, Q(x).$$

Зауважте: обидва квантори зв’язують одну й ту саму літеру $x$ — це навмисне, щоб показати необхідність кроку 3.

Крок 1 (усунути $\to$). За тотожністю $F \to G \equiv \neg F \vee G$:

$$\varphi \ \equiv\ \neg\, \forall x\, P(x) \ \vee\ \forall x\, Q(x).$$

Крок 2 (занести $\neg$). Застосовуємо де Морган для квантора до першого доданка, $\neg\,\forall x\, P(x) \equiv \exists x\, \neg P(x)$:

$$\equiv\ \exists x\, \neg P(x) \ \vee\ \forall x\, Q(x).$$

Крок 3 (перейменувати). Тепер обидва квантори зв’язують $x$, а це завадить винести їх коректно. Перейменуємо зв’язану змінну другого квантора з $x$ на $z$ (літери $z$ у формулі досі не було):

$$\equiv\ \exists x\, \neg P(x) \ \vee\ \forall z\, Q(z).$$

Крок 4 (винести квантори). Оскільки в $\neg P(x)$ немає $z$, а у $Q(z)$ немає $x$, обидва квантори виносяться у префікс (порядок зберігаємо):

$$\varphi \ \equiv\ \exists x\, \forall z\, \big(\neg P(x) \vee Q(z)\big).$$

Це вже ВНФ: префікс $\exists x\, \forall z$, матриця $\neg P(x) \vee Q(z)$.

Приклад 6.17 (з глибшим зануренням заперечення). Звести до ВНФ $\psi = \neg\,\forall x\,\big(P(x) \to \exists y\, R(x, y)\big)$.

• Крок 1: усунемо внутрішню імплікацію, $\psi \equiv \neg\,\forall x\,\big(\neg P(x) \vee \exists y\, R(x, y)\big)$.
• Крок 2: проштовхуємо $\neg$ послідовно — $\equiv \exists x\, \neg\big(\neg P(x) \vee \exists y\, R(x, y)\big)$ (де Морган для $\forall$) $\equiv \exists x\, \big(\neg\neg P(x) \wedge \neg \exists y\, R(x, y)\big)$ (де Морган для $\vee$) $\equiv \exists x\, \big(P(x) \wedge \forall y\, \neg R(x, y)\big)$ (подвійне заперечення та де Морган для $\exists$).
• Крок 3: змінні $x, y$ вже різні — перейменування не потрібне.
• Крок 4: виносимо квантори у префікс:

  $$\psi \ \equiv\ \exists x\, \forall y\, \big(P(x) \wedge \neg R(x, y)\big).$$

Зауваження (навіщо потрібна ВНФ). Єдиний стандартний вигляд дає змогу порівнювати й автоматично опрацьовувати формули. Саме з ВНФ починаються алгоритми автоматичного доведення теорем: після винесення кванторів квантори існування усувають (сколемізація), а з матрицею вже працює резолюція — той самий механізм, що лежить в основі мови Prolog з наступного параграфа.

6.7 Пролог — логіка предикатів у дії #

Prolog (від PROgrammation en LOGique) — мова програмування, у якій програма є просто набором тверджень логіки предикатів, а виконання — це логічне виведення. Це найпрямша практична реалізація всього, що ми вивчили. Програма на Пролозі складається з трьох видів речень: фактів, правил і питань.

Домовленість про запис (важливо!). У логіці предикати заведено писати з великої літери, а змінні — з малої: ВИКЛАДАЄ$(x, y)$. У Пролозі — навпаки: імена предикатів і сталих пишуть із малої літери (teaches, odm), а змінні — з великої (L, C). Далі назви подаємо латиницею (samantsov, vpvps23, odm, …) — так код гарантовано виконається в будь-якому інтерпретаторі; самі назви суто ілюстративні.

Факти #

Факт — це атомарна формула, оголошена істинною (аналог області істинності предиката, заданої переліком). Кожен факт закінчують крапкою.

% --- Студенти та їхні групи: student(Студент, Група) ---
student(skovoroda, vpvps23).   student(zabuzhka, vpvps23).
student(kidruk,    vpvps23).   student(franko,   pzpi23).

% --- Які предмети вивчає група: studies(Група, Предмет) ---
studies(vpvps23, odm).   studies(vpvps23, inf).   studies(pzpi23, kdm).

% --- Хто який предмет викладає: teaches(Викладач, Предмет) ---
teaches(samantsov, odm).   teaches(samantsov, kdm).   teaches(deineko, inf).

% --- Оцінки: mark(Студент, Предмет, Оцінка) ---
mark(zabuzhka, odm, 4).   mark(skovoroda, odm, 3).   mark(kidruk, odm, 2).

Ці факти описують невелику навчальну базу знань: студенти належать до груп, групи вивчають предмети, а викладачі ці предмети викладають (для прикладу взято дисципліни цього курсу):

Правила #

Правило — це імплікація (точніше, диз’юнкт Горна), записана «задом наперед». Символ :- читають «якщо» (це логічне $\leftarrow$), кому в тілі — як кон’юнкцію $\wedge$. Наприклад, «викладач $L$ навчає студента $S$» означає, що $L$ викладає предмет $C$, який вивчає група $G$, до якої належить $S$:

$$\text{lecturer\_of\_student}(L, S) \ \leftarrow\ \text{teaches}(L, C) \ \wedge\ \text{studies}(G, C) \ \wedge\ \text{student}(S, G)$$

мовою Prolog це й ще кілька правил виглядають так:

% Викладач L читає лекції групі G (викладає предмет, який вона вивчає)
lecturer_of_group(L, G) :-
    teaches(L, C),
    studies(G, C).

% Викладач L навчає студента S
lecturer_of_student(L, S) :-
    lecturer_of_group(L, G),
    student(S, G).

% Одногрупники: різні студенти однієї групи
classmate(X, Y) :-
    student(X, G),
    student(Y, G),
    X \= Y.

% Студент S склав предмет C (оцінка 3, 4 або 5)
passed(S, C) :-
    mark(S, C, M),
    M >= 3.

Зверніть увагу, як логічний запис перекладається один в один: змінні L, S неявно зв’язані квантором загальності («для всіх $L, S$: якщо тіло істинне, то й голова істинна»), а змінні C, G, що є лише в тілі, — квантором існування («існує спільний предмет $C$ і група $G$»). Предикат $\neq$ реалізовано вбудованим \=, а числове порівняння — вбудованим >=.

Питання #

Питання (ціль, запит) починають із ?-. Інтерпретатор шукає, чи можна вивести ціль із фактів і правил, і повертає true/false, а для змінних — усі значення, за яких ціль істинна.

?- teaches(samantsov, odm).         % чи Саманцов викладає ОДМ?
true.

?- studies(vpvps23, X).             % які предмети вивчає група ВПВПС23?
X = odm ;
X = inf.

?- lecturer_of_group(samantsov, G). % яким групам читає Саманцов?
G = vpvps23 ;
G = pzpi23.

?- lecturer_of_student(samantsov, S). % кого навчає Саманцов?
S = skovoroda ;
S = zabuzhka ;
S = kidruk ;
S = franko.

?- classmate(zabuzhka, X).          % хто одногрупники Забужко?
X = skovoroda ;
X = kidruk.

Передостаннє питання розкриває всю механіку. Щоб довести lecturer_of_student(samantsov, zabuzhka), Prolog застосовує правило й має знайти таку групу G, що lecturer_of_group(samantsov, G) і student(zabuzhka, G). Правило lecturer_of_group вимагає предмета C з teaches(samantsov, C) та studies(G, C): береться C = odm, studies(vpvps23, odm) — факт, тож G = vpvps23; лишається перевірити student(zabuzhka, vpvps23) — теж факт. Ціль доведено. Це і є логічне виведення — обчислювальна суть логіки предикатів.

Відповідність «логіка ↔ Prolog».

Логіка предикатів	Prolog
предикат $P(\dots)$	p(...) (з малої літери)
стала / об’єкт	ivan, 1, atom (з малої)
змінна $x$	X (з великої)
атомарна формула-факт	p(a).
імплікація $H \leftarrow B_1 \wedge B_2$	h :- b1, b2.
кон’юнкція $\wedge$	, (кома)
диз’юнкція $\vee$	кілька правил з тією ж головою
$\forall$ (змінні голови)	неявно над змінними правила

У Лабораторній роботі 2 той самий підхід застосовують до іншої бази знань — генеалогічного дерева: за фактами man/woman та father/mother виводять предикати brother, sister, grandfather, а далі uncle, aunt, cousin. Виконують її в онлайн-середовищі SWISH (https://swish.swi-prolog.org/).

6.8 Застосування у видавництві та поліграфії #

• Реляційні бази даних і SQL. Запит SELECT … WHERE умова — це буквально обчислення предиката над рядками таблиці; JOIN відповідає багатомісним предикатам, а квантори $\forall/\exists$ — конструкціям ALL/EXISTS. Каталог видань, база шрифтів чи облік замовлень працюють саме так (див. реляційну модель у Лекції 2).
• Перевірка обмежень (constraints). Вимога «жодна сторінка макета не порожня» формалізується як $\forall s\, \neg\,\text{ПОРОЖНЯ}(s)$, а «є хоча б одна кольорова ілюстрація» — як $\exists i\, \text{КОЛЬОРОВА}(i)$; система автоматично перевіряє такі предикати.
• Передпідготовка (preflight). Контроль макета перед друком — це перевірка універсально квантованого предиката: $\forall$ об’єкт сторінки задовольняє вимоги (роздільність $\ge 300$ dpi, кольори в межах профілю, шрифти вкладено). Знайдений контрприклад — це помилка, яку показують оператору.
• Пошук і фільтри. Фільтр «усі шрифти з насиченістю bold і підтримкою кирилиці» — це предикат над множиною гарнітур; результат — його область істинності.
• Валідація структури (XML/JSON-схеми). Правильність структури документа (наприклад, «кожен розділ має заголовок») задають правилами-предикатами, дуже близькими до правил Prolog.

Підсумок #

• Предикат — правило $P \colon M \to \{0,1\}$: області визначення $M$ воно зіставляє істиннісне значення. Область істинності $\{x \in M \mid P(x) = 1\}$ ототожнює предикати з підмножинами (Лекція 1), а двомісні предикати — з відношеннями (Лекція 2).
• Місність (порядок) — число аргументів. $0$-місний предикат — це звичайне висловлення (Лекція 5).
• Функціональні символи $f \colon M^n \to M$ будують об’єкти, а не істинність; з них і зі змінних та сталих складають терми. Предикат над термами — атомарна формула.
• Квантори: $\forall x\, P(x) = 1$, коли $P$ істинний на всіх елементах; $\exists x\, P(x) = 1$, коли хоч на одному. На скінченній області це «велика кон’юнкція» та «велика диз’юнкція». Порядок різнойменних кванторів суттєвий: $\forall x \exists y \not\equiv \exists y \forall x$.
• Закони алгебри предикатів: перейменування зв’язаної змінної, перестановка однойменних кванторів, дистрибутивність ($\forall$ щодо $\wedge$, $\exists$ щодо $\vee$) і, найважливіше, де Морган для кванторів: $\neg\forall x\, P \equiv \exists x\, \neg P$, $\neg\exists x\, P \equiv \forall x\, \neg P$.
• Випереджена нормальна форма $(Q_1 x_1)\dots(Q_n x_n) M$ — префікс плюс безкванторна матриця. Алгоритм: усунути $\leftrightarrow, \to$; занести $\neg$ до предикатів; перейменувати зв’язані змінні; винести квантори у префікс.
• Prolog — логіка предикатів як мова: факти (істинні атоми), правила (диз’юнкти Горна $H \leftarrow B$), питання (цілі для логічного виведення). Це міст до Лабораторної роботи 2.

Вправи #

Для розігріву #

1. Для предиката ДІЛИТЬСЯ$(x, y)$ на $M = \mathbb{N}$ обчисліть значення: ДІЛИТЬСЯ$(12, 3)$, ДІЛИТЬСЯ$(12, 5)$, ДІЛИТЬСЯ$(7, 7)$, ДІЛИТЬСЯ$(0, 4)$.
2. Запишіть область істинності одномісного предиката ПРОСТЕ$(x)$ на множині $M = \{2, 3, 4, \dots, 12\}$.
3. Визначте місність кожного предиката: ПАРНЕ$(x)$; БІЛЬШЕ$(x, y)$; МІЖ$(x, y, z)$ («$x$ між $y$ і $z$»); «$5$ — просте».
4. Прочитайте вголос і скажіть, істинні чи хибні на $\mathbb{N}$: (а) $\forall x\, \text{БІЛЬШЕ}(x + 1, x)$; (б) $\exists x\, \text{ПАРНЕ}(x)$; (в) $\forall x\, \text{ПРОСТЕ}(x)$.

Стандартні #

5. Формалізуйте мовою логіки предикатів на області «усі студенти»: (а) «кожен студент склав сесію»; (б) «деякий студент не склав сесію»; (в) «жоден студент не склав сесію». Покажіть, що (б) — це заперечення (а), і звірте це із законом де Моргана для кванторів.
6. Побудуйте дерево розбору терма мінус(плюс$(x, 1)$, $y$) та атомарної формули ДІЛИТЬСЯ(мінус($x$, $y$), $2$). Де в них предикат, а де — функціональні символи?
7. Доведіть закон де Моргана $\neg\, \exists x\, P(x) \equiv \forall x\, \neg P(x)$ за схемою доведення Теореми 6.14.
8. Зведіть до випередженої нормальної форми: (а) $\forall x\, P(x) \to \exists x\, Q(x)$; (б) $\neg\big(\exists x\, P(x) \wedge \forall y\, Q(y)\big)$. Обов’язково вкажіть, на якому кроці знадобилося перейменування.
9. Наведіть спростовний приклад (підберіть $M$ і предикати) до хибної рівносильності $\exists x\,(P(x) \wedge Q(x)) \equiv \exists x\, P(x) \wedge \exists x\, Q(x)$.

Підвищеної складності #

10. Доведіть односторонню імплікацію $\forall x\, P(x) \vee \forall x\, Q(x) \Rightarrow \forall x\,(P(x) \vee Q(x))$ і поясніть на прикладі, чому обернена хибна.
11. На області $\mathbb{Z}$ розгляньте предикат $S(x, y) =$ «$x + y = 0$». Визначте значення істинності формул $\forall x\, \exists y\, S(x, y)$ та $\exists y\, \forall x\, S(x, y)$; поясніть різницю в термінах Твердження 6.10.
12. Додайте до бази знань §6.7 правила для предикатів uncle(X, Y) («$X$ — дядько $Y$») та cousin(X, Y) («$X$ — двоюрідний брат/сестра $Y$»), виразивши їх через parent, brother, sister. Сформулюйте питання, що знаходить усіх двоюрідних Миколи. (Це передпідготовка до Лабораторної роботи 2.)

Lectures/ODM-L06.md · 59.5 KB · updated 2026-08-04 19:50