Istituzioni di matematica - Appunti

Transitiva

aRb e bRc
aRc
a: m = q₁ x₁
b: m = q₂ x₂
c: m = q₃ x₃
x₁ = x₃ = aRc

Antisimmetrica

aRb bRa = a = b
a: m = q₁ x₁
b: m = q₁ x₂ = x₂ = x₁ ma a ≠ b

È una relazione di equivalenza fra l'insieme Z, questa relazione prende il nome di congruenza modulo ma ≡ b tro 5 m 10 10 10.

Eserc. 2: Alcuni esempi di congruenza mod 2

Classi del resto

a ≡ b mod 2
a2, b2
a: = q₁ x₁
b: = q₁ x₂
a: = 29 x₁
b: = 29 x₂
x₂ = x₁

4 ≡ 6 mod 2
9 ≡ 2 mod 2
3 ≡ 43 mod 2
10 ≡ 12 mod 2
21 ≡ 4 mod 2
15 ≡ 25 mod 2

Congruenza mod 5

Classi del resto:
mod 5
0: { 0, 5, 10, 15, 20, 25, -5, 10, ... }
1: { 1, 6, 11, 4, 9, ... }
2: { 2, 7, 12, 3, 8, ... }
3: { 3, 8, 13, ... }
4: { 4, 5, 14, 1, 6, ... }
Z/5Z = { 0, 1, 2, 3, 4 } R

L'insieme Z dei numeri interi

(positivi e negativi)

La moltiplicazione e la divisione sono possibili in quanto:
(m, m) → 0
(m - m) oppure (m : m)
oppure m x n ≠ 0 → ZZ = N ∪ -{m con m ∈ N}
(m, m) → 0
(n, n)

Proprietà

1. m = m₁ q + r
2. m ≥ r/mq
3. 0 ≤ r
4. 0 ≤ r m+

Nuovo esempio

32 : 5 = 6 (+2)
-32 : 5 = -6
Prova: -6.5=-30; 32; NO
Prova: -7.5=-35; -32; 32:5=-7 (+3)
ok 3 ⁶ 5 ok!

32:(-5) = -6
Prova: -6.(-5)=+30; 32; 32:(-5)=-6 (+2)
ok 2 ⁵ ok!

-32:(-5) = 6
Prova: 6(-5)=-30; -32 NO
Prova: 7(-5)=-35; -32; -32:(-5)=-7 (3)
ok 3 ¹ 5 ok!

2) Le classi sono a 2 a 2 disgiunte

Siano a ∈ A e b ∈ b elementi di A tali che a2 = b2 → bKa
Dobbiamo allora dimostrare che a e b sono disgiunte, cioè che
a ∩ b = ∅

Lo dimostro per assurdo ammettendo che a ∩ b ≠ { }
c ∈ a e c ∈ b, quindi cRa e cRb e a l e c e b l e c ae a dimostrarlo b.

3) L'unione di tutte le classi di equivalenze di A è uguale ad A

Sì: 1 ∪ S2 ∪ S3 = A
A e _ stato parlato in classi di equivalenza
sempre dimostrazione di A e _ quindi in classi di equivalenza

Per l'altro dato dimostro le 3 proprietà
A ⊂ Si, S2, S3, relazioni di A?
Però dimostriamo per assurdo
Si ⊂ A, Se, A, S2 ⊂ A, S3 ⊂ A sono {}

S1 ≠ ∅, S2 ≠ ∅, S3 ≠ ∅
Si ∪ S2 ∪ S3 = A
S1 ∩ S2 = ∅; S2 ∩ S3 = ∅; Si ∩ S3 = ∅ sono parlezioni di A

Esercizio: obiettivo: riporta i numeri in base dieci

135₈, 83₉, 27₈, 10111₂, 101001₂

Trasformazione in base 10

135₈ 5.8¹+3.8¹+6.8⁰=5.8+3.8+6=418.36=59
83₉=8.9¹+3.9⁺¹=8.9+3.9=27
27₈=7.8¹+2.8⁰=7.16.23
10111₂=1.2⁴+1.2³+1.2²+1.2¹+0.2¹+1.2⁰=1+2+4+8+0.32+1=47
101001₂=1.2⁵+0.2⁴+0.2³+1.2²+0.2¹+0.2⁰+1.2⁰=41

75>59, 47>41, 23>83, 135, 10111, 101001, 59, 570

Secondo: conviare in base 5 il numero 746

Valutiamo in base 10
5₄*8, 5₃1, 5², 5¹, 5⁰
12491546580105⁵43, 5¹4=83
[20, 15, 15]
[580+116, 5=[23, 5*1, 5]
(4*13, 5+),(5.4.5+4]
580=5*116, 116.5=580
580, 5=16
116.15=23 con reg. 1
23, 5=4 con reg. 3
[43.5+3], 5+1.5+2.3
430₁₀

Scrivere i numeri

Vi sono scritture di cifre per i numeri che si assegnano per posizione alla cifra stessa come, valore a seconda della sua posizione:
ad esempio

1. 2 = 2 u
2. 2 0 = 20 u
3. 200 = 200 u
4. 2 0 0 0 = 2.000 u

I numeri romani, per esempio, non sono della scrittura posizionali, ma ogni simbolo mantiene fisso valore a prescindere dalla posizione.
I = 1 u
II = 2 u
VI = 7 u
V = 5
L = 50
C = 100

Scrittura posizionale

Indicare la posizione in base 10

1 9 7 6=1 000 + 9 0 0 + 7 0 + 6 = 1.000 + 9 . 10 0 + 7 . 10 1 + 6 .10 0
POSIZIONE 3 -> 1
POSIZIONE 2 -> 9
POSIZIONE 1 -> 7
POSIZIONE 0 -> 6

In base 2 (codice binario)

1 2 3= 2² è la potenza di 2 più grande, ma minore di 23
2 + 7 = 23
= 2² è la potenza di 2 più grande, ma minore di 7
2² + 2 + 3 = 23
= 2¹ è la potenza di 2 più grande, ma minore di 3
2¹ + 2 + 1 = 23
= 2 0 è la potenza di 2 = 1
2⁰ + 2³ + 2² + 2⁰ = 23

1. Posizione 4 -> C'è
2. Posizione 3 -> No
3. Posizione 2 -> C'è
4. Posizione 1 -> C'è
5. Posizione 0 -> C'è

Esercizi

Dimostrare per induzione che 1³ + 2³ + ... + n³ = (n²(n+1)²)/4

1. n = 0

(0 = (0*(0+1)²)/4)
0 = 0

2. Supponiamo che sia vero per un numero generico
3. Dimostra che vale per m+1

m² + (m+1)²(m+1)³ = ((m+1)²(m+2)²)/4
m² + 4m + 1 = (m² + 4m + 4)

Dimostrare per induzione che 3*5 + 5*7 + ... + (6*m+1*1) = 3*(m + 1)²

1. n = 0

(6*0 + 3 = 3 (0+1)²)
3 = 3

2. Supponiamo che sia vero per un numero generico
3. Dimostrare per m+1

3(m+1)² + (6(m+1) + 3) = 3(m+2)²
3(m+1)² + (6m+6+3) = 3(m+2)²
3(m+1) + (6m+9) = 3(m+2)²
3(m²+2m+1) + (6m+5) = 3(m²+4m+4)
3m²+6m+3+6m+5 = 3m² + 12m + 12
3m² + 12m + 12 = 3m² + 12m + 12
È dimostrato

Dimostrazione per induzione

Siano: N₁ ⊃ N₂
con p.m.: n₁ ⟶ n+1 (successore di n)
0 ⟶ 1
1 ⟶ 2 ecc.
A ⊆ N di matrici d_e A,_enb g(sup)a N,sup di numeri natural
O ∈ A

1. S ∈ N, E A, allora anche il successore k+1 ∈ A. A ⟶ N Teo dell’uno componente
2. Un’affermazione P relativa ai numeri naturali, F(val) poi 0. 0 è V D de V ved per un generico naturai K. allora val per un selezione altra D ved per tutti i numeri naturai.

Procedimento della dimostrazione

1. Vder delic prevedetepropriendeu indeDmmsel avilne

Esercizi

Mostrare per induzione che 0+1+2+..+n=n(m+1)/2 m > 0

1. m=0

0=0/(0+1)
0=0
a punto che sia Ve) per un generico m.smotto ,P_m. = m+1
0+1+2+.. m(m+1)= (m+1) [(m+1)+1]
n(m+1)/2 + n+1 = (m+1)(n+2)/2
m² + m + 2 m + 2 - m² + m + 2m + 3 m + 2 - m² + 3 m + 2
e dimostreta

Dimostrazione di A⊂B

|A|<|B|
esempio
N: insieme dei numeri naturali
P: insieme dei numeri pari
P⊂N
iN→P è una funzione se mettete un numero si ottiene e quindi è iniettiva
N-{2n}iN(i) coincide, quindi |N|=|P|-o anche se P è contenuto in
A⊂B
|A|<|B|

Insieme infinito

Insieme dei pari si può mettere in corrispondenza con N o con un altro insieme pari
esercizio-dimostrare che
A=={1,2,3,4,5} è infinito
f: N→A
m→m²
e iniettiva
e suriettiva

Se queste affermazioni sono vere o false e dimprime il motivo

1) N→B è iniettiva, allora B è infinito VERA
Perché N è is. funzione suriettiva che |B|<|N| perché ad ogni elemento distinto di N corrispondono elementi distiniti di B perché N→α anche B è infinito

2) N→B è suriettiva, allora B è infinito FALSA
Perché N→α e is. funzione suriettiva che ad ogni elemento di B corrispondono almeno un elemento di N finché |N|<|B|. B potrebbe contenere anche un solo elemento in tal caso N

L'insieme infinito N

N è l'insieme dei numeri naturali.
In questo insieme valgono contemporaneamente le seguenti relazioni:

1. Tutti i numeri si possono contare tra essi.
2. Tutti i numeri si possono utilizzare e moltiplicare.
3. I numeri sono infiniti.

Proprietà

a ∈ N e b ∈ N
a > b

Proprietà riflessiva

per ogni m ∈ N m ≥ m

Proprietà transitiva

se m ≥ k e m ≥ k allora m ≥ k

Proprietà antisimmetrica

se m ≥ m e m ≤ m allora m = m

Principio del terzo escluso

per ogni coppia di numeri m, m o m ≥ m o m ≤ m
ⓘ sostituite con o minore se l'insieme di m contiene o di almeno
due elementi numeri minimo che è l'elemento più piccolo

esempio:
A_m = {k ∈ N l'v k > m}
A₁₀₀ = {k ∈ N tale che k > 100} = {101, 102, 103...}

Minimo

2) Prop. 6. Leggi di De Morgan

A^c ∩ B^c = (A ∪ B)^c
(A^c x B)^c ∩ (A x B)^c = [(A^π x B)' ∪ (A^π x B')]^c
(A¹ x B')^π ∩ (A x B')^c = { (0, β), (2, "γ") }

Attenzione

|A x B| = |A| · |B| = |B| |A| = |B x A|

Funzioni

INIEITIVE
|A| f: A → B
SURIEITIVE
|A| > |B|
fi; A → B
BIUNIVOCE
|A| = |B|
fi: A → B

Si dice funzione da A in B una legge che adduce AD OGNI ele mento di A UNO e UNO SOLO elemento di B
A = dominio
B = codomomio
a: pre immagine di b
b = immagine di A

Dimostrazione

(A∧B)^c = A^c∪B^c

DEVO DIMOSTRARE
(A∧B)^c ⊂ A^c∪B^c
A^c∪B^c ⊂ (A∧B)^c

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

Verifica su esempio

I = {0, 1, 2, 3, 4, 5, 6, 7, 8, #}
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8, #}
⇒ A⊂I e B⊂I

(A∪B)^c = A^c∩B^c
A∪B = {1,2,3,4,5,6,7,8,#}
(A∪B)^c = {0, 9}
A^c = {0, 6, 7, 8, #}
B^c = {0, 1, 2, 3, 9}
A^c∩B^c = {0, 9}

È verificato
perché (A∪B)^c = A^c∩B^c

Proprietà

Se A ⊂ B A ∪ A^c = B A ∩ A^c = ∅
Se A ∩ B = ∅ ⇒ A e B sono disgiunti
(A ∩ B) ⊆ A
(A ∩ B) ⊆ B
A ⊆ (A ∪ B)
B ⊆ (A ∪ B)
(A ∩ B) ⊆ A ⊆ A ∪ B ⇒ A ∩ B ⊆ A ∪ B
(A^c)^c = A

Cardinalità

|A| = n° di elementi contenuti in A
Ad esempio
|A| = 3     |B| = 4    Quanti elementi posso avere in A ∪ B e in A ∩ B?

A ∩ B             A ∪ B
0             7
1             6
2             5
3             4

Operazioni tra insiemi

1. Intersezione

T = {Tasti del telefono} = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, *, #}
P = {numeri pari
L'intersezione tra T e P è l'insieme degli elementi che appartengono contemporaneamente a T e a P
T ∩ P
L'intersezione è un sottoinsieme sia di T sia di P e il risultato è comune soltanto tra le due insiemi
T ∩ P ⊆ T e T ∩ P ⊆ P?

2. Unione

Tra A e B è l'insieme costituito da tutti e soli gli elementi che appartengono ad A o a B o ad entrambi.
A ∪ B A unione B
Ad esempio
S = {le linee delle parole sole} = {s, o, l, e}
L = {le linee delle parole luna} = {l, u, n, a}
S ∪ L = {s, o, l, e, u, n, a}
S ∩ L = {l}