WYKA
AD 1: ZBIORY I DZIAA
ANIA NA NICH
Zakres wykładu
1. Niektóre szczególne zbiory
2. Działania na zbiorach: suma, iloczyn, różnica, różnica symetryczna
3. Prawa algebry zbiorów
4. Iloczyn kartezjański
Teoria mnogości to dział logiki matematycznej zapoczątkowany przez
Cantora w XIX wieku. Dział ten zajmuje się różnymi zbiorami, które są
pojmowane jako kolekcje obiektów. Ogólne pojęcie zbioru i należenia do
niego jest przyjmowane jako pojęcie pierwotne (tzn. takie, które nie jest
definiowane)
Notacja:
" Zbiory będziemy oznaczać wielkimi literami- A, B, C.....
" Elementy (obiekty) zbiorów będziemy oznaczać małymi literami.
a"A ,
" Jeśli a jest obiektem, A jest zbiorem- piszemy że a jest
elementem zbioru A (należy do zbioru A)
" Jeśli a nie jest obiektem zbioru A - piszemy a "A ,
Oznaczenia zbiorów liczbowych:
" !
- zbiór liczb naturalnych {0,1,2,...}
" $! - zbiór liczb całkowitych {& .-1,0,1,2...}
" !
- zbiór liczb wymiernych
k
!= x"! : istniejÄ… k ,l "$! , l`"0i x=
{ }
l
" ! - zbiór liczb rzeczywistych, np.: 2,-Ćą ,e
ćą
" !
- zbiór liczb zespolonych np.: -2+5i
Schematy definiowania zbiorów
A={x" B : Wśąx źą} - zbiór włożony z elementów x "B mających pewną
własność W(x)
Wykład z logiki dla informatyków  przygotowała Joanna Karbowska  Chilińska 1
Przykład 1
{ }
" A= x"! : x2"Ä…2
" B={studenci I roku informatyki : sÄ… obecni na I zjez
dzie}
" [a ,b]={x"! : ad"xd"b}
" ( a , b ]={x"! : a"Ä… xd"b}
" [ a ,b )={x "! : ad"x"Ä…b}
" śąa ,bźą={x "! : a"ąx"ąb}
" [ a ," )={x"! : xe"a }
Zbiór, który nie ma żadnego elementu nazywamy zbiorem pustym i
oznaczamy ".
{a}
jest zbiorem, którego jedynym elementem jest a- tzw. singleton
elementu a.
Definicja równości zbiorów
A=B wttw. gdy dla każdego x, jeśli x " A, x "B , i jeśli x "B to
to
x " A.
{a , a}={a}
np.:
{1,1,1,2}={1,2}
{1,2}`"{{1,2}}
{"}`"".
Definicja zawierania się zbiorów
Aą"B oznacza to, że dla każdego x jeśli x " A, x "B.
to
Zbiór A jest nazywany wtedy podzbiorem zbioru B. Zbiór B jest
nadzbiorem zbioru A.
{a}Ä…"{a ,{a }}
np.:
Wykład z logiki dla informatyków  przygotowała Joanna Karbowska  Chilińska 2
A=B wttw. gdy AÄ…"B BÄ…"A.
i
Jeśli Aą"B i A`"B to zbiór A jest podzbiorem właściwym zbioru B.
śąpiszemy wtedy Aˆ"B źą
Zbiór A nie jest podzbiorem zbioru B wttw. gdy
istnieje taki element zbioru A, który nie należy do zbioru B.
Zbiór pusty jest podzbiorem każdego zbioru B, gdyż nie istnieje w ogóle
żaden element zbioru pustego, a więc tym bardziej żaden element, który
nie należy do B.
"Ä…"{"}.
np.:
Dla każdego skończonego zbioru A przez |A| oznaczamy liczbę jego
elementów (moc zbioru).
Definicja zbioru potęgowego
Zbiór potęgowy to rodzina wszystkich podzbiorów zbioru A
Pśą Aźą={X : X ą" A}.
Przykład 2
Pśą{a}źą={" ,{a }},
P śą{a , b ,c}źą={" ,{a}, {b},{c},{a ,b},{a ,c},{b ,c },{a ,b , c}}.
Twierdzenie 1
P śą Aźą
Jeśli A jest zbiorem n-elementowym, to ma dokładnie 2n
elementów.
Działania na zbiorach
Sumą A*"B zbiorów A i B nazywamy zbiór złożony z tych elementów,
które należą do co najmniej jednego spośród zbiorów A i B, to jest
Wykład z logiki dla informatyków  przygotowała Joanna Karbowska  Chilińska 3
x "A*"B wttw, gdy x " A lub x "B.
A*"B={x : x " A lub x "B}.
Diagram Venna dla sumy zbiorów:
A B
A*"B
Przykład 3
A={x"!: xd"11 }, B={x"!: x jest nieparzysta i xd"20}.
A*"B={0,1,2,3,4 ,5,6 ,7,8,9 ,10,11,13,15,17,19}.
Iloczynem (częścią wspólną lub przecięciem) A)"B zbiorów A i B
nazywamy zbiór złożony z tych elementów, które należą jednocześnie do
zbiorów A i B, to jest x "A)"B wttw, gdy x " A i x"B .
A)"B={x : x " A i x"B}.
Diagram Venna dla iloczynu zbiorów:
A
B
A)"B
Wykład z logiki dla informatyków  przygotowała Joanna Karbowska  Chilińska 4
Przykład 4
A={x"!: xd"11 }, B={x"!: x jest nieparzysta i xd"20}.
A)"B={1,3 ,5,7,9 ,11}.
Różnicą A" B zbiorów A i B nazywamy zbiór złożony z tych elementów,
które należą do zbioru A i nie należą do zbioru B, tzn. x " A" B wttw,
gdy x " A i x "B .
A" B={x : x"A i x " B}.
Diagram Venna dla różnicy zbiorów:
A
B
A" B
Przykład 5
A={x"!: xd"11 }, B={x"!: x jest nieparzysta i xd"20}.
A" B={0,2,4 ,6,8,10}.
B" A={13,15,17,19}.
.
Różnicą symetryczną zbiorów A i B nazywamy zbiór
A-B
zdefiniowany w następujący sposób:
.
x " A-B wttw. gdy, x "A " B lub x "B" A
Wykład z logiki dla informatyków  przygotowała Joanna Karbowska  Chilińska 5
Diagram Venna dla różnicy symetrycznej zbiorów:
B
A
A" B
B" A
.
A-B=śą A" Bźą*"śąB" Aźą
Przykład 6
A={x"!: xd"11 }, B={x"!: x jest nieparzysta i xd"20}.
.
{ }
A-B= 0,2,4,6 ,8,10 ,13,15,17,19 .
Dopełnienie zbioru
Często wygodnie jest używać ustalonego zbioru U, np.: takiego jak
! , ! nazywanego uniwersum lub przestrzeniÄ….
Dla zbioru Aą"U różnicę zbiorów zbiorów U " A nazywamy
dopełnieniem lub uzupełnieniem zbioru A i oznaczamy -A
U
- A
A
Przykład 7
Niech U ={n"!:n"ą20} będzie ustaloną przestrzenią i niech A oraz B
będą podzbiorami takim, że:
A={3Å"nƒÄ…1 : n"! , n"Ä…2} B={2Å"nƒÄ…2 : n"! , n"Ä…3}.
i
Wykład z logiki dla informatyków  przygotowała Joanna Karbowska  Chilińska 6
Wyznaczamy -A i -B .
A={1, 4} , - A={0,2,3 ,5,6,7 ,... ,19}
B={2, 4,6}, -B={0,1,3,5 ,7,8,9... ,19}.
Różnica zbiorów może być opisywana za pomocą dopełnienia:
A" B=A)"śą-Bźą.
Prawa algebry zbiorów
5.Prawo identyczności
1. Prawo przemienności:
a. A:á8á=A
a. A:áB=B:áA
b. A:áU=U, U oznacza przestrzeÅ„
b. A9áB=B9áA
c. A9á8á=8á
2. Prawo łączności
d. A9áU=A,
a.(A:áB):áC=A:á(B:áC)
6. Prawo podwójnego dopełnienia
b.(A9áB)9áC=A9á(B9áC)
a.-(-A)=A
3. Prawo rozdzielności:
7. a. A:á(-A)=U
a.A:á(B9áC)=(A:áB)9á(A:áC)
b. A9á(-A)=8á
b.A9á(B:áC)=(A9áB):á(A9áC)
8. a. -U=8á
4. Prawa idempotnentości
b. -8á=U
a.A:áA=A
9. Prawa d'Morgana
b.A9áA=A
a. A\(B:áC)=(A\B)9á(A\C)
b. A\(B9áC)=(A\B):á(A\C)
c. -(A:áB)= (-A)9á(-B)
d. -(A9áB) = -A:á-B
Przykład 8
Uzasadnimy, że (A:áB)9á(-A)Ä…" B
Z definicji zawierania podzbiorów mamy pokazać, że jeśli
x"(A:áB)9á(-A) to x"B
(A:áB)9á(-A)=(-A)9á(A:áB) z prawa przemiennoÅ›ci 1b
=(-A9áA):á(-A9áB) z prawa rozdzienoÅ›ci 3b
=(A9á-A):á(-A9áB) z prawa przemiennoÅ›ci 1b
Wykład z logiki dla informatyków  przygotowała Joanna Karbowska  Chilińska 7
= 8á:á(-A9áB) z 7b
=(-A9áB):á8á z prawa przemiennoÅ›ci 1a
= (-A9áB)
Zatem jeÅ›li x"(A:áB)9á(-A) to jest równoważne temu (z definicji
równoÅ›ci zbiorów), że x"(-A9áB), a to również oznacza, że x"B co
kończy uzasadnienie.
Para uporzÄ…dkowana
Rozważmy dwa zbiory S i T. Dla każdego elementu s"S i każdego
elementu t"T tworzymy parę uporządkowaną (s,t). Kolejność
uporzÄ…dkowania par jest istotna.
(s ,t )=(s ,t ) wtedy i tylko wtedy gdy s = s i t = t .
1 1 2 2 1 2 1 2
Zbiór wszystkich par uporządkowanych (s,t) nazywamy iloczynem
kartezjaÅ„skim zbiorów S i T i oznaczamy S )á T.
S )á T= {(s,t) : s"S i t"T}
Przykład 9
S={1,2,3}, T={a,b,c}
S )á T= {(1,a), (1,b), (1,c), (2,a), (2,b), (2,c), (3,a), (3,b), (3,c)}
T )á S= {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3), (c,1), (c,2), (c,3)}
Twierdzenie o mnożeniu
Jeśli zbiór S ma m elementów, a zbiór T ma n elementów, to liczba różnych
par uporządkowanych (s,t), takich że s"S i t"T wynosi m" n.
Iloczyn kartezjański jest wykorzystywany przy definiowaniu relacji
(zależności między elementami). Pojęcie relacji w informatyce jest
kluczowe w informatyce dla baz danych.
Wykład z logiki dla informatyków  przygotowała Joanna Karbowska  Chilińska 8