Wykład 1
Algebra zbiorów
Pierwotne (czyli niezdefiniowane) wymienione poj
ħ
cia:
-
zbiór
(inaczej: mnogo
Ļę
, klasa)
-
nale
Ň
enia elementu do zbioru.
Zbiory oznaczamy du
Ň
ymi literami alfabetu A, B, X, ...
a ich elementy małymi literami a, b, x,....
1.
N
={1, 2, 3, 4, 5,...} - zbiór liczb naturalnych
2.
Z
– zbiór liczb całkowitych
3.
W
– zbiór liczb wymiernych
4.
R
( lub
Q
) - zbiór liczb rzeczywistych
Je
Ň
eli x jest elementem zbioru X, to zapisujemy:
xÎX.
Je
Ň
eli x nie jest elementem zbioru X, to piszemy
xÏX lub ~ (xÎX).
Definicja
Zbiór, który zawiera sko
ı
czon
Ģ
liczb
ħ
elementów
nazywa si
ħ
zbiorem
sko
ı
czonym
.
A= {
a
1
,
a
2
, … ,
a
n
}
Zbiór, który zawiera niesko
ı
czon
Ģ
liczb
ħ
elementów
nazywa si
ħ
zbiorem
niesko
ı
czonym
.
A= {x Î R: 2 < x < 3};
Definicja
Zbiory A i B s
Ģ
równe
, je
Ň
eli ka
Ň
dy element, który nale
Ň
y do zbioru
A, nale
Ň
y te
Ň
do zbioru B i na odwrót, ka
Ň
dy element nale
ŇĢ
cy do
zbioru B nale
Ň
y do zbioru A.
Je
Ň
eli zbiory A i B nie s
Ģ
równe, to piszemy A¹B.
Definicja
Zbiór B nazywamy
podzbiorem
zbioru A (lub zbiór B zawiera si
ħ
w zbiorze A),
i piszemy B Í A, je
Ň
eli ka
Ň
dy element zbioru B nale
Ň
y do zbioru A.
2
Zbiór, który nie zawiera
Ň
adnego elementu,
nazywa si
ħ
zbiorem
pustym
:
Æ
Przykłady
{x Î
N
: 2 < x < 3} = Æ;
{
x
Î
Z
:
x
2
+ 2=0} = Æ;
{
x
Î
R
:
x
2
= 2 } = Æ;
Zbiór krokodylów pływaj
Ģ
cych w Wi
Ļ
le = Æ.
Definicja
Niech X i Y b
ħ
d
Ģ
dowolnymi zbiorami. Element, oznaczony
symbolem (
x
,
y
), gdzie
x
ÎX i
y
Î Y, nazywamy
par
ħ
uporz
Ģ
dkowan
Ģ
o poprzedniku
x
i nast
ħ
pniku
y
.
(
x
,
y
) = (
u
,
v
) « (
x
=
u
) Ù (
y
=
v
)
Definicja
Iloczynem kartezja
ı
skim
(produktem) zbiorów X i Y nazywamy
zbiór wszystkich par uporz
Ģ
dkowanych (
x
,
y
), gdzie
x
ÎX i
y
ÎY,
i oznaczamy przez X ×Y. A wi
ħ
c
X ×Y = { (
x
,
y
) :
x
ÎX Ù
y
ÎY}
Je
Ļ
li S = T, to piszemy S
2
zamiast S × S.
S
1
, S
2
, ..., S
n
- rodzina zbiorów.
Element (
s
1
,
s
2
,...,
s
n
), gdzie
s
i
ÎS
i
"
i
= 1, 2, ...,
n
nazywamy
ci
Ģ
giem
n-elementowym
.
(
s
1
,
s
2
, ...,
s
n
) = (
t
1
,
t
2
, ...,
t
n
) «
s
i
=
t
i
"
i
= 1,2,...,
n
.
3
Definicja
Iloczynem kartezja
ı
skim
dowolnej sko
ı
czonej rodziny zbiorów S
1
,
S
2
, ..., S
n
nazywamy zbiór wszystkich uporz
Ģ
dkowanych ci
Ģ
gów
n
-
elementowych (
s
1
,
s
2
, ...,
s
n
), gdzie
s
i
ÎS
i
"
i
= 1, 2, ...,
n
, i oznaczamy
przez S
1
× S
2
× ... × S
n
.
Relacje
Definicja
Relacj
Ģ
binarn
Ģ
R
mi
ħ
dzy elementami zbiorów X i Y nazywamy dowolny podzbiór
iloczynu kartezja
ı
skiego X ×Y.
R
=
{ (x,y) Î X ×Y | x
R
y } Í X ×Y
Relacj
Ģ
R
w zbiorze
X nazywamy dowolny podzbiór iloczynu kartezja
ı
skiego X ×X.
Przykład
X={1,2,3}, Y={1,2,3,4}
R
= { (1,2), (1,4), (2,1), (2,4), (3,3)}.
1. Sposób graficzny
2. Sposób tablicowy
R
1 2 3 4
1 * *
2 * *
3 *
3. Sposób macierzowy
X= {
x
1
,
x
2
, ...,
x
m
} , Y={
y
1
,
y
2
, ...,
y
n
}.
M
Â
= [
m
ij
], gdzie
4
m
ij
=
Ì
1
dla
(
x
i
,
y
j
)
Î
Â
0
dla
(
x
,
y
)
Ï
Â
.
i
j
I.
Ç
0
1
0
1
×
È
Ø
M
Â
=
È
1
0
0
1
Ø
È
Ø
0
0
1
0
É
Ù
Własno
Ļ
ci relacji
Niech
R
Í X
2
. Na ogół je
Ň
eli (
a
,
b
) Î
R
Í X × X, to wówczas piszemy
a
R
b
.
1.
Relacje
R
nazywamy
zwrotn
Ģ
je
Ň
eli
"(
x
Î X) (
x
R
x
)
Ç
1
*
*
...
*
×
È
Ø
È
*
1
*
...
*
Ø
M
Â
=
È
Ø
.
*
*
1
...
*
È
Ø
È
...
...
...
...
...
...
...
Ø
È
*
*
*
...
1
Ø
Graf relacji zwrotnej ma w ka
Ň
dym wierzchołku p
ħ
tl
ħ
.
2. Relacje
R
nazywamy
symetryczn
Ģ
je
Ň
eli
"(
x
,
y
Î X) (
x
R
y
®
y
R
x
)
M
Â
=
M
Â
T
.
3. Relacje nazywamy
antysymetryczn
Ģ
je
Ň
eli
Ê
Ë
É
Ù
5
"(x,y Î X ) [ (x
R
y) Ù (y
R
x) ® x = y]
4. Relacje nazywamy
przechodni
Ģ
je
Ň
eli
" ( x,y,z Î X ) [ (x
R
y )
Ù (y
R
z )
® (x
R
z) ].
5. Relacje nazywamy
spójn
Ģ
je
Ň
eli
"(x,y Î X ) [ (x
R
y) Ú (y
R
x) ]
to znaczy,
Ň
e ka
Ň
de dwa elementy x,y Î X s
Ģ
porównywalne
Przykłady
1. Relacja ( £ ) jest zwrotna i przechodnia, nie jest symetryczna:
x £ x
x £ y Ù y £ z ® x £ z.
R
= { (x,y) Î
Q
2
| x +y £ 5 },
gdzie
Q
zbiór liczb rzeczywistych, jest symetryczna.
Relacja równowa
Ň
no
Ļ
ci
Definicja
Relacje
R
nazywamy
relacj
Ģ
równowa
Ň
no
Ļ
ciow
Ģ
, lub
równowa
Ň
no
Ļ
ci
Ģ
, je
Ļ
li jest ona
relacj
Ģ
zwrotn
Ģ
, przechodni
Ģ
i symetryczn
Ģ
.
Przykłady
1. Relacja równoległo
Ļ
ci prostych jest relacje równowa
Ň
no
Ļ
ci w zbiorze wszystkich
prostych na płaszczy
Ņ
nie.
2. Relacja podobie
ı
stwa w zbiorze figur geometrycznych na płaszczy
Ņ
nie.
3. Relacja zamieszkania w tym samym budynku w zbiorze wszystkich mieszka
ı
ców
Cz
ħ
stochowy.
Definicja
Rodzin
ħ
zbiorów {A
1
, A
2
, ... , A
n
} nazywamy
podziałem
albo
rozbiciem
zbioru X,
je
Ň
eli zbiór X mo
Ň
na przedstawi
ę
w postaci:
2. Relacja