Post on 02-May-2015
Logica Matematica
Seconda lezione
Teoria Formale Assiomatica L
Linguaggio formale
per il calcolo proposizionale.
È 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.
1
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 (AB). A: negazione di A; AB: A implica B.
2
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:
3
Schemi di Assiomi di L
A1 (A (BA)) Da A segue ( B implica A).
A2 ((A(BC)) ((AB)(AC)) ) 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
Regole di inferenzaEsiste 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 AB,
- B risulta conseguenza diretta di A e AB.
4
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 | AA.
1) ( (A ((AA)A) ) ( (A(AA)) (AA) ) ) (A2)
2) (A ((AA)A)) (A1)
3) ( (A(AA)) (AA) ) 2), 1), MP
4) ( (A(AA)) (A1)
5) (AA) 4), 3), MP
Nelle applicazioni degli schemi di assiomi si sostituisce B con (A A) Schemi diassiomi
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
e, sommandolo a n2, si ottiene n2+2n+1=(n+1)2
Teorema di deduzione
Se ,A | B allora | AB. (Se B è una conseguenza delle ipotesi e A,
allora AB è una conseguenza di ).In particolare, nel caso in cui è l’insieme
vuoto, si ha che: se A |B allora | AB. (Se B è una conseguenza di A, allora AB è
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 (AB1)) è un assioma ,
per MP si ottiene | AB1.
- Se B1 è A, per il lemma precedente si ha che |
AA e, a maggior ragione, | AA.SCHEMI DI ASSIOMI
Per ipotesi induttiva, sia il teorema
vero per ogni k<i: | ABk.
Bisogna far vedere che:
| ABi.
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 (BjBi) e, per ipotesi induttiva, si avrà :
| ABj e | A(BjBi).
Ma ((A (BjBi) ) ( (ABj) (ABi) ))
è un assioma e, per MP applicato due volte, si otterrà, finalmente,
| ABi.
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)
AB, BC | ACDimostrazione1) A B ip2) BC ip.3) A ip.4) B 1, 3, MP5) C 2, 4, MP_________________AB, BC , A | CPer il teorema di deduzioneAB, BC | AC RITORNO
Corollario 1.9b)A (BC), B | AC Dimostrazione1) A (BC) ip2) A ip.3) B ip.4) BC 1, 2, MP5) C 3, 4, MP_________________A (BC), B, A | CPer il teorema di deduzioneA(BC), B | AC RITORNO
Lemma 1.10
a) | BB.
1) (B B)((BB) 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.9aCorollario 1.9a) Corollario 1.9b) Assiomi
Lemma 1.10b) | B B.
1) (BB)((BB) 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
RITORNOASSIOMI
C) | A (AB). 1) A ip. 2) A ip. 3) A (BA) A1 4) A(BA) A1 5) BA 2, 3, MP 6) BA 1, 4 MP 7) (BA) ((BA)B) A3 8) (BA) B 6, 7, MP 9) B 5, 8, MP________________________________________Perciò A, A | B e, per il teorema di deduzione,
| A(AB).RITORNO
d) | (BA) (AB) 1) BA ip. 2) A ip. 3) (BA ) (BA)B A3 4) A(BA) A1 5) (BA)B 1, 3, MP 6) AB 4, 5, cor. 1.9a 7) B 2, 6, MP
Perciò (BA), A |B) e, con due successive applicazioni del teorema di deduzione | (BA) (AB)
e)| (AB)(BA) 1)AB ip. 2)A A parte a) 3)AB 1, 2, cor.1.9a) 4)BB parte b) 5)AB 3, 4, cor.1.9a) 6)(AB) (BA) parte d) 7)(BA) 5, 6. MP_____________________________________Perciò AB | BA e, per il teorema di deduzione | (AB) (BA).
f) | A(B (AB)
1) A ip.
2) AB ip.
3) B 1, 2, MP
Perciò A, AB | B e, per il teorema di deduzione,
| A((AB)B).
4)A((AB)B)
5)((AB)B).(B(AB)) Lemma 1.10 e)
6)A(B (AB) 4, 5, cor.1.9a
RITORNO
g) | (AB)((AB)B) 1) (AB) ip. 2) AB ip. 3) (AB) (BA) parte e) 4) B A 1, 3, MP 5) (AB) (BA) 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, MPPerciò AB, AB| A e, per il t. di deduzione
| (AB)((AB)B).RITORNO
Lemma 1.12Sia 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 A5 (A2A5) Relazioni di deducibilità V V F A2, A5 (A2A5) F V F A2, A5 (A2A5) V F F A2,A5 (A2A5) F F V A2, A5 (A2A5)
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.10bLEMMA 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 | (BC)***. Ma (BC) è 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 BC. 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 | (BC)****.
Poiché (BC) è 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 | BkA.
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 (AB) lemma 1.10c4) A B 1, 3, MP5) 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 B AB0 0 01 0 22 0 00 1 21 1 22 1 00 2 21 2 02 2 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.