Дискретная математика: Учебное пособие. Часть I - Основания дискретной математики, страница 11


Особенность исполнения этой операции состоит в том, что значения r(xi; xj) также принадлежат двухэлементному множеству {0; 1}. Поэтому для r(xi;xj)=1 значение r(xi;xj)=0, а для r(xi;xj)=0 значение`r(xi;xj)=1.

Пример: Пусть дано отображение h.

Подпись: ùh	Iy	Ix1	Ix2			
	a1	c1	d1			
	a1	c1	d2			
	a1	c1	d3			
	a1	c2	d2			
	a2	c1	d2			
	a2	c1	d3			
	a2	c2	d1			
	a2	c2	d2			
	a2	c2	d3			
	a3	c1	d1			
	a3	c1	d3			
	a3	c2	d1			
	a3	c2	d2			
	a3	c2	d3			

Подпись: h	Iy	Ix1	Ix2
	a1	c2	d3
	a2	c1	d1
	a3	c1	d2
	a1	c2	d1

Для поиска ùh необходимо найти множество кортежей, совместимых с кортежами h, но отличающихся значением хотя бы одной компонентой. Для этого определяют число элементов n  области определения h  и число компонент k.

Тогда |ùh|=n×(n-1)×(n-2)×..×(n-k+1) -|h|.

Для h, представленной на таблице, имеем n=|Iy|+|Ix1|+|Ix2|=3+2+3=8 и k=3. Тогда |ùh|=8×7×6 – 4 =332,

 т. е. таблица  ùh должна содержить 332 кортежа. Однако, если принять, что значения компонент кортежей не выходят за пределы своего атрибута, т. е. |Iy|=3, |Ix1|=2, |Ix2|=3, то |ùh |=3×2×3 – 4=14.

          Пример: Пусть дано множество кортежей A={(a,b),

(b, c)} и универсальное множество U={(b, c), (b, c, d), (c, d), (a,b)}. Найти C=ùА.

C={(b, c, d,), (c, d)}.

Операции дополнения, пересечения и объединения формируют две дополнительные операции: разности и симметрической разности.

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

С=(А\В)= {x|xÎА и xÏВ}, где “\” - символ разности.

Операторная запись разности имеет вид: С=difference(A, B).                                        Рис. 5 Разность множеств A и B.

Исполнение этой операции можно реализовать с помощью основных операций конъюнкции множества A с дополнением множества B,

 т. е.С=(А\В)=(АÇ(ùВ)).

Пример: Пусть даны множества A={a, b, c}, B={b, c, d, e}. Найти C= (А\В).

C={a}, т.к. элементы b, сÎB.

Пример: Пусть даны множества A и B, которым принадлежат подмножества A={{a, b}, c}, B={{b, c, d}, c, d}. Найти C= (А\В).

C={a, b}, т.к. элемент сÎB.     

Пример: Пусть даны множества несовместимых кортежей A={(a,b), (b, c)}, B={(b, c), (b, c, d), (c, d)}. Найти C= (АÈВ).

C={(a, b)}, т. к. кортеж (b, c)ÎB.

Пример: Пусть даны отображения h1 и h2. Найти h=(h1\h2).

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

h1

y

x1

x2

x3

\

h2

y

x1

x2

x3

=

h=(h1\h2)

y

x1

x2

x3

2

b

c

6

3

c

e

2

2

b

c

6

3

c

e

5

5

c

b

2

3

c

e

5

5

c

b

2

4

a

e

5

 

4

a

e

5

2

a

e

6

 

Пример: Пусть даны отношения r1 и r2. Найти r=(r1\r2).

Особенность исполнения этой операции состоит в том, что
операция r=(r1\r2) выполняется для каждой пары (xi, xj), входящей в r1 и r2, по правилу конъюнкции r1(xi, xj) и `r2(xi, xj), т. е.
 r(xi, xj)=(r1(xi, xj)×`r2(xi, xj)).


r1

x1

x2

x3

x4

r2

x1

x2

x3

x4

r=(r1\r2)

x1

x2

x3

x4

x1

1

0

0

0

x1

0

1

1

1

x1

1

0

0

0

x2

0

1

0

1

\

x2

1

1

0

0

=

x2

0

0

0

1

x3

1

0

1

0

x3

0

1

1

0

x3

1

0

0

0

x4

0

1

1

1

x4

0

0

0

0

x4

0

1

1

1