WYKŁAD 1: ZBIORY I DZIAŁ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.
• Jeśli a jest obiektem, A jest zbiorem- piszemy a∈A , ż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≠0 i 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
•
A={ x∈ℝ : x 22}
•
B={studenci I roku informatyki : są obecni na I zjeździe }
•
[ a , b]={ x∈ℝ : a≤ x≤ b}
•
( a , b ]={ x∈ℝ : a x≤ b}
•
[ a , b )={ x ∈ℝ : a≤ x b}
•
a , b={ x ∈ℝ : a x b}
•
[ a , ∞ )={ x∈ℝ : x≥ 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 , to x ∈ B , i jeśli x ∈ B to x ∈ A.
np.: { a , a}={ a}
{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 , to x ∈ B.
Zbiór A jest nazywany wtedy podzbiorem zbioru B. Zbiór B jest nadzbiorem zbioru A.
np.: { a}⊆{ a , { a }}
Wykład z logiki dla informatyków – przygotowała Joanna Karbowska – Chilińska 2
Jeśli A⊆ B i A≠ B to zbiór A jest podzbiorem właściwym zbioru B.
Zbiór A nie jest podzbiorem zbioru B piszemy wtedy A⊈ 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
Jeśli A jest zbiorem n-elementowym, to P A ma dokładnie 2 n 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∈ℕ: x≤11 }, B={ x∈ℕ: x jest nieparzysta i x≤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
A={ x∈ℕ: x≤11 }, B={ x∈ℕ: x jest nieparzysta i x≤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∈ℕ: x≤11 }, B={ x∈ℕ: x jest nieparzysta i x≤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:
A
B
A∖ B
B∖ A
A−. B= A ∖ B∪ B ∖ A
Przykład 6
A={ x∈ℕ: x≤11 }, B={ x∈ℕ: x jest nieparzysta i x≤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∈ℕ: n20} będzie ustaloną przestrzenią i niech A oraz B
będą podzbiorami takim, że:
A={3⋅ n1 : n∈ℕ , n2} i B={2⋅ n2 : n∈ℕ , n3}.
Wykład z logiki dla informatyków – przygotowała Joanna Karbowska – Chilińska 6
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
.
1 Prawo przemienności:
5.Prawo identyczności
a. AB=BA
a. A=A
.
b AB=BA
.
b AU=U,
U oznacza przestrzeń
.
2 Prawo łączności
c. A=
a.(AB)C=A(BC)
.
d AU=A,
.(
b AB)C=A(BC)
.
6 Prawo podwójnego dopełnienia
.
3 Prawo rozdzielności:
a.-(- )
A =A
a.A(BC)=(AB)(AC)
.
7 .
a A(-A)=U
.
b A(BC)=(AB)(AC)
.
b A(-A)=
.
4 Prawa idempotnentości
.
8 . -
a U=
a.AA=A
. -
b =U
.
b AA=A
.
9 Prawa d'Morgana
a. A (
\ BC)=(A\B)(A\C)
.
b A (
\ BC)=(A\B)(A\C)
c. -(AB)= (-A)(-B)
. -
d (AB) = -A-B
Przykład 8
Uzasadnimy, że (AB)(-A)⊆ B
Z definicji zawierania podzbiorów mamy pokazać, że jeśli x∈(AB)(-A) t
o x∈B
(AB)(-A)=(-A)(AB)
z prawa przemienności 1b
=(-AA)(-
A
)
B
z praw
a rozdzieności 3b
=(A-A)(-AB) z prawa przemienności 1b
Wykład z logiki dla informatyków – przygotowała Joanna Karbowska – Chilińska 7
z 7b
=(-AB)
z prawa przemienności 1a
= (-AB)
Zatem jeśli x∈(AB)(-A) to jest równoważne temu (z definicji równości zbiorów), że x∈(-AB), 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 1, t 1)=( s 2, t 2) wtedy i tylko wtedy gdy s 1= s2 i t 1 = t2.
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