Zadaci s relacijama i njihovim svojstvima
19(kolokvij 01-12-07)Z
Na univerzalnom skupu S:={1..4} dana je binarna
relacija r:={(1,2),(2,3),(3,4),(1,3),(2,4),(4,4),(1,4)}.
Odredite svojstva relacije r.
Rj (refl) Da bi bila refleksivna, mora vrijediti
(A_x)(xrx). No !(1r1), dakle nije
refleksivna.
(irefl) Da bi bila irefleksivna, ne smije postojati nijedan
x takav da je xrx. No 4r4, pa
r nije ni irefleksivna.
(sim) Za svaki par xry moramo provjeriti vrijedi li i
yrx. No 1r2&!(2r1) pokazuje da r
nije ni simetri~cna.
(antisim) Za antisimetri~cnost ne smiju postojati x != y
takvi da xryrx. Takvi zaista ne postoje, ~sto se mo~ze
provjeriti ispitivanjem svih slu~cajeva, ali mo~ze i ovako:
vidimo da je u svakom ure~denom paru xry ispunjeno
x<=y (mo~zemo re~ti, r je
podskup relacije ~ podrelacija od
<= na S). Sad naravno da takvi x
i y ne postoje, jer bi moralo biti i x<=y<=x,
~sto bi povla~cilo x=y. Iz toga vidimo da je podrelacija
antisimetri~cne relacije ponovo antisimetri~cna.
(tranz) ~Stovi~se, bolje pogledav~si, vidimo da je r
zapravo relacija < na S, kojoj je dodan
jo~s par (4,4). Iz toga direktno slijedi da je tranzitivna
(~sto se tako~der mo~ze dobiti Dz provjerom svih slu~cajeva).
Naime, neka je xryrz. To zna~ci ili
x<y<z (u kom slu~caju je i x<z, pa i
xrz), ili su bar dva od
x,y,z ~cetvorke. U potonjem
slu~caju, ako je x=4, tad o~cito svi moraju biti 4, pa je
ok. Ina~ce, y=z(=4), pa xry zna~ci isto ~sto i
xrz. Dakle, r jest tranzitivna.
20(pismeni 02-09-20)Z Na skupu prirodnih brojeva definirana je
relacija $ s: m$n:<=>"3m i 5n daju isti ostatak pri
dijeljenju sa 7". Ispitajte svojstva te relacije.
Rj (refl) Nije. !(1$1) |
(irefl) Nije. 7$7 |
(sim) Nije. 5$3 & !(3$5) |
(antisim) Nije. 7$14 & 14$7 & 7 != 14 |
(tranz) Nije. 3$6 & 6$5 & !(3$5)
21(pismeni 02-04-23)Dz Na skupu studenata prve godine definirana
je relacija EM. Za dva studenta A i
B vrijedi AEMB :akko vrijedi jedna od
sljede~tih tvrdnji:
- Nijedan od njih nije polo~zio ispit iz EM1,
- Oba su polo~zila EM1, s istom ocjenom, ili
- A je polo~zio EM1, a B nije.
Odredite svojstva relacije EM.
Hi Refleksivna i tranzitivna jest. Ako postoje bar dva studenta
koja nisu polo~zila EM1, i bar jedan koji jest, nije ni simetri~cna ni
antisimetri~cna.
23Z Na univerzalnom skupu S:={1..5} zadana je
relacija
r:={(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(4,5),(5,4)}.
Doka~zite da je r relacija ekvivalencije, i odredite
kvocijentni skup S/r.
Rj Da bismo dokazali da je r RE, trebamo dokazati
njenu refleksivnost, simetri~cnost i tranzitivnost.
(refl) Prolazimo po x@S, i provjeravamo
xrx. Vidimo da vrijedi za sve brojeve od 1 do 5 .
(sim) Parove jednakih elemenata xrx sada ne treba provjeravati,
jer za njih o~cito vrijedi i s druge strane, xrx. Dakle,
preostalo je samo provjeriti 1r3 , 3r1 i 4r5 ,
5r4.
(tranz) Idemo po svim slu~cajevima. Opet, parove jednakih ne treba
provjeravati jer: (1) ako je x=y, tada yrz
zna~ci xrz; i (2) ako je y=z, tada
xry zna~ci xrz. Dakle, strategija je: idemo s
(x,y); x != y po r, i za svaki takav par
tra~zimo sve z; != y takve da vrijedi yrz. Za svaki
takav z provjeravamo je li xrz. Idemo:
(x,y)=(1,3). x=1 & y=3. Tra~zimo one
z !=3 za koje vrijedi 3rz. Lako se vidi da je
jedini takav z=1. No tada xrz zna~ci
1r1, a to vrijedi.
(x,y)=(3,1). y=1. Jedini z
razli~cit od 1 koji je u relaciji s 1 , je 3 . xrz sada
postaje 3r3, pa je i to ok.
(x,y)=(4,5). y=5. Jedini
vrijedan razmatranja z=4. 4r4.
x=5 y=4 z=5 . 5r5.
Dakle, r jest RE. Odre~dujemo klase:
[1]r={x:1rx}={1,3}
[2]r={x:2rx}={2}
[3]r=[1]r(*jer 1r3*)={1,3}
[4]r=[5]r={4,5}
Dakle,
S/r={[x]r;x@S}={{1,3},{2},{4,5}}.
(pismeni 02-02-04)Dz Na S:={1..4} dana je relacija
r:={(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(1,3),(3,4),(1,4)}.
Je li to parcijalni ure~daj?
Z Na skupu {1..5} definirajte jednu RE koja ima
to~cno dvije klase.
Rj Zapravo trebamo skup {1..5} podijeliti na dva
neprazna disjunktna podskupa. Valjda je najprirodnija podjela
na parne i neparne
brojeve. Sad je jasno da je relacija "biti iste parnosti".
S/"iste parnosti"={{1,3,5},{2,4}}.