YX denota l’insieme delle funzioni da X in Y

Antonino Salibra

Universit`a Ca’Foscari Venezia

Queste dispense non sono sufficienti per la preparazione dell’esame di Matematica Disc- reta.

NOTAZIONI:

1. N = {0, 1, 2, 3 . . . } `e l’insieme dei numeri naturali.

2. Z = {. . . , −3, −2, −1, 0, +1, +2, +3 . . . } `e l’insieme dei numeri interi.

3. Q = {n/m : n, m ∈ Z, m 6= 0} `e l’insieme dei numeri razionali.

4. R `e l’insieme dei numeri reali.

5. Se n `e un numero naturale, allora ˆn = {1, 2, . . . , n}.

6. Se X `e un insieme, allora P(X) `e l’insieme delle parti di X ovvero l’insieme dei suoi sottoinsiemi.

7. Y^X denota l’insieme delle funzioni da X in Y .

8. Se X `e un insieme, allora |X| denota la sua cardinalit`a.

9. Se A `e un alfabeto finito, A^∗ denota l’insieme delle stringhe o parole su A.

10. Se A `e un alfabeto finito, A^∗_n denota l’insieme delle stringhe su A di lunghezza n.

11. Se a `e un carattere, aⁿ denota la stringa aa · · · a (n volte).

12. Se R `e una relazione di equivalenza su X e a ∈ X, allora [a]_R (oppure a/R) denota la classe di equivalenza di a.

13. ⁿk
denota il coefficiente binomiale n su k.

1. Perch´e la matematica `e importante?

1.1. Dati semplici

Un tipo di dato `e un insieme di elementi o dati con delle operazioni elementari su di essi. Nel seguito distinguiamo tra dati semplici e composti (o strutturati).

1

• Il tipo di dato Nat dei numeri naturali `e costituito dall’insieme N dei naturali e le operazioni usuali di somma e prodotto. La sottrazione x − y `e definita se x ≥ y.

Esempi di problemi: Determinare se il numero naturale x `e primo. Scomporre x in fattori primi.

I numeri naturali si rappresentano come opportune stringhe sull’alfabeto delle cifre.

• Il tipo di dato Int dei numeri interi `e costituito dall’insieme Z degli interi e le operazioni usuali di somma, prodotto e sottrazione. La divisione x/y `e definita solo se x `e multiplo di y. I numeri interi si rappresentano in modulo e segno oppure in complemento a due.

• Il tipo di dato delle stringhe (o parole) su un alfabeto A `e costituito dall’insieme A<sup>∗</sup> delle stringhe su A e le operazioni di concatenazione di stringhe (per esempio, cane + stro =canestro), lunghezza di una stringa (per esempio, lunghezza di “cane” = 4), creazione di sottostringhe (per esempio, la sottostringa di “canestro” di lunghezza 4 a partire dal terzo carattere `e uguale a “nest”), etc. Esempio di algoritmo su stringhe: Determinare se una stringa `e palindroma, etc.

1.2. Dati composti

• Sequenze di dati semplici (per esempio, sequenze di stringhe o numeri) si rapp- resentano di solito con i vettori (se le sequenze hanno una lunghezza massima).

Operazione tipica su una sequenza A di lunghezza minore o uguale ad n, `e il re- cupero del valore A[i] che si trova nella posizione i ≤ n della sequenza. Algoritmi tipici sulle sequenze sono quelli di ordinamento e di ricerca.

Sequenze di dati semplici di lunghezza arbitraria possono essere rappresentate come liste. Per accedere ad un elemento in una lista bisogna scorrere la lista dall’inizio.

• Un grafo (come tipo di dati) `e costituito da un insieme finito di nodi (o vertici) ed un insieme finito di archi (orientati o meno). Un arco orientato connette un nodo sorgente x ad un nodo target y e si disegna di solito con una freccia orientata da x verso y:

x ^//y

Un arco non orientato connette due nodi x, y e si disegna con un segmento che unisce x e y. In questo caso non vi `e una direzione privilegiata:

x —— y

I nodi di un grafo sono in genere etichettati da dati semplici, numeri o stringhe.

Nodi differenti possono avere la stessa etichetta.

Un cammino in un grafo `e una sequenza x₁, x₂, . . . , x_n di nodi tale che, per ogni 1 ≤ i ≤ n − 1, esiste un arco che connette il nodo xi al nodo xi+1.

Il seguente `e un esempio di grafo orientato:

5

8 9 ^//7

5 ^//

^^ OO

10 5

__oo

Si noti che tre nodi distinti hanno la stessa etichetta.

1. L’orario degli esami [4, pagina 230]. Consideriamo un corso di laurea con n studenti e r corsi. Immaginiamo che gli esami siano scritti e che tutti gli studenti di un corso facciamo gli esami contemporaneamente. Due esami si possono svolgere lo stesso giorno se non hanno studenti in comune. Qual’`e il numero minimo di giorni per svolgere tutti gli esami? Si costruisce un grafo i cui nodi sono etichettati dai nomi dei corsi; un arco connette il corso x al corso y se i due corsi hanno alcuni studenti in comune (e quindi gli esami non possono svolgersi lo stesso giorno). Il numero cromatico del grafo risultante corrisponde al numero minimo di giorni per svolgere gli esami. (Spiegazione del numero cromatico: coloriamo i nodi del grafo in maniera tale che due nodi adiacenti, cio`e connessi da un arco, devono avere colori diversi. Il numero cromatico `e il numero minimo di colori necessari).

2. Problema matematico: `e possibile colorare una carta geografica planare con 4 colori in maniera tale che stati confinanti hanno colori diversi? Problema informatico: Scrivere un programma che prende in input una carta geografica e restituisce la carta colorata con quattro colori [4, pagina 230-1]. La carta geografica si rappresenta con un grafo i cui nodi rappresentano gli stati ed un arco non orientato connette il nodo (stato) x con il nodo (stato) y se esiste una linea di confine tra lo stato x e lo stato y. Per esempio:

Italia —— Francia

Se consideriamo la carta geografica politica della terra come grafo, esiste un cammino che collega l’Italia all’Olanda:

Italia —— Svizzera —— Germania —— Olanda

ma non esiste un cammino che collega l’Italia al Canada perch´e i due paesi si trovano in continenti diversi non collegati da lembi di terra.

• Un albero (come tipo di dati) `e un grafo finito in cui esiste un nodo, detto radice dell’albero, che verifica la seguente propriet`a: per ogni altro nodo x nell’albero esiste uno ed un solo cammino che collega il nodo dato x alla radice dell’albero. Il seguente

`e l’albero genealogico del vostro professore a partire dal nodo radice, il mio bisnonno

Luigi:

Luigi

vv ((

Vincenzo

xx  ((

Nin`ı

Maria

vv ||  &&

Antonino Luigi Junior

 ((

F E C S Antonino Junior Elena

Dato un albero, il nodo x `e figlio del nodo y se l’unico cammino che collega x alla radice r dell’albero ha la forma seguente x, y, . . . , r. I figli di un nodo possono essere ordinati. Per esempio, se ordiniamo fratelli e sorelle in ordine crescente di et`a otteniamo il seguente albero:

Luigi

ww %%

Vincenzo

tt  ''

Nin`ı

Luigi Junior

uu 

Maria

zz  '' ++

Antonino

Antonino Junior Elena E C S F

1. Ordinamento di sequenze di naturali: leggendo la sequenza da sinistra a destra pongo gli elementi su un albero binario ordinato. Esempio: data la sequenza 6, 4, 8, 1, 5, 86, 7, 2, mi costruisco un albero binario ordinato (ogni nodo ha un figlio sinistro e/o un figlio destro), che ha il primo numero 6 come radice. Gli altri numeri vengono inseriti scendendo nell’albero a destra (a sinistra) se il nu- mero `e pi`u piccolo (grande) del numero che etichetta il nodo in considerazione.

6

ww ''

8

 

4

86 7 5 1

2

La sequenza ordinata in ordine crescente (decrescente) si recupera visitando i nodi dell’albero X da destra verso sinistra (da sinistra verso destra) secondo il seguente algoritmo ricorsivo.

Stampa-etichette(X);

begin

If X 6= albero-vuoto then begin

Stampa-etichette(sottoalbero-destro(X));

Stampa-etichetta-radice(X);

Stampa-etichette(sottoalbero-sinistro(X));

end;

end

In conclusione, i dati semplici o composti di un programma sono sempre strutture finite. La matematica discreta studia le propriet`a matematiche di queste strutture finite che molto spesso sono essenziali alla comprensione del problema informatico. Si cerca di rispondere alla domanda: `E vero che i grafi verificano la seguente propriet`a? Per esempio,

`

e vero che possiamo colorare un grafo planare con 4 colori?

2. Insiemi

Un insieme `e una collezione non ordinata di elementi distinti. Gli insiemi si rappresen- tano con parentesi graffe. Per esempio,

{0, 1, 2, 3}; {abcm, ddef, casa, casato, theta}

sono due esempi di insiemi con un numero finito di elementi. Il primo insieme ha come elementi i primi quattro numeri naturali 0, 1, 2, 3. Il secondo insieme ha come elementi cinque stringhe di caratteri “abcm”, “ddef”, “casa”, “casato”, “theta”. L’ordine con cui scriviamo gli elementi di un insieme non `e importante. Due insiemi sono uguali se e solo se (sse, per brevit`a) hanno gli stessi elementi. Per esempio,

{0, 1, 2, 3} = {2, 1, 0, 3}.

L’appartenenza di un elemento ad un insieme si scrive utilizzando il simbolo ∈. Per esem- pio, 3 ∈ {0, 1, 2, 3} e casato ∈ {abcm, ddef, casa, casato, theta}. La non appartenenza di un elemento ad un insieme si scrive utilizzando il simbolo /∈. Per esempio, 5 /∈ {0, 1, 2, 3}

e aa /∈ {abcm, ddef, casa, casato, theta}. Quindi l’appartenenza `e una relazione tra ele- menti ed insiemi.

Esistono insiemi con un numero infinito di elementi. Per esempio, l’insieme dei numeri naturali, l’insieme dei numeri interi, etc. L’insieme dei dati in input di un algoritmo `e un insieme che in generale `e infinito. L’insieme dei programmi sintatticamente corretti in un linguaggio di programmazione `e un altro esempio di insieme infinito.

Abbiamo visto che `e possibile definire un insieme per enumerazione dei suoi elementi nel caso in cui il numero di elementi `e finito. Come possiamo definire un insieme con un numero infinito di elementi? Tramite una propriet`a. Nel seguito delineiamo come.

• Definizione di un insieme tramite una propriet`a [2, Cap.2]. Esempi di propriet`a:

essere alto, essere un numero naturale, essere residente a Iesolo, essere multiplo di 11, etc. Una propriet`a ha senso o assume significato rispetto ad un opportuno insieme di riferimento. Per esempio, non ha senso dire che 5 `e alto oppure che Giovanni

`e un numero naturale; ma ha senso dire che il mio amico Giovanni non `e alto (e quindi non verifica la propriet`a “essere alto”), e che 5 `e un numero naturale (ossia 5 verifica la propriet`a “essere un numero naturale”).

Si consideri una propriet`a P e un insieme A rispetto al quale la propriet`a P ha senso.

L’insieme A si chiama universo del discorso. Se x ∈ A, si hanno esattamente due possibilit`a: x verifica la propriet`a P oppure x non verifica la propriet`a P . Nel primo caso si scrive P (x) `e vero, mentre nel secondo caso P (x) `e falso. In matematica non esistono altre possibilit`a (non in generale nella vita reale). Possiamo allora definire l’insieme degli elementi di A che verificano P . In notazione matematica:

{x ∈ A | P (x) `e vero}.

In notazione pi`u compatta si sottintende “`e vero”:

{x ∈ A | P (x)}

e a volte, se l’universo del discorso A `e evidente dal contesto, si sottintende l’appartenenza ad A:

{x | P (x)}.

Al posto del simbolo “|” che significa “tali che” si pu`o usare in modo equivalente il simbolo “:”

{x : P (x)}.

Example 2.1. Alcuni insiemi definiti da propriet`a:

- {n : n `e un multiplo di 11}. Qui l’insieme dei numeri naturali `e l’universo del discorso sottinteso.

Per risparmiare spazio e tempo, `e preferibile dare nomi brevi agli insiemi:

- X₁ = {n | n `e un multiplo di 11}.

- X₂ = {n | n `e un essere umano alto}. Qui l’universo del discorso `e l’insieme degli esseri umani.

- X₃ = {n | n `e dispari}.

Abbiamo gi`a detto che una propriet`a si riferisce sempre ad una prefissato universo del discorso. Per esempio, nella definizione dell’insieme precedente la propriet`a

“essere dispari” divide l’insieme dei numeri naturali in due parti: i numeri naturali che verificano la propriet`a: 1, 3, 5, . . . , e quelli che non la verificano: 2, 4, 6, . . . .

• A volte si utilizzano propriet`a che determinano coppie di elementi (oppure triple, etc). Una coppia si scrive racchiudendo i due elementi tra parentesi tonde: (1, 2)

costituisce la coppia il cui primo elemento `e 1 ed il secondo elemento `e 2. In una coppia l’ordine degli elementi `e importante. Le due coppie (1, 2) e (2, 1) sono diverse:

(1, 2) 6= (2, 1). Supponendo che l’universo del discorso sia l’insieme dei numeri naturali, definiamo alcuni insiemi di coppie ed insiemi di triple:

- X₄ = {(x, y) : x < y}.

- X₅ = {(x, y, z) : x + y = z}. Se l’universo del discorso `e l’insieme degli esseri umani, abbiamo per esempio:

- X₆ = {(x, y) : x `e padre di y}.

- X₇ = {(x, y) : x `e antenato di y}.

• Prodotto Cartesiano. Se X ed Y sono insiemi, l’insieme delle coppie con primo elemento in X e secondo elemento in Y si indica con X × Y . L’insieme X × Y `e detto prodotto Cartesiano di X e Y :

X × Y = {(x, y) : x ∈ X e y ∈ Y }.

Example 2.2.

- 3 ∈ {0, 1, 2, 3, 4} mentre 5 /∈ {0, 1, 2, 3, 4}.

Si considerino gli insiemi X1, X2, . . . , X6 definiti precedentemente. Allora si ha:

- 121 ∈ X₁ mentre 5 /∈ X₁. - Antonino Salibra /∈ X₂. - 1 ∈ X₃, ma 2 /∈ X₃.

- (2, 5) ∈ X₄, ma (5, 2) /∈ X₄.

- (Luigi Salibra, Antonino Salibra) ∈ X₅. - (2, 3, 5) ∈ X₆, ma (2, 3, 6) /∈ X₆.

- X₁×N = {(x, y) : x `e un multiplo di 11 e y `e un numero naturale}. Allora (22, 5) ∈ X1 × N mentre (21, 5) /∈ X1× N.

• L’insieme vuoto. L’insieme che non ha elementi si indica con il simbolo ∅ ed `e detto insieme vuoto. L’insieme vuoto pu`o essere definito dalla propriet`a “essere diverso da se stesso”:

∅ = {x : x 6= x}.

• Singletons. Un insieme `e un singleton se ha esattamente un elemento. Per esempio, gli insiemi {1} e {a} sono singletons.

• La relazione di uguaglianza. Due insiemi sono uguali se hanno gli stessi elementi.

Nota che l’ordine degli elementi in un insieme non `e importante. Per esempio, {0, 1, 2, 3, 4} = {3, 1, 4, 2, 0}.

• La relazione di contenuto o uguale. Per esprimere che gli elementi di un insieme sono anche elementi di un altro insieme si utilizza il simbolo ⊆. Si scrive A ⊆ B, e si dice che l’insieme A `e contenuto o uguale all’insieme B, se x ∈ A implica che x ∈ B. Si scrive A 6⊆ B se A non `e contenuto in B. Se A ⊆ B, si dice che A `e un sottoinsieme di B. La relazione di contenuto o uguale `e una relazione tra insiemi.

Esempio: {2, 4} ⊆ {0, 1, 2, 3, 4} mentre {2, 7} 6⊆ {0, 1, 2, 3, 4}.

• La relazione di contenuto o uguale `e una relazione d’ordine parziale. Dato un insieme X, indichiamo con P(X) l’insieme di tutti i sottoinsiemi di X. L’insieme P(X)

`e detto insieme delle parti di X. Per esempio, se X = {0, 1}, allora P(X) = {∅, {0}, {1}, {0, 1}} `e un insieme di 4 elementi. Se X = {a, b, c}, allora P(X) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} `e un insieme di 8 elementi.

L’insieme P(X) delle parti di X `e parzialmente ordinato dalla relazione di contenuto o uguale (si veda Sezione 3.2). Per esempio, la relazione di ⊆ sulla’insieme P({0, 1}) pu`o essere rappresentata come un grafo orientato i cui nodi sono i sottoinsiemi di {0, 1} ed un arco orientato connette il nodo A al nodo B se B \ A `e un singleton.

Quindi, per esempio, abbiamo

{1} −→ {0, 1}

perch´e {0, 1} \ {1} = {0} `e un singleton.

{0, 1}

{0}

⊆ <<

{1}

bb ⊆

∅

⊆

cc

⊆

;;

Se X = {0, 1, 2} allora l’insieme P(X) delle parti `e parzialmente ordinato come segue:

{0, 1, 2}

{0, 1}

99

{0, 2}

OO

{1, 2}

ee

{0}

OO 99

{1}

ee 99

{2}

ee OO

∅

ee OO 99

Dal diagramma capiamo che, per esempio, {1} ⊆ {0, 1, 2} perch`e c’`e un cammino {1} −→ {1, 2} −→ {0, 1, 2}

che parte da {1} ed arriva a {0, 1, 2}. Il cammino non `e unico:

{1} −→ {0, 1} −→ {0, 1, 2}

Osserviamo che l’insieme delle parti di un insieme di 2 elementi ha 4 elementi, e che l’insieme delle parti di un insieme di 3 elementi ha 8 elementi. Dimostreremo in seguito che l’insieme delle parti di un insieme di n elementi ha 2ⁿ elementi.

• L’algebra Booleana dei sottoinsiemi di un insieme X. Se A, B sono sottoinsiemi di X, definiamo la loro unione A ∪ B come segue:

A ∪ B = {x : x ∈ A oppure x ∈ B}.

Allora abbiamo che A ⊆ A ∪ B e B ⊆ A ∪ B. Viceversa, se x ∈ A ∪ B allora x ∈ A oppure x ∈ B. Per esempio, {0, 1} ∪ {1, 3, 4} = {0, 1, 3, 4}.

L’intersezione A ∩ B di A e B `e definita come segue:

A ∩ B = {x : x ∈ A e x ∈ B}

Allora abbiamo A ∩ B ⊆ A e A ∩ B ⊆ B. Viceversa, se x ∈ A e x ∈ B allora x ∈ A ∩ B. Per esempio, {0, 1} ∩ {1, 3, 4} = {1}.

La complementazione X \ A di un sottoinsieme A di X `e definita come segue:

X \ A = {x : x ∈ X e x /∈ A}

Allora abbiamo (X \A)∩A = ∅ e A∪(X \A) = X. Per esempio, {0, 1, 3, 4}\{3, 4} = {0, 1}.

Le precedenti operazioni sono chiamate operazioni Booleane [2, Cap.2] e verificano le seguenti identit`a per ogni sottoinsieme A, B e C di X:

– Idempotenza: A ∩ A = A; A ∪ A = A

– Propriet`a associativa: (A ∩ B) ∩ C = A ∩ (B ∩ C); (A ∪ B) ∪ C = A ∪ (B ∪ C) – Propriet`a commutativa: A ∩ B = B ∩ A; A ∪ B = B ∪ A

– Assorbimento: A ∪ (A ∩ B) = A; A ∩ (A ∪ B) = A

– Distributivit`a: A∩(B ∪C) = (A∩B)∪(A∩C); A∪(B ∩C) = (A∪B)∩(A∪C) – Complementazione: A ∪ (X \ A) = X; A ∩ (X \ A) = ∅

Nei seguenti due esempi mostriamo come `e possibile dimostrare enunciati del tipo “Per tutti i sottoinsiemi A, B, C di X, A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)”.

Example 2.3. ( Prima dimostrazione di uguaglianza di due espressioni insiemistiche) Sia X un insieme. Dimostrare che, per tutti i sottoinsiemi A, B di X, vale la seguente propriet`a: A ∪ (A ∩ B) = A.

Soluzione: L’uguaglianza A ∪ (A ∩ B) = A `e vera se sono vere le seguenti due disug- uaglianze: A ∪ (A ∩ B) ⊆ A e A ⊆ A ∪ (A ∩ B). Cominciamo con la dimostrazione della prima disuguaglianza:

Se x ∈ A ∪ (A ∩ B) allora x ∈ A oppure x ∈ A ∩ B, per definizione dell’operatore insiemistico di unione. Nel primo caso abbiamo finito perch´e x ∈ A. Nel secondo caso da x ∈ A ∩ B deriviamo x ∈ A e x ∈ B. Quindi in entrambi i casi deriviamo x ∈ A.

A ⊆ A∪(A∩B): Se x ∈ A allora x appartiene ad ogni sovrainsieme di A, in particolare all’insieme A ∪ (A ∩ B).

Example 2.4. ( Seconda dimostrazione di uguaglianza di due espressioni insiemistiche) Sia X un insieme. Dimostrare che, per tutti i sottoinsiemi A, B, C di X, vale la propriet`a distributiva: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

Soluzione: Proviamo prima che A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C). Sia x ∈ A ∪ (B ∩ C).

Allora abbiamo due casi esaustivi: x ∈ A oppure x ∈ B ∩ C.

• Se x ∈ A allora x appartiene ad ogni sovrainsieme di A, in particolare x ∈ A ∪ B e x ∈ A ∪ C, da cui x ∈ (A ∪ B) ∩ (A ∪ C).

• Se x /∈ A allora x ∈ B ∩ C (stante l’ipotesi x ∈ A ∪ (B ∩ C)), che implica x ∈ B e x ∈ C. Da x ∈ B segue che x ∈ A ∪ B, mentre da x ∈ C segue che x ∈ A ∪ C. In conclusione, x ∈ (A ∪ B) ∩ (A ∪ C).

Proviamo ora il viceversa: (A ∪ B) ∩ (A ∪ C) ⊆ A ∪ (B ∩ C). Sia x ∈ (A ∪ B) ∩ (A ∪ C).

Allora abbiamo x ∈ A ∪ B e x ∈ A ∪ C. Analizziamo due casi.

• Se x ∈ A allora x ∈ A ∪ (B ∩ C) che `e un sovrainsieme di A.

• Se x /∈ A allora da x ∈ A ∪ B segue x ∈ B, mentre da x ∈ A ∪ C segue x ∈ C. In conclusione, x ∈ B ∩ C, e quindi x ∈ A ∪ (B ∩ C).

3. Relazioni

Definition 3.1. [2, Sezione 10.1] Siano A e B insiemi.

1. Una relazione binaria R tra A e B `e un sottoinsieme del prodotto Cartesiano A × B (in simboli, R ⊆ A × B). L’insieme A `e il dominio della relazione, mentre l’insieme B `e il suo codominio.

2. Una relazione n-aria R su A `e un sottoinsieme di Aⁿ(cio´e, A × A × · · · × A n volte).

Se R ⊆ A × B `e una relazione binaria, scriveremo spesso aRb al posto di (a, b) ∈ R.

Example 3.1. Sia E l’insieme degli esseri umani e N l’insieme dei numeri naturali.

Allora, il sottoinsieme R ⊆ E × N, definito dall’insieme delle coppie (x, y) tali che x ∈ E, y ∈ N e x ha et`a y, `e una relazione binaria tra E e N.

3.1. Stringhe (o parole) e sequenze finite

1. Abbiamo gi`a definito il prodotto Cartesiano X × Y di due insiemi X e Y come l’insieme delle coppie (a, b) con a ∈ X e b ∈ Y . X × Y × Z `e l’insieme delle triple (a, b, c) con a ∈ X, b ∈ Y e c ∈ Z, etc. Notazione X × X × · · · × X n-volte si abbrevia Xⁿ (vedi l’inizio di [2, Sezione 10.2]).

2. Sequenze finite su X =S

n∈NXⁿ. L’insieme X⁰ha come unico elemento la sequenza vuota λ.

3. Stringhe o parole su un alfabeto A sono sequenze finite di caratteri. In questo caso (a, b, a, b) si scrive in maniera pi`u compatta come abab. Le stringhe vengono di solito indicate con le lettere greche α, β, γ. La stringa vuota `e denotata con λ. La giustapposizione o concatenazione di due stringhe α e β viene indicata con αβ. Per esempio, la giustapposizione di “casa” e “matta” `e la stringa “casamatta”.

3.2. Ordini parziali

Nel seguito scriviamo talvolta ∀x al posto di “Per ogni x”. Inoltre ∀xy significa “Per ogni x e per ogni y”.

Definition 3.2. Sia A un insieme. Una relazione binaria R su A `e un ordinamento parziale se verifica le seguenti propriet`a:

1. Propriet`a riflessiva: ∀x(xRx)

Significato: Per ogni x ∈ A, si ha (x, x) ∈ R.

2. Propriet`a transitiva: ∀xyz(xRy e yRz → xRz)

Significato: Per ogni x, y, z ∈ A, se (x, y) ∈ R e (y, z) ∈ R, allora (x, z) ∈ R.

3. Propriet`a antisimmetrica: ∀xy(xRy e yRx → x = y)

Significato: Per ogni x, y ∈ A, se (x, y) ∈ R e (y, x) ∈ R, allora x = y.

Un ordine parziale R `e totale se `e verificata la seguente ulteriore propriet`a:

4. ∀xy(xRy oppure yRx)

Significato: Per ogni x, y ∈ A si ha uno dei seguenti due casi: (x, y) ∈ R oppure (y, x) ∈ R.

Gli ordini parziali verranno indicati in genere con il simbolo ≤.

Definition 3.3. Un ordinamento parziale stretto < sugli elementi di un insieme A `e definito dalle propriet`a transitiva e antisimmetrica e dalla seguente propriet`a:

• Propriet`a irriflessiva: ∀x(x 6< x).

Possiamo sempre definire un ordinamento parziale stretto a partire da un ordinamento parziale ≤:

x < y sse x ≤ y e x 6= y.

Viceversa, possiamo definire un ordinamento parziale da uno stretto:

x ≤ y sse x < y oppure x = y.

Definition 3.4. Sia A un insieme parzialmente ordinato dalla relazione ≤.

• Due elementi x e y di A si dicono comparabili se x ≤ y oppure y ≤ x; x e y sono incomparabili se n´e x ≤ y n´e y ≤ x;

• Un sottoinsieme X di A `e una catena se gli elementi di X sono comparabili a due a due.

• Un sottoinsieme X di A `e una anti-catena se gli elementi di X sono incomparabili a due a due.

Definition 3.5. Un ordinamento parziale ≤ su un insieme A `e ben fondato se non ammette catene discendenti infinite: a₀ > a₁ > a₂ > · · · > a_n > . . . .

Example 3.2. • Ordine naturale su N: x ≤ y se esiste k ∈ N tale che y = x + k.

L’ordinamento su N `e ben fondato.

• Ordine naturale su Z: x ≤ y se esiste k ∈ N tale che y = x + k. L’ordinamento su Z non `e ben fondato: 0 > −1 > −2 > . . . .

• Ordine di divisibilit`a su N: x|y se x divide y. Questo ordinamento ammette 1 come minimo elemento e 0 come massimo. `E un ordinamento ben fondato perch´e, per ogni x, esiste soltanto un numero finito di divisori di x.

• Ordine prefisso sulle stringhe: α ≤_pre β se esiste una stringa γ tale che β = αγ.

L’ordine prefisso `e ben fondato. Per esempio, cane >pre can >pre ca >pre c >pre λ, dove λ `e la stringa vuota.

• Ordine lessicografico sulle stringhe: Sia A = {a1, . . . , an} un alfabeto finito di carat- teri con a₁ < a₂ < · · · < a_n. Allora α ≤_lex β se α ≤_pre β oppure esistono stringhe γ, δ, η e caratteri a_i e a_j tali che α = γa_iδ e β = γa_jη con a_i < a_j. Un metodo per enumerare tutte le stringhe su un alfabeto finito, per esempio A = {a, b, c} con a < b < c, `e quello di enumerare prima le stringhe di lunghezza 0 (la sola stringa vuota λ), poi quelle di lunghezza 1, poi quelle di lunghezza 2 e cos`ı via. Le stringhe di lunghezza n, che sono in numero finito, sono ordinate in ordine lessicografico:

, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aac, aba, abb, abc, . . .

• Ordine parziale di “contenuto o uguale” sull’insieme P(X) delle parti di un insieme X: Se A e B sono sottoinsiemi di X, X ⊆ Y se ogni elemento di X `e anche elemento di Y . Se X `e infinito, l’ordine ⊆ non `e ben fondato. Per esempio, N ⊃ N \ {0} ⊃ N \ {0, 1} ⊃ . . . .

3.3. Relazioni di equivalenza e Partizioni

[2, Sezione 7.2, 7.3, 12.2]. Partizioni (vedi l’inizio di [2, Sezione 12.1]).

Sia R una relazione di equivalenza su A.

• [a]_R= {b : aRb} denota la classe di equivalenza di a ∈ A. In alcuni libri la classe di equivalenza [a]R`e denotata con a/R.

• La famiglia di sottoinsiemi ([a]R : a ∈ A) determina una partizione di A.

• L’insieme {[a]_R : a ∈ A} `e chiamato insieme quoziente ed `e denotato da A/R.

Sia P = (X_i : i ∈ I) una partizione di A. Allora la relazione aRb sse ∃i ∈ I.a, b ∈ X_i

`

e una relazione di equivalenza su A.

3.4. Funzioni

Un programma definisce una “regola” di trasformazione dei dati in input nei dati in output. Il concetto di funzione in matematica (si veda [2, Sezione 5.1]) formalizza e generalizza questa intuizione.

Definition 3.6. Siano A e B insiemi. Una funzione f : A → B (leggi: una funzione f da A in B) `e una regola che ad ogni elemento x di A assegna uno ed un solo elemento y di B. L’insieme A `e il dominio della funzione f , mentre l’insieme B `e il suo codominio.

L’elemento y, che `e il risultato dell’applicazione della funzione f ad x, si scrive y = f (x).

A volte si scrive f_x al posto di f (x).

Una funzione, oltre che dal suo dominio A e codominio B, `e caratterizzata dal suo comportamento “input-output”, che pu`o essere rappresentato dall’ insieme seguente:

{(x, y) ∈ A × B : y = f (x)}.

B^A denota l’insieme delle funzioni da A in B.

Example 3.3. La funzione di elevamento a quadrato ha l’insieme N come dominio e codominio, ed `e definita come segue: f (x) = x². Se applichiamo f all’elemento 2 ∈ N otteniamo f (2) = 4 come risultato.

Composizione di funzioni (si veda [2, Sezione 5.3]). Se f : A → B e g : B → C sono funzioni, allora la funzione g ◦ f : A → C `e definita come segue:

(g ◦ f )(x) = g(f (x)), per ogni x ∈ A.

Example 3.4. Consideriamo il seguente comando, dove a `e una variabile di tipo nat:

C ::= while a = [1 + 1] do a := [a ∗ a] od

Non `e difficile verificare che il comportamento input-output del programma input(a); C; output(a)

definisce la seguente funzione f da N in N:

f (x) =

(x if x 6= 2;

4, if x = 2.

Si consideri ora il programma:

D ::= input(a); a := [a ∗ a]; output(a)

il cui comportamento input-output definisce la seguente funzione g da N in N:

g(x) = x². Qual’`e il comportamento input-output del programma

input(a); C; D; output(a)

ottenuto componendo il primo comando C ed il secondo comando D? La composizione delle due funzioni f e g. La composizione di f e g si scrive f ; g con notazione informatica oppure g ◦ f con notazione matematica. Essa `e definita cos`ı:

(g ◦ f )(x) = g(f (x)).

In altre parole, per calcolare (g ◦ f )(x) prima applichiamo la funzione f ad x e successi- vamente applichiamo la funzione g a f (x). Nel nostro esempio,

(g ◦ f )(x) =

(x² if x 6= 2;

16, if x = 2.

Funzioni iniettive, surgettive e bigettive. Inversa di una funzione bigettiva [2, Sezione 5.2, 5.4]. Se f : A → B `e una funzione bigettiva, denotiamo con f⁻¹ : B → A la sua inversa.

4. Numeri naturali

Il tipo di dato pi`u semplice `e l’insieme dei numeri naturali con le usuali operazioni aritmetiche di addizione e moltiplicazione. Attenzione: Nel libro [2] l’insieme dei numeri naturali `e definito come {1, 2, 3, . . . }, mentre noi seguiremo l’usuale convenzione che 0 `e un naturale. Quindi studieremo le leggi algebriche dell’insieme

N = {0, 1, 2, . . . }.

4.1. Le leggi dell’algebra [2, Sezione 4.1]

1. . Come provare che l’enunciato ”∀xy(x + y = y + x)” `e vero? Si potrebbe verificare la propriet`a tramite la tabellina dell’addizione per le cifre da 0 a 9 e poi controllare che l’algoritmo dell’addizione che abbiamo imparato alla scuola elementare verifica la propriet`a. Comunque la prova dipende dalla rappresentazione che abbiamo scelto per i numeri naturali. Cosa succede se scegliamo di rappresentare i numeri in un alfabeto binario oppure con la rappresentazione romana? Il concetto di numero esiste a prescindere dalla sua rappresentazione concreta!

2. Leggi dell’algebra come assiomi. (N, +, ×, 0, 1) `e un quasi anello integrale:

(a) (N, +, 0) e (N, ×, 1) sono monoidi commutativi, cio`e verificano le seguenti leggi:

• Propriet`a associativa della somma: ∀xyz{x + (y + z) = (x + y) + z};

Per non mettere troppe parentesi tonde abbiamo scritto ∀xyz{. . . } al posto di ∀xyz(. . . ). Lo faremo spesso.

Inoltre spesso non scriveremo i quantificatori universali ∀; scriveremo quindi:

vale la propriet`a associativa della somma, x + (y + z) = (x + y) + z, sot- tintendendo che vale per ogni x, y, z.

• Propriet`a associativa del prodotto: x × (y × z) = (x × y) × z

• Propriet`a commutativa della somma: x + y = y + x;

• Propriet`a commutativa del prodotto: x × y = y × x

• Propriet`a dell’elemento neutro: x + 0 = 0 + x = x; x × 1 = 1 × x = x.

(b) x × 0 = 0 × x = 0.

(c) Distributivit`a della moltiplicazione rispetto alla somma: x × (y + z) = (x × y) + (x × z),

(d) Propriet`a di cancellazione della somma: x + z = y + z implica x = y, che formalmente si scrive:

∀xyz(x + z = y + z → x = y).

(e) Propriet`a di cancellazione del prodotto (questa legge `e chiamata anche legge dell’ integralit`a):

∀xyz(z 6= 0 ∧ z × x = z × y → x = y).

Come abbreviazione scriveremo spesso

(∀z 6= 0)(. . . ) al posto di

∀z(z 6= 0 → . . . )

Notazione: Di solito scriveremo xy al posto di x × y e supporremo che la moltipli- cazione lega di pi`u dell’addizione, cio`e xy + z sta per (x × y) + z.

3. L’ ordinamento sui numeri naturali si definisce come segue:

x ≤ y sse ∃z(x + z = y).

L’ordinamento stretto sui numeri naturali si definisce come segue:

x < y sse x ≤ y ∧ x 6= y sse ∃z 6= 0(x + z = y).

Supporremo che valga la seguente legge:

(Legge di tricotomia) Dati i numeri naturali x ed y, soltanto una delle seguenti tre condizioni vale: x < y oppure y < x oppure x = y.

Verifichiamo per ≤ le propriet`a che definiscono un ordinamento parziale:

• Propriet`a riflessiva: Da x + 0 = x segue x ≤ x.

• Propriet`a transitiva: sia x ≤ y e y ≤ z. Dalla definizione di ≤ segue che esistono k, r tali che x + k = y e y + r = z. Allora si ha:

x + (k + r) = (x + k) + r = y + r = z, da cui segue x ≤ z.

• Prima prova della propriet`a antisimmetrica: Sia x ≤ y e y ≤ x; allora, esistono k, r tali che x + k = y e y + r = x. Con semplici calcoli deriviamo:

x + (k + r) = (x + k) + r = y + r = x.

Dalla legge di cancellazione della somma e da x + (k + r) = x + 0 segue che k + r = 0, e quindi k = r = 0. In conclusione, y = x + k = x + 0 = x.

• Seconda prova della propriet`a antisimmetrica: Sia x ≤ y e y ≤ x. Supponiamo per assurdo che x 6= y. Allora, dalla definizione di ordinamento stretto segue che x < y e y < x. Ma ci`o contraddice l’assioma di tricotomia. Quindi supporre x 6= y ha portato ad un assurdo; ne segue che x = y vale.

• L’ordine `e totale dalla legge di tricotomia.

• 0 `e il minimo, cio`e 0 ≤ x per ogni numero naturale x.

5. Il principio di induzione

5.1. Il principio di induzione con base 0

Il Principio di Induzione [2, Sezioni 4.3, 4.4, 4.5, 4.6, 4.8] nella sua forma pi`u semplice:

sia P(x) una propriet`a sui numeri naturali.

P (0) ∧ ∀x(P (x) → P (x + 1)) → ∀xP (x).

In altri termini, per provare ∀xP (x) bisogna:

1. Base dell’induzione x = 0: Provare che P vale per il numero 0;

2. Ipotesi di induzione: Supporre che P valga per x.

3. Utilizzare l’ipotesi d’induzione per provare che P vale anche per x + 1.

Notazione: Una sommatoria si scrive con il simbolo Σ. Per esempio, 1 + 2 + · · · + n = X

1≤k≤n

k

Per esempio, se n = 3, allora

X

1≤k≤3

k = 1 + 2 + 3.

Example 5.1. Provare per induzione che X

0≤k≤x

(2k + 1) = (x + 1)².

1. Base dell’induzione x = 0: In questo caso 2 × 0 + 1 = 1 = (0 + 1)². 2. Ipotesi di induzione: Supponiamo che

X

0≤k≤x

(2k + 1) = (x + 1)².

3. Utilizziamo l’ipotesi d’induzione per provare che X

0≤k≤x+1

(2k + 1) = ((x + 1) + 1)².

Infatti, X

0≤k≤x+1

(2k +1) = ( X

0≤k≤x

2k +1)+2(x+1)+1 = (x+1)²+2(x+1)+1 = ((x+1)+1)².

Ne segue dal principio di induzione che l’ uguaglianza vale per ogni numero naturale x.

5.2. Il principio di induzione con base k

Il Principio di Induzione con base di induzione il numero naturale k:

P (k) ∧ ∀x(x ≥ k ∧ P (x) → P (x + 1)) → ∀x(x ≥ k → P (x)).

In altri termini, per provare che P (x) vale per ogni x ≥ k bisogna:

1. Base dell’induzione x = k: Provare che P vale per il numero k;

2. Ipotesi di induzione: Supporre che P valga per x ≥ k.

3. Utilizzare l’ipotesi d’induzione per provare che P vale anche per x + 1.

Example 5.2. Provare che per ogni numero naturale x ≥ 8, esistono due numeri interi y, z (y o z possono essere negativi) tali che x = 3y + 5z.

Prova:

1. Base dell’induzione (x = 8): 8 = 3 × 1 + 5 × 1;

2. Ipotesi di induzione: Supponiamo che x ≥ 8 e che x = 3y + 5z.

3. Allora x + 1 = 3y + 5z + 1. Ma 1 = 5 × 2 − 3 × 3, da cui x + 1 = 3y + 5z + 1 = 3y + 5z + 5 × 2 − 3 × 3 = 3(y − 3) + 5(z + 2).

Ne segue dal principio di induzione che l’ uguaglianza vale per ogni numero naturale x.

Notazione: Con [x, y] intendiamo l’insieme di tutti gli elementi z tali che x ≤ z ≤ y.

5.3. Il principio di induzione completa Il Principio di Induzione Completa:

P (0) ∧ ∀x(P (0) ∧ P (1) ∧ · · · ∧ P (x) → P (x + 1)) → ∀xP (x).

1. Base dell’induzione x = 0: Provare che P vale per 0;

2. Ipotesi di induzione: Supporre che P valga per tutti i numeri naturali nell’intervallo [0, x].

3. Utilizzare l’ipotesi d’induzione per provare che P vale anche per x + 1.

Invece del numero 0 si pu`o utilizzare un qualsiasi altro numero k.

Example 5.3. Provare che ogni numero naturale x ≥ 2 `e scomponibile in fattori primi.

Prova:

1. Base dell’induzione (x = 2): 2 `e un numero primo;

2. Ipotesi di induzione: Supponiamo che tutti i numeri nell’intervallo [2, x] siano scom- ponibili in fattori primi.

3. Consideriamo x + 1. Si hanno due possibilit`a: x + 1 `e primo oppure no. Nel primo caso una scomposizione in fattori primi di x + 1 `e data dal numero stesso. Nel secondo caso, x + 1 non `e primo; quindi esistono due altri numeri y, z tali che x + 1 = yz e y, z 6= 1, x + 1. Da queste due ultime relazioni segue che y e z appartengono all’intervallo [2, x]. Quindi, per ipotesi d’induzione sia y che z sono scomponibili in fattori primi: y = p₁. . . p_r e z = q₁. . . , q_s, con p_i, q_j primi. In conclusione, x + 1 = yz = p₁. . . p_rq₁. . . , q_s ammette una scomposizione in fattori primi.

Ne segue dal principio di induzione che ogni numero naturale x ≥ 2 `e scomponibile in fattori primi.

5.4. Dati induttivi

I numeri naturali sono definiti “induttivamente” a partire dal numero 0 applicando l’operazione di successore (+1). In altre parole,

1. 0 `e un numero naturale;

2. Se x `e un numero naturale allora x + 1 `e un numero naturale;

3. Nient’altro `e numero naturale.

Il principio di induzione trova la sua giustificazione nella precedente definizione.

Altri tipi di dato sono definiti induttivamente a partire da alcuni dati di base utilizzando delle operazioni che “costruiscono” dati pi`u complessi. Di seguito troverete degli esempi.

Example 5.4. (Stringhe sull’alfabeto {a, b}) Indichiamo con  la stringa vuota, cio`e la stringa senza caratteri. L’insieme {a, b}<sup>∗</sup> delle stringhe di alfabeto {a, b} `e definito induttivamente come segue:

1. “” `e una stringa;

2. Se α `e una stringa allora la concatenazione αa delle stringhe α e del carattere a `e una stringa;

3. Se α `e una stringa allora la concatenazione αb delle stringhe α e del carattere b `e una stringa;

4. Nient’altro `e stringa.

Per esempio, la concatenazione di ababa e bbb `e la stringa abababbb., mentre la concate- nazione di ababa e la stringa vuota  `e uguale alla stringa ababa.

Sia P una propriet`a sulle stringhe. Il principio di induzione per il tipo di dato stringa (le variabili α e β variano sull’insieme delle stringhe):

P () ∧ ∀α(P (α) → P (αa) ∧ P (αb)) → ∀αP (α).

Exercize 5.1. Provare per induzione che, per ogni stringa α, la lunghezza della stringa αα `e un numero pari.

Indichiamo con l(α) la lunghezza di una stringa α. La lunghezza l(αβ) della concate- nazione di due stringhe α e β `e uguale a l(α) + l(β).

1. Base dell’induzione:  =  ha lunghezza 0 che `e pari.

2. Ipotesi di induzione: Consideriamo una stringa α, e supponiamo per ipotesi d’induzione che l(αα) sia un numero pari.

3. Consideriamo la stringa αa. Se permutiamo i caratteri presenti in una stringa la sua lunghezza non cambia. Quindi

l(αaαa) = l(ααaa) = l(αα) + l(aa).

Per ipotesi d’induzione l(αα) `e pari e l(aa) = 2 che `e pari.

Ne segue dal principio di induzione che ogni stringa αα ha lunghezza pari.

Example 5.5. (Espressioni aritmetiche) Siano a, 0, 1, [, ], +, ∗ dei caratteri.

L’insieme EXP delle espressioni aritmetiche `e definito induttivamente come segue:

1. a, 0 e 1 sono espressioni;

2. Se E₁ e E₂ sono espressioni allora [E₁+ E₂] e [E₁∗ E₂] sono espressioni.

3. Nient’altro `e espressione.

Esempio: Le stringhe “[a+1]” e “[0+[a∗0]]” sono espressioni, mentre le stringhe “[a+1[”

e “[]” non sono espressioni.

Sia P una propriet`a che pu`o essere soddisfatta o meno dalle espressioni. Il principio di induzione per il tipo di dato espressione (le variabili x e y variano sull’insieme delle espressioni):

P (a) ∧ P (0) ∧ P (1) ∧ ∀xy{P (x) ∧ P (y) → P ([x + y]) ∧ P ([x ∗ y])} → ∀xP (x).

Exercize 5.2. Provare per induzione che ogni espressione ha un numero pari di parentesi.

Indichiamo con p(E) il numero di parentesi dell’espressione E.

1. Base dell’induzione: L’espressione “a” ha 0 parentesi (che `e pari), cos`ı come le espressioni “0” e “1”.

2. Ipotesi di induzione: Supponiamo che le espressioni E1 e E2 abbiano un numero pari di parentesi, cio`e p(E₁) e p(E₂) sono numeri pari.

3. Consideriamo [E₁ + E₂]. Allora si ha: p([E₁+ E₂]) = p(E₁) + p(E₂) + 2, che `e un numero pari, perch´e per ipotesi d’induzione p(E₁) e p(E₂) sono numeri pari. Un ragionamento simile funziona per l’espressione [E₁∗ E₂].

Example 5.6. (Comandi) Dopo aver definito le espressioni, definiamo induttivamente il tipo dei comandi. Supponiamo che a, b sono le sole variabili a disposizione per eseguire comandi di assegnamento.

L’insieme COM dei comandi `e definito induttivamente come segue:

1. Se E `e una espressione allora le stringhe “a := E” e “b := E” sono comandi;

2. Se C₁, C₂ sono comandi ed E₁, E₂ sono espressioni, allora “C₁; C₂” e “while E₁ = E₂ do C₁ od”

sono comandi.

3. Nient’altro `e comando.

Ecco un comando sintatticamente corretto: while [a ∗ 0] = 1 do a := [a ∗ [a ∗ 1]]; b := [1 + 1] od.

Sia P una propriet`a che pu`o essere soddisfatta o meno dai comandi. Il principio di induzione per il tipo di dato comando lo scriviamo informalmente (c, c₁, c₂ sono variabili che prendono valori in COM, mentre E, E₁E₂ sono variabili che prendono valori in EXP).

Da ∀E{P (a := E) ∧ P (b := E)}

e ∀c₁c₂{P (c₁) ∧ P (c₂) → P (c₁; c₂)}

e ∀E1E2∀c{P (c) → P (while E1 = E2 do c od)}

segue ∀cP (c)

Se volessimo provare per induzione che una propriet`a P vale per tutti i comandi, dovremmo partire dalla base dell’induzione che in questo caso comprende infiniti casi.

Infatti possiamo scrivere un numero infinito di comandi di assegnamento a := E al vari- are di E nell’insieme infinito EXP.

5.5. Definizione ricorsiva di funzioni

Se un insieme A `e definito per induzione, allora possiamo definire “ricorsivamente”

funzioni di dominio A. Nel seguito prima di presentare lo schema generale di ricorsione, consideriamo degli esempi.

Example 5.7. Ricordiamo che i numeri naturali sono definiti induttivamente a partire dal numero 0 e dalla funzione successore “+1” (si veda Sezione 5.4). Allora definiamo la funzione 2^x per ricorsione a partire dalla funzione successore e dalla funzione di moltipli- cazione:

(i) 2⁰ = 1;

(ii) 2^x+1 = 2 × 2^x.

Proviamo per induzione che la propriet`a “la funzione 2<sup>x</sup> `e ben definita su x” vale per ogni numero naturale x.

Base dell’induzione 2⁰ `e ben definita perch´e 2<sup>0</sup> = 1 Ipotesi d’induzione Supponiamo di aver ben definito 2<sup>x</sup> Allora 2<sup>x+1</sup> `e ben definita perch´e 2^x+1 = 2 × 2^x

Conclusione Per il principio d’induzione 2^x `e definita per ogni x Come si calcola ricorsivamente:

2² = 2¹⁺¹ =_(ii) 2 × 2¹ = 2 × 2⁰⁺¹ =_(ii) 2 × (2 × 2⁰) =_(i) 2 × (2 × 1)) = 2 × 2 = 4 Example 5.8. Definiamo il fattoriale di x per ricorsione come segue:

(i) 0! = 1;

(ii) (x + 1)! = (x + 1) × x!.

Proviamo per induzione che la propriet`a “la funzione fattoriale `e ben definita su x” vale per ogni numero naturale x.

Base dell’induzione ! `e ben definita su 0 perch´e 0! = 1 Ipotesi d’induzione Supponiamo di aver ben definito x!

Allora (x + 1)! `e ben definita perch´e (x + 1)! = (x + 1) × x!

Conclusione Per il principio d’induzione x! `e definita per ogni x Come si calcola ricorsivamente:

3! =_(ii) 3×2! =_(ii)3×(2×1!) =_(ii)3×(2×(1×0!)) =_(i) 3×(2×(1×1)) = 3×(2×1) = 3×2 = 6.

Nei prossimi due esempi definiamo ricorsivamente la somma ed il prodotto. Il dominio della funzione somma (oppure del prodotto) `e l’insieme delle coppie di numeri naturali.

Example 5.9. Definiamo la somma di x e y per ricorsione a partire dalla funzione successore “+1”. L’induzione `e sul secondo argomento y:

(i) x + 0 = x;

(ii) x + (y + 1) = (x + y) + 1.

Fissiamo x ∈ N. Allora la propriet`a “P (y) ≡ la funzione x + y `e ben definita su y”

dipende soltanto da y. Proviamo per induzione che vale ∀yP (y). Dall’arbitrartiet`a della scelta di x, seguir`a che la funzione x + y sar`a ben definita per ogni x, y.

Base dell’induzione x + 0 `e ben definita perch´e uguale a x Ipotesi d’induzione Supponiamo di aver ben definito x + y

Allora x + (y + 1) `e ben definita perch´e uguale a (x + y) + 1 Conclusione Per il principio d’induzione x + y `e ben definita per ogni y

Come si calcola ricorsivamente:

5 + 3 = (5 + 2)+1 = ((5 + 1)+1)+1 = (((5 + 0)+1)+1)+1 = ((5+1)+1)+1 = (6+1)+1 = 7+1 = 8.

Example 5.10. Definiamo il prodotto di x e y per ricorsione a partire dalla funzione successore “+1” e dalla somma. L’induzione `e sul secondo argomento y:

(i) x × 0 = 0;

(ii) x × (y + 1) = (x × y) + x.

Fissiamo x ∈ N. Proviamo per induzione che la propriet`a “x × y `e ben definita su y” vale per ogni y.

Base dell’induzione x × 0 `e ben definita perch´e uguale a 0 Ipotesi d’induzione Supponiamo di aver ben definito x × y

Allora x × (y + 1) `e ben definita perch´e uguale a (x × y) + x Conclusione Per il principio d’induzione x × y `e ben definita per ogni y Come si calcola ricorsivamente:

5 × 3 = (5 × 2)+5 = ((5 × 1)+5)+5 = (((5 × 0)+5)+5)+5 = ((0+5)+5)+5 = (5+5)+5 = 10+5 = 15.

Example 5.11. Definiamo la lunghezza di una stringa per ricorsione. Essa `e una fun- zione dall’insieme {a, b}^∗ nell’insieme N.

(i) len() = 0;

(ii) len(αa) = len(α) + 1; len(αb) = len(α) + 1.

Base dell’induzione len() `e ben definita perch´e uguale a 0 Ipotesi d’induzione Supponiamo di aver ben definito len(α)

Allora len(αa) e len(αb) `e ben definita perch´e uguale a len(α) + 1 Conclusione Per il principio d’induzione len(α) `e ben definita per ogni α Veniamo ora alla definizione generale dello schema di definizione ricorsiva. Per sem- plicit`a ci limiteremo all’insieme dei numeri naturali.

Definition 5.1. Una funzione g : N → N `e definita ricorsivamente a partire da una costante c e da una funzione h : N × N → N se

g(0) = c; g(x + 1) = h(x, g(x)).

Per esempio, nel caso della funzione 2^x abbiamo c = 1 e h(x, y) = 2×y. Allora abbiamo:

(i) 2⁰ = c = 1

(ii) 2^x+1 = h(x, 2^x) = 2 × 2^x.

Nel caso del fattoriale c = 1 e h(x, y) = (x + 1) × y. Allora abbiamo:

(i) 0! = c = 1

(ii) (x + 1)! = h(x, x!) = (x + 1) × x!.

Generalizziamo lo schema di ricorsione con dei parametri in pi`u.

Definition 5.2. Una funzione f : Nⁿ⁺¹ → N `e definita ricorsivamente a partire da una funzione g : Nⁿ → N e da una funzione h : Nⁿ⁺² → N se

f (x₁, . . . , x_n, 0) = g(x₁, . . . , x_n); f (x₁, . . . , x_n, y + 1) = h(x₁, . . . , x_n, y, f (x₁, . . . , x_n, y)).

Per esempio, nel caso della funzione x + y abbiamo un parametro x, g(x) = x e h(x, y, z) = z + 1. Allora abbiamo:

(i) x + 0 = g(x) = x

(ii) x + (y + 1) = h(x, y, x + y) = (x + y) + 1.

Nel caso del prodotto x × y abbiamo un parametro x, g(x) = 0 e h(x, y, z) = z + x.

Allora abbiamo:

(i) x × 0 = g(x) = 0

(ii) x × (y + 1) = h(x, y, x × y) = (x × y) + x.

5.6. Il principio del buon ordinamento

Minimo e Massimo. Il principio del buon ordinamento: ogni sottoinsieme di N ha minimo elemento [2, Sezione 4.7].

Theorem 5.1. Il principio del buon ordinamento su N `e equivalente al principio di in- duzione su N.

Proof.

5.7. Il principio d’induzione e prove di correttezza

Il principio di induzione `e collegato ai cicli iterativi della programmazione. Spieghiamo il perch´e con un esempio.

Consideriamo il problema di calcolare il quoziente ed il resto della divisione di x ≥ 0 per d > 0. Essi sono definiti come gli unici numeri q ed r che soddisfano la seguente relazione:

x = (q × d) + r, 0 ≤ r < d.

L’algoritmo usuale consiste nel sottrarre ripetutamente d a x, aumentando di volta in volta di 1 il valore di q (eventuale quoto) e decrementando di d il valore di r (eventuale resto).

q := 0; r := x; while (r ≥ d) do q := q + 1; r := r − d od (1) L’algoritmo `e corretto se proviamo per induzione sul numero di volte che eseguiamo il corpo del “while” che la relazione x = (q × d) + r `e un “invariante”, cio`e se vale prima dell’esecuzione del “while” allora vale anche dopo l’esecuzione del “while”.

Definiamo per induzione le due funzioni q : N → N e r : N → N ∪ {errore}:

(i) q0 = 0;

(ii) q_n+1= q_n+ 1.

(i) r₀ = x;

(ii)

r_n+1=

(errore if r_n < d oppure r_n= errore;

r_n− d, if r_n ≥ d.

Proviamo per induzione su n che ∀n(r_n 6= errore → x = q_nd + r_n). Ricordiamo che per provare una implicazione

Base dell’induzione: q₀d + r₀ = 0 × d + x = x, perch`e per definizione r₀ 6= errore Ipotesi d’induzione: Supponiamo che sia vera r_n 6= errore → x = q_nd + r_n

Allora Proviamo che r_n+1 6= errore → x = q_n+1d + r_n+1. Supponiamo che

r_n+1 6= errore. Allora dalla definizione di r segue che r_n+1 = r_n− d. Quindi si ha:

q_n+1d + r_n+1= (q_n+ 1)d + (r_n− d) = q_nd + d + r_n− d = q_nd + r_n = x

Quest’ultima uguaglianza si ha per ipotesi d’induzione perch`e da r_n+1 6= errore si he necessariamente r_n6= errore.

Conclusione Per il principio d’induzione ∀n(r_n6= errore → x = q_nd + r_n).

Ritorniamo ora al comando in (1). Dopo aver eseguito i comandi di assegnamento q := 0; r := x, q₀ e r₀ sono i valori delle variabili q ed r. Non `e difficile provare per induzione su n che q<sub>n</sub> e r<sub>n</sub> con r<sub>n</sub>< d sono i valori delle variabili q ed r dopo aver eseguito il corpo del while per n volte. Quindi, dal fatto che vale ∀n(r<sub>n</sub>6= errore → x = q<sub>n</sub>d + r<sub>n</sub>), dopo l’esecuzione del “while” avremo che x = q<sub>n</sub>d + r<sub>n</sub> per un opportuno n, ed inoltre 0 ≤ r<sub>n</sub>< d. Ne segue che il comando (1) `e corretto.

6. Logica: enunciati e loro dimostrazione

In matematica si dimostrano enunciati che esprimono propriet`a di oggetti matematici.

Gli enunciati sono di solito espressi in linguaggio naturale. Gli oggetti matematici possono essere di tipo differente: interi, reali, matrici, sequenze, insiemi, funzioni continue, gruppi, etc... Quando dimostriamo un enunciato φ, esprimiamo un giudizio di verit`a: l’enunciato φ `e vero perch´e ne abbiamo una prova. In tal caso, la negazione dell’enunciato `e falsa. In matematica non esistono altri valori di verit`a oltre il vero ed il falso. Nella vita reale la situazione `e ben diversa.

6.1. Espressioni e formule atomiche

Nel linguaggio della matematica gli enunciati atomici sono costruiti mettendo in re- lazione tra di loro elementi che appartengono al mondo della matematica (oggetti matem- atici, per brevit`a). Per esempio, 3 < 5 e 5 + 7 = 12 sono enunciati atomici veri, mentre 5 < 3 e 5 + 7 = 13 sono enunciati atomici falsi. Dagli esempi si evince che “atomico” sig- nifica “costruito senza i connettivi logici e i quantificatori”. Per poter costruire enunciati atomici abbiamo bisogno di poter nominare gli oggetti matematici. Questo viene fatto introducendo la categoria sintattica delle espressioni. In algebra le espressioni possono

denotare gli elementi di un gruppo oppure di uno spazio vettoriale, mentre in analisi le espressioni possono denotare numeri reali o funzioni continue. Vi sono anche espressioni che denotano insiemi di elementi, per esempio, sottogruppi, sottospazi vettoriali, etc.

• Le espressioni senza variabili denotano oggetti matematici:

– 3 denota (= `e un nome per) il numero naturale tre

– 5 + 6 denota (= `e un nome per) il numero naturale undici

– 0.3147 denota (= `e un nome per) il numero reale 3/10+1/100+4/1000+7/10000 – {3, 6, 7} denota (= `e un nome per) l’insieme con elementi 3, 6 e 7

– “L’autore di Romeo e Giulietta” `e una espressione che denota (= `e un nome per) Shakespeare

– “Il padre di Antonino Salibra” `e una espressione che denota (= `e un nome per) Luigi Salibra

• Le espressioni con variabili denotano oggetti matematici generici. Non appena si assegna un valore alle variabili nell’universo del discorso si ottiene un nome per un particolare oggetto matematico:

– x denota un elemento generico

– 5 + x, dove x varia nell’insieme dei numeri naturali (l’universo del discorso), denota un generico numero naturale pi`u grande o uguale a 5. Se ad x assegnamo il valore 10, allora 5 + x denota 15.

– 0.3xy7 denota un generico numero reale della forma 3/10+x/100+y/1000+7/10000 (in questo caso le variabili x e y variano tra le cifre 0, 1, . . . , 9)

– {x, y} denota un insieme generico di al pi`u due elementi (in questo caso le variabili x, y variano tra tutti i possibili elementi)

– “L’autore di x” denota un generico scrittore (in questo caso la variabile x varia tra i titoli dei libri)

• Un enunciato atomico (senza occorrenze di variabili) denota un valore di verit`a:

– 3 divide 21 (vero)

– 121 `e un multiplo di 11 (vero) – 3 = 5 + 6 (falso)

– 11 + 6 `e un numero primo (vero) – 5 `e dispari (vero)

– 3 ∈ {3, 6, 7} (vero) – {3} ⊆ {3, 6, 7} (vero)

– John ama Mary (non si sa, dipende dal contesto in cui si pronunzia l’enunciato) – John `e il padre di Mary (come sopra)

– P (5) (leggi: 5 ha la propriet`a P ). Se non si conosce quale propriet`a P rappre- senta, non si conosce il valore di verit`a.

– {3, 5} ⊆ {x ∈ N : x `e dispari} (vero)

Le locuzioni “divide”, “`e un multiplo di”, “=”, “⊆”, “ama”, “`e il padre di” sono chiamate relazioni binarie (o predicati binari). Le relazioni binarie mettono in relazioni coppie di oggetti matematici che appartengono all’universo del discorso. Le locuzioni “`e dispari”,

“`e un numero primo” e “P” sono propriet`a o predicati unari.

• Un enunciato atomico (con occorrenze di variabili) denota un valore di verit`a dopo che interpretiamo le variabili nell’universo del discorso:

– x divide 122 – x + y = y + x

– 3 + 5 = 5 + 3 (`E un caso particolare della formula x + y = y + x, dove x = 3 e y = 5)

– x `e un numero primo – x `e dispari

– 3 ∈ X – X ⊆ Y

– {3} ⊆ {3, 6, 7} (it is a particular instance of the atomic formula X ⊆ Y , where X = {3} and Y = {3, 6, 7})

– John ama X

– P (x) (leggi: x ha la propriet`a P )

Altri esempi di enunciati atomici possono essere trovati in [2, Ex.1.2.1] e [2, Ex.1.2.5,6].

6.2. Enunciati composti [2, Sezione 1.3]

Enunciati pi`u complessi si possono definire a partire dalle formule atomiche utilizzando i connettivi proposizionali:

∧ (and, e); ∨ (or, oppure); ¬ (not, non);

→ (if-then, se-allora); ↔ (if and only if, se e solo se), il quantificatore universale

∀ (Every, Ogni) e il quantificatore esistenziale

∃ (Some, Qualche).

Un’altra espressione idiomatica per il quantificatore universale `e “per tutti” e per il quan- tificatore esistenziale `e “esiste”.

Precedenze tra connettivi proposizionali : Per eliminare parentesi, adottiamo il seguente schema di precedenze:

1 : ¬, ∀, ∃ 2 : ∧, ∨ 3 : →

Allora ∀xA ∧ B → C ∨ ¬D corrisponde all’enunciato ((∀xA) ∧ B) → (C ∨ (¬D)), dove A, B, C, D sono enunciati arbitrari.

Alcuni esempi di enunciati composti:

• 5 `e un numero primo e 8 `e un numero pari.

• Un numero `e pari se e solo se `e divisibile per 2.

• 5 non `e un numero pari.

• Ogni numero naturale `e somma di due numeri primi.

• Per ogni x esiste y tale che P (x, y).

I quantificatori universale ed esistenziale hanno significato soltanto in relazione ad un universo del discorso. Per esempio, il valore di verit`a dell’enunciato “Esiste un uomo alto”

dipende dal contesto. Se pensiamo alle persone presenti in un asilo di bambini, l’enunciato

`

e falso; se l’universo del discorso riguarda la squadra di basket della nazionale italiana l’enunciato `e vero.

Ecco alcuni esempi di enunciati universali ed esistenziali. Altri enunciati esistenziali e universali possono essere trovati in [2, Sezione 1.4 e 1.5].

• Esiste un numero diverso da 1 che divide 122. Nel linguaggio formale della matem- atica si scrive: ∃x(x 6= 1 ∧ ∃y(122 = x · y)). L’enunciato si legge letteralmente come segue: Esiste x diverso da 1 tale che x · y = 122, per qualche y.

• Propriet`a commutativa: ∀x∀y(x + y = y + x).

Notiamo che la logica classica `e una logica a due valori di verit`a. Quindi, un enunciato

`

e vero oppure falso, ma non entrambe le cose.

Le tavole di verit`a dei connettivi logici :

• A ∧ B `e un enunciato vero sse l’enunciato A `e vero e l’enunciato B `e vero (in tutti gli altri casi A ∧ B `e un enunciato falso);

• A ∨ B `e un enunciato falso sse l’enunciato A `e falso e l’enunciato B `e falso (in tutti gli altri casi A ∨ B `e un enunciato vero);

• A → B `e un enunciato falso sse l’enunciato A `e vero e l’enunciato B `e falso (in tutti gli altri casi A → B `e un enunciato falso);

• A ↔ B `e un enunciato vero sse A e B sono entrambi veri oppure A e B sono entrambi falsi (in tutti gli altri casi A ↔ B `e un enunciato falso);

• ¬A `e vero sse A `e falso.

L’enunciato “5 `e un numero primo e 8 `e un numero pari” `e un enunciato vero perch´e sia

“5 `e un numero primo” che “8 `e un numero pari” sono enunciati veri.

L’enunciato “5 `e un numero primo oppure 8 `e un numero dispari” `e un enunciato vero perch´e “5 `e un numero primo” `e un enunciato vero.

6.3. Significato dei quantificatori 6.3.1. Universo del discorso finito

Consideriamo, per esempio, l’insieme {0, 1, 2, 3, 4} come universo del discorso. Allora l’enunciato universale ∀xP (x) `e vero sse la congiunzione finita

P (0) ∧ P (1) ∧ P (2) ∧ P (3) ∧ P (4)

`

e un enunciato vero. Quindi il quantificatore universale ∀x `e una forma abbreviata di ∧.

Similmente, l’enunciato esistenziale ∃xP (x) `e vero sse la disgiunzione finita P (0) ∨ P (1) ∨ P (2) ∨ P (3) ∨ P (4)

`

e un enunciato vero. Quindi il quantificatore esistenziale ∃x `e una forma abbreviata di ∨.

6.3.2. Universo del discorso infinito

Se l’universo del discorso `e infinito, per esempio l’insieme dei numeri naturali, allora

∀xP (x) `e equivalente ad una congiunzione infinita

P (0) ∧ P (1) ∧ P (2) ∧ · · · ∧ P (n) ∧ . . .

Verificare che ∀xP (x) `e vero richiede un tempo infinito. Devo verificare che gli infiniti enunciati P (0), P (1), P (2), . . . , P (n), . . . sono tutti veri!

Consideriamo un esempio concreto. L’enunciato “Ogni numero pari maggiore di tre `e somma di due numeri primi”. Questo enunciato `e vero sse 4 `e somma di due primi, 5

`

e somma di due primi, 6 `e somma di due primi, 7 `e somma di due primi, etc. Infiniti enunciati! L’enunciato “x > 3 `e somma di due primi” `e stato verificato al computer sino a x = 400.000.000.000.000, ma nessun matematico `e riuscito a dimostrarlo sinora per ogni x.

L’enunciato ∃xP (x) `e equivalente ad una disgiunzione infinita P (0) ∨ P (1) ∨ P (2) ∨ · · · ∨ P (n) ∨ . . . 6.4. Esercizi di Formalizzazione

In questa sezione presentiamo alcuni esercizi di formalizzazione dal linguaggio naturale al linguaggio formale della matematica.

6.4.1. Primo Esempio

Consideriamo un primo enunciato: “Miriam ammira ogni professore”. Dopo aver fis- sato come universo del discorso l’insieme degli esseri umani, eseguiamo un’analisi log- ica dei componenti dell’enunciato. “Miriam” `e il nome di una persona e come tale `e un’espressione. Il termine “Professore” `e una propriet`a degli esseri umani. Il verbo

“ammirare” `e transitivo, quindi determina una relazione binaria tra il soggetto ed il com- plemento oggetto. Il termine “Ogni” `e collegato alla quantificazione universale. Nel linguaggio naturale le variabili sono nascoste.

Dichiarazione di costanti, operazioni, propriet`a e relazioni :

• Universo del discorso: Insieme degli esseri umani

• “m” `e una espressione costante che sta per “Miriam”

• P (x) significa x `e un professore

• xAy significa x ammira y.

Cerchiamo di capire qual’`e la traduzione dell’enunciato formale

∀x(mAx)

Ricordiamo che ∀x significa “per ogni elemento x dell’universo del discorso”, che nel nostro esempio significa “per ogni essere umano x”. Allora, abbiamo la seguente sequenza di traduzioni equivalenti.

• Per ogni essere umano x, Miriam ammira x

• Ogni essere umano `e ammirato da Miriam

• Miriam ammira ogni essere umano

• Miriam ammira tutti (con sottinteso “gli esseri umani”)

Per formalizzare l’enunciato originale dobbiamo ridurre la portata della quantificazione universale da “Per ogni essere umano x” a “Per ogni professore x”. L’insieme dei profes- sori `e un sottoinsieme dell’insieme degli esseri umani. Dobbiamo riuscire a formalizzare

“Per ogni essere umano x che `e un professore”. In generale, ”Ogni Professore” ”Tutti i Professori” si traducono utilizzando l’implicazione:

∀x(P (x) → ....) Quindi, Miriam ammira ogni professore si traduce come

∀x(P (x) → mAx) Abbiamo la seguente sequenza di traduzioni equivalenti.

• Per ogni essere umano x, se x `e un professore allora Miriam ammira x

• Per ogni essere umano x che `e un professore, Miriam ammira x

• Ogni essere umano che `e un professore `e ammirato da Miriam

• Ogni professore `e ammirato da Miriam

• Miriam ammira ogni professore

6.4.2. Altri Esempi

1. Alcuni professori ammirano Miriam: Cerchiamo di capire qual’`e la traduzione dell’enunciato formale

∃x(xAm)

Ricordiamo che ∃x significa “per qualche elemento x dell’universo del discorso”, che nel nostro esempio significa “per qualche essere umano x”. Allora, abbiamo la seguente sequenza di traduzioni equivalenti.

• Per qualche essere umano x, x ammira Miriam

• Qualche essere umano ammira Miriam

• Qualcuno ammira Miriam

Per formalizzare l’enunciato originale dobbiamo ridurre la portata della quantifi- cazione esistenziale da “Qualche essere umano x” a “Qualche professore x”. L’insieme dei professori `e un sottoinsieme dell’insieme degli esseri umani. Dobbiamo riuscire a formalizzare “Per qualche essere umano x che `e un professore”. In generale,

”Qualche Professore” si traduce utilizzando la congiunzione (e non l’implicazione!):

∃x(P (x) ∧ ....)

Quindi, Alcuni professori ammirano Miriam si traduce come

∃x(P (x) ∧ xAm) 2. Miriam ammira solo i professori :

∀x(P (x) → mAx) ∧ ∀x(¬P (x) → ¬mAx) Si pu`o portare il quantificatore universale fuori

∀x((P (x) → mAx) ∧ (¬P (x) → ¬mAx)) perch´e vale la seguente regola logica:

∀x(Q(x) ∧ R(x)) ↔ (∀xQ(x) ∧ ∀xR(x)) 3. Un solo professore ammira Miriam:

∃x(P (x) ∧ xAm ∧ ∀z(P (z) ∧ zAm → z = x)) 4. Almeno due professori ammirano Miriam:

∃xy(P (x) ∧ P (y) ∧ x 6= y ∧ xAm ∧ yAm)

Aggiungiamo altri predicati: B(x, y) (x ama y), C(x) (x `e un corso), S(x) (x `e uno studente).

5. Nessuno studente ama ogni corso:

¬∃x(S(x) ∧ ∀y(C(y) → xBy)) 6. Nessun corso `e amato da tutti gli studenti :

¬∃x(C(x) ∧ ∀y(S(y) → yBx))

7. x `e un numero primo: Ricordiamo che un numero naturale `e primo se `e diverso da 0, 1 ed `e divisibile solo per 1 e se stesso.

P (x) ≡_def x 6= 0 ∧ x 6= 1 ∧ ∀z(∃k(x = z · k) → z = 1 ∨ z = x) 6.5. Tecniche di dimostrazione

1. Tecniche elementari di dimostrazione [2, Sezione 1.6].

• Per provare un enunciato esistenziale ∃xP (x) bisogna trovare un elemento a tale che P (a) `e vero. Per esempio, se vogliamo dimostrare l’enunciato “Esiste un numero x il cui quadrato `e uguale a 121”, `e sufficiente trovare la soluzione x = 11.

• Controprova di enunciato universale ∀xP (x): trovare un controesempio [2, Ex.1.6.3]. Per esempio, se vogliamo falsificare l’enunciato “Ogni numero diverso da 0 e 1 `e un numero primo”, `e sufficiente trovare un numero diverso da 0, 1 che non `e primo, per esempio x = 8.

• Prova di enunciato universale ∀xP (x): si utilizzano le propriet`a generali delle variabili quantificate; esempio: [2, Ex. 1.6.2].

• Controprova di enunciato esistenziale ∃xP (x): si prova che P (x) `e falso utiliz- zando le propriet`a generali della variabile x.

• Altre tecniche di dimostrazione: dimostrazione per contraddizione [2, Sezione 1.6, Theorem]; dimostrazione per contropositiva [2, Sezione 3.5, Example].

• Prove di uguaglianza di espressioni numeriche e di espressioni insiemistiche.

2. Tavole di verit`a: and, or, not [2, Sezione 3.1]; equivalenza logica ed il connettivo if-and-only-if [2, Sezione 3.2]; if-then [2, Sezione 3.2]. Quantificatori esistenziali ed universali [2, Sezione 3.6].

REFERENCES

1. F. Bellissima, F. Montagna. Matematica per l’informatica: aritmetica e logica, probabilit`a, grafi. Carocci Editore, 2006.

2. Norman L. Biggs: Discrete Mathematics, Oxford University Press, 2002.

3. David M. Burton. Elementary Number Theory. Allyn and Bacon, 1980.

4. M. Cesaroli, F. Eugeni, M. Protasi. Elementi di Matematica Discreta. Zanichelli, 1988.