come si capisce dalla matrice di una relazione quante funzioni contiene?

Messaggioda wattbatt » 31/12/2018, 11:26

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?
wattbatt
Junior Member
Junior Member
 
Messaggio: 16 di 116
Iscritto il: 20/09/2016, 16:22

Re: come si capisce dalla matrice di una relazione quante funzioni contiene?

Messaggioda fmnq » 31/12/2018, 17:39

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$?
fmnq
Average Member
Average Member
 
Messaggio: 68 di 764
Iscritto il: 03/10/2017, 23:14

Re: come si capisce dalla matrice di una relazione quante funzioni contiene?

Messaggioda gugo82 » 01/01/2019, 14:25

@ 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$.
Sono sempre stato, e mi ritengo ancora un dilettante. Cioè una persona che si diletta, che cerca sempre di provare piacere e di regalare il piacere agli altri, che scopre ogni volta quello che fa come se fosse la prima volta. (Freak Antoni)
Avatar utente
gugo82
Cannot live without
Cannot live without
 
Messaggio: 20226 di 44915
Iscritto il: 12/10/2007, 23:58
Località: Napoli

Re: come si capisce dalla matrice di una relazione quante funzioni contiene?

Messaggioda fmnq » 01/01/2019, 16:09

Da che cosa si sarebbe potuta dedurre questa interpretazione del testo?
fmnq
Average Member
Average Member
 
Messaggio: 69 di 764
Iscritto il: 03/10/2017, 23:14

Re: come si capisce dalla matrice di una relazione quante funzioni contiene?

Messaggioda gugo82 » 01/01/2019, 16:44

@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. :wink:
Sono sempre stato, e mi ritengo ancora un dilettante. Cioè una persona che si diletta, che cerca sempre di provare piacere e di regalare il piacere agli altri, che scopre ogni volta quello che fa come se fosse la prima volta. (Freak Antoni)
Avatar utente
gugo82
Cannot live without
Cannot live without
 
Messaggio: 20229 di 44915
Iscritto il: 12/10/2007, 23:58
Località: Napoli


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite