Wykład drugi
Temat IV.1
Logika i matematyka
Wprowadzenie do teorii mnogości
Tworząc teorię mnogości G. Cantor - inaczej niż Euklides - nie podał żadnych aksjomatów czy postulatów, lecz sformułował definicje głównych jej pojęć: zbioru, liczby kardynalnej, równoliczności, zbioru uporządkowanego i typu porządkowego. W książce, która była systematyzacją i podsumowaniem uzyskanych wcześniejszych wyników, Cantor pisze:
Przez ‘zbiór’ rozumiemy każde zebranie w jedną całość M określonych, dobrze odróżnionych przedmiotów m naszej naoczności albo naszego myślenia (które są nazywane ‘elementarni’ [zbioru] M) Beiträge zur Begründung der transfiniten Mengelehre(1895-1897).
Intuicyjna teoria zbiorów
Zbudowana przez Georga Cantora w latach 1871-1883 teoria mnogości operuje dwoma pojęciami pierwotnymi: pojęciem zbioru oraz relacji bycia elementem (należenia). Zbiór dany jest enumeracją elementów lub ogółem obiektów, którym na wspólna własność.. W pierwszym przypadku nazwy elementów zapisuje się w nawiasie klamrowym, np.
{ a1, a2, ... , an}, dla n-elementowego zbioru, gdy n > 1 jest liczbą naturalną.
W drugim przypadku zbiór jest ogółem obiektów, które posiadają własność. wyrażoną funkcją zdaniową jednej zmiennej x,
(1) Zφ={x: φ(x)}
Założenie, że dla dowolnej funkcji zdaniowej φ(x) istnieje zbiór Z postaci (1), tj. zbiór elementów spełniających tę funkcję nazywane jest aksjomatem abstrakcji.
G. Malinowski Logika ogólna, s. 166
------------------------------------
1. Terminologia i definicje
A, B, C … - zmienne przebiegające zbiory
x - nazwa (dowolnego) przedmiotu
W(x) – funkcja zdaniowa o zmiennej wolnej x
{x: W(x)} – operator abstrakcji; {x: } wiąże zmienną x
y{x: W(x)} – y jest elementem zbioru takich x, że zachodzi W(x)
Prawo eliminacji operatora abstrakcji
y{x: W(x)} W(y)
Relacje między elementami a zbiorami:
Należenie elementu do zbioru: xA - x jest elementem zbioru A, x należy do A
Nienależenie elementu do zbioru: xA - x nie jest elementem zbioru A, x nie należy do A. Zachodzi: xA (xA) xA
Działania na zbiorach, ich określenie
A B - suma zbiorów A i B; sumą zbiorów A i B jest zbiór tych i tylko elementów, które należą do zbioru A lub należą do zbioru B
A B = x: xA xB; x A B xA xB
A B - iloczyn zbiorów A i B; iloczynem zbiorów A i B jest zbiór tych i tylko elementów, które należą do zbioru A i należą do zbioru B
A B = x: xA xB; x A B xA xB
A B - różnica zbiorów A i B; różnicą zbiorów A i B jest zbiór tych i tylko elementów zbioru A, które nie są elementami zbioru B
A B = x: xA xB; x A B x A xB
Różnica symetryczna dwóch zbiorów: A (A
V - zbiór uniwersalny; zbiór pełny, zbiór wszystkich przedmiotów
V = x: x = x; xV x = x
- zbiór pusty
= x: x x; x x x
Właściwości zbioru pustego:
x (x) x (x x)
x (x) - żaden przedmiot nie jest elementem zbioru pustego
A’ - dopełnienie zbioru A; dopełnieniem zbioru A jest zbiór tych i tylko przedmiotów, które nie są elementami zbioru A
A’ = x: xA; xA’ xA
Właściwości dopełnienia zbioru:
xA’ xV xA xV A
Relacje między zbiorami
Równość (identyczność) zbiorów: A = B
Zasada ekstensjonalności: A = B x (xA x B); zbiory identyczne składają się z tych samych elementów.
Różność (nierówność) zbiorów: A B
Zbiory A i B są różne wtedy i tylko wtedy, gdy nie są równe (identyczne).
A B – relacja inkluzji; zbiór A zawiera się w zbiorze B; zbiór A jest podzbiorem zbioru B; zbiór A jest częścią zbioru B.
Zbiór A zawiera się w zbiorze B wtedy i tylko wtedy, gdy każdy element zbioru A jest elementem zbioru B: A B x (xA xB)
Właściwości zawierania się zbiorów: A B x (xA xB)
A B – inkluzja właściwa; zbiór A jest podzbiorem właściwym zbioru B wtedy i tylko wtedy, gdy każdy element zbioru A jest elementem zbioru B, ale istnieje taki element zbioru B, który nie jest elementem zbioru A.
A B A B A B
Rozłączność zbiorów A i B: A)(B
Zbiory A i B są rozłączne wtedy i tylko wtedy, gdy nie mają elementów wspólnych.
A)(B (A B =)
Krzyżowanie się zbiorów A i B: A   
Zbiory A i B krzyżują się wtedy i tylko wtedy, gdy mają pewne elementy wspólne, ale ponadto, gdy każdy z nich ma elementy, które nie należą do drugiego z tych zbiorów.
A  B [(A B AB BA ]
2. Prawa teorii mnogości
1) (A’)’ = A
Dopełnienie dopełnienia zbioru A jest identyczne ze zbiorem A
Dowód:
a) x(A’)’ xA’ - na podstawie definicji dopełnienia zbioru
b) xA’ xA’ - na podstawie definicji nie należenia elementu do zbioru
c) xA’ (xA) - na podstawie definicji dopełnienia zbioru
d) (xA) xA - na podstawie prawa podwójnej negacji
e) x(A’)’ xA - na podstawie prawa przechodniości równoważności
2) A B B’ A’
Zbiór A zawiera się w zbiorze B wtedy i tylko wtedy, gdy dopełnienie zbioru B zawiera się w dopełnieniu zbioru A.
Dowód na podstawie: definicji zawierania się zbiorów, prawa transpozycji prostej i definicji dopełnienia zbioru.
3) A = B A’ = B’
Zbiory są identyczne wtedy i tylko wtedy, gdy ich dopełnienia są identyczne.
4) A = B’ B = A’
Zbiór A jest dopełnieniem zbioru B wtedy i tylko wtedy, gdy zbiór B jest dopełnieniem zbioru A.
5) (AB)’ A’ B’ - prawo de Morgana dla sumy zbiorów
Dopełnienie sumy dwóch zbiorów jest równe iloczynowi dopełnień tych zbiorów.
6) (A B)’ A’ B’ - prawo de Morgana dla iloczynu zbiorów
Dopełnienie iloczynu dwóch zbiorów jest równe sumie dopełnień tych zbiorów.
7) AA’ V
8) A V
Dowolny zbiór jest zawarty w zbiorze uniwersalnym.
9) A V = A
Iloczyn dowolnego zbioru A i zbioru uniwersalnego jest równy zbiorowi A.
Zbiór uniwersalny odgrywa w teorii mnogości przy mnożeniu zbiorów rolę analogiczną do liczby 1 przy mnożeniu liczb, gdzie a 1 = a.
10) A
Zbiór pusty jest podzbiorem dowolnego zbioru.
11) A = A
Suma dowolnego zbioru A i zbioru pustego jest równa zbiorowi A.
Zbiór pusty odgrywa przy dodawaniu zbiorów rolę analogiczną do liczby 0 przy dodawaniu liczb, gdzie a + 0 = a.
12) V’ =
Dopełnieniem zbioru uniwersalnego jest zbiór pusty.
13) ’= V
Dopełnieniem zbioru pustego jest zbiór uniwersalny.
Inne prawa
A = A (A B)
A = (A B) (A B’)
A = A (A B)
A B A B = B A B = A
A B A B’ =
A B’ A B =
A B’ A B = V
A B = A (B A)
A B = A (A B)
A B = A (A B)
A B = A B’
A (AB) = A (A B) = A - prawo pochłaniania
A=B [(A B’) (A’ B) = ]
A= [(A B’) (A’ B) = B]
Rodzina zbiorów
A – zbiór
Definicja
Rodziną zbioru A jest zbiorem podzbiorów tego zbioru. Oznaczamy ją przez R(A)
R(A) = {X: X A} XR(A) X A
Rodziny zbiorów to zbiory zbiorów, tj. są to takie zbiory, których wszystkie elementy są zbiorami.
3. Iloczyn kartezjański zbiorów
A, B, C, D – zbiory
x A, y B, z C, u D
Definicja. Para uporządkowana x, y o pierwszym elemencie x i drugim elemencie y:
x, y x, x, y
Właściwości par uporządkowanych:
1) ( x, y = z, u) (x = z y = u)
Pary uporządkowane są identyczne wtedy i tylko wtedy, gdy ich pierwsze elementy są ze sobą identyczne i ich drugie elementy są ze sobą identyczne.
2) y, x x, y , zachodzi bowiem x, x, y y, y, x
3) ( x, y z, u ) (x z y u)
Dwie pary uporządkowane są różne wtedy i tylko wtedy, gdy ich pierwsze elementy są od siebie różne lub ich drugie elementy są od siebie różne.
- trójka uporządkowana: x, y, z : x A, y B, z C
- układ uporządkowany o n-elementach: x1, x2, … , xn > : xi Xi
Definicja
A x B - iloczyn kartezjański zbiorów A i B to zbiór wszystkich par
uporządkowanych: x, y, gdzie x A, y B
A x B = x, y: xA, yB
Jeśli A = B, piszemy: A2 = A x A, ogólnie: An = A x A x … x A (n razy)
Przykłady
R – zbiór liczb rzeczywistych
R 2 = R x R
R 3 = R x R x R,
1) R 2 = R x R – płaszczyzna; x, y: x, y R
2) R 3 = R x R x R – przestrzeń 3-wymiarowa: x, y, z : x, y, z R
3) R 4 = R x R x R x R – przestrzeń euklidesowa 4-wym.: x, y, z, v : x, y, z, v R
Rys. Iloczyn kartezjański zbiorów A i B
Właściwości iloczynu kartezjańskiego zbiorów
1) (A B) x C = (A x C) (B x C)
2) (A B) x C = (A x C) (B x C)
3) (A B) x (C D)= (A C) x (B D)
Jeżeli C A, D B, to:
4) (C x D) = (C x B) (A x D)
5) (C x D)’ = (C’ x B) (A x D')
Zapis funkcji za pomocą iloczynu kartezjańskiego
X - dziedzina funkcji; Y - przeciwdziedzina funkcji
f - funkcja (matematyczna); f: X Y, y x y = f (x)
Funkcja f jako podzbiór iloczynu kartezjańskiego dziedziny i przeciwdziedziny (X x Y):
f X x Y, gdzie X x Y = x, f (x) : xX f(x)Y
x, f (x) f y = f (x)
f = x, f (x)
4. Algebra Boole’a zbiorów
Terminologia
A, B, C, A’ – zbiory
1 – V (zbiór uniwersalny)
0 – (zbiór pusty)
Algebrą Boole'a zbiorów jest aksjomatyczny system teorii mnogości, zbudowany w oparciu o następujące aksjomaty:
l) A B
2) A B
3) A (B
4) A (B
5) A (B )
6) A (B )
7) A 0
8) A 1
9) A A’
10) A A’
Na podstawie aksjomatów 1-10 można, stosując reguły dowodowe (podstawiania i zastępowania) udowodnić każde prawo teorii mnogości.
Na podstawie tych aksjomatów można też wprowadzić, za pomocą odpowiednich definicji dalsze działania nazw zbiorach oraz relacje między zbiorami, np.
A – B A B’
A )( B A B

|