# Relazioni binarie
Sia $A$ un insieme. Una relazione binaria $R$ di $A$ in sè, è un sottoinsieme del prodotto cartesiano $AxA$.
Una relazione $R$ è riflessiva se $AA a in A$ $(a,a) in R$.
Una relazione $R$ è simmetrica se $(a,b) in R=>(b,a) in R$.
Una relazione $R$ è transitiva se $(a,b) in R$ e $(b,c) in R=>(a,c) in R$.
Ciò premesso, si consideri l'insieme $A={x,y,z,w}$.
(i) Quante relazioni binarie si possono definire su $A^2$?
Tra queste, quante sono:
(ii) riflessive;
(iii) simmetriche;
(iv) riflessive, simmetriche e transitive.
Una relazione $R$ è riflessiva se $AA a in A$ $(a,a) in R$.
Una relazione $R$ è simmetrica se $(a,b) in R=>(b,a) in R$.
Una relazione $R$ è transitiva se $(a,b) in R$ e $(b,c) in R=>(a,c) in R$.
Ciò premesso, si consideri l'insieme $A={x,y,z,w}$.
(i) Quante relazioni binarie si possono definire su $A^2$?
Tra queste, quante sono:
(ii) riflessive;
(iii) simmetriche;
(iv) riflessive, simmetriche e transitive.
Risposte
Con "Quante relazioni binarie si possono definire su $A^2$" intendi quanti insiemi che sono relazioni binarie riesco a definire?
Saluti, Ermanno.
Saluti, Ermanno.
Sì.
Per maggior chiarezza:
il sottoinsieme di $A^2$
$R_1={(w,y)}$ è una relazione binaria, oppure
$R_2={(y,y),(x,y),(y,x)}$.
In generale, un qualsiasi sottoinsieme di $A^2$ è una relazione binaria.
Per maggior chiarezza:
il sottoinsieme di $A^2$
$R_1={(w,y)}$ è una relazione binaria, oppure
$R_2={(y,y),(x,y),(y,x)}$.
In generale, un qualsiasi sottoinsieme di $A^2$ è una relazione binaria.
OK! E quindi, ad esempio, $R1$ come da te definita non è nelle relazioni riflessive...giusto?
Saluti, Ermanno.
Saluti, Ermanno.
Vero, e neanche la $R_2$. La $R_2$ è simmetrica.
Per essere riflessiva deve contenere tutte le coppie
$(x,x),(y,y),(z,z),(w,w)$.
Per essere riflessiva deve contenere tutte le coppie
$(x,x),(y,y),(z,z),(w,w)$.
Credo di aver capito...per quanto riguarda le riflessive!
Dato un insieme $A$, $|P(A)|=2^{|A|}$. Ora se abbiamo l'insieme $A^2$, $|A^2|=|A|^2$. Quindi $|P(A^2)|=2^{|A^2|}=2^{|A|^2}$. Essendo una relazione un sottoinsieme del prodotto cartesiano, si ha che il numero di relazioni è proprio $2^{|A|^2}$. Rappresentiamo le relazioni binarie con una matrice quadrata di ordine $|A|$, dove ogni elemento della matrice può assumere valore $0$ oppure valore $1$. Ora le relazioni binarie riflessive nella nostra rappresentazione assumono valore $1$ quando gli indici di riga e colonna sono uguali, cioè gli elementi della diagonali principale. Per definire una relazione riflessiva devo scegliere il valore che dovranno assumere le $|A|^2-|A|$ celle rimanenti. Il numero di relazioni riflessive sarà quindi $2^{|A|^2-|A|}$.
Per gli altri casi ci sto pensando
Saluti, Ermanno.
Dato un insieme $A$, $|P(A)|=2^{|A|}$. Ora se abbiamo l'insieme $A^2$, $|A^2|=|A|^2$. Quindi $|P(A^2)|=2^{|A^2|}=2^{|A|^2}$. Essendo una relazione un sottoinsieme del prodotto cartesiano, si ha che il numero di relazioni è proprio $2^{|A|^2}$. Rappresentiamo le relazioni binarie con una matrice quadrata di ordine $|A|$, dove ogni elemento della matrice può assumere valore $0$ oppure valore $1$. Ora le relazioni binarie riflessive nella nostra rappresentazione assumono valore $1$ quando gli indici di riga e colonna sono uguali, cioè gli elementi della diagonali principale. Per definire una relazione riflessiva devo scegliere il valore che dovranno assumere le $|A|^2-|A|$ celle rimanenti. Il numero di relazioni riflessive sarà quindi $2^{|A|^2-|A|}$.
Per gli altri casi ci sto pensando
Saluti, Ermanno.
Ok
Per le relazioni simmetriche, considerando sempre la matrice di rappresentazione, gli elementi che assumono valore $1$ sono quelli del triangolo che i lati della matrice formano con la diagonale principale. Il numero di elementi contenuti in questo triangolo è $(n*(n+1))/2$. Quindi il numero di relazioni simmetriche sarà $2^((n*(n+1))/2)$.
Le relazioni riflessive, simmetriche e transitive sono le cosidette relazioni di equivalenza. Contare quante relazioni di equivalenza è possibile definire su un insieme $A$ è equivalente a contare quante partizioni in sottoinsiemi disgiunti ammette questo insieme $A$. Il numero di partizioni di questo tipo (numero di relazioni di equivalenza) si calcola con i numeri di Bell. Sia $|A|=n+1$, ho che $B_{n+1}=sum_{k=0}^nB_k((n),(k))$
Saluti, Ermanno.
Le relazioni riflessive, simmetriche e transitive sono le cosidette relazioni di equivalenza. Contare quante relazioni di equivalenza è possibile definire su un insieme $A$ è equivalente a contare quante partizioni in sottoinsiemi disgiunti ammette questo insieme $A$. Il numero di partizioni di questo tipo (numero di relazioni di equivalenza) si calcola con i numeri di Bell. Sia $|A|=n+1$, ho che $B_{n+1}=sum_{k=0}^nB_k((n),(k))$
Saluti, Ermanno.
Bene.
Per le relazioni simmetriche il denominatore deve stare ad esponente:
$2^((n(n+1))/2$, ma chiaramente è una svista.
Per le relazioni simmetriche il denominatore deve stare ad esponente:
$2^((n(n+1))/2$, ma chiaramente è una svista.
"Piera":
Bene.
Per le relazioni simmetriche il denominatore deve stare ad esponente:
$2^((n(n+1))/2$, ma chiaramente è una svista.
Eh sì, un errore nella parentesizzazione.
Comunque davvero interessanti questi ultimi quesiti che hai postato. Sempre così!
Saluti, Ermanno.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo