Logica Matematica
Seconda lezione
Teoria
Formale
Assiomatica
L
Linguaggio formale
per il calcolo proposizionale.
1
È dato un insieme al più numerabile di simboli.
In L i simboli sono:
- connettivi primitivi ,  negazione, implicazione
- parentesi (,)
- lettere enunciative A1, A2,...An.
Una sequenza finita di simboli si chiama
Espressione.
2
Le formule ben formate
sono particolari espressioni individuate
dalla definizione seguente:
• (a) Le lettere enunciative sono f.b.f.
• (b) Se A e B sono f.b.f.
lo sono anche (A) e (AB).
A: negazione di A; AB: A implica B.
3
Si privilegia un insieme di f.b.f. da
chiamare Assiomi.
La teoria si dice assiomatica se esiste un
procedimento che permette di decidere
effettivamente se una fbf è un assioma.
Nel nostro caso gli assiomi
(o, più precisamente, schemi di assiomi)
sono:
Schemi di Assiomi di L
A1
(A  (BA))
Da A segue ( B implica A).
A2
((A(BC)) ((AB)(AC)) )
Se da A segue (B implica C), da (A implica B) segue (A implica C).
A3
((B  A)  (( B  A) B)).
Se da (non B) segue (non A), da ((non B) implica A) segue B.
RITORNO
4
Regole di inferenza
Esiste un insieme finito di relazioni
tra fbf dette regole di inferenza.
In L abbiamo una sola regola di inferenza, il
Modus Ponens (M P):
- Date le fbf. A e AB,
- B risulta conseguenza diretta di A e AB.
Dimostrazione
Sequenza di formule ben formate
i cui elementi sono assiomi o
conseguenze dirette di fbf
precedenti per mezzo di una
delle regole di inferenza (M P).
Teorema
Una fbf A con la proprietà che esiste una
dimostrazione la cui ultima fbf è A.
Decidibilità
La teoria si dice decidibile quando
esiste un procedimento meccanico
che permette di stabilire se una
qualsiasi fbf è un teorema oppure no.
Conseguenza
Una fbf A si dice conseguenza di un insieme
 di fbf. se A è l’ultima fbf di una sequenza che
contiene assiomi, conseguenze dirette e fbf. di .
Si ha, in tal caso, una deduzione di A da .
Si usa scrivere:  | A.
Quando  è l’insieme vuoto, si scrive | A.
In quest’ultimo caso, A è un teorema.
Esempio di teorema in L
• Lemma 1.7
| AA.
1) ( (A  ((AA)A) ) 
( (A(AA))  (AA) ) )
2) (A  ((AA)A))
3) ( (A(AA))  (AA) )
4) ( (A(AA))
5) (AA)
(A2)
(A1)
2), 1), MP
(A1)
4), 3), MP
Nelle applicazioni degli schemi di assiomi si sostituisce B con (A A)
Schemi di
assiomi
Principio d’induzione finita
Data una proposizione Pn, si supponga che
siano soddisfatte le seguenti condizioni:
1) P1 è vera;
2) Supposta vera Pn, si riesce a dimostrare
che è vera anche Pn+1.
___________________
Si può, allora, affermare che Pn è vera per
ogni n.
Principio d’induzione
finita:esempio
La somma dei primi n numeri dispari è n2.
L’affermazione è vera per n=1.
Supposto, per ipotesi induttiva, che
l’affermazione sia vera per n numeri
dispari (cioè che 1+3+...+2n-1= n2),
bisogna far vedere che essa risulta vera
anche per n+1.
Principio d’induzione
finita:esempio
Infatti, l’(n+1)esimo numero
dispari si scrive
2(n+1)-1 = 2n+1
2
e, sommandolo a n , si ottiene
2
2
n +2n+1=(n+1)
Teorema di deduzione
Se ,A | B allora  | AB.
(Se B è una conseguenza delle ipotesi  e A,
allora AB è una conseguenza di ).
In particolare, nel caso in cui  è l’insieme
vuoto, si ha che:
se A |B allora | AB.
(Se B è una conseguenza di A, allora AB è
un teorema).
Dimostrazione
Sia B1, B2,...Bn=B una deduzione di B da ,A.
Il teorema è vero per n=1:
- Se B1 è un assioma o B1  ,
poiché anche (B1  (AB1)) è un assioma ,
per MP si ottiene  | AB1.
- Se B1 è A, per il lemma precedente si ha che
|AA e, a maggior ragione,  | AA.
SCHEMI DI ASSIOMI
Per ipotesi induttiva, sia il teorema
vero per ogni k<i:  | ABk.
Bisogna far vedere che:
 | ABi.
Se Bi è un assioma, Bi  , Bi è A,
si procede come nel caso i=1.
Se Bi è ottenuto per MP da due elementi
precedenti della sequenza, essi dovranno
assumere la forma Bj e (BjBi) e, per
ipotesi induttiva, si avrà :
| ABj e  | A(BjBi).
Ma ((A  (BjBi) )  ( (ABj)  (ABi) ))
è un assioma e, per MP applicato due
volte, si otterrà, finalmente,
 | ABi.
Proposizione 1.11
• Ogni teorema di L è una tautologia.
Infatti, gli assiomi sono tautologie
e l’MP fa passare da tautologie a
tautologie.
Corollario 1.9a)
AB, BC | AC
Dimostrazione
1) A B ip
2) BC
ip.
3) A
ip.
4) B
1, 3, MP
5) C
2, 4, MP
_________________
AB, BC , A | C
Per il teorema di deduzione
AB, BC | AC
RITORNO
Corollario 1.9b)
A (BC), B | AC
Dimostrazione
1) A  (BC)
ip
2) A
ip.
3) B
ip.
4) BC
1, 2, MP
5) C
3, 4, MP
_________________
A  (BC), B, A | C
Per il teorema di deduzione
A(BC), B | AC
RITORNO
Lemma 1.10
a) | BB.
1) (B B)((BB)  B) A3
2) ( B B)
lemma 1.7
3) ( B   B)  B
1, 2, cor. 1.9b
4) B  (B   B )
A1
5) B  B
3, 4, cor.1.9a
Corollario 1.9a)
Corollario 1.9b)
Assiomi
Lemma 1.10
b) | B B.
1) (BB)((BB) B) A3
2) (B B)
Lemma1.10a
3) ( B B)  B
1, 2, MP
4) B  (B  B )
A1
5) B   B
3,4,cor. 1.9a
ASSIOMI
RITORNO
| A  (AB).
1) A
ip.
2) A
ip.
3) A (BA)
A1
4) A(BA)
A1
5) BA
2, 3, MP
6) BA
1, 4 MP
7) (BA) ((BA)B)
A3
8) (BA)  B
6, 7, MP
9) B
5, 8, MP
________________________________________
Perciò A, A | B e, per il teorema di deduzione,
C)
| A(AB).
RITORNO
d) | (BA) (AB)
1) BA
2) A
3) (BA )  (BA)B
4) A(BA)
5) (BA)B
6) AB
7) B
ip.
ip.
A3
A1
1, 3, MP
4, 5, cor. 1.9a
2, 6, MP
Perciò
(BA), A |B)
e, con due successive applicazioni del teorema di
deduzione | (BA) (AB)
e)| (AB)(BA)
1)AB
ip.
2)A A
parte a)
3)AB
1, 2, cor.1.9a)
4)BB
parte b)
5)AB
3, 4, cor.1.9a)
6)(AB)  (BA) parte d)
7)(BA)
5, 6. MP
_____________________________________
Perciò
AB | BA
e, per il teorema di deduzione
|  (AB)  (BA).
f) | A(B (AB)
1) A
ip.
2) AB
ip.
3) B
1, 2, MP
Perciò A, AB | B
e, per il teorema di deduzione,
| A((AB)B).
4)A((AB)B)
5)((AB)B).(B(AB)) Lemma 1.10 e)
6)A(B (AB)
4, 5, cor.1.9a
RITORNO
g) | (AB)((AB)B)
1) (AB)
ip.
2) AB
ip.
3) (AB) (BA)
parte e)
4) B A
1, 3, MP
5) (AB) (BA)
parte e)
6) B A
2, 5, MP
7) (B A)(B A)B A3
8) (B A)B
6, 7, MP
9) B
4, 8, MP
Perciò AB, AB| A
e, per il t. di deduzione
| (AB)((AB)B).
RITORNO
Lemma 1.12
Sia A una fbf e B1,..., Bk le lettere enunciative che
occorrono in A.
Per una data assegnazione di valori di verità a B1,...,
Bk, siano B’1,..., B’k tali che B’i sia Bi se Bi
assume il valore di verità V, B’i sia Bi se Bi
assume il valore F.
In maniera analoga A’ sarà A se quest’ultima assume
il valore V, A’ sarà A se A assume il valore F.
Allora B’1,..., B’k | A’.
Esempio di applicazione del
lemma 1.12
A2
V
F
V
F
A5  (A2A5)
V
F
V
F
F
F
F
V
Relazioni di deducibilità
A2, A5   (A2A5)
A2, A5   (A2A5)
A2,A5   (A2A5)
A2, A5   (A2A5)
Dimostrazione del lemma 1.12
Se n=0 allora A è una lettera
enunciative B1 e il lemma si riduce
a B1| B1 e B1 | B1.
Supponiamo che il lemma valga per
tutte le fbf con un numero di
connettivi primitivi j < n:
1) A è B. B ha meno occorrenze di A .
a) B ha il valore V e A ha il valore F.
B’ è B e A’ è A. Per ipotesi induttiva
B’1,..., B’k | B e,
poiché B  B** si ha, per MP,
B’1,..., B’k | B, cioè
B’1,..., B’k |A’
** lemma 1.10b
LEMMA 1.10
b) B ha il valore F e A il valore V.
B’ è B e A’ è A.
Per ipotesi induttiva
B’1,..., B’k | B, cioè
B’1,..., B’k | A’
2) A è (B C).
Poiché B e C hanno meno occorrenze di A
per ipotesi induttiva si avrà
B’1,..., B’k | B’e B’1,..., B’k | C’.
a) B ha il valore F e A il valore V.
B’1,..., B’k | B e
B’1,..., B’k | (BC)***.
Ma (BC) è A’, per cui B’1,..., B’k | A’
***
Lemma 1.10c)
b)C ha il valore V e, quindi, A il
valore V.
B’1,..., B’k  C e, per lo
schema d’assiomi A1 e MP,
B’1,..., B’k  BC. Quindi,
B’1,..., B’k  A’.
c) C ha il valore F e B il valore V,
quindi A ha il valore F.
B’1,..., B’k | C, quindi,
B’1,..., B’k | (BC)****.
Poiché (BC) è A’,
si ha la tesi.
****
Lemma 1.10f)
Teorema di completezza
Se una formula ben formata
è una tautologia, allora
essa è un teorema di L.
Dimostrazione : essendo A una tautologia,
essa ha sempre il valore V.
Il lemma 1.12 dà le due relazioni di deduzione:
B’1,...,B’k-1, Bk | A
B’1,...,B’k-1,Bk|A.
Per il teorema di deduzione si ha
B’1,...,B’k-1 | Bk A
B’1,...,B’k-1 | BkA.
Si ha, quindi, B’1,...,B’k-1 | A.***** Applicando k
volte questo procedimento si ottiene | A.
*****
Lemma 1.10g)
Corollario 1.15
Il sistema L è consistente, cioè non esiste
alcuna fbf. A tale che tanto A quanto A
siano teoremi di L.
Dimostrazione.
Ogni teorema di L è una tautologia e, dato
che la negazione di una tautologia non
può essere, a sua volta, una tautologia, si
ottiene la tesi.
Si osservi che L è consistente se e
solo se non tutte le sue fbf sono
teoremi.
Infatti, se L è consistente , le
negazioni dei teoremi sono fbf
che non sono teoremi. .
Viceversa, se L è inconsistente (cioè,
se ammette come teoremi una fbf e
la sua negazione), allora,
1) A
ip.
2) A
ip.
3) A  (AB) lemma 1.10c
4) A  B
1, 3, MP
5) B
2, 4, MP
Perciò, se L è inconsistente, qualsiasi
formula ben formata B è un
teorema di L.
Una teoria nella quale non tutte le
fbf sono teoremi è detta
assolutamente consistente..
Indipendenza di assiomi
Proposizione 1.16.
Ogni schema di assiomi A1-A3 è
indipendente.
Dimostrazione.
Indipendenza di A1.
Si considerino le seguenti tavole:
“Negazione”
A A
0
1
1
1
2
0
“Condizionale”
A
0
1
2
0
1
2
0
1
2
B
0
0
0
1
1
1
2
2
2
AB
0
2
0
2
2
0
2
0
0
• Se una formula ben formata A assume
sempre il valore 0, diciamo che A è una
scelta.
• L’MP fa passare da fbf scelte a fbf scelte.
Gli schemi di assiomi A2 e A3 sono scelti,
mentre A1 non è scelto. Con tecniche
analoghe si fa vedere l’indipendenza degli
altri schemi di assiomi.