CAPITOLO 6
DEDUZIONE NATURALE PROPOSIZIONALE CLASSICA
AVVERTENZA: TRASCURATELA A VOSTRO RISCHIO E PERICOLO . Quanto segue é un cross-over
tra un set di lecture notes e un textbook. La presentazione in paragrafi e sottoparagrafi, la presenta di NOTE ed OSSERVAZIONI,
etc é tipica di un libro di testo; invece la presenza di esempi ed esercizi, commenti a chiarimento, etc e la mancanza di una
bibliografia sera e ragionata é tipica di appunti di lezione. La forma tipografica (colpa di Donald Knuth) é quella di un libro
di testo. Il fatto che vi siano umpteen casi di errori di stompa, e magari errori matematici, lo denuncia come al massimo una
bozza di possibile textbook, il che é avvalorato da ricorrenze di ”[[MANCA]]” che sono dei promemoria di altro materiale che
potrebbe essere aggiunto. Ogni segnalazione di sviste, errori, o miglioramenti possibili é benvenuta. [email protected]
1. La deduzione naturale
Finora, abbiamo trattato della relazione di conseguenza logica (proposizionale)|= nel
senso ”semantico”. Nell’ esperienza comune delle dimostrazioni in matematica non si
usano certo le t.d.v., e si lavora in modo del tutto diverso: un asserto (la tesi A) è
ottenuto a partire da certi assunti Γ (le ipotesi) tramite un ragionamento svolto applicando regole (implicite nel ragionamento usuale) che consentono passaggi logici e che
conduce in un numero finito di passi da certi assunti C−vera (C ∈ Γ) alla conclusione
A−vera; se proviamo ad esplicitare le singole regole logiche, intuitivamente un ragionamento formale si puó rappresentare come un grafo (finito) ad albero che procede dalle
”foglie” (le assunzioni in Γ prese come vere) a trarre conclusioni intermedie secondo
prefissate regole logiche e procede utilizzando tali conclusioni intermedie, sempre per via
di prefissate regole logiche, fino ad ottenere la conclusione: quella che si puó chiamare
una ”deduzione” o ” dimostrazione” di A vera a partire da Γ vere.
Si noti la grande disparitá dei due approcci: da una parte Γ |= A se per ogni ”situazione
possibile” (i.e. valutazione) che renda vere le assunzioni o ipotesi in Γ, anche A è resa
vera. Dall’ altra, invece, A−vera sará ”deducibile” dalle varie C−vera, se esiste un
”ragionamento” che porta da Γ alla conclusione A. In piu,’ occorrerá che alla fine le due
nozioni si equivalgano.
Le regole che riguardano i varii connettivi, introdotte da G. Gentzen negli anni ’30,
si ottengono riflettendo sul compito svolto dai connettivi stessi.(È tradizionale, e non si
perde nulla, considerare il connettivo ↔ come derivato, mediante →, ∧.)
1
2
CAPITOLO 6
Domandiamoci, per ciascun connettivo :
(1) cosa è sufficiente avere, in generale, per poter immediatamente costruire una
dimostrazione di (A B) vera a partire dalle ipotesi C vera (per C ∈ Γ) ?
(2) cosa possiamo dedurre immediatamente dal possedere una dimostrazione di (A
B) vera dalle solite assunzioni? (ossia, come si utilizza in via immediata una
siffatta informazione, ossia la conoscenza che (A B) vera?)
Per cominciare con la congiunzione ∧, le domande 1 e 2 hanno una risposta chiara:
–per costruire una dimostrazione di (A ∧ B) vera, basta avere due cose: una dimostrazione
di A vera, ed una di B vera. Notare che NON si sostiene affatto che questo sia l ’unico modo
che consente di dimostrare A ∧ B vera ! Ma certo questo e’ un modo per farlo... .
–da una data dimostrazione di (A ∧ B) vera, possiamo costruire immediatamente sia una
dimostrazione di A vera che una dimostrazione di B vera.
Notare che NON si sostiene che queste siano le uniche conclusioni possibili a partire da
A ∧ B vera !
Se una riga orizzontale sta per ”l’ asserto sottostante è evidentemente ed immediatamente
ricavabile da quelli sovrastranti”, potremo stenografare questa riflessione cosı́ :
Γ vere
|
Avera
Γ vere
|
Bvera
A ∧ Bvera
dove il trattino verticale indica l’ ipotetico ragionamento che da Γ ha consentito di concludere
A, rispettivamente B; l’ intero grafo ora rappresenta una dimostrazione di (A ∧ B) vera , dalle
solite assunzioni.
D’ altra parte, come possiamo usare una assunzione A∧Bvera ; cosa possiamo sicuramente ed
immediatamente dedurre? Certamente possiamo dedurre a piacere A vera o B vera: abbiamo
due schemi, entrambi accettabili:
Γ vere
|
A ∧ B vera
Γ vere
|
A ∧ B vera
Avera
Bvera
Circa l’ implicazione avremo:
– per ottenere una dimostrazione di (A → B) vera da certe ipotesi Γ,, è sufficiente che, aggiungendo A vera a tali ipotesi, si possegga una dimostrazione di B vera . D’altronde, la maggior parte dei teoremi matematici dimostrano delle implicazioni; e tipicamente la dimostrazione
di un teorema ”A → B” procede esattamente in questo modo: si prende l’ ipotesiI che A vera,
e insieme agli assiomi iniziali si dimostra che allora B vera. SE ne conclude A → B vera dai soli
assiomi iniziali. L ’ipotesi A vera ha svolto il suo ruolo e sparisce comte ipotesi nell’ enumciato
finale: e’ andata a finire nell’ antecedente dell’ implicazione. Il che si schematizzerebbe cosı́ :
Γ, [A]n vere
|
B vera
(A → B) vera
(n)
CAPITOLO 6
3
ricordando che l’ ipotesi A e’ aggiunta momentaneamente alla assunzioni generali di Γ, allo
scopo di dedurre B vera e puo’ essere ”scaricata” al momento di asserire la conclusione
A → B vera : per questo motivo, al momento di tirare la linea di conclusione, aggiungiamo
parentesi [ ] attorno alle assunzioni momentanee di forma A usate nella dimostrazione che
ha concluso con B vera. Siccome questo tipo di ”scarico” o disattivazione di assunzioni si
puo’ ripetere varie volte all ’interno di una dimostrazione, e’ anche necessario sapere in quale
momento si sta effettuando un tale scarico: pertanto decoreremo le parentesi [ ] con un indice
numerico [ ]n e riporteremo tale indice numerico accanto alla linea di quella conclusione che
consente lo scarico. (Gli esempi qui avanti chiariranno la situazione.)
–d’altra parte, l’ utilizzo immediato di una dimostrazione di (A → B) vera sta nel combinarla con una dimostrazione di A vera per ottenere B vera ; schematizzando:
Γ vere
|
A vera
Γ vere
|
(a → B) vera
B vera
la quale è forse la regola logica piú familiare che si conosca (nota anche con il nome medievale
di modus ponens): la prova ” ausiliaria” di A → B vera costituisce un classico lemma, avendo
il quale, in vista di concludere con B vera , bastera’ che si sia stabilito anche A vera .
Passiamo al connettivo ∨ :
–per costruire una dimostrazione di (A ∨ B) vera , basta certamente una delle due: una
dimostrazione di A vera oppure una di B vera ; stenografando come sopra abbiamo due possibilitá:
Γ vere
Γ vere
|
|
A vera
B vera
A ∨ B vera
A ∨ B vera
–l’ informazione che (A ∨ B) vera , non consente in generale di sapere quale delle due sia
vera; essa si utilizza solitamente proseguendo ”per casi”: se possedessi una dimostrazione di una
certa conclusione C vera aggiungendo momentaneamente A vera alle solite ipotesi, nonchè
una dimostrazine di C vera aggiungendo momentaneamente alle solite ipotesi B vera , allora
dalle solite ipotesi concluderei con C vera . Per esempio, sappiamo che un numero intero e’
o pari o dispari. Per dimostrare che numero n ha una proprieta’ P, posso procedere come
segue: Con una dimostrazione ausiliaria d1 , provo che: se il numero e’ pari, allora soddisfa
P ; con un’ altra dimostrazione ausiliaria d2, provo che se il numero e’ dispari, ancora vale P ;
conclusione P vale ”comunque” ; ed in questa conclusione le ipotesi ”il numero e’ pari ” e ”il
numero e’ dispari ” utilizzate nelle prove ausiliarie, non hanno piu’ ruolo.
Tutto ció , suggerisce Gentzen, si puo’ schematizzare come segue:
Γ vere
|
(A ∨ B) vera
Γ, [A] vere
|
C vera
Γ, [B] vere
|
C vera
C vera
Si noti come la conclusione si ottiene dalle sole ipotesi Γ; nelle due dimostrazioni ausuliarie
da Γ, A a δ e da Γ, B a δ, le aggiunte di A o di B sono momentanee: le sole ipotesi necessarie
4
CAPITOLO 6
per ottenere δ sono, alla fine, solo quelle in Γ. Per questo motivo sono segnate tra parentesi
[ ] : esse, una volta utilizzate nelle dimostrazioni ausiliari, non fanno piú parte delle assunzioni
usate per la conclusione δ.
Circa la negazione ¬,
–per ottenere una dimostrazione di ¬A vera è certo sufficiente mostrare che, se gi aggiungesse A vera alle assunzioni, si otterrebbe l’ assurdo ⊥ vera :
Γ, [A] vere
|
⊥ vera
¬A vera
–d’altronde, l’uso piú immediato che si possa fare di una dimostrazione di ¬A vera è che,
insieme ad una eventuale dimostrazione di A vera si otterrebbe un assurdo:
Γ vere
Γ vere
|
|
A vera
¬A vera
⊥ vera
Si noti che se ¬A viene trattata come se fosse, letteralmente, eguale a A → ⊥ le due regole
su ¬ sono casi particolare delle regole su → .
Circa ⊥, l’ultima regola sulla negazione, fornisce le premesse minime sufficienti per ottenere
⊥ vera ; mentre dall’ assumere ⊥ vera si potrá ottenere qualunque conclusione:
Γ, vere
|
⊥ vera
A vera
schema che ha il nome medievale di ex falso quodlibet.
In logica classica c’ è infine un procedimento dimostrativo usato spesso che coinvolge ¬ e
che, essenzialmente, consiste nel dire che una prova di ¬¬A vera da certe ipotesi è, in effetti,
una prova di A vera . Tenendo conto della prima regola sulla negazione, questo dá lo schema:
Γ vere , [¬A vera ]
|
⊥ vera
A vera
che corrisponde al ragionamento per assurdo: se ¬A vera comporta un assurdo, deve essere
A vera . Questo schema ha il nome medievale di reductio ad absurdum.
A questo punto riassumiamo in forma schematica le regole della deduzione proposizionale
classica nella seguente tabella.
CAPITOLO 6
5
REGOLE DELLA DEDUZIONE NATURALE PROPOSIZIONALE CLASSICA
Introduzione ed eliminazione della congiunzione
D
F
D∧F
D∧F
∧I
∧E
∧E
D∧F
D
F
Introduzione della disgiunzione:
F
D
∨I
∨I
D∨F
D∨F
Eliminazione della disgiunzione:
[D]1
|
C
D∨F
[F ]2
|
C
C
∨ E (1)(2)
Introduzione dell’ implicazione:
[D]1
|
F
→ I(1)
D→F
Eliminazione dell’ implicazione (“modus ponens”):
D
D→F
→E
F
Regola del falso (ex falso quodlibet):
⊥
⊥
D
Introduzione ed eliminazione della negazione:
[D]1
|
⊥
¬D
Reductio ad absurdum
¬ I(1)
[¬D]1
|
⊥
D
¬D
D
⊥
RAA (1)
¬E
6
CAPITOLO 6
Tralasceremo, da qui in avanti, di scrivere ” vera ” accanto alle varie formule. Si noti che per
i connettivi binari le regole si dividono in coppie dette rispettivamente regola/e di introduzione
(I), regola/ di elimiinazione (E): tutte le regole hanno un’ etichetta che le identifica. Infine
accanto alle parentesi quadre ”[ ]” che circondano alcune assunzioni in ∨E, → I, ¬I, RAA è
segnata una cifra che viene riportata nel nome della regola; questo è essenziale per ricordare
che è solo nel momento dell’ applicazione della regola che quella assunzione possa, come si suol
dire, scaricata o disattivata. In generale si possono scaricare interi pacchetti di altre assunzioni
che siano occorrenze della stessa formula presenti come assunzioni in quello stesso sottoalbero
che sta sopra la regole che consente lo scarico, come si vedra’ negli esempi.
2. Alberi di derivazione: come si lavora in Deduzione Naturale
Passiamo ora a definire precisamente cosa sia un “ragionamento ” svolto secondo
queste regole e che impiega delle assunzioni o ipotesi prese in Γ e reca alla conclusione
D.
La nozione, definita per induzione, è quella di albero di derivazione (a.d.d.) di D
(conclusione) da Γ (assunzioni) .
In effetti definiamo dei grafi planari costruiti come “disegni” usando occorrenze di
formule, linee orizzontali (“ di conclusione”), nomi di regole, e la parentesi [,] decorate
con degli indici. –Passo base:
·D
è un a.d.d. di D da {D}, con D ∈ Γ esso si rappresenta scrivendo la formula D.
Questo rappresenta un passo iniziale di una derivazione: consiste nell’ assumere una
ipotesi o assunzione, che a questo punto e’ anche conclusione (da se stessa).
–Passi induttivi (uno per ciascuna regola ):
– Se d, d′ sono rispettivamente a.d.d. di D da Γ, e di F da Γ′ , allora un a.d.d. di
D ∧ F da Γ ∪ Γ′ sara’:
d
d′
D∧F
– Se d è un a.d.d. di D ∧ F da Γ, allora
d
∧E
∧I
d
∧E
E
F
sono a.d.d. rispettivamente di D e di F da Γ.
Si prosegue induttivamente con una clausola per ciascuna regola. Vediamo il caso di
regole che consentono lo scarico di assunzioni.
– Se d e ’ un a.d.d. di F da Γ ∪ {D}, allora
d ⋆ ([D]n
→ I(n)
D→F
è un a.d.d. di D → F da Γ in cui d ⋆ ([D]n ) si ottiene come segue: le assunzioni
presenti in cima all’ albero d che siano occorrenze della formula D – ammesso che ve ne
CAPITOLO 6
7
siano– vengono decorate con le parentesi [, ] e con una (medesima) cifra n ”nuova” (non
ancora utilizzata) che é riportata accanto al nome della regola, e sono quelle considerate
scaricate. (Solitamente esse si saricano tutte, ma basterebbe semplicemente concedere
di poterle scaricare.)
– Se d è un a.d.d. di ⊥ da Γ ∪ {¬D}, allora
d ⋆ ([¬D]n )
RAA(n)
D
è un a.d.d. di D da Γ, in cui d ⋆ ([¬D]n si ottiene da d decorando con [ ] e con un indice
nuovo ( da riportare poi nel nome della regola) le occorrenze di ¬D tra le assunzioni di
d.
Il lettore fará un utile esercizio completando la definizione induttiva di albero di
derivazione di una formula da un insieme di formule, considerando una ad una tutte
le regole della deduzione naturale. Ci sara’ una clausola di chiusura , che impone che
un a.d.d di D da Gamma si puo’ ottenere solo applicando un numero finito di volte
le clausole precedenti. Pertanto un a.d.d. e’ una struttura finita, in cui compare un
numero finito di formule: anche se Γ fosse infinito, in un a.d.d. di A da Γ usiamo solo
un numero finito di assunzioni.
Scriviamo:
A1 vera, · · · , An vera ⊢ B vera
o piú semplicemente:
(∗)
A1 , · · · , A n ⊢ B
per indicare che esiste un albero di derivazione di B le cui assunzioni non scaricate sono
comprese nella lista A1 vera, · · · , An vera.
Puó succedere che siamo in grado di costruire un albero di derivazione con conclusione
B vera ed in cui tutte le assunzioni sono state scaricate e in tal caso scriveremo:
⊢ B vera.
o piu’ semplicemente
⊢ B,
e allora il giudizio B vera sará chiamato una legge logica classica . Inoltre, se Γ ⊆
P ROP , ed A ∈ P ROP, scriviamo
Γ⊢A
per indicare che esiste un a.d.d. di A da Γ : tutte le assunzioni non scaricate appartengono a Γ, mentre le assunzioni che prima o poi si scaricano possono essere formule
qualunque.
8
CAPITOLO 6
Pima di passare agli esempi, una importante
AVVERTENZA
Per come sono fatte le regole, é intuitivo che per ottenere (∗) é necessario che A1 , . . . , An |=
B; questo verrá dimostrato a breve (Teorema di validitá). Negli esercizi è buona norma pertanto
controllare che tra assunzioni e conclusione sia soddisfatta la relazione |= di conseguenza logica;
in mancanza di ció sarebbe tempo perso cercare un albero di derivazione.
Spesso é anche utile ricorrere al seguente principio euristico: per cercare un albero di
derivazione con un dato giudizio conclusivo - se un a.d.d.esiste . . . - si parte dal risultato
come se fosse acquisito e, dal basso verso l’alto, si analizza passo passo quale possa essere la
regola di introduzione che è stata applicata: questo ovviamente se la conclusione non é una
variabile. Ad ogni passo ci si trova con una proposizione di forma piú semplice rispetto a
quella che si vuole dedurre e allo stesso tempo (se la regola prevede scarico) puo’ darsi di aver
ulteriori assunzioni.
Quando la conclusione corrente non sia composta, si passa all’ altro verso, dalle premesse
correnti verso la conclusione corrente. Di solito il problema iniziale viene cosı́ ridotto man
mano ad atri piú semplici: una volta che per questi si trova una deduzione, si incollano i vari
alberi per trovare la soluzione.
[ Questo principio euristico e’ paragonabile al metodo di costruire un biglietto di treno
per raggiungere Vladivostok da Roma con arrivo in una certa data d; uno guarda quali treni
raggiungono Vladivostok il giorno d a partire da Mosca in data d′ . Poi gaurda quali treni
raggiungono Mosca in data d′ a partire da Varsavia in data d” ed infine quali treni raggiungono
Varsavia in data d” a partire da Roma in data d′′′ ]
Questo, tuttavia, non si puo’ prendere come metodo risolutivo sempre efficace: per es. se
la conclusione momentanea sia una disgiunzione, e’ ben raro (ma ovviamente é possibile) che
sia introdotta da ∨I, per il semplice motivo intuitivo che A-vera é piú pregna di informazione
che non A ∨ B- vera. Inoltre la regola classica per eccellenza, ossia la RAA, non si presta
correntemente a questa strategia, in quanto non è una regola di “introduzione” né una regola
di “eliminazione”.
Vediamo alcune sempici casi di a.d.d.:
1.
A ⊢ A, onde ⊢ A → A.
(che qualcuno chiama la legge logica fondamentale): bastano i seguenti due a.d.d.
·A
(o)
e
[A]1
A→A
→ I(1)
Quest’ ultimo significa che prima costruiamo (o) ( in cui A compare sia come assunzione
che come conclusione) e poi applichiamo → I, scaricando la A, che é presente in (o) in quanto
CAPITOLO 6
9
assunzione. Potremmo procedere in modo diverso:
[A]1
[A]1
∧I
A∧A
∧I
A
→ I(1)
A→A
Questo sottolinea che se esiste un a.d.d. per (⋆) allora ne esistono infiniti: le soluzioni di un
esercizio possono ben essere diverse.
2.
A, B ⊢ A
L’a.d.d. (o) serve anche per (ii).
A ⊢ A ∨ A; ed anche A ∨ A ⊢ A
La prima si puó ottenere con una applicazione di ∨I. Per la seconda usiamo ∨E : i due
sottalberi ausiliarii sono due copie di (o) :
3.
A∨A
[A]1
[A]2
A
4.
B ⊢ A → B Ecco un a.d.d.:
∨ E(1, 2)
B
→ −I
A→B
in cui si ha un’ applicazione del tutto regolare della regola →-I. Oppure un’ altro:
[A]1
B
∧I
A∧B
∧E
B
→ I(1)
A→B
ESEMPIO 1.
Mostrare che:
A → B, A → C ⊢ A → (B ∧ C).
Naturalmente il controllo di validita’ |= é positivo.
(a).Cerchiamo di costruire un albero che abbia come foglie ”vive” (non scaricate) le premesse
A → B, A → C (che possono anche comparire piú di una volta ) e come ”radice” la conclusione
A → (A ∧ B) :
A → B, A → C
\|/?
A → (A ∧ B)
Si tratta di riempire il percorso per ora incognito indicato come “\|/?”.
La conclusione corrente‘e una implicazione (da A a B ∧ C; ) tentiamo pertanto di trovare un
albero che utilizza – oltre alle premesse precedenti, anche – la premessa A e che concluda con
B ∧ C. (Se ci riusciamo, poi avremo risolto il problema precedente, per mezzo della regola di
→-I ).
10
CAPITOLO 6
(b)Pertanto, ci spostiamo al problema di trovare un albero come segue:
A → B, A → C, A
\|/?
B∧C
A questo punto la conclusione è una congiunzione; pertanto proviamo a trovare due alberi
che dalle date premesse concludano rispettivamente con B e con C; se ci riusciamo, poi con la
regola di ∧-I, avremo anche risolto il problema (b) - e quindi anche (a).
Cerchiamo allora: (c1) un albero:
A → B, A → C, A
\|/?
B
ed inoltre
(c2) ed un albero:
A → B, A → C, A
\|/?
C
Per i sottoproblemi (c1) e (c2), non possiamo continuare allo stesso modo, ossia ”smontando”
la conclusione: sia B che C potrebbero essere proposizioni atomiche. Tenteremo con le regole
di eliminazione di passare dalle premesse di (c1) e di (c2) alle loro conclusioni. Nel caso in
esame, i sottoproblemi (c1) e (c2) hanno delle soluzioni immediate, usando la regola del modus
ponens:
A
A→B
A
A→C
;
.
B
C
A questo punto possiamo presentare nella sua interezza una soluzione del problema, partendo
adesso dalle foglie (assunzioni) e procedendo verso la radice:
[A]1
A→B
B
(→ E)
B∧C
A → (B ∧ C)
[A]1
A→C
(→ E)
C
(∧I)
(→ I)(1)
Si noti che in ciascuna applicazione di regole segnaliamo di quale regola si tratti. Inoltre che
nell’ applicazione della regola →-I abbiamo anche segnalato che in questo momento si stanno
scaricando entrambe le occorrenze della premessa A segnate entrambe con 1, e a questo punto
entrambe sono state messe entro parentesi [ ]. Restano quindi attive - non scaricate - le sole
assunzioni A → B, A → C.
ESEMPIO 2.
Mostrare che
A → C, B → C ⊢ (A ∨ B) → C.
CAPITOLO 6
11
Il problema è di trovare un albero:
A → C, B → C
\|/?
(A ∨ B) → C
Proviamo a ridurci a quello di trovare un albero
A → C, B → C, (A ∨ B)
\|/?
C
Qui C non non si presenta come composta; pertanto a questo punto tenteremo di far ricorso
alle regole di eliminazione. Siccome una premessa qui è una disgiunzione, è naturale provare
con la regola ∨-E. Cerchiamo pertanto un albero (b1):
A → C, B → C, A
\|/?
C
nonchè un albero (b2):
A → C, B → C, B
\|/
C
se ci riusciamo, potremo applicare ∨-E (scaricando A e B):
A∨B
(b1)
(b2)
.
C
Ora è chiaro che (b1) e (b2) si possono trovare usando →E:
B
B→C
A→C
.
C
C
(Si noti che non abbiamo divuto usare tutte le ipotesi di (b1) e (b2), ma solo quella che occorre).
In conclusione un albero di derivazione che risolve il problema sara’:
A
[A ∨ B]3
[A]1
A→C
(→ E)
[B]2
C
B→C
C
C
(A ∨ B) → C
(→ E)
(∨E)(1)(2)
(→ I)(3)
Anche qui si mettono tra parentesi quadre – al momento dello scarico – le formule che via via
si scaricano, segnalando anche in base alla applicazione di quale regola si effettua tale scarico.
ESEMPIO 3.
Mostrare che:
A ∨ B, C ⊢ (A ∧ C) ∨ (B ∧ C).
La conclusione è una disgiunzione, e saremmo tentati di ipotizzare che essa sia stata prodotta
da ∨-I. Questo vorrebbe dire che dalle assunzioni A ∨ B, C vorremmo poter dedurre A ∧ C
(oppure l’altra B ∧ C). Ma ció non è possibile in generale: se in una certa valutazione B, C
12
CAPITOLO 6
sono vere e A è falsa, allora A ∨ B sará ancora vera, C è vera ma la presunta conclusione A ∧ C
è falsa.
Tentiamo allora con le regole di eliminazione: siccome tra le assunzioni solo la A ∨ B si
presenta come composta, proveremo a ridurre il problema al seguente: trovare due alberi (b1):
C, A
\|/?
(A ∧ C) ∨ (B ∧ C)
e (b2):
C, B
\|/?
(A ∧ C) ∨ (B ∧ C)
Dopodichè potremo utilizzare ∨E per risolvere il problema:
A∨B
(b1)
(b2)
(A ∧ C) ∨ (B ∧ C)
- notate che in questa applicazione di ∨-E scaricheremo le assunzioni A e B presenti in cima a
(b1) e (b2)-.
Trovare (b1) e (b2) non è difficile: riproviamo con il solito principio, e cioè - per (b1) - riduciamo il problema a dedurre da A, C una delle due componenti della disgiunzione conclusiva:
A
C
(∧I)
A∧C
(∨I)
(A ∧ C) ∨ (B ∧ C)
ed in modo simile si trova (b2). Allora un albero di derivazione che risolve il problema iniziale
è:
[A]1
A∨B
C
[B]2
∧I
A∧C
∨I
(A ∧ C) ∨ (B ∧ C)
C
∧I
B∧C
∨I
(A ∧ C) ∨ (B ∧ C)
(A ∧ C) ∨ (B ∧ C)
∨ E(1)(2)
ESEMPIO 4.
Mostrare che (A → B) → ((¬B) → (¬A) è una legge logica.
Schematizziamo : in primo luogo, proviamo a trovare un albero della forma:
A→B
\|/?
(¬B) → (¬A)
Da qui, con →I e scaricando la sola assunzione A → B, avremmo risolto il problema. Questo
a sua volta ci suggerisce di cercare:
A → B, ¬B
\|/?
¬A
CAPITOLO 6
13
Esso a sua volta ci suggerisce di cercare:
A → B, ¬B, A
\|/?
⊥
A questo punto lavoriamo sulle assunzioni A → B, ¬B, A con regole di eliminazione allo scopo
di ottenere ⊥: ció si puó avere per eliminazione della negazione da B, ¬B ; a sua volta B si
ricava da A, A → B con la regola di →E. Un albero che risolve il problema è il seguente (tutte
le assunzioni sono prima o poi scaricate):
[A → B]3
[A]1
B
⊥
→E
¬I(1)
¬A
¬B → ¬A
(A → B) → ((¬B → (¬A))
[¬B]2
¬E
→ I(3)
→ I(2)
Degli ultimi esempi diamo direttamente una soluzione.
ESEMPIO 5.
(¬(¬(¬A))) ⊢ ¬A.
Ecco una possibile soluzione:
[A]2
¬¬¬A
⊥
¬A
[¬A]1
⊥
¬¬A
¬I(2)
¬E
¬I(1)
¬E
ESEMPIO 6.
⊢ (¬(¬(A ∧ B))) → ((¬¬A) ∧ (¬¬B)).
Una soluzione possibile si ottiene facendo prima:
[A ∧ B]1
A
∧E
⊥
¬(A ∧ B)
[¬A]2
¬I(1)
⊥
¬E
¬¬(A ∧ B)
¬E
¬I(2)
¬¬A
D’altro lato con lo stesso schema si ottiene la conclusione ¬¬B, ed infine si aggiunge come
passo finale una applicazione di ∧I per ottenere la conclusione desiderata.
ESEMPIO 7. (”Tertium non datur”.)
⊢ A ∨ (¬A).
14
CAPITOLO 6
Una possibile derivazione:
[A]1
A ∨ (¬A)
∨I
[¬A]2
[¬(A ∨ (¬A))]3
⊥
¬A
A ∨ (¬A)
¬E
¬I(1)
∨I
[¬(A ∨ (¬A))]4
⊥
¬¬A
⊥
A ∨ (¬A)
¬E
¬I(2)
¬E
RAA(3)(4)
ESEMPIO 8.(”Doppia negazione.”)
⊢ (¬¬A) → A.
Ecco una possibile derivazione:
[¬A]1
[¬¬A]2
A
⊥
(¬¬A) → A
¬E
RAA(1)
→ I(2)
ESEMPIO 9.
⊢ (A → B) ∨ (B → A).
Si puó ottenere come segue:
[¬A]4
[A]3
\|/
A ∨ (¬A)
(Esempio7)
→I
B→A
∨I
(A → B) ∨ (B → A)
B
[A]1
⊥
¬E
(⊥)
→ I(1)
A→B
∨I
(A → B) ∨ (B → A)
(A → B) ∨ (B → A)
∨ E(3)(4)
In questo caso, sopraA∨¬A occorre riscrivere tutto un’ a.d.d. (per esempio, quello dell’esempio
7). Il lettore fará un utile esercizio provando con altre deduzioni.
ESEMPIO 10.
A → B ⊢ (¬A) ∨ B.
[¬A]1
(¬A) ∨ B
∨I
⊥
[¬((¬A) ∨ B)]2
¬E
A→B
RAA(1)
A
B
(¬A) ∨ B
→E
∨I
⊥
(¬A) ∨ B
RAA(2)(3)
[¬((¬A) ∨ B)]3
CAPITOLO 6
15
ATTENZIONE. Presentiamo qui una presunta ”derivazione” che vorrebbe mostrare che
⊢ A → B, quali che siano A, B proposizioni.
[A]3
[¬A]1
⊥
¬¬A
¬E
¬I(1)(2)(ERRORE !)
⊥
[¬A]2
¬E
⊥
B
→ I(3)
A→B
Nell’ applicare la regola ¬I si poteva scaricare la occorrenza 1 della formula ¬A, ma non
la occorrenza 2 della stessa formula: questa non sta nel sottoalbero la cui ultima regola
e’ ¬I .
3. ESERCIZI DI DEDUZIONE NATURALE PROPOSIZIONALE.
Gli esercizi da 1 a 30 sono dal piu’ facile al piu’ difficile; gli altri sono invece esercizi
d’esame degli ultimi anni. 1. (A ∧ B) ∨ A ⊢ A.
2. A ⊢ (A ∧ B) ∨ A.
3. A → B, B → A ⊢ (A ∨ B) → (A ∧ B).
4. (¬A) ∨ B ⊢ A → B.
5. A ∨ C, B ∨ C ⊢ (A ∧ B) ∨ C.
7. A ∨ B ⊢ B ∨ A.
8. A ∧ B ⊢ B ∧ A.
9. A ∧ (B ∨ C) ⊢ ((A ∧ B) ∨ (A ∧ C)).
10. ⊢ A → (¬¬A).
11. ⊢ (A → (B → C)) → ((A ∧ B) → C)).
12. ⊢ ((A ∧ B) → C)) → (A → (B → C)).
13. ⊢ (¬A) → (¬¬¬A).
14. (A ∨ B) → (A ∧ B) ⊢ A → B.
15. ⊢ A → (B → A).
16. A → (¬A) ⊢ ¬A.
17. (¬A) ∨ B ⊢ A → B.
18. (¬A) ∨ (¬B) ⊢ ¬(A ∧ B).
19. A → B ⊢ ¬(A ∧ (¬B)).
20. A ∧ B ⊢ ¬((¬A) ∨ (¬B)).
21. ¬(A → B) ⊢ A.
22.(Legge di PEIRCE) ((A → B) → A) ⊢ A.
23. ¬(A ∧ B) ⊢ (¬A) ∨ (¬B).
24. ¬(A ∧ (¬B)) ⊢ A → B.
25. ¬((¬A) ∨ (¬B)) ⊢ A ∧ B.
26.(”Consequentia mirabilis”) ⊢ ((¬A) → A) → A.
27. (¬A) → (¬B) ⊢ B → A.
16
CAPITOLO 6
28. (¬A) → B ⊢ A ∨ B.
29. ¬((¬A) ∧ (¬B)) ⊢ A ∨ B.
30. (¬A → B), B → C, ¬C ⊢ A.
Ecco alcuni suggerimenti per gli esercizi (ma ci sono altre soluzioni)
(N.21). Osservare prima che ¬A ⊢ A → B - si usi l’esercizio 4 -. Allora con
l’assunzione ¬(A → B) si ottiene ⊥. Poi con RAA, etc.
(N.22). Utilizzando l’esempio 4, ottenere ¬(A → B) dalle assunzioni (A → B) →
A, ¬A. Quindi, con l’esercizio 21, ricavare A; di nuovo utilizzare l’assunzione ¬A per
avere ⊥, ad infine con RAA ottenere A (scaricando ¬A).
(N.23). Negando la conclusione -ossia assumendo ¬((¬A ∨ (¬B))- ricavare A e B assumendo anche, per poi scaricarle con RAA - rispettivamente ¬A e ¬B. Cosı́ si ricava
A ∧ B e quindi ⊥, usando l’assunzione ¬(A ∧ B). Si conclude con RAA.
(N.25). Prima si usi l’esercizio 23: insieme all’assunzione attuale si ricava ⊥; e si
conclude con RAA.
Nel prossimo gruppo di esercizi, CONTROLLARE PRIMA CHA VALGA LA CONSEGUENZA SEMANTICA |= e solo in caso positivo, produrre un a.d.d.
31. A, B, ¬C ⊢ ¬(A → (B → C)) [??]
32. ¬(A → B) ⊢ B → A [??]
33. A ∨ (B → C) ⊢ B → A;
A ∨ (B → C) ⊢ C [??]
34. A ∨ (B → C) ⊢ (B → A) ∨ C [??]
35. ¬(A → C) ⊢ (¬(A → B)) ∨ (¬(B → C)) [??]
36. (A → B) ∨ C ⊢ A → (B ∨ C) [??]
37. (A → B) → (A ∧ C) ⊢ A [??]
38. B → C ⊢ C ∨ (¬B) [??]
39. ¬(B → C), A → (¬B) ⊢ A → C [??]
40.A ∨ (B → C) ⊢ B → A;
A ∨ (B → C) ⊢ C [??]
41. A ∨ (B → C) ⊢ (B → A) ∨ C [??]
42. (A → B) ∨ (A → C) ⊢ A → (B ∨ C) [??]
43. (¬A) → B ⊢ A ∨ B [??]
44.((A → B) → C) ⊢ A ∨ C [??]
45.] A, ¬(B → C) ⊢ ¬((A ∧ B) → C) [??]
46. B ∨ ¬C, A → C ⊢ A → B [??]
47. (A → B) → C ⊢ A ∨ C [??]
48.A, B, ¬B ∨ ¬C ⊢ ¬(A → C) [??]
49. C → A, (¬C) → B ⊢ A ∨ B [??]
50. (¬A) → ((¬B) → C) ⊢ (A ∨ B) ∨ C [??]
51. ⊢ (A → B) ∨ (A → ¬B) (??)
4. L’ algebra di Lindenbaum-Tarski
Abbiamo trascurato il connettivo ↔, che consideriamo come definito: A ↔ B sta per
(A → B) ∧ (B ↔ A). Pertanto, Γ ⊢ A ↔ B equivale alle due Γ ⊢ A → B e Γ ⊢ B → A,
CAPITOLO 6
17
oppure anche equivale alle due Γ, A ⊢ B e Γ, B ⊢ A. Mentre Γ, A ↔ B ⊢ C equivale a
Γ, A → B, B → A ⊢ C.
La dimostrazione delle seguenti semplici proprietá (nonostante il nome pomposo) è
lasciata per esercizio al lettore:
Proposizione 1.
(1) (Teorema di Finitezza) Γ ⊢ D sse esiste un insieme finito
F ⊆ Γ tale che F ⊢ D.
(2) (Teorema di Deduzione) Γ ∪ {A} ⊢ D sse Γ ⊢ A → D.
(3) ⊢ D sse ⊢ D ↔ ¬⊥
(4) ⊢ ¬D sse ⊢ D ↔ ⊥
Consideriamo ora la relazione binaria ∼ in P ROP definita da
A ∼ B sse ⊢ A ↔ B;
(cioé sse A ⊢ B e B ⊢ A).
Proposizione 2. La relazione ∼ è di equivalenza in P ROP ; essa è una congruenza
dell’ algebra delle formule PROP.
DIM. E’ pressochè ovvio che ∼ è riflessiva, simmetrica e transitiva. Si tratta poi di
mostrare che se A ∼ A′ , B ∼ B ′ allora (A B) ∼ (A′ B)′ e ¬A ¬A′ . Vediamone
alcune, lasciando le altre verifiche come esercizio al lettore. Caso: ∨. Siano d, d′ alberi di
derivazione senza assunzioni non scaricate e di conclusioni rispettive A → A′ , B → B ′ :
essi esistono per l’ ipotesi induttiva. Allora A∨B → A′ ∨B ′ si trova facilmente mediante:
d
A → A′
[A]1
A∨B
A′
A′ ∨ B ′
d′
B → B′
[B]2
→E
∨I
B′
A′ ∨ B ′
∨I
→E
∨ E(1)(2)
A′ ∨ B ′
E simmetricamente si procede per A′ ∨ B ′ → A ∨ B.
Vediamo il caso →: se d è un a.d.d. derivazione di A′ → A, e d′ é un a.d.d. di B → B ′ ,
per provare che A → B ⊢ A′ → B ′ basta osservare:
[A′ ]1
d
A′ → A
A
→E
B
A→B
B′
A′ → B ′
→E
→ I(1)
d′
B → B′
→E
Proposizione 3. La struttura quoziente L= PROP/ ∼ è un’ algebra di Boole, nota
come algebra di Lindembaum–Tarski della logica proposizionale classica.
18
CAPITOLO 6
DIM. Si tratta di una serie di esercizi di derivazione, in corrispondenza degli assiomi
di algebra di Boole. Notiamo che le costanti di tale struttura sono:
0 = ⊥/ ∼= {D| ⊢ ¬D}; 1 = (¬⊥)∼ = {D| ⊢ D}.
Per esempio, occorre dimostrare che
A ∨ (A ∧ B) ∼ A;
⊢ A ∨ ¬A;
⊢ ¬(A ∧ ¬A).
Per la prima, una delle implicazioni si ottiene da ∨I. per l’altra, si ha:
A ∨ (A ∧ B)
[A ∧ B]2
[A]1
A
∧E
∨ E(1)(2)
A
Per la seconda, è la legge del terzo escluso. Per la terza, si ha:
[A ∧ ¬A]1
A
[A ∧ ¬A]1
∧E
¬A
⊥
¬(A ∧ ¬A)
¬I(1)
∧E
¬E
Le altre verifiche sono lasciate per esercizio. Per quanto se ne sa a questo punto, l’ algebra L potrebbe essere degenere, ridotta ad
un solo elemento (ossia 0 = 1). Questo significherebbe che ⊢ ⊥. Finora niente proibisce
che ci sia un’ a.d.d. con tutte le assunzioni scaricate e di conclusione ⊥. Escluderemo
presto questa disastrosa possibilita’ (vorrebbe dire che abbiamo elaborato delle regole
sbagliate), dopo aver confrontato la deducibilitá con la validitá semantica.
5. Il teorema di validita’ o correttezza
Teorema 1. (Teorema di validita’) Se Γ ⊆ P ROP, D ∈ P ROP e se Γ ⊢ D, allora
Γ |= D.
DIM. Risulta che le regole di derivazione ”rispettano la verità ”: in una qualunque
valutazione v che renda vere le premesse (non scaricate) di una qualunque regola, anche la
conclusione è necessariamente valutata come vera. Che sia cosı́, é intuitivamente chiaro
per il fatto che le singole regole sono state prsentate proprio come modi di trasmettere
la verita’ dalle assunzioni alle conclusioni.
La dimostrazione dell’ enunciato è per induzione sull’ albero di derivazione d di D da
assunzioni non scaricate appartenenti a Γ.
– (Passo base): se d è un punto: ·D, vuol dire che D ∈ Γ e la conclusione è ovvia.
– (Passo induttivo) Supponiamo ora che d′ , d′′ siano a.d.d. rispettivamente di D, F da
Γ e d sia ottenuto applicando come ultima regola la ∧-I:
d=
d′
D
d′′
F
D∧F
∧I
CAPITOLO 6
19
Per ipotesi induttiva, Γ |= D, Γ |= F ; è allora immediato che Γ |= D ∧ F.
Si procede in modo analogo per tutte le altre regole. Supponiamo che l’ ultima regola
applicata in D sia ∨E; avremo allora derivazioni d′ , d′′ , d′′′ rispettivamente di D ∨ F, C, C
da Γ, Γ ∪ {D}, Γ ∪ {F }. La derivazione D sará allora
d′
D∨F
d′′ d′′′
C C
∨E
C
Per ipotesi induttiva, Γ |= D ∨ F, Γ ∪ {D} |= C, Γ ∪ {F } |= C. È allora facile concludere
che Γ |= C : se cosı́ non fosse, esisterebbe una valutazione v tale che v(Γ) ⊆ {1}, v(C) =
0; allora peró v(D ∨ F ) = 1; se v(D) = 1, allora dovrebbe essere v(C) = 1 poichè
Γ ∪ {D} |= C; ed analogamente se v(F ) = 1.
Lasciamo gli altri casi alla verifica del lettore.
Il teorema di validita’, oltre a valorizzare la deduzione naturale come un metodo che
produce solamente relazioni di conseguenza valide, è anche utile per asserire che non
valga una certa relazione di deducibilitá : per esempio
Corollario 1. La deduzione naturale è consistente, ossia ̸⊢ ⊥.
(Altrimenti dovrebbe essere |= ⊥ : assurdo.
Corollario 2. L’ algebra di Lindenbaum-Tarski L è infinita.
(Infatti, se pi , pj sono lettere proposizionali distinte, si ha ovviamente pi ̸|= pj , pj ̸|= pi ,
allora per il teorema di validitá pi ̸∼ pj .)
6. Il teorema di Completezza
Dobbiamo ora chiudere il discorso mostrando che la deduzione naturale puó produrre
tutte le relazioni di conseguenza valide. Intanto l’ enunciato:
Teorema 2. (Teorema di completezza) Se Γ ⊆ P ROP, D ∈ P ROP e se Γ |= D, allora
Γ ⊢ D.
Prima di procedere alla dimostrazione, alcuni importanti concetti.
Diremo che Γ ⊆ P ROP è inconsistente se Γ ⊢ ⊥; che Γ è consistente se non è
inconsistente; che Γ è deduttivamente chiuso se ogni volta che Γ ⊢ D, si ha D ∈ Γ; ed
infine che Γ e’massimale consistente se è consistente e per ogni insieme ∆ consistente,
se Γ ⊆ ∆ allora Γ = ∆. Quindi Γ é massimale consistente se e solo se é consistente e per
ogni D ∈
/ Γ, si ha che Γ ∪ {D} é inconsistente.
Una singola formula A sara’ consistente se A ̸⊢ ⊥; altrimenti e’ inconsistente.
Proposizione 4.
(1) Le seguenti sono equivalenti:
i Γ è inconsistente;
ii Per ogni D ∈ P ROP, Γ ⊢ D;
iii Esiste D ∈ P ROP tale che Γ ⊢ D, Γ ⊢ ¬D;
20
CAPITOLO 6
(2) Le seguenti sono equivalenti:
i Γ è consistente;
ii Esiste D ∈ P ROP tale che Γ ̸⊢ D;
iii Non esiste D ∈ P ROP, tale che Γ ⊢ D e Γ ⊢ ¬D.
(3) Γ ∪ {D} è inconsistente sse Γ ⊢ ¬D; Γ ∪ {¬D} è consistente sse Γ ̸⊢ D.
(4) L’ unione di una catena (per l’ inclusione) di insiemi consistenti è consistente.
(5) Un insieme massimale consistente è deduttivamente chiuso.
(6) Le seguenti sono equivalenti se Γ è consistente:
(i) Γ è massimale consistente;
(ii) Per ogni D ∈ P ROP, o D ∈ Γ oppure ¬D ∈ Γ;
(iii) Per ogni D, F ∈ P ROP, se Γ ⊢ D ∨ F, allora D ∈ Γ oppure F ∈ Γ.
DIM. Circa (1): è pressoché ovvio che i ⇒ ii ⇒ iii ⇒ i.
(2) segue da (1).
Circa (3): Se Γ ∪ {D} ⊢ ⊥, allora per ¬I, Γ ⊢ ¬D; viceversa, se Γ ⊢ ¬D, allora da
Γ ∪ {D} si deducono sia D che ¬D.
Circa (4): sia Γi , i ∈ I una catena di insiemi consistenti e sia Γ la loro unione. Se
Γ ⊢ ⊥, esisteranno F1 , . . . , Fn ∈ Γ, con F1 , . . . , Fn ⊢ ⊥; allora esiste un j ∈ I con
F1 , . . . , Fn ∈ Γj ; allora peró Γj sarebbe inconsistente.
Circa (5): sia Γ un insieme massimale consistente e sia Γ ⊢ D; se D ∈
/ Γ, allora Γ∪{D}
è inconsistente, onde Γ ⊢ ¬D; allora peró Γ sarebbe inconsistente.
Circa 6: assumiamo (i); se D ∈
/ Γ, allora Γ ∪ {D} è inconsistente, onde Γ ⊢ ¬D;
per 5, concludiamo che ¬D ∈ Γ : quindi vale (ii). Assumiamo (ii) e dimostriamo (iii):
se Γ ̸⊢ D e Γ ̸⊢ F, in particolare avremmo D, F ∈
/ Γ; allora sia Γ ∪ {D} che Γ ∪ {F }
sono inconsistenti; pertanto allora Γ ⊢ ¬D ∧ ¬F ; allora peró Γ ⊢ ¬(D ∨ F ); essendo Γ
consistente, concludiamo che Γ ̸⊢ D ∨ F.
Assumiamo infine (iii): in particolare, per ogni formula D, avremo Γ ⊢ D ∨¬D; allora,
se D ∈
/ Γ, avremo ¬D ∈ Γ e pertanto Γ ∪ {D} è inconsistente. Dunque Γ è massimale
consistente. La proprietá espressa nel punto (6)(ii) suggerisce un sinonimo per ”consistente massimale”: Γ ⊆ P ROP è detto completo se per ogni F ∈ P ROP, si verifica una ed una sola
tra le: F ∈ Γ, ¬F ∈ Γ. Dunque ”completo” = ”massimale consistente”.
Circa l’ esistenza di insiemi massimali consistenti, possiamo far ricorso alla semantica,
per osservare che se v è una valutazione proposizionale, l’ insieme
M = v −1 ({1}) = {D|v(D) = 1}
è completo: se M ̸⊢ D, allora D ∈
/ M, quindi v(D) = 0, quindi v(¬D) = 1, quindi
¬D ∈ M ed allora M ⊢ ¬D.
Anzi, di questo tipo sono tutti i possibili insiemi consistenti massimali:
CAPITOLO 6
21
Proposizione 5. Sia M un insieme massimale consistente; esiste allora una valutazione
v tale che M = v −1 ({1}).
DIM. Si consideri la valutazione definita per p lettera proposizionale da:
v(p) = 1 sse p ∈ M.
E’ facile vedere, per induzione su F che allora:
v(F ) = 1 sse F ∈ M.
Infatti per le lettere proposizionali si tratta della definizione. Se vale per D, F , avremo
v(D ∧ F ) = 1 sse v(D) = v(F ) = 1 sse D, F ∈ M sse D ∧ F ∈ M ; l’ ultimo passaggio
essendo dovuto al fatto che M sia deduttivamente chiuso. Inoltre v(¬D) = 1 sse v(D) =
0 sse D ∈
/ M sse ¬D ∈ M.
Dal teorema di correttezza, se Γ e’ inconsistente, allora e’ insoddisfacibile; come dire
che (soddisfacibile) ⇒ (consistente). Il viceversa non e’ affatto scontato, in quanto dal
dato che nessun albero di deduzione con premesse non scaricate in Γ possa terminare
con ⊥, non si vede come trovare una valutazione che renda vere tutte le formule di Γ. Ma
la proposizione precedente fornisce una via d’ uscita, che si realizza tramite il seguente
lemma:
Lemma 1. (Lemma di Lindenbaum) Per ogni insieme consistente Γ ⊆ P ROP esiste
un insieme massimale consistente M con Γ ⊆ M.
DIM. La dimostrazione si puó eseguire facendo uso del lemma di Zorn, oppure piú
direttamente .
(Ia.dimostrazione). Si consideri la famiglia C degli insiemi consistenti contenenti Γ,
parzialmente ordinata dall’ inclusione.C non é vuota: Γ ∈ C. Siccome l’ unione di una
catena di insiemi in C appartiene a C, possiamo applicare il lemma di Zorn, ed ottenere
che esiste un insieme M massimale in CC. Resta da vedere che in effetti M sia massimale
consistente (ed ovviamente Γ ⊆ M ) : M é consistente perché appartiene a C; sia H un
insieme consistente con M ⊆ H; allora Γ ⊆ H; quindi H ∈ C, quindi (essendo M
massimale in C, H = M.
(IIa.dimostrazione.) Siccome P ROP è un insieme numerabile, sia (Fn |n ∈ ω) una
successione infinita contenente tutte e sole le formule proposizionali. Definiamo una
successione di insiemi Γn , per induzione su n ∈ ω : Γ0 := Γ; Γn+1 := Γn , se Γn ∪ {Fn }
inconsistente; altrimenti Γn+1 := Γn .
∪ Si ha cosı́ una catena (per l’ inclusione) di insiemi consistenti; la loro unione M =
(Γn |n ∈ ω) è pertanto consistente. Dimostriamo che M é massimale consistente (
ed ovviamente contiene Γ). Sia D ∈
/ M, allora D = Fm per un opportuno m ∈ ω; Se
M ∪{Fm } fosse consistente, e siccome Γm ∪{Fm } ⊆ M ∪{Fm }, anche Γm ∪{Fm } sarebbe
consistente, onde D = Fm ∈ M. Pertanto M è massimale consistente.
La prima dimostrazione si applica direttamente anche ad un insieme piu’ che numerabile di lettere proposizionali. Per la seconda dimostrazione, si potrebbe estrenderla a
questo caso, ma lavorando per induzione transinita.
22
CAPITOLO 6
La dimostrazione del teorema di completezza procede ora come segue.
Si assuma che Γ ̸⊢ D; allora Γ ∪ {¬D} è consistente; esso si puó dunque estendere ad
un insieme massimale consistente M ; pertanto esiste una valutazione v con v(M ) = {1},
ed in particolare v(¬D) = 1; cioe’ v(D) = 0. Allora per definizione Γ ̸|= D. 7. Completezza e compattezza
7.1. Intanto ripetiamo che il teorema di completezza vale per un insieme infinito qualunque di
cardinalita’ α ≥ ω di lettere proposizionali. Sia P ROPα l’insieme delle formule proposizionali
su αlettere proposizionali.
Essenzialmente, il teorema di completezza (per un qualunque insieme infinito di lettere
proposizionali) e’ equivalente al
Teorema 3. (Teorema di esistenza del modello). Per ogni cardinale α ≥ ω, sia Γ ⊆ P ROPα ;
se Γ è consistente allora Γ è soddisfacibile.
Come corollario, otteniamo una prova alternativa del teorema di compattezza:
Corollario 3. (Teorema di compattezza proposizionale)
Per ogni α ≥ ω,sia Γ ⊆ P ROPα ; allora Γ è soddisfacibile se (e solo se) ogni suo sottinsieme
finito è soddisfacibile.
Ció segue dalla banale osservazione vista sopra (Teorema di Finitezza) che Γ ⊢ D sse per
qualche sottinsieme finito F di Γ. Pertanto se Gamma é insoddisfacibile, allora Γ |= ⊥, allora
Γ ⊢ ⊥, quindi per un qualche F finito contenuto in Γ, avremo F ⊢ ⊥, e quindi (per il teorema
di validita’) F |= ⊥, ossia F e’ insoddisfacibile.
7.2. Possiamo domandarci se valga anche il contrario, ossia se dal teorema di compattezza
proposizionale segua il teorema di completezza. La risposta e’ positiva.
Per vedere i passaggi, diamo dei nomi agli enunciati seguenti:
(Teorema dell’ ultrafiltro booleano)
Per ogni algebra di boole B e per ogni insieme ∅ ̸= F ⊆ B con la f.i.p., esiste un ultrafiltro
U di B con F ⊆ U.
(Per ora, dimentichiamo che tale teorema e’ stato dimostrato usando il lemma di Zorn).
(Teorema di completezza debole)
Per ogni α ≥ ω, per ogni A ∈ P ROPα , se |= A allora ⊢ A.
I passaggi sono ora i seguenti:
I. Dal teorema di compattezza proposizionale segue il teorema dell’ ultrafiltro booleano.
II. Dal teorema dell’ ultrafiltro booleano segue il teorema di completezza debole.
III. Il teorema di completezza e’ equivalente alla congiunzione del teorema di compattezza
e del teorema di completezza debole.
Quindi: dal teorema di compattezza proposizionale segue il teorema di completezza.
Dim.[I.]
Se B e’ un’ algebra di Boole finita, ed F = {b1 , . . . , bn } ⊆ B la f.i.p. significa che b1 ∧· · ·∧bn ̸=
0. Allora esiste un atomo a di B con a ≤ b1 ∧ · · · ∧ bn ; il filtro generato da a e’ un ultrafiltro
di B ed ovviamente contiene F.
CAPITOLO 6
23
Nel caso B infinita di cardinalita’ α, useremo la compattezza proposizionale. Per ogni b ∈ B,
fissiamo una lettera proposizionale pb ; quindi definiamo l’ insieme di formule:
Γ = {p1 } ∪ {pa∧b ↔ (pa ∧ pb )|a, b, ∈ B} ∪ {pa∨b ↔ (pa ∨ pb )|a, b, ∈ B}.
Ora mostriamo che Γ e’ finitamente soddisfacibile. Sia F un sottinsieme finito di Γ, e
consideriamo il sottinsieme F ∗ di B:
F ∗ = {b ∈ B|pb compare in qualche formula di F }.
Consideriamo la sottalgebra S generata da F ∗ in B : S e’ finita, quindi ha almeno un
ultrafiltro; sia U0 uno di questi. Consideriamo l’ assegnazione v0 definita da
v0 (px ) = 1
se e solo se
x ∈ U0 .
Indichiamo con v0 anche la valutazione che estende tale assegnazione. Si ha
(•)
per ogni formula A ∈ F, v0 (A) = 1.
Per dimostrare (•), basta considerare il motivo per cui A ∈ F. Se A = p1 , ovviamente v0 (p1 ) =
1. Se A = pa∧b ↔ (pa ∧ pb ) ∈ F avremo: a, b, a ∧ b ∈ F ∗ ⊆ S. Avremo che le seguenti sono
equivalenti:
v0 (pa∧b ) = 1,
a ∧ b ∈ U0 (per definizione),
a, b ∈ U0 (U e’ un ultrafiltro),
v0 (pa ) = 1 = v0 (pb ),
v0 (pa ∧ pb ) = 1.
Un modo del tutto simile, si lavora se A = pa∨b ↔ (pa ∨ pb ) : ne segue (•). Quindi F e’
soddisfacibile. Allora Γ e’ soddisfacibile: esistera’ una valutazione v tale che v(Γ = {1} :
definiamo U ⊆ B :
U = {a ∈ B|v(pa ) = 1}.
E’ ora facile concludere che U é un ultrafiltro di B; per esempio ,sono equivalenti le seguenti
(tenendo conto che v(pa∨b ↔ (pa ∨ pb )) = 1, e quindi v(pa∨b ) = v(pa ∨ pb ):
A ∨ B ∈ U,
v(pa∨b ) = 1,
v(pa ∨ pb ) = 1,
v(pa ) = 1 oppure v(p) = 1,b)
a ∈ U oppure b ∈ U.
Dim.[II.] Proveremo la contronominale: se ̸⊢ D allora ̸|= D. Se ̸⊢ D, allora nell’ algebra di
Lindembaum-Tarski, L, [D]∼ ̸= 1 e quindi [¬D]∼ ̸= 0. Esiste per ipotesi un ultrafiltro U di L
con [¬D]∼ ∈ U. D’ altronde, definiamo l’ assegnazione v mediante
v(pi ) = 1 sse
[pi ]∼ ∈ U ;
Si procede ora dimostrando per induzione su F che per ogni formula F :
v(F ) = 1 sse [F ]∼ ∈ U
(lasciamo i facili dettagli al lettore). In particolare v(¬D) = 1, ed infine v(D) = 0, e cioè ̸|= D.
24
CAPITOLO 6
DIM [III.] Si assuma Γ |= D; per il teorema di compattezza, sará A1 , . . . , An |= D per certi
Ai ∈ Γ; allora |= (A1 ∧· · ·∧An ) → D. Per il teorema di completezza debole, ⊢ (A1 ∧· · ·∧An ) →
D. Da cio’ si ottiene ovviamente a1 , . . . An ⊢ D e quindi Γ ⊢ D. Vicecersa, e’ ovvio che il teorema
di completezza implica il teorema di compattezza ed il teorema di completezza debole. In conclusione (senza usare l’ assioma di scelta) abbiamo dimostrato che:
• Completezza proposizionale
• Compattezza proposizionale
• Teorema dell’ ultrafiltro booleano
sono tre enumciati equivalenti.
7.3. N.B.: si potrebbe dimostrare che in teoria degli insiemi (escluso l’assioma di scelta)
l’ enunciato del teorema dell’ ultrafiltro booleano non implica l’assioma di scelta; mentre
sappiamo che dall’ assioma di scelta (lemma di Zorn) si ottiene il teorema dell’ ultrafiltro.
Preso come ” assioma”, tuttavia, anche il teorema dell’ ultrafiltro, per quanto piu’ debole
dell’ assioma di scelta, non ha un carattere ”costruttivo” : asserisce che esita un ultrafiltro,
senza specificare come determinarlo. Per esempio, nell’ algebra di boole P(ω) dei sottinsiemi
di ω deve esistere qualche ultrafiltro contenente tutti i cofiniti (siccome questi sono un filtro
proprio); ma nessuno ha idea su come trovarne uno, ne’ saprebbe dire se un siffatto ultrafitro
contenga l’ insieme dei numeri pari o viceversa quello dei numeri dispari . . . , ma deve contenere
uno dei due.
7.4. Come conseguenza del teorema di completezza (debole) abbiamo che la relazione di equivalenza logica ≈coincide con la relazione ∼; quindi le algebre di boole P ROP/ ≈ e P ROP/ ∼ .
coincidono.
7.5. Possiamo domandarci se possiamo trattare di un calcolo proposizionale a partire da un
numero finito di lettere proposizionali. Visto il teorema di forma normale digiuntiva ”completa”, e visto che i letterali sono in numero finito, avremmo che esiste solo un numero finito
di formule che non siano logicamente equivalenti a due a due, e tutte le atre sono equivalenti a
qualcuna di queste. Lo studioso lettore farebbe un utile esercizio a descrivere la corrispondente
algebra di Lindenbaum-Tarski (che é finita): si vedrebbe che essa ha 2n elementi, se ci sono
esattamente n lettere proposizionali.
8. Esercizi
1. (”METAESERCIZIO”) Per ciascun esercizio alla fine del capitolo 5, cambiare |=
con ⊢, e trovare l’albero di derivazione (quando si sia controllato che esiste un a.d.d). Si
eviti l’ uso furbesco del teorema di completezza: ”E’ vero che ⊢ (A → B) ∨ (A → ¬B)?”
Risposta: ”Certo, si tratta di una tautologia, quindi e’ una legge logica...”. Di norma
vogliamo vedere piuttosto un a.d.d !
2. Stabilire se sia vero o meno che: ”L ’intersezione di due insiemi inconsistenti di
formule e’ un insieme inconsistente”
3.Sia Γ l’ intersezione di tutti gli insiemi massimali consistenti di formule proposizionali. Dimostrare che Γ = T AU T.
CAPITOLO 6
25
4. Stabilire se i seguenti insiemi di formule proposizionali siano o meno consistenti:
{(A → B) → C, ¬(A → C), B ∨ C}
{A ∨ B, ((¬B) ∨ C) → ¬A, (A → C) ∨ (¬B)}
5. Siano R, S, Q tre formule distinte. Sapendo che l’insieme {R, S, Q} sia consistente,
si puo’ concludere che anche l’insieme {¬(R → S), ¬(S → Q)} deve essere consistente ?
6. Sia Γ in insieme consistente e deduttivamente chiuso di formule, e P sia un formula
che non appartiene a Γ.. Dimostrare che esiste un insieme massimale consistente di
formule chiuse M che contiene Γ e tale che P ∈
/ M.
7. Esibire un insieme di formule Γ che sia consistente, deduttivamente chiuso, ma non
massimale consistente. [Esempio: TAUT. Oppure, fissata una lettera proposizionale P,
si consideri Γ = {A|P ⊢ A}]
8. Se Γ e’ consistente, esso e’ eguale all’ intersezione di tutti i consistenti massimali
che lo contengono.
9. Sia Γ un insieme consistente e deduttivamente chiuso di formule che non e’ massimale consistente. Dimostrare che esistono almeno due insiemi massimali consistenti
contenenti Γ.
10. Dimostrare che esiste una quantita’ infinita piu’ che numerabile di insiemi consistenti massimali. [Ce ne sono almeno quante sono le valutazioni. . . .].
9. Altri sistemi di deduzione formale
[Qui ci starebbe un cenno ad altri sistemi di regole per trattare la deduzione proposizionale.] [Sistemi alla Hilbert. .. MANCA] [Risoluzione proposizionale. .. MANCA]
[Sequenti. .. MANCA] [ Tableux semantici. .. MANCA]