LIBRO ADOTTATO

G.M. PIACENTINI CATTANEO: MATEMATICA DISCRETA,

ed. ZANICHELLI

LIBRI CONSIGLIATI

A. FACCHINI: ALGEBRA E MATEMATICA DISCRETA,

ed. ZANICHELLI

M.G. BIANCHI, A. GILLIO: INTRODUZIONE ALLA MA-

TEMATICA DISCRETA, ed. McGRAW-HILL

L. DI MARTINO, M.C. TAMBURINI: APPUNTI DI ALGE-

BRA, ed. CLUED

INSIEMI NUMERICI

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

insieme dei numeri naturali

Z = {. . . ,−4,−3,−2,−1,0,1,2,3,4, . . . }insieme dei numeri relativi

Q e l’insieme dei numeri della forma pq ,

dove p e q sono numeri relativi e q e diverso da 0; Q si diceinsieme dei numeri razionali

con il simbolo R indicheremo l’insieme dei numeri reali e definiremoanche l’insieme C dei numeri complessi.

SIMBOLI FONDAMENTALI

Il simbolo di appartenenza di un oggetto ad un insieme e:

” ∈ ”

si legge: ”appartiene” oppure ”e elemento di”. Ad esempio:

3 ∈ N, −1 ∈ Z,5

3∈ Q, −

√5 ∈ R

I simboli di inclusione sono:

⊂⊆il primo indica l’inclusione stretta o propria (che puo essere an-

che scritta come $) tra insiemi e si legge: ”e incluso (oppure

e contenuto) propriamente o strettamente” o anche ”e sottoin-

sieme proprio”, il secondo si legge ”e incluso (o uguale)” oppure

”e contenuto (o uguale)”. Esempi: N ⊂ Z, Z ⊂ Q.

Definizione 1 Si dice che due insiemi A e B sono uguali, e si

scrive A = B, se essi hanno gli stessi elementi.

E chiaro, quindi, che A = B se e soltanto se A ⊆ B e B ⊆ A.

osservazione 2 Quali che siano gli insiemi A, B, C si ha:

1. A ⊆ A

2. se A ⊆ B e B ⊆ A allora A = B

3. se A ⊆ B e B ⊆ C allora A ⊆ C

Naturalmente abbiamo le negazioni:

”non appartiene”: /∈

esempi: −3 /∈ N, 13 /∈ Z, π /∈ Q

”non e contenuto”: *

esempi: Z * N, R * Q.

Insieme vuoto: ∅

e l’insieme che non ha elementi. Si osservi che esso e sottoin-

sieme di qualunque insieme.

Si puo assegnare un insieme enumerando i suoi elementi (nel caso

questo sia possibile), oppure tramite una proprieta caratteristica,

ovvero una proprieta che verificano tutti e soli gli elementi dell’in-

sieme che si vuole definire. Si scrive:

A = {x ∈ U | P(x)} oppure A = {x ∈ U : P(x)}

Esempi: {x ∈ Z | x > −3}, {3n | n ∈ N}.

quantificatori:

∀ quantificatore universale

∃ quantificatore esistenziale

il primo si legge ”per ogni”, il secondo si legge ”esiste”.

Si usa anche il simbolo

∃|

che vuol dire ”esiste ed e unico”.

Esempi:

(∀n ∈ N) (3n ∈ N)

Sia P l’insieme dei numeri pari. Allora si puo scrivere

P = {n ∈ Z | ∃m ∈ Z tale che n = 2m}.

L’insieme D dei numeri dispari puo essere scritto come

D = {n ∈ Z | ∃h ∈ Z tale che n = 2h + 1}.

(∀x)(x /∈ ∅)

(∀A insieme)(∅ ⊆ A)

Connettivi logici

congiunzione: ∧ che si legge ”e”

disgiunzione: ∨ che si legge ”o”.

Esempi: (8 ∈ P) ∧ (8 e divisibile per 4)

sia n ∈ Z allora: (n ∈ P) ∨ (n ∈ D).

Definizione 3 Dati due insiemi A e B si definiscono l’unione

A ∪B e l’intersezione A ∩B come segue:

A ∪B = {x |x ∈ A ∨ x ∈ B}

A ∩B = {x |x ∈ A ∧ x ∈ B}

Si osserva subito che per ogni insieme A

A ∪ ∅ = A A ∩ ∅ = ∅

e che se A ⊆ B allora si ha

A ∪B = B A ∩B = A.

1. (A ∪B) ∪ C = A ∪ (B ∪ C) proprieta associativa dell’unione

2. (A∩B)∩C = A∩(B∩C) proprieta associativa dell’intersezione

3. A ∪B = B ∪A proprieta commutativa dell’unione

4. A ∩B = B ∩A proprieta commutativa dell’intersezione

5. (A∪B)∩C = (A∩C)∪(B∩C), A∩(B∪C) = (A∩B)∪(A∩C)

6. (A∩B)∪C = (A∪C)∩(B∪C), A∪(B∩C) = (A∪B)∩(A∪C)

5. proprieta distributive dell’intersezione rispetto all’unione,6. proprieta distributive dell’unione rispetto all’intersezione.

Definizione 4 Sia A insieme e B ⊆ A si definisce il complementare

di B rispetto ad A:

{A(B) = {x ∈ A | x /∈ B}.

Si ha ovviamente:

{A(A) = ∅; {A(∅) = A; B ∪ {A(B) = A; B ∩ {A(B) = ∅

Si dimostrano le LEGGI DI DE MORGAN:

{A(B ∪ C) = {A(B) ∩ {A(C); {A(B ∩ C) = {A(B) ∪ {A(C)

Definizione 5 L’insieme:

A r B = {x ∈ A | x /∈ B}

si dice insieme differenza tra l’insieme A e l’insieme B

Definizione 6 Sia A un insieme. Si dice insieme delle parti di Ae si indica con P(A) l’insieme formato da tutti i sottoinsiemi diA. In simboli:

P(A) = {X | X ⊆ A}

E ovvio che A ∈ P(A), ∅ ∈ P(A), se X ∈ P(A), Y ∈ P(A), alloraX ∪ Y ∈ P(A) e X ∩ Y ∈ P(A).

Definizione 7 Siano A e B insiemi. Si definisce il prodotto carte-siano:

A×B = {(a, b) | a ∈ A, b ∈ B}.

Naturalmente si ha: A× ∅ = ∅ ×A = ∅.

Definizione 8 Siano A e B insiemi. Si dice relazione tra A e Bun qualunque sottoinsieme del prodotto cartesiano.

Sia A un insieme ed R una relazione tra gli elementi di A, cioe

R ⊆ A×A.

Definizione 9 Si dice che R e riflessiva se e verificata la se-

quente condizione:

(∀a ∈ A) ((a, a) ∈ R).

osservazione 10 Ovviamente, perche R non sia riflessiva basta

che esista un solo elemento x ∈ A tale che (x, x) /∈ A.

Definizione 11 Si dice che R e antiriflessiva se e verificata la

sequente condizione:

(∀a ∈ A) ((a, a) /∈ R).

Esempi Delle relazioni sull’insieme A = {α, β, γ}

R1 = {(α, α), (β, β), (γ, γ), (α, β), (α, γ)}

R2 = {(α, α), (β, β), (α, β), (β, γ)}

R3 = {(α, β), (β, α), (γ, β), (β, γ), (γ, γ)}

R4 = {(α, β), (β, α), (α, γ)}

R5 = {(α, α), (β, β), (γ, γ), (α, β), (β, α)}

sono riflessive R1 e R5, e antiriflessiva R4 mentre R2 e R3 non

sono riflessive (ne’ antiriflessive).

Definizione 12 Si dice che R e simmetrica se e verificata la

sequente condizione:

(∀a, b ∈ A) (se (a, b) ∈ R allora (b, a) ∈ R).

osservazione 13 Naturalmente e sufficiente che esista una sola

coppia (x, y) ∈ R, x 6= y, tale che (y, x) /∈ R perche R non sia

simmetrica.

Definizione 14 Si dice che R e antisimmetrica se e verificata la

sequente condizione:

(∀a, b ∈ A) (se ((a, b) ∈ R ∧ (b, a) ∈ R) allora a = b).

Esempi Si ha: R1 e R2 sono antisimmetriche, R3 e R5 sono

simmetriche, R4 non e simmetrica ne’ antisimmetrica.

Definizione 15 Si dice che R e transitiva se e verificata la se-

quente condizione:

(∀a, b, c ∈ A) (se ((a, b) ∈ R ∧ (b, c) ∈ R) allora (a, c) ∈ R).

osservazione 16 Anche in questo caso e sufficiente che esistano

(x, y), (y, z) ∈ R tali che (x, z) /∈ R perche R non sia transitiva.

Esempi Si ha: R1 e R5 sono transitive, R2, R3 e R4 non lo

sono.

osservazione 17 Si osservi che spesso si usa la notazione aRb

in luogo di (a, b) ∈ R.

Definizione 18 Si dice che R e una relazione d’ordine se e ri-

flessiva, antisimmetrica e transitiva. La coppia ordinata (A,R)

(ovvero l’insieme A munito della relazione d’ordine) si chiama in-

sieme ordinato.

Esempio 19 R1 e d’ordine.

Esempio 20 Sia X un insieme. Allora la relazione ” ⊆ ” e una

relazione d’ordine su P(X). Infatti dall’osservazione 2 si ha che

per ogni A, B, C sottoinsiemi di X

1. A ⊆ A

2. se A ⊆ B e B ⊆ A allora A = B

3. se A ⊆ B e B ⊆ C allora A ⊆ C

Esempio 21 L’ordinamento naturale ” ≤ ” sull’insieme Z dei

numeri relativi e la relazione definita come segue:

∀m, n ∈ Z, si dice che m ≤ n se e solo se ∃h ∈ N tale che n = m+h.

Si verifica che ” ≤ ” e una relazione d’ordine su Z.

Definizione 22 Siano m, n ∈ Z, m 6= 0. Si dice che m divide

oppure e un divisore di n (ovvero che n e un multiplo di m) e si

scrive

m | n

se esiste h ∈ Z tale che n = mh.

Si osserva subito che un qualunque numero intero divide 0.

Esempio 23 La relazione ”| ” sull’insieme N∗ := N r {0} dei

numeri naturali non nulli e una relazione d’ordine.

Esempio 24 Per ogni n ∈ N∗ si indica con Dn l’insieme dei di-

visori di n. Di particolare interesse e la relazione d’ordine ”| ”

indotta sull’insieme Dn.

Definizione 25 Sia (A,≤) un insieme ordinato, X un sottoin-

sieme di A, x0 ∈ X. Si dice che x0 e minimo di X se:

∀x ∈ X x0 ≤ x.

Si dice che x0 e massimo di X se

∀x ∈ X x ≤ x0.

Proposizione 26 Sia (A,≤) un insieme ordinato, X un sottoin-

sieme di A. Se esiste un massimo (o un minimo) di X, esso e

unico.

Dimostrazione Siano, infatti, x0 e x1 due massimi di X. Allora,

poiche x0 e massimo e x1 ∈ X, si ha x1 ≤ x0 e, scambiando i ruoli

di x0 e x1, si ha x0 ≤ x1. Per la proprieta antisimmetrica delle

relazioni d’ordine deve essere x0 = x1. (Analoga la dimostrazione

dell’unicita del minimo.)

E quindi lecito scrivere x0 = min(X) se x0 e il minimo (che si

dice anche il piu piccolo elemento) di X, oppure x0 = max(X)

se x0 e il massimo (che si dice anche il piu grande elemento) di

X.

Esempi

1. considerato l’insieme ordinato (A,R1), dove A = {α, β, γ} e

R1 = {(α, α), (β, β), (γ, γ), (α, β), (α, γ)}.

Si ha α = min(A) ma non esiste il massimo di A

2. 0=min(N), ma non esiste il massimo considerando su N la

relazione d’ordine ” ≤ ” naturale

3. 1 = min(N∗) ma non esiste il massimo considerando su N∗ la

relazione d’ordine ”|”

4. considerando il sottoinsieme X = {2,3,9,18} come sottoin-

sieme dell’insieme ordinato (N∗, |), esiste max(X) = 18 ma

non esiste il minimo di X

5. considerando l’insieme ordinato (Dn, |) si ha min(Dn) = 1,

max(Dn) = n

Definizione 27 Sia (A,≤) un insieme ordinato, A ⊆ X. Un ele-

mento y ∈ A si dice minorante di X se

(∀x ∈ X)(y ≤ x).

Se X e dotato di minoranti si dice minorato o limitato inferior-

mente.

Definizione 28 Sia (A,≤) un insieme ordinato, X un sottoin-

sieme di A, minorato, α ∈ A. Si dice che α e estremo inferiore di

X se e il piu grande dei minoranti.

In altri termini α e estremo inferiore di se verifica le seguenti

condizioni:

1. (∀x ∈ X) (α ≤ x)

2. ∀ β ∈ A tale che (∀x ∈ X) (β ≤ x) si ha β ≤ α.

Si vede che se esiste un estremo inferiore, esso e unico, per

cui e lecito scrivere α = inf(X). Inoltre, se inf(X) ∈ X, allora

inf(X) = min(X).

Definizione 29 Sia (A,≤) un insieme ordinato, A ⊆ X. Un ele-

mento y ∈ A si dice maggiorante di X se

(∀x ∈ X)(x ≤ y).

Se X e dotato di maggioranti si dice maggiorato o limitato su-

periormente.

Definizione 30 Sia (A,≤) un insieme ordinato, X un sottoin-

sieme di A, maggiorato, α ∈ A. Si dice che α e estremo superiore

di X se e il piu piccolo dei maggioranti.

In altre parole α e estremo superiore verifica le seguenti con-

dizioni:

1. (∀x ∈ X) (x ≤ α)

2. ∀ β ∈ A tale che (∀x ∈ X) (x ≤ β) si ha α ≤ β.

Si vede che se esiste un estremo superiore di X, esso e unico, per

cui e lecito scrivere α = sup(X). Inoltre, se sup(X) ∈ X, allora

sup(X) = max(X).

osservazione 31 Nel caso X = {x, y}, α = sup(x, y) vuol dire

1. x ≤ α, y ≤ α

2. ∀ β ∈ A tale che x ≤ β, y ≤ β si ha α ≤ β.

Analogamente α = inf(x, y) si scrive

1. α ≤ x, α ≤ y

2. ∀ β ∈ A tale che β ≤ x, β ≤ y si ha β ≤ α.

Definizione 32 Sia (A,≤) un insieme ordinato. Si dice che ” ≤ ”

e una relazione di ordine totale ovvero che (A,≤) e totalmente

ordinato se e soltanto se

(∀x, y ∈ A) (x ≤ y ∨ y ≤ x).

Nel caso contrario, cioe se ∃x, y tali che x � y ∧ y � x, si dice

che ” ≤ ” e una relazione di ordine parziale oppure che (A,≤) e

parzialmente ordinato.

Esempi Sono totalmente ordinati (N,≤), (Z,≤); sono parzial-

mente ordinati (N∗, |), (Dn, |), (P(X),⊆), (A,R1).

Definizione 33 Siano A, B insiemi non vuoti, R una relazione

tra elementi di A ed elementi di B. Si dice che R e una relazione

funzionale se e soltanto se

∀a ∈ A ∃|b ∈ B tale che (a, b) ∈ R

Se R e una relazione funzionale tra A e B, la terna ordinata

f = (A, B,R) si dice applicazione o funzione tra A e B. A si dice

dominio o insieme di partenza di f , B si dice insieme di arrivo di

f . La relazione R si chiama grafico di f .

Quando ci si riferira ad applicazioni, si supporra implicitamente

che l’insieme di partenza e l’insieme di arrivo siano non vuoti.

Esempi: Siano A = {1,2,3,4}, B = {a, b, c, d, e} allora

R = {(1, a), (2, b), (2, c), (3, d), (4, e)}

non e funzionale,

R′ = {(1, a), (2, a), (3, b), (4, c)}

e funzionale

R′′ = {(1, a), (2, b)(4, c)}

non e funzionale.

D’ora in avanti si usera la notazione

f : A → B

per indicare un’applicazione dall’insieme A all’insieme B. Se,

inoltre, Rf e la relazione funzionale tale che f = (A, B,Rf), si

porra b = f(a) se e solamente se (a, b) ∈ Rf . In questo caso si

dice che b e l’immagine di a mediante f o il valore assunto da f

in a. Pertanto il grafico dell’applicazione f e:

Rf = {(a, f(a)) | a ∈ A}.

Quindi l’applicazione f ′ = (A, B,R′) precedentemente introdotta

si scrivera nel modo seguente:

f ′ : A → B tale che f ′(1) = a, f ′(2) = a, f ′(3) = b, f ′(4) = c.

Chiaramente due applicazioni f : A → B, g : C → D sono uguali

se e soltanto se A = C, B = D e ∀a ∈ A f(a) = g(a).

Si osservi che un’applicazione e una particolare relazione, mentre

non e vero che una qualsiasi relazione e un’applicazione.

Esempi

1. Siano X e Y insiemi, c ∈ Y . Allora l’applicazione

fc : X → Y tale che ∀x ∈ X fc(x) = c

si dice applicazione costante di costante valore c

2. sia X un insieme. Allora l’applicazione

idX : X → X tale che ∀x ∈ X idX(x) = x

si dice applicazione identica di X

3. f1 : Z → Z tale che ∀n ∈ Z f1(n) = 2n

4. f2 : Z → Z tale che ∀x ∈ Z f2(x) = x2 non e un’applicazione

5. f3 : P → Z tale che ∀x ∈ P f3(x) = x2

6. f4 : Q∗ → Q tale che ∀x ∈ Q f4(x) = 1x

7. f5 : Z → Z tale che ∀a ∈ Z f5(a) = a2.