Zasada włączeń i wyłączeń
02.12.2009 - Krzysztof Piecuch
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 i . 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ść: . To dlatego, że elementy wspólne dla zbiorów oraz policzyliśmy dwukrotnie. Raz przy liczeniu elementów z i drugi raz przy liczeniu elementów z .
Niech na przykład , oraz . Wtedy . Zbiór ma 5 elementów, zbiór ma 6, ale suma zbiorów i nie ma 11 elementów, ale tylko 9. Aby poprawnie policzyć liczbę elementów w sumie należy dodać ilość elementów zbioru do ilości elementów zbioru a później odjąć ilość elementów wspólnych i : Spróbujmy teraz zrobić to samo dla trzech zbiorów. Sumujemy najpierw wszystkie trzy zbiory: , oraz . Jednak wiemy już że policzyliśmy za dużo. Odejmijmy teraz wszystkie przecięcia: , oraz . 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 .
Podsumowując zatem wzór na ilość elementów w sumie trzech zbiorów wygląda tak: . Ogólna zasada włączeń i wyłączeń mówi nam, że aby obliczyć ilość elementów w sumie zbiorów , , ..., 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 , , oraz .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 elementy. Policzyliśmy za dużo! Choć elementy zostały policzone dokładnie jeden raz, to elementy zostały policzone dwukrotnie, elementy trzykrotnie, a element aż czterokrotnie! Odejmujemy teraz przecięcia wszystkich par zbiorów: , , , , oraz . Od naszych 32 elementów odjęliśmy a więc zostało nam 8 elementów. Policzyliśmy za mało! Chociaż elementy policzyliśmy dokładnie jeden raz, to elementów nie policzyliśmy w ogóle, a element wręcz policzyliśmy minus dwa razy!. Spróbujmy teraz dodać przecięcia trójek: , , oraz . Jest już bardzo dobrze do poprzednich 8 elementów dodaliśmy teraz 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 otrzymujemy oczekiwany wynik.
(4 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com