Logica Matematica- teoremi

Teoremi di logica matematica

Sommario

• Teorema di correttezza e completezza dei tableaux proposizionali ................................................................. 3
• Definizione di α-formula ................................................................................................................................ 3
• Proposizione sulle α-formule ........................................................................................................................ 3
• Definizione di β-formula ................................................................................................................................ 3
• Proposizione sulle β-formule ......................................................................................................................... 3
• Proposizione sulle formule proposizionali .................................................................................................... 3
• Definizione di sottoformule (induzione strutturale) ..................................................................................... 3
• Definizione di tableaux proposizionale ......................................................................................................... 3
• Definizione di tableaux proposizionale chiuso e aperto ............................................................................... 4
• Proposizione sui tableaux proposizionali chiusi ............................................................................................ 4
• Enunciato teorema di completezza e correttezza per i tableaux proposizionali .......................................... 4
• Enunciato teorema di correttezza per i tableaux proposizionali .................................................................. 4
• Dimostrazione teorema di correttezza per i tableaux proposizionali ....................................................... 4
• Enunciato teorema di completezza per i tableaux proposizionali ................................................................. 5
• Definizione di H-set proposizionali ................................................................................................................ 5
• Definizione di rango ....................................................................................................................................... 5
• Lemma 1 ........................................................................................................................................................ 5
• Dimostrazione lemma 1............................................................................................................................. 5
• Lemma 2 ........................................................................................................................................................ 5
• Dimostrazione lemma 2............................................................................................................................. 5
• Dimostrazione teorema di completezza per i tableaux proposizionali ..................................................... 6
• Teorema di correttezza e completezza dei tableaux della logica dei predicati ................................................ 6
• Definizione di γ-formule ................................................................................................................................ 6
• Lemma sulle γ-formule .................................................................................................................................. 6
• Dimostrazione lemma sulle γ-formule ...................................................................................................... 6
• Definizione di δ-formule ................................................................................................................................ 6
• Lemma sulle δ-formule .................................................................................................................................. 6
• Dimostrazione lemma sulle δ-formule ...................................................................................................... 6
• Lemma sulle formule della logica dei predicati ............................................................................................. 6
• Definizione di tableaux nella logica dei predicati .......................................................................................... 7
• Definizione di tableaux chiuso e aperto nella logica dei predicati ................................................................ 7
• Enunciato teorema di completezza e correttezza per i tableaux nella logica dei predicati .......................... 7
• Enunciato teorema di correttezza per i tableaux nella logica dei predicati .................................................. 7
• Dimostrazione teorema di correttezza per i tableaux nella logica dei predicati ...................................... 7
• Enunciato teorema di completezza per i tableaux nella logica dei predicati ................................................ 8
• Definizioni di tableaux sistematici ................................................................................................................. 8
• Definizione di H-set nella logica dei predicati ............................................................................................... 9
• Lemma 1 ........................................................................................................................................................ 9
• Dimostrazione lemma 1............................................................................................................................. 9
• Lemma 2 ........................................................................................................................................................ 9
• Dimostrazione lemma 2........................................................................................................................... 10
• Dimostrazione teorema di completezza per i tableaux nella logica dei predicati .................................. 10

Teorema di correttezza e completezza dei tableaux proposizionali

Definizione di α-formula

∧ ¬( ∨ ) ¬( → ). Una formula è una α-formula se ha la forma oppure oppure. I ridotti di una α-formula sono:

Proposizione sulle α-formule

Ogni α-formula è equivalente alla congiunzione dei suoi ridotti.

Definizione di β-formula

∨ ¬( ∧ ) →. Una formula è una β-formula se ha la forma oppure oppure. I ridotti di una β-formula sono:

Proposizione sulle β-formule

Ogni β-formula è equivalente alla disgiunzione dei suoi ridotti.

Proposizione sulle formule proposizionali

Ogni formula è di uno dei seguenti tipi:

• È un letterale
• = ¬¬ è una doppia negazione, cioè
• È una α-formula
• È una β-formula

Definizione di sottoformule (induzione strutturale)

L'insieme delle sottoformule di una formula è definito nel seguente modo:

• () = {}; Se P è una variabile proposizionale allora
• = ∧ = ∨ = → () = ( ) ∪ ( ) ∪ {}; Se, , o allora in1 2 1 2 1 2 1 2. Questo caso diremo che e sono le sottoformule principali di1 2
• = ¬ () = ( ) ∪ {}; Se allora in questo caso è la sottoformula principale di1 1 1

Definizione di tableaux proposizionale

Un tableau per una formula è un albero i cui nodi sono etichettati con insiemi di sottoformule di (). Denotiamo con l'etichetta del nodo. L'albero si costruisce per passi successivi. Al passo 0 abbiamo un {}. Al passo 0 abbiamo un albero formato da un solo nodo con etichetta. Se al passo abbiamo costruito un albero, al passo costruiamo l'albero guardando le foglie dell'albero:

• Se nelle foglie ci sono solo letterali, allora la costruzione termina e sarà l'albero finale.
• () Supponiamo che nell'etichetta della foglia ci sia una formula che non è un letterale. Allora si possono avere i seguenti casi:
• = ¬¬ Se è una doppia negazione, allora l'albero si costruisce aggiungendo un nodo come successore di e ponendo1 1 1