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

02.12.2009 - Krzysztof Piecuch
TrudnośćTrudność

W informatyce - podobnie jak w życiu - niektóre problemy łatwiej rozwiązać, a inne trudniej. W niniejszym artykule pokażemy jak problem trudny rozwiązać za pomocą problemów łatwiejszych. Problemem jakim się zajmiemy będzie liczenie elementów sumy zbiorów.

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

Liczenie elementów sumy zbiorów jest problemem niełatwym, ze względu na elementy powtarzające się w zbiorach. Zacznijmy od dwóch zbiorów $ A $ i $ B $. Ponieważ oba zbiory mogą mieć elementy wspólne to ilość elementów w sumie tych zbiorów nie musi być równa sumie ilości elementów w poszczególnych zbiorach.

Czyli mówiac w języku matematyki - nie zawsze zachodzi równość: $ |A \cup B| = |A| + |B| $. To dlatego, że elementy wspólne dla zbiorów $ A $ oraz $ B $ policzyliśmy dwukrotnie. Raz przy liczeniu elementów z $ A $ i drugi raz przy liczeniu elementów z $ B $.

 

 

Niech na przykład $ B = \left\lbrace 0, 3, 4, 5, 7, 8\right\rbrace $, oraz $ A = \left\lbrace 1, 2, 3, 8, 9 \right\rbrace  $. Wtedy $ A \cup B = \left\lbrace 0, 1, 2, 3, 4, 5, 7, 8, 9 \right\rbrace $. Zbiór $ A $ ma 5 elementów, zbiór $ B $ ma 6, ale suma zbiorów $ A $ i $ B $ nie ma 11 elementów, ale tylko 9. Aby poprawnie policzyć liczbę elementów w sumie należy dodać ilość elementów zbioru $ A $ do ilości elementów zbioru $ B $ a później odjąć ilość elementów wspólnych $ A $ i $ B $:

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

Spróbujmy teraz zrobić to samo dla trzech zbiorów. Sumujemy najpierw wszystkie trzy zbiory: $ A $, $ B $ oraz $ C $. Jednak wiemy już że policzyliśmy za dużo. Odejmijmy teraz wszystkie przecięcia: $ A \cap B $, $ A \cap C $ oraz $ B \cap C $.

Okazuje się jednak, że odjęliśmy za dużo (prezentuje to diagram Venna poniżej), musimy teraz dodać jeszcze przecięcie wszystkich zbiorów $ A \cap B \cap C $.

 

Podsumowując zatem wzór na ilość elementów w sumie trzech zbiorów wygląda tak: $ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| $.

Ogólna zasada włączeń i wyłączeń mówi nam, że aby obliczyć ilość elementów w sumie zbiorów $ A_1 $, $ A_2 $, ..., $ A_n $ należy policzyć przecięcia wszystkich możliwych zbiorów i zsumować je. Te króte zawierają nieparzystą ilość zbiorów ze znakiem plus, te które mają parzystą ze znakiem minus.

Zilustrujmy jeszcze działanie tej zasady dla czterech zbiorów aby upewnić się, że faktycznie zasada ta działa. Niech $ A = \left\lbrace1, 2, 3, 4, 5, 6, 7, 8\right\rbrace $, $ B = \left\lbrace2, 3, 4, 5, 11, 12, 14, 15\right\rbrace $, $ C = \left\lbrace4, 5, 6, 7, 10, 11, 12, 13\right\rbrace $ oraz $ D = \left\lbrace3, 4, 7, 8, 9, 10, 11, 14\right\rbrace $.Każdy zbiór ma po 8 elementów, ale sumą wszystkich zbiorów ma ich tylko 15 (co łatwo sprawdzić). Dodając moce wszystkich zbiorów otrzymujemy $ 4 \times 8 = 32 $ elementy.

Policzyliśmy za dużo! Choć elementy $ 1, 9, 13, 15 $ zostały policzone dokładnie jeden raz, to elementy $ 2, 6, 8, 10, 12, 14 $ zostały policzone dwukrotnie, elementy $ 3, 5, 7, 11 $ trzykrotnie, a element $ 4 $ aż czterokrotnie! Odejmujemy teraz przecięcia wszystkich par zbiorów: $ A \cap B = \left\lbrace2, 3, 4, 5\right\rbrace $, $ A \cap C = \left\lbrace4, 5, 6, 7\right\rbrace $, $ A \cap D = \left\lbrace3, 4, 7, 8\right\rbrace $, $ B \cap C = \left\lbrace4, 5, 11, 12\right\rbrace $, $ B \cap D = \left\lbrace3, 4, 11, 14\right\rbrace $ oraz $ C \cap D = \left\lbrace4, 7, 10, 11\right\rbrace $. Od naszych 32 elementów odjęliśmy $ 6 \times 4 = 24 $ a więc zostało nam 8 elementów.

Policzyliśmy za mało! Chociaż elementy $ 1, 2, 6, 8, 9, 10, 12, 13, 14, 15 $ policzyliśmy dokładnie jeden raz, to elementów $ 3, 5, 7, 11 $ nie policzyliśmy w ogóle, a element $ 4 $ wręcz policzyliśmy minus dwa razy!. Spróbujmy teraz dodać przecięcia trójek: $ A \cap B \cap C = \left\lbrace4, 5\right\rbrace $, $ A \cap B \cap D = \left\lbrace3, 4\right\rbrace $, $ A \cap C \cap D = \left\lbrace4, 7\right\rbrace $ oraz $ B \cap C \cap D = \left\lbrace4, 11\right\rbrace $. Jest już bardzo dobrze do poprzednich 8 elementów dodaliśmy teraz $ 4 \times 2 = 8 $ elementów. Mamy już 16.

To za dużo o jeden. Wszystkie liczby policzyliśmy dokładnie raz, oprócz 4 którą policzyliśmy dwa razy. Odejmując przecięcie wszystkich zbiorów $ A \cap B \cap C \cap D = \left\lbrace4\right\rbrace  $ otrzymujemy oczekiwany wynik.

3.25
Twoja ocena: Brak Ocena: 3.3 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com