Istituzioni di matematica - Appunti

Transitiva su

aRb e bRc

aRc

a: m = q₁ + r₁

b: m = q₁ + r₂

c: m = q₁ + r₃

r₁ = r₃ = b

Antisimmetrica no

a R b

b R a

a = b

a: m = q + r₁

b: m = q + r₂

r₁ = r₂

a = b

ed è relazione di equivalenza, l'insieme Z questa relazione modulo si pone di congruenza modulo m

a ≡ b mod-m

Esempi di congruenza mod-2 e classi di resto

a ≡ b mod-2

4 ≡ 6 mod 2

7 ≡ 29 mod 2

9 ≡ 43 mod 2

10 ≡ 12 mod 2

21 ≡ 25 mod 2

Congruenza mod 5

Classi di resto 0, 1, 2, 3, 4

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, -2, 7 ....}

4 - {4, 5, 14, -1, 6 ....}

Z_m = {0, 1, 2, 3, ....}

47 : 7 = 6

prob. 6*7 = 42

<47

47 : 7 = 6 (5)

0<5<7 ok!

-47 : 7 = -6

poco -7 (7) = -48

<47

47 : 7 = 7 (2)

0<2<7 ok!

-47 : (-7) = -6

poco -6 (7) = 42

<47

47 : (-7) = -6 (5)

0<5. : (-7)

0<5<7 ok

-47: (-7) = 7

poco (7) 7 = -48

<47

47 : (7) = 7 (2)

0<2 < (- 7)

0< 2< 7 ok!

Le Congruenze in ℤ

• aRb (a, b ∈ ℤ) e esiste a, b, con lo stesso resto

• a ≡ b (mod m) ∃ m ∈ ℕ

• a : m = q + x

  a = mq + x

  b : m = q + x

  b = mq + x

Riflessiva ∀

a ∈ ℤ

a = mq + x

a = mq + x

x = x

Simmetrica ∀

arb

bRa

a : m = q + x₁

a = mq + x₁

b : m = q + x₂

b = mq₁ + x₂

x₁ = x₂

x₂ = x₁

aRb

bRa

A₁ = {0,3,5} ø = {0}

A₃ = {1,2,3,4} {1,2,3,4}

INSIEME QUOIENTE (PA)

R = {A₁, A₂, A₃, A₄, A₅}

A = {0,3,5} ; R è la relazione binaria definita su A tale che aRb se e solo se a+b è un numero pari. Come R?

0+0 = 0 pari

3+3 = 6 pari

5+5 = 10 pari

Im francese aRa per ogni a ∈ A ; a+a = 2a pari

0∈3 = 3 dispari

0∈5 = 5 dispari

3∈5 = 8 pari

Im francese aRb = bRa = a+b = b+a pari

3+5 = 8 pari

3+3 = 6 pari

Im francese a+b = b+a pari e b+c pari → a+2b+c pari

R è UNA RELAZIONE DI EQUIVALENZA

CLASSI DI EQUIVALENZA : 0, 3 (∈5)

INSIEME QUOIENTE A R = {0, 3}

{0, 3}

Trasformare in base 4 il numero 123₁₀

1 | 123₁₀ 4 | 30 - 3 4 | 7 - 2 4 | 1 - 1 0

3 × 4⁰ + 2 × 4¹ + 1 × 4² 123₁₀ = 3 × 4⁰ + 2 × 4¹ + 1 × 4² = 2 + 8 + 12 = 20 + 2 + 1^x 1103₄

Trovare le cifre x base 4 di 3x² + 1x = 103_x

3x² = 41x = 103_x

3x² = 2x + 3x¹ 1x¹ = 1x⁰ + 1x¹ 103_x = 3x⁰ + 0x¹ + 1x²

2x⁰ + 3x + x⁰ × x = 3x⁰ + x² 3/ +4 x = 3x +x²

x = 4;

2 × x = x² 4 − x² = x

PROVA

3¹ + 2¹ + 01123 11¹57

1103_x

Dire se l'affermaz_me come è vero o falso e spieg_ane il perché

Ogni numero che scritto in base 10 finisce per 5 e divisibile per 5: vero

dimostrazione

a b c 5 = 5₁₀ + c×10⁴ + b×10² + a×10₃

e multiplo_d 5₁₀

sono tutti multiplici sono tutti multeplici lascia das₃ multiplo

di 10 è div_lib 5 perche era multiple

CRITERIO DI DIVISIBILITA × 5

togli la' matematiche finiamo per 5 o per 0 sono divisibili per 5

1) OPERAZIONI IN N

f: N x N -> N

(m, n) -> m+n

FUNZIONE SOMMA

.. è una funzione perchè ad ogni coppia di NxN si può associare un elemento di N

... som a ogni coppia (m, n) N si può ottenere un solo elemento di N (proprietà commutativa della somma)

(m, m) -> (m+m)

(m, m) -> (m+m)

....è suriettiva, perchè ogni numero di N può essere visto come la somma di 2 numeri naturali quando gli elementi in e N, nmin, uno di essi

.....è in N x N

2) f: N x N -> N

.... mm -> o min

FUNZIONE PRODOTTO

.. è una funzione

... a ogni m in eN uno in N

.... è suriettiva, perchè ogni numero di N è immagine di almeno una coppia di N x N

3) f: N xN -> N

NON è UNA FUNZIONE

(m,m) -> m-m

..non è una funzione perchè la differenza m N {parti dg

nnel caso in cui m-m -> m-m = m

nnel caso m < m si otterebbe de N esistibili in 2 i non fa

4) f: N x N -> N

non è una funzione ne

(m, m) -> m : m

.. non è una funzione perchè la divisione øøheor in N

è parrebbe quando m : m : m > m e con m ≠ 0 cuo, nel caso in cui ciò non avvenga, a mondelletta in N e anche nelle in ≠ o m Q

Esercizi

1) A = {a,b} B = {c,d,e}

1 . | A x B | = .

1. funzione iniettiva 2 iniettive di P(A), A x 3

1. elementi
• a,b {a,c} {b,e} {a,c}{b,d}
• {a,b}{a,e}
• 2 element {a,b} {b,c}
• 2 elementi
• 3 elementi
• {a,b,c} {a,b,c} {a,b,c} {a,c} {a,c} {b,b}

P(A) = { a {a, b} {b} {c} {ab} {ac} {bc} {a,b,c}

1. 2) A x B = (a,i) (a,i) (b,0) (b,i) (c,0) (c,i)

3) L' fimzione iniettiro ad ogni elemento B corraponde un in elemento di A

|A|/|B|

|A| = 2 = 8 6 parte di . P(A) =

1 x |B| = 3x 2 = 6 [a] A x B {a} {a,b} (b,c) (b,c)

functse i nitt ka ad elementi distinati di A heterispomlon elitni distiroito A.

3) Quante sono le funzioni da A a B tali che:

f(a) = 1, f(b) = 1

₁ ² ₃

a _A b

a _B b

3 - funzioni

ESERCIZIO

A = {a, b, c}

Trovarle tutte le funzioni da A a B |A| = 3 |B| = 2

{h A->B} = 2

a _A b c

X

a _B b 1 2

a _A b c a _B b 1 1

a _A b c a _B b 2 2

a _A b c a _B b 1 2

Sono tutte le funzioni identiche tranne 1

1 |A| = 3 |B| = 2 = 3

a _A b c a _B b 1 2 = 8

a _A b c

b 1 2

b 2 2

b 3 2

b 1 1 b 2 1

b 1 1

b 2 2

(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∉B ⇒ x∈B^c ⇒ x∈(A ∩ B)^c
• x ∈A^c ∪ B^c ⇒ x ∈ A^c
• x ∈ A^c ∪ B^c ⇒ x ∈ B^c ⇒ x ∈ A ∪ B ⇒ x ∈ (A ∩ B)^c

Verifica su esempio

• T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, #}
• A = {1, 2, 3, 4, 5}
• B = {4, 5, 6, 7, 8, #}

⇒ A ⊂ T e B ⊂ T

(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, 9, *, #}
• B^c = {0, 1, 2, 3, 9, *}

A^c ∩ B^c = {0, 9, *}

(A ∪ B)^c = A^c ∩ B^c è verificata