Matematyka dyskretna - Szepietowski.pdf

(1445 KB) Pobierz
Matematyka Dyskretna
Andrzej Szepietowski
25 czerwca 2002 roku
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
Rozdział 1
Oznaczenia
W tym rozdziale przedstawimy podstawowe oznacznia.
oznacza kwantykator ogólny "dla ka˙ dego". oznacza kwantykator szczegółowy
z
"istnieje".
1.1 Sumy
©
§ ©¨
¤¢
§
¥¦¢ ¤¢
£
Maj¸ c dany sko´ czony ci¸ g
a
n
a
,
,...
, sum¸ jego elementów zapisujemy jako
e
Niezbyt formalnie mo˙ emy to zapisa´
z
c
Jako przykład zastosujmy symbol sumy do zapisu wzoru na
sum˛ ci¸ gu arytmetycznego).
e a
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
T ¢ ` ¢ Y V ¥ £
¦aXW)FW¢)XW¢)¦¢)#¢
IP8
(wzór (1.2) jest słuszny dla ka˙ dego
z
B¸ dziemy te˙ u˙ ywa´ zapisu typu
e
z z
c
)
3
8
E 8
£ C
GH& EFD§
&
oraz wzoru na
sum˛ ci¸ gu geometrycznego).
e a
1
5
"&
§ ¢ ¢ £
#"! ¥¦¤¢
(
41
2
3
§
¡
8
8
&Q 8
B !A
¥
1
)"! 0)
(
¢
£
©
'
&
¢
©
£
§ ©¨
&@
$
%£
¢
T R
UR S£
§ ©¨
©
© ¨
967
8
§ ©¨
 
(1.1)
(1.2)
4
Rozdział 1. Oznaczenia
W tym przypadku zbiór indeksów okre´lony jest za pomoc¸ warunku pod znakiem sumy.
s
a
Warunek okre´laj¸ cy indeksy, po których nale˙ y sumowa´ mo˙ e by´ bardziej skompliko-
s a
z
c
z
c
wany, na przykład
Mo˙ emy te˙ sumowa´ ciagi, których elementy zale˙ a od dwóch indeksów,
z
z
c ˛
z˛
Za pomoca podwójnej sumy mo˙ emy na przykład przedstawi´ uogólnione prawo roz-
˛
z
c
dzielno´ci mno˙ enia wzgl˛ dem dodawania:
s
z
e
a tak˙ e wzór na podnoszenie sumy do kwadratu:
z
1.2 Iloczyny
§
#¢
©
¥¦¢ £ ¢
Aby zapisa´ iloczyn elementów ci¸ gu
c
a
,
,...
, stosujemy zapis
Znów niezbyt formalnie mo˙ emy to zapisa´ jako
z
c
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
¢
¢
V V ¢) ¥ V ) V ¥ ¢) ¥ ¥ ¢) V £ ¥ £ ¢
9
¢ ¢ (
9
©
I
©
¢
¤¡¢8¢ 
R 7 ¡
Q ¡ £ ¡
¤¥¤¢ 
B
C
R
9
¢ ¢ £
21
¢)`¦XV¦) ¤¢
§ ¢
¢ £
#! ! ¥¦"#¢
¨
S
E
¨ ©
R£
DF
9
©
¥
I G
PH
R
9
¢
0
G
'
G
%
1()
¤
&
¤
&
G
¢
BH
R
£
§
T
©
©¨
¨
RS£
R£
@A
©
©
$
¢
oznaczaj¸cy sum¸ tych elementów
a
e
indeksów . Na przykład, je˙ eli
z
´
, których indeksy nale˙ a do skonczonego zbioru
z¸
, to
¢
"
¤!
©¨
Stosowa´ b¸ dziemy tak˙ e zapis
c e
z
¢
¢
T Y a ¥ ¢
©
¢
(1.3)
(1.4)
©
&
©
¥©¨£
§
¦ ¡ £ ¡
¤¥¤¢ 
¥
¢
DF
E
©
£
¢
DF
§
T
©
¨
#
¤!
"
¢
©
¢
©¨
B
C
R
©
BH
R
9
©¨
©¨
S£
R
¢
R£
5 ¡ 7 ¡
¤¢86
5 ¡ £ ¡
¤4¤3 
@A
@A
¨
#
1.3. Zbiory
5
1.3 Zbiory
oznacza zbiór pusty, który nie zawiera zadnych elementów.
˙
oznacza zbiór liczb naturalnych
.
oznacza zbiór liczb całkowitych.
oznacza zbiór liczb wymiernych.
oznacza zbiór liczb rzeczywistych.
oznacza, ze elment nale˙ y do zbioru ,
˙
z
, ze elment nie nale˙ y do
˙
z
zbioru . Najprostszy sposób zdeniowania zbioru polega na wypisaniu jego elementów
zawiera elementy 1,2,3. Inny spo-
w nawiasach klamrowych. Na przykład zbiór
sób deniowania zbioru polega na podaniu własno´ci, któr¸ spełniaj¸ elementy zbioru.
s
a
a
Na przykład
oznacza zbiór liczb naturalnych wi¸ kszych od 3 i
e
mniejszych od 7.
oznacza
moc zbioru
, czyli liczb¸ jego elementów.
e
0
A zatem suma
zawiera wszystkie elementy zbioru i wszystkie elementy zbioru
.
oznacza
iloczyn lub przekrój zbiorów,
czyli zbiór, który zawiera te elementy,
które nale˙ a do obu zbiorów naraz.
z¸
Jak wida´ kolejno´c elementów w zapisie zbioru nie ma znaczenia. I tak na przykład
c
s´
. Taki zbiór dwuelementowy nazywamy czasami
par¸ nieuporz¸ dkowan¸
.
a
a
a
W poni˙ szym lemacie zebrano podstawowe własno´ci operacji sumy i iloczynu zbio-
z
s
rów.
0
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
"
©
Dwa zbiory s¸ równe je˙ eli zawieraj¸ te same elementy, lub inaczej
a
z
a
wtedy gdy
i
.
(
0
¤
%
G G
0
G
&
0 &
G
%
"
(
G
&
$
$
2
0 %&
G
0
&
G
(
(
G
1
G
0
$
&
$
© 2
4"
©
oznacza, ze zbior
˙
nale˙ a do zbioru .
z¸
"
zawiera si¸
w zbiorze , to znaczy wszystkie elementy zbioru
e
(
0
$
"
E
©
W
0
G
G
0
&
$
Przykład 1.1
Dla
i
mamy:
"
& §
i
0
8
$
8
0
G
G
0
8
©
&§
$
&
$
"
%'!©
(
"
%!©
G
0
G
1
G G
$
0
"
( &
©
$
0
G G
0
E
©
&
"
"
" 2
(3©
&
G
(
$
" 2
(3©
0
(
©
do
oznacza
ró˙nic¸ zbiorów,
czyli zbiór, który zawiera te elementy, które nale˙ a
z e
z¸
i nie nale˙ a do .
z¸
"
"
)§
i
0
"
&§
lub
0
©
8
8
©
&§
©
%§
8
8
$
$
8
$
8
$
do
:
"
#!©
"
%©
wtedy i tylko
©
oznacza
sum¸ zbiorów,
czyli zbiór, który zawiera elementy, które nale˙ a do
e
z˛
¢
¢
© §
¢
 
0 %
(
!
¡
¢
¤
%
G G G
£
$
G
&
©
(
G G
&
$
¤
%
G
0 (
0
G
¤
G
"
%'!©
¢
8
%
$
¨
%
G
©
¡
§
8
8
$
©
© §
¨
¢
" '
)(©
E
©
"
#!©
"
©
G
&
$
 
¡
¤
¥
¦
"
©
lub

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin