W tym rozdziale zastanowimy się nad tym, ile elementów ma suma dwóch zbiorów.
Popatrzmy najpierw na zadanie. W klasie jest 16 chłopców i 13 dziewcząt. Ilu uczniów jest w tej klasie? Tu odpowiedź jest bardzo prosta: 29. Wynika to stąd, że zbiory chłopców i dziewcząt są rozłączne. Wtedy wystarczy dodać liczbę dziewcząt do liczby chłopców, by otrzymać poprawny wynik.
Popatrzmy na zadanie podobne. Wiemy, że w pewnej klasie każdy uczeń trenuje pływanie lub skoki na nartach. Pływanie trenuje 17 uczniów, skoki na nartach 21 uczniów.
Spróbujmy zapisać to wszystko, używając symboliki matematycznej. Spróbujmy też zrozumieć, co odróżnia jeden z tych dwóch przykładów od drugiego.
Garść pojęć i definicji
Jeśli świetnie wiesz, co to jest suma zbiorów, co to są zbiory rozłączne i zbiory parami rozłączne, to pewnie nie musisz czytać tego fragmentu (ale możesz). Jeśli masz wątpliwości, co znaczą wytłuszczone słowa w ostatnim zdaniu - lepiej przeczytaj wszystko. To nie jest długi tekst.
Zbiory można dodawać. Przypomnijmy:
|
Element x należy do sumy dwóch zbiorów A i B wtedy i tylko wtedy, gdy należy do co najmniej jednego z tych zbiorów.
|
Przypuśćmy, że mamy dane dwa zbiory rozłączne A i B , tzn. takie zbiory, które nie mają żadnego elementu wspólnego (symbolicznie piszemy: \(A \cap B=\emptyset\)). Wtedy zachodzi równość
\(\qquad |A \cup B| = |A| + |B|.\)
Ta równość oddaje istotę dodawania: jeśli mamy 5 jabłek i dostaniemy 4 inne jabłka, to razem będziemy mieli 5 + 4 = 9 jabłek. Zatem ten wzór na liczbę elementów sumy zbiorów rozłącznych jest w istocie definicją dodawania liczb naturalnych.
Jeśli zbiory A i B nie są rozłączne, to mamy tylko nierówność
\(\qquad |A \cup B| \le |A| + |B|.\)
|
Jeśli znamy liczbę elementów części wspólnej, to możemy obliczyć liczbę elementów sumy zbiorów: \(\qquad |A \cup B| = |A| + |B| - |A \cap B|.\)
|
Ta równość wynika stąd, że jeśli będziemy zliczać elementy sumy zbiorów \(A \cup B\) , to możemy najpierw policzyć elementy zbioru A , potem policzyć elementy zbioru B , dodać te liczby do siebie i wtedy zauważyć, że elementy części wspólnej, czyli iloczynu \(A \cap B\) zbiorów A i B, zostały (niepotrzebnie!) policzone dwukrotnie. Liczbę tych elementów musimy zatem odjąć od wyniku.
Sumę wielu zbiorów definiujemy podobnie, jak sumę dwóch zbiorów.
|
Mówimy, że element x należy do sumy zbiorów \(A_1, A_2, \ldots , A_ n\) wtedy i tylko wtedy, gdy należy do co najmniej jednego z tych zbiorów. Inaczej mówiąc, x należy do sumy, oznaczanej symbolem \(A_1 \cup A_2 \cup \ldots \cup A_n,\) wtedy i tylko wtedy, gdy należy do zbioru A1 lub należy do zbioru A2 lub należy do zbioru A3, i tak dalej, aż do zbioru An : \(\qquad x \in A_1 \cup A_2 \cup \ldots \cup A_ n \Leftrightarrow x\in A_1 \, \lor \, x\in A_2 \, \lor \ldots \lor \, x \in A_ n.\)
|
W podobny sposób definiujemy iloczyn wielu zbiorów.
|
Mówimy, że element x należy do iloczynu zbiorów \(A_1, A_2, \ldots , A_ n\) , oznaczanego symbolem \(A_1 \cap A_2 \cap \ldots \cap A_ n\) , wtedy i tylko wtedy, gdy należy do każdego z tych zbiorów: \(\qquad x \in A_1 \cap A_2 \cap \ldots \cap A_ n \Leftrightarrow x\in A_1 \, \land \, x\in A_2 \, \land \ldots \land \, x \in A_ n.\)
|
I jeszcze jedno pojęcie, z którego będziemy korzystać:
|
Jeśli każde dwa zbiory spośród zbiorów \(A_1, A_2, \ldots , A_ n\) są rozłączne, to mówimy, że te zbiory są parami rozłączne.
|
Uwaga. Zbiory \(A_1, A_2, \ldots , A_ n\) czasami nazywa się rozłącznymi, jeśli iloczyn wszystkich tych zbiorów jest pusty: \(A_1 \cap A_2 \cap \ldots \cap A_ n = \emptyset\) . To nie jest to samo! Zbiory
\(\qquad \{ 1,2\} , \quad \{ 1,3\} \quad \mbox{oraz}\quad \{ 2,3\}\)
są rozłączne, ale nie są parami rozłączne.
Ogólna reguła
Wzór na liczbę elementów sumy dwóch zbiorów rozłącznych uogólnia się na przypadek dowolnej liczby zbiorów parami rozłącznych.
| Twierdzenie (liczba elementów sumy zbiorów parami rozłącznych): |
|
Jeśli zbiory \(A_1, A_2, \ldots , A_ n\) są parami rozłączne, to zachodzi równość \(|A_1 \cup A_2 \cup \ldots \cup A_ n| = |A_1|+|A_2|+\ldots +|A_ n|.\) |
Treść wyrażoną w ostatnim wzorze można wypowiedzieć potocznie jako tzw. regułę dodawania. Z reguły tej będziemy wielokrotnie korzystać.
| Twierdzenie (reguła dodawania): |
|
Jeśli możemy wykonać n czynności, przy czym pierwsza czynność daje jeden z k1 wyników, druga czynność daje jeden z k2 wyników itd. aż do n -tej czynności, która daje jeden z kn wyników oraz te wszystkie wyniki są różne, to wykonanie jednej (którejkolwiek) z tych czynności daje jeden z \(k_1+k_2+\ldots +k_n\) wyników. |
Przykłady
Zadanie 1.2.1: Na ile sposobów możemy wybrać jednoosobową delegację parlamentu, w skład którego wchodzi 460 posłów i 100 senatorów?
∎
Zadanie 1.2.2: Każdy uczeń w klasie gra w piłkę nożną lub w koszykówkę. W piłkę nożną gra 23 uczniów, w koszykówkę 18 uczniów, natomiast w obie te gry razem gra 11 uczniów. Ilu uczniów jest w tej klasie?
\(\qquad |N| = 23, \quad |K| = 18, \quad |N \cap K| = 11.\)
Stąd wynika, że
\(\qquad |N \cup K| = |N| + |K| - |N \cap K| = 23 + 18 - 11 = 30.\)
Ponieważ każdy uczeń należy do któregoś ze zbiorów N i K , więc zbiór \(N \cup K\) jest zbiorem wszystkich uczniów w klasie. Zatem w tej klasie jest 30 uczniów.
∎
Zadanie 1.2.3: Ile jest liczb naturalnych od 1 do 125 włącznie dających resztę 0 lub resztę 1 przy dzieleniu przez 4?
\(\qquad A = \{ 4n :\, 1 \le n \le 31 \} .\)
Liczby dające resztę 1 tworzą zbiór
\(\qquad B = \{ 4n+1:\, 0 \le n \le 31 \} .\)
Te zbiory oczywiście nie mają elementów wspólnych. Zatem \(|A \cup B| = |A| + |B|.\) Zbiór A ma oczywiście 31 elementów, a zbiór B ma 32 elementy. Ostatecznie \(|A \cup B| = 63\) .
∎
Zadanie 1.2.4: Ile jest liczb naturalnych od 1 do 1000 włącznie podzielnych przez 3 lub przez 5?
\(\qquad A = \{ 3n:\, 1 \le n \le 333 \} .\)
Liczby podzielne przez 5 tworzą zbiór
\(\qquad B = \{ 5m:\, 1 \le m \le 200 \} .\)
Zbiory A i B nie są jednak rozłączne. Ich część wspólną stanowi zbiór liczb podzielnych przez 15 (liczba naturalna jest podzielna przez 3 i przez 5 wtedy i tylko wtedy, gdy jest podzielna przez 15 – jest tak dlatego, że liczby 3 i 5 są względnie pierwsze, tzn. nie mają wspólnego dzielnika większego od 1).
Mamy zatem
\(\qquad A \cap B = \{ 15k:\, 1 \le k \le 66 \}.\)
Stąd dostajemy
\(\qquad |A \cup B| = |A| + |B| - |A \cap B| = 333 + 200 - 66 = 467.\)
∎
\(\qquad |A \setminus B| = |A| - |A \cap B|.\)
Wynika to stąd, że
\(\qquad A = (A \setminus B) \cup (A \cap B),\)
a zbiory \(A \setminus B\) i \(A \cap B\) są rozłączne. Gdy jeden ze zbiorów A i B jest podzbiorem drugiego, to zachodzi wzór:
\(\qquad \mbox{jeśli}\, \, B \subseteq A, \quad \mbox{to}\, \, |A \setminus B|=|A|-|B|.\)
Zadanie 1.2.5: Ile jest liczb naturalnych od 1 do 1000 włącznie podzielnych przez 3 i niepodzielnych przez 5?
\(\qquad |A \setminus B| = |A| - |A \cap B| = 333 - 66 = 267.\)
∎