Множества и их представление на языке Пролог. Простые программы обработки множеств.

5.5.1 Основные определения.

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

5.5.2 Предикат unionset.

Предикат unionset определяет операцию объединения двух множеств. Объединением двух множеств X и Y является множество Z, состоящее из элементов, которые принадлежат или множеству X, или множеству Y, или обоим множествам одновременно.

Предикат unionset(X,Y,Z) ¾истинен, если множество Z является объединением множеств X и Y. Схема отношения этого предиката имеет вид:

unionset(<список>,<список>,<список>).

Декларативное описание предиката unionset(X,Y,Z)формулируется следующим образом:   

v Объединение пустого множества с непустым множеством Х есть множество Х.

v Список, определяющий первое множество Х можно разделить на голову Н и хвост Xs. Если голова первого списка Н принадлежит второму списку Y, то рекурсивно вызывается процедура unionset с аргументами Xs и Y. При этом терм H в результирующий список не помещается.

v Список, определяющий первое множество Х можно разделить на голову Н и хвост Xs. Если голова первого списка Н не принадлежит второму списку Y, то рекурсивно вызывается процедура unionset с аргументами Xs и Y. При этом терм H помещается в результирующий список.

 Процедура unuonset(X,Y) состоит из трех правил:

unionset([],X,X).
    unionset([H|Xs],Y,Z):-member(H,Y),!,unionset(Xs,Y,Z).

unionset([H|Xs],Y,[H|Z]):-unionset(Xs,Y,Z).

Процедура unionset выполняется следующим образом:

? ¾ unionset([a,b,c],[d,a,b,f],Z).                                            

ТР: unionset([a,b,c],[d,a,b,f],Z).                                            

Шаг 1: ТЦ: unionset([a,b,c], [d,a,b,f] ,Z).                                            

Пр1: [a,b,c] =[] Þ неуспех (списки разной длины)

Пр2: unionset([a|[b,c]],[d,a,b,f],Z):-member(a,[d,a,b,f]),!,unionset([b,c], [d,a,b,f],Z).

ТР: member(a,[d,a,b,f]),!,unionset([b,c],[d,a,b,f],Z).

Шаг 2: ТЦ: member(a,[d,a,b,f]) Þ успех[3]

ТР: unionset([b,c],[d,a,b,f],Z1).

Шаг 3: ТЦ: unionset([b,c],[d,a,b,f],Z).

Пр1: [b,c] =[] Þ неуспех (списки разной длины)

Пр2: unionset([b|[c]],[d,b,a,f],Z):-member(b,[d,a,b,f]),!,unionset([c],[d,a,b,f],Z).

ТР: member(b,[d,a,b,f]),!,unionset([c],[d,b,a,f],Z).

Шаг 4: ТЦ: member(b,[d,a,b,f]) Þ успех

ТР: unionset([c],[ d,a,b,f],Z).

Шаг 5: ТЦ: unionset([c],[ d,a,b,f ],Z).

Пр1: [c] =[] Þ неуспех (списки разной длины)

Пр2: unionset([c|[]],[d,a,b,f],Z):-member(c,[d,a,b,f]),!,unionset([],[d,a,b,f],Z).

ТР: member(c,[d,a,b,f]),!,unionset([],[d,a,b,f ],Z).

Шаг 6: ТЦ: member(с,[d,a,b,f]) Þ неуспех

Возврат.

Пр3: unionset([c|[]],[ d,a,b,f ],[c|Z1]):- unionset([],[d,a,b,f ],Z1).

Z=[c|Z1]

ТР: unionset([],[d,a,b,f ],Z1).

Шаг 7: ТЦ: unionset([],[d,a,b,f ] ,Z1).

Пр1: [] =[] Þ успех при подстановке Z1=[d,a,b,f ].

Выход из рекурсии на шаг 6, получается подстановка Z=[c|Z1] или Z=[c,d,a,b,f].

Выход из рекурсии на шаг 5, Z=[c,d,a,b,f].

Выход из рекурсии на шаг 3, Z=[c,d,a,b,f].

Выход из рекурсии на шаг 1, Z=[c,d,a,b,f].

ТР: ÿ ¾успех.

Результат вычисления запроса Z=[c,d,a,b,f].Þ успех.

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

Предикат interset определяет операцию пересечения двух множеств. Пересечением двух множеств X и Y является множество Z, состоящее из элементов, которые принадлежат и множеству X, и множеству Y одновременно.

Предикат interset (X,Y,Z) ¾истинен, если множество Z является пересечением множеств X и Y. Схема отношения этого предиката имеет вид:

interset(<список>,<список>,<список>).

Декларативное описание предиката interset(X,Y,Z)формулируется следующим образом:   

v Пересечение пустого множества с непустым множеством Х есть пустое множество.

v Список, определяющий первое множество Х можно разделить на голову Н и хвост Xs. Если голова первого списка Н принадлежит второму списку Y, то рекурсивно вызывается процедура interset с аргументами Xs и Y. При этом терм H помещается в результирующий список.

v Список, определяющий первое множество Х можно разделить на голову Н и хвост Xs. Если голова первого списка Н не принадлежит второму списку Y, то рекурсивно вызывается процедура interset с аргументами Xs и Y. При этом терм H в результирующий список не помещается.

 Процедура interset(X,Y,Z) состоит из трех правил:

interset([],X,[]).
    interset([H|Xs],Y, [H|Z]):-member(H,Y),!,interset(Xs,Y,Z).

interset([H|Xs],Y,Z):-interset(Xs,Y,Z).

Процедура interset выполняется следующим образом:

? ¾ interset([a,b,c],[d,a,b,f],Z).                                            

ТР: interset([a,b,c],[d,a,b,f],Z).                                            

Шаг 1: ТЦ: interset([a,b,c], [d,a,b,f] ,Z).                                            

Пр1: [a,b,c] =[] Þ неуспех (списки разной длины)

Пр2: interset([a|[b,c]],[d,a,b,f],[a|Z1]):-member(a,[d,a,b,f]),!,interset([b,c], [d,a,b,f],Z1).

при этом Z=[a|Z1]

ТР: member(a,[d,a,b,f]),!,interset([b,c],[d,a,b,f],Z).

Шаг 2: ТЦ: member(a,[d,a,b,f]) Þ успех

ТР: interset([b,c],[d,a,b,f],Z1).

Шаг 3: ТЦ: interset([b,c],[d,a,b,f],Z1).

Пр1: [b,c] =[] Þ неуспех (списки разной длины)

Пр2: interset([b|[c]],[d,b,a,f],[b|Z2]):-member(b,[d,a,b,f]),!,interset([c],[d,a,b,f],Z2).

при этом Z1=[b|Z2]

ТР: member(b,[d,a,b,f]),!,interset([c],[d,b,a,f],Z2).

Шаг 4: ТЦ: member(b,[d,a,b,f]) Þ успех

ТР: interset([c],[ d,a,b,f],Z2).

Шаг 5: ТЦ: interset([c],[ d,a,b,f ],Z2).

Пр1: [c] =[] Þ неуспех (списки разной длины)

Пр2: interset([c|[]],[d,a,b,f],[c|Z3]):-member(c,[d,a,b,f]),!,interset([],[d,a,b,f],Z3).

ТР: member(c,[d,a,b,f]),!,interset([],[d,a,b,f ],Z3).

Шаг 6: ТЦ: member(с,[d,a,b,f]) Þ неуспех

Возврат.

Пр3: interset([c|[]],[ d,a,b,f ],Z2):- interset([],[d,a,b,f ],Z2).

ТР: interset([],[d,a,b,f ],Z2).

Шаг 7: ТЦ: interset([],[d,a,b,f ] ,Z2).

Пр1: [] =[] Þ успех при подстановке Z2=[].

Выход из рекурсии на шаг 3, Z1=[b|Z2] или Z1=[b].

Выход из рекурсии на шаг 1, Z=[a|Z1] или Z=[a|[b]] или Z=[a,b].

ТР: ÿ ¾успех.

Результат вычисления запроса Z=[a,b].Þ успех.

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

Предикат difset определяет операцию разности двух множеств. Разностью двух множеств X и Y является множество Z, состоящее из элементов, которые принадлежат множеству X, но не принадлежат множеству Y.

Предикат difset (X,Y,Z) ¾истинен, если множество Z является разностью множеств X и Y. Схема отношения этого предиката имеет вид:

difset(<список>,<список>,<список>).

Декларативное описание предиката difset(X,Y,Z)формулируется следующим образом:   

v Разность пустого множества и непустого множеством Х есть пустое множество.

v Список, определяющий первое множество Х можно разделить на голову Н и хвост Xs. Если голова первого списка Н не принадлежит второму списку Y, то рекурсивно вызывается процедура difset с аргументами Xs и Y. При этом терм H помещается в результирующий список.

v Список, определяющий первое множество Х можно разделить на голову Н и хвост Xs. Если голова первого списка Н принадлежит второму списку Y, то рекурсивно вызывается процедура difset с аргументами Xs и Y. При этом терм H в результирующий список не помещается.

 Процедура difset(X,Y,Z) состоит из трех правил:

difset([],X,[]).
    difset([H|Xs],Y, [H|Z]):-not(member(H,Y)),!,difset(Xs,Y,Z).

difset([H|Xs],Y,Z):-difset(Xs,Y,Z).

Процедура difset выполняется следующим образом:

? ¾ difset([a,b,c],[d,a,b,f],Z).                                            

ТР: difset([a,b,c],[d,a,b,f],Z).                                        

Шаг 1: ТЦ: difset([a,b,c], [d,a,b,f] ,Z).                                            

Пр1: [a,b,c] =[] Þ неуспех (списки разной длины)

Пр2: difset([a|[b,c]],[d,a,b,f],[a|Z1]):-not(member(a,[d,a,b,f])),!,difset([b,c], [d,a,b,f],Z1).

при этом Z=[a|Z1]

ТР: not(member(a,[d,a,b,f])),!,difset([b,c],[d,a,b,f],Z).

Шаг 2: ТЦ: not(member(a,[d,a,b,f])) Þнеуспех[4]

Возврат.

Пр3: difset([a|[b,c]],[d,a,b,f],Z):-difset([b,c], [d,a,b,f],Z).

ТР: difset([b,c],[d,a,b,f],Z).

Шаг 3: ТЦ: difset([b,c],[d,a,b,f],Z).

Пр1: [b,c] =[] Þ неуспех (списки разной длины)

Пр2: difset([b|[c]],[d,b,a,f],[b|Z1]):-not(member(b,[d,a,b,f])),!,difset([c],[d,a,b,f],Z1).

при этом Z=[b|Z1]

ТР: not(member(b,[d,a,b,f])),!,difset([c],[d,b,a,f],Z1).

Шаг 4: ТЦ: not(member(b,[d,a,b,f])) Þ неуспех

Возврат.

Пр3: difset([b|c]],[d,a,b,f],Z):-difset([c], [d,a,b,f],Z).

ТР: difset([c],[ d,a,b,f],Z).

Шаг 5: ТЦ: difset([c],[ d,a,b,f ],Z).

Пр1: [c] =[] Þ неуспех (списки разной длины)

Пр2: difset([c|[]],[d,a,b,f],[c|Z1]):-not(member(c,[d,a,b,f])),!,difset([],[d,a,b,f],Z1).

при этом Z=[c|Z1]

ТР: not(member(c,[d,a,b,f])),!,difset([],[d,a,b,f ],Z2).

Шаг 6: ТЦ: not(member(с,[d,a,b,f])) Þ успех

Шаг 7: ТЦ: difset([],[d,a,b,f ] ,Z1).

Пр1: [] =[] Þ успех при подстановке Z1=[].

Выход из рекурсии на шаг 5, Z=[c|Z2] или Z=[c].

Выход из рекурсии на шаг 3, Z=[c].

Выход из рекурсии на шаг 1, Z=[c].

ТР: ÿ ¾успех.

Результат вычисления запроса Z=[c].Þ успех.

5.5.5. Определение подмножества.

Предикат subset определяет, является ли множество подмножеством другого множества. Множество X является подмножеством множества Y, если все элементы X, принадлежат множеству Y.

Предикат subset(X,Y) ¾истинен, если множество X является подмножеством Y. Схема отношения этого предиката имеет вид:

subset(<список>,<список>).

Декларативное описание предиката subset(X,Y)формулируется следующим образом.   

v Пустое множество является подмножеством любого множества.

v Список, определяющий первое множество Х можно разделить на голову Н и хвост Xs. Множество X есть подмножество Y, если голова первого списка Н принадлежит второму списку Y и Xs есть подмножество множества Y.

 Процедура subset(X,Y) состоит из двух правил:

subset([],Y).
    subset([H|Xs],Y):-member(H,Y),subset(Xs,Y).

Рассмотрим пример запроса к процедуре subset.

Процедура subset выполняется следующим образом:

? ¾ subset([a,b,c],[d,a,b,c,f]).                                            

ТР: subset([a,b,c],[d,a,b,c,f]).                                            

Шаг 1: ТЦ: subset([a,b,c], [d,a,b,c,f]).                                        

Пр1: [a,b,c] =[] Þ неуспех (списки разной длины)

Пр2: subset([a|[b,c]],[d,a,b,c,f]):-member(a,[d,a,b,f])subset([b,c], [d,a,b,c,f]).

ТР: member(a,[d,a,b,c,f])),subset([b,c],[d,a,b,c,f]).

Шаг 2: ТЦ: member(a,[d,a,b,c,f]) Þуспех[5]

ТР: subset([b,c],[d,a,b,c,f]).

Шаг 3: ТЦ: subset([b,c],[d,a,b,c,f]).

Пр1: [b,c] =[] Þ неуспех (списки разной длины)

Пр2: subset([b|[c]],[d,a,b,c,f]):-member(b,[d,a,b,c,f]))subset([c],[d,a,b,c,f]).

ТР: member(b,[d,a,b,c,f])),subset([c],[d,b,a,c,f]).

Шаг 4: ТЦ: member(b,[d,a,b,c,f]) Þ успех

ТР: subset([c],[ d,a,b,f],Z).

Шаг 5: ТЦ: subset([c],[ d,a,b,c,f ]).

Пр1: [c] =[] Þ неуспех (списки разной длины)

Пр2: subset([c|[]],[d,a,b,f],[c|Z1]):-member(c,[d,a,b,c,f])),subset([],[d,a,b,c,f]).

ТР: member(c,[d,a,b,c,f])),subset([],[d,a,b,c,f ]).

Шаг 6: ТЦ: member(с,[d,a,b,f,c]) Þ успех

Шаг 7: ТЦ: subset([],[d,a,b,f ] ).

Пр1: [] =[] Þ успех.

Выход из рекурсии на шаг 5.

Выход из рекурсии на шаг 3.

Выход из рекурсии на шаг 1.

ТР: ÿ ¾успех.

Результат вычисления запроса Þ успех.