Transcript
Logica proposizionale classica • Studia il comportamento dei connettivi proposizionali quali ∧ (“And”) e ∨ (“Or”) • Parte da una famiglia di enunciati atomici di cui non analizziamo la struttura interna, che rappresentiamo con delle lettere, di cui ci interessa conoscere solo il valore di verit`a • Da queste “lettere proposizionali” costruiamo enunciati pi`u elaborati usando i connettivi proposizionali • Sapere quali enunciati composti sono veri a causa della loro struttura: le tautologie, e quali enunciati sono conseguenza logica di altri 1
Linguaggio della logica proposizionale classica • insieme P = {p1, p2, p3, . . .} di lettere proposizionali • simboli di costante: ⊤ (vero) e ⊥ (falso) • connettivi proposizionali: – unari: ¬ (negazione) – binari: ∧, ∨, ⊃, ≡,... • parentesi: (,)
2
Definizione delle formule proposizionali Una formula atomica `e una lettera proposizionale, ⊤ o ⊥. Indichiamo con ATProp l’insieme di tutte le formule atomiche L’insieme delle formule proposizionali Prop viene definito come il pi`u piccolo insieme S ⊆ Σ+ che gode delle seguenti propriet`a: 1. ATProp ⊆ S 2. X ∈ S ⇒ ¬X ∈ S 3. X, Y ∈ S ⇒ (X ◦ Y ) ∈ S, per ogni connettivo binario ◦
3
Principio di induzione strutturale Metodo di dimostrazione che sfrutta la struttura induttiva delle formule Sia Q ⊆ Prop, se • CASO BASE: 1. ATProp ⊆ Q • PASSO INDUTTIVO: 2. X ∈ Q ⇒ ¬X ∈ Q 3. X, Y ∈ Q ⇒ (X ◦ Y ) ∈ Q, per ogni connettivo binario ◦ Allora Q = Prop 4
Principio di ricorsione strutturale
C’`e una ed una sola funzione f definita su Prop tale che CASO BASE Il valore di f `e specificato esplicitamente sulle formule atomiche attraverso una funzione g : ATProp → D PASSO INDUTTIVO il valore di f su ¬X viene specificato in termini del valore di f su X attraverso una funzione f¬ : D → D il valore di f su (X ◦ Y ) viene specificato in termini dei valori di f su X e su Y mediante una funzione l : BinarySymbol × D × D → D 5
Definizione di funzioni per induzione Sia A ⊆ U definito induttivamente dalla base B e dall’insieme di costruttori K. Sia V un insieme arbitrario. Associamo • ad ogni elemento a ∈ B un elemento h(a) ∈ V • ad ogni costruttore r ⊆ U n × U ∈ K, (n ≥ 1), una funzione h(r) : V n → V
6
Definizione di funzioni per induzione (ctnd.) Una definizione induttiva di una funzione g : A → V viene data da a) g(a) = h(a) per ogni elemento a ∈ B b) g(a) = h(r)(g(a1), . . . , g(an)) cio´e (a, h(r)(b1, . . . , bn)) ∈ g se (a1, b1), . . . , (an, bn) ∈ g per tutti gli r ⊆ U n × U, e a1, . . . , an ∈ A con ((a1, . . . , an), a) ∈ r Questa definizione `e consistente solo se ad ogni a ∈ A viene assegnato esattamente un valore mediante a) oppure b) (cio´e se g `e una funzione) Se questa condizione viene soddisfatta diciamo che g `e ben definita 7
Definizione di funzioni per induzione (ctnd 1.) Teorema di ricorsione Se la definizione induttiva di un insieme A mediante l’insieme base B e l’insieme dei costruttori K `e libera, allora la funzione g : A → V definita induttivamente come nella definizione precedente `e ben definita
8
Unicit` a del parsing Ogni formula proposizionale `e esattamente in una delle tre categorie: • Atomica • ¬X per un’unica formula proposizionale X • (X ◦ Y ) per un unico simbolo binario ◦ e formule proposizionali uniche X e Y
9
Sottoformula Le sottoformule immediate sono definite come segue: 1. Una formula atomica non ha sottoformule immediate 2. La sola sottoformula immediata di ¬X `e X 3. Per un simbolo binario ◦, le sottoformule immediate di (X ◦ Y ) sono X e Y L’insieme delle sottoformule di una formula X `e il pi`u piccolo insieme S tale che: •X ∈ S • per ogni Y ∈ S, tutte le sottoformule immediate di Y sono contenute in S 10
Semantica della logica proposizionale La logica classica `e a due valori. Prendiamo come spazio dei valori di verit`a l’insieme Tr = {t, f } Come interpretiamo ciascuno dei simboli di operazione del linguaggio? • Per la negazione assumiamo di avere una mappa ¬ : Tr → Tr data da ¬(t) = f e ¬(f ) = t • Possiamo individuare dieci connettivi. Otto primari e due secondari
11
Connettivi binari
t t f f
t f t f
∧ t f f f
∨ t t t f
⊃ t f t t
⊂ t t f t
↑ f t t t
12
↓ f f f t
6⊃ f t f f
6⊂ f f t f
≡ t f f t
6≡ f t t f
Valutazioni booleane Una valutazione booleana `e un’applicazione v : Prop → Tr che soddisfa le condizioni 1. v(⊤) = t, v(⊥) = f 2. v(¬X) = ¬v(X) 3. v(X ◦ Y ) = v(X) ◦ v(Y ), dove ◦ sta per uno dei connettivi proposizionali Lemma Data f : {p1, p2, . . .} → Tr , esiste un’unica valutazione booleana vf tale che vf (P ) = f (P ), per ogni lettera proposizionale P .
13
Valutazioni booleane Lemma Siano S un insieme di lettere proposizionali, X una formula proposizionale coinvolgente solo lettere proposizionali in S, e v1, v2 due valutazioni booleane tali che v1(P ) = v2(P ) per ogni P ∈ S, allora v1(X) = v2(X).
14
