Definicję powyższą można też krótko zapisać w postaci A\B = { x ∈ A : x ∉ B} (por Rys. 1.5.1).

Rys. 1.5.1  Różnica zbiorów A i B.

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.5.1

(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".

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.

Mamy więc ostatecznie, x ∈ B i x ∉ C, co oznacza, że x ∈ B\C. ♦

Do najważniejszych praw rachunku zbiorów należą zależności wiążące sumę, różnicę i iloczyn zbiorów, zwane prawami de Morgana.

Dowód.

1. Przedstawimy dowód pierwszego z wymienionych praw.

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.1 mamy A \ (B ∪ C) ⊆ (A \ B) i A \ (B ∪ C) ⊆ (A \ C). Stąd na mocy lematu 1.4.1 mamy A \ (B ∪ C) ⊆ (A \ B) ∩ (A \ C).

2. Zamiast dowodu, lewą i prawą stronę drugiego prawa de Morgana zilustrujemy, za pomocą diagramów Venna (por. Rys. 1.5.2). Uzasadnienia za pomocą 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ć. ♦

Rys. 1.5.2 Ilustracja graficzna prawa A \ (B ∩ C) = (A \ B) ∪ (A \ C).

Rozważane w zastosowaniach zbiory bardzo często są same podzbiorami jakiegoś jednego większego zbioru. Po prostu, w rozważaniach ograniczamy się tylko do elementów pewnego, interesującego nas w danej chwili, 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 A^c (od angielskiego słowa complement).

Prawa de Morgana zapisane dla operacji uzupełnienia przyjmują postać:

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.

Rys. 1.5.3 Różnica symetryczna zbiorów A i B.

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 jest prostą konsekwencją  praw de Morgana:

A ⊕ B = (A ∪ B)\(A ∩ B) = (A ∪ B)\ A ∪ (A ∪ B)\ B = (B\A) ∪ (A\B) = (A\B) ∪ (B\A).

Przykład 1.5.2

Niech A = {2i ∈ N : i<6} i B = {3i ∈ N: i< 6}. Wtedy A ⊕ B = {2,4,8,10,3,9,12,15}.

Pytanie 1.5.1: Jaki jest wynik A ⊕ A ?

« poprzedni punkt

następny punkt »