« poprzedni punkt  następny punkt »


5. Różnica zbiorów

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):

  1. A \ (B È C) = (A \ B) Ç (A \ C)
  2. A \ (B Ç C) = (A \ B) È (A \ C)

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 »