Rozdział V
ZBIORY.
WSTĘP.
Obecny rozdział wraz z kolejnym – poświęconym relacjom, pełnią rolę w pewnym sensie pomocniczą. Omawiane w nich problemy nie dotyczą bezpośrednio logiki w jej tradycyjnym rozumieniu, jako dziedziny zajmującej się badaniem poprawności wnioskowań. Ponieważ jednak w XX wieku logika została silnie związana z matematyką, takie dziedziny jak teoria zbiorów i relacji uważane są współcześnie za jej pełnoprawne działy.
Ze zbiorami i relacjami spotkaliśmy się już we wcześniejszych rozdziałach. Obecnie pojęcia te zostaną omówione w sposób bardziej ścisły i systematyczny. Będzie się to wiązało, niestety, z większą ilością koniecznej to opanowania teorii. Jednakże, jak zwykle, największy nacisk położony zostanie na rozwiązywanie typowych zadań, spotykanych w podręcznikach do logiki w częściach poświęconych zbiorom i relacjom.
5.1. PODSTAWOWE WIADOMOŚCI O ZBIORACH.
5.1.1. ŁYK TEORII.
Zbiór to pewna kolekcja obiektów. Mówimy, na przykład, o zbiorze znaczków pocztowych, zbiorze liczb nieparzystych, zbiorze nudnych książek, zbiorze studentów itp., itd. Zbiory oznaczamy najczęściej dużymi literami, na przykład X, Y, Z lub A, B, C, D itd. Jeśli wypisujemy elementy jakiegoś zbioru, to zwykle umieszczamy je w nawiasach klamrowych, oddzielając od siebie przecinkami, na przykład: {a, b, c ,d}. W zbiorze nie jest istotna kolejność, w jakiej elementy zostały przedstawione. Na przykład poniższe zbiory A i B są sobie równe (identyczne): A = {a, b, c}, B = {c, a, b}. Również fakt, że jakiś element zostaje, z jakichś powodów, wymieniony kilkakrotnie, nie zmienia w niczym zbioru. Przykładowo zbiór C = {a, a, c, b, a, b, c, a} jest identyczny z wymienionymi wcześniej A i B; każdy z tych zbiorów (również C!) zawiera trzy elementy – a, b, oraz c.
Szczególnym zbiorem jest tak zwany zbiór pusty, który nie zawiera żadnego elementu. Zbiór pusty oznaczamy zwykle symbolem Æ – bez żadnych nawiasów klamrowych.
Fakt, że jakiś obiekt jest elementem pewnego zbioru oznaczamy symbolem: Î. Symbol ten odczytujemy jako „należy” lub „jest elementem”. W odniesieniu do powyższego przykładu możemy więc napisać: a Î A, b Î A oraz c Î A. To, że obiekt nie jest elementem zbioru, zapisujemy przy pomocy znaku: Ï. Powiemy, na przykład: d Ï A.
Wypisanie elementów w klamrowych nawiasach nie jest jedyną metodą przedstawienia zbioru. Można to uczynić również podając swego rodzaju „przepis” według którego ktoś, gdyby chciał, mógł elementy zbioru wypisać. „Przepis” taki może być mniej lub bardziej formalny. Zbiór D = {1, 2, 3, 4} możemy przedstawić na przykład: D – zbiór liczb naturalnych mniejszych od 5; lub bardziej formalnie: D = {x: x Î N Ù x < 5} (gdzie N oznacza zbiór liczby naturalnych). Zapis typu {x: ...} odczytujemy: „zbiór takich iksów (elementów), że...”, a więc, w naszym wypadku, powiedzielibyśmy: zbiór takich x, które są liczbami naturalnymi i są jednocześnie mniejsze od 5.
Elementami jakiegoś zbioru mogą być nie tylko „zwykłe” obiekty, ale również inne zbiory. Na przykład X = { {a, b}, {c}, {d, e, f, g} }. Zbiór X ma trzy elementy, które z kolei same też są zbiorami. To, że te „pomniejsze” zbiory też mają swoje elementy, nie ma żadnego wpływu na ilość elementów X. X ma trzy elementy, ponieważ w jego „głównych” nawiasach klamrowych znajdują się trzy obiekty oddzielone przecinkami.
Oczywiście zbiory mogą mieć elementy różnego typu: zarówno „zwykłe” przedmioty, jak i inne zbiory. Na przykład: Y = { {a, b}, c, d, {e, f, g, h} }; zbiór Y ma cztery elementy: c, d, {a,b} i {e, f, g, h}.
Określając elementy zbiorów trzeba bardzo uważnie przyglądać się nawiasom klamrowym. Przykładowo zupełnie różne są zbiory: A = {a, b, c} oraz E = { {a, b, c} }. Zbiór A ma trzy elementy, natomiast E jeden, sam będący zbiorem.
Trzeba również koniecznie zdać sobie sprawę, że różne od siebie są następujące zbiory: F = {a} oraz G = { {a} }. Wprawdzie obydwa mają po jednym elemencie, jednak elementem F jest po prostu „zwykły” obiekt a, natomiast elementem zbioru G jest zbiór, którego elementem jest a.
5.2. STOSUNKI MIĘDZY ZBIORAMI.
5.2.1. ŁYK TEORII.
Zbiory mogą pozostawać względem siebie w różnych zależnościach.
Identyczność.
Mówimy, że dwa zbiory są sobie równe lub że są identyczne, gdy mają dokładnie te same elementy. Identyczność dwóch zbiorów oznaczamy symbolem: =. Posługując się znanymi z rachunku zdań i predykatów symbolami, możemy identyczność zbiorów zdefiniować:
A = B º "x (x Î A º x Î B)
(To, że A i B są równe, oznacza, że dla każdego x to, że x należy do A jest równoważne temu, że x należy do B)
Przykładowo identyczne są zbiory A – zbiór liczb parzystych oraz B – zbiór liczb podzielnych przez 2. Równe są też zbiory A = {a, b, c, d} i B = {b, d, c, a}.
Inkluzja (zawieranie się zbiorów).
Mówimy, że zbiór A zawiera się w zbiorze B (A pozostaje w stosunku inkluzji do B), gdy każdy element A jest jednocześnie elementem B (choć niekoniecznie na odwrót). Inkluzję oznaczamy symbolem: Í. Zawieranie się zbiorów możemy przedstawić wzorem:
A Í B º "x (x Î A ® x Î B)
Inkluzja zachodzi na przykład pomiędzy zbiorami: A = {a, b}, B = {a, b, c, d} lub A – zbiór krokodyli, B – zbiór gadów.
Jeśli zbiór A zawiera się w zbiorze B, to możemy też powiedzieć, że A jest podzbiorem B.
Rozłączność.
Zbiory A i B są rozłączne, gdy nie mają żadnego elementu wspólnego. Rozłączność oznaczamy: )(. Symbolicznie:
A )( B º "x (x Î A ® x Ï B) lub ~ $x (x Î A Ù x Î B)
Przykładowo, rozłączne są zbiory A = {a, b, c} i B = {d, e} lub A – zbiór ssaków, B – zbiór płazów.
Krzyżowanie.
Zbiory się krzyżują gdy mają one pewne elementy wspólne, ale oprócz nich w każdym zbiorze znajdują się również takie obiekty, których nie ma w drugim. Krzyżowanie zbiorów oznaczamy najczęściej przy pomocy dwóch zazębiających się nawiasów, jednakże z przyczyn technicznych (brak takiego symbolu w edytorze tekstu) będziemy na oznaczenie krzyżowania używali obecnie znaku: #. Symbolicznie krzyżowanie zbiorów definiujemy:
A # B º $x (x Î A Ù x Î B) Ù $x (x Î A Ù x Ï B) Ù $x (x Ï A Ù x Î B)
Krzyżują się na przykład zbiory: A = {a, b, c, d} i B = {a, b, e} lub A – zbiór ssaków, B – zbiór drapieżników (istnieją ssaki będące drapieżnikami, ale też ssaki nie będące drapieżnikami oraz drapieżniki nie będące ssakami).
Odnośnie przedstawionych zależności pomiędzy zbiorami dobrze jest zauważyć, że stosunki identyczności, rozłączności oraz krzyżowania się zbiorów są symetryczne. Oznacza to, że jeśli taka zależność zachodzi „w jedną stronę”, to zachodzi również „w drugą”. Jeśli A = B, to również B = A, jeśli A )( B, to również B )( A, a jeśli A # B, to również B # A. A zatem w przypadku tych stosunków nie jest istotna kolejność, w jakiej wypiszemy pozostające w nich zbiory. Inaczej ma się sytuacja w przypadku inkluzji. Tu fakt, że A Í B, nie oznacza, że B Í A.
Zależności między zbiorami można przedstawić graficznie:
B
A
Identyczność (A = B) Inkluzja (A Í B)
Rozłączność (A )( B) Krzyżowanie (A # B)
5.2.2. PRAKTYKA: OKREŚLANIE ZALEŻNOŚCI MIĘDZY ZBIORAMI.
Zadania związane ze stosunkami między zbiorami polegają zwykle na określeniu zależności pomiędzy kilkoma podanymi zbiorami. Po nabraniu pewnej wprawy, zadania tego typu są bardzo łatwe i rozwiązywać je można „od ręki”, bez stosowania jakichkolwiek systematycznych metod. Na początku można posłużyć się metodą eliminacji, po kolei sprawdzając, czy zachodzi dany stosunek, zaczynając od tych, które najłatwiej jest stwierdzić i ewentualnie odrzucić. Przykładowa procedura może wyglądać następująco:
1. Najpierw sprawdzamy, czy zbiory mają te same elementy. Jeśli tak, to znaczy, że są one identyczne, jeśli nie, szukamy dalej.
2. Sprawdzamy wtedy, czy badane zbiory mają choć jeden wspólny element. Jeśli nie mają, znaczy to, że są one rozłączne.
3. Jeśli natomiast zbiory mają jakieś wspólne elementy, to pytamy, czy może jest tak, że każdy element pierwszego jest elementem drugiego lub każdy element drugiego elementem pierwszego. Jeśli tak jest, to znaczy to, że jeden ze zbiorów zawiera się drugim (zachodzi inkluzja).
4. Jeśli tak nie jest, to zbiory muszą się krzyżować – jest to ostatnia możliwość, która nam została. Dla sprawdzenia, możemy zadać sobie pytanie, czy oprócz elementów wspólnych dla obu zbiorów są też takie, które są tylko w jednym i takie, które są tylko w drugim. Jeśli nigdzie wcześniej nie popełniliśmy błędu, to odpowiedź na to pytanie musi być twierdząca.
Przykład:
Sprawdzimy, jakie zachodzą stosunki między następującymi zbiorami:
A = {4}, B = {2, 3}, C = {1, 2, 3, 4}, D = {1, 2, 4}.
Zaczynamy od sprawdzenia, w jakich stosunkach do innych zbiorów pozostaje A. Zbiory A i B nie mają żadnego wspólnego elementu, więc są one rozłączne. W przypadku A i C zachodzi sytuacja przedstawiona w punkcie 3) – każdy element A jest elementem C, a więc A zawiera się w C. Z podobną sytuacją mamy do czynienia w przypadku zbiorów A i D – A zawiera się w D.
Następnie przechodzimy do zbadania, w jakich zależnościach do innych zbiorów pozostaje B. Ponieważ stosunek pomiędzy B i A już znamy, zaczynamy od B i C. Po odrzuceniu dwóch pierwszych możliwości widzimy, że każdy element B jest również elementem C, a zatem B zawiera się w C. W przypadku zbiorów B i D widzimy, że nie są one na pewno identyczne ani rozłączne; nie jest też tak, aby każdy element jednego był elementem drugiego. A zatem zbiory te muszą się krzyżować. Faktycznie mają one element wspólny – 2, ale jest też taki element który jest tylko w B – 3 oraz elementy będące tylko w D – 1 i 4. Pozostało nam jeszcze określenie stosunku pomiędzy zbiorami C i D. Tutaj widzimy, że każdy element D jest elementem C. A więc zbiór D zawiera się w C. Pamiętamy, że w przypadku inkluzji istotne jest, który zbiór zawiera się w którym, a więc piszemy: D Í C. Ostateczne rozwiązanie zadania wygląda następująco:
A )( B, A Í C, A Í D, B Í C, B # D, D Í C
▲
Określimy stosunki pomiędzy następującymi zbiorami:
A – zbiór studentów prawa,
B – zbiór studentów,
C – zbiór studentów dziennych,
D – zbiór studentów matematyki.
W przypadku zbiorów A i B już na pierwszy rzut oka widać, że każdy element A jest elementem B (każdy student prawa jest studentem), a więc A zawiera się w B. W odniesieniu do zbiorów A i C odrzucamy pierwsze trzy możliwości, co świadczy, że zbiory te się krzyżują. Faktycznie mają one elementy wspólne: dziennych studentów prawa, ale są też obiekty będące elementami tylko zbioru A (zaoczni studenci prawa) oraz będące elementami tylko C (studenci dzienni innego niż prawo kierunku – np. filozofii). W przypadku zbiorów A oraz D z powodu braku danych empirycznych trudno dać jednoznaczną odpowiedź. Albo jest tak, że zbiory te są rozłączne (jeśli żaden student prawa nie studiuje jednocześnie matematyki), albo też, jeśli znajdzie się choć jedna osoba studiująca oba te kierunki, zbiory te się krzyżują. Zauważmy, że jeśli będziemy rozpatrywać wszystkich studentów na całym świecie, to zapewne zbiory te się krzyżują, jeśli natomiast ograniczymy nasze rozważania do jakiegoś wybranego niewielkiego uniwersytetu, to mogą być one rozłączne. Na pewno natomiast nie są to zbiory identyczne, ani też jeden z nich nie zawiera się w drugim.
Jeśli chodzi o zbiór B i C oraz B i D, to w każdym z tych przypadków zachodzi inkluzja. Pamiętamy jednak o właściwej kolejności: to C zawiera się B (każdy student dzienny jest studentem) oraz D zawiera się w B (każdy student matematyki jest studentem) a nie na odwrót. W przypadku zbiorów C i D zachodzi krzyżowanie – istnieją dzienni studenci matematyki, a także dzienni studenci innych kierunków, oraz zaoczni studenci matematyki.
Ostateczna odpowiedź, to zatem:
A Í B, A # C, A )( D lub A # D, C Í B, D Í B, C # D.
5.2.3. UTRUDNIENIA I PUŁAPKI.
Pomiędzy zbiorami może zachodzić jeszcze jeden stosunek, trochę innego typu niż omówione wyżej. Może się mianowicie zdarzyć tak, że jeden zbiór sam jest elementem innego zbioru, czyli: A Î B. Aby tak było, zbiór B musi szczególnym rodzajem zbioru – takim, którego elementy (przynajmniej niektóre) są zbiorami. Sytuacja taka zachodzi na przykład w stosunku do następujących zbiorów: A – zbiór kanarków, B – zbiór, którego elementami są zbiory ptaków poszczególnych gatunków.
Bardzo istotne jest, aby nie mylić zawierania się zbiorów, czyli zależności A Í B oraz bycia elementem (należenia), czyli A Î B. Pierwsza zależność, inkluzja (Í), oznacza, że każdy element zbioru A jest również elementem zbioru B. Należenie (Î) natomiast, oznacza, że sam zbiór A, jako całość, jest elementem zbioru B. W przypadku przedstawionych wyżej zbiorów A nie zawiera się w B, bo nie jest tak, aby każdy kanarek (elementy A) był jednocześnie zbiorem ptaków jakiegoś gatunku (elementy B). Natomiast A jako całość (czyli zbiór kanarków), jest jednym z elementów B.
Stosunek należenia (jeśli zachodzi), jest zależnością, która występuje niejako obok „zwykłych”, omawianych wyżej relacji między zbiorami. Znaczy to, że pewien zbiór A należąc do zbioru B (będąc elementem B) może jednocześnie być z nim rozłączny, zawierać się w nim lub krzyżować.
Zobaczmy w jakich stosunkach pozostają do siebie zbiory:
A = {a, b},
B = { {a, b}, {c, d, e} },
C = {a, b, c, d, e},
D = {a, b, {a, b} },
E = {a, d, e, {a, b} }
Zbiory A i B nie mają wspólnych elementów, ponieważ elementami A są „zwykłe” obiekty a oraz b, natomiast elementami B są zbiory. Tak więc A i B są rozłączne. Jednocześnie jednak zbiór A sam jest jednym z elementów zbioru B. W przypadku A oraz C sprawa jest oczywista: każdy element A jest elementem C, a zatem A zawiera się w C. Porównując A oraz D widzimy, że każdy element A jest elementem D. D ma jednak również trzeci element będący zbiorem; a ten zbiór, to nic innego, jak A. A zatem A zawiera się w D i jednocześnie należy do D. Jeśli chodzi o zbiory A i E, to mają one jeden element wspólny (a), ale też każdy z nich ma też takie elementy, których nie ma w drugim (b w zbiorze A oraz d, e i {a, b} w zbiorze E. Tak więc zbiory te się krzyżują. Równocześnie jednak A sam jest jednym z elementów E.
Porównując B oraz C już na pierwszy rzut oka widzimy, że nie mogą mieć one żadnego wspólnego elementu, ponieważ elementami B są zbiory, natomiast elementami C „zwykłe” obiekty. Tak więc B i C są rozłączne. Zbiory B i D mają jeden wspólny element: zbiór {a, b}. Jednocześnie w B jest element, którego nie ma D – zbiór {c, d, e}, natomiast w D elementy, których nie ma w B – a, b. Zbiory B i D się zatem krzyżują. Analogiczna sytuacja zachodzi w przypadku B i E.
Nie powinno nikomu sprawić trudności zauważenie, że krzyżują się również zbiory C i D, C i E oraz D i E.
Ostateczne rozwiązanie, to zatem:
A )( B i A Î B, A Í C, A Í D i A Î D, A # E i A Î E,
B )( C, B # D, B # E,
C # D, C # E,
D # E.
Zadanie:
Określimy zależności pomiędzy następującymi zbiorami.
A – zbiór studentów, którzy zdali logikę na 5,
B – zbiór studentów, którzy zdali logikę na 3,
C – zbiór studentów leniwych,
D – zbiór, którego elementami są zbiory studentów, którzy zdali logikę na taką samą ocenę.
Zbiory A i B są rozłączne (oczywiście przy założeniu, że nikt nie zdawał logiki dwukrotnie, na przykład „za kolegę”). A i C się krzyżują: na pewno są studen...
jelonka72