Corso Geometria e Combinatoria: Teoria e Guide pratiche

FORMULE DA RICORDARE

• COMBINATORIA
  • Combinazioni semplici: ^mC_k = ^mC_m-k = m!/k!(m-k)!
  • Con ripetizioni: ^m+k-1C_k = (m+k-1)!/k!(m-1)!
  • Disposizioni semplici: ^mP_k = m!/(m-k)!
  • Con ripetizioni: m^k (m: possibilità k: da dove estraggo)
  • Permutazioni semplici: m!
  • Con ripetizioni: m!/m₁!

• SOMMATORIE
  • Σ_q=0ⁿ qⁿ⁺¹ = (qⁿ⁺¹-1)/(q-1)
  • Σα = α(m-m+1)
  • Σ1 = m(m+1)/2

• PRODOTTORIE
  • Π_k=1^m k = m!
  • Πα = α^|I|
  • Π_k∈I α_αk = Σαk

FUNZIONE DI EULERO:φ(m) = mπ^-1(p-1)

UNITÀ: φ(m) - MCD(x,m) = 1

DIVISORI DELLO ◯ -m-1-φ(m)/[◯mod m]

POTENZE IN MODULO m: MCD(base, modulo) = 1 applicabile a φ(m) = 1 mod m

CRITTOGRAFIA

• Decifrare: m = c^d mod m [c messaggio cifrato, d privata, m pubblica]
• Cifrare: c = m^e mod m
• Chiave privata: m = p⋅q
• Chiave pubblica: d = e^-1 mod φ(m) φ(m) = (p-1)(q-1)

COMPLESSI

• Potenze i^m: Resto / 4 dell'esponente
• Modulo: √Re²+Im²
• Divisione: z/◉

logica

• TRACCIARE LA TAVOLA DELLA VERITÀ: decomporre fino ad avere solo proposizioni atomiche.
• TAUTOLOGIA: se le variabili in output e' sempre vero
• CONTRADDIZIONE: se il valore in uscita e' sempre falso
• EQUIVALENZA LOGICA: se due valori di uscita (2+) sono uguali

TIPI DI FUNZIONI:

¬ NOT → Vera se ne uno dei due lo è

∨ OR → Vera se uno dei due lo è

∧ AND → Vera se entrambi lo sono

∨ XOR → Vera se solo uno dei due è vero

a → b: Vera se H e TH sono vera o ne H è falsa.

a ↔ b: Vera se H e TH entrambi vera o entrambi false.

• TRADUZIONI IN ITALIANO: ∀ per ogni ∃ esiste almeno un... poi si valuta la proporzione formita

insiemi

OPERAZIONI SU INSIEMI

• ∪ unione
• ∩ intersezione
• ± Somma/Sottrazione di elementi

• SE SONO ELEMENTI: Si trattano discretamente
• SE SONO INTERVALLI: Si trattano come "linee continue" da cui poi si trattano le eventuali intersezioni.
• SCRIVERE L'INSIEME DELLE PARTI: calcolo l'insieme potenza, cioè l'insieme di tutti i sottoinsiemi. Ricordare di inserire SEMPRE l'insieme vuoto ∅ come elemento. HA 2ⁿ ELEMENTI.
• CALCOLO DI INSIEMI PRODOTTO CARTESIANO: A x B ogni elemento di A va "abbinato" ad ogni elemento di B creando vettori |R².

⊆: contenuto totalmente

SOMMATORIE

• _Σk=0^m q^k = ^{qm+1 - 1}/_{q - 1}
• _Σk=m α = d(m . m+1)

IMPORTANTE!

_Σk=1^m k = ^m(m+1)/₂

DOPPIE: SI SVILUPPA PRIMA QUELLA INTERNA POI L’ESTERNA.

PRODUTTORIE

• _Πk=1^m k = m!
• _Πk∈I α = α^|I|
• _Πk=m α = α^m-n+1
• _Πk∈I α^a_k ⇒ α^Σ_ak ← proprietà delle potenze!

_Πk=m^m k = ^m!/_(m-1)!

Modulo 1

Tavole della verità e legami logici

Connettivi logici:

• ¬ = not
• ∨ = or
• ∧ = and
• ∨̇ = xor (exclusive or)

Implicazione logica

• p → q

Complugazione logica

• p ↔ q

Proprietà

• Commutativa (p ∧ q) ↔ (q ∧ p)
• Associativa (p ∧ q) ∧ r ↔ p ∧ (q ∧ r)
• (p ∧ q) ∧ r ↔ p ∨ (q ∨ r)

Leggi di De Morgan

• ¬(p ∧ q) ↔ (¬p) ∨ (¬q)
• ¬(p ∨ q) ↔ (¬q) ∧ (¬p)

Doppia negazione: ¬ (¬p) ↔ p

Contronominale: (p → q) ↔ (¬q) → (¬p)

• (p → q) ∧ (q → p) ↔ (p ↔ q)

Quantificatori:

• Esistenziale: ∃ esiste almeno un...
• Universale: ∀ per ogni...

In logica possono operare solo su elementi

basi numeriche

= numero di cifre distintē usate per rappresentare i numeri

n ∈ ℤ_>0

b ∈ ℤ_>2

n IN BASE b RISULTA

n = _k=0^mn_kb^k = n₀b⁰ + n₁b¹ + ... + n_mb^m

TEOREMA

m ≥ n m n ∈ ℤ

∃! q, r ∈ ℤ (con 0 < r < n) tale che m = n.q + r

Teorema Binomiale

(a+b)ⁿ = ⁿ∑ _k=0 ⁽ⁿ⁾C_k a^n-k · b^k

Dimostrazione

Si hanno in totale D’, n=2ⁿ monomi al grado n e vanno sommati quelli simili, cioè

C’_n, n = (2-1)ⁿ (n+1) = n+1

Con monomi simili, quante volte compare ognuno? Con monomio al k volte a al grado n, n-k volte b.

P_n,k,n-k = ^n! / k!(n-k)! = ⁽ⁿ⁾C_k

Corollario

∑_k=0⁽ⁿ⁾C_k = 2ⁿ

Dimostro:

a=1

b=1

(1+1)ⁿ = ∑_k=0 ⁽ⁿ⁾C_k 1·1 → 2ⁿ∑_k=0 ⁽ⁿ⁾C_k

Coefficiente Multinomiale

(ⁿC_{k₁,...,kₘ}) = ^n! / k₁! k₂!...kₘ! = ^n! / Π_s=1^mkₛ!

Teorema Multinomiale

(x₁+x₂+...+xₘ)ⁿ = ∑_k₁=0ⁿ∑_k₂=0ⁿ...∑_kₘ=0ⁿ⁽ⁿ⁾C_{k₁,...,kₘ} ∏_i=1^mx_i^k

Congruenziali

_{basate sulle classi resto modulo n}

Classi Resto Modulo n ℤ/nℤ se a e b ∈ ℤ hanno stesso resto dalla divisione per n si indica comea ≡ b (n) "a congruo a b modulo n"a = b + nk = a - b ∈ ℤ : {nk, k ∈ ℤ}

Unità: implica invertibilità. Se ∃ b ∈ ℤ: ab = 1 (n) dove si chiama b inverso moltiplicativo (ℤ/nℤ) insieme

Divisore dello Zero: se a ≠ 0 ∃ b ≠ 0 ∈ ℤ : a·b = 0 mod(n)∄ in ℤ

Operazione ben definita: se non varia la classe resto al variare dei rappresentanti.

Teorema ne ℤ/ℤ a ∈ ℤ/nℤ

• a è invertibile ↔ MCD(a,n) = 1
• a è divisore dello zero ↔ MCD(a,n) > 1

nota: a·b = b ≡ 0 (n) ↔ a ≡ 0 (n) ∨ b ≡ 0 (n) ↔ n è primo!

AC·b ≡ c (n) ∉ ∅ (n) ma: ac·c⁻¹ ≡ bc·c⁻¹ (n) se ∃ c⁻¹

Proprietà

• a ≡ b (n) ⇔ a + c ≡ b + c (n)
• a ≡ b (n) ⇒ ac ≡ bc (n)
• ac ≡ bc (n) ∧ MCD(c,n) = 1 ⇒ a ≡ b (n)
• ax ≡ b (n) ha soluzioni ⇔ MCD(a,n) = b
• ac ≡ bc (n) ∧ d = MCD(c,n) ⇒ a ≡ b (n)
• a ≡ b (n) m | n m∈ℤ ⇒ a ≡ b (m)

a ≡ b (r) ⇒ a ≡ b (MCM(r,s)) fondamentalmente per il sistemidi congruenze multiple

n = a₁d₁ ... aₛ = ∏_i=1^r di MCD(di,aj)=1

a ≡ b (n) ⇒ a ≡ b (ai)

a ≡ b (ds)

sia MCD(a,n) = d | b segue che

ax ≡ b (n) ⟺ a'x ≡ b' (n') a' = ^a/_d, b' = ^b/_d, n' = ⁿ/_d

d = MCD(a, n), x₀ ∈ ℤ soluzione

x = x₀ + ⁿ/_d k k∈ℤ k = 0...d-1