Множества

В Прологе, в отличие от некоторых императивных языков программирования, нет такой встроенной структуры данных как множества. Однако это понятие можно реализовать это понятие, опираясь на имеющиеся стандартные домены. Под множеством можно понимать список, который не содержит повторных вхождений элементов, то есть в множестве любое значение не может встречаться более одного раза. Можно разработать предикаты, которые реализуют основные теоретико-множественные операции.

Предикат превращает произвольный список в множество. Для этого удалим повторные вхождения элементов, для чего воспользуемся предикатом DeleteAll. Два аргумента – исходный и выходной список.

list_set([],[]). /* пустой список является множеством

в нашем понимании */

list_set ([H|T],[H|T1]) :–

delete_all(H,T,T2),

/* T2 — результат удаления

вхождений первого элемента

исходного списка H из хвоста T */

list_set (T2,T1).

/* T1 — результат удаления

повторных вхождений элементов

из списка T2 */

Можно реализовать каждую операцию так, чтобы в результате гарантированно получалось множества.

Предикат, проверяющий принадлежность элемента списку.

member3(X,[X|_]) :- !.

member3(X,[_|T]) :- member3(X,T).

Объединения двух множеств A, B. Три параметра: первый – множество А, второй – множество В, третий – выходное множество. В других операция аналогично.

union([ ],S2,S2). /* результатом объединения

пустого множества со множеством S2

будет множество S2 */

union([H|T],S2,S):–

member3(H,S2),

/* если голова первого

множества H принадлежит второму

множеству S2, */

!,

union(T,S2,S).

/* то результатом S будет

объединение хвоста первого

множества T и второго

множества S2 */

union([H |T],S2,[H|S]):–

union(T,S2,S).

/* в противном случае результатом

будет множество, образованное

головой первого множества H

и хвостом, полученным объединением

хвоста первого множества T

и второго множества S2 */

Пересечение множеств.

intersection([],_,[]). /* в результате пересечения

пустого множества с любым

множеством получается пустое

множество */

intersection([H|T1],S2,[H|T]):–

member3(H,S2),

/* если голова первого множества H

принадлежит второму множеству S2 */

!,

intersection(T1,S2,T).

/* то результатом будет множество,

образованное головой первого

множества H и хвостом, полученным

пресечением хвоста первого

множества T1 со вторым

множеством S2 */

intersection([_|T],S2,S):–

intersection(T,S2,S).

/* в противном случае результатом

будет множество S, полученное

объединением хвоста первого

множества T со вторым

множеством S2 */

Разность множеств.

minus([],_,[]). /* при вычитании любого множества

из пустого множества получится пустое

множество */

minus([H|T],S2,S):–

member3(H,S2),

/* если первый элемент первого

множества H принадлежит второму

множеству S2*/

!,

minus(T,S2,S).

/* то результатом S будет разность

хвоста первого множества T

и второго множества S2 */

minus([H|T],S2,[H|S]):–

minus(T,S2,S).

/* в противном случае, результатом

будет множество, образованное

первым элементом первого

множества H и хвостом, полученным

вычитанием из хвоста первого

множества T второго множества S2 */

Другой вариант через разность.

intersection2(A,B,S):–

minus(A,B,A_B), /*A_B=A\B */

minus(A,A_B,S). /* S = A\A_B = A\(A\B) */

Предикат проверяющий является ли множество подмножеством другого.

subset([],_). /* пустое множество является

подмножеством любого множества */

subset([H|T],S):– /* множество [H|T] является

подмножеством множества S */

member3(H,S), /* если его первый элемент H

принадлежит S */

subset(T,S). /* и его хвост T является

подмножеством множества S */

Тот же предикат через операции объединение и пересечение.

subsetU(A,B):–

union(A,B,B). /* объединение множеств

совпадает со вторым множеством */

subsetI(A,B):–

intersection(A,B,A).

/* пересечение множеств

совпадает с первым множеством*/

Проверка совпадений двух множеств.

equal(A,B):– /* множество A совпадает

со множеством B, */

subset(A,B), /* если множество A содержится

во множестве B */

subset(B,A). /* и множество B является

подмножеством множества A*/

Проверка на собственное подмножество.

Prop_subset(A,B):–

subset(A,B),

/* множество A содержится

во множестве B */

not(equal(A,B)).

/* множества A и B не совпадают*/

Симметрическая разность – множество, чьи элементы принадлежат первому множеству и не принадлежат второму и наоборот.

Sim_minus(A,B,SM):–

minus(A,B,A_B), /* A_B — это разность

множеств A и B */

minus(B,A,B_A), /* B_A — это разность

множеств B и A */

union(A_B,B_A,SM). /* SM — это объединение

множеств A_B и B_A */

Дополнение. Для определенности, возьмем в качестве универсального множества множество цифр ({0,1,2,3,4,5,6,7,8,9}).

supp(A,D):–

U=[0,1,2,3,4,5,6,7,8,9],

minus(U,A,D). /* D — это разность

универсального множества U

и множества A */

Имея дополнение, можно выразить операцию объединения через пересечение и дополнение, или, наоборот, операцию пересечения через объединение и дополнение, используя законы де Моргана.

unionI(A,B,AB):–

supp(A,A_), /* A_ — это дополнение

множества A */

supp(B,B_), /* B_ — это дополнение

множества B */

intersection(A_,B_,A_B),

/* A_B — это пересечение

множеств A_ и B_ */

supp(A_B,AB). /* AB — это дополнение

множества A_B */

intersectionU(A,B,AB):–

supp(A,A_), /* A_ — это дополнение

множества A */

supp(B,B_), /* B_ — это дополнение

множества B */

union(A_,B_,A_B), /* A_B — это объединение

множеств A_ и B_ */

supp(A_B,AB). /* AB — это дополнение

множества A_B */