La matematica del calcolatore

Insiemi

Definizioni e proprietà

Un insieme è un’entità formata da oggetti distinti, si indica un insieme con un nome e lo si individua tramite l’elenco degli oggetti che lo costituiscono: L = {0,1,2,3,4,5,6,7,8,9}. Due insiemi con gli stessi costituenti sono uguali: L_i = {0,1,2} = L_j = {1,2,0}, ciò significa che l’ordine dei costituenti l’insieme non ha alcuna importanza. Con il simbolo ε si indica l’appartenenza di un oggetto ad un insieme, ad esempio: 0 ε L_i.

Oltre alla esplicitazione diretta di un insieme mediante l’elenco dei suoi costituenti, un insieme J può essere definito da un insieme I esistente (o da più insiemi esistenti), come l’insieme formato dagli elementi di I che hanno una qualche proprietà [1] . Secondo questa definizione, ed utilizzando solo il concetto di appartenenza, si definiscono i seguenti insiemi derivati:

A 4 B = {x: x ε A o x ε B}

A 3 B = {x: x ε A e x ε B}

A - B  = {x: x ε A e x non ε B}

Essi sono detti rispettivamente unione, intersezione e sottrazione. I simboli 4 , 3,  - possono essere pensati come operatori fra insiemi.

Se vale A 4 B = A allora si dice che B è incluso in A, e lo si indica con B ` A.

Se  A e B non hanno elementi comuni, l’insieme A 3 B non contiene elementi è quindi un insieme vuoto e lo si indica con Ø. L’insieme vuoto può anche essere definito come  Ø =  {x: x non ε A}.

Un sottoinsieme I di un insieme J è l’insieme definito come:

I = {x: x ε J o x = {Ø}}

I al più coincide con J o è l’insieme vuoto; l’insieme vuoto è quindi sottoinsieme di qualsiasi insieme. Il numero di elementi di un insieme è detto dimensione dell’insieme.

Dalla definizione di insieme, segue anche che insiemi aventi un ugual numero di elementi sono di fatto indistinguibili; fra tutti gli insiemi riveste una particolare importanza l’insieme avente due elementi (indicato con I₂) in quanto è connesso con il concetto di relazione fra gli elementi di un insieme.

L’insieme di tutti i sottoinsiemi di un insieme è detto insieme delle parti. Se I ha n elementi, l’insieme delle parti di I ha 2ⁿ elementi.

Se la dimensione dell’insieme I è di ordine infinito contabile, cioè ogni suo elemento può essere messo in corrispondenza biunivoca (1 ad 1) con i numeri naturali N, il suo insieme delle parti ha una dimensione che non è contabile:

Si supponga che 2^N l’insieme delle parti dei numeri naturali, abbia dimensione infinita contabile, allora è possibile enumerare tutti i sottoinsiemi numerici:

2^N = {S₀, S₁,…}

Si consideri ora un insieme formato da numeri che non appartengono al sottoinsieme S_n. Tale sottoinsieme appartiene ovviamente all’insieme delle parti 2^N, ed avrà un suo indice, supponiamo k.

Se k ε S_k non può far parte di S_k per definizione.

Se k non ε S_k per definizione deve appartenere a S_k.

In entrambi i casi si ha contraddizione, dunque l’insieme 2^N non è contabile. ■

Relazioni

Intuitivamente una relazione R fra elementi (p,q,…) di un insieme è una proprietà che questi elementi hanno, ed è legata all’affermazione “è vero che p,q,… soddisfano la relazione R”. Per rendere più formale tale definizione: due o più elementi ordinati di un insieme A sono in relazione R fra di loro se essi sono associabili all’elemento V dell’insieme I₂ ={V,F}. Ề necessario che gli elementi siano ordinati, perché anche se ci sono relazioni, ad esempio la relazione di uguaglianza in cui l’ordine non ha importanza, in altre l’ordine è essenziale, ad esempio, nell’insieme dei numeri interi positivi la relazione minore di è una relazione fra coppie di elementi ordinati, infatti R(7,11) è associato a V, ma non lo è R(11,7). Le relazioni sono possibili anche fra elementi di insiemi diversi, ad esempio la relazione Città – Nazione.

Funzioni

Una funzione f associa uno o più elementi ordinati di un insieme [2] , detto dominio della funzione, ad un elemento di un altro insieme, eventualmente coincidente con il dominio della funzione stessa, ciò si indica con f: N^k → N.

Ad esempio:

        i)      y = add(x₁,x₂)     somma di due numeri appartenenti all’insieme dei numeri interi positivi

       ii)      y = mod(a,b)      il resto della divisione fra a e b

     iii)      y = if(a,b,c)         se a = 0 allora y = b, altrimenti y = c.

     iv)      y = f_göd (n₁,n₂,…n_k) = 2ⁿ¹·3ⁿ²·… ·p_k^nk  dove p_k è il k-esimo numero primo, la funzione genera i cosiddetti numeri di gödel [3] , ad esempio f_göd (3,7) = 2³·3⁷ = 17496. La funzione codifica k numeri (una k-upla), in uno solo.

Molte funzioni con due argomenti hanno tradizionalmente una notazione infissa [4] , ad esempio i) si scrive y = x₁+x₂. E’ un retaggio storico, ma ha perlomeno un vantaggio pratico nel calcolo manuale, ad esempio si consideri la proprietà distributiva del prodotto rispetto alla somma espressa con le due notazioni:

a·(b + c) = a·b + a·c

·(a,+(b,c)) = +(·(a,b),·(a,c))

Un altro modo di scrivere formule deriva dalla osservazione che una espressione si può scrivere senza parentesi, in quanto queste sono ridondanti. In alcune calcolatrici scientifiche si immettono le espressioni in una forma che è detta RPN (Reverse Polish Notation ). In RPN gli operandi precedono il loro operatore e il calcolo è effettuato senza la necessità di memorizzare risultati intermedi, ad esempio l'espressione ((8 + 6)(7 - 5)) / (9 - 7), diventa:

8 6+7 5-·9,7-/ 

14 7 5-·9 7-/

14 2·9,7-/

28 9 7-/

28 2/

14

Il calcolo procede da sinistra a destra, applicando l'operatore ai valori alla sua sinistra e sostituendo operatore e valori con il risultato.

Funzioni ricorsive

Una funzione è ricorsiva se fra gli elementi del dominio compare  la funzione stessa. Lo schema delle funzioni ricorsive (uno fra i possibili), è analogo a quello della funzione if:

F_ric(n) = if(a,b, f(F_ric(n-1)))

Dove b è il valore assunto dalla funzione quando a vale 0, f è una funzione opportuna; ad esempio:

Fatt(n) = if(n,1,n·Fatt(n-1))     funzione fattoriale

Add(n,m) = if(n,m,1+Add(n-1,m))

Mult(n,m) = if(n,0,m+Mult(n-1,m))

Exp(n,m) = if(m,1,n*Exp(n,m-1))   calcola n^m

.