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

no

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 m

a ≡ 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 → Z

Z = N ∪ -{m con m ∈ N}

(m, m) → 0(n, n)

PROPRIETA

1. m = m₁ q + r
2. m ≥ r/mq
3. 0 ≤ r < m
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 disjunte

Siano a ∈ A e b ∈ b elementi di A tali che a2 = b2 → bKa

Dobbiamo allora dimostrare che a e b sono disjunte, cioè che

a ∩ b = ∅

Lo dimostro per assurdo ammetendo che a ∩ b ≠ { }

c ∈ a e c ∈ b, quindi cRa e cRb e a l e c e b l e c a

e a dimostrarlo b

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

Si: 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 propretà

• A ⊂ Si, S2, S3,

relazioni di A?

Pero dimostriamo per assurdo

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₈=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:

• SECONDO: CONVIARE IN BASE 5 IL NUMERO 746
• VALUTIAMO IN BASE 10
• 5₄*8, 5₃1, 5², 5¹, 5⁰
• 12491
• 546
• 580
• 10
• 5⁵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, maogni 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 prevedete
2. propriendeu inde
3. Dmmsel 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 + 2

m + 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.

PROPRIETA

a ∈ N e b ∈ Na > b

• PROPRIETA RIFLESSIVAper ogni m ∈ N m ≥ m
• PROPRIETA TRANSITIVAse m ≥ k e m ≥ k allora m ≥ k
• PROPRIETA ANTISIMMETRICAse m ≥ m e m ≤ m allora m = m

PRINCIPIO DEL TERZO ESCLUSOper ogni coppia di numeri m, m o m ≥ m o m ≤ mⓘ sostituite con o minore se l'insieme di m contiene o di almenodue elementi numeri minimo che è l'elemento più piccoloesempio:

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| < |B|

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

(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}

è verificata

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

PROPRIETA

• 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

CARDINALITA

|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 < 21} = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}

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}