Andrzej Wiśniewski
Logika I
Materiały do wykładu dla studentów kognitywistyki
Wykład 1. Wprowadzenie do rachunku zbiorów
1
Podstawowe pojęcia rachunku zbiorów
Uwaga 1.1. W teorii mnogości mówimy o zbiorach w sensie dystrybu-
tywnym; rachunek zbiorów jest fragmentem teorii mnogości.
Pojęcia bycia zbiorem oraz należenia do zbioru są pojęciami
pierwotnymi; nie są one (wprost) definiowane, lecz ich sens określają
łącznie aksjomaty teorii mnogości.
Piszemy:
Zbiór(x) dla wyrażenia tego, że x jest zbiorem,
x " A dla wyrażenia tego, że (przedmiot, obiekt,
indywiduum) x należy do zbioru A.
Gdy x " A, mówimy też, że x jest elementem zbioru A.
Uwaga 1.2. Rozróżnienie między indywiduami a zbiorami nie ma charak-
teru absolutnego. W szczególności, zbiory mogą być ele-
mentami (należeć do) innych zbiorów.
2
Jak określamy zbiory?
Mamy dwa podstawowe sposoby określania zbioru:
1. sporządzenie listy elementów określanego zbioru.
Notacja: {a1, a2, ..., an} oznacza zbiór, którego elementami są
obiekty a1, a2, ..., an i żadne inne.
{a} oznacza zbiór, którego jedynym elementem jest
obiekt a (zbiór tego rodzaju nazywamy zbiorem jednost-
kowym lub singletonem).
Przykład 1.1. {Zielona Góra, Gorzów Wielkopolski}
Przykład 1.2. {1, 3, 5, 7}
Przykład 1.3. {1, 3, {5, 7}}
Dygresja 1.1. Zbiór {1, 3, 5, 7} ma cztery elementy, natomiast zbiór
{1, 3, {5, 7}} ma trzy elementy. Dlaczego?
Uwaga 1.3: Elementy listy powinny desygnować różne obiekty. Gdy,
przykładowo, napiszemy {1, 2, 1}, jest to używając
eufemizmu - pretensjonalny opis zbioru {1, 2}.
3
Jak określamy zbiory?
2. podanie warunku, który spełniają te i tylko te obiekty, które
są elementami określanego zbioru.
Notacja: {x : Ś(x)} oznacza zbiór wszystkich x-ów takich, że Ś(x)
Przykład 1.4. {x : x jest studentem 1-go roku kognitywistyki}
- zbiór wszystkich studentów 1-go roku kognitywistyki
Przykład 1.5. {x : x jest liczbą naturalną i x jest podzielne przez 2}
- zbiór wszystkich liczb naturalnych parzystych
Przykład 1.6. {x : x jest mężczyzną w ciele kobiety}
Dygresja 1.2. Czasami zamiast dwukropka używamy kreski |. Tak więc
napisy {x : Åš(x)} oraz {x | Åš(x)} majÄ… to samo znaczenie.
4
Jak określamy zbiory?
Dygresja 1.3. Gdy pragniemy scharakteryzować pewien podzbiór uprzed-
nio scharakteryzowanego zbioru, czasami umieszczamy odniesienie do
tego zbioru przed dwukropkiem/kreską. Przykładowo, napisy:
{x " N : x jest podzielne przez 2}
{x : x jest liczbÄ… naturalnÄ… i x jest podzielne przez 2}
oznaczają ten sam zbiór, tj. zbiór liczb naturalnych parzystych.
Dygresja 1.4. Zbioru nieskończonego nie możemy scharakteryzować po-
przez podanie listy jego wszystkich elementów. Niektóre zbiory skoń-
czone możemy jednak scharakteryzować zarówno poprzez podanie li-
sty, jak i poprzez podanie warunku. Przykładowo, zbiór {1, 3, 5, 7}
można również określić następująco:
{x: x jest nieparzystą liczbą całkowitą dodatnią mniejszą od 9}
5
Zasada ekstensjonalności
Notacja: wyrażenie wtw jest skrótem zwrotu wtedy i tylko wtedy, gdy .
Następujące podstawowe zasady są albo aksjomatami teorii mno-
gości, albo konsekwencjami jej aksjomatów:
ZASADA EKSTENSJONALNOÅšCI: Zbiory A oraz B sÄ… identyczne wtw
mają one dokładnie te same elementy; symbolicznie:
A = B wtw "x (x " A "! x " B).
Mówiąc swobodnie, wynika stąd, że określić zbiór to tyle, co określić, z
jakich przedmiotów się on składa.
Przykład 1.7. Niech:
A = {x : x jest prostokątem równobocznym}
B = {x : x jest kwadratem}
Zbiory A oraz B sÄ… identyczne (tj. A = B).
6
Zasada dystrybutywności
ZASADA DYSTRYBUTYWNOŚCI: Żaden zbiór nie jest identyczny z
żadnym ze swoich elementów; symbolicznie:
Ź("y "x (Zbiór(x) '" y " x '" x = y))
Intuicyjnie rzecz biorąc, zbiór pusty to zbiór nie mający żadnego
elementu. Pojęcie to można ściśle zdefiniować następująco:
Definicja 1.1 (zbiór pusty) Zbiorem pustym nazywamy zbiór:
{x : x = x '" Ź(x = x)}.
Zbiór pusty oznaczamy symbolem ".
Wniosek 1.1. Następujące zbiory:
", {"}, {{"}}, {{{"}}}, {{{{"}}}}, ...
są różne między sobą.
7
Inkluzja zbiorów
Inkluzję zbiorów (inaczej: zawieranie się zbiorów) definiujemy następu-
jÄ…co:
Definicja 1.2. (inkluzja) Zbiór A zawiera się w zbiorze B wtw każdy ele-
ment zbioru A jest też elementem zbioru B; symbolicznie:
A Ä…" B wtw "x(x " A x " B)
Definicja 1.3. (podzbiór) Zbiór A jest podzbiorem zbioru B wtw A ą" B.
Dygresja 1.5. Zbiór pusty jest podzbiorem każdego zbioru. Dlaczego?
Przykład 1.8. Zbiór wszystkich mężczyzn jest podzbiorem zbioru
wszystkich ludzi.
Przykład 1.9. Zbiór wszystkich ludzi jest podzbiorem zbioru wszystkich
ludzi.
Wniosek 1.2. Każdy zbiór jest swoim własnym podzbiorem
- albowiem "x(x " A x " A)
8
Inkluzja właściwa
Definicja 1.3. (inkluzja wÅ‚aÅ›ciwa) A ‚" B wtw A Ä…" B '" Ź(A = B)
Definicja 1.4. (podzbiór właściwy) Zbiór A jest podzbiorem właściwym
zbioru B wtw A ‚" B.
Wniosek 1.3. Jeżeli A ‚" B, to "x (x " B '" Ź(x " A)).
Przykład 1.10. Zbiór wszystkich mężczyzn jest podzbiorem właściwym zbioru
wszystkich ludzi.
OSTRZEŻENIE: Długoletnia posługa dydaktyczna wśród humanistów
nauczyÅ‚a mnie, że znaki " oraz ‚" (czy Ä…") sÄ… nagminnie mylone, co
znaczy, że nie dostrzega się różnicy między należeniem elementu do
zbioru a zawieraniem się zbioru w zbiorze. Jest to poważny błąd! Z
pewną taką rezygnacją zwracam więc uwagę, że napisy typu:
1 ‚" {1, 2, 3}
1 " 1
nie majÄ… sensu!!!
9
Krzyżowanie się zbiorów i rozłączność zbiorów
Definicja 1.5. (krzyżowanie się zbiorów)
Zbiór A krzyżuje się ze zbiorem B wtw
(i) "x (x " A '" x " B),
(ii) "y (y " A '" Ź(y " B)), oraz
(iii) "z (z " B '" Ź(z " A)).
Przykład 1.11. Zbiór wszystkich leni krzyżuje się ze zbiorem wszystkich
studentów.
Przykład 1.12. Następujące zbiory A i B krzyżują się:
A = {1, 2, 3}
B = {2, 3, 4}
Definicja 1.6. (rozłączność zbiorów) Zbiory A oraz B są rozłączne wtw
Ź"x (x " A '" x " B).
Przykład 1.13. Zbiór wszystkich liczb całkowitych dodatnich jest rozłączny
ze zbiorem wszystkich liczb całkowitych ujemnych.
10
Twierdzenie 1.1. Niech A i B będą dowolnymi zbiorami. Wówczas:
(i) A i B są rozłączne lub
(ii) A jest identyczny z B lub
(iii) A jest podzbiorem właściwym B lub
(iv) B jest podzbiorem właściwym A lub
(v) A krzyżuje się z B.
Komentarz zostanie podany na wykładzie :)
11
Zbiór potęgowy
Terminologia: Zbiór zbiorów (tj. zbiór, którego elementami są zbiory)
nazywamy rodziną zbiorów.
Definicja 1.7. Rodzinę wszystkich podzbiorów danego zbioru A nazywamy
zbiorem potęgowym zbioru A i oznaczamy symbolem 2A.
Tak więc 2A = {X : X ą" A}.
Przykład 1.14. Niech A = {1, 2, 3}. Mamy wówczas:
2A = {", {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
Twierdzenie 1.2. Jeżeli zbiór A jest skończony i ma n elementów, to zbiór
potęgowy zbioru A ma 2n elementów.
12
Równoliczność zbiorów
Przypomnienie: Jeżeli przekształcenie f zbioru A w zbiór B jest funkcją, to
każdemu elementowi x zbioru A odpowiada dokładnie jeden element
f(x) zbioru B.
Terminologia: Funkcja f jest wzajemnie jednoznaczna, jeżeli dla różnych
argumentów przyjmuje ona zawsze różne wartości, tj. zachodzi f(x) =
f(y) x = y.
Definicja 1.8. (równoliczność zbiorów). Dwa zbiory A i B są równoliczne
wtw istnieje funkcja wzajemnie jednoznaczna f, która odwzorowuje
zbiór A na zbiór B. O funkcji takiej mówimy, że ustala ona równolicz-
ność zbiorów A i B. O zbiorach równolicznych mówimy natomiast, że
są one równej mocy.
Przykład 1.15. Niech A = {1, 3, 5} oraz B = {2, 4, 6}. Funkcja f: A | B określona
następująco:
f(x) = x +1
ustala równoliczność zbiorów A i B.
13
Zbiory skończone i nieskończone
Przykład 1.16. Niech N będzie zbiorem liczb naturalnych, a N2 zbiorem
liczb naturalnych parzystych. Funkcja f: N | N2 określona następują-
co:
f(x) = 2x
ustala równoliczność zbiorów N i N2.
Wniosek 1.4. Zbiór liczb naturalnych jest równoliczny z pewnym swoim
podzbiorem właściwym.
Definicja 1.9 (zbiór nieskończony w sensie Dedekinda).
Zbiór A jest nieskończony wtw zbiór A jest równoliczny z jakimś
swoim podzbiorem właściwym; w przeciwnym przypadku zbiór A jest
skończony.
Wniosek 1.5. Zbiór pusty jest skończony.
14
Zbiory skończone i nieskończone
Definicja 1.10. (zbiór przeliczalny) Zbiór A jest przeliczalny wtw zbiór A
jest skończony lub zbiór A jest równoliczny ze zbiorem liczb natural-
nych.
Lemat 1. Przedział (0, 1) nie jest przeliczalny.
Wniosek 1.6. Istnieją zbiory nieskończone różnych mocy.
Lemat 2. Przedział (0, 1) jest równoliczny ze zbiorem liczb rzeczywistych.
Twierdzenie 1.3. Zbiór liczb rzeczywistych jest nieskończony, ale nie jest
równoliczny ze zbiorem liczb naturalnych.
Twierdzenie 1.4. Dla dowolnego zbioru A, moc zbioru 2A (tj. zbioru
potęgowego zbioru A) jest większa od mocy zbioru A.
15
Addendum: antynomia Russella
Niech Z =df {X : Ź(X " X)}. Zapytajmy, czy Z " Z ?
Załóżmy, że Z " Z. Wówczas na mocy definicji zbioru Z dostajemy:
Ź(Z " Z).
Załóżmy, że Ź(Z " Z). Wówczas na mocy definicji zbioru Z dostajemy:
Z " Z.
Mamy zatem dwie implikacje:
Z " Z Ź(Z " Z)
Ź(Z " Z) Z " Z
skąd dostajemy Z " Z "! Ź(Z " Z)
co na mocy KRZ daje Z " Z '" Ź(Z " Z)
czyli sprzeczność !!
W aksjomatycznych systemach teorii mnogości sprzeczność ta jest blo-
kowana na różne wyrafinowane sposoby o czym kiedy indziej.
16
Literatura:
Poruszane na tym wykładzie zagadnienia mają (poza równoliczno-
ścią zbiorów i zbiorami nieskończonymi) charakter czysto propedeu-
tyczny i jako takie są one omówione w prawie każdym podręczniku lo-
giki lub teorii mnogości. Z nowszych (a więc łatwiej dostępnych) pozycji
można wymienić:
[1] Roman Murawski, Kazimierz Świrydowicz: Wstęp do teorii mnogo-
ści, Wydawnictwo Naukowe UAM, Poznań 2005.
[2] Barbara Stanosz: Wprowadzenie do logiki formalnej, Wydawnictwo
Naukowe PWN, Warszawa 1999 (jest to jedno z licznych wydań tej po-
zycji).
[3] Ryszard Wójcicki: Wykłady z logiki z elementami teorii wiedzy, Wy-
dawnictwo Naukowe Scholar, Warszawa 2003.
Dowody lematu 1, lematu 2 oraz twierdzenia 1.4 można znalezć
m.in. w książce [1]. Bardzo sympatyczne (i pełniejsze) ujęcie bardziej
17
zaawansowanych zagadnień poruszanych na tym wykładzie znajduje
się w części pierwszej podręcznika:
[4] Geoffrey Hunter, Metalogika, Państwowe Wydawnictwo Naukowe,
Warszawa 1982.
18
Wyszukiwarka
Podobne podstrony:
01 podstawowe pojeciaMatematyka dyskretna 2004 01 Podstawowe pojęcia, oznaczenia01 wprowadzenie do teorii eksploatacji statkow powietrznych podstawowe pojecia i definicjeid)9001 PODSTAWY RACHUNKU PRAWDOPODOBIENSTWA01 podstawyrachunek zbiorow 21 podstawowe pojecia zwiazane z ekologia01 Podstawy języka UML 2 0469 W02 SKiTI wprowadzenie podstawowe pojeciaMateriały do terminologii więźb dachowych podstawowe pojęcia, cz 1Posługiwanie się podstawowymi pojęciami z zakresu obróbki plastycznejwięcej podobnych podstron