Logica e matematica discreta - Appunti

Principi Induzione sugli Interi

(sono 3 equivalenti)

1. Mo ∈ Z [P(mo) & ∀x > mo (P(x) ⇒ P(x+1))] ⇒ ∀m > mo P(m)

2. Mo ∈ Z [P(mo) & ∀N > mo (∀z ∈ [Mo, N] P(z) ⇒ P(y))] ⇒ ∀m > mo P(m)

3. Mo ∈ Z [(P(mo) & ∀x > mo (P(x-1) ⇒ P(x))] ⇒ ∀m > mo P(m)

Dimostrazione:

∀m > 3 m² > 2m + 1

base m=3 3² + 2 . 3 + 1 ⇒ > 7 ok induzione m > 3 (m+1)² = m² + 1 + 2m > (2m+1) + 1 + 2m ⇒ 7 + 2m + 1= 8 + 2m > 2(m+1) + 1

Ultra proprietà su induzione

• 6: N - N
• ϕ ∉ ϵ(n)
• 6 ϵ moltiplica
• 6(N)= N-ϕ
• P(m)= ∃x. m = x+1 + ∀m > 0

Base m 1=x+1 ⇒ x=0 ok induzione P(m) = ∃x. m=x+1 dimostrato per m+1 cioè: 3 ∀. m+1 = 4+1 A/X. tale che ∀ a, b ∈ X

PARTIZIONE NOTEVOLE

f: A -> B

a₁ ~ a₂ f(a₁) = f(a₂)

Posso definire una partizione come immagine inversa della funzione

RELAZIONE EQUIVALENZA ≡ PARTIZIONE

QUANTI ELEMENTI CI SONO IN UN INSIEME ?

Dato A quanti elementi sono in A

caso A finito : posso rispondere precisamente

caso A infinito : posso dire quando 2 insiemi hanno lo stesso numero di elementi

ESEMPIO

{1, 2, 3, 4,..., 2} ⊆ N = A |A| = 3 cardinalità (x insiemi finti c è numero element)

P ⊆ N P è un numero pari |P|=|N|

ESEMPIO

• Q ℝ N |A|
• |Q| = |N|
• |R| > |Q|
• |P(N)| > |N|
• |P(N)| = |R|

INSIEME FINITO : (def mutua) : insieme ai cui elementi si possono contare

c’è è risultato di un numero naturale

∪m ∈ N I_m = |n| o ≤ m ≤ n₊₁ questi insiemi qui vengono chiamati

segmenti limitati di numeri naturali

1 = {o}

1_-1 = {}

I₂ = {o, 1}

Sono compagni degli insiemi finti |I_m+1|= m

A, B sono equipalenti ognuno hanno la stessa cardinalità: |A|= |B|

se é solo se ∃f: A -> B biunivoca

DEFINIZIONE: A è finito se e solo se esiste un numero naturale m

tale che A è equipallente a I_m

∃M∈N |A|= |I_m|

|Im f| = |A|

∃ f: Im → A

f(o) = a ∈ A

f(o) = ⊘ ⊆ A

f(m-1) = 2^m-1 ∈ A

|A| = m

INSIETE INFINITO:

un insieme A è infinito se e solo se non è finito.

non esiste m ∈ f: f: Im → A

INSIETE NUMERABILE:

un insieme è numerabile se esiste una funzione f

t.c. f: N → A bionieca

PROPRIETA INSIETE FINITI:

• A insieme finito ⇔ ∃ f: A → A
• f è iniettivo ⇔ f è suriettiva ← dimostro → cosa

Esercizio: f nouuso f: N → N nessun nouo suriettwo: f(m) = 2M

tourec f: N → N sostitwo maom mineitwo:

f(q(o)) = o f(g(m))M-1 M>o

A ∩ B = φ ⇒ |A∪B|= |A|+|B|

In generale |A∪B| = |A| + |B| - |A∩B|

|A|+|B| = |A|+|B| + |A∩B|

|A×B| = |A|. |B| A×B = U a∈A B 1|f: X→B| = |B|/1

|B|/.|b|./ 1|B|...

|A|. 1oet. . |A|. |B|

COROLLARIO

|A|^M = A×A_{M volte} = |A|^M

ESERCIZIO

|P(A)| = 2^|A| autovsgo po macicovsso sv A

base A = φ

P(φ) = {φ} 1 ⇒ 2^o = 1 dvs ok

indivenos A=M+1 |P(m)| = 2^M⇔

P(M+1) = |P(m)| +M = 2^M x M = 2^M+1

DEFINIZIONE

A^m = f(a₁,(a₂),...| a₁,...,a_m ∈ A

f(a₁),(a₂), b}: ce∩ x

c∩a c∩b => b∩c

PERMUTAZIONI

Da una sequenza ordinata di elementi non è altro che uno scambio di elementi qui faccio un esempio:

esempio A={a, b, c}

(c b a)

(b a c)

f: I_m → I_m

f: I_m → A

(i₀, ..., i_m-1) _t

(j₀, ..., j_m-1) _t

(a₀, ..., a_m-1)

→ applico f (per esempio f funzionava per mettere 6 pacchetti → dunque fa 5 scelte)

COEFFICIENTI BINOMIALI

\(\binom{M}{K} = \frac{M!}{K! (M-K)!} \)

\(\binom{M-1}{K-1} + \binom{M-1}{K} = \binom{M}{K} \) ← proprietà importante

# elementi _i=1 ^m ∑i = \(\frac{M(M+1)}{2} \)

← triangolo di Tartaglia

\(\binom{M}{0} = 1 \)

\(\binom{M}{M} = 1 \)

1° APPLICAZIONE COEFF. BINOMIALI SUI BINOMI

Devo scomporre (x+4)^M

(x+y)⁴ = x + 4

(x+y)² = x² + 2x4y + 4²

(x+4)³ = x³ + 3x24 + 3x4² + 4³

\(\to \) (x+4)^M = \(\sum_{k=0}^{M} \binom{M}{K} x^{M-K} 4^K \)

∀m≥1:

2° APPLICAZIONE COEFF. BINOMIALI

|A| = M → 1≤ |x|≤A x|=k| | = \(\binom{n}{k} \)

Quanti sono i "sottosuccessi" di k elementi su n elementi?

Corollario

Q^e è numerabile

Q ⊆ ×

Q è infinito può contenere comunque tutti gli elementi { (m, 1) | m ∈ }

Q è numerabile ⟹ Q ≅ × | N ≠ Q

φ : → (m, m') = [ m, m' ]

≅ quattro volte 2

Importante (come non farelo)

|A| = |B|

|A| ≤ |B| ⟹ φ : A → B ¡iniettiva

φ e φ⁻¹ sono cicli di tutte

Antisimmetria: x ≤ y & y ≤ x ⟹ x = y

Ordinamenti

• 1. Riflessivita
• 2. Transitiva
• 3. Antisimmetria

Ordine Parziale

€ ≤ × A × A

una relazione d'ordine parziale gode di:

• 1. Riflessività ∀a ∈ A a ≤ a
• 2. Transitività ∀a, b, c ∈ A ≤ b ∧ b ≤ c ⟹ a ≤ c
• 3. Antisimmetria ∀a, b ∈ A ≤ b ∧ b ≤ a ⟹ a = b

Esercizio

≤ ⊆ × ==> m ≤ m' <==> ∃p. m + p = m'

Riflessiva m = m

m = m' ==> ∃p m = o ⇒ p = o

Profe: M × M ≡ M m/o = M

Considero * (naturali positivi > 0)

m/la N ⊆ Z

ESISTE UN NUMERO CHE NON E' NATURALE∃ x . ¬N(x) ≡ ∃ x . ¬N(x)

OGNI NUMERO NATURALE RAGGIUNGE DI 1 E SOMMA DI 4 NUMERI NATURALI > 0∀x . (N(x) ⟹ ∃ y . (⊕ (41)) -- o x)

FUNZIONE COSTA LENGTH A PEZZINI

ℓ: T → ℕ

• ℓ(c) = 1
• ℓ(x) = 1
• ℓ(Pm(t₁ , ... , tₘ)) = 3m+1 × ℓ (t₁) + ... + ℓ(tₘ)
• ℓ(Pm(t₁ , ... , tₘ)) = 1 _ℓ× (ℓ(t₁), ..., ℓ(tₘ))

SCOPING E VISIBILITA

(∀x . (p(x) ⟹ q(z)) ∧ R(x, z))

SOTTOPORZIA

SF(I) = I

• SF(P(t₁, ..., tₘ)) = P(t₁, ..., tₘ)
• SF(A → B) = {λ x . B | ₓ ₋ SF(A) = SF(B)}
• SF(∀x . A) = {∀ x . A ₓ ₒ SF (A)}

VARIABILI LIBERI E LEGATE

F(LIE E BOUNDED)

ESEMPIO A. (∀ x. (p(x) ⟹ P(z))) ∨ (∃ z. (q(z) ∨ p(x)))

↓ ↓ ↓ ↓ ↓ ↓

(F B F B B F)

occupate di variabili

Dalla una forma A una variabile x è un occorronza di x in A si dice che l'accortezza è x in A è legale se x occorre in una sottaformula della forma yx, B di A

FV(A) è l'insieme delle variabili che hanno davvero un accadeenza libera

FV(A) = {λ x . I

Un accadimento di una variabile è libera se non è legato

• FV(c) = ∅ se c è una costante
• FV(x) = {x} (accetta di variabile libera per i nomi)
• FV(f(t₁, ..., tₘ)) = FV(t₁) ∪ ... ∪ FV(tₘ)
• FV(⊥) = ∅
• FV(t₁ = t₂) = FV(t₁) ∪ ... ∪ FV(tₘ) (accetta di variabile libera per funzioni)
• FV(A → B) = FV(A) ∪ FV(B) Def-e,∨,¬,∀,∄
• FV(∀ x . A) = FV(A) − {x} (regolo di scoping)

Le regole di scoping assumono per la sostituzione

B = A[t/x]

B = A con la formula ottentua rimpiazzando tutte le occorrenze della variabile

con il termine t

ESEMPIO

A = (p(x) → (∃ x (p(x))))

A[t1/x] = (p(f(q₁)) → (∃ x (p(x))))

A[t₂/x] = (p(y) → (∃ x (p(x)))

A[t₃/x] = (p(y) → (∃ x(p(x))))

ESEMPIO

∀ x. (p(x) → q(x))

A[t/x] = ∀ x. (p(x) → (∃ x (p(x))))

t = f(x)

LA SOSTITUZIONE DEVE PRESERVARE LA VERITÀ DELLA FORMULA

PRINCIPIO FONDAMENTALE

(∀ x. A) → A [t/x]

REGOLE DI SOSTITUZIONE PER TERMINI

t.c[u/x] = c

x[u/x] = u

z[u/x] = z z ≠ x

f(t₁ ,...,t_n)[u/x] = f(t₁[u/x],...,t_n[u/x])

Le variabile proprie non hanno identità propria

f(f(x),...,f(y)) ≡ f(A) ≡ g(f(x),...) (sono lo stesso interpretab)

f(f(u1,...,ui,f((m+1),...,f(n),t(f(x,y)),f(return yi, return yj)

REGOLE DI SOSTITUZIONE PER FUNZIONI

P(t₁,...,t_n)[t/x] = P(t₁[t/x],...,t_n[t/t])

(∀ x A)(t/x) = (∀ x (A)[t/x])

Avremo allora che il termine (∀ x A) ha diverse occorrenze libere

(∀ x A) (t/x) = (∀ z (AT[t/x]][z/x]) se x ≠ y ∧ y ∉ FV(t) ∧ y ∉ FV(a)

(∀ x,t,z,b) f = < (A [u/z])[t/a] = (∀ x (∃ z A/τ)[u/x])[t/a]

Complesso e automicità con CPSH

ESEMPIO

A = ((∃ x. p) ∨ (∃ y. q(x,f(x))))

A [t/x,u='false'] = ((∀ x t (p(z, x) t)[z/x]) ∨ (∃ y. q (u,f(y,x)))[x/y])

Cosa si lueggisce questo con le formule dove dove non è consentivo

(osservanza indutto di semantica apposizionata)

SEMANTICA LOGICA 1^a ORDINE

< A, R < R> struttura

< N, S < N> struttura N

τ, R', π, ϕ , R, o ' s struttura R

STRUTTURA

In generale una struttura è formata da:

<D, c_i^D, f_m^D, r_s^D> (p. e) <i∈I, r^sD <e, j>>

• dove: costanti
• funzioni
• relazioni

Le strutture sono base di assi, le semantica degli oggetti del primo ordine

LINGUAGGIO

L =<c₁, c₂, ...., f_m, P_r, ....>

• costanti funzioni predicati

ASSEGNAZIONE/INTERPRETAZIONE

A =<D, J>

• dominio assegnamento

1. D ≠
2. ∀ costante c J(c)∈D
3. ∀ f^m J(f): D^m→D
4. ∀ P^m J(e)⊆D^m

STRUTTURA x FISSA una struttura A =<D, J> le variabili libere x come |s interpreto

AMBIENTE

A luogo composizione intorno [esempio del valore...

Se VAR – D es una funzione ↔ g variabili corrette

SEMANTICA PER I TERMINI

Dato un termine t e un ambiente g

[t_{A, g}] è il valore del termine t nell'ambiente g è dato da

[c_{A, g}]=J(c)

[x_{A, g}]=g(x)

f(t₁, ..., t_m)_{A, g}=J(f)([t₁] _{A, g}..., [t_m]_{A, g})

=J(f)([t₁] _{A, g}..., [t_m]_{A, g})

La copia <A | g> preude le nome di interpretazione

SEMANTICA DELLE FORME

Data una formula F e un ambiente g ν: FBF × ENV → {01}, ν(A)g ≡ ν (A, g) ν(J)g=0

ν(p(t₁, ..., t_m))≡ ν(p)^A

ν(((A), B))≡1 ↔ ν(A)g=e ν(B)g=1

ν((A∧B))g=1 ↔ ν(A)g=1 ν(B)g=1

ν(¬A)g=1 ↔ νA g) ≠ 1

ν((A))g=1 ↔ ν(A)g=1

ν(∀x. A) g ≡1 ↔ αm ∼ condivisio β

ν(A)g_x/m=1

ν(A)g ≡ ν A∪B ↔ ∌

• A
• B

e valido se solo se per ogni struttura A 上 B (β)↩️ e valido