Matematica Discreta-Insiemi e Aplicazioni PDF

Preview

Summary

Matematica Discreta -Insiemi e Aplicazioni...

Description

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 MATEMATICA DISCRETA, ed. McGRAW-HILL L. DI MARTINO, M.C. TAMBURINI: APPUNTI DI ALGEBRA, 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 dice insieme dei numeri razionali con il simbolo R indicheremo l’insieme dei numeri reali e definiremo anche 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: √ 5 3 ∈ N, −1 ∈ Z, ∈ Q, − 5 ∈ R 3

I simboli di inclusione sono:

 ⊂ ⊆

il primo indica l’inclusione stretta o propria (che pu` o essere anche scritta come $) tra insiemi e si legge: ”` e incluso (oppure ` e contenuto) propriamente o strettamente” o anche ”` e sottoinsieme 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.

` chiaro, quindi, che A = B se e soltanto se A ⊆ B e B ⊆ A. E 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,

1 ∈ 3 /

Z, π ∈ /Q

”non ` e contenuto”: * esempi:

Z * N, R * Q . Insieme vuoto:

∅

` e l’insieme che non ha elementi. Si osservi che esso ` e sottoinsieme di qualunque insieme.

Si pu` o assegnare un insieme enumerando i suoi elementi (nel caso questo sia possibile), oppure tramite una propriet` a caratteristica, ovvero una propriet` a che verificano tutti e soli gli elementi dell’insieme 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 pu` o scrivere

P = {n ∈ Z | ∃m ∈ Z tale che n = 2m}. L’insieme D dei numeri dispari pu` o essere scritto come

D = {n ∈ Z | ∃h ∈ Z tale che n = 2h + 1}. (∀x)(x ∈ / ∅) (∀A insieme)(∅ ⊆ A)

Connettivi logici

Esempi:

congiunzione:

∧ che si legge ”e”

disgiunzione:

∨ che si legge ”o”.

(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) propriet` a associativa dell’unione 2. (A∩B)∩C = A∩(B∩C) propriet` a associativa dell’intersezione 3. A ∪ B = B ∪ A propriet` a commutativa dell’unione 4. A ∩ B = B ∩ A propriet` a 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. propriet` a distributive dell’intersezione rispetto all’unione, 6. propriet` a 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 A e si indica con P(A) l’insieme formato da tutti i sottoinsiemi di A. In simboli: P(A) = {X | X ⊆ A} ` ovvio che A ∈ P(A), ∅ ∈ P(A), se X ∈ P(A), Y ∈ P(A), allora E X ∪ Y ∈ P(A) e X ∩ Y ∈ P(A). Definizione 7 Siano A e B insiemi. Si definisce il prodotto cartesiano: 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 B un qualunque sottoinsieme del prodotto cartesiano.

Sia A un insieme ed R una relazione tra gli elementi di A, cio` e R ⊆ A × A. Definizione 9 Si dice che R ` e riflessiva se ` e verificata la sequente condizione: (∀a ∈ A) ((a, a) ∈ R). osservazione 10 Ovviamente, perch` e 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 perch` e 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 sequente 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 perch` e 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 riflessiva, antisimmetrica e transitiva. La coppia ordinata (A, R) (ovvero l’insieme A munito della relazione d’ordine) si chiama insieme 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 divisori di n. Di particolare interesse ` e la relazione d’ordine ”| ” indotta sull’insieme Dn.

Definizione 25 Sia (A, ≤) un insieme ordinato, X un sottoinsieme 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 sottoinsieme 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, poich` e x0 ` e massimo e x1 ∈ X, si ha x1 ≤ x0 e, scambiando i ruoli di x0 e x1, si ha x0 ≤ x1. Per la propriet` a antisimmetrica delle relazioni d’ordine deve essere x0 = x1. (Analoga la dimostrazione dell’unicit` a del minimo.) ` quindi lecito scrivere x0 = min(X) se x0 ` E e il minimo (che si dice anche il pi` u piccolo elemento) di X, oppure x0 = max(X ) se x0 ` e il massimo (che si dice anche il pi` u 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 sottoinsieme 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 elemento y ∈ A si dice minorante di X se (∀x ∈ X)(y ≤ x). Se X ` e dotato di minoranti si dice minorato o limitato inferiormente. Definizione 28 Sia (A, ≤) un insieme ordinato, X un sottoinsieme di A, minorato, α ∈ A. Si dice che α ` e estremo inferiore di X se ` e il pi` u 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 elemento y ∈ A si dice maggiorante di X se (∀x ∈ X)(x ≤ y ). Se X ` e dotato di maggioranti si dice maggiorato o limitato superiormente. Definizione 30 Sia (A, ≤) un insieme ordinato, X un sottoinsieme di A, maggiorato, α ∈ A. Si dice che α ` e estremo superiore di X se ` e il pi` u piccolo dei maggioranti.

In altre parole α ` e estremo superiore verifica le seguenti condizioni:

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, cio` e 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 parzialmente 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 riferir` a ad applicazioni, si supporr` a 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 user` a 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 porr` a 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 scriver` a 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

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

5. f3 : P → Z tale che ∀x ∈ P f3(x) = 2x 6. f4 : Q∗ → Q tale che ∀x ∈ Q f4(x) = x1 7. f5 : Z → Z tale che ∀a ∈ Z f5(a) = a2....