intro7.pdf
(
89 KB
)
Pobierz
381442680 UNPDF
WSTE¸PDOMATEMATYKI
Lista7
1.
Zbada¢,którezponi»szychrelacjis¡relacjamiporz¡dku(cz¦±ciowego,liniowego,dobrego).
Wyznaczy¢-oileistniej¡-elementymaksymalne,minimalne,najwi¦kszeinajmniejsze.
(
a
)
P
(
X
)
zrelacj¡inkluzji
;
(
b
)
X
6
=
;
,x,y
2
X,x
y
$
x
=
y
;
(
c
)
x
i
,y
i
2
R
,
(
x
1
,y
1
)
(
x
2
,y
2
)
$
(
x
1
<x
2
)
_
(
x
1
=
x
2
^
y
1
¬
y
2
);
(
d
)(
X,
¬
X
)
,
(
Y,
¬
Y
)
dowolnezbiorydobrzeuporz¡dkowane,,x
1
,x
2
2
X,y
1
,y
2
2
Y,
(
x
1
,y
1
)
(
x
2
,y
2
)
$
(
x
1
¬
X
x
2
^
x
1
6
=
x
2
)
_
(
x
1
=
x
2
^
y
1
¬
Y
y
2
);
(
e
)
k,l
2
N
\{
0
,
1
,
}
,x
y
$
x
|
y
;
2.
Rozwa»myrelacj¦
zdefiniowan¡wpodpunkcie(
c
)zadania1.Wskaza¢(oileistniej¡)elementy
maksymalne,minimalne,najwi¦kszyinajmniejszywnast¦puj¡cychzbiorach:
{
(
x,y
):
x
2
+
y
2
¬
1
}
,
{
(
x,y
):
x
2
+
y
2
<
4
}
,
{
(
x,y
):
x
2
[
−
1
,
1]
,y
2
[0
,
1
)
}
.
3.
Wzbiorze
P
(N)wprowadzili±myrelacj¦równowa»no±ci=
?
(lista6,zad.5(a)).Niech[
A
]
,
[
B
]
2
P
(N)
/
=
?
b¦d¡klasamiabstrakcjiwyznaczonymiprzezzbiory
A,B
N
.
Definiujemyrelacj¦:
[
A
]
?
[
B
]
$
A
\
Bjestzbioremsko
´
nczonym.
Pokaza¢,»ejesttopoprawniezdefiniowanarelacjacz¦±ciowegoporz¡dkuna
P
(N)
/
=
?
.
Wyznaczy¢jej
elementynajmniejszyinajwi¦kszy.
4.
Zakładamy,»e
F
jestultrafiltremna
P
(
X
)
,Y
=R
.
Wzbiorze
X
Rwprowadzili±myrelacj¦=
F
(lista7,zad.5(d)).Pokaza¢,»erelacjazdefiniowanawzorem:
[
f
]
F
[
g
]
${
x
2
X
:
f
(
x
)
¬
g
(
x
)
}2
F
jestcz¦±ciowymporz¡dkiemw
X
R
.
Czyjesttoporz¡dekliniowy?
5.
Drzewobinarne:
Niech
B
oznaczazbiórwszystkichsko«czonychci¡gówzero-jedynkowych(tj.
funkcjipostaci
{
0
,
1
,...,n
}!{
0
,
1
}
).Zakładamy,»e
p,q
2B
.
Pokaza¢,»e
B
jestcz¦±ciowouporz¡dkowany
relacj¡inkluzji(
).
Gał¦zi¡
drzewa
B
nazywamymaksymalnyliniowouporz¡dkowanypodzbiór
B
.
Pokaza¢,»eka»dagał¡¹jestdobrzeuporz¡dkowana,oraz»ewyznaczawsposóbjednoznacznypodzbiór
zbioruN
.
Inaodwrót,ka»dypodzbiór
A
Nwyznaczadokładniejedn¡gał¡¹drzewabinarnego.
ZADANIEDOMOWE
Lista7
1.
Zbada¢,którezponi»szychrelacjis¡relacjamiporz¡dku(cz¦±ciowego,liniowego,dobrego).
Wyznaczy¢-oileistniej¡-elementymaksymalne,minimalne,najwi¦kszeinajmniejsze.
(
a
)
k,l
2
N
,k
l
$
l
¬
k
;
(
b
)
x
i
,y
i
2
[0
,
1)(
x
1
,y
1
)
(
x
2
,y
2
)
$
(
x
1
<x
2
)
_
(
x
1
=
x
2
^
y
1
¬
y
2
);
(
c
) [0
,
1]
,
[0
,
1)
,
(0
,
1]
,
(0
,
1
)
zporz¡dkiemdziedziczonymz
R;
(
d
) (
X,
¬
X
)
,dowolnyzbiórdobrzeuporz¡dkowany,,x
1
,x
2
,y
1
,y
2
2
X,
(
x
1
,y
1
)
(
x
2
,y
2
)
$
max
{
x
1
,y
1
}
<
max
{
x
2
,y
2
}_
(max
{
x
1
,y
1
}
=max
{
x
2
,y
2
}^
x
1
<x
2
)
_
_
(max
{
x
1
,y
1
}
=max
{
x
2
,y
2
}
x
1
=
x
2
^
y
1
¬
y
2
);
2.
Rozwa»myrelacj¦
zdefiniowan¡wpodpunkcie(
b
)zadania1.Wskaza¢(oileistniej¡)elementy
maksymalne,minimalne,najwi¦kszyinajmniejszywnast¦puj¡cychzbiorach:
{
(
x,y
):
x
2
+
y
2
<
1
}
,
{
(
x,y
):
x
2
+
y
2
<
1
4
}
,
{
(
x,y
):
x
2
[0
,
1
2
]
,y
2
[
1
2
,
3
4
)
}
.
3.
Wzbiorze
N
Nwprowadzili±myrelacj¦równowa»no±ci=
?
(lista7,zad.5(b)).Niech
f,g
b¦d¡
dowolnymici¡gamiliczbnaturalnych,azbiory[
f
]
,
[
g
]wyznaczonymiprzeznieklasamiabstrakcji.
Definiujemyrelacj¦:
[
f
]
?
[
g
]
${
n
:
f
(
n
)
>g
(
n
)
}
jestzbioremsko
´
nczonym.
Pokaza¢,»ejesttopoprawniezdefiniowanarelacjacz¦±ciowegoporz¡dkuna
N
N
/
=
?
.
Wyznaczy¢jej
elementnajmniejszy.Pokaza¢,»eka»dyprzeliczalnypodzbiórjestograniczony.
4.
Mówimy,»erelacja
jestostrymporz¡dkiemna
X,
je»elijestprzechodniaiantyzwrotna(tzn.
8
x
2
X
¬
(
x
x
)).Udowodni¢,»e:
(a)Je»eli
jestostrymporz¡dkiemna
X,
torelacja
zadanawzorem:
x
y
$
x
y
_
x
=
y
jestporz¡dkiemcz¦±ciowymna
X
.
(b)Je»eli
jestporz¡dkiemcz¦±ciowymna
X,
torelacja
zadanawzorem
x
y
$
x
y
^
x
6
=
y
jestostrymporz¡dkiem.
5.
WzbiorzeZokre±lamyrelacj¦:
k
l
$
((
k
·
l<
0
^
k>l
)
_
(
k
·
l
0
^|
k
|¬|
l
|
)
.
(a)Sprawdzi¢,czytarelacjajestdobrymporz¡dkiemwzbiorzeZ
.
(b)Sprawdzi¢,czyzbiory(N
,
¬
)oraz(Z
,
)s¡porz¡dkowoizomorficzne(tzn.czyistniejemi¦dzynimi
zachowuj¡caporz¡dekbijekcja).
Plik z chomika:
Jaszczomp
Inne pliki z tego folderu:
intro1.pdf
(93 KB)
intro10.pdf
(80 KB)
intro11.pdf
(125 KB)
intro2.pdf
(78 KB)
intro3.pdf
(88 KB)
Inne foldery tego chomika:
inne
PG
PP
PW
PWJSTK
Zgłoś jeśli
naruszono regulamin