Разбор фрагмента
- База фактов:
parent(a,b).
parent(a,c).
- Правило:
sibling(X,Y) :- parent(Z,X), parent(Z,Y), X \= Y.
- Запрос:
?- sibling(b,Y).
Как Prolog выполняет запрос (backtracking):
1. Prolog ищет родителя Z для X=b: находит Z=a (из fact `parent(a,b)`).
2. Затем ищет Y с тем же родителем Z=a: перебирает `parent(a,Y)`. Сначала Y=b — но проверка `X \= Y` отвергает этот вариант, затем Y=c — проходит, результат Y=c возвращается.
3. При попытке получить следующий ответ Prolog откатывается (backtracks) к предыдущним выборочным точкам: пытаетя взять другие варианты для `parent(a,Y)` (их нет) — затем пробует другие варианты для `parent(Z,X)` (их нет) — и завершает поиск.
Почему бывают лишние/неожиданные решения
- Дублирование из-за нескольких общих родителей: если есть два факта `parent(p1,b)` и `parent(p2,b)` и оба дают одного и того же `Y`, то тот же пара (b,Y) может быть найдена дважды через разные Z.
- Симметрия: правило даёт и (b,c), и (c,b) при общем родителе — если вам нужна «пара» без упорядочивания, то это два представления одной и той же пары.
- Backtracking порождает все логически возможные доказательства; если вы хотите единственный ответ, нужно явно ограничить поиск.
Оператор cut (!) — как он работает
- `!` удаляет все choice-points, созданные в нынешнем вызове предиката до места cut. После `!` при откате Prolog не вернётся к альтернативам, предшествовавшим cut в этой clause.
- Cut используется для «коммита» к выбору. Это может ускорять вычисление, но:
- Green cut: не меняет логическое значение предиката (только оптимизация).
- Red cut: меняет логическое значение (меняет суть программы), снижая декларативность и переносимость.
Примеры переписывания sibling
1) Убрать симметричные дубликаты (возвращать только упорядоченные пары, но все возможные Y):
sibling(X,Y) :-
parent(Z,X),
parent(Z,Y),
X \= Y,
X @< Y.
Объяснение: `X @< Y` — термовое упорядочивание; для пары (b,c) вернётся только (b,c), а (c,b) уже не будет даваться. Это сохраняет полноту (все разные братья/сестры), но убирает симметричные дубляжи.
2) Вернуть ровно один упорядоченный результат для каждого запроса (детерминизировать — выбрать первый найденный):
sibling_one(X,Y) :-
parent(Z,X),
parent(Z,Y),
X \= Y,
X @< Y,
!.
Объяснение: `!` после успешного нахождения первой подходящей пары запрещает дальнейший backtracking внутри этого правила — для конкретного запроса будет ровно один ответ (первый в порядке поиска БД). Компромисс: вы теряете остальные логически корректные ответы (неполнота).
3) Детальная, но декларативная версия (получить уникальные Y и выбрать первый явно):
sibling_first(X,Y) :-
setof(Y0, Z^(parent(Z,X), parent(Z,Y0), X \= Y0, X @< Y0), Ys),
Ys = [Y|_].
Объяснение: `setof` собирает все уникальные упорядоченные Y в список (в отсортированном виде), потом берем первый элемент; тут нет cut, поведение декларативно предсказуемо, но нужна поддержка агрегатов (setof/3).
Компромиссы детерминизации и применимость логического программирования
- Детерминизация (cut или выбор «первого» результата) даёт предсказуемое и эффективное поведение, но снижает полноту: вы можете потерять альтернативные выводы, что критично в задачах вывода знаний, где важно получить все возможные заключения.
- Сохранение полной логики (без cut) делает программу чисто декларативной и пригодной для автоматического вывода и доказательства, но может приводить к дублированию и более дорогостоящему поиску; поэтому для удобства часто комбинируют:
- логически чистые правила + агрегаты (setof/1, bagof/1) для устранения дубликатов и контроля над результатами;
- cut там, где действительно нужен «коммит» и где теряется только лишняя вычислительная детализация (green cut).
- Для систем вывода знаний предпочтительна декларативность (чтобы сохранялась интерпретируемость и полнота); оптимизации (cut) применять осмотрительно и документировать их влияние на смысл.
Краткая рекомендация
- Если нужно только убрать симметричные дубли — добавьте `X @< Y`.
- Если нужно ровно один ответ (жёсткая детерминация) — добавьте `!` в конце, но помните о потере других корректных выводов.
- Для безопасного и предсказуемого поведения в KB-системах лучше использовать агрегаты (setof/bagof) или явную постобработку результатов.