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. In matematica una costante viene di solito indicata come una variabile. 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 e l'elemento neutro)

ℚ = {^m/_n, m ∈ ℤ, n ∈ ℤ, n>0} "lanci/^m/_n, ... " "è razionale!" ℝ = {definizione e intersezione mi seguono} ℂ= {a + ib, a, b ∈ ℝ}

dove i² = -1

Esiste l'insieme vuoto. Ovvero l'insieme che non presenta alcuni elementi. E indicato 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 la si usa nel caso in cui l'insieme A è contenuto in B.

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

Si indica con:

A ⊆ B

Ogni insieme ha almeno un sottoinsieme.

Ogni insieme infatti ha almeno come sottoinsieme { } insieme vuoto

Quindi, tornando ai due insiemi A e B, A è un sottoinsieme di B se ogni elemento di A appartiene a B.

Si scrive così:

∀ x∈A ⟶ x∈B

Facciamo un esempio

se 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 i un solo elemento è sempre zero

Sarà per forza scontato 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 elencarli bisogna definire la cordialità di B.

Essa si scrive come:

|B| = 4

oppure:

# B = 4

A^C

sta per complementare

Quindi:

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

Esempio:

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

Il complementare di B lo otteniao come:

B^C = {n ∈ IN | n ∉ B } = {n ∈ IN | n > 4 }

LEGGI DISTRIBUTIVE

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

LEGGI DI DEMORGAN

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

Dimostrazione 1

x ∈ A ∩ (B ∪ C)

=> x ∈ A ∧ x ∈ B ∪ C

=> x ∈ A ∧ (x ∈ B oppure x ∈ C) x ∈ B => x ∈ A ∩ B

se ho

x ∈ C => x ∈ A ∩ C

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

Disegno:

PASSO INDUTTIVO

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

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

Per fare questa dimostrazione, cioè, se assumiamo vera la nostra ipotesi, ossia:

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

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

Scriviamo ∑_i=1^k+1 i spezzando la somma così:

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

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

Otteniamo:

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

Che riscrivendo il secondo membro, è proprio:

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

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

ALTRO ESERCIZIO

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

Possiamo effettuare un'altra dimostrazione sulla base del metodo del principio di induzione.

Ovvero, facendo un ragionamento sulla figura:

Il quadrato di lato 4 e area 4² si ottiene sommando i "canini" di questo quadrato. In questo caso, si somma dei primi 4 numeri dispari.

1 + 3 + 5 + 7.

Un quadrato di lato n ed area n² si ottiene estendendo il quadrato di n/area dispari, partendo da -3, 5, 1, 3, 5,...2n-1

Proponiamo anche in questo caso una dimostrazione per induzione.

Proposizione: per ogni n∈ ℕ - {0}, P(n), P(n) è:

P(n): ∑_i=0^n-1 (2i+1) = n²