Diskreetti matematiikka
, syksy 2010
Harjoitus 5 (14.-15.10., to 16-18 M107, pe 12-14 M107)
Olkoon
S
Í
X
×
X
transitiivinen relaatio. Osoita, että
S
k
Í
S
kaikilla
k
Î
N
.
Onko matriisin
M
: =
æ
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
è
0
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
1
1
1
1
0
0
1
0
0
0
1
0
0
0
1
1
1
1
1
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
1
1
1
1
0
0
1
0
1
0
1
0
0
1
0
0
1
0
1
0
1
0
0
0
ö
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
ø
edustama relaatio transitiivinen?
Olkoon
X
: = {
x
1
,
x
2
,
x
3
,
x
4
,
x
5
} ja
R
: = {(
x
1
,
x
2
), (
x
2
,
x
5
), (
x
3
,
x
1
), (
x
4
,
x
2
)}. Muodosta transitiivinen sulkeuma [
`
(
R
)]
t
a) suoraan päättelemällä,
b) laskemalla matriisin
M
R
avulla.
Olkoon
X
äärellinen joukko, jossa on
n
alkiota ja olkoon
R
Í
X
×
X
relaatio. Todista:
Jos
p
Î
N
ja
xR
n
+
p
z
, niin
xR
k
z
jollakin
k
Î
[
n
].
Olkoot
X
ja
R
kuten tehtävässä
4
. Osoita kyseisen tehtävän avulla, että transitiivinen sulkeuma on laskettavissa äärellisenä yhdisteenä
R
t
=
n
È
k
=1
R
k
.
Näytä lisäksi, että voi olla aidosti
È
k
=1
n
-
1
R
k
Ì
[
`
(
R
)]
t
.
Mitkä seuraavista reaalilukujen joukossa määritellyistä relaatioista ovat ekvivalenssirelaatioita?
a)
xRy
Û
x
-
y
on luvun 3 kokonaislukupotenssi
b)
xRy
Û
x
+
y
on pariton tai
x
=
y
c)
xRy
Û
x
2
=
y
2
Määritä (myönteisissä tapauksissa) ekvivalenssiluokat.
Mikä on se ekvivalenssirelaatio, joka määrää osituksen {{1, 2, 3}, {4, 5} } joukkoon
X
: = {1, 2, 3, 4, 5}?
File translated from T
E
X by
T
T
H
, version 3.80.
On 05 Oct 2010, 15:21.