Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 19

Zbiór jest grupą obiektów traktowaną jako jednostka. Zbiory mogą zawierać dowolne typy obiektów, w tym liczby, symbole, a nawet inne zbiory. Obiekty w zbiorze nazywane są elementami. Zbiory mogą być formalnie opisywane różnymi sposobami.

Pierwszym z nich jest wyliczenie elementów zbioru w nawiasach klamrowych. Tym samym zbiór

S = {7, 21, 57}

zawiera elementy 7, 21 oraz 57. Symbole ∈ oraz ∉ oznaczają odpowiednio należenie i nienależenie do zbioru. Możemy napisać 7 ∈ {7, 21, 57} oraz 8 ∉ {7, 21, 57}. Dla dwóch zbiorów A i B mówimy, że A jest podzbiorem zbioru B, co zapisujemy jako A ⊆ B, jeśli każdy element zbioru A jest również elementem zbioru B. Mówimy, że A jest podzbiorem właściwym B, co zapisujemy A ⊊ B, jeśli A jest podzbiorem B i nie jest równe B.

Kolejność elementów w zbiorze nie jest istotna, podobnie jak powtórzenia elementów. Pisząc {57, 7, 7, 7, 21}, uzyskamy ten sam zbiór S. Gdybyśmy chcieli uwzględniać liczbę wystąpień elementów, grupę taką nazywamy wielozbiorem, a nie zbiorem. Tym samym {7} i {7, 7} są różnymi wielozbiorami, ale są identyczne jako zbiory. Zbiór nieskończony zawiera nieskończenie wiele elementów. Nie można wypisać listy wszystkich elementów zbioru nieskończonego, zatem niekiedy będziemy używać zapisu „…” w znaczeniu „kontynuować sekwencję w nieskończoność”. Tym samym możemy zapisać zbiór liczb naturalnych N jako

{1, 2, 3, …}.

Zbiór liczb całkowitych Z można zapisać jako

{… ,−2,−1, 0, 1, 2, …}.

Zbiór, który ma zero elementów, nazywamy zbiorem pustym i zapisujemy jako Ø. Zbiór zawierający dokładnie jeden element niekiedy nazywany jest singletonem, a zbiór o dwóch elementach – parą nieuporządkowaną.

Kiedy chcemy opisać zbiór zawierający elementy spełniające pewną regułę, zapisujemy to jako {n : reguła dotycząca n}. Tym samym {n : n = m² dla pewnego m ∈ N} oznacza zbiór liczb stanowiących kwadraty liczb naturalnych.

Mając dwa zbiory A i B, ich sumą, zapisywaną jako A ∪ B, jest zbiór, który uzyskamy, łącząc wszystkie elementy zbiorów A i B w jeden. Przecięciem (częścią wspólną) zbiorów A i B, zapisywanym jako A ∩ B, jest zbiór tych elementów, które należą zarówno do A, jak i do B. Dopełnieniem zbioru A, zapisywanym jako A, jest zbiór wszystkich elementów rozważanej dziedziny, które nie należą do A.

Jak często bywa w matematyce, rysunek może pomóc w wyjaśnieniu niektórych pojęć. W przypadku zbiorów używamy tak zwanych diagramów Venna. Reprezentują one zbiory jako regiony zawarte w owalnych liniach. Niech zbiór START-t będzie zbiorem wszystkich słów rozpoczynających się literą t. W tym przykładzie na rysunku koło oznacza zbiór START-t. Kilka elementów tego zbioru jest reprezentowanych jako punkty wewnątrz tego koła.

Rysunek 0.1

Diagram Venna dla zbioru słów zaczynających się na literę „t”

Analogicznie na kolejnym rysunku możemy przedstawić zbiór END-z złożony ze słów kończących się na literę „z”.

Rysunek 0.2

Diagram Venna dla zbioru angielskich słów kończących się na literę „z”

Aby przedstawić obydwa zbiory w tym samym diagramie Venna, musimy narysować je tak, aby koła się nakładały, sygnalizując, że mają pewne elementy wspólne, jak na kolejnym rysunku. Na przykład słowo topaz należy do obu zbiorów. Rysunek ten zawiera też koło dla zbioru START-j. Nie nakłada się ono na koło dla zbioru START-t, gdyż żadne słowo nie może należeć do obu tych zbiorów.

Rysunek 0.3

Nakładające się koła wskazują na wspólne elementy

Kolejne dwa diagramy Venna ilustrują sumę i przecięcie zbiorów A i B.

Rysunek 0.4

Diagramy dla (a) A ∪ B oraz (b) A ∩ B