# 2. Методичні вказівки

Цей розділ **самодостатній**: він містить усю теорію, потрібну для роботи, — поняття
предиката як відношення, синтаксис мови Prolog (факти, правила, запити), стислий опис
уніфікації та пошуку з поверненням, опис середовища [SWISH](https://swish.swi-prolog.org/)
і техніку вираження родинних відношень через базові предикати — а також повний
**демонстраційний приклад**. Зовнішні джерела не потрібні. Теоретичне підґрунтя —
[Лекція 6 «Логіка предикатів»](../../Lectures/ODM-L06.md).

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

Нагадаємо з [Лекції 6](../../Lectures/ODM-L06.md): **предикат** — це правило, що кожному
набору об'єктів зі своєї **області визначення** $M$ ставить у відповідність одне з двох
значень з **області значень** $\{1, 0\}$ (**істина** / **хиба**). Кількість аргументів
називають **місністю** (арністю) предиката:

- одномісний предикат $\mathrm{MAN}(x)$ — «$x$ є чоловіком»;
- двомісний предикат $\mathrm{FATHER}(x, y)$ — «$x$ є батьком $y$».

![Одномісний предикат MAN як правило, що кожній людині з області M зіставляє 1 або 0](img/lb2_predicate.png)

Кожен предикат рівносильний **відношенню** — множині тих наборів, на яких він
істинний. $n$-місний предикат $P$ над $M$ задає підмножину декартового степеня:

$$
P \;\longleftrightarrow\; R_P = \{\, (x_1, \dots, x_n) \in M^{n} \mid P(x_1, \dots, x_n) = 1 \,\} \subseteq M^{n}.
$$

Так, $\mathrm{FATHER}$ — це підмножина пар $M \times M$: усі пари $(x, y)$, для яких «$x$
батько $y$» істинно. Саме цей погляд — **предикат як перелік істинних наборів** —
робить логіку предикатів придатною для програмування: у Prolog ми просто **перелічуємо
істинні набори** (факти) і **описуємо правилами**, як з одних істинних наборів
дістати інші.

> **Зауваження (базові та похідні предикати).** У цій роботі $\mathrm{MAN}$,
> $\mathrm{WOMAN}$, $\mathrm{FATHER}$, $\mathrm{MOTHER}$ — **базові**: їхні істинні
> набори перелічують явно. Решту ($\mathrm{BROTHER}$, $\mathrm{GRANDFATHER}$ тощо)
> **не перелічують**, а **обчислюють** — задають логічною формулою над базовими. У
> цьому і полягає ощадність логічного опису: кілька десятків фактів + кілька правил
> описують сотні істинних наборів похідних відношень.

## 2.2 Синтаксис Prolog: факти, правила, запити

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

### Атоми та змінні

Перш ніж писати речення, засвоїмо головне синтаксичне правило Prolog:

| Пишеться | Що це | Приклади |
|---|---|---|
| з **малої** літери | **атом** — конкретна стала (ім'я об'єкта чи предиката) | `ivan`, `petro`, `man`, `father` |
| з **великої** літери або `_` | **змінна** — «якийсь об'єкт», значення якого добирає інтерпретатор | `X`, `Y`, `Z`, `Person`, `_` |

> **Типова помилка.** Ім'я, записане з **великої** літери, Prolog вважає **змінною**,
> а не константою. Тому реальне ім'я «Іван» не можна записати як `Ivan` — це буде
> змінна. Записуйте константи з малої (`ivan`) або, якщо потрібні саме кириличні
> імена з великої літери, беріть їх в одинарні лапки: `'Іван'`. У цій роботі радимо
> вживати короткі атоми з малої літери (транслітерацію), як у прикладах нижче.

Окрема **анонімна змінна** `_` означає «будь-що, значення не цікавить»: запит
`father(ivan, _)` питає «чи є в `ivan` хоч якась дитина».

### Факти

**Факт** стверджує, що предикат істинний на конкретних сталих. Це найпростіше речення:
голова без умов, завершена **крапкою**.

```prolog
man(ivan).             % «ivan — чоловік» істинно
woman(maria).          % «maria — жінка» істинно
father(ivan, petro).   % «ivan є батьком petro» істинно
mother(maria, petro).  % «maria є матір'ю petro» істинно
```

Набір фактів — це і є явний перелік істинних наборів базового предиката (його
відношення $R_P$ з §2.1).

### Правила

**Правило** визначає предикат **через інші** предикати. Воно має вигляд

```prolog
Голова :- Тіло.
```

і читається «**Голова** істинна, **якщо** істинне **Тіло**». Знак `:-` — це імплікація
«якщо» (тіло $\to$ голова), а **кома** в тілі — **кон'юнкція** (логічне «і», $\wedge$):

```prolog
parent(X, Y) :- father(X, Y).   % X — один із батьків Y, якщо X — батько Y,
parent(X, Y) :- mother(X, Y).   % або (окреме правило) якщо X — мати Y.
```

Два правила з однаковою головою — це **диз'юнкція** («або»): `parent` істинний, якщо
істинне **перше** тіло **або** друге. Змінні в правилі **універсально квантовані**:
`parent(X, Y) :- father(X, Y)` означає «для всіх $X, Y$: якщо $\mathrm{FATHER}(x,y)$, то
$\mathrm{PARENT}(x,y)$». А змінна, що трапляється **лише в тілі** (не в голові),
**існує** — вона квантована $\exists$ (див. §2.5).

### Запити (питання)

**Запит** — це питання до бази знань; його ставлять після запрошення `?-`. Prolog
шукає, чи можна вивести запит із фактів і правил.

```prolog
?- man(ivan).            % true   — є такий факт
?- man(maria).           % false  — такого факту немає й вивести не можна
?- father(ivan, X).      % X = petro ; X = oleh ; X = olha   — усі діти ivan
```

Якщо в запиті є змінна, Prolog повертає **підстановки**, за яких запит істинний.
Кілька відповідей перебирають по черзі (див. §2.3).

> **Зауваження (припущення замкненого світу).** Відповідь `false` означає не «хибно за
> означенням», а «не вивідно з наявних знань». Prolog вважає **хибним усе, чого не
> можна довести** з бази (*closed-world assumption*). Тому база має містити **всі**
> потрібні факти: забули факт — і залежні запити повертатимуть `false`.

## 2.3 Уніфікація та пошук із поверненням

Виконуючи запит, Prolog зіставляє **ціль** (goal) з головами речень за допомогою
**уніфікації** — пошуку такої підстановки значень змінних, за якої два вирази стають
однаковими. Наприклад, ціль `father(ivan, X)` уніфікується з фактом
`father(ivan, petro)`, зв'язуючи `X = petro`.

Якщо цілей кілька (тіло правила — кон'юнкція), Prolog доводить їх **зліва направо**.
Коли якась ціль має **кілька** способів справдитися, інтерпретатор бере перший, а
решту запам'ятовує; якщо згодом виникає невдача — він **вертається** (backtracking) до
останньої точки вибору й пробує наступний варіант. У SWISH наступну відповідь просять,
натиснувши **`;`** (крапка з комою) або кнопку **Next**.

**Приклад.** За фактами `father(ivan, petro)`, `father(ivan, oleh)`,
`father(ivan, olha)` запит `father(ivan, X)` дає послідовно `X = petro`, потім (після
`;`) `X = oleh`, потім `X = olha`, а далі — `false` (варіантів більше немає). Саме так
Prolog «обходить» усі істинні набори предиката.

## 2.4 Середовище SWISH

**SWISH** — онлайн-версія SWI-Prolog: <https://swish.swi-prolog.org/>. Реєстрація не
потрібна, працює у браузері. Робоче вікно поділене на дві частини:

1. **Ліва панель — програма.** Сюди вводять факти й правила (усю базу знань). Кириличні
   символи підтримуються (файл у кодуванні UTF-8), але атоми все одно мають починатися
   з малої літери.
2. **Права нижня панель — запити.** Поле з підказкою `?-`. Введіть запит і натисніть
   **Run!** (або `Ctrl`+`Enter`). Для наступної відповіді натисніть **`;`** / **Next**,
   для припинення перебору — **Stop**.

Порядок роботи: наберіть програму ліворуч → поставте запит праворуч → натисніть
**Run!** → за потреби перебирайте відповіді через **`;`**. Для звіту зручно робити
**знімки екрана** (скріншоти) кожного запиту разом з відповіддю. Будь-який інший
інтерпретатор Prolog (наприклад, десктопний SWI-Prolog) теж підійде.

## 2.5 Родинні відношення через базові предикати

Ключова ідея роботи — **виразити** складні відношення формулою над базовими. Спочатку
введемо зручний допоміжний предикат «бути одним із батьків»:

$$
\mathrm{PARENT}(x, y) \;\equiv\; \mathrm{FATHER}(x, y) \;\vee\; \mathrm{MOTHER}(x, y).
$$

Мовою Prolog диз'юнкцію зручно подати **двома правилами** з однаковою головою (див.
§2.2). Далі всі відношення виражають через `parent`, `man`, `woman` та нерівність.

### Приклад: предикат «брат»

«$x$ — брат $y$» означає: $x$ — **чоловік**, у $x$ та $y$ є **спільний батько або
мати**, і $x$ та $y$ — **різні** особи:

$$
\mathrm{BROTHER}(x, y) \;\equiv\; \mathrm{MAN}(x) \;\wedge\; \exists z\,\big(\mathrm{PARENT}(z, x) \wedge \mathrm{PARENT}(z, y)\big) \;\wedge\; x \ne y.
$$

Змінна $z$ (спільний предок) квантована $\exists$: достатньо, щоб знайшовся **хоч
один** спільний із $x$ та $y$ батько чи мати. У правилі Prolog вона просто трапляється
лише в тілі:

```prolog
brother(X, Y) :-
    man(X),          % X — чоловік
    parent(Z, X),    % Z — один із батьків X
    parent(Z, Y),    % той самий Z — один із батьків Y
    X \= Y.          % X та Y — різні особи
```

![Схема правила brother(X, Y): спільний предок Z, чоловіча стать X та умова X ≠ Y](img/lb2_rule.png)

> **Типова помилка (пропущена нерівність).** Без цілі `X \= Y` кожен був би сам собі
> братом: `parent(Z, X)` і `parent(Z, X)` уніфікуються з тим самим `Z`, тож
> `brother(petro, petro)` хибно вивелося б як `true`. Оператор `\=` означає «**не
> уніфікуються**» (не можуть бути зроблені рівними) — на сталих це звичайне «не
> дорівнює».

### Решта відношень — за тим самим зразком

Аналогічно (наведено **логічні означення**; коди для власного дерева ви пишете самі —
див. [4task.md](4task.md)):

- **Сестра.** $\mathrm{SISTER}(x, y) \equiv \mathrm{WOMAN}(x) \wedge \exists z\,(\mathrm{PARENT}(z,x) \wedge \mathrm{PARENT}(z,y)) \wedge x \ne y$ — те саме, але $x$ — жінка.
- **Батьки.** $\mathrm{PARENTS}(x, y, z) \equiv \mathrm{FATHER}(x, z) \wedge \mathrm{MOTHER}(y, z)$ — $x$ (батько) і $y$ (мати) є батьками спільної дитини $z$.
- **Дід / баба (композиція «через покоління»).** $\mathrm{GRANDFATHER}(x, y) \equiv \exists z\,(\mathrm{FATHER}(x, z) \wedge \mathrm{PARENT}(z, y))$: $x$ — батько **когось** ($z$), хто є одним із батьків $y$. Для баби беруть $\mathrm{MOTHER}(x, z)$ замість $\mathrm{FATHER}$.
- **Дядько / тітка.** $\mathrm{UNCLE}(x, y) \equiv \exists z\,(\mathrm{BROTHER}(x, z) \wedge \mathrm{PARENT}(z, y))$: $x$ — брат одного з батьків $y$. Для тітки — $\mathrm{SISTER}$ замість $\mathrm{BROTHER}$.
- **Двоюрідні.** $\mathrm{COUSIN}(x, y) \equiv \exists a\,\exists b\,\big(\mathrm{PARENT}(a, x) \wedge \mathrm{PARENT}(b, y) \wedge \mathrm{SIBLING}(a, b)\big)$, де $\mathrm{SIBLING}(a,b) \equiv \exists z\,(\mathrm{PARENT}(z,a)\wedge\mathrm{PARENT}(z,b)) \wedge a \ne b$. Тобто батьки $x$ і батьки $y$ — рідні брат/сестра; звідси спільний **дід або баба**, але **різні** батьки.

Зверніть увагу на прийом **композиції відношень**: «дід» — це «батько» ∘ «батько-чи-мати»,
«дядько» — «брат» ∘ «батько-чи-мати». Він працює завдяки спільній змінній ($z$),
квантованій $\exists$: вона «склеює» два кроки в ланцюжок.

## 2.6 Демонстраційний приклад

Нижче — **повна** невелика база знань (те саме дерево, що на рисунку) з одним похідним
предикатом `brother` і запитами до нього. Скопіюйте її в ліву панель SWISH і
повторіть запити.

![Демонстраційне генеалогічне дерево: сині вузли — чоловіки, помаранчеві — жінки; стрілки ведуть від батьків до дітей](img/lb2_tree.png)

```prolog
% ---------- Факти: стать -------------------------------------------------
man(ivan).      man(petro).   man(oleh).    man(andrii).  man(taras).
woman(maria).   woman(nina).  woman(halyna).  woman(olha).  woman(sofia).

% ---------- Факти: батьківство (father(X, Y): X — батько Y) --------------
father(ivan, petro).    father(ivan, oleh).   father(ivan, olha).
father(petro, andrii).  father(petro, sofia).
father(oleh, taras).

% ---------- Факти: материнство (mother(X, Y): X — мати Y) ----------------
mother(maria, petro).   mother(maria, oleh).  mother(maria, olha).
mother(nina, andrii).   mother(nina, sofia).
mother(halyna, taras).

% ---------- Похідні предикати -------------------------------------------
parent(X, Y) :- father(X, Y).
parent(X, Y) :- mother(X, Y).

brother(X, Y) :-
    man(X),
    parent(Z, X),
    parent(Z, Y),
    X \= Y.
```

Запити та очікувані відповіді (у правій панелі; `;` — прохання про наступну відповідь):

```prolog
?- father(ivan, petro).
true.

?- parent(P, andrii).
P = petro ;
P = nina ;
false.

?- brother(petro, olha).
true.

?- brother(taras, _).
false.                       % у taras немає рідних братів/сестер

?- brother(X, olha).
X = petro ;
X = petro ;
X = oleh ;
X = oleh ;
false.
```

> **Зауваження (повтори у відповідях).** В останньому запиті `petro` та `oleh`
> з'являються **двічі**. Це не помилка: `petro` — брат `olha` через **спільного
> батька** `ivan` **і** через **спільну матір** `maria`, тобто існує **два різні
> доведення**, і пошук із поверненням показує кожне окремо. Якщо потрібні лише різні
> імена, у SWI-Prolog це роблять предикатами `distinct/1` або `setof/3` (виходить за
> межі базового рівня; згадайте про повтори у висновках звіту).

## 2.7 Типові помилки та поради

- **Велика літера в імені.** `Petro` — це змінна, а не особа. Константи — з малої:
  `petro`.
- **Забутий факт.** Через замкнений світ (§2.2) неповна база дає `false` там, де ви
  очікуєте `true`. Спершу переконайтеся, що всі `man`/`woman`/`father`/`mother` внесені.
- **Пропущена нерівність `X \= Y`.** Дає «сам собі брат/сестра». Додавайте її в
  `brother`, `sister`, а також `a \= b` у `cousin`.
- **`parent` лише з `father`.** Не забудьте **друге** правило з `mother` — інакше
  відношення по материнській лінії «зникнуть».
- **Плутанина `=` та `\=`.** `=` — уніфікація (спроба зробити рівними), `\=` — її
  заперечення. Для порівняння вже відомих сталих цього достатньо.
- **Крапка в кінці.** Кожне речення (факт, правило, запит) завершують крапкою; її брак —
  найчастіша синтаксична помилка.
- **Достатньо велике дерево.** Щоб `uncle`, `aunt`, `cousin` мали відповіді, у вашому
  дереві мають бути **щонайменше двоє** дітей в однієї пари, і **принаймні в двох** із
  них — власні діти (тоді з'являються двоюрідні). Плануйте дерево заздалегідь.