RACHUNEK ZBIORÓW
RACHUNEK ZBIORÓW
pojęcia zbioru i elementu
zbioru elementu
zbiór A zawiera element a
element a należy do zbioru A
a " A
a jest elementem zbioru A
a " A Ô! <" (a " A)
X  zbiór wszystkich przedmiotów indywidualnych, których dotyczy
dana nauka  zbiór pełny (uniwersalny)
pełny
A = X Ô! '"a " A
a
"  zbiór pusty
pusty
A = " Ô! <"("a " A Ô! '"a " A
a a
Zbiory wyznaczone przez funkcje zdaniowe
Zbiory wyznaczone przez funkcje zdaniowe
Symbol abstrakcji { x: P(x) }
oznacza zbiór tych i tylko tych elementów zbioru X, które spełniają
funkcjÄ™ zdaniowÄ… P(x).
O funkcji zdaniowej P(x) mówimy, że wyznacza zbiór {x:P(x)}.
Niech X = { 1, 2, 3, 5, 7, 9 }
A = {x"X: x>3} = { 5, 7, 9 }
" = { x: x `" x }
X = { x: x = x }
Matematyka Dyskretna
Barbara GÅ‚ut 1
Zdanie '"P(x) jest prawdziwe Ô! { x"X : P(x) } = X
x
("P(x)
Zdanie jest prawdziwe Ô! { x"X : P(x) } `""
x
'"P(x)
Zdanie jest faÅ‚szywe Ô! { x"X : P(x) } `" X
x
Zdanie jest faÅ‚szywe Ô! { x"X : P(x) } = "
("P(x)
x
'" <" P(x)
Zdanie jest prawdziwe Ô! { x"X: <"P(x) } =X
x
<"("P(x)
Ô! { x"X: P(x) } ="
x
(" <" P(x)
Zdanie jest prawdziwe Ô! { x"X: <"P(x) } `""
x
<" '"P(x)
Ô! { x"X : P(x) } `" X
x
Inkluzja
Inkluzja
Zbiór A jest zawarty w zbiorze B (A jest podzbiorem B) wtedy i tylko
wtedy, gdy każdy element zbioru A należy do zbioru B.
A Ä…" B Ô! '"(a " A Ò! a " B)
a
A Ä…" B Ô! ("(a " A '" a " B)
/
Zbiór A nie jest zawarty w B:
a
Zbiór A jest właściwie zawarty w zbiorze B (jest podzbiorem właściwym
zbioru B) wtedy i tylko wtedy, gdy jest zawarty w B, ale zbiór B nie
jest zawarty w A.
A ‚" B Ô! (A Ä…" B '" B Ä…" A)
/
Uwaga: AÄ…"A ale A""A
Inny zapis: A B dla oznaczenia, że A jest podzbiorem właściwym B
Matematyka Dyskretna
Barbara GÅ‚ut 2
Równość zbiorów
Równość zbiorów
Zbiory są równe wtedy i tylko wtedy, gdy mają te same elementy.
A = B Ô! '"(a " A Ô! a " B)
a
A = B Ô! (A Ä…" B '" B Ä…" A)
{x : P(x)} = {x : R(x)} Ô! '"(P(x) Ô! R(x))
x
Działania na zbiorach
Działania na zbiorach
Suma zbiorów:
A *" B = {x : x " A (" x " B}
A B
Iloczyn (przecięcie) zbiorów:
A )" B = {x : x " A '" x " B}
A B
n
Ai oznacza sumę zbiorów A1, A2, ... , An
U
i=1
n
Ai oznacza iloczyn zbiorów A1, A2, ... , An
I
i=1
Matematyka Dyskretna
Barbara GÅ‚ut 3
Działania na zbiorach
Działania na zbiorach
Różnica zbiorów:
A \ B = {x : x " A '" x " B}
A B
Różnica symetryczna zbiorów:
A •" B = (A *" B) \ (A )" B)
A B
Dopełnienie zbioru:
X X
A A
A'= X \ A = {x : x " A}
Działania na zbiorach
Działania na zbiorach
wyznaczonych przez funkcje zdaniowe
wyznaczonych przez funkcje zdaniowe
{x: P(x)} *" {x: R(x)} = {x: P(x) (" R(x)}
{x: P(x)} )" {x: R(x)} = {x: P(x) '" R(x)}
{x: P(x)} \ {x: R(x)} = {x: P(x) '" ~ R(x)}
{x: P(x)} •" {x: R(x)} = {x: (P(x) (" R(x)) '" ~(P(x) '" R(x))}
{x: P(x)}' = {x: ~ P(x)}
Matematyka Dyskretna
Barbara GÅ‚ut 4
Prawa algebry zbiorów
Prawa algebry zbiorów
A *" " = A A *" X = X
A )" " = " A )" X = A
A *" A'= X A)" A'= "
X '= " "'= X
A*" A = A A)" A = A
(A')'= A A Ä…" B Ô! (A )" B = A)
A \ B = A )" B'
Prawa algebry zbiorów
Prawa algebry zbiorów
Prawa przemienności:
A*" B = B *" A A)" B = B )" A
Prawa łączności:
(A *" B) *" C = A *" (B *" C)
(A )" B) )" C = A )" (B )" C)
Prawa rozdzielności:
A *" (B )" C) = (A *" B) )" (A *" C)
A )" (B *" C) = (A )" B) *" (A )" C)
Prawa de Morgana:
(A *" B)'= A')"B'
(A )" B)'= A'*"B'
Matematyka Dyskretna
Barbara GÅ‚ut 5
Sprawdzanie za pomocą kół Eulera
Sprawdzanie za pomocą kół Eulera
(A *" B)'= A')"B'
A B
A B
Diagramy Venna
Diagramy Venna
Niepustość danego zbioru zaznaczamy na diagramie poprzez znak  +
na obszarze symbolizującym ten zbiór.
To, że dany zbiór jest pusty, zaznaczamy na diagramie poprzez znak
 - (lub zakreskowując obszar symbolizujący ten zbiór).
symbolizuje, że:
+
A = X
Matematyka Dyskretna
Barbara GÅ‚ut 6
Diagramy Venna
Diagramy Venna
IV
Obszar I symbolizuje A )" B
Obszar II symbolizuje A \ B
II III
I
A B
Obszar III symbolizuje B \ A
Obszar IV symbolizuje (A *" B)2
A Ä…" B
+
A B
+
A B
?
?
Diagramy Venna
Diagramy Venna
(A *" B) \ B = A ?
+
A B
+
+
(A )" B)2 = A2 *" B2
A B
Matematyka Dyskretna
Barbara GÅ‚ut 7
Zbiór, którego elementami są zbiory, nazywamy rodziną tych zbiorów.
Zbiór wszystkich podzbiorów zbioru A nazywamy zbiorem potęgowym
zbioru A i oznaczamy P(A).
Np.: A = { b, c } P(A) = { ", {b}, {c}, {b, c} }
Funkcja charakterystyczna zbioru:
1 gdy a " A
ż#
ÇA(a) =
¨#0 gdy a " A
©#
Moc zbioru  liczba kardynalna
Moc zbioru  liczba kardynalna
Liczność zbioru skończonego - liczba jego elementów |A|
Uogólnienie pojęcia liczby elementów
Moc zbioru  liczba kardynalna
dla zbiorów skończonych = liczność
dla zbiorów nieskończonych: card N = 5!0 (alef zero)
card R = c (continuum)
Dwa zbiory są równoliczne, gdy istnieje funkcja wzajemnie jednoznaczna
z jednego zbioru w drugi.
Zbiory równoliczne mają te samą moc  tę samą liczbę kardynalną.
Matematyka Dyskretna
Barbara GÅ‚ut 8
Iloczyn kartezjański zbiorów
Iloczyn kartezjański zbiorów
Iloczynem kartezjańskim (lub produktem) zbiorów A i B nazywamy
zbiór wszystkich i tylko takich par uporządkowanych, których
pierwsze elementy należą do zbioru A, a drugie do zbioru B.
Oznaczamy: A x B
(a,b) " A x B Ô! ( a " A '" b " B )
A x B = { (a, b) : a " A '" b " B }
Np.: A = { 1, 2} B = { a, b, c }
A x B = { (1, a), (1, b), (1, c), (2, a), (2, b), (2, c) }
A1 x A2 x ... x An = { ( a1, a2, ... an ): ai"Ai, i = 1, 2, ... n }
RELACJE
RELACJE
Relacja wyraża związek zachodzący między zadanymi obiektami
Dowolny podzbiór A1 x A2 x ... x An
nazywamy n-argumentowÄ… relacjÄ…
na zbiorze A1 x A2 x ... x An
Dowolny podzbiór R ą" An
nazywamy n-argumentowÄ… relacjÄ… w zbiorze A.
Gdy n = 2 relacja dwuargumentowa (binarna)
Matematyka Dyskretna
Barbara GÅ‚ut 9
Relacje dwuargumentowe
Relacje dwuargumentowe
Przykład:
R = { (0,0), (1,2), (2,4), (3,6), ... } jest relacjÄ… na N
R = { (0,0), (1,2), (2,4), (3,6), ... } jest relacjÄ… na
Zapisujemy ją też:
R = { (a,b)" N x N: b = 2a }
R Ä…" N x N, aRb Ô! b = 2a
Liczby a oraz b są w relacji, jeśli b jest dwukrotnością a.
Każda funkcja zdaniowa dwóch zmiennych wyznacza pewną relację.
Każda funkcja zdaniowa dwóch zmiennych wyznacza pewną relację.
xRy Ô! P(x,y)
xRy
Ale istnieją relacje, które nie są określone przez żadną funkcję zdaniową.
To, że dwa elementy są ze sobą w relacji zapisujemy:
(a,b) " R lub aRb
Relację binarną można przedstawić w postaci tabeli lub diagramu (grafu).
Np.: A = {1, 2, 3, 4, 6}
1
R Ä…" A x A, aRb Ô! ( a mod b = 0 ) 6
2
4
3
jeśli R ą" AxA
b
1 2 3 4 6
a
1
1
1 1 0 0 0 0
2
2
2 1 1 0 0 0
3
3
3 1 0 1 0 0
4
4
4 1 1 0 1 0
6 1 1 1 0 1
6
6
Matematyka Dyskretna
Barbara GÅ‚ut 10
Dziedzina relacji R Ä…" A x B :
{a " A : ((": aRb)}
b"B
- zbiór poprzedników par należących do R (lewa dziedzina)
Przeciwdziedzina relacji R Ä…" A x B :
{b " B : ((": aRb)}
a"A
- zbiór następników par należących do R (prawa dziedzina)
Pole relacji  suma dziedziny i przeciwdziedziny
Relacja binarna R Ä…" A2 jest
{(a,b)" A× A : a = b}
identycznościowa
zbiór par (a,a) dla wszystkich a"A
'"aRa
zwrotna
a"A
każdy element jest w relacji z samym sobą
'"~ aRa
przeciwzwrotna
a"A
żaden element nie jest w relacji z samym sobą
'" ((aRb '" bRc) Ò! aRc)
przechodnia
a,b,c"A
jeśli a jest w relacji z b, b w relacji z c, to a jest w relacji z c
Matematyka Dyskretna
Barbara GÅ‚ut 11
Relacja binarna R Ä…" A2 jest
'" (aRb Ò! bRa)
symetryczna
a,b"A
jeśli a i b są w relacji, to b i a również (nie ma wyróżnionego kierunku)
słabo antysymetryczna (asymetryczna)
'" ((aRb '" bRa) Ò! a = b)
a,b"A
relacja  w obie strony możliwa jedynie, gdy elementy są równe
silnie antysymetryczna
'" ~ (aRb '" bRa)
a,b"A
relacja  w obie strony w ogóle nie jest możliwa
Relacja binarna R Ä…" A2 jest
'" (aRb (" bRa (" a = b)
spójna
a,b"A
każde dwa elementy są w relacji w jedną lub drugą stronę
Dla relacji binarnej R w zbiorze A relacjÄ™:
R-1 = {(a,b)" A2 : bRa}
nazywamy relacjÄ… odwrotnÄ… do relacji R.
Diagram relacji odwrotnej R-1 otrzymujemy z diagramu relacji R przez zmianÄ™
kierunku wszystkich strzałek
RelacjÄ™ R = " nazywamy relacjÄ… pustÄ….
Relację R = A2 nazywamy relacją pełną.
Matematyka Dyskretna
Barbara GÅ‚ut 12
Relacja binarna R jest równoważnościowa, jeśli jest
zwrotna, symetryczna i przechodnia
Dla dowolnej relacji równoważności R w zbiorze A i dowolnego a"A
zbiór
[a]R = {b " A : aRb}
nazywamy klasą abstrakcji elementu a względem relacji R.
Klasa abstrakcji  klasa równoważności  zbiór wszystkich elementów będących
z a w relacji R.
Element a nazywamy reprezentantem klasy.
Jeśli aRb, to [a]R = [b]R
Jeśli ~ aRb, to zbiory [a]R i [b]R są rozłączne.
Zbiór wszystkich klas abstrakcji nazywamy zbiorem ilorazowym i
oznaczamy A/R
Relacja binarna R ą" A2 nazywana jest słabo porządkującą
(częściowym, słabym porządkiem),
jeśli jest zwrotna, słabo antysymetryczna i przechodnia.
Para (A, R) nazywana jest zbiorem częściowo uporządkowanym.
Relacja binarna R Ä…" A2 nazywana jest silnie porzÄ…dkujÄ…cÄ… (porzÄ…dkiem),
jeśli jest silnie antysymetryczna i przechodnia.
Relacja binarna R Ä…" A2 nazywana jest
słabo porządkującą liniowo, jeśli jest
zwrotna, słabo antysymetryczna, przechodnia i spójna.
Relacja binarna R Ä…" A2 nazywana jest
silnie porządkującą liniowo, jeśli jest
silnie antysymetryczna, przechodnia i spójna.
Matematyka Dyskretna
Barbara GÅ‚ut 13
Relacja R jest funkcją jednej zmiennej wtedy i tylko wtedy, gdy każdemu
elementowi a przyporządkowuje dokładnie jeden przedmiot.
'"((xRy '" xRz) Ò! y = z)
x, y,z
Relacja jest funkcjÄ… wtedy i tylko wtedy, gdy jest zbiorem par
uporządkowanych, wśród których nie ma dwóch różnych par o takim
samym elemencie pierwszym.
Diagram relacji nie może wówczas zawierać dwóch strzałek o tym samym
poczÄ…tku.
Relacja jest wzajemnie jednoznaczna wtedy i tylko wtedy, gdy jest
funkcją i gdy relacja do niej odwrotna też jest funkcją.
Matematyka Dyskretna
Barbara GÅ‚ut 14