3206.

80.a)

TEKST ZADATKA

U skupu reči A={I, ILI, ALI, NE, A} A = \{\text{I, ILI, ALI, NE, A}\} uvedena je relacija r1ρr2⇔ r_1 \rho r_2 \Leftrightarrow reči r1 r_1 i r2 r_2 su iste dužine (na primer, ILI ρ \rho ALI). Dokazati da je ρ \rho relacija ekvivalencije na skupu A. A .

REŠENJE ZADATKA

Da bi relacija ρ \rho bila relacija ekvivalencije, ona mora ispunjavati tri svojstva: refleksivnost, simetričnost i tranzitivnost.

Prvo proveravamo refleksivnost. Za svaku reč r∈A r \in A važi da je njena dužina jednaka samoj sebi. Prema tome, svaka reč je u relaciji sa samom sobom.

(∀r∈A)  rρr(\forall r \in A) \; r \rho r

Zatim proveravamo simetričnost. Neka su r1 r_1 i r2 r_2 proizvoljne reči iz skupa A A takve da važi r1ρr2. r_1 \rho r_2 . To znači da su one iste dužine. Iz toga trivijalno sledi da i reč r2 r_2 ima istu dužinu kao reč r1, r_1 , pa važi i r2ρr1. r_2 \rho r_1 .

(∀r1,r2∈A)  r1ρr2⇒r2ρr1(\forall r_1, r_2 \in A) \; r_1 \rho r_2 \Rightarrow r_2 \rho r_1

Na kraju proveravamo tranzitivnost. Neka za reči r1,r2,r3∈A r_1, r_2, r_3 \in A važi r1ρr2 r_1 \rho r_2 i r2ρr3. r_2 \rho r_3 . To znači da r1 r_1 ima istu dužinu kao r2, r_2 , a r2 r_2 istu dužinu kao r3. r_3 . Sledi da r1 r_1 i r3 r_3 imaju istu dužinu, odnosno r1ρr3. r_1 \rho r_3 .

(∀r1,r2,r3∈A)  (r1ρr2∧r2ρr3)⇒r1ρr3(\forall r_1, r_2, r_3 \in A) \; (r_1 \rho r_2 \land r_2 \rho r_3) \Rightarrow r_1 \rho r_3

Pošto su ispunjena sva tri svojstva, dokazali smo da je ρ \rho relacija ekvivalencije na skupu A. A .

Kao dodatak, možemo zapisati klase ekvivalencije (količnički skup). Skup A A se razbija na disjunktne podskupove reči koje imaju istu dužinu:

A/ρ={{I, A},{NE},{ILI, ALI}}A / \rho = \{ \{\text{I, A}\}, \{\text{NE}\}, \{\text{ILI, ALI}\} \}