LINUX.ORG.RU

[swi-prolog][howto] Логическая программа


0

0

Около месяца назад один товарищ просил помочь ему решить задачу на Prolog. Я сам по маленьку пролог изучаю, но тогда мне было не до этого. Если вдруг автору всё ещё актуально, предлагаю свой вариант решения - на основе множеств.

Для интересующихся, напоминаю задачу:

Область определения - люди колледжа.

  • Все выпускники Итона в колледже играют в крикет.
  • Никто, кроме преподавателей, не обедает за верхним столом.
  • Ни один из тех, кто играет в крикет, не умеет грести.
  • Все мои друзья в этом колледже выпускники Итона.
  • Все преподаватели прекрасные гребцы.

Вывод: все мои друзья не преподаватели.

Решение:

set(eton_alumni).
set(lecturers).
set(friends).
set(cricket_players).
set(rowers).
set(dinner).

subset(eton_alumni, cricket_players). % all Eton alumni are cricket players
subset(dinner, lecturers). % nobody except lecturers dinners at upper table
subset(friends, eton_alumni). % all of my friends are Eton alumni
subset(lecturers, rowers). % all lecturers are good rowers
subset(X, X):- set(X).
nsubset(X, Y):- subset(X, Y), !.
nsubset(X, Y):- subset(X, Z), X \= Z, nsubset(Z, Y).

intersection(X, X, _):- !.
intersection(X, Y, _):- nsubset(X, Y), !.
intersection(X, Y, _):- nsubset(Z, X), X \= Z, intersection(Z, Y, 0), !.
intersection(Y, X, 0):- intersection(X, Y, 1).

no_intersection(cricket_players, rowers, _):- !. % no cricket players are rowers
no_intersection(X, Y, _):- nsubset(X, Z), X \= Z, no_intersection(Z, Y, 0), !.
no_intersection(Y, X, 0):- no_intersection(X, Y, 1).

intersection_possible(X, Y):-
	intersection(X, Y, 0);
	not(no_intersection(X, Y, 0)).

run:- not(intersection_possible(friends, lecturers)).

Если есть какие либо замечания/предложения/комментарии по поводу вариантов решения - с удовольствием выслушаю.

★★★★

Ответ на: комментарий от yoghurt

Человек изучает Пролог.

Писать простые программы и выкладывать решения - хороший подход.

x4DA ★★★★★ ()

1. ставь пробелы с обеих сторон от ':-'

2. наличие флага 1/0 как бы намекает тебе, что ты что-то делаешь не так

3. intersection можно написать проще. В данном случае «множества» могут быть только вложенными друг в друга. Соответственно, они «пересекаются» если кто-то напрямую в кого-то вложен, или есть третье множество, которое является подмножеством и того и того.

4. зачем нужен no_intersection и почему там приписан частный случай про игроков я не понял. Старайся все таки отделять данные от правил.

anonymous ()
Ответ на: комментарий от anonymous

Спасибо за советы.

зачем нужен no_intersection и почему там приписан частный случай про игроков я не понял. Старайся все таки отделять данные от правил.

Мне необходимо явно указать, что «A и B не пересекаются» доказуемо, и указать конкретный случай (множества cricket_players и rowers не пересекаются). Т.е., получается следующее: предикат intersection имеет значение истины, если доказуемо пересечение множеств; в то же время, если intersection ложен, это ещё не означает доказуемость того, что множества не пересекаются (благодаря closed world assumption); то же самое с no_intersection.

Предикат intersection_possible определяет, возможно ли пересечение множеств (если доказуемо пересечение или если недоказуемо отсутствие пересечения). Цель - доказать, что пересечение множеств невозможно.

runtime ★★★★ ()
Ответ на: комментарий от runtime

Для начала, давай таки избавимся от слова «множество». Те объекты и операции над ними, что ты ввел, не слишком соответствуют понятию множество. То, что ты описываешь больше подходит на описание отношения предок-потомки (твои «множества» или не пересекаются или вложены друг в друга, это как-то куцо для множеств, а для такого отношения самое то.), с одной поправкой: у каждого объекта есть хотя бы один предок - он сам. Тогда твоё «A и B не пересекаются» трансформируется в «A и B не связаны родством».

Мне необходимо явно указать, что «A и B не пересекаются» доказуемо, и указать конкретный случай (множества cricket_players и rowers не пересекаются). Т.е., получается следующее: предикат intersection имеет значение истины, если доказуемо пересечение множеств; в то же время, если intersection ложен, это ещё не означает доказуемость того, что множества не пересекаются (благодаря closed world assumption); то же самое с no_intersection.

Это сработало на таком простом примере. Будь входных данных чуть побольше и вопрос не такой очевидный, составить базу с полным описанием было бы значительно сложней. Вобщем-то, как писать зависит от конкретной задачи, важно, чтобы ты понимал, что происходит.

У меня получилось как-то так:

set(lecturers).
set(friends).
set(cricket_players).
set(rowers).
set(dinner).

subset_(eton_alumni, cricket_players).
subset_(dinner, lecturers).
subset_(friends, eton_alumni).
subset_(lecturers, rowers).

subset(X,X) :- set(X).
subset(X,Y) :- subset_(X,Y).
subset(X,Y) :- subset_(X,Z), subset(Z,Y), Z \= Y.

intersection(X,Y) :- subset(X,Y).
intersection(X,Y) :- subset(Y,X), X \= Y.


%% ?- subset(X,Y), writeln((X,Y)), fail.
%% ?- intersection(X,Y), writeln((X,Y)), fail.

anonymous ()
Ответ на: комментарий от runtime

И да, не злоупотребляй отсечением, хотя бы поначалу.

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.