Matematica Discreta
Lezione del giorno 15 aprile 2010 Operazioni in un insieme.
In aritmetica é ben noto il concetto di “operazione” fra numeri: un esempio sono le operazioni di somma e prodotto fra numeri naturali.
Ma cos’è formalmente un’operazione ?
Se esaminiamo la somma fra numeri naturali, essa non è altro che una regola che associa ad ogni coppia (x,y) di numeri naturali (detti “addendi”) un unico numero naturale x+y (detto “somma”).
Nel linguaggio insiemistico dunque la somma fra numeri naturali è una funzione f. NxNN.
Da queste osservazioni si perviene facilmente alla seguente definizione più generale:
Un’operazione definita nell’insieme (non vuoto) A è una funzione f : AxA → A
(dove AxA = {(x,y) / x,yA } è il prodotto cartesiano contenente le coppie ordinate di elementi di A) che associa ad ogni coppia ordinata (x,y) di elementi di A uno e un solo elemento f(x,y)A.
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 sugli operandi x,y.
Useremo spesso il simbolo xy per indicare il risultato f(x,y) dell’operazione sugli operandi x,y.
Esempio.
Nell’insieme N dei numeri naturali sono esempi di operazioni quelle definite ponendo:
xy = x+y (somma) xy = x∙y (prodotto)
xy = xy (elevamento a potenza)
Poiché un’operazione non è altro che una funzione, un’operazione in un insieme A può essere definita:
- in modo implicito: dati 2 operandi variabili x,y in A si definisce un’operazione ponendo xy = ………
dove dopo il segno di eguaglianza vi è una “formula” nelle variabili x, y che permette di calcolare il risultato, dati gli operandi x,y.
Gli esempi precedenti di operazioni di somma, prodotto, elevamento a potenza in N sono definiti in modo implicito. Ovviamente nello stesso insieme N potremmo definire in modo implicito altre operazioni, ovviamente meno “utili” di quelle precedenti (che sono legate al procedimento di
“contare”).
Per esempio potremmo definire in modo implicito un’operazione in N ponendo:
xy = x + y + xy
Se volessimo allora calcolare in particolare in questa operazione il risultato 32 dovremmo calcolare:
32 = 3 + 2 + 32 = 11
- in modo esplicito (tale modalità è praticabile solo nel caso in cui l’insieme A sia finito): per ognuna delle possibili coppie di operandi x,y in A si indica esplicitamente il risultato xy (che deve essere un unico elemento di A).
Per esempio nell’insieme A = {a, b, c} delle prime 3 lettere dell’alfabeto, possiamo definire un’operazione indicando, per ognuna delle 9 coppie possibili di operandi in A, il risultato nel modo seguente:
aa=b, bb=b, cc=a, ab=c, ba=a, ac=b, ca=c, bc=a, cb=a
Si può rendere la definizione esplicita di una operazione (definita in un insieme finito A di cardinalità n) utilizzando una tavola operazionale: è una matrice quadrata di n2 caselle disposte in n righe e n colonne, in cui si fanno corrispondere alle righe e alle colonne ordinatamente gli elementi di A (in un ordine prefissato), e inserendo in ogni casella il risultato xy, dove x è l’operando corrispondente alla riga della casella, y è l’operando corrispondente alla colonna della casella.
Nell’ esempio precedente, l’operazione definita nell’insieme A = {a, b, c} di cardinalità 3 avrebbe la seguente tavola operazionale 3x3 (rispetto all’ordine prefissato a,b,c):
a b c a
b c
Proprietà commutativa.
Un’operazione definita nell’insieme A è detta commutativa, se, comunque dati gli operandi x,y, si ha xy= yx (ossia se il risultato non cambia quando si cambia l’ordine degli operandi).
Esempio.
Nell’insieme N dei numeri naturali le operazioni di somma e prodotto sono commutative (perché è ben noto che, comunque dati i numeri naturali x,y si ha x+y=x+y , x∙y=y∙x).
Invece l’operazione di elevamento a potenza non è commutativa, perché per esempio:
23=2332=32 .
Nell’insieme A = {a, b, c} l’operazione definita in precedenza non è commutativa perché per esempio: ab=cba=a .
Nel caso di un insieme finito, la proprietà commutativa si riflette in proprietà della tavola operazionale: la proprietà commutativa equivale alla proprietà che la tavola operazionale sia simmetrica rispetto alla diagonale principale \ (sinistra alto – destra basso), nel senso che caselle simmetriche rispetto a tale diagonale hanno eguale contenuto.
Proprietà associativa.
Un’operazione definita nell’insieme A è associativa se, comunque presi gli elementi x,y,zA, si ha:
(xy)z = x(yz) Esempio.
E’ ben noto che le operazioni di somma e prodotto nell’insieme dei numeri naturali sono associative, in quanto (x+y)+z=x+(y+z), (xy)z=x(yz), comunque dati i numeri naturali x,y,z.
Invece l’operazione di elevamento a potenza xy=xy non è associativa perché, dati i numeri naturali x,y,z, non è sempre vero che i seguenti risultati sono uguali:
(xy)z= (xy)z=(xy)z=xyz x(yz)= x(yz) =x(yz)
L’operazione (esaminata come esempio in precedenza) definita in modo implicito nell’insieme dei numeri naturali da:
xy = x+y+xy
è associativa, perché i seguenti 2 risultati:
b c b
a b a
c a a
(xy)z= (x+y+xy)z=(x+y+xy)+z+(x+y+xy)z=x+y+xy+z+xz+yz+xyz x(yz)= x(y+z+yz)= x+(y+z+yz)+x(y+z+yz)= x+y+z+yz+xy+xz+xyz
sono uguali (notare che in tale ragionamento si sono utilizzate proprietà della somma e del prodotto di numeri naturali, come la proprietà distributiva).
L’operazione definita in precedenza in modo esplicito nell’insieme A={a,b,c} non è associativa perché per esempio (ab)c=cc=a è diverso da a(bc)=aa=b.
