1 ALGEBRA ZBIORÓW
2 Zbiór Przykłady: zbiór studentów 1go roku zbiór książek w bibliotece zbiór liczb naturalnych (ozn. N) zbiór liczb rzeczywistych (ozn. R) zbiór słów nad alfabetem A (ozn. A*) Zamiast mówić, że 5 jest liczbą naturalną, mówimy, że 5 należy do zbioru liczb naturalnych i piszemy 5N. Symbol nazywamy relacją należenia. Jeśli element nie należy do zbioru, np nie jest liczbą naturalną, tzn nie należy do zbioru N, tzn. -2.5N. Dział matematyki, którego zadaniem jest badanie ogólnych własności zbiorów, nazywamy Teorią Mnogości. (George Cantor).
3 Definiowanie zbiorów A = {a,b,c,d,e,f,g}przez wymienienie ich elementów przez podanie własności, które muszą spełniać elementy przez podanie sposobu wyliczania elementów B = {x : xN oraz x<6} C = {x2 + 1 : xN} Jeśli zbiór nie posiada żadnych elementów, to powiemy, że jest pusty. Zbiór pusty oznaczamy przez . Zbiór A nie jest pusty, bo należy do niego element a. A, bo aA. Nie ma takiego obiektu, który należałby do zbioru pustego!
4 Równość zbiorów DefinicjaPowiemy, że dwa zbiory są równe wtedy i tylko wtedy, gdy mają dokładnie te same elementy. A=B (wttw) dla dowolnego x, jeżeli xA, to xB i odwrotnie jeżeli xB, to xA . AB wttw istnieje taki element zbioru A, który nie należy do B lub istnieje taki element zbioru B, który nie należy do A. Uwaga: Jeżeli A=B i B=C , to A=C. Przykład: A = {5,50,500,5000} = {5*10x: 0x<4 i xN} A = {5000,5,50,500}
5 Relacja zawierania inkluzja DefinicjaPowiemy, że zbiór A zawiera się w zbiorze B, ozn. A B wttw dla dowolnego obiektu x, jeśli xA, to xB. UWAGA: Jeśli A=B, to również AB. Jeśli AB i AB, to mówimy, że A jest właściwym podzbiorem zbioru B, ozn. AB. Przykłady: NR, QR, ZR {d, a}{a,b,c,d,e,f}
6 O zbiorze A mówimy, że jest podzbiorem zbioru B.A jest zawarty w zbiorze B Zbiór B zawiera zbiór A O zbiorze A mówimy, że jest podzbiorem zbioru B. O zbiorze B mówimy, że jest nadzbiorem zbioru A.
7 Jeżeli zbiór A nie zawiera się w zbiorze B, tznJeżeli zbiór A nie zawiera się w zbiorze B, tzn. nie jest prawdą, że zbiór A jest zawarty w zbiorze B, to musi istnieć taki obiekt (element), który należy do zbioru A i jednocześnie nie należy do zbioru B. A A B B AB wttw istnieje takie x, że xA i xB. Przykład. Zbiór liczb podzielnych przez 2 nie jest podzbiorem zbioru liczb podzielnych przez 5, bo np. 4 jest podzielne przez 2, a nie jest podzielne przez 5.
8 Własności inkluzji Twierdzenie Dla dowolnych zbiorów A,B,C : A AAJeśli AB oraz BC, to AC. Jeśli AB oraz BA, to A=B. Uwaga: Jeśli xA, to {x}A.
9 Zbiór potęgowy DefinicjaZbiór, który składa się z wszystkich podzbiorów pewnego zbioru A, nazywa się zbiorem potęgowym ozn. P(A) Przykład: A={1,2,3}, wtedy P(A) = {, {1},{2}, {3},{1,2},{2,3},{1,3}, {1,2,3}} UWAGA: P() = {}
10 Suma zbiorów DefinicjaSumą zbiorów A i B nazywamy zbiór, którego elementami są wszystkie elementy zbioru A i wszystkie elementy zbioru B. Sumę zbiorów A i B oznaczamy przez AB . xAB wttw xA lub xB A B Uwaga: xAB wttw xA i xB Przykład: A={3k: kN}, B= {2k : kN}. AB = {n: n jest liczbą, która dzieli się przez 2 lub przez 3}.
11 Własności sumy Twierdzenie Dla dowolnych zbiorów A,B,C : A = AA A = A A B = B A (A B) C = A (B C) przemienność łączność Uwaga: Powyższe równości można udowodnić wykazując, że jeśli element należy do lewej strony równości, to należy do prawej strony i odwrotnie.
12 Inkluzja a suma Twierdzenie Dla dowolnych zbiorów A, B, C:A A B oraz B A B Jeśli A C i B C , to A B C Jeśli A B i C D , to A C B D A B wttw A B = B
13 Dowód własności: A B wttw A B = B Zakładamy, że A B Dowodzimy, że A B= B (czyli A B B i B A B) i) Po pierwsze A, B B A B ii) Jeśli x A B to x A lub x B. Jeśli x A to na mocy założenia A B, x B. Powyższe rozumowanie jest poprawne dla dowolnego x (wzięliśmy dowolne x), więc udowodniliśmy, że jeśli A B to A B B. Odwrotnie, zakładamy, że A B = B. Jeżeli x A wtedy x A B, a ponieważ zbiory A B i B są równe więc x B. Czyli A B.
14 Iloczyn zbiorów DefinicjaIloczynem(przecięciem) zbiorów A i B nazywamy zbiór, którego elementami są te elementy zbioru A , które są równocześnie elementami zbioru B. x A B wttw x A i x B A B UWAGA: x A B wttw x A lub x B Przykład: Niech iN{0} A={2i : i<16}, B={3i : i<11} A B={0,6,12,18,24,30}= {6i : i < 6}
15 Własności iloczynu Twierdzenie Dla dowolnych zbiorów A,B,C : A = A A = A A B = B A (A B) C = A (B C) przemienność łączność
16 Dla dowolnych zbiorów A,B,C: A (A B) = A (A B) B = B Twierdzenie Dla dowolnych zbiorów A,B,C: A (A B) = A (A B) B = B A (B C) = (A B) (A C) A (B C) = (A B) (A C) Prawa absorpcji Prawa rozdzielności
17 Diagramy Venna A B C =
18 Różnica symetryczna DefinicjaRóżnicą symetryczną zbiorów A, B nazywamy zbiór A B taki, że: xA lub xB ale x nie należy do obu zbiorów równocześnie. Przykład: Niech iN{0} A= {2i : i<6}, B= {3i : i<6} A B = {2,3,4,8,9,10,12,15}
19 Różnica zbiorów DefinicjaRóżnicą zbiorów A i B nazywamy zbiór , którego elementami są te obiekty zbioru A, które nie są równocześnie elementami zbioru B. Różnicę zbiorów oznaczamy przez A\B. xA\B wttw xA i xB A B UWAGA: x A\ B wttw x A lub x B . Przykład: A= {1,2,3,4,5,6} B={ 2i+1: i<5 i iN {0}} A\B = {2,4,6} B\A = {7,9}
20 Własności różnicy Twierdzenie Dla dowolnych zbiorów A,B,C : A\B AA B wttw A\B = Jeśli A B, to C\B C\A A \(B C)= (A\B)\C. Prawa de Morgana A\(B C) = (A\B) (A\C) A\(B C) = (A\B) (A\C)
21 Dopełnienie zbioru DefinicjaDopełnieniem (Uzupełnieniem) zbioru A w przestrzeni U nazywamy zbiór -A, którego elementami są wszystkie elementy przestrzeni U nie należące do zbioru A, tzn. dla dowolnego x U i dowolnego podzbioru A przestrzeni U: x- A wttw x A U A UWAGA: U\A = -A Przykład: Niech uniwersum U=N oraz A={2i: i N}. Wtedy -A jest zbiorem wszystkich liczb nieparzystych.
22 Własności dopełnień TwierdzenieDla dowolnych zbiorów A,B pewnego uniwersum U : - = U -U = -(-A ) = A Jeśli A B, to - B -A. Prawa de Morgana -(A B) = -A -B -(A B) = -A -B
23 Działania nieskończoneDefinicja Niech będzie rodzina zbiorów A= {Ai : iI}. Sumą nieskończonej rodziny zbiorów nazywamy zbiór Ai taki, że xAi wttw istnieje takie iI, że xAi . Iloczynem (lub przecięciem) nieskończonej rodziny zbiorów nazywamy zbiór Ai taki, że x Ai wttw dla wszystkich i I, x Ai Przykład: Ai = {x R : x
24 Para uporządkowana Postulaty jakie musi spełniać para uporządkowana:Można ją utworzyć dla dowolnych dwóch elementów
25 Iloczyn (produkt) kartezjańskiDefinicja Iloczynem kartezjańskim zbiorów A i B (ozn. AB) nazywamy zbiór par uporządkowanych definiowany następująco: AB={
26 Własności iloczynu kartezjańskiegoTwierdzenie Dla dowolnych zbiorów X,A,B: X Y = Y X wttw X = Y X = X (A B) = (X A) (X B) X (A B) = (X A) (X B) X (A\B) = (X A) \ (X B) A B i C D wttw AC B D A (B C) (A B) C Stwierdzenie Jeżeli X jest zbiorem n-elementowym, a Y zbiorem m-elementowym, to produkt X Y ma n*m elementów.