Semantiche proposizionali
logica classica logica intuizionista valutazione BIVALENTE NO valutazione BIVALENTE
ν : Prop(L) −→ {0, 1}
valutazione MULTIVALENTE valutazione MULTIVALENTE
ν : Prop(L) −→ B ν : Prop(L) −→ H
inalgebra di Boole
B
inalgebra di HeytingH
def. contromodello di un enunciato fr di L
=modello bivalente in cui fr `e falsa
ovvero ν(fr) = 0
def. contromodello MULTIvalente di un enunciato fr di L
= modello MULTIvalente in cui fr NON `e vera
ovvero ν(fr) 6= 1
ALGEBRE di Boole e di Heyting
algebra diBoole
B
algebra di Heyting=
algebra diHeyting +
¬ a
`e complemento dia ∈ B ¬ a
`e PSEUDO-complementodia ∈ H
ovvero
a ∨¬ a = 1 a ∨¬ a ≤ 1
⇓ ⇓
a → b = ¬ a ∨ b a → b ≥ ¬ a ∨ b
Teorema di validit `a
tautologia formale
⊢ fr
`e derivabile inL
⇓
(th. Validit `a)la sua dimostrazione segue da dimostrazionevalidit `a
delle regole del calcolo laverit `a di un sequente in un modello
scende
⇓
dalle premesse alla radice di ogni regola inOGNI singolo modellotautologia semantica
fr
ha SOLTANTO modelliTeorema di completezza
tautologia semantica
fr
ha SOLTANTO modelli⇓
(th. completezza) dimostrazione ad hoc a seconda della semantica!!tautologia formale
⊢ fr
`e derivabile inL
Teorema di completezzatra LCp e semantica bivalente
tautologiasemantica bivalente
fr
haSOLTANTO modelli⇓
(th. completezza) via procedura di decisione derivabilit `a sequente proposizionale classicotautologiaformale
⊢ fr
`e derivabile in LCpTeorema di completezza traLCp e semanticabooleana
tautologia semantica booleana
fr
ha SOLTANTO modelli⇓
(th. completezza)via interpretazione identica
nell’ algebra booleana delleformule(algebra di Lindenbuam)
tautologia formale
⊢ fr
`e derivabile in LCpTeorema di completezzatra LIp e semantica intuizionista
tautologia semantica intuizionista
fr
ha SOLTANTO modelli⇓
(th. completezza)viainterpretazione identica
nell’ algebra di Heytingdelle formule(algebra di Lindenbuam)
tautologia formale
⊢ fr
`e derivabile in LIpTeorema di completezza traLC= e semantica bivalente
tautologiasemantica bivalente
fr
haSOLTANTO modelli⇓
(th. completezza)dimostrazione NON costruttiva via LEMMA DI ZORN
tautologiaformale
⊢ fr
`e derivabile in LCpTeorema di completezza traLC= e semantica booleana predicativa
tautologia semantica booleana predicativa
fr
haSOLTANTO modelli⇓
(th. completezza)dimostrazione costruttiva
via completamento di Dedekind-MacNeille dell’algebra delle formuledi Lindenbaum
tautologia formale
⊢ fr
`e derivabile inLC
=
Teorema di completezza traLI= e semantica in algebre di Heyting complete
tautologia semantica in algebre di Heyting complete
fr
ha SOLTANTO modelli⇓
(th. completezza)dimostrazione costruttiva
via completamento di Dedekind-MacNeille dell’ algebra delle formuledi Lindenbaum
tautologia formale
⊢ fr
`e derivabile in LC=teoremi di completezza predicativi conalgebra delle formule
l’algebra delle formule predicative sia diLI= che di LC=
ha una struttura descrivibile in teoria delle categorie
⇓
teorema dicompletezzadi LI= rispetto alla semantica categorialeintuizionista
tramite l’interpretazione identica nell’algebra delle formulediLI=
teorema dicompletezza diLC= rispetto alla semantica categorialeclassica
tramite l’interpretazione identica nell’algebra delle formuledi LC=
