Алгоритм вычисления объединения множеств.

Вход: А и В – представлены упорядоченными списками

Выход: С=А È В.

pa:=a, pb:=b, c=nil, e=nil.

while pa=nil and pb¹nil do

if pa.i<pb.i then

d:=pa.i, pa:=pa.n

else if pa.i>pb.i then

d=pb.i, pb:=pb.n

else

d:=pa.i

pa:=pa.n,pb=pb.n

end if

Append(c,e,d)//процедура добавления

end while

p:=nil

if pa ¹nil then

p:=pa

end if

if pb ¹nil then

p:=pb

end if

while p ¹nil do

Append(c,e,p.i)

p:=p.n

endwhile.

 

На каждом шаге основного цикла происходит добавление элемента одного из множеств в результирующее множество.

Процедура Append добавляет элемент d в конец списка с.

 

Append(c,e,d)

Вход: указатель С на первый элемент списка

Выход: список

q=new(elem)

q.i=d, q.n=nil

if c=nil then

c:=q

else e.n=q

end if

e:=q.

Алгоритм вычисления пересечения множеств.

Вход: А и В – представлены упорядоченными списками

Выход: С=АÇВ

pa:=a, pb:=b, c:=nil, e:=nil

while pa¹nil and pb¹nil do

if pa.i<pb.i tne

pa:=pa.n

else if pa.i>pb.i then

pb:=pb.n

else Append (c,e,pa.i);

pa:=pa.n, pb:=pb.n

end if

end while.

 

Append(c,e,d)

Вход: указатель С на первый элемент списка

Выход: список

q=new(elem)

q.i=d, q.n=nil

if c=nil then

c:=q

else e.n=q

end if

e:=q.

Упорядоченное множество. Прямое произведение множеств.

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

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

Число элемента кортежа – длина кортежа.

а= (а_1,а_2,а_3,…а_n)

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

Пустой кортеж задается условием: кортеж а = кортежу b, если элементы одного кортежа соответственно должны равняться другому кортежу.

а=bÞa₁=b₁, a₂=b₂… a_n=b_n

а= {а_1,а_2,а_3,…а_n}

b= {b_1,b_2,b_3…b_n}

Прямое произведение множеств

Пусть а и b - два множества,

прямым произведением (декартовым произведением) 2 множеств а и b называется множество упорядоченных пар, принадлежащих множеству А, второй – множеству В.

А´В={(a,b)ïaÎA, bÎB}

X:{1,2}

Y:{3,4}

X´Y={(1,3), (1,4), (2,3), (2,4)}

Метод координат ввел Рене Декарт. отсюда и возникло название декартовое произведение.

Степенью множества А называется его прямое произведение самого на себя

Аⁿ=A´A´A´…´A(n-раз)

Отношения. Композиция отношений.

Элементы множеств могут находиться в некоторых отношениях друг с другом и с элементами других множеств.

Отношения между парами объектов называется бинарными отношениями.

аÎА АÌВ

В общем виде отношение можно записать след. образом: хАу, где х, у – элементы, которые находятся в отношении. А – отношение.

Бинарным отношением R из множества А в множество В называется подмножество прямого произведения множества А и В.

R ÌA´B

Для бинарных отношений обычно используется инфиксная запись, когда отношение расположено между операндами: aRb:={(a,b)ïRÌA´B, aÎA, bÎB}

Префиксная запись: R(a,b)

Постфиксная запись: (a,b)R

Если А=В, то говорят, что R – это отношения на множестве А.

Обратным отношением называется отношение: R^-1:={ (a,b)ï(b,a) ÎR}

Дополнением к отношению: :={(a,b) ï(a,b)ÏR}

Тождественное отношение: I:= {(a,a) ïaÎA}

Универсальное отношение: U:={(a,b) ï aÎA, bÎB }

Обобщенное понятие «отношение» - это n-местное отношение R, которое состоит из кортежей, у которых a₁ÎA₁ a₂ÎA₂… a_nÎA_n

RÌA₁´A₂´…´A_n={a_1,a_2…a_nï a₁ÎA₁ a₂ÎA₂… a_nÎA_n }

Композиция отношений задается след. образом:

пусть R₁ÌA´B, R₂ÌB´C

Композицией R₁ и R₂ называется отношение R ÌA´С

R:={(a,c) ïaÎA, cÎC и $ bÎB, aRb и bRc}

Степенью отношения на множестве А называется его композиция с самим собой n-раз. Rⁿ=RR...R(n-раз)