Come si capisce dalla matrice di una relazione quante funzioni contiene?
Ho un esercizio che data la relazione sullo stesso insieme, espressa in matrice qui sotto, chiede quante funzioni ammette
$((0,1,0,0,0,0),(0,0,1,0,0,0),(0,0,1,0,0,0),(0,0,0,0,1,0),(0,0,0,0,1,0),(1,1,0,0,0,0))$
La soluzione dice: dato che c'è almeno un 1 in ogni riga e nel'ultima ci sono due 1, R contiene 2 funzioni...non mi dice come ha trovato il risultato però.... sono 2 funzioni perchè ci sono al massimo due 1 tipo?
edit: "deducendo" da esercizi simili mi pare sia moltiplicare il numero di 1 di ogni riga, quindi qui il risultato è 1*1*1*1*1*2=2, giusto?
$((0,1,0,0,0,0),(0,0,1,0,0,0),(0,0,1,0,0,0),(0,0,0,0,1,0),(0,0,0,0,1,0),(1,1,0,0,0,0))$
La soluzione dice: dato che c'è almeno un 1 in ogni riga e nel'ultima ci sono due 1, R contiene 2 funzioni...non mi dice come ha trovato il risultato però.... sono 2 funzioni perchè ci sono al massimo due 1 tipo?
edit: "deducendo" da esercizi simili mi pare sia moltiplicare il numero di 1 di ogni riga, quindi qui il risultato è 1*1*1*1*1*2=2, giusto?
Risposte
Penso sarebbe il caso di esprimerlo meglio: su un insieme con $6$ elementi, numerati dagli elementi di $I=\{1,..,6\}$, definiamo una matrice $6\times 6$ a partire da una relazione su $I$: $A_R$ ha ingresso $1$ nei posti di indice $(i,j)$ se $(i,j)\in R$, e $0$ altrimenti.
Ora, la domanda che hai fatto non è chiara: probabilmente ti viene chiesto di dire quali di queste matrici corrispondono a relazioni su $I$ che sono in realtà funzioni $I\to I$?
Ora, la domanda che hai fatto non è chiara: probabilmente ti viene chiesto di dire quali di queste matrici corrispondono a relazioni su $I$ che sono in realtà funzioni $I\to I$?
@ fmnq: L’esercizio chiede di stabilire quante sottorelazioni contenute nella relazione assegnata (mediante la matrice di incidenza del suo grafo) sono funzioni di $I$ in sé.
@wattbatt: La risposta è $2$, come detto.
Il ragionamento è il seguente: la matrice di incidenza del grafo ti mostra che ad ognuno dei “primi” cinque dei sei elementi di $I$ è associato un unico elemento di $I$, mentre al sesto elemento la relazione associa due elementi di $I$ (ricorda: la presenza di un $1$ su una riga è segno di associazione dell’elemento “indice di riga” con l’elemento “indice di colonna” corrispondente all’entrata $1$); dunque hai una sola possibile associazione per ognuno dei “primi” cinque elementi, e due possibili associazioni per il sesto.
Ne viene che le uniche sottorelazioni della relazione assegnata che sono funzioni sono funzioni di $I$ in sé sono esattamente $2$.
In generale, la regola che deduci è corretta ed è essenzialmente di natura combinatoria.
Se hai $k$ alternative, ognuna delle quali si presenta in $n_k$ modalità, il totale di combinazioni possibili è dato dal prodotto $n_1*n_2* ... * n_k$.
@wattbatt: La risposta è $2$, come detto.
Il ragionamento è il seguente: la matrice di incidenza del grafo ti mostra che ad ognuno dei “primi” cinque dei sei elementi di $I$ è associato un unico elemento di $I$, mentre al sesto elemento la relazione associa due elementi di $I$ (ricorda: la presenza di un $1$ su una riga è segno di associazione dell’elemento “indice di riga” con l’elemento “indice di colonna” corrispondente all’entrata $1$); dunque hai una sola possibile associazione per ognuno dei “primi” cinque elementi, e due possibili associazioni per il sesto.
Ne viene che le uniche sottorelazioni della relazione assegnata che sono funzioni sono funzioni di $I$ in sé sono esattamente $2$.
In generale, la regola che deduci è corretta ed è essenzialmente di natura combinatoria.
Se hai $k$ alternative, ognuna delle quali si presenta in $n_k$ modalità, il totale di combinazioni possibili è dato dal prodotto $n_1*n_2* ... * n_k$.
Da che cosa si sarebbe potuta dedurre questa interpretazione del testo?
@fmnq: Da una lettura attenta del testo, soprattutto della soluzione esposta (male, ma ciò non esime dal leggere con attenzione anche quella) e sfruttando l’esperienza accumulata in anni di servizio sul forum e nell’università/scuola. 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo