72982 ullman132 (2)

Krotka (1,2) występuje tutaj tylko jeden raz i krotka (3, 4) także. Dzieje się lak dlatego, że krotka (1,2) występuje w R 3 razy, a w S jeden raz, min (3. I) = 1, a więc w R r> S krotka (1,2) występuje 1 raz. Z kolei krotka (3, 4) w iloczynie R n .V występuje min(l, 2)    1 raz Natomiast krotka (5, 6)

W zbiorze R wcale nic występuje, a w zbiorze S jeden raz, więc w iloczynie RnS występuje min (0, 1) razy.

Operacje wiclozbiorowe w zastosowaniu do zbiorów

Załóżmy, że dane są dwa zbiory R i S Każdy z nich możemy traktować jako wiclozbiór, ale taki, w którym przypadkow-o wszystkie elementy występują tylko jednokrotnie. Przy obliczaniu przecięcia R n S korzystamy z właściwości przecięcia wielozbiorów. Ale wynik dostaniemy taki sam jak w przypadku, gdybyśmy traktow-ali R i S jako zbiory. Krotka l należy do wielozbiorów R i S tyle razy, ile wynosi minimum z liczb wystąpień w R i S. Ponieważ oba wielozbiory R i S są w tym przypadku zbiorami, więc l moż.e w każdym z nich wystąpić albo 0 razy, albo 1 raz. A więc stosując zarówno regułę przecięcia zbiorów, jak regułę przecięcia wiclozbio-rów, krotka \ może w wyniku przecięcia wystąpić co najwyżej jeden raz. a dokładnie raz. jeśli występuje równocześnie w R i S. Podobnie można przeanalizować wyniki obliczania różnicy wielozbiorów, gdy oba argumenty są zbiorami. Zarówno wartość R - S_t jak i S R jest taka sama, jak gdybyśmy stosowali regułę obliczania różnicy zbiorów.

Operacja sumy natomiast ma inne właściwości i stosowanie reguły sumowania wielozbiorów daje inny wynik niż stosowanie reguły sumowania zbiorów. Jeśli bowiem stosujemy regułę sumowania wielozbiorów, to nawet gdy oba argumenty są zbiorami, wynik nic musi być zbiorem. Dzieje się tak dlatego, że jeśli jakakolwiek krotka t występuje jednocześnie w obu zbiorach R i S, to w sumie Ru S wystąpi ona dwukrotnie, gdy stosuje się regułę sumowania w ielozbiorów. a tylko jeden raz, gdy zastosujemy regułę sumowania zbiorów. A więc przy obliczaniu sumy trzeba ściśle precyzować, czy chodzi o obliczanie sumy wielozbiorów, czy sumy zbiorów.

Różnica wielozbiorów R - S zawiera następujące krotki:

i

1

2

2

Aby przekonać się, dlaczego tak się dzieje, zauważmy, żc w relacji R krotka (1.2) występuje trzy razy i jeden raz w relacji S. a więc w relacji R - S wystąpi ona max(0, 3 - 1) - 2 razy. Z kolei krotka (3. 4) występuje w relacji R jeden raz, a w relacji S dwa razy, czyli liczba wystąpień w relacji R - S wynosi max(0. 1 - 2)    0. W relacji R nie ma innych krotek, więc w różnicy R S też

innych krotek nie ma.

Z kolei różnica S ■ R jest następującym wiclozbiorem:

A    B

3    4

5    6

Krotka (3.4) występuje tu jeden raz, co wynika z różnicy liczby wystąpień tej krotki w relacji S i liczby wystąpień w relacji R. /. tego samego powodu krotka (5, 6) w relacji S R występuje też jeden raz. W tym przypadku wiclozbiór jest zbiorem we właściwym sensie.

□

4.6.3. Rzutowanie wielozbiorów

Pokazaliśmy już rzutowanie wielozbiorów. Jak zobaczyliśmy w przykładzie 4.48. operacja rzutowania jest przeprowadzana niezależnie dla każdej krotki. Jeśli relacja R jest wiclozbiorem o wartościach występujących na rys. 4.29 i obliczymy rzutowanie wielozbiorów n_AJ^R), to otrzymamy wielo-zbiór z rys. 4.28.

Prawa algebry w przypadku wielozbiorów

Prawem algebraicznym nazywamy równoważność dwóch wyrażeń algebraicznych. w których relacje są oznaczane nazwami zmiennych. l aka równoważność oznacza, że relacje opisywane przez wyrażenia są równe, niezależnie od tego, jakie relacje wchodzą w skład wyrażeń. Dobrze zna nym przykładem prawa algebraicznego jest prawo przcmienności sumowania: R\j S= S R. Zachodzi ono niezależnie od tego, jakie elementy należą do relacji R i S, i niezależnie od tego, czy R i S są zbiorami czy wielozbiorami. Istnieją jednak takie prawa algebry' relacji, które są spełnione przez konwencjonalne relacje traktowane jako zbiory, a mogą nic być spełnione, gdy dopuścimy relacje w postaci wielozbiorów. Prostym przykładem jest w takim przypadku prawo rozdzielności różnicy wzglę dem sumy, czyli (/? u S) - T a (R - T) u (S - T). To prawo jest zawsze spełnione dla zbiorów, ale nie jest w ogólnym przypadku spełnione przez wielozbiory. Dlaczego nie zachodzi ono dla wielozbiorów? Załóżmy, że krotka / występuje jednokrotnie w każdym z wielozbiorów R, S i T. Wówczas w relacji opisanej w wyrażeniu po lewej stronie równoważności krotka / wy stępuje jeden raz. a w wyrażeniu po prawej wcale. Gdybyśmy operacje traktowali jako operacje na zbiorach, to krotka / nie wystąpiłaby w żadnym z tych dwóch wyrażeń. Ćwiczenia 4.6.4 i 4.6.5 dają możliwość uzyskania większej praktyki w korzystaniu z praw algebraicznych dla wielozbiorów.