Logica proposizionale

Sintassi

Il linguaggio della logica proposizionale è formato da un alfabeto e da una grammatica.

Alfabeto

L'alfabeto è costituito da:

Un insieme L infinito numerabile di lettere proposizionali.
Un insieme di simboli per i connettivi vero-funzionali ( , , , , ).
Un insieme di simboli ausiliari: parentesi.

Specifichiamo ora la grammatica della logica proposizionale presentando le cosiddette regole di buona formazione. Le regole di buona formazione sono regole ricorsive che permettono di definire proposizioni, cioè formule di complessità qualunque:

ogni lettera proposizionale è una formula atomica;
ogni formula atomica è una formula;
se X è una formula lo è anche X;
se X e Y sono formule allora lo sono anche:
(XY), (XY), (XY), (XY);
nient'altro è una formula.

L'insieme delle formule è indicato con P.

Semantica

Il concetto semantico fondamentale per il linguaggio della Logica proposizionale è quello di valutazione.

Tavole di verità

Valutazione

Definizione

Una valutazione è l'assegnazione di uno dei valori di verità (vero o falso) ad ogni formula atomica di L.

Una valutazione v è una funzione v: P --> {V,F} (dove P è l'insieme delle formule) che soddisfa le seguenti condizioni:

v(X) = v(X) se X è una lettera proposizionale;
v(X) = V se v(X) = F;
v(XY) = V se v(X) = V e v(Y) = V;
v(XY) = V se v(X) = V o v(Y) = V;
v(XY) = V se v(X) = F o v(Y) = V;
v(XY) = V se v(X) = v(Y).

Modello

Diciamo che v è modello di X (dove X è una formula) se v associa il valore "vero" a X; si scrive v |==

X e si dice che v rende vera X; altrimenti che v rende falsa X.

Proprietà semantiche

Le proprietà semantiche vengono definite in base al concetto di valutazione. È inoltre possibile definire le proprietà semantiche mediante il concetto di inconsistenza; in questo caso solo la consistenza e l'inconsistenza vengono definite con il concetto di valutazione.

Proprietà semantiche definite mediante "valutazione"

Verità: Una formula X è vera se e solo se una valutazione v la rende vera.
Validità: Una formula P è valida se e solo se ogni valutazione v la rende vera. Formule di questo tipo sono dette tautologie.
Falsità: Una formula P è falsa se e solo se ogni valutazione v la rende falsa.
Inconsistenza: Un insieme di formule si dice inconsistente se e solo se non è consistente.
Equivalenza: Due proposizioni P e Q sono equivalenti se e solo se per ogni valutazione v, P e Q assumono lo stesso valore.
Consistenza: Un insieme di formule è consistente se e solo se c'è almeno una valutazione per cui tutti gli elementi dell'insieme sono veri.
Implicazione logica: Un insieme F di formule implica logicamente una formula P se e solo se non c'è alcuna valutazione per cui tutti gli elementi di F sono veri e P è falsa. Esiste un simbolo del metalinguaggio per l'implicazione logica:

Proprietà semantiche definite mediante "inconsistenza"

Chiamiamo {X} l'insieme unitario di X:

Una formula X è valida se e solo se {X} è inconsistente.
Una formula X è falsa se e solo se {X} è inconsistente.
Una formula X è indeterminata se e solo se sia {X} che {X} sono consistenti.
Due formule X e Y sono equivalenti se e solo se {(XY)} è inconsistente.
Un insieme di formule F implica logicamente la formula X se e solo se F{X} è inconsistente.

Apparato deduttivo

Introduzione

La logica in quanto sistema formale è costituita da un linguaggio (sintassi e semantica) e da un apparato deduttivo che permette di ottenere formule nuove a partire da altre formule. Generalizzando il concetto di apparato deduttivo, parliamo di procedure dimostrative, espressione con la quale si intendono tutti quei sistemi formali di calcolo che sono in grado di produrre tutte e sole le formule di un linguaggio logico. Le procedure dimostrative che prenderemo in esame sono: gli alberi semantici e la deduzione naturale.

Alberi semantici

Introduzione

Il metodo degli alberi semantici è una procedura dimostrativa di natura semantica; è cioè una procedura di verifica della validità delle formule. Non è propriamente un apparato deduttivo, ma può essere considerato una procedura dimostrativa perché in grado di produrre tutte e sole le formule valide del linguaggio oggetto.

Dal momento che le proprietà semantiche possono essere definite a partire dal concetto di inconsistenza, la procedura dimostrativa ad albero si basa su questo risultato: mostrando che la negazione di un insieme di formule è inconsistente si prova la sua validità.

Il vantaggio offerto dal metodo degli alberi semantici rispetto alle tavole di verità è la semplicità; infatti la complessità del metodo delle tavole di verità cresce esponenzialmente in rapporto al numero delle lettere proposizionali presenti nella formula. Anche gli alberi di verità possono diventare poco maneggevoli, ma la loro complessità non è funzione diretta del numero delle lettere proposizionali.

Convenzione notazionale

Nella costruzione dell'albero semantico useremo espressioni del tipo V[A] e F[A]; esse prendono il nome di formule segnate e si leggono "A è vera", "A è falsa". Inoltre si stipula che data una valutazione v,

v -> V[A] se e solo se v(A) = V
v -> F[A] se e solo se v(A) = F.

Dunque V[A] equivale ad "A" e F[A] equivale a " not A".

Regole per la costruzione dell'albero semantico

Le regole per la costruzione dell'albero semantico sono otto, due per ogni connettivo secondo che la formula sia segnata con "V" o "F".

Dividiamo le otto regole in due classi secondo il tipo di diramazione che provocano nella costruzione dell'albero semantico: parliamo di a-formule nel caso di un prolungamento dell'albero con uno o due nodi consecutivi; di b-formule nel caso di una biforcazione dell'albero.

Procedimento di costruzione dell'albero semantico

Data una formula X si scrive F[X] alla radice dell'albero. Si procede per induzione.

Base dell'induzione

Secondo che X sia una a-formula o una b-formula si procede in base alle regole per le a-formule o per le b-formule. Si contrassegna F[X] e si contrassegnano eventuali formule atomiche.

Passo n+1

Si prende in esame ogni ramo dell'albero sviluppato sino al passo n:

se un ramo contiene due nodi contraddittori (V[A] e F[A]), allora il ramo si chiude;
se non contiene nodi contraddittori, si considerano le sottoformule non ancora segnate; se non ce ne sono, il ramo è terminato;
se ci sono nodi contenenti formule non contrassegnate, si sceglie quella di altezza minore e si procede in base alle regole per le a-formule o per le b-formule.

Stratagemmi per costruire gli alberi di verità

Dare la priorità alle a-formule.
Dare la priorità alle proposizioni la cui decomposizione fa chiudere uno o più rami.
Fermarsi quando s'incontra una contraddizione.
Quando non sono più applicabili gli stratagemmi 1-3, decomporre la prima formula più complessa.

Definizioni

Ramo chiuso:: un ramo in cui è presente una formula atomica e la sua negazione.
Ramo aperto:: un ramo che non è chiuso.
Ramo aperto completo:: un ramo aperto finito in cui ogni formula è segnata (cioè ogni a-formula e ogni b-formula è stata scomposta).
Albero completo:: un albero in cui ogni ramo è chiuso o ha un ramo aperto completo.
Albero chiuso:: un albero in cui ogni ramo è chiuso.

Uso degli alberi semantici per provare le proprietà semantiche

Validità

Una formula X è valida <==>

l'insieme { not

X} ha un albero chiuso.

Equivalenza

Due formule X e Y sono equivalenti <==>

l'insieme { not

X)} ha un albero chiuso.

Falsità

Una formula X è falsa, cioè è una contraddizione <==>

l'insieme {X} ha un albero chiuso.

Consistenza

Un insieme finito F di formule è consistente <==>

F ha un albero semantico con almeno un ramo completo aperto.

Inconsistenza

Un insieme di proposizioni F è inconsistente <==>

almeno un sottoinsieme finito di F ha un albero chiuso.

Implicazione logica

Un insieme finito F di formule implica logicamente una formula P <==>

l'insieme F

{

P} ha un albero chiuso.

Esempio

      F[(AB)  (AB)]
             |
             |
          V[AB]
             |
             |
          F[AB]
             |
             |
           V[A]
             |
             |
           V[B]
            /\
           /  \
        F[A]  F[B]

Deduzione naturale

Le derivazioni sono un procedura dimostrativa sintattica che si basa esclusivamente sulla forma delle formule da dimostrare. Regole di derivazione vengono usate per costruire le derivazioni, procedimenti che mostrano in una serie di passi facili da comprendere come formule derivino da altre.

I sistemi che impiegano le regole di derivazione di cui tratteremo sono detti sistemi a deduzione naturale.

Definizioni

Sequenza: Si dice sequenza una qualsiasi stringa di formule del tipo A X, dove A è un insieme di proposizioni (eventualmente vuoto), detto antecedente della sequenza, e X è una proposizione, detta conseguente della sequenza.
Derivazione: Una derivazione è una serie di sequenze di proposizioni in cui ogni sequenza è una assunzione, oppure è ottenuta dalle sequenze precedenti mediante le regole di deduzione.
Formula derivabile: Una formula X è derivabile nel calcolo proposizionale a deduzione naturale (che denotiamo con CP) da un insieme F di proposizioni, se e solo se esiste una derivazione di una sequenza in cui gli antecedenti sono membri di F e il conseguente è X. X è derivabile da F e si scrive: F X.

Regole di derivazione

Regole primitive

La base di connettivi che prenderemo in considerazione è

, �, mentre viene definito: X <==>

Y = (X

Regola di assunzione

```
X  X [A]
```
È banale che una formula derivi da se stessa.

Regole di introduzione ed eliminazione della congiunzione

```
A  X
B  Y   [I ]
-------
A, B  XY
```
```
A  XY [E ] 
-------
A  X oppure A  Y
```

Regole di introduzione ed eliminazione della implicazione

```
A,X  Y   [I ]
-------
A  X  Y
```
```
A  X    [E ]
B  X  Y
-------
A, B  Y
```

Regole di introduzione ed eliminazione della disgiunzione

A  X    [I ]
-------
A  X  Y oppure
A  Y  X

A  X  Y    [E  nel conseguente]
 X
X  Z Y Z
---------
A, X, Y  Z

Regola di negazione classica

```
A, X  Y
B, X  Y
----------
A, B  X
```

Regole eliminabili

Le regole eliminabili si dicono tali perché possono essere ricondotte alle otto regole primitive.

Regole di inferenza

 Modus tollens
    A  X � Y
    B  Y
   -------------
    A, B  X

Sillogismo ipotetico
    A  X
    B, X  Y
   ----------
    A, B  Y


 Sillogismo disgiuntivo
    A  P  Q                 A  P  Q
    B  P        oppure      B  Q
   -----------               -----------
    A, B  Q                  A, B  P

Regole d'equivalenza

Queste regole permettono di derivare alcune formule da altre cambiando i componenti proposizionali.

```
PQ  QP
PQ  QP
```
```
P(QR)  (PQ)R
P(QR)  (PQ)R
```
```
P � Q  PQ
```
```
P  P
```
Leggi di De Morgan:
```
(PQ)  PQ
(PQ)  PQ
```
```
P  PP
P  PP
```
```
P � Q  Q � P
```
```
P � (Q � R)  (PQ) � R
```
```
P(QR)  (PQ)  (PR)
P(QR)  (PQ)  (PR)
```

P � Q  (P � Q)  (Q � P)
P � Q  (PQ)  (PQ)

Proprietà del calcolo proposizionale a deduzione naturale

Una sequenza è derivabile se e solo se la conclusione della sequenza è derivabile dall'insieme formato dalle premesse.
Una formula X è un teorema se e solo se X è derivabile dall'insieme vuoto.
Due formule X e Y sono equivalenti se e solo se Y è derivabile da {X} e X è derivabile da {Y}.
Un insieme F di formule è inconsistente se e solo se una formula X e la sua negazione not X sono derivabili da F. Un insieme F di formule è consistente se e solo se non è inconsistente.

Metateoria

Introduzione

Una procedura dimostrativa si dice corretta se e solo se ogni proposizione che può essere derivata da un insieme di formule usando quella procedura è logicamente implicata da quell'insieme di formule.

Una procedura dimostrativa si dice completa se e solo se ogni proposizione logicamente implicata da un insieme di formule può essere derivata usando quella procedura.

Teoremi di correttezza e completezza per gli alberi semantici

Introduzione

Per quanto riguarda la procedura dimostrativa con alberi semantici, i due teoremi permettono di dimostrare rigorosamente il fatto che ogni formula dimostrabile col metodo degli alberi è valida (teorema di correttezza) e che se una formula X è valida allora ogni albero completo per F[X] è chiuso (teorema di completezza).

Proprietà

Proprietà 1

Data una regola per le a-formule, se una valutazione è modello della formula che costituisce il nodo in alto, allora è modello delle sue conseguenze dirette; e inversamente se una valutazione è modello delle conseguenze del nodo, allora è modello del nodo in alto.
Data una regola per le b-formule, se una valutazione è modello della formula che costituisce il nodo in alto, allora è modello di almeno una delle conseguenze; e inversamente se una valutazione è modello di almeno una delle conseguenze, allora è modello del nodo in alto.

Proprietà 2

Ogni ramo completo e non chiuso è consistente.

Infatti consideriamo un qualsiasi ramo R completato e non chiuso e definiamo una valutazione nel modo seguente:

  v(P) = V  se  V[P] ==> R
  v(P) = F  se  F[P] ==> R
  v(P) = V o F a scelta se né V[P] né F[P] sono in R

Considerando un qualsiasi nodo N di R, per la definizione di ramo completo il ramo R contiene le conseguenze di N. Per come è stata costruita, v rende vere le conseguenze di N, e per la proprietà 1 anche N. Quindi v rende vero ogni nodo di R e pertanto R è consistente.

Definizioni

Si dice che una valutazione v è modello di un ramo di un albero semantico se e solo se è modello di tutti i nodi del ramo.

Un ramo si dice consistente se e solo se esiste una valutazione v che è modello del ramo.

Un albero è consistente se e solo se ha almeno un ramo consistente.

Si dice che la proposizione A è derivabile con il procedimento dell'albero semantico, e si scrive |-- A, se e solo se esiste almeno un albero chiuso ottenuto sviluppando l'albero costituito dall'unico nodo F[A] mediante le regole di costruzione.

Teorema di correttezza per gli alberi semantici

Ipotesi

A (se una formula A è derivabile),

Tesi

allora

A (allora A è una tautologia).

Dimostrazione

Si deve dimostrare che, se esiste un albero chiuso ottenuto partendo con la radice F[A], allora A è una tautologia.

Se un albero T è consistente, lo è anche T1, sua estensione diretta ottenuta applicando a un nodo N di T una a-formula o una b-formula. Se una valutazione v è modello di T, lo è anche di T1. Infatti per la proprietà 1, se il nodo N di T è una a-formula, v è modello delle conseguenze dirette di N; se N è una b-formula, v sarà modello di almeno una delle conseguenze.

Dunque, se una valutazione rende vero un ramo, rende anche vero almeno uno dei prolungamenti che subisce durante il processo di costruzione (si dice che la consistenza si trasmette verso il basso).

Premesso questo, si dimostra per assurdo che se A non fosse una tautologia, vi sarebbe almeno una valutazione v che renderebbe vero F[A]. Dal momento che la consistenza si trasmette verso il basso, un qualsiasi albero sviluppato partendo da F[A] dovrebbe avere un ramo consistente. Ma, per ipotesi, vi è un albero chiuso sviluppato partendo da F[A], e ciò è assurdo poiché un albero chiuso non ha alcun ramo consistente.

Teorema di completezza per gli alberi semantici

Ipotesi: Se A (se la formula A è una tautologia),
Tesi: allora A (allora A è derivabile.
Dimostrazione: Si vuole dimostrare che, se A è una tautologia, allora esiste almeno un albero chiuso per F[A].
Consideriamo un qualsiasi albero T per F[A] che sia completo. Necessariamente T è chiuso, e quindi A. In caso contrario vi sarebbe in T almeno un ramo aperto completato; ma, per la proprietà 2, tale ramo sarebbe consistente, quindi dovrebbe esistere una valutazione che rende veri tutti i nodi, in particolare F[A] (la radice fa parte di tutti i rami); ma ciò è impossibile poiché, per ipotesi, A è una tautologia (e ogni valutazione rende vera V[A]).

Teoremi di correttezza e completezza per il calcolo proposizionale a deduzione naturale

Teorema di correttezza in CP

Ipotesi

X (se la formula X è derivabile da A),

Tesi

X (allora A rende vera X).

Dimostrazione

Per definizione di A ==> X esistono X1, X2, ..., Xn in A tali che X1, X2, ..., Xn ==> X. Se si dimostra che X1, X2, ..., Xn ==> X si ha, a maggior ragione, A ==> X. Si deve dunque dimostrare che

X1, X2, ..., Xn ] X --> X1, X2, ..., Xn ==> X

cioè che in ogni argomento derivabile il conseguente è conseguenza logica dell'insieme degli antecedenti. Poiché ogni argomento derivabile è ottenuto applicando le regole di CP, basta dimostrare che ciascuna regola è corretta, cioè che ogni regola se applicata ad argomenti corretti produce argomenti corretti.

Verifichiamo quanto detto per le otto regole primitive di CP.

[A]   Hp. X  X
      Th. X ==> X

[I ] Si tratta di dimostrare che se le sequenze AX e BY sono
corrette, allora la sequenza A, B  X  Y è corretta, cioè:

   Hp. A ==> X        Th. A, B ==> X  Y 
       B ==> Y

Dimostrazione. Si vuole mostrare che data una qualsiasi interpretazione
v, se v ==> A, B, allora v ==> X  Y. 

v ==> A, B           ==>    v ==> A  e  v ==> B
v ==> A              ==>    v ==> X             [ per ipotesi ]
v ==> B              ==>    v ==> Y             [ per ipotesi ]
v ==> X  e v ==> Y   ==>    v ==> X & Y       [per la proprietà 3 della funzione v]


[E ]     Hp. A   X  Y
          Th. A   X (oppure Y)
Dimostrazione. 
v  A        v  X  Y  [Hp.]
v  X  Y    v  X  ( v  Y )  [proprietà 3 di v].

[I ]     Hp. A X
          Th. A X  Y

v A   X  [Hp.]
v X   X  Y                 [proprietà 4 di v].


[v I]   Hp. A, X  Z
            B, Y  Z 
        Th. A, B, X v Y  Z
Dimostrazione. Sia v tale che  v  A, B, X v Y, dobbiamo mostrare che v  Z.

v  A, B, X v Y    v  A,  v   B e v  X v Y
v  X v Y         v   X o v  Y  [proprietà 4 di v]
v �X e v  A     v  A, X
oppure
v  Y e v   B      v  B, Y
v  A, X            v  Z               [Hp.]
oppure
v  B, Y             v  Z              [Hp.]


[I -->]    Hp. A, X   Y
           Th. A   X --> Y

Dimostrazione.   Si deve mostrare che, per ogni v, se v A, allora
                   v X --> Y

v  A                v  X o v   X
v  X                v  X --> Y        
v  X e v  A        v  A, X
v  A, X             v  Y           [Hp.]
v  X e v  Y        v  X --> Y

In entrambi i casi v  X --> Y.



[E -->]   Hp. A  X
              B  X --> Y
          Th. A, B  Y          

Dimostrazione. 
v  A, B               v  A e v  B
v  A                  v  X               [Hp.]
v  B                  v  X --> Y      [Hp.]
v  X e v  X --> Y    v  Y


[ K]    Hp.  A,  X  Y
              B,  X   Y
         Th.  A, B  X

Dimostrazione. Sia v  A, B, dobbiamo dimostrare che v.  Supponiamo per
assurdo che v  X, ossia che v   X:

v  A e v   X     v  A,  X
v  A,  X          v  Y             [Hp.]
v  B e v   X    v   B,  X
v  B,  X          v   Y           [Hp.]
ma v  Y e v   Y sono in contraddizione quindi:
                  v  X
e con questo termina la dimostrazione del teorema di correttezza.

Teorema di completezza in CP

Ipotesi: A X (se A rende vera X),
Tesi: A X (allora A è derivabile da X).
Dimostrazione: Il teorema di completezza è equivalente ad un altro teorema detto di "esistenza del modello". Introdotti alcuni concetti preliminari, è in questa forma che lo dimostreremo.

La dimostrazione del teorema di completezza avviene in quattro passi:

Definizioni

Definizione. Un insieme di formule A si dice contraddittorio (Ctr A) se esiste una formula X tale che: A (X

X). Da questo si può dimostrare che, se da una formula A è derivabile una contraddizione, allora è derivabile una formula qualunque.

Definizione. Un insieme di formule A è non contraddittorio (N-Ctr A) se e solo se da esso non è derivabile una contraddizione. Si dimostra che vale la seguente proprietà:

N-Ctr A {X} A X

Teoremi equivalenti

Consideriamo i seguenti teoremi:

Teorema di correttezza: A X A X
Teorema di completezza: A X A X
Teorema di consistenza: Cons A N-Ctr A
Teorema di esistenza del modello: N-Ctr A Cons A

Si dimostra che:

1)  3)
2)  4)

Da questo risultato segue che il teorema di completezza può essere provato nella forma del Teorema di esistenza del modello:

N-Ctr A Cons A.

Insiemi non contraddittori massimali

Consideriamo un insieme A non contraddittorio e dimostriamo che esiste un'interpretazione che rende vere tutte le formule dell'insieme.

Si estende A quanto più è possibile compatibilmente alla sua non contraddittorietà. L'insieme B che si ottiene è detto: non contraddittorio massimale.

Lemma di Lindenbaum
Ogni insieme non contraddittorio A ammette una estensione non contraddittoria massimale.

Proprietà degli insiemi non contraddittori massimali

Proprietà di chiusura:
X B B X
Proprietà di completezza rispetto a :
X Y B X B e Y B
Proprietà di completezza rispetto a :
X Y B X B o Y B
Proprietà di completezza rispetto a :
X Y B X $e\$ B o Y B
Proprietà di completezza rispetto a :
X B X $e\$ B

Teorema di esistenza del modello

Ipotesi

N-Ctr A

Tesi

Consistente A

Dimostrazione

Sia A non contraddittorio. Applichiamo il lemma di Lindenbaum e consideriamo un'estensione non contraddittoria massimale B di A. Per la proprietà di completezza rispetto alla negazione, ogni lettera proposizionale P figura in B o vi figura la sua negazione.

Definiamo una interpretazione v ponendo: v(P) = V P B

Si dimostra per induzione che v ==> X X B, cioè che la interpretazione v sopra definita rende vere tutte le formule di B, quindi consistente B. Dalla consistenza di B segue la consistenza di A (A ==> B) e con ciò è dimostrato il teorema di esistenza del modello equivalente al teorema di completezza.