Wykład drugi



Pobieranie 67.46 Kb.
Data02.05.2016
Rozmiar67.46 Kb.




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ść. wy­raż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: xA - x jest elementem zbioru A, x należy do A


Nienależenie elementu do zbioru: xA - x nie jest elementem zbioru A, x nie należy do A. Zachodzi: xA  (xA)  xA
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: xA  xB; x A  B xA  xB



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: xA  xB; x A  B xA  xB


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: xA  xB; x A  B  x A  xB


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; xV  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: xA; xA’  xA


Właściwości dopełnienia zbioru:

xA’  xV  xA  xV  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 (xA  xB)
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    AB    BA  ]



2. Prawa teorii mnogości
1) (A’)’ = A

Dopełnienie dopełnienia zbioru A jest identyczne ze zbiorem A

Dowód:

a) x(A’)’  xA’ - na podstawie definicji dopełnienia zbioru



b) xA’  xA’ - na podstawie definicji nie należenia elementu do zbioru

c) xA’  (xA) - na podstawie definicji dopełnienia zbioru

d) (xA)  xA - na podstawie prawa podwójnej negacji

e) x(A’)’  xA - 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  (AB) = 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} XR(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: xA, yB

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) : xX  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 (pod­stawiania 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 



©absta.pl 2016
wyślij wiadomość

    Strona główna