Appunti di Informatica

APPUNTI DI INFORMATICA

UNIVERSITÀ DI TRENTO

PROF. ROBERTO ZUNINO

CORSO DI LAUREA IN MATEMATICA

RICCARDO TOSI

NOTAZIONE LOGICA

• ∨: ∨ / or / p ∨ q = p oppure q
• ∧: ∧ / and / p ∧ q = p e q
• ¬: ¬ / not / ¬p = non p
• →: → / implies / p → q = p implica q

Una formula dimostrabile è detta TEOREMA

Durante una dimostrazione:

• 1: inserire formule dette ipotesi (già conosciute come valide)
• 2: formula detta TESI
• Regola BASE ↔ t.e.f. dimostrazione finita (t vero per ipotesi)

Regole logiche di:

• I: Introduzione: dimostrazione di un connettivo nella tesi
• E: Eliminazione: sfruttare un connettivo noto

AND INTRODUZIONE

p ∧ q: nella tesi si scinde la dimostrazione in due:

• / tesi p → q / tesi q
• / tesi p ∧ q

AND ELIMINAZIONE

p ∧ q: nell’ipotesi: si aggiungono due tesi, p e q

• / tesi ¬p + q → tesi q

Esempio:

IP1: p ∧ (q ∧ r)

• tesi: q ∧ r
• a) Eliminazione
• IP2: p
• IP3: q ∧ r
• IP4: q
• IP5: r
• b) Eliminazione
• c) Introduzione
• IP5: x
• x ∧ p
• p

1) Regola base.

• IP5
• IP2
• R.T.
• 1)

OR: INTRODUZIONE

1. Si sceglie arbitrariamente una proposizione

IP: p

oppure

ten: p

ten: p

Se p non si dimostra si prova con q

OR: ELIMINAZIONE

1. Si riporta la dimostrazione, aggiungendo come ipotesi p₁ o altra q. Se entrambi i rami sono corretti allora la dimostrazione è vera.

Esempio:

• IP: p ∨ q
• IP₁: p
• ten: q ∨ p

Introducendo la ten:

IP₂: q

Eliminando l'IP₁:

• ten: q
• ten: q
• ten: q
• ten: q ✓
• ton: ✓
• isomma: OR è COMMUTATIVO

IMPLICA: INTRODUZIONE

1. Si assume p₁ per vera e la si assume tra le ipotesi

IP: q

ten:

IMPLICA: ELIMINAZIONE

1. Primo si dimostra, p, poi si assume l'ipotesi q

IP: p ⇒ q

Elimina:

Esempio:

(p): q ⇒ n

• IP: p
• IP: q ⇒ n
• ten: y

IP₁: (q)

• ten: q ⇒ n
• p: (q)
• ✓

SE E SOLO SE

IP₁: (p ∧ x) ⇒ n

• ten: r
• ten: q ¬ n

SE:

• IP₁:
• p ∧ x ⇒ n

• ten:

VERO - INTRODUZIONE

ten vero − Fine della dimostrazione

VERO - ELIMINAZIONE

1. Non esiste un ipotesi che dice vero è finita

Esempio

¬p ∧ p ⇒ vero

• IP₁: ¬p
• IP₂: p
• IP₃: vero

BASE

• p
• ⇒

Vero ⇒ ¬p

Ció dimostra che vero è l'elemento neutro di ∧

- Altre due proprietà:

_y^ε(p_x) ⇒ vero _∃x^ε(p_x) ⇒ falso

Si può riscrivere come

p(y)_z (∀z (q(z,y,z))) ⇒ r(x,y,z)

Poiché:

a ∧ b ⇒ c ↔ a ⇒ (b ⇒ c)

∀x,y,z p(x,y) (a ∧ b ⇒ c) ⇒ r(x,y,z)

E poiché p(x,y) non dipende da z, si può portare dietro:

∀x,y [p(x,y) ∧ ∀z (q(z,y,z) ⇒ r(x,y,z))]

Ovvero quando se non più variabili:

∀x,y φ(x,y) ⇒ (ψ ∧ … ∧ φ(x,y)) ⇒ …

∀x γ(x) ⇒ (∀y_x (γ(x) ∧ …)) ⇒ …

INSIEMISTICA

• Appartenenza: a ∈ x |= p(x) ⇒ p(a)

• a appartiene ad un insieme x se solo se vale p(a)

• Estensionalità:

∀x (x ∈ a ⇔ x ∈ b) ⇔ A = B

(A e B sono uguali se hanno gli stessi elementi)

Operazioni:

• A ∩ B = {x | x ∈ A ∧ x ∈ B}

• A ∩ B = A \ B

• A \ B = {x | x ∈ A ∧ ¬(x ∈ B)}

Insieme vuoto: {x | x ≠ x} = ∅ Singoletto: {x_a} = {x | x = a}

Insieme enumerato: {a₁, a₂ …}_n = {x | x = a₁ ∨ x = a₂ ∨ x = a_n}

L’insieme non contiene costantemente n elementi poiché gli elementi possono compartli:

Appartenenza: si può combinare con i quantificatori

∀x_a. p(x) ⇒ (∃x. x∈A ∧ p(x))

[∃x∈A p(x)] ⇔ (∃x. x∈A ∧ p(x))

∃ ∈ {a,b} ⇔ {x | x=x} ∧ x ∈ A ⇔ a ∈ A

{{ ∃(a) . a ∈ A } ⇔ (∃x | x ∉ A) ⇔ a ∉ A

Per la contrapposizione a ∉ A ⇔ ¬a ∉ A

Sottrazione: A < B ⇔ x ∉ A ∈ x ∈ B

Insieme degli aperti: P(A) = {B ⊆ A | B ⊆ A}

Uno è definito “insieme di insiemi” = famiglia di insiemi.

UNIONE GENERALIZZATA:

Unione di insiemi X, X ⊆ Y

∪Y { x | ∃X. X ⊆ Y ∧ x ∈ X } ⇔ cioè l’unione comprende i punti che appartengono ad un insieme che appare alla famiglia!

Nota: A ∪ B = ∪{A,B}. Altre volte vi utilizzato la notazione con indici U_α=∪{A₁, i ∈ I}

Programmazione

Def: Siano input e output insiemi.

• Una specifica è una funzione da input ad output che si desidera calcolare automaticamente.

Algoritmo: descrizione di un processo automatico che associ ad ogni input una sequenza finita di passi di calcolo per avere un output (gli algoritmi che risolvono varie specifiche non sono unici).

Un linguaggio formale è un insieme finito di stringhe (sequenze finite di simboli). La programmazione usa i linguaggi affinché gli elementi detti programmi indichino una specifica particolare.

Sintassi: descrive quali stringhe appartengono ad un linguaggio.

Semantica: descrizione che associa ad ogni stringa il suo significato (ciò che un programma fa).

Paradigmi di programmazione

• funzionale
• imperativo
• logico

IMP

_{IMP = sottoinsieme di Java}

Espressioni di IMP

Si indichi con Var un insieme di nomi di variabili.

Nel linguaggio IMP le variabili ∈ Var e non vi sono limiti di cifre.

Funzione stato associa ad ogni variabile il suo valore: σ: State_{Var -> Z} σ(x) valore di x

La sintassi contiene espressioni aritmetiche: (definite ricorsivamente)

• z∈Z (z var) e.g. e_{1} + e_{2}, e_{1} - e_{2}, 2*e_{1}, e_{1}/e_{2} ...

Per dim che ∀ e ∈ Exp prec) basta che:

1. ∀ z ∈ Z, pf(z)
2. ∀ x ∈ Var, pf(x)
3. ∀ e1, e2 ∈ Exp, pf(e1) ∧ pf(e2) → pf(e1 + e2)

Semantica delle espressioni, relazione --> che ancora ad ogni espressione e ∈ Exp e ad ogni stato σ il valore di e:

(σ, e) --> v ∈ Z se (⟦e⟧ Exp State x Z) ⇔ 1. (σ, z) --> z

Esempio: (x+ y) / (x - y) , se x>1 or x(σ) = 2 or y = 5

NB: un'espressione non ha alcun valore se non gli è stato associato uno stato.

Semantica delle espressioni

_{(σ, z) --> z ⇔ ⟦z⟧σ = z e q,}

(σ, x) --> σ(x) ⇔ ⟦x⟧σ = σ(x)

(σ, e1 + e2) --> z1 + z2 ⇔ (σ, e1) --> z1 ∧ (σ, e2) --> z2 ⇔ ⟦e1 + e2⟧σ = ⟦e1⟧σ + ⟦e2⟧σ, ecc...

^[Plan]

Per dim che ∀ σ (σ, e) --> v ; < (σ', x) = v/q.⟦e⟧σ = v basta che

1. ∀ z ∈ Z, σ(z) = z
2. ∀ x ∈ Var, σ(x) = σ(x)
3. ∀ e1, e2 ∈ Exp, (σ, e1) --> z1 ∧ (σ, e2) --> z2

RT