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

Цей розділ самодостатній: він містить усю теорію, потрібну для роботи, — поняття предиката як відношення, синтаксис мови Prolog (факти, правила, запити), стислий опис уніфікації та пошуку з поверненням, опис середовища SWISH і техніку вираження родинних відношень через базові предикати — а також повний демонстраційний приклад. Зовнішні джерела не потрібні. Теоретичне підґрунтя — Лекція 6 «Логіка предикатів».

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

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

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

Кожен предикат рівносильний відношенню — множині тих наборів, на яких він істинний. $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:

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

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

Факти #

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

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

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

Правила #

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

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

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

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 шукає, чи можна вивести запит із фактів і правил.

?- 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 вона просто трапляється лише в тілі:

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

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

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

Аналогічно (наведено логічні означення; коди для власного дерева ви пишете самі — див. 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 і повторіть запити.

% ---------- Факти: стать -------------------------------------------------
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.

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

?- 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 мали відповіді, у вашому дереві мають бути щонайменше двоє дітей в однієї пари, і принаймні в двох із них — власні діти (тоді з’являються двоюрідні). Плануйте дерево заздалегідь.

Laboratory/Laboratory2/2method.md · 20.4 KB · updated 2026-08-04 14:36