Logica matematica/Calcolo delle proposizioni/Sistema di Hilbert: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 108:
In secondo luogo, esso ci fornisce la possibilità di trattare generiche derivazioni da insiemi di formule come teoremi. Infatti, in virtù della proprietà di compattezza di <math>\vdash</math>, abbiamo che, se <math>\Gamma \vdash A</math>, allora esiste un insieme finito <math>\Gamma_0 \subseteq \Gamma</math> tale che <math>\Gamma_0 \vdash A</math>. Siccome <math>\Gamma_0</math> è finito, sarà del tipo <math>\{A_1,...,A_n\}</math>, o equivalentemente <math>\{A_1 \and ... \and A_n\}</math>, quindi <math>\Gamma \vdash A</math> implica <math>\Gamma_0 \vdash A</math>, che equivale a <math>A_1 \and ... \and A_n \vdash A</math> e <math>A_1,...,A_n \vdash A</math>. Per il teorema di deduzione, otteniamo <math>\vdash (A_1 \and ... \and A_n) \to A</math> e <math>\vdash A_1 \to(... \to (A_n \to A)...)</math>.
== Consistenza ==▼
Introduciamo ora la nozione di ''consistenza''.▼
==== Insieme di formule consistente ====▼
{{Definizione|▼
Un insieme di formule proposizionali <math>\Gamma</math> è ''consistente'' sse è verificata una delle seguenti proprietà:▼
# non esiste una proposizione <math>A</math> tale che <math>\Gamma \vdash A</math> e <math>\Gamma \vdash \neg A</math>;▼
# esiste una proposizione <math>A</math> tale che <math>\Gamma \nvdash A</math>.▼
}}Si può dimostrare che le due formulazioni sono equivalenti.▼
(<math>\Rightarrow</math>) Se non esiste una proposizione <math>A</math> tale che <math>\Gamma \vdash A</math> e <math>\Gamma \vdash \neg A</math>, allora si ha che <math>\Gamma \nvdash A</math> oppure <math>\Gamma \nvdash \neg A</math> per ogni proposizione <math>A</math>, dunque esiste una proposizione <math> B</math> tale che <math>\Gamma \nvdash B</math>.▼
(<math>\Leftarrow</math>) Viceversa, supponiamo che esista una proposizione <math>A</math> tale che <math>\Gamma \vdash A</math> e <math>\Gamma \vdash \neg A</math>, e che non esista una formula <math> B</math> tale che <math>\Gamma \nvdash B</math>, che equivale a dire <math>\Gamma \vdash B</math> per ogni formula <math> B</math>. Se si dimostra che <math>A, \neg A \vdash B</math> per ogni formula <math> B</math>, allora, per taglio sulle premesse, si ha che <math>\Gamma \vdash B</math>.▼
Per il teorema di deduzione, abbiamo che <math> A \vdash \neg A \to B</math> e <math>\vdash A \to (\neg A \to B)</math>, e per monotonia <math>A \vdash A \to (\neg A \to B)</math>. Dunque, <math>A, \neg A \vdash B</math> sse <math>A \vdash A \to (\neg A \to B)</math>.▼
Dallo schema ''a'' abbiamo <math id="to"> \vdash (\neg A \to B) \to (A \to (\neg A \to B))</math>, e, per MP, da <math> A \vdash \neg A \to B</math> otteniamo <math>A \vdash A \to (\neg A \to B)</math>. Quindi, effettivamente vale <math>A, \neg A \vdash B</math>, e, per taglio sulle premesse, si ha che <math>\Gamma \vdash B</math> per ogni formula <math> B</math>.▼
Dunque, per contrapposizione, se esiste una formula <math> B</math> tale che <math>\Gamma \nvdash B</math>, allora non esiste una proposizione <math>A</math> tale che <math>\Gamma \vdash A</math> e <math>\Gamma \vdash \neg A</math>.▼
==== Insieme di formule completo ====▼
{{Definizione|▼
Un insieme di formule <math>\Gamma</math> si dice ''consistente e massimale'' o ''completo'' se, per ogni formula <math>A \in \mathcal{L}</math>, si verifica una e una sola delle seguenti relazioni:▼
:<math>\Gamma \vdash A</math> oppure <math>\Gamma \vdash \neg A</math>.▼
}}▼
Notare che la nozione di insieme consistente e massimale è analoga a quella di [[Logica/Calcolo delle proposizioni/Dimostrazione del teorema di compattezza#Insieme di formule massimale|insieme massimale]] soddisfacibile.▼
== Correttezza e completezza ==
Line 169 ⟶ 139:
=== Teorema di correttezza ===
:<math>\vdash A \to B</math> implica <math>\vDash A \to B</math>.
Line 182 ⟶ 153:
Per quanto riguarda la SU, sia <math>F[p]</math> una tautologia. Allora, <math>\vDash F[p]</math> per qualunque assegnazione booleana alle lettere proposizionali di <math>F[p]</math>, in particolare a <math>p</math>; dunque, per qualunque proposizione <math>X</math> possiamo porre <math>I_\mathcal{V}(p)=I_\mathcal{V}(X)</math>. Per il teorema del rimpiazzamento, <math>I_\mathcal{V}(F[p/p])=I_\mathcal{V}(F[X/p])</math>, da cui segue <math>\vDash F[X/p]</math>.
=== Teorema di completezza ===
<math>\vDash A \to B</math> implica <math>\vdash A \to B</math>.
▲== Consistenza ==
▲Introduciamo ora la nozione di ''consistenza''.
▲==== Insieme di formule consistente ====
▲{{Definizione|
▲Un insieme di formule proposizionali <math>\Gamma</math> è ''consistente'' sse è verificata una delle seguenti proprietà:
▲# non esiste una proposizione <math>A</math> tale che <math>\Gamma \vdash A</math> e <math>\Gamma \vdash \neg A</math>;
▲# esiste una proposizione <math>A</math> tale che <math>\Gamma \nvdash A</math>.
▲}}Si può dimostrare che le due formulazioni sono equivalenti.
▲(<math>\Rightarrow</math>) Se non esiste una proposizione <math>A</math> tale che <math>\Gamma \vdash A</math> e <math>\Gamma \vdash \neg A</math>, allora si ha che <math>\Gamma \nvdash A</math> oppure <math>\Gamma \nvdash \neg A</math> per ogni proposizione <math>A</math>, dunque esiste una proposizione <math> B</math> tale che <math>\Gamma \nvdash B</math>.
▲(<math>\Leftarrow</math>) Viceversa, supponiamo che esista una proposizione <math>A</math> tale che <math>\Gamma \vdash A</math> e <math>\Gamma \vdash \neg A</math>, e che non esista una formula <math> B</math> tale che <math>\Gamma \nvdash B</math>, che equivale a dire <math>\Gamma \vdash B</math> per ogni formula <math> B</math>. Se si dimostra che <math>A, \neg A \vdash B</math> per ogni formula <math> B</math>, allora, per taglio sulle premesse, si ha che <math>\Gamma \vdash B</math>.
▲Per il teorema di deduzione, abbiamo che
▲
▲Dunque, per contrapposizione, se esiste una formula <math> B</math> tale che <math>\Gamma \nvdash B</math>, allora non esiste una proposizione <math>A</math> tale che <math>\Gamma \vdash A</math> e <math>\Gamma \vdash \neg A</math>.
▲==== Insieme di formule completo ====
▲{{Definizione|
▲Un insieme di formule <math>\Gamma</math> si dice ''consistente e massimale'' o ''completo'' se, per ogni formula <math>A \in \mathcal{L}</math>, si verifica una e una sola delle seguenti relazioni:
▲:<math>\Gamma \vdash A</math> oppure <math>\Gamma \vdash \neg A</math>.
▲}}
▲Notare che la nozione di insieme consistente e massimale è analoga a quella di [[Logica/Calcolo delle proposizioni/Dimostrazione del teorema di compattezza#Insieme di formule massimale|insieme massimale]] soddisfacibile.
== Esempi di dimostrazioni ==
| |||