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

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

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

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

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

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

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

• Список, определяющий первое множество Х можно разделить на голову Н и хвост 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]. успех.

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

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

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

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

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

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

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

• Список, определяющий первое множество Х можно разделить на голову Н и хвост 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])) неуспех⁴

Возврат.

Пр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]. успех.