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

## Огляд

У [Лекції 5](ODM-L05.md) ми вивчали **логіку висловлень**. Там найменшою
неподільною одиницею був **атом** — ціле розповідне речення, якому приписують одне
значення істинності: «Дніпро впадає в Чорне море» ($=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](../Laboratory/Laboratory2/main.md), де ви власноруч
збудуєте базу знань про генеалогічне дерево.

> **Про строгість.** Як і в попередніх лекціях, ключові закони оформлені як
> **теореми** й **твердження** та супроводжуються доведенням до позначки
> $\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$.

![Предикат ПАРНЕ як відображення області визначення M у область значень {0,1}](img/l06_predicate_map.png)

> **Зауваження (предикат — це відображення).** Означення дослівно збігається з
> означенням **функції** (відображення) з [Лекції 1](ODM-L01.md), у якої областю
> прибуття є двоелементна множина $\{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](ODM-L05.md). Тому логіка висловлень — це «логіка предикатів без змінних
> і без кванторів», а нинішня лекція — її повноцінне узагальнення.

---

## 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$ називають **місністю** (або
> **порядком**, **арністю**) предиката.

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

| Місність $n$ | Назва | Приклад |
|:--:|---|---|
| $0$ | висловлення | «$5$ — просте» |
| $1$ | одномісний (властивість) | ПРОСТЕ$(x)$, ПАРНЕ$(x)$ |
| $2$ | двомісний (бінарне відношення) | ДІЛИТЬСЯ$(x, y)$, БІЛЬШЕ$(x, y)$ |
| $3$ | тримісний | МІЖ$(x, y, z)$, СКЛАДАТИ$(x, y, z)$ |

**Приклад 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](ODM-L02.md):
$$ 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$, стрілка веде від
батька до дитини.

![Двомісний предикат БАТЬКО як орієнтований граф — відношення на множині M](img/l06_father_relation.png)

Саме цей предикат ми оживимо на Пролозі в §6.7, а розширимо — у
[Лабораторній роботі 2](../Laboratory/Laboratory2/main.md).

---

## 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$).

![Дерево розбору атомарної формули БІЛЬШЕ(плюс(x,1), x): предикат у корені, терми в аргументах](img/l06_term_tree.png)

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

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

**Приклад 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$.

![Квантор загальності (усі елементи дають 1) проти квантора існування (принаймні один дає 1)](img/l06_quantifiers.png)

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

Коли область **скінченна**, $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](ODM-L01.md).

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

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

| Квантор | Природномовні відповідники |
|---|---|
| $\forall x$ | «для всіх $x$», «кожен $x$», «будь-який $x$», «усякий $x$», «жоден… не» (з $\neg$) |
| $\exists x$ | «існує $x$», «знайдеться $x$», «деякий $x$», «хоча б один $x$», «принаймні один $x$» |

**Приклад 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$

![Закони де Моргана для кванторів: заперечення міняє квантор на протилежний і переходить усередину](img/l06_demorgan_quant.png)

> **Зауваження (це справді де Морган).** На скінченній області закон миттєво
> випливає зі «звичайного» де Моргана з [Лекції 5](ODM-L05.md):
> $$ \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, $$
> і аналогічно для інших зв'язок.

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

| Закон | Формулювання |
|---|---|
| Перейменування зв'язаної змінної | $\forall x\, P(x) \equiv \forall y\, P(y)$ ($y$ не входить у $P$) |
| Перестановка однойменних кванторів | $\forall x \forall y\, P \equiv \forall y \forall x\, P$;  $\exists x \exists y\, P \equiv \exists y \exists x\, P$ |
| Дистрибутивність $\forall$ щодо $\wedge$ | $\forall x\,(P(x) \wedge Q(x)) \equiv \forall x P(x) \wedge \forall x Q(x)$ |
| Дистрибутивність $\exists$ щодо $\vee$ | $\exists x\,(P(x) \vee Q(x)) \equiv \exists x P(x) \vee \exists x Q(x)$ |
| Де Морган для $\forall$ | $\neg\,\forall x\, P(x) \equiv \exists x\, \neg P(x)$ |
| Де Морган для $\exists$ | $\neg\,\exists x\, P(x) \equiv \forall x\, \neg P(x)$ |
| Винесення множника | $\forall x\,(P(x) \wedge Q) \equiv \forall x P(x) \wedge Q$ ($x$ не входить у $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)$.

![Побудова випередженої нормальної форми крок за кроком: усунення імплікації, де Морган, перейменування, винесення кванторів](img/l06_prenex.png)

**Приклад 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`, …) — так код гарантовано виконається в будь-якому
> інтерпретаторі; самі назви суто ілюстративні.

### Факти

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

```prolog
% --- Студенти та їхні групи: 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).
```

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

![Навчальна база знань: студенти → групи → предмети ← викладачі](img/l06_study.png)

### Правила

**Правило** — це імплікація (точніше, **диз'юнкт Горна**), записана «задом наперед».
Символ `:-` читають «**якщо**» (це логічне $\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 це й ще кілька правил виглядають так:

```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`, а для змінних — усі значення, за
яких ціль істинна.

```prolog
?- 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](../Laboratory/Laboratory2/main.md) той самий підхід
застосовують до **іншої** бази знань — генеалогічного дерева: за фактами `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](ODM-L02.md)).
- **Перевірка обмежень (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](../Laboratory/Laboratory2/main.md).

## Вправи

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

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](../Laboratory/Laboratory2/main.md).)