Вы на НеОфициальном сайте факультета ЭиП

На нашем портале ежедневно выкладываются материалы способные помочь студентам. Курсовые, шпаргалки, ответы и еще куча всего что может понадобиться в учебе!
Главная Контакты Карта сайта
 
Где мы?

Реклама


1. 5 Алгебра множеств

Просмотров: 4688 Автор: Angel
1. 5 Алгебра множеств

Две бинарные операции (? и ?) и одна унарная операция (? ), заданные на булеане универсального множества P (U), формируют алгебру множеств, т. е.
Aмнож.=,
где ?(U) – носитель алгебры,
  ?={?; ?; ?} сигнатура алгебры, где ? символ унарной операции –дополнения, ? символ бинарной операции – объединения, ? символ бинарной операции пересечения. 

Непосредственно из определения граней упорядоченного множества подмножеств следуют основные законы алгебры множеств:

• коммутативности: (A?B)=(B?A) и (A?B)=(B?A);
• ассоциативности: A?(B?C)=(A?B)?C и A?(B?C)=(A?B)?C;
• идемпотентности: A?A=A и A?A=A;
• поглощения: A?(A?B)=A и A?(A?B)=A;
• дистрибутивности: A?(B?C)=(A?B)?(A?C) и ?(B?C)=(A?B)?(A?C);
• “третьего не дано” A??A=U;
• противоречия: A??A=?.
• двойного отрицания: ? (?A)=A.

Рассмотрим исполнение отдельных операций над подмножествами A, B, C множества P (U). 

Для изображения исполнения отдельных операций обозначим прямоугольником универсальное множество U, а внутри него кругами подмножества A, B и C. 
Заштрихованная область будет представлять результат исполнения операции. Такое изображение называют кругами Эйлера.

Объединение множеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному множеству А или В, т.е. С=(А?В)={x| x?A или x?B}.  

Операторная запись объединения имеет вид: С=union(A, B).
Если В=?, то А?В=А??=А.
Если B=U, то А?В=А?U=U. 
Если А?С и В?С, то А?В?С.

Рис. 2 Объединение множеств A и B.

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

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

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

Пример: Пусть даны отображения h1 и h2, представляющие множества совместимых кортежей. Найти h=(h1?h2).
Если все компоненты двух совместимых кортежей имеют одинаковые значения, т.е. (y(1)=y(2), x1(1)=x1(2), x2(1)=x2(2),..xn(1)=xn(2)), то в результате исполнения этой операции формируется один кортеж (y, x1, x2, ..xn), при различии хотя бы одной компоненты совместимых кортежей в результате исполнения этой операции формируются два кортежа (y(1), x1(1), x2(1),..xn(1)) и (y(2), x1(2), x2(2),..xn(2)). 
В таблицу h войдут все кортежи h1={(2, b, c, 6), (3, c, e, 5), (5, c, b, 2), (4, a, e, 5)} и те кортежи h2, которых нет в h1, т. е. {(3, c, e, 2) и (2, a, e, 6)}.

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 5 c b 2
 4 a e 5 2 a e 6 4 a e 5
  3 c e 2
  2 a e 6


Пример: Пусть даны отношения r1 и r2. Найти r=(r1?r2).
Особенность исполнения этой операции состоит в том, что
Поэтому операция r=(r1?r2) выполняется для каждой пары (xi, xj), входящей в r1 и r2, по правилу дизъюнкции: 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 1 1 1 
x2 0 1 0 1 ? x2 1 1 0 0 = x2 1 1 0 1 
x3 1 0 1 0 x3 0 1 1 0 x3 1 1 1 0 
x4 0 1 1 1 x4 0 0 0 0 x4 0 1 1 1 
Операцию объединения можно распространить на произвольное число подмножеств универсального множества U. 
Например, если А1;А2;...;Аn?U, то А1?А2?...?Аn=i=1?Аn?U.


 Пересечение множеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат множеству А и принадлежат множеству В, т.е. (А?В)={x|x?A и x?B}. 
Операторная запись имеет вид: С=intersection(A,B). 
Если В=?, то А?В=А??=?. 
Рис. 3 Пересечение множеств A и B. Если B=U, то А?В=А?U=А.

Если С?А и С?В, то С?А?В. Если А?? и В??, то при А?В=? множества A и B не имеют общих элементов.

Пример: Пусть A={a, b, c}, B={b, c, d, e}. Найти C= (А?В).
 C={b, c}, т. к. b, c?A и B. 

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

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

Пример: Пусть даны отображения h1 и h2, представляющие множества совместимых кортежей. Найти h=(h1?h2).
Если все компоненты двух совместимых кортежей имеют одинаковые значения, т.е. (y(1)=y(2);x1(1)=x1(2);x2(1)=x2(2);...xn(1)=xn(2)), то в результате исполнения этой операции формируется один кортеж (y;x1;x2;...xn), при различии хотя бы одной компоненты совместимых кортежей в результате исполнения этой операции формируются пустой кортеж. 
В h войдут только кортежи (5, c, b, 2), (4, a, e, 5), которые принадлежат 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 = 5 c b 2
 3 c e 5 5 c b 2 4 a 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, по правилу конъюнкции: 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 1 1 1 1 x1 1 0 0 0 
x2 0 1 0 1 ? x2 1 1 0 0 = x2 0 1 0 0 
x3 1 0 1 0 x3 0 1 1 0 x3 0 0 1 0 
x4 0 1 1 1 x4 0 0 0 1 x4 0 0 0 1 

Дополнение множества А есть множество, состоящее из всех тех элементов, которые принадлежат универсальному множеству U и не принадлежат множеству А, т.е.?А={x| x?U и x?A}.  

Операторная запись дополнения имеет вид: ?А=complement(A).
Рис.4 Дополнение множества А

Если существует?А, то справедливы следующие соотношения: А??А=?, А??А=U и ?(?А)=А. 

Пример: Пусть дано множество A={a, b, c}и универсальное множество U={a, b, c, d, e, f}. Найти C=?А. C={d, e, f}. 

Пример: Пусть дано множество A={{a, b}, c} и универсальное множество U={a, b, {a, b}, c, {d, e}, f}. Найти C=?А. 
C={a, b, {d, e}, f}.

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

Пример: Пусть дано отображение h. 
Для поиска ?h необходимо найти множество кортежей, совместимых с кортежами h, но отличающихся значением хотя бы одной компонентой. Для этого определяют число элементов n области определения h и число компонент k. 
Тогда |?h|=n?(n1)?(n2)?..?(nk+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?В}, где “\” символ разности.
Рис. 5 Разность множеств A и B.
Операторная запись разности имеет вид: С=difference(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 


Симметрическая разность множеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат разности (А\В) или (В\А).

 Симметрическую разность множеств (“?”) также можно исполнить, опираясь только на основные операции объединения, пересечения и дополнения по правилу: С=(А?В)=(А??В)?(В??А)={x|x?(A\В) или x?(B\А)}.
Операторная запись имеет вид: С:=union(difference(A, B), difference(B, A)). 

Следует обратить внимание, что если (А?В)=(А??В)?(В??А)=?, то А=В. Это правило будет часто использоваться при доказательстве тождеств и поиске неизвестных множеств.
Рис.6 Симметрическая разность множеств A и B.

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

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

 Пример: Пусть даны множества несовместимых кортежей A={(a,b), (b, c)}, B={(b, c), (b, c, d), (c, d)}. Найти C= (А?В).
C={(a, b), (b, c, d), (c, d)}, т. к. кортеж (b, c)?A, 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 3 c e 2
 4 a e 5 2 a e 6 2 a e 6
В таблицу h не вошли кортежи (5, c, b, 2) и (4, a, e, 5)}, которые принадлежат h1 и h2.

Пример: Пусть даны отношения r1 и r2. Найти r=(r1?r2).
Особенность исполнения этой операции состоит в том, что операция r=(r1?r2) выполняется для каждой пары (xi, xj), входящей в r1 и r2, по правилу:
r(xi, xj)=(r1(xi, xj) ??r2(xi, xj))?r2(xi, xj) ??r1(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 1 1 1 
x2 0 1 0 1 ? x2 1 1 0 0 = x2 1 0 0 1 
x3 1 0 1 0 x3 0 1 1 0 x3 1 1 0 0 
x4 0 1 1 1 x4 0 0 0 0 x4 0 1 1 1 


Информация

Комментировать статьи на нашем сайте возможно только в течении 60 дней со дня публикации.

Популярные новости

Статистика сайта



Rambler's Top100



 
Copyright © НеОфициальный сайт факультета ЭиП