Matematyka dyskretna 2004 - 01 ...

Matematyka dyskretna 2004 - 01 Podstawowe pojęcia, Matematyka dyskretna

[ Pobierz całość w formacie PDF ]
Matematyka Dyskretna
Andrzej Szepietowski
25 marca 2004 roku
Rozdział 1
Podstawowe pojecia, oznaczenia
1.1 Sumy
Maj ac dany sko nczony ci ag
a
1
,
a
2
,...
a
k
, sume jego elementów zapisujemy jako
k
X
a
i
:
i=1
Niezbyt formalnie mozemy to zapisac
k
X
a
i
= a
1
+ a
2
++ a
k
:
i=1
Jako przykład zastosujmy symbol sumy do zapisu wzoru na
sume ci agu arytmetycznego
).
k
X
i = 1 + 2 ++ k =
(k + 1)k
2
(1.1)
i=1
oraz wzoru na
sume ci agu geometrycznego
).
k
X
x
i
= 1 + x + x
2
++ x
k
=
x
k+1
1
x1
;
(1.2)
i=0
(wzór (1.2) jest słuszny dla kazdego
x 6= 1
)
Bedziemy tez uzywac zapisu typu
X
a
i
= a
1
+ a
2
+ a
3
+ a
4
+ a
5
+ a
6
:
1i6
W tym przypadku zbiór indeksów okreslony jest za pomoc a warunku pod znakiem sumy.
Warunek okreslaj acy indeksy, po których nalezy sumowa c moze byc bardziej skompliko-
wany, na przykład
X
a
i
= a
2
+ a
4
+ a
6
:
1
i
6
i parzyste
3
4
Rozdział 1. Podstawowe pojecia, oznaczenia
Stosowac bedziemy takze zapis
X
a
i
i2I
oznaczaj acy sume tych elementów
a
i
, których indeksy nalez a do sko nczonego zbioru
indeksów
I
. Na przykład, jezeli
I =f1; 3; 5; 7g
, to
X
a
i
= a
1
+ a
3
+ a
5
+ a
7
:
i2I
Mozemy tez sumowac ci agi, których elementy zalez a od dwóch indeksów,
X
X
X
a
ij
=
a
ij
a
12
+ a
13
+ a
22
+ a
23
+ a
32
+ a
33
:
1
i
3
2
j
3
1i3
2j3
Za pomoc a podwójnej sumy mozemy, na przykład, przedstawi c uogólnione prawo roz-
dzielnosci mnozenia wzgledem dodawania:
0
1
0
1
X
X
X
@
A
@
A
a
i
b
j
=
a
i
b
j
(1.3)
1im
1jn
1
i
m
1
j
n
a takze wzór na podnoszenie sumy do kwadratu:
0
@
A
2
X
X
X
a
i
+
a
i
=
2a
i
a
j
(1.4)
1im
1im
1i<jm
1.2 Iloczyny
Aby zapisac iloczyn elementów ci agu
a
1
,
a
2
,...,
a
k
, stosujemy zapis
k
Y
a
i
:
i=1
Znów niezbyt formalnie mozemy to zapisac jako
k
Y
a
i
= a
1
a
2
a
k
:
i=1
1.3 Zbiory
;
oznacza zbiór pusty, który nie zawiera zadnych elementów.
N
oznacza zbiór liczb naturalnych
N =f0; 1; 2; 3; : : :g
.
Z
oznacza zbiór liczb całkowitych.
1
1.3. Zbiory
5
Q
oznacza zbiór liczb wymiernych.
R
oznacza zbiór liczb rzeczywistych.
a2A
oznacza, ze elment
a
nalezy do zbioru
A
,
a =2A
, ze elment
a
nie nalezy do
zbioru
A
. Najprostszy sposób zdefiniowania zbioru polega na wypisaniu jego elementów
w nawiasach klamrowych. Na przykład zbiór
f1; 2; 3g
zawiera elementy 1,2,3. Inny spo-
sób definiowania zbioru polega na podaniu własnosci, któr a spełniaj a elementy zbioru.
Na przykład
fxjx2N; 3 < x < 7g
oznacza zbiór liczb naturalnych wiekszych od 3 i
mniejszych od 7.
jAj
oznacza
moc zbioru
A
, czyli liczbe jego elementów.
jf3; 6; 9gj= 3; j;j= 0:
A[B
oznacza
sume zbiorów
, czyli zbiór zawieraj acy elementy, które nalez a do
A
lub do
B
:
A[B =fx : x2A
lub
x2Bg:
A zatem suma
A[B
zawiera wszystkie elementy zbioru
A
i wszystkie elementy zbioru
B
.
A\B
oznacza
iloczyn lub przekrój zbiorów
, czyli zbiór zawieraj acy elementy, które
nalez a do obu zbiorów naraz.
A\B =fx : x2A
i
x2Bg:
AB
oznacza
róznice zbiorów
, czyli zbiór zawieraj acy elementy, które nalez a do
A
i nie nalez a do
B
.
AB =fx : x2A
i
x =2Bg:
Przykład 1.1
Dla
A =f1; 2; 4g
i
B =f1; 4; 6g
mamy:
A[B =f1; 2; 4; 6g;
A\B =f1; 4g;
AB =f2g:
AB
oznacza, ze zbior
A
zawiera sie
w zbiorze
B
, to znaczy wszystkie elementy zbioru
A
nalez a do zbioru
B
.
f2; 1gf1; 2; 3g
Dwa zbiory s a równe jezeli zawieraj a te same elementy, lub inaczej
A = B
wtedy i tylko
wtedy gdy
AB
i
BA
.
f1; 4; 2; 3g=f4; 1; 3; 2g:
Jak widac kolejnosc elementów w zapisie zbioru nie ma znaczenia. I tak na przykład
f1; 2g=f2; 1g
. Taki zbiór dwuelementowy nazywamy
par a nieuporz adkowan a
.
W ponizszym lemacie zebrano podstawowe własnosci operacji sumy i iloczynu zbio-
rów.
Lemat 1.2
A[B = B[A
(przemiennosc sumy).
A\B = B\A
(przemiennosc iloczynu).
[ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

mement.xlx.pl