Logica proposizionale e del primo ordine

LOGICA

5 Ottobre 2016

Studia che cos'è la matematica utilizzando la matematica => che cos'è il ragionamento matematico

quali sono gli assiomi necessari per poter dimostrare tutti i teoremi di una data teoria ~ nozione di VERITÀ

1. RISULTATI DI UNITA TEZZA mostrare che ci sono problemi matematici interessanti che non possano essere risolti - Teorema di Gödel
2. RISULTATI POSITIVI La logica matematica è alla base della moderna informatica teorica e ci dà strumenti molto efficaci per classificare i problemi trattabili

✶Formulizzazione ai linguaggi matematici

trasformazione di un'espressione matematica in una stringa di simboli => un calcolatore può poi manipolare questa stringa

Le dimostrazioni consistono in ripetute applicazioni di regole elementari di deduzione

ESEMPIO: ф(x) pari ⟹ ψ(x) è numero naturale ф(x) ⟹ (ψ(x) ⟹ ⊥) ⟹ ψ(x) ⊥

1. modus ponens
2. universalizzazione ∀x ф(x) ⟹ ф(c)
3. Reductio ad absurdum ф(x), !φ(x) ⟹ ⊥

scrivere quelli che sono i teoremi matematici in un linguaggio leggibile alle manipolazioni

Un sistema di assiomi individua una classe di strutture matematiche

ESEMPIO (Z, +) ⊨ φ _E ∀ x (x · e = x) poiché (Z, +) ⊨ ∀ x x · 0 = x

(Q≥0, ·) ⊨ ∀ x x · n = x

TEOREMA DI CORRETTEZZA e COMPLETEZZA

Sia T una teoria e φ un enunciato. Sono equivalenti:

1. T ⊢ φ (ossia la stringa T ⊢ si può ottenere applicando un numero finito di regole di deduzione a partire da stringhe di T)
2. T ⊨ φ (ossia ogni struttura G tale che G ⊨ T è anche tale che G ⊨ φ)

Trasforma il problema di carattere universale

T ⊨ φ nel problema di carattere esistenziale

T ⊢ φ

nel campo della mente!

PLATONISMO gli enti matematici hanno una concreta esistenza, la matematica è il linguaggio che ci permette di descrivere le proprietà

FINITISMO l'unica matematica che ha senso sono i calcoli concreti.

Teorema di correttezza e completezza mette d'accordo platonisti e finitisti

LOGICA PROPOSIZIONALE parla di connettivi mentre quella del PRIMO ORDINE mette in mezzo i quantificatori

Programma

• logica proposizionale
• logica del primo ordine
• (teorema di compattezza e completezza)
• sviluppo dell'aritmetica

ESEMPI

1. Tautologia La congettura di Riemann è vera oppure è falsa
2. Soddisfacibile Oggi piove a Torino

Per una tautologia ⇔ ΓP è una contraddizione Per soddisfacibile se ΓP non è una contraddizione

ESEMPI

1. Soddisfacibile (A ∨ ¬A) → ¬(A → B)
2. Tautologie ((A → B) → A) → A Legge di Pierce

Una proposizione Q è conseguenza logica di P₁, ..., P_m se ogni assegnazione di valori di verità alle lettere uninterne in P₁, ..., P_m, Q che rende vere tutte le proposizioni P₁, ..., P_m rende vera anche Q

ESEMPIO

Un Teorema, Se f: [0,A] → R, è continua allora f ammette un massimo

1. P₁ ∧ ... ∧ P_m ⊨ Q se e solo se (P₁ ∧ ... ∧ P_m) → Q è una tautologia
2. se e solo se per ogni n variabili proposizionali → ∀0,n² min_i ν(P_i) con i = 1, ..., m, m² ≤ ν(Q)

Due proposizioni si dicono logicamente equivalenti se ogni assegnazione di valori al vero in P e Q danno lo stesso valore di verità a P e Q

13 Ottobre 2016

Γ ⊧ Δ dove Γ = {f₁, f₂, ..., f_m} = {γ₁, γ₂, γ₃, f_m} = {γ_m} se e solo se ogni valutazione v i.x pop ⊨ f₀ γ i che rende vere tutte le formule in Γ rende vera almeno una formula in Δ

Una regola di deduzione è un'operazione che prende in input una o due coppie di insiemi finiti di formule {Г_i, Δ_i} e restituisce come output una coppia {Γ', Δ'} con la proprietà che se gli input sono tali che ⊧ Г_i = Δ_i allora anche per l'output Γ' ⊧ Δ'

ESEMPI

1. Modus ponens Γ ⊧ ψ Γ, ψ ⊧ ψ Γ ⊧ ψ
2. Γ, ψ ⊧ Γ, ψ₁, ψ₂, Δ Γ, ψ₁, ψ₂ ⊧ Δ Γ, ψ₁, ψ₂ ⊧ Δ Γ ⊧ Γ, ψ₁, ψ₂ ⊧ Γ, ψ ⊧ ψ Ragionamento per assurdo

LK - calcolo

1. ASSIOMI ϕ ⊧ ϕ
2. INDEBOLIMENTO Γ ⊧ Δ Γ ⊆ Γ ∪ П
3. TAGLIO Γ, ϕ, Δ Γ ⊧ Δ
4. WEDGE Γ ⊧ ϕ, ψ, Δ Γ ⊧ ϕ ∧ ψ, Δ left
5. VEL Γ ⊧ 1 Δ T Γ ⊧ Δ Γ ⊧ ϕ, ψ, Δ Γ ⊧ ϕ ∧ ψ, Δ right
6. NON Γ ⊧ ϕ, Δ Γ ⊧ ϕ, Δ left Γ ⊧ Δ Γ ⊧ Δ right

18 Ottobre 2016

La logica proposizionale formalizza alcuni costrutti del linguaggio naturale che ricorrono in matematica. Permette di formalizzare la nozione di Teorema con la nozione Γ ⊢ ϕ (deduce).

1. Tavola di verità o valutazioni per assegnare un valore di verità a ogni proposizione (semantica).
2. Nozione di conseguenza logica: Γ ⊨ Δ se e solo se (¬Γ → ∨Δ) è una Tautologia.
3. Proof teorico (calcolo LK) è la nozione Γ ⊢ Δ che formalizza l'idea che ∨/Δ è la conclusione di una dimostrazione che usa un'ipotesi.
4. Teorema Γ ⊨ Δ se e solo se Γ ⊢ Δ.

LEMMA Se Rᵢ è LK-logica rule                                                     Δ ◊₁                                                                Δ ◊₂...                                                     Δ ◊_n                                         Γ per esempio                                         ΨψΨ ◊ Δ                                                                  allora Γ ⊢ Δ sse (Γ ⊨ Δ per Σ ⊢ Δ)

Assia se V: V' prop ⊢ ϕ₁, ϕ₂ e Γ ⊨ Δ¹ Γ ⊢ Δ per Γ          T→Δ₁

LK-logicale rule si ha che v(Γ) ≤ V (∨Δ) ⇔ v (Δ) ≤ v (∨Δ_j) con j = 0,1

Φ ≡ [(Α→Β)→[(Β→c) + (Α→~c)]]                                        è Tautologia ⇔ ϕ̇̇ ⇔ ϕ̇ è LK-derivabile

Come dimostrare qui è una TAUTOLOGIA