mat_dys.pdf

(236 KB) Pobierz
Matematyka dyskretna (tryb zaoczny) - cz. I
Matematyka dyskretna (tryb zaoczny) – cz. I
TEORIA GRAFÓW
Z
Z - zbiór liczb całkowitych dodatnich { }
..., -
-
2
1
2
,...
}
1
,...
Z - zbiór liczb całkowitych ujemnych {
..., -
-
2
1
R - zbiór liczb rzeczywistych
Funkcje całkowitoliczbowe
f
:
R
®
Z
1) Funkcja podłoga („ floor ”)
É Ù
x
=
max
{
n
:
n
Î
Z
Ù
n
£
x
2 =
É Ù
2
1 =
É Ù
75
1
-
2
75
=
-
3
É Ù
e
=
2
É Ù
- p
=
-
4
2) Funkcja sufit („ ceiling ”)
Ç ×
min
Najmniejsza liczba całkowita, która jest wi ksza b d równa x
Ç ×
x
=
{
n
:
n
Î
Z
Ù
n
³
x
0 =
Ç ×
1
-
2
75
=
-
2
Ç ×
p
=
4
je eli
n Î , to É Ù Ç ×
N
n =
n
je eli
n Ï , to Ç × É Ù
N
n
= n
=
1
[ x - cz całkowita x
[ ]
x =
É Ù É Ù
É Ù
x
-
x
¹
-
x
Własno ci:
1. É Ù Ç ×
-
x -
=
x
2.
1
-
x
<
É Ù Ç ×
x
£
x
£
x
<
x
+
1
3.
x Î ,
R
n Î
Z
É Ù
x
=
n
Û
n
£
x
<
n
+
1
4. É Ù
x
=
n
Û
x
-
1
<
n
<
x
5. Ç ×
x
=
n
Û
n
-
1
<
x
£
n
6. Ç ×
x
=
n
Û
x
£
n
<
x
+
1
7. É Ù É Ù
x
+
n
=
x
+
n
n Î
Z
8. Ç × Ç ×
x
+
n
=
x
+
n
n Î
Z
É Ù É Ù
e
+
3
=
e
+
3
=
2
+
3
=
5
Ç × Ç ×
2
-
p
=
2
+
-
p
=
2
-
3
=
-
1
Ç ×
- p
=
-
3
Wysza Szkoła Komunikacji i Zarzdzania w Poznaniu
1
Z - zbiór liczb całkowitych
{
=
2
É Ù
Matematyka dyskretna (tryb zaoczny) – cz. I
Niech
x Î
,
R
x +
É Ù É Ù
x + É Ù É Ù
y
y
1
45
+
1
95
=
3
40
=
3
É Ù É Ù
1
45
+
1
95
=
1
+
1
=
2
--
Mantysa liczby, cz ułamkowa
{ } ( )
x
=
m
x
=
x
-
É Ù
x
0
£
{ }
É Ù
x
<
1
{ x
x
=
x
+
np.
{ }
3
25
=
3
25
-
É Ù
3
25
=
3
25
-
3
=
0
25
{
-
3
25
}
=
-
3
25
-
É Ù
-
3
25
=
-
3
25
-
( ) 75
-
4
=
0
Przykłady zastosowa :
n
Î N
+
m - długo słowa w zapisie dwójkowym
10
2
1
1
m = 1
2
10
m = 2
3
11
m = 3
m
=
É Ù
log
2
n
+
1
=
( Ç ×
log
2
n
+
1
4
100
m = 3
n
=
8
m
=
? =
4
5
101
m = 3
É Ù É Ù
log 2
8
+
1
=
3
+
1
=
4
6
110
m = 3
É Ù É Ù É Ù
log
8
=
log
2
3
=
3
log
2
2
2
2
7
111
m = 3
( Ç × Ç ×
log 2
8
+
1
=
3
1699
=
4
n
=
32000
m
=
?
É
log 2
32000
Ù É Ù
+
1
=
14
.
9658
...
+
1
=
14
+
1
=
15
f
:
R
®
R
funkcja rosn ca okre lona na liczbach rzeczywistych
( ) ( )
2
x
1
<
x
2
¼
f
x
1
<
f
x
( É Ù É ( É Ù
f
x
=
f
x
( Ç × Ç ( Ç ×
f
x
=
f
x
np.
x
( ) x
0
f =
É Ù É É Ù É Ù É Ù
x
4
75
=
4
75
=
4
=
2
=
2
Ç × Ç Ç × Ç × Ç ×
15
.
99
=
15
.
99
=
16
=
4
=
4
É Ù É É Ù É Ù 3
10
.
24
=
10
.
24
=
10
=
--
Liczby Kuuth’a
Liczby zdefiniowane wzorem rekurencyjnym
1
k
0
=
2
Wysza Szkoła Komunikacji i Zarzdzania w Poznaniu
É Ù
>
321799364.006.png 321799364.007.png 321799364.008.png
Matematyka dyskretna (tryb zaoczny) – cz. I
k
=
1
+
min
Å
Æ
2
×
k
,
×
k
Õ
Ö
n
+
1
Å
È
n
Ø
È
n
Ø
Õ
É
Ù
É
Ù
2
3
k
=
k
=
1
+
min
Å
Æ
2
×
k
,
×
k
Õ
Ö
=
1
+
min
(
2
×
k
,
×
k
)
=
1
+
2
=
3
2
1
+
1
Å
È
1
Ø
È
1
Ø
Õ
0
0
É
Ù
É
Ù
2
3
k
=
k
=
1
+
min
Å
Æ
2
×
k
,
×
k
Õ
Ö
=
1
+
min
(
2
×
k
,
×
k
)
=
1
+
3
=
4
3
2
+
1
Å
È
2
Ø
È
2
Ø
Õ
1
0
É
Ù
É
Ù
2
3
k
=
k
=
1
+
min
Å
Æ
2
×
k
,
×
k
Õ
Ö
=
1
+
min
(
2
×
k
,
×
k
)
=
1
+
2
=
3
1
0
+
1
Å
È
0
Ø
È
0
Ø
Õ
0
0
É
Ù
É
Ù
2
3
n Î
,
Z
Ç
n
×
+
Ç
n
-
1
×
+
Ç
n
-
2
×
+
...
+
Ç
n
-
(
m
-
1
×
=
n
È
Ø
È
Ø
È
Ø
È
Ø
m
m
m
m
np. n = 18 m = 4
m składników
Ç
18
×
+
Ç
18
-
1
×
+
Ç
18
-
2
×
+
Ç
18
-
3
×
=
Ç × Ç × Ç × Ç ×
4
×
5
+
4
25
+
4
+
3
75
=
5
+
5
+
4
+
4
=
18
È
Ø
È
Ø
È
Ø
È
Ø
4
4
4
4
S ´ - produkt kartezja ski dwóch zbiorów
A , B - zbiory
( )
A
´
B
=
{
a
,
b
:
a
Î
A
,
b
Î
B
S
´
S
=
{
( )
a
,
b
:
a
Î
S
,
b
Î
S
}
Ì
Relacja binarna = dowolny podzbiór produktu kartezja skiego
( ) R
S
´
S
a Î
,
= aRb
element a jest w relacji binarnej R z elementem b
--
Relacja kongruencji (relacja przystawania)
mod , gdzie
p
p Î
Z
(
m - jest wielokrotno ci liczby p , tzn. e istnieje liczba k taka, e
n
)
(
m
- )
n
=
k
×
p
m
º
n
(
mod
p
)
p
=
33
m
=
n
=
15
33 º
15
(
mod
6
) ?
18
=
3
×
6
k p
(
m
-
n
)
=
k
×
p
(
33
-
15
)
=
k
×
6
18
= k
×
6
Wysza Szkoła Komunikacji i Zarzdzania w Poznaniu
3
Ä
Ô
Ä
Ô
Ä
Ô
Ä
Ô
--
S – zbiór liczbowy
S
R
6
321799364.009.png 321799364.001.png
Matematyka dyskretna (tryb zaoczny) – cz. I
k
=
18
=
3
6
Te dwie liczby (33, 15) przystaj do siebie
mod
6
33 º
12
(
mod
7
) ?
tak
33 º
40
(
mod
7
) ?
tak
33 º
19
(
mod
7
) ?
tak
Dwie liczby przystaj do siebie, je eli istnieje takie k , e
(
m
- )
n
=
k
×
p
(
m
º
n
(
mod
p
)
)
Liczba m przystaje do liczby n
mod , je eli obie te liczby s podzielne przez p (maj tak
p
sam reszt z dzielenia)
r – reszta z dzielenia
r
m
=
k
×
p
+
p
> r
³
0
0
£
r <
p
m
=
17
m
=
-
17
p
=
3
p
=
3
17
=
5
×
3
+
2
-
17
=
-
6
×
3
+
1
n
=
j
×
p
+
r
m
-
n
=
k
×
p
+
r
-
(
j
×
p
+
r
)
=
k
×
p
+
j
×
p
=
(
k
-
j
)
×
p
(
m
-
n
)
=
k
×
p
załó my, e
m
=
l
×
p
+
r
n
=
j
×
p
+
r
m
-
n
=
( )
l
-
j
×
p
+
(
r
1
-
r
2
)
r
1
- r
2
=
0
r =
1
r
2
0
£
r <
1
p
0
£
r <
2
p
-
p
<
r
1
-
r
2
<
p
Podstawowe własno ci relacji przystawania
1.
m Î
Z
p Î
Z
p
>
1
Ú własno ci zwrotno ci
m
º
m
(
mod
p
)
m jest w relacji przystawania z samym sob
2. Je eli
m
º
n
(
mod
p
)
, to
n
º
m
(
mod
p
)
- własno symetrii
33 º
15
(mod
6
13
-
33
=
k
6
×
6
33
-
15
=
k
×
6
-
18
=
k
×
18
= k
×
6
18
18
=
k
-
=
k
6
6
k
=
3
k
=
-
3. Je eli
m
º
n
(
mod
p
)
oraz
n
º
s
(
mod
p
)
, to wówczas
m
º
s
(
mod
p
)
- własno
przechodnio ci
4
Wysza Szkoła Komunikacji i Zarzdzania w Poznaniu
321799364.002.png 321799364.003.png
Matematyka dyskretna (tryb zaoczny) – cz. I
np.
33 º
15
(
mod
6
)
15 º
9
(
mod
6
)
33 º
9
(
mod
6
)
33
-
15
=
k
×
6
15
-
9
=
k
×
6
33
-
9
=
k
×
6
18
= k
×
6
6
= k
×
6
24
= k
×
6
18
6
24
=
k
=
k
=
k
6
6
6
k
=
3
k
=
1
k
=
4
Ka da relacja, która jest zwrotna, symetryczna i przechodnia jest relacj równowa no ci .
--
x Î
[ ]
S
x - zbiór wszystkich elementów zbioru S , które s w relacji R z elementem x .
( R – relacja równowa no ci)
x Î
,
y
S
[ ]
x [ ]
y albo [ ] [ ]
x = albo [ ] [ ] 0
y
x
Ù y
=
[ ]
x
p
=
{
m
: º
x
n
(
mod
p
)
}
p – ilo klas
1
£ r
£
np.
=
2
0
-
(
-
4
=
4
=
2
×
2
[ ] {
0 2
=
...,
-
4
-
2
0
2
4
,...
}
2
-
(
-
4
=
6
=
3
×
2
[ ] {
2
2
=
...,
-
4
-
2
0
4
6
,...
}
[ ] {
4
2
=
...,
-
4
-
2
4
,...
}
[ ] 2
4 - klasa wyznaczona przez 4, gdzie
p
=
2
[ ] [ ] [ ] ...
0
2
=
2
2
=
4
2
=
- zbiór liczb parzystych
[ ] [ ] [ ] ...
2
=
3
2
=
5
2
=
- zbiór liczb rzeczywistych
p
=
3
[ ] 3
r
=
0
{
...,
-
9
-
6
-
3
,...
}
r
=
1
{
...,
-
8
-
5
-
2
4
7
,
10
,...
}
r
=
2
{
...,
-
7
,
-
4
-
1
2
11
,...
}
[…]
f
( )
n
=
O
( ) Û
g
( )
n
istnieje
C
>
0
takie, e ( )
f
n
=
C
×
g
( )
dla dost. du ych warto ci n
3) Je eli ( )
f
n
=
O
a
( )
n
i ( )
g
n
=
O
b
( )
n
¼
f
( ) ( )
n
×
g
n
=
O
(
a
( ) ( )
n
×
b
n
)
Wysza Szkoła Komunikacji i Zarzdzania w Poznaniu
5
0
p
1
n
321799364.004.png 321799364.005.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin