« poprzedni punkt | następny punkt » |
Definicja 1.6
Różnicą zbiorów A i B nazywamy zbiór A\B, którego elementami są te elementy zbioru A, które nie są elementami zbioru B:
x Î A\B wttw x Î A i x Ï B
Definicję powyższą można też krótko zapisać w postaci A\B = { x Î A : x Ï B}( por Rys. 1.7)
Rys. 1.7
Z rysunku wynika natychmiast, że A\B jest podzbiorem zbioru A dla dowolnych zbiorów A i B. Ponadto, jeśli zbiory A i B są rozłączne, to A\B jest identyczne z A.
Przykład 1.8
(a) Niech A = {1, 2, 3, 4, 5, 6} i B={2i+1 Î N : i <5}. Wtedy A\B = {2, 4, 6}, a B\A = {7, 9}.
(b) Niech Q oznacza zbiór wszystkich liczb wymiernych. Wtedy R\Q jest zbiorem liczb niewymiernych.
Z przyjętej definicji różnicy wynika, że x Ï A\B wtedy i tylko wtedy, gdy któryś z warunków "x Î A" lub "x Ï B" nie jest spełniony. Zatem
x Ï A\B wttw x Ï A lub x Î B
Następujący lemat ustala związek między inkluzją, a różnicą zbiorów. W szczególności wynika z niego powszechnie znane prawo: "jeśli odejmiesz więcej to pozostanie mniej".
Lemat 1.5
Dla dowolnych zbiorów A, B, C, D, jeśli A Í B i C Í D, to A\D Í B\C.
Dla dowodu tej zależności, załóżmy, że A Í B i C Í D i rozważmy dowolny element x Î A\D. Wtedy x Î A i xÏ D.
Skoro xÎ A, to x Î B, bo A Í B.
Skoro xÏ D, to x Ï C, bo C Í D.
Mamy więc ostatecznie, x Î B i x Ï C, co oznacza, że x Î B\C.J
Do najważniejszych praw rachunku zbiorów należą zależności wiążące sumę, różnicę i iloczyn zbiorów, zwane prawami de Morgana.
Twierdzenie 1.3
Dla dowolnych zbiorów A, B, C zachodzą równości (prawa de Morgana):
Dowód.
Przedstawimy dowód pierwszego prawa De Morgana.
1. Jeśli x Î (A \ B) Ç (A \ C), to x Î A oraz x Ï B i x Ï C. Stąd x Î A i x Ï (B È C), czyli x Î A \ (B È C). Wykazaliśmy tym samym zawieranie (A \ B) Ç (A \ C) Í A \ (B È C).
W dowodzie implikacji odwrotnej wykorzystamy udowodnione wcześniej prawa rachunku zbiorów.
Ponieważ B Í (B È C) i C Í (B È C), zatem na mocy lematu 1.5 mamy A \ (B È C) Í (A \ B) i A \ (B È C) Í (A \ C) . Stąd na mocy lematu 1.4 mamy A \ (B È C) Í (A \ B) Ç (A \ C).
2. Zamiast dowodu, lewą i prawą stronę drugiej z równości zilustrujemy, przy pomocy diagramów Venna (por. Rys. 1.8). Dowody przy pomocy diagramów Venna są bardzo intuicyjne i przez to łatwiejsze, i chociaż nie do końca opisują szczegóły rozumowania, będziemy je czasami przedstawiać.J
Rys. 1.8 Ilustracja graficzna prawa A \ (B Ç C) = (A \ B) È (A \ C).
Bardzo często, rozważane w zastosowaniach zbiory, są same podzbiorami jakiegoś jednego większego zbioru. Po prostu w swoich rozważaniach ograniczmy się tylko do elementów pewnego zbioru. Zbiór ten będziemy nazywać przestrzenią lub uniwersum. Jeśli U jest takim zbiorem i rozważamy tylko jego podzbiory, to różnicę U\A nazywamy uzupełnieniem zbioru A w uniwersum U i oznaczamy przez -A lub Ac (od angielskiego słowa complement).
Prawa de Morgana zapisane dla operacji uzupełnienia przyjmują postać:
- (A È B) = (- A) Ç (- B)
- (A Ç B) = (- A) È (- B)
Powyższe równości zachodzą dla dowolnych zbiorów A, B, będących podzbiorami tego samego uniwersum U. Czytamy: uzupełnienie sumy zbiorów jest równe iloczynowi uzupełnień, uzupełnienie iloczynu zbiorów jest równe sumie uzupełnień.
Uwaga. Uważny czytelnik dostrzeże dualność praw rachunku zbiorów: jeśli w jakimś prawie sumę zastąpimy iloczynem, a iloczyn zastąpimy przez sumę, to otrzymamy również prawo rachunku zbiorów.
Definicja 1.7
Różnicą symetryczną zbiorów A i B nazywamy zbiór AÅ B, elementami którego są te elementy zbioru A È B, które nie należą równocześnie do obu zbiorów A i B, por. Rys.1.9
xÎ A Å B wttw xÎ (A È B)\(A Ç B)
Rys. 1.9 Różnica symetryczna.
Zwróćmy uwagę na występującą w tej definicji alternatywę wykluczającą:
xÎ A Å B wttw albo xÎ A albo x Î B).
Dlaczego operacja ta nazywa się różnicą symetryczną? Wynika to z następującej charakteryzacji operatora Å :
A Å B = (A\B) È (B\A)
Prawdziwość powyższej równości wynika wprost z praw deMorgana A Å B = (A È B)\(A Ç B) = (A È B)\ A È (A È B)\ B = (B\A) È (A\B) = (A\B) È (B\A)
Przykład 1.9
Niech A = {2iÎ N : i<6} i B = {3iÎ N: i< 6}. Wtedy A Å B = {2,4,8,10,3,9,15}.
Pytanie 7: Jaki jest wynik A Å A ?
« poprzedni punkt | następny punkt » |