Matemtyka Dyskretna Skrypt.pdf

(1813 KB) Pobierz
Matematyka Dyskretna
Andrzej Szepietowski
17 marca 2003 roku
Rozdział 1
Podstawowe poj˛ cia, oznaczenia
e
1.1 Sumy
Maj¸ c dany sko´ czony ci¸ g
a
1
,
a
2
,...
a
k
, sum¸ jego elementów zapisujemy jako
a
n
a
e
k
a
i
.
i=1
Niezbyt formalnie mo˙ emy to zapisa´
z
c
k
a
i
=
a
1
+
a
2
+
· · ·
+
a
k
.
i=1
Jako przykład zastosujmy symbol sumy do zapisu wzoru na
sum˛ ci¸ gu arytmetycznego).
e a
k
i
= 1+2+
···
+
k
=
i=1
(k + 1)k
2
(1.1)
oraz wzoru na
sum˛ ci¸ gu geometrycznego).
e a
x
k+1
−
1
x
= 1+
x
+
x
+
···
+
x
=
,
x
−
1
i=0
i
2
k
k
(1.2)
(wzór (1.2) jest słuszny dla ka˙ dego
x
= 1)
z
B¸ dziemy te˙ u˙ ywa´ zapisu typu
e
z z
c
a
i
=
a
1
+
a
2
+
a
3
+
a
4
+
a
5
+
a
6
.
1≤i≤6
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
a
i
=
a
2
+
a
4
+
a
6
.
1≤i≤6
i
parzyste
3
4
Rozdział 1. Podstawowe poj˛ cia, oznaczenia
e
Stosowa´ b¸ dziemy tak˙ e zapis
c e
z
a
i
i∈I
´
oznaczaj¸cy sum¸ tych elementów
a
i
, których indeksy nale˙ a do skonczonego zbioru
a
e
z¸
indeksów
I.
Na przykład, je˙ eli
I
=
{1,
3, 5, 7},
to
z
a
i
=
a
1
+
a
3
+
a
5
+
a
7
.
i∈I
Mo˙ emy te˙ sumowa´ ciagi, których elementy zale˙ a od dwóch indeksów,
z
z
c ˛
z˛
a
ij
=
a
12
+
a
13
+
a
22
+
a
23
+
a
32
+
a
33
.
1≤i≤3
2≤j≤3
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
 
1≤i≤m
a
i
·
1≤j≤n
b
j
=
a
i
b
j
(1.3)
1≤i≤m
1≤j≤n
a tak˙ e wzór na podnoszenie sumy do kwadratu:
z
1≤i≤m
a
i
=
2
a
2
+
i
1≤i≤m
1≤i<j≤m
2a
i
a
j
(1.4)
1.2 Iloczyny
Aby zapisa´ iloczyn elementów ci¸ gu
a
1
,
a
2
,...,
a
k
, stosujemy zapis
c
a
k
a
i
.
i=1
Znów niezbyt formalnie mo˙ emy to zapisa´ jako
z
c
k
a
i
=
a
1
·
a
2
· · · · ·
a
k
.
i=1
1.3 Wielomiany
Wielomian jest to funkcja postaci
P
(x) =
a
n
·
x
n
+
· · ·
+
a
0
,
1.3. Wielomiany
5
gdzie
x
jest zmienna rzeczywista, a
a
0
,
a
1
, ... ,a
n
sa stałymi rzeczywistymi, nazywanymi
˛
˛
˛
współczynnikami wielomianu. Stopniem wielomianu
P
(x)
jest najwi˛ ksze takie
k,
ze
e
˙
n
a
k
= 0,
stopie´ oznaczamy, przez
st(W
(x)).
Zwykle piszac
P
(x) =
a
n
·
x
+
· · ·
+
a
0
n
˛
b˛ dziemy zakłada´ , ze
a
n
= 0,
czyli ze stopie´
st(P
(x)) =
n.
U˙ ywajac symbolu sumy
e
c ˙
˙
n
z
˛
wielomian mo˙ emy przedstawi´ w nast˛ pujacy sposób:
z
c
e ˛
n
P
(x) =
i=0
a
i
x
i
.
Wielomian, którego wszystkie współczynniki sa równe zeru nazywamy wielomianem ze-
˛
n
n
i
rowym. Dwa wielomiany
P
(x) =
i=0
a
i
x
oraz
Q(x)
=
i=0
b
i
x
i
sa równe je˙ eli
˛
z
maja takie same wspólczynniki, to znaczy je˙ eli
a
i
=
b
i
dla ka˙ dego
i.
˛
z
z
Wielomiany mo˙ na dodawa´ , odejmowa´ lub mno˙ y´ . Suma, ró˙ nica i iloczyn wie-
z
c
c
z c
z
lomianów
P
(x)
i
Q(x)
okre´lone sa nast˛ pujaco:
s
˛
e ˛
•
P
(x) +
Q(x)
=
•
P
(x)
−
Q(x)
=
n
i=0
(a
i
n
i=0
(a
i
2n
+
b
i
)x
i
,
−
b
i
)x
i
,
i
k=0
•
P
(x)
·
Q(x)
=
i=0
(c
i
)x
i
, gdzie
c
i
=
dla wszystkich
k > n.
a
k
·
b
i−k
oraz
a
k
= 0
i
b
k
= 0
Wzór na iloczyn wielomianów wyglada skomplikowanie, ale jest on równowa˙ ny szkol-
˛
z
nemu sposobowi mno˙ enia wielomianów, gdzie wyrazy (jednomiany) obu wielomianów
z
wymna˙ a si˛ ka˙ dy z ka˙ dym a nast˛ pnie grupuje wyrazy według wykładników. Wielo-
z e z
z
e
mian
P
(x)
mo˙ na pomno˙ y´ przez stała
a
z
z c
˛
n
a
·
P
(x) =
i=0
a
·
a
i
x
i
.
Przykład 1.1
Niech
P
(x) =
x
2
+ 2x + 1
oraz
Q(x)
= 2x
2
+
x.
Wtedy
P
(x) +
Q(x)
= 3x
2
+ 3x + 1
P
(x)
·
Q(x)
= 2x
4
+ 5x
3
+ 4x
2
+
x
1.3.1 Dzielenie wielomianów
Wielomiany mo˙ na te˙ dzieli´ . Mamy
z
z
c
Twierdzenie 1.2
Dla dowolnych dwóch wielomianów
W
(x)
i
V
(x)
istnieja dwa wielo-
˛
miany
Q(x)
i
R(x)
takie ze
˙
(a)
W
(x) =
V
(x)
·
Q(x)
+
R(x)
(b)
st(R(x)) < st(V
(x))
Wielomian
Q(x)
nazywamy ilorazem a
R(x)
reszta z dzielenia
W
(x)
przez
V
(x).
Iloraz
˛
i reszta sa wyznaczone jednoznacznie, to znaczy istnieje tylko jedna para
Q(x), R(x)
˛
spełniajaca warunki (a) i (b).
˛
Dowód:
Najpierw przedstawimy

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin