Zasada włączeń i wyłączeń

Przypomnijmy z poprzedniego rozdziału wzór wyrażający liczbę elementów sumy dwóch zbiorów w przypadku ogólnym:

$\qquad|A \cup B| = |A| + |B| - |A \cap B|.$

Zasada włączeń i wyłączeń dla trzech zbiorów

Podobnym wzorem wyraża się liczba elementów sumy trzech zbiorów:

Wzór ten nosi nazwę zasady włączeń i wyłączeń lub wzoru włączeń i wyłączeń. Nazwa ta bierze się stąd, że liczbę po prawej stronie otrzymujemy,,włączając” do niej trzy liczby | A | , | B | i | C | , potem,,wyłączając” z niej liczby $|A \cap B|$ , $|A \cap C|$ i $|B \cap C|$ i wreszcie,,włączając” do niej liczbę $|A \cap B \cap C|$ .

Spróbujmy policzyć elementy sumy $A \cup B \cup C$ . Najpierw liczymy elementy zbioru A , potem elementy zbioru B i wreszcie elementy zbioru C . Otrzymane liczby dodajemy. Mamy więc na razie wynik | A | + | B | + | C | . Teraz zauważamy, że pewne elementy liczyliśmy dwukrotnie: jeśli $x \in A \cap B$ , to element x był policzony dwukrotnie, raz jako element zbioru A i raz jako element zbioru B . Musimy więc odjąć od wyniku liczbę $|A \cap B|$ . Podobnie musimy odjąć liczby $|A \cap C|$ i $|B \cap C|$ . To jednak jeszcze nie koniec. Zauważamy, że jeśli x jest elementem wszystkich zbiorów, to najpierw był policzony trzykrotnie: raz jako element zbioru A , raz jako element zbioru B i raz jako element zbioru C . Ale potem trzykrotnie policzyliśmy go jako element zbiorów $A \cap B$ , $A \cap C$ i $B \cap C$ . W naszym dotychczasowym wyniku element x trzykrotnie uwzględniliśmy, potem trzykrotnie się go pozbyliśmy. Trzeba więc jeszcze raz go dodać. Stąd wynika, że do wyniku należy dodać liczbę $|A \cap B \cap C|$ i w ten sposób otrzymujmy prawą stronę wzoru.

Zasada włączeń i wyłączeń: przypadek ogólny

Podobny wzór zachodzi również dla większej liczby zbiorów. Dla czterech zbiorów można jeszcze spróbować go wypisać.

Zasada włączeń i wyłączeń: przypadek czterech zbiorów

Dla większej liczby zbiorów wypisanie odpowiedniego wzoru jest jeszcze bardziej uciążliwe. Widać jednak tę samą, jasną zasadę:

Typowy przykład

Pokażemy dwa przykłady zadań, w których można wykorzystać zasadę włączeń i wyłączeń. Oto pierwszy z nich

Zadanie 1.3.1: W klasie liczącej 33 osoby 17 uczniów uczy się języka włoskiego, 17 uczniów uczy się języka hiszpańskiego i 15 uczniów uczy się języka portugalskiego. Wśród nich 7 uczniów uczy się dwóch języków: włoskiego i hiszpańskiego, 9 uczniów uczy się języka włoskiego i portugalskiego oraz 6 uczniów uczy się języka hiszpańskiego i portugalskiego. Wreszcie 2 uczniów uczy się tych trzech języków. Ilu uczniów nie uczy się żadnego z tych języków?

$\qquad \begin{array}{c} |W|=17, \, |H|=17, \, |P|=15, \\ |W \cap H|=7, \, |W \cap P|=9, \, |H \cap P|=6, \\ |W \cap H \cap P|=2. \\ \end{array}$

Z zasady włączeń i wyłączeń wynika, że

$\qquad |W \cup H \cup P| = 17+17+15-7-9-6+2 = 29.$

A zatem 4 uczniów nie uczy się żadnego z tych języków.
∎

To zadanie można też rozwiązać, nie odwołując się do zasady włączeń i wyłączeń. Wprowadzimy parę nowych pojęć i oznaczeń, i pokażemy, jak można zasadę włączeń i wyłączeń zastąpić odpowiednio wykonanymi rysunkami.

Zbiór, przestrzeń, dopełnienie, składowe. Jak robić rysunki?

Przypuśćmy, że rozważamy wyłącznie zbiory zawarte w pewnym ustalonym zbiorze X. Zbiór X nazywamy wtedy przestrzenią. Jeśli mamy zbiór A zawarty w przestrzeni X , tzn. $A \subseteq X$ , to zbiór $X \setminus A$ nazywamy dopełnieniem (lub uzupełnieniem) zbioru A (czasem dodajemy słowa "do przestrzeni X", dla zaznaczenia, jaką przestrzeń rozważamy) i oznaczamy symbolem A'.

Zauważmy, że różnica zbiorów A i B wyraża się łatwo za pomocą iloczynu i dopełnienia: $A \setminus B=A \cap B'.$

Przypuśćmy teraz, że mamy dane dwa zbiory A i B zawarte w przestrzeni X.

Dobrze: dwa zbiory, A i B, w położeniu ogólnym

Często robimy schematyczny rysunek takich zbiorów. Będziemy mówić, że naszkicowane zbiory A i B są w położeniu ogólnym, jeśli na rysunku są uwidocznione cztery obszary odpowiadające zbiorom $A \cap B$ , $A \cap B'$ , $A' \cap B$ i $A' \cap B'$ .

Tak więc na rysunku obok zbiory A i B zostały przedstawione właśnie w położeniu ogólnym. Na tym rysunku zbiory A i B zostały narysowane jako dwa przecinające się okręgi, dzielące płaszczyznę na cztery obszary. Liczby wpisane wewnątrz tych obszarów wskazują, który z czterech zbiorów $A \cap B$ , $A \cap B'$ , $A' \cap B$ i $A' \cap B'$ odpowiada danemu obszarowi:

$\begin{array}{ll} 1: & \quad A \cap B, \\ 2: & \quad A \cap B', \\ 3: & \quad A' \cap B, \\ 4: & \quad A' \cap B'. \\ \end{array}$

Zbiory $A \cap B$ , $A \cap B'$ , $A' \cap B$ i $A' \cap B'$ nazywamy składowymi zbiorów A i B .

Źle: te pary zbiorów nie są w położeniu ogólnym

Natomiast na rysunkach obok zbiory A i B nie są przedstawione w położeniu ogólnym.

Dlaczego?

Na lewym z tych rysunków nie jest zaznaczony obszar odpowiadający zbiorowi $A \cap B$.

Na prawym rysunku nie ma obszaru, który odpowiadałby zbiorowi $A' \cap B.$

Podobnie mówimy, że trzy zbiory A , B i C są narysowane w położniu ogólnym, jeśli zaznaczone są obszary odpowiadające ośmiu składowym:

$\begin{array}{c} A \cap B \cap C, \quad A \cap B \cap C', \quad A \cap B' \cap C, \quad A \cap B' \cap C', \\ A' \cap B \cap C, \quad A' \cap B \cap C', \quad A' \cap B' \cap C, \quad A' \cap B' \cap C'. \\ \end{array}$

Na poniższym rysunku widzimy trzy zbiory naszkicowane w położeniu ogólnym:

Trzy zbiory, A, B i C, w położeniu ogólnym

Zbiory A, B i C zostały ponownie przedstawione jako trzy przecinające się okręgi, dzielące płaszczyznę na osiem obszarów, które odpowiadają składowym. Liczby wpisane wewnątrz tych ośmiu obszarów wskazują, której składowej odpowiada dany obszar:

$\begin{array}{ll} 1: & \quad A \cap B \cap C, \\ 2: & \quad A \cap B \cap C', \\ 3: & \quad A \cap B' \cap C, \\ 4: & \quad A \cap B' \cap C', \\ 5: & \quad A' \cap B \cap C, \\ 6: & \quad A' \cap B \cap C', \\ 7: & \quad A' \cap B' \cap C, \\ 8: & \quad A' \cap B' \cap C'. \\ \end{array}$

Natomiast na rysunku

trzy zbiory A , B i C nie są narysowane w położeniu ogólnym, gdyż jedna z ośmiu składowych nie została uwidoczniona.

Zauważmy jeszcze, że składowe są zbiorami parami rozłącznymi (tzn. każde dwie składowe są rozłączne) i w sumie dają całą przestrzeń X .

Kolejne przykłady

Przypomnijmy ostatnie zadanie.

Zadanie 1.3.2: W klasie liczącej 33 osoby 17 uczniów uczy się języka włoskiego, 17 uczniów uczy się języka hiszpańskiego i 15 uczniów uczy się języka portugalskiego. Wśród nich 7 uczniów uczy się dwóch języków: włoskiego i hiszpańskiego, 9 uczniów uczy się języka włoskiego i portugalskiego oraz 6 uczniów uczy się języka hiszpańskiego i portugalskiego. Wreszcie 2 uczniów uczy się tych trzech języków. Ilu uczniów nie uczy się żadnego z tych języków?

Zbiory $W,\,\, H$ i P. W poszczególne składowe wpisane są liczby ich elementów (można te liczby kolejno wyliczyć, patrz opis obok).

W obszary odpowiadające składowym wpisujemy liczby elementów tych składowych. Zaczynamy od składowej $W \cap H \cap P$: wpisujmy w odpowiadający jej obszar liczbę 2, gdyż 2 uczniów uczy się wszystkich trzech języków.

Następnie w obszar odpowiadający składowej $W \cap H \cap P'$ wpisujemy liczbę 5. Dlaczego? Otóż,

$\qquad (W \cap H \cap P) \cup (W \cap H \cap P') = W \cap H.$

Wiemy, że zbiór $W \cap H$ ma 7 elementów, przy czym 2 z nich należą do składowej $W \cap H \cap P.$ Zatem składowa $W \cap H \cap P'$ musi mieć 5 elementów.

W podobny sposób stwierdzamy, że

$\qquad |W' \cap H \cap P|=4 \, \, \mbox{oraz}\, \, |W \cap H' \cap P|=7.$

Obie liczby wpisujemy w odpowiednie obszary.

Wreszcie, w analogiczny sposób obliczamy, ile elementów mają składowe $W \cap H' \cap P'$ , $W' \cap H \cap P'$ oraz $W' \cap H' \cap P$.

Po wpisaniu wszystkich liczb w odpowiednie obszary dostajemy rysunek, któy został przedstawiony obok. Teraz wystarczy zauważyć, że wszystkie wpisane liczby dają w sumie 29, a więc składowa $W' \cap H' \cap P'$ ma 33 − 29 = 4 elementy.

∎

Zadanie 1.3.3: W klasie liczącej 31 osób 18 uczniów uczy się języka włoskiego, 16 uczniów uczy się języka hiszpańskiego i 12 uczniów uczy się języka portugalskiego. Wśród nich 7 uczniów uczy się dwóch języków: włoskiego i hiszpańskiego, 9 uczniów uczy się języka włoskiego i portugalskiego oraz 5 uczniów uczy się języka hiszpańskiego i portugalskiego. Wreszcie 3 uczniów nie uczy się żadnego z tych trzech języków. Ilu uczniów uczy się wszystkich języków?

Rozwiązanie:

To zadanie można łatwo rozwiązać za pomocą zasady włączeń i wyłączeń. Mamy bowiem

$\qquad \begin{array}{ll} |W \cup H \cup P| & = |W| + |H| + |P| - |W \cap H| - |W \cap P| - |H \cap P| + |W \cap H \cap P| = \\ & = 18 + 16 + 12 - 7 - 9 - 5 + |W \cap H \cap P| = 25 + |W \cap H \cap P|. \\ \end{array}$

Ponieważ 3 uczniów nie uczy się żadnego języka, więc

$\qquad |W \cup H \cup P| = 31 - 3 = 28.$

Zatem

$\qquad 28 = 25 + |W \cap H \cap P|,$

skąd wynika, że wszystkich trzech języków uczy się 3 uczniów.

∎

Pokażemy teraz rozwiązanie korzystające ze składowych.

Zbiory $W,\,\, H$ i P. Nie wiemy z początku, ile elementów mają składowe - ale stopniowo układamy równanie.

Znów robimy schematyczny rysunek, na którym zaznaczamy zbiory W, H i P w położeniu ogólnym. W polu odpowiadającym składowej $W \cap H \cap P$ wpisujemy niewiadomą x.

W pola odpowiadające składowym $W \cap H \cap P'$ , $W \cap H' \cap P$ oraz $W' \cap H \cap P$ wpisujemy odpowiednio 7 − x , 9 − x oraz 5 − x. Dlaczego? Chodzi o to, aby każdy z trzech iloczynów $W \cap H$, $H \cap P$ i $W \cap P$ miał odpowiednią liczbę elementów.

Teraz w pola odpowiadające składowym $W \cap H' \cap P'$ , $W' \cap H \cap P'$ oraz $W' \cap H' \cap P$ wpisujemy odpowiednio x + 2, x + 4 i x − 2.

Wiemy też, że zewnętrzna składowa $W' \cap H' \cap P'$ ma 3 elementy. Dodając wpisane na rysunku liczby do tej trójki, otrzymamy równanie

$\qquad x+(7-x)+(5-x)+(9-x)+(x+2)+(x+4)+(x-2)+3=31.$

Jego rozwiązaniem jest liczba 3, a więc trzech uczniów uczy się wszystkich języków.