является множество, содержащее все элементы, принадлежащие
X или
Y или одновременно им обоим.
Пример: {a,b,c} ∪ {с,d,е} = {a,b,c,d,e}.
Это – основные операции, которые обычно используются при работе с множествами. Теперь мы можем приступить к написанию Пролог-программ, реализующих каждую из них. Первая основная операция 'принадлежность' реализуется тем же самым предикатом принадлежит, с которым мы уже встречались несколько раз. Однако в нашем определении принадлежит в граничном случае нет символа «отсечения», поэтому мы можем создавать последовательные элементы списка, используя возвратный ход:
принадлежит(Х,[Х|_]).
принадлежит(Х,[_|Y]):- принадлежит(Х,Y).
Следующая операция 'включение' реализуется предикатом включает, причем включает(Х, Y) завершается успешно, если X является подмножеством Y, т. е. Y включает X. Второе утверждение в его определении опирается на математическое соглашение о том, что пустое множество является подмножеством любого множества. В Прологе это соглашение дает способ проверки граничного условия для первого аргумента, поскольку запрограммирована рекурсивная обработка его хвоста:
включает([А|Х],Y):- принадлежит(А,Y), включает(Х,Y).
включает([],Y).
Следом идет самый сложный случай, реализация пересечения. Целевое утверждение пересечение(Х, Y,Z) доказуемо, если пересечением X и Y является Z. Это как раз тот случай, когда используется предположение, что данные списки не содержат повторяющихся элементов:
пересечение([], X, []).
пересечение([X|R],Y,[X|Z]):-принадлежит(Х, Y),!,пересечение(R, Y,Z).
пересечение([Х|R],Y,Z):- пересечение(R, Y,Z).
Наконец, объединение. Целевое утверждение объединение (X,Y,Z) доказуемо, если объединением X и Y является Z. Заметим, что реализация предиката объединение сконструирована на основе определений предикатов пересечение и присоединить:
объединение([],Х,Х).
объединение([Х|R],Y,Z):- принадлежит(Х,Y),!,
объединение(R,Y,Z). объединение([X |R],Y,[X|Z]):- объединение(R,Y,Z).
Этим исчерпывается наш перечень предикатов работы с множествами. И хотя использование множеств может оказаться не характерным для ваших программ, тем не менее полезно изучить эти примеры. Они позволяют вам получить ясное представление о том, как можно использовать рекурсию и возвратный ход.
