05 02 2013

Pagina 1

LOGICA E ALGEBRA 5 febbraio 2013 I PARTE ESERCIZIO 1 Si consideri la relazione R sull’insieme X = {a, b, c, d} avente la seguente matrice d’incidenza: MR =             0010 0000 0100 0001 1. Si dica perché R non è una relazione d’equivalenza e si costruisca la relazione d’equivalenza S generata da R. 2. Si determini l’insieme quoziente X / S. 3. Si stabilisca se R è una relazione d’ordine. In caso negativo si costruisca, se esiste, la minima relazione d’ordine T contenente R e si determinino gli elementi massimali, minimali, massimo e minimo di X rispetto a T. 4. Si calcoli il numero di funzioni contenute in R e in S. Si scrivano poi le matrici di incidenza di tutte le funzioni invertibili contenute in S. Traccia di soluzione 1. R non è una relazione d’equivalenza perché, ad esempio, non è riflessiva infatti sulla diagonale principale ci sono degli zeri. Costruiamo la chiusura riflessiva e simmetrica R’ di R: MR’ =             1010 0110 1110 0001 Per costruire la chiusura transitiva di R’ calcoliamo le potenze di R’: M(R’) 2 =             1110 1110 1110 0001 = M(R’) 3 Poiché S =  Nn nR  )'( segue che MS =             1110 1110 1110 0001 . 2. La relazione S ha due classi di equivalenza: [a]S = {a} [b]S = {b, c, d} quindi X / S = {[a]S , [b]S }. 3. R non è una relazione d’ ordine perché, ad esempio, non è riflessiva. Poiché R è antisimmetrica può esistere una relazione d’ordine contenente R. Costruiamo la chiusura riflessiva R” di R: MR” =             1010 0100 0110 0001 Per costruire la chiusura transitiva R”’ di R” calcoliamo le potenze di R”: M(R”) 2 =             1110 0100 0110 0001 = M(R”) 3 Poiché R”’ =  Nn nR  )"( segue che MR”’ =             1110 0100 0110 0001 ed essendo R”’…