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čna.
(antisim) Za antisimetričnost ne smiju postojati x != y
takvi da xryrx. Takvi zaista ne postoje, što se može
provjeriti ispitivanjem svih slučajeva, ali može i ovako:
vidimo da je u svakom uređenom paru xry ispunjeno
x<=y (možemo reći, 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,
što bi povlačilo x=y. Iz toga vidimo da je podrelacija
antisimetrične relacije ponovo antisimetrična.
(tranz) Štoviše, bolje pogledavši, vidimo da je r
zapravo relacija < na S, kojoj je dodan
još par (4,4). Iz toga direktno slijedi da je tranzitivna
(što se također može dobiti Dz provjerom svih slučajeva).
Naime, neka je xryrz. To znači ili
x<y<z (u kom slučaju je i x<z, pa i
xrz), ili su bar dva od
x,y,z četvorke. U potonjem
slučaju, ako je x=4, tad očito svi moraju biti 4, pa je
ok. Inače, y=z(=4), pa xry znači isto što 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ćih tvrdnji:
- Nijedan od njih nije položio ispit iz EM1,
- Oba su položila EM1, s istom ocjenom, ili
- A je položio EM1, a B nije.
Odredite svojstva relacije EM.
Hi Refleksivna i tranzitivna jest. Ako postoje bar dva studenta
koja nisu položila EM1, i bar jedan koji jest, nije ni simetrična ni
antisimetrična.
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žite da je r relacija ekvivalencije, i odredite
kvocijentni skup S/r.
Rj Da bismo dokazali da je r RE, trebamo dokazati
njenu refleksivnost, simetričnost 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čito vrijedi i s druge strane, xrx. Dakle,
preostalo je samo provjeriti 1r3 , 3r1 i 4r5 ,
5r4.
(tranz) Idemo po svim slučajevima. Opet, parove jednakih ne treba
provjeravati jer: (1) ako je x=y, tada yrz
znači xrz; i (2) ako je y=z, tada
xry znači xrz. Dakle, strategija je: idemo s
(x,y); x != y po r, i za svaki takav par
tražimo 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žimo one
z !=3 za koje vrijedi 3rz. Lako se vidi da je
jedini takav z=1. No tada xrz znači
1r1, a to vrijedi.
(x,y)=(3,1). y=1. Jedini z
različit 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đujemo 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đaj?
Z Na skupu {1..5} definirajte jednu RE koja ima
točno 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}}.