• Non ci sono risultati.

Matematica Discreta Lezione del giorno 10 dicembre 2010 Principio delle scelte multiple.

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Matematica Discreta Lezione del giorno 10 dicembre 2010 Principio delle scelte multiple."

Copied!
1
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 1 pagine )

Testo completo

(1)

Matematica Discreta

Lezione del giorno 10 dicembre 2010 Principio delle scelte multiple.

Supponiamo di volere contare il numero di elementi di un insieme finito A e di sapere che ogni elemento di A dipende dai valori di 2 variabili x,y, di modo che contare il numero di elementi di A equivalga a contare le possibili coppie di valori x,y.

Per contare le possibili coppie di valori x,y potremmo allora fissare in tutti i modi possibili un valore di x, e (per ogni valore fissato di x) calcolare il numero dei corrispondenti valori di y, e poi sommare i risultati ottenuti.

Esempio: supponiamo che A sia l’insieme dei numeri naturali di 2 cifre (decine e unità) con cifre scelte fra i valori 1,2,3,4, e tali che la cifra delle decine sia minore di quella delle unità. Per contare il numero di elementi di A, possiamo notare che ogni elemento di A dipende dai valori di 2 variabili: la cifra x delle decine e la cifra y delle unità.

Fissato il valore x=1 otteniamo in corrispondenza 3 valori di y (che sono y=2,3,4), analogamente fissato il valore x=2 otteniamo in corrispondenza 2 valori di y (che sono y=3,4), fissato il valore x=3 otteniamo in corrispondenza 1 valore di y (che è y=4), fissato il valore x=4 otteniamo in corrispondenza 0 valori di y. In totale il numero di coppie di valori x,y (e quindi il numero di elementi di A) è la somma 3+2+1+0=6.

Sempre nell’ambito del problema di contare il numero di elementi di un insieme finito A in cui ogni elemento dipende dai valori di 2 variabili x,y, facciamo un ulteriore ipotesi (che non è verificata nell’esempio precedente): supponiamo che il numero dei valori possibili della variabile x sia = h e che, fissato un valore della variabile x, il numero dei corrispondenti valori di y sia costantemente = k (indipendentemente dal valore fissato per x).

In tale caso il numero delle coppie di valori di x,y (e quindi il numero di elementi di A) si otterrà sommando k+k+….+k (con h addendi) quindi sarà uguale al prodotto kh (questo è il cosiddetto principio delle scelte multiple per 2 variabili).

Quindi il principio delle scelte multiple per 2 variabili ha il seguente enunciato:

se ogni elemento dell’insieme finito A dipende dal valore di 2 variabili x,y e se - il numero di valori possibili di x è = h

- fissato un valore di x, il numero di valori possibili di y è costantemente = k allora la cardinalità di A è il prodotto kh.

Esempio: supponiamo che A sia l’insieme dei numeri naturali di 2 cifre (in base 10) con cifre scelte fra i valori 1,2,3,4,5,6 e tali che la cifra delle decine sia diversa da quella delle unità. Come nell’esempio precedente, possiamo notare che ogni elemento dipende dai valori di 2 variabili: la cifra x delle decine e la cifra y delle unità.

La variabile x può assumere 6 valori distinti 1,2,3,4,5,6. Fissato un valore di x, il numero dei valori corrispondenti di y è costantemente uguale a 5 (sono tutti i valori 1,2,3,4,5,6 tranne quello scelto per x).

Siamo nelle ipotesi del principio delle scelte multiple e possiamo concludere che il numero di elementi di A è il prodotto 65=30

Con ragionamenti simili ai precedenti si ottiene il principio delle scelte multiple per più variabili:

supponiamo che ogni elemento dell’insieme finito A dipenda dai valori di n variabili x

1

,x

2

,….,x

n

;

supponiamo inoltre che:

(2)

- il numero di possibili valori di x

1

é = h

1

- fissato un valore di x

1

, il numero di valori possibili di x

2

è costantemente = h

2

- fissato un valore di x

1

e di x

2

, il numero di valori possibili di x

3

é costantemente = h

3

……etc

- fissato un valore per ognuna delle variabili x

1

,x

2

,…,x

n-1

, il numero dei valori possibili di x

n

é costantemente = h

n

allora il numero degli elementi di A è uguale al prodotto h

1

h

2

……h

n

. Vediamo alcune applicazioni del principio delle scelte multiple.

Numero delle funzioni fra insiemi finiti

Siano A,B due insiemi finiti rispettivamente con A=n, B=m, e contiamo il numero di tutte le possibili funzioni f: A  B.

Se {a

1

, a

2

, ….., a

n

} sono gli elementi di A, ognuna di tali funzioni dipende dalle n variabili seguenti:

x

1

=valore del corrispondente in B dell’elemento a

1

; x

2

=valore del corrispondente in B dell’elemento a

2

;

…..

x

n

=valore del corrispondente in B dell’elemento a

n

.

La variabile x

1

ha m valori possibili (gli m elementi di B); fissato un valore di x

1

, la variabile x

2

ha m valori possibili (di nuovo gli m elementi di B); fissato un valore di x

1

e un valore di x

2

, la variabile x

3

ha m valori possibili (di nuovo gli m elementi di B); etc ..…. ; infine fissato un valore di x

1

, uno di x

2

,…, uno di x

n-1

, la variabile x

n

ha m valori possibili (sempre gli m elementi di B). Per il principio delle scelte multiple, il numero delle possibili funzioni f: A  B è il prodotto mm…..m (con n fattori), quindi è la potenza m

n

.

La formula che dà il numero di tutte le funzioni f: A  B è allora B

A

.

Esempio: Se A={a,b}, B={1,2,3}, il numero delle possibili funzioni f: A  B è 3

2

=9, mentre il

numero delle possibili funzioni f: B  A è 2

3

=8 .

Riferimenti

Scarica adesso ( DOC - 1 pagine - 29.00 KB )

Documenti correlati

Matematica Discreta Lezione del giorno 2 novembre 2009 Principio delle scelte multiple.

Supponiamo di volere contare il numero di elementi di un insieme finito A e di sapere che ogni elemento di A dipende dai valori di 2 variabili x,y, di modo che contare il numero

Matematica Discreta Lezione del giorno 15 aprile 2010 Operazioni in un insieme.

Gli elementi x,y sono detti operandi (l’elemento x è il primo operando, l’elemento y è il secondo operando), mentre l’elemento f(x,y) è detto risultato dell’operazione

Matematica Discreta Lezione del giorno 19 aprile 2010 Elemento neutro.

1) Gli insiemi Z, Q, R (rispettivamente dei numeri interi relativi, dei numeri razionali relativi e dei numeri reali relativi) sono monoidi (commutativi) rispetto all’operazione

Matematica Discreta Lezione del giorno 28 aprile 2010

Con ragionamento analogo, se vi fossero invece per assurdo 2 elementi uguali nella stessa colonna, si otterrebbe una contraddizione (utilizzando stavolta la legge di cancellazione

Matematica Discreta Lezione del giorno 10 maggio 2010

[r]

Matematica Discreta Lezione del giorno 8 novembre 2010 Elementi di Logica Matematica Proposizioni e predicati.

Si definisce predicato logico (o brevemente predicato) una frase di senso compiuto che contiene delle variabili (spesso indicate con lettere come x,y,z….) e che diventa una

Matematica Discreta Lezione del giorno 10 novembre 2010 Operatori logici.

Spesso però i valori delle variabili che rendono vero P sono in numero infinito, e in tal caso non è possibile, come nell’esempio precedente, verificare singolarmente che ciascuno

Matematica Discreta Lezione del giorno 10 novembre 2010 Operatori logici.

[r]