Matematica Discreta - Appunti parte 1

NOZIONI DELLA MATEMATICA

La matematica è fatta di convenzioni. Spieghiamo, dunque, quali sono le convenzioni generalmente usate per descrivere la matematica.

Una qualsiasi nuova lettera come A indica un insieme. Gli insiemi presentano simbolo. Ad esempio, quando voglio scrivere che x piccolo appartiene all'insieme A, scrivo:

x ∈ A

Il simbolo di appartenenza lo uso anche per dire:

1 ∈ {0,1,2,3}

Per dire che un valore non appartiene a un insieme:

4 ∉ {0,1,2,3}

Per indicare l'insieme dei numeri naturali:

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

Altri insiemi conosciuti sono:

Z = {...,-2,-1,0,1,2,...}

(da ricordare che lo 0 è l'elemento neutro)

Q = {_m/_n | n,m ∈ Z / n > 0} "anche i che...!"

R (definiamo e utilizzeremo mi seguito) C = {a + ib | a,b ∈ R} dove i² = -1

Esiste l'insieme vuoto. Questo è l'insieme che non è presente alcun elemento. Si indica con:

ϕ = {}

Un altro tipo di insieme potrebbe essere senza numeri, quindi di valori o simboli. Ad esempio:

X = {IN, ϕ, a}

Tale insieme ha 3 elementi. Di conseguenza:

IN ∈ X, ϕ ∈ X, a ∈ X

Nozioni della Matematica

La matematica è fatta di convenzioni. Spieghiamo, dunque, quali sono le convenzioni generalmente usate per descrivere la matematica.

Un qualsiasi insieme viene indicato con una lettera maiuscola.

Gli insiemi presentano simboli.

Ad esempio, quando voglio scrivere che x piccolo appartiene all’insieme A, scrivo:

x ∈ A

Il simbolo di appartenenza lo uso anche per dire:

1 ∈ {0,1,2,3}

Per dire che un valore non appartiene a un insieme:

4 ∉ {0,1,2,3}

Per indicare l’insieme dei numeri naturali:

ℕ = {0,1,2,}

Altri insiemi conosciuti sono:

ℤ = {..., -2, -1, 0, 1, 2, ...}

(Da ricordare che lo 0 è l’elemento neutro)

ℚ = { ^m/_n | m, n ∈ ℤ ∧ n > 0 }

"Tali/i che..."

ℝ (definiamo e intenderemo mi seguenti)

ℂ = { a + ib | a, b ∈ ℝ }

dove i² = -1

Esiste l’insieme vuoto.

Ovvero l’insieme che non ha e possiede alcun elemento.

Si indica con:

ϕ = {}

Un altro tipo di insieme potrebbe essere senza numeri, quindi di valori o simboli. Ad esempio:

X = {ℕ, ϕ, a}

Tale insieme ha 3 elementi. Di conseguenza:

ℕ ∈ X, ϕ ∈ X, a ∈ X

Esiste anche la nozione di sottoinsieme.

Tale nozione fa uso nel caso in cui l'insieme A è contenuto in B.

Posso dire che A è contenuto in B se ogni elemento di A si

indica con:

A ⊆ B

Ogni insieme ha almeno un sottoinsieme.

Ogni insieme, inoltre, ha almeno come sottoinsieme

l'insieme vuoto.

Quindi, tornando ai due insiemi A e B, A è un sottoin-

sieme se per ogni elemento di A appartiene a B.

si indica con:

∀x ∈ A ⇒ x ∈ B

Facciamo un esempio.

Io ho come insiemi

B = {0, 1, 2, 3}

A = {0, 3}

Ho che A ⊆ B

Posso anche dire che l'insieme formato dal solo zero,

è contenuto in B.

Quindi sono che:

{0} ⊆ B

Se considero un solo elemento e quindi 0∈0,

saro per forza spinto a dire che zero appartiene a B.

Quindi è sono che:

0 ∈ B

Possiamo ora provare a scrivere i sottoinsiemi di un'insieme.

1 Esercizio:

È dato l'insieme B.

B = {0, 1, 2, 3}

Scrivere tutti i sottoinsiemi di B.

Prima di cominciare bisogna definire la cardinalità di B.

Essa si scrive come:

|B| = 4

Ovvero:

# B = 4

Ora possiamo scrivere tutti i sottoinsiemi di B.

• ∅
• {0}
• {1}
• {2}
• {3}
• {0,1}
• {0,2}
• {0,3}
• {1,2}
• {1,3}
• {2,3}
• {0,1,2}
• {0,1,3}
• {0,2,3}
• {1,2,3}

B

In totale ho 16 sottoinsiemi, o meglio:

2⁴ sottoinsiemi di B

Non a caso ciò sa per la cardinalità di B.

In generale, se ho un insieme X:

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

insieme delle parti di X

Riprendendo l'insieme precedente B, avevo:

B = { 0, 1, 2, 3 }

Denotiamo P(B):

P(B) = { ∅ , {0}, ... , {0,1,2,3}, B }

quindi |P(B)| = 2⁴

Possiamo trovare un'altra scrittura, ovvero quella dei sottoinsiemi.

Possiamo, quindi, scrivere:

B ⊆ A sottoinsieme

PRODOTTO CARTEGIANO DI DUE INSIEMI

Abbiamo due insiemi A, B.

Definiamo A, come:

A = { a, b, c }

Definiamo B, come:

B = { 0, 1, 2, 3 }

Cosa intendo per il prodotto di A e di B? (A x B)

Per A x B intendo il insieme di tutte le coppie di numeri con le proprietà tando il cui primo elemento sta in A e le secondo in B.

Quindi, in questo caso:

A x B = { (a,0), (b,0), (c,0), (b,1), (a,1), (c,1) ,

(a,2), (b,2), (c,2), (a,3), (b,3), (c,3) }

Il prodotto di A x B mi da il risultato scritto precedentemente, poiché:

Se prendiamo generalmente gli insiemi X e Y, allora definiamo il loro prodotto come:

X x Y = { (x,y) | x∈X, y∈Y }

In generale, la cardinalità di X x Y viene definita come:

Se |X| = n, |Y|= m = → |X x Y| = n · m

Noi conosciamo già il prodotto cartesiano, perciò lo scriviamo il prodotto cartesiano R ²:

R x R = R ² = { (x,y) | X∈R, Y∈R }

In generale, il prodotto di più insiemi è scritto come:

A x B x C := { (a,b,c) | a∈A, b∈B, c∈C }

Riprendiamo l'insieme B precedente, avem:

B= {0,1,2,3}

In generale per definizione:

B= { n∈ IN | 0 ≤ n ≤4 }

Prendiamo gli insiemi X e Y, definiti come:

X = {a | P(a)}Y = {b | Q(b)}

Voglio rappresentare l'unione di X e Y.Quindi scrivo:

X ∪ Y = {a | a ∈ X ∨ a ∈ Y} = {a | P(a) ∨ Q(a)}

Voglio rappresentare l'intersezione di X e Y.Quindi scrivo:

X ∩ Y = {a | a ∈ X ∧ a ∈ Y} = {a | P(a) ∧ Q(a)}

Potremmo prendere:

X = {n ∈ ℕ | 2/n}Y = {n ∈ ℕ | 2 divides n}

Nell'unione:X ∪ Y = {n ∈ ℕ | 2/n ∨ 2 x n} = ℕ

Nell'intersezione:X ∩ Y = {n ∈ ℕ | 2/n ∧ 2 x n} = ∅

Prendiamo, ad esempio:

X = ℕY = {y ∈ ℝ | 0 ≤ y ≤ 7}

X ∩ Y = {y ∈ ℕ | y ∈ ℝ ∧ (y ∈ ℝ 0 ≤ y < 7)} == {0, 1, 2, 3, 4, 5, 6}

Prendiamo A ⊂ XEsiste il complementare di A e lo indichiamo con:

A^C

ista per complemento

Quindi:

A^C = { x ∈ I | x ∉ A }

Esempio:

Abbiamo B ⊆ I quindi B = { n ∈ N | 0 ≤ n ≤ 4 }

Il complemento di B lo definiamo come:

B^C = { n ∈ N | n ^/∈ B } = { n ∈ N | P(n) è falsa }

= { n ∈ N | n > 4 }

LEGGI DISTRIBUTIVE

1. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
2. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

LEGGI DI DE MORGAN

3. (A ∩ B)^C = A^C ∪ B^C
4. (A ∪ B)^C = A^C ∩ B^C

Dimostrazione 1

x ∈ A ∩ (B ∪ C)

=> x ∈ A e x ∈ B ∪ C

=> x ∈ A e ( x ∈ B oppure x ∈ C )

     x ∈ B => x ∈ A ∩ B

     x ∈ C => x ∈ A ∩ C

                  x ∈ (A ∩ B) ∪ (A ∩ C)

Disegno:

Dimostrazione 3)

x ∈ (A ∩ B)^c ⇒ x ∉ A ∩ B ⇒ x ∈ A^c ∪ x ∈ B^c ⇒⇒ x ∈ A^c ∪ B^c

Disegno:

INDUZIONE

Con l'induzione si lavora sui n ∈ ℕ e ℤ.Abbiamo n! definito come fattoriale e sappiamo che 0! = 1 percio' e' la nostra iniziale.Regola per calcolare il successivo, con il fattoriale:

(n+1)! = (n+1) n!

1 Esempio:

Calcoliamo le fattoriale di 4, quindi 4!Sappiamo che:

0! = 1

quindi:1! = 1 · 0! = 1 · 1 = 12! = 2 · 1 = 23! = 3 · 2! = 64! = 4 · 3! = 4 · 6 = 24

Questo metodo di ricorrenza permette di definire le valore di n! ∀ n ∈ ℕ.

Definizione per ricorrenza:z⁰ = 1

quindi: zⁿ⁺¹ = z · zⁿ

Dimostrazione per induzione:

Sappiamo che n/1 > 2ⁿ ∀n > 4

Coloro di bianco per n, quando ho eliminato nero.Coloro di nero di n, quando ho eliminato stesso.

Conclusione che:

1. Ho un minuto bianco
2. Il successivo di un minuto bianco è bianco.

(Quindi da ho un poi tutti i minuti sono bianchi)

Ho = 4 (1) è vera 4/1 > 2⁴

Supponiamo che n/1 > 2ⁿdimostro che n+1 è bianco.Allora:

(n+1)/1 > 2 _n+1

(n+1)n/1 > (n+1) 2ⁿ > 2 2ⁿ = 2ⁿ⁺¹

Per ed principio di induzione nel eliminato ∀n ≥ 4.Quindi i numeri ≤ 4 sono bianchi.

PRINCIPIO DI INDUZIONE

Abbiamo visto l'ultima volta le definizioni per induzione omeglio anche ricorzione attraverso l'esempio della funzione fattoriale. Affrontiamo, quindi, le dimostrazioni per induzione (le dimostrazioni per induzione seguono un principio simile a quello usato per le unzioni anche se diverse deleas che in questo caso si tratta di uno strumento per dimostrare qualcosa anziché per definire qualcosa.) I problemi di dimostrazione si affrontano in due fasi: una analitica una algebrica le prime due fasi si conducono anche al calcolatore la prima giornata.

• PRINCIPIO DI INDUZIONE (I° FORMA)

Sia P(n) una proprietà definita per n ε Z (per i numeri interi). Supponiamo che valgano due parti "a" e "b" che affermano:

1. ∃ n₀ ε Z tale che P(n₀) sia vero (ovviamente non deve essere ∞). Tale punto viene definito come PASO BASE.
2. ∀ k ≥ n₀ se P(k) è vero ⇒ P(k+1) è vero Tale punto viene definito come PASO INDUTTIVO ipotesi induttiva

Se entrambe queste ipotesi sono verificate, allora la tesi c'è che:

P(m) è vera ∀ n ≥ n₀

Il principio di induzione serve a dimostrare che una qualità d'im è vera. Come faccio a dimostrare che è vera? Verifico le ipotesi, ovvero che paso base e che paso induttivo. Non mai utilizzato la dimostrazione per induzione perché lo presentiamo come un'ulima, ovvero una cosa che: il minune dovrebbe essere vera da perso senza dimostrare. Quindi: solo principio viene automaticamente preso per vero. C'è una quantità iniziale e io ho 10 penne nel tavolo e ne aggiungo una allora vedo che ho 5 penne più mila e di conseguentemente 6. Voi al contrario devo dimostrare di avere 6 penne nel tavolo, dato che una penna potrebbo essersi rotta, essere volata do fuori casa e quindi: a risulto vero. Così funzionano. Con il principio di induzione, la proprietà, prima, detto che ci mettiamo delle sporo con un penne, visto che abbiamo utilizzato il principio di induzione e chiamato a passo andiamo a ulteriorxvaro.

ESEMPIO:

Dimostrare che n! ≥ 2^m ∀ n ≥ 4 In questo caso P(n) è: P(m) = {n! ≥ 2^"}P(m) dimostrato che provo che per i numeri interi e cioè se è vero o faso. Cosa devo verificare? Devo vericare l'ipotesi "a" e l'ipotesi "b". L'ipotesi "a", quella che abbiamo definito come paso base e l'ipotesi "b" come paso indutivo. Nel nostro caso "l'ipotesi" in quanto nel vedere se P((4) è vera. Chi c' P(4) ? E' coloro che mi dice che 4! >= 2... fini questo caso P è vero. Dobbiamo fare l'ipotesi induttiva. Abbiamo verificato P(5) è vero P(4). Verificazione passo base. Verifica induttivo.

Le passo induttivo non è sempre facile da dimostrare, perché io devo ipotizzare che P(k) sia vero e dimostrare che allora P(k+1) sia vero.

Quindi, assumo che per avere ipotesi induttiva che k² sia

induttivo uguale a 2^k, quindi

k² ≤ 2^k e voglio dimostrare che (k+1)² ≤ 2^k+1

Per il procedimento, mi chiedo come posso usare questa disuguaglianza per ottenere quella cosa?

Devo migliorare l'espressione

Star dunque pone a dimostrazione

quindi (k+1)² = k² + 2k + quindi ho seguito i calcoli.

Quello è vero induttivo è crucialmente che k² ≤ 2^k quindi posso considerare questa disuguaglianza

k² + 2k ≤ 2^k+1.

Io so che 2^k+1 = 2∙2^k, quindi quello che voglio dimostrare.

In ogni quota è equivalente,

quello che segua è in eccesso 2^k equivalente io so che k^k+1 ≤ 2k.

Soltanto c 2^k da tutti è due le porti.

Quindi:

So che 2^k ≥ k² e k ^≥ 4 > 2+1

Allora, dunque, dimostrato che due punti "i" e "ii" sono veri allo stesso tempo, io Principium Induttivo delle paradose che la mia dimostrazione sia vera.

ALTRO ESEMPIO

Dimostrare che per ogni numero naturale positivo n vale:

ⁿ∑_i=1 i = n(n+1)/2

È possibile dimostrare ciò attraverso una dimostrazione visiva, ma non valida per il principio induttivo.

Consideriamo un rettangolo n x (n+1) di casi 4 x 5:

Rettangolo 4 x 5 diviso in due parti: ciascuna ci area 1+2 e 3+4

Una sperata come quello mi figura lo divide in due parti di

area n²+n, dunque vale che ∑ i = n(n+1)/2.

Aiutiamo a dimostrare inizialmente la formula, ma stavolta per induzione.

Per prima cosa si propone P(n).

P(1) si dice n^{i i=1} = n(n+1)/2,

la base del'induzione tolierà di questo che per avere P(k)

sia Ugualmente equivalente a dire voglio orare che ogni numero

intero k ≥ 4, e vero l'implicazione P(k).

PASSO BASE Questo rappresenta operazione propria sostenerà

sotto che ∑_1-ai=1 e uguale a 1(1+1) /^{2 4}

PASSO INDUTTIVO

Sia k ≥ 1 un intero. Dobbiamo dimostrare che è vera l'implicazione:

∑_i=1^k+1 i = k(k+1)/2 ⇒ ∑_i=1^k+1 i = (k+1)(k+1+1)/2

Per fare ciò basta dimostrare che, se assumiamo vera la nostra ipotesi induttiva, ossia:

∑_i=1^k i = k(k+1)/2, allora deve essere vera ∑_i=1^k+1 i = (k+1)(k+1+1)/2

Scriviamo ∑_i=1^k+1 i separando la somma così: ∑_i=1^k+1 i = (∑_i=1^k i) + (k+1)

L'ipotesi induttiva ci permette di sostituire, al posto di (∑_i=1^k i), il suo valore k(k+1)/2.Otteniamo:

∑_i=1^k+1 i = k(k+1)/2 + k + 1

che riorganizzando il secondo membro, è proprio: ∑_i=1^k+1 i = (k+1)(k+2)/2

Il principio di induzione, introduce a questo punto ci permette di concludere che è vera la proposizione ∀ n: "per ogni n ∈ N - {0}, P(n), ossia per ogni n ∈ N - {0} la somma dei primi n numeri naturali positivi è uguale a n(n+1)/2.

ALTRO ESERCIZIO:

Dato un numero intero positivo m, la somma dei primi m numeri dispari è m².

Posiamo effettuare una piccola dimostrazione senza usare il metodo del principio di induzione. Ovvero, ponendo un ragionamento sulle figure:

(Il quadrato di lato 4 è ottenuto sommando quello di lato 3 con 4, ed è quindi la somma dei primi 4 numeri dispari. così si somma dei primi 4 numeri dispari): 1+3+5+7.

Un quadrato di lato dispari m può essere ottenuto sommando un "anello" di area dispari, rappresentante es 9, 15, 21,...

Poi dimostrare anche questo con induzione per induzione avere preso P(m) scriviamo: P(m): ∑_i=0^m-1 (2i+1) = m²

Passo base:

Si verifica subito che P(1) è vera visto che si ottiene nell’uguaglianza 1 = 1.

Passo induttivo:

Sia k ≥ 1 un intero. Dobbiamo dimostrare che è vera l’implicazione

∑_i=0^k-1 (2i+1) = k² ⟶ ∑_i=0^k (2i+1) = (k+1)²

Scriviamo ∑_i=0^k (2i+1) spezzando la somma così:

∑_i=0^k (2i+1) = ( ∑_i=0^k-1 (2i+1) ) + (2k+1)

Ma l’ipotesi induttiva ci permette di sostituire il suo valore k².

Otteniamo:

∑_i=1^k+1 i² = (k+1)²

Progressione aritmetica

Diciamo che una successione di numeri reali a₀, a₁, …, a_n è una progressione aritmetica, se le differenze a_i - a_i-1 sono tutte uguali tra loro (chiamiamo una simile uguaglianza differenza costante e il numero a). Per generare una progressione aritmetica si può scrivere in modo che, per ogni u ∈ ℕ, a_i = a + ib per certi numeri reali fissati a e b.

Quanto vale ∑_i=0^u (a_i + b) ?

Possiamo scrivere:

∑_i=0^u (a_i + b) = a ( ∑_i=0^u i ) - ∑_i=0^u b = a (u (u+1)/2) - (u+1) b

Se in un problema capita di incontrare una sommatoria che non parte da 1 o da 0, si può sempre riscrivere, se conviene, le cose come sopra partendo da 0.

(Vedi esempio svolto)

Progressione geometrica

Diciamo che una successione di numeri b₀, b₁, …, b_n è una progressione geometrica se il rapporto b_i / b_i-1 sono tutti uguali tra loro.

Chiamiamo questo rapporto il numero k. Per generare una progressione geometrica si può scrivere in modo che, per ogni u ∈ ℕ, b_i = c kⁱ per certi numeri reali fissati c e k.

Quanto vale ∑_i=0^u ckⁱ ?

Possiamo rispondere osservando che ∑_i=0^u ckⁱ = c ( ∑_i=0^u kⁱ ).

Se k = 1 otteniamo la progressione aritmetica; se k ≠ 1 possiamo riscrivere la somma in una relazione una specie di relazione ricorsiva in modo da ottenere f(k, u+1).

Se invece k ≠ 1, possiamo partire considerando

(a + a k + a k² + … + l kⁿ)(k-1).

Sviluppando il calcolo vediamo che molti termini si cancellano e otteniamo k^u+1 - 1.