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

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

Решение, как обычно, будет рекурсивным. Базис рекурсии будет представлен фактом, утверждающим, что пустое множество является подмножеством любого множества. Шаг рекурсии: чтобы одно множество было подмножеством другого, нужно, чтобы его первый элемент принадлежал второму множеству (проверить это нам позволит предикат member3, рассмотренный нами ранее), а его хвост, в свою очередь, должен быть подмножеством второго множества. Этих рассуждений достаточно, чтобы записать предикат, реализующий операцию включения.

subset([],_).

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

subset([H|T],S):-

/* множество [H|T] является подмножеством множества S */

member3(H,S),

/* если его первый элемент H принадлежит S */

subset(T,S).

/* и его хвост T является подмножеством множества S */

Пример 10.6. Предикат, реализующий отношение равенства двух множеств.

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

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

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

?- equal([1,2,3] и множество [3,4,5]).

No

?- equal([1,2,3] и [2,1,3]).

No

Пример 10.7. Определение собственного подмножества множества

Prop_subset(A,B):-

subset(A,B),

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

not(equal(A,B)).

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

?- prop_subset([1,3], [1,2,3])

Yes

?- prop_subset([1,4], [2,1,3])

No

Пример 10.8. Симметричная разность

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

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 */

Убедимся, что симметрическая разность множеств [1,2,3,4] и [3,4,5] равна множеству [1,2,5], а симметрическая разность множеств [3,4,5] и [1,2,3,4] равна множеству [5,1,2]. Множество [1,2,5] с точностью до порядка элементов совпадает с множеством [5,1,2]. Таким образом, мы выяснили, что результат не зависит от порядка аргументов.

Пример 10.9. Дополнение множества

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

supp(A,D):-

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

minus(U,A,D).

/* D — это разность универсального множества U и множества A */

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

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 */