1.3        Logica

La logica ha per oggetto lo studio di quei complessi linguistici, detti proposizioni, ai quali può essere associato un valore di verità. Caratteristica delle proposizioni è di affermare un fatto, una proprietà o una relazione. Proposizioni sono ad esempio:

Piove
Socrate è un filosofo
7 è multiplo di 4
13 è compreso fra 11 e 17
I filosofi sono uomini

Negli esempi "piove" è un fatto, "Socrate è un filosofo" e "I filosofi sono uomini" affermano una proprietà, "multiplo" e "compreso fra" sono relazioni. Gli esempi mostrano che una proposizione può essere relativa a nessuno o a più oggetti: una proposizione con al più un oggetto è detta predicato, e, in genere, relazione n-aria se coinvolge n argomenti. Se il valore di verità è determinato, si usa il termine enunciato o (fatto).

Nella logica si considerano delle operazioni fra proposizioni, di solito un'operazione unaria ed alcune operazioni binarie. Le proposizioni ottenute da altre proposizioni tramite connettivi, hanno un valore di verità che dipende unicamente dal valore di verità delle proposizioni componenti.

La proposizione "I filosofi sono uomini" differisce dalla proposizione "Socrate è un filosofo", perché la prima è una affermazione generale che può essere parafrasata come: per tutte le entità che sono filosofi ne segue che sono uomini.

Il modo di considerare le proposizioni conduce a "logiche" diverse, la logica più semplice, il Calcolo Proposizionale, considera le proposizioni a se stanti, senza occuparsi degli eventuali oggetti che le compongono; nel Calcolo dei Predicati si considerano anche affermazioni sugli oggetti delle proposizioni ed affermazioni sulle stesse relazioni; la proposizione "I filosofi sono uomini" nel Calcolo Preposizionale è espressa con una semplice variabile, nel calcolo dei predicati potrebbe assumere una forma più complessa, ma più espressiva.

1.3.1            Calcolo proposizionale

Nel calcolo proposizionale predicati e relazioni si indicano mediante simboli {p,q,r,..p1,p2,..pn} detti variabili proposizionali. Altri simboli indicano le operazioni fra proposizioni ed eventuali simboli di precedenza {(,)} stabiliscono l'ordine delle operazioni. I simboli sono combinati tramite regole in modo che solo certe sequenze di simboli sono ritenute valide. E’ possibile sviluppare il calcolo proposizionale basandosi solo sugli aspetti formali delle formule, qui tuttavia interessa operare con il loro significato, e precisamente: ogni variabile può assumere valore vero o falso{V,F}, ed ogni formula valida assume valore {V,F} in funzione del valore delle variabili e dell'azione degli operatori presenti in essa.

Gli operatori sono: un operatore unario ¬ (not) , ed un operatore binario ● (and), per questo: se α e β sono variabili o formule, allora:

¬ α è una formula
α ● β  è una formula

¬,● agiscono sulle formule secondo le tavole di verità sottostanti

α

¬ α

F

V

V

F

α

β

α ● β

F

F

F

F

V

F

V

F

F

V

V

V

Dalla tavola di verità di ¬ si ricava che ¬¬α = α.

Il simbolo {=}, che non appartiene alla logica bensì al linguaggio (metalinguaggio) utilizzato per parlare di logica, indica che due formule sono ottenibili l’una dall'altra tramite l’applicazione di trasformazioni che lasciano invariato il valore di verità della formula, qualunque sia il valore assegnato alle variabili presenti.

Nel linguaggio naturale si utilizzano altri operatori, che è utile definire:

o (or): (α v β) =def  ¬ (¬α ● ¬β)
implica:  (α > β) =def  (¬ α v β)
equivale (xor):  (α ≡ β) =def :  (α > β)  ● (β  > α)

Le tavole di verità di v  (or) e di > (implica) sono:

Α

β

α v β

F

F

F

F

V

V

V

F

V

V

V

V

α

β

α > β

F

F

V

F

V

V

V

F

F

V

V

V

Sempre applicando le tavole di verità si possono verificare le seguenti uguaglianze:

1

α v (β ● γ) = (α v β) ● (α v γ)              

proprietà distributiva

2

α ● (β v γ) = (α ● β) v (α ● γ)    

″

3

 (α v β) = (β v α)

proprietà commutativa

4

(α ● β) = (β ● α)

″

5

α v V = V

 

6

α v F = α

 

7

α ● V = α

 

8

α ● F = F

 

9

(α v β) = (¬α ● ¬β)

leggi di De Morgan

10

(α ● β) = (¬α v ¬β)              

″

Figura 1‑1

Le tavole di verità si possono utilizzare per ricavare il valore assunto da una formula dati i valori dei suoi costituenti, ad esempio per la formula (p v (¬q ● r)):

p

q

r

(p v (¬q ● r))

F

F

F

F

F

F

V

V

F

V

F

F

F

V

V

F

V

F

F

V

V

F

V

V

V

V

F

V

V

V

V

V

Figura 1‑2

Se, ad esempio, p = V, q = r = F, la formula vale V.

Nell’esempio la tavola di verità contiene 8 righe, una formula con n variabili conterrà 2n righe.

Se si costruisce la tavola di verità di q ● (p v q), si noterà che per qualsiasi valore delle variabili, il risultato è sempre V, le formule con queste caratteristiche sono dette Teoremi o Tautologie. La formula ottenuta negando un Teorema da sempre valore F.

Un semplice teorema è p v ¬p.

Altri teoremi si ottengono sostituendo nelle uguaglianze il simbolo (metalinguistico) = con l’operatore logico ≡ (equivale).

1.3.2            Dalla tavola di verità alla formula

Data una tavola di verità qualsiasi è immediato dedurre una formula che soddisfa la tavola stessa: per ogni riga in cui la funzione vale V, si scrive una formula in cui compaiono in and tutte le variabili o le variabili negate in funzione dell’aver esse V oppure F in detta riga, infine tutte queste formule sono poste in or fra di loro. Tale formula si dice forma normale disgiuntiva.

Per semplificare la scrittura delle formule, potremo omettere il segno and ● e le parentesi fra le espressioni in and, adottando la convenzione che il segno ● abbia la precedenza sul segno v.

Ad esempio la formula normale disgiuntiva della Figura 1.2.‑2 è:

¬p¬qr v p¬q¬r v p¬qr v pq¬r v pqr.

1.3.2.1              Semplificazione di una formula

Data una formula in forma normale disgiuntiva la si semplifica applicando le proprietà della  Figura 1‑1 , in particolare le proprietà 2, 4 e 7:

sia α una espressione in and e p una variabile, se ci sono due disgiunti del tipo:

α ● p v α ● ¬p = α(p v ¬p) = α

La semplificazione deriva dalla proprietà distributiva e dalla proprietà 7 della Figura 1‑1 perché p v ¬p è un teorema e quindi vale V.

Le componenti in and della formula della Figura 1‑2 sono:

  1. ¬p¬qr
  2. p¬q¬r
  3. p¬qr
  4. pq¬r
  5. pqr

da 2 e 3: p¬q¬r v p¬qr = p¬q(¬r v r) = p¬q

da 4 e 5:  pq¬r v pqr = pq(¬r v r) = pq

  1. ¬p¬qr
  2. p¬q
  3. pq

da 2 e 3: p¬q v pq = p(¬q v q) = p

La formula semplificata è quindi: ¬p¬qr v p.

1.3.3            Deduzione

Nella logica la deduzione è l’operazione per cui da un insieme di premesse vere si ottiene, una conclusione vera applicando opportune regole. Si è visto che certe proposizioni, i Teoremi o Tautologie, sono sempre vere; esistono degli insiemi di teoremi, detti base assiomatica, che, con le regole di deduzione, permettono di dedurre tutti e soli i teoremi. Una delle regole di deduzione si basa sull’operatore implica: la formula (α > β) può essere letta: se (è vero) α allora (è vero) β. La frase, comprese le parti fra parentesi, rappresenta il modo comune di intendere l’operatore implica; in realtà nella logica la formula risulta vera anche quando α è falso e β indifferentemente vero o falso. Di fatto questi due casi non hanno quasi importanza pratica [1] .

La seconda regola permette di sostituire in una formula tutte le occorrenze di una variabile proposizionale con un teorema. Per essere più formali sarà indicato come sistema PM [2] l'insieme di assiomi e regole che permettono la deduzione:

Base assiomatica

A1. (p v p) > p
A2. p > (p v q)
A3. (p v q) > (q v p)
A4. (q > r) > ((p v q) > (p v r))

Regole

TR1.         Regola di sostituzione: é possibile sostituire in una formula tutte le occorrenze di una variabile proposizionale con un teorema.
TR2.         Modus ponens(MP) o separazione: se α è vera e (α > β) è vera, allora β è vera.

Dato un insieme di formule e variabili proposizionali Φ ={α1,α2,…a1,a2,… }, in cui ogni componente di Φ è vera per ipotesi [3] , diciamo che β è una deduzione, se β  è deducibile da Φ perché o è una formula o è una variabile proposizionale appartenente a Φ, o è ricavabile applicando le regole.

Un semplice esempio è:

Φ = {"piove" , "piove > strada bagnata"}
β = "strada bagnata" 

Un esempio un po' più complesso è il seguente, in cui occorre verificare se la variabile proposizionale b è derivabile dall'insieme Φ:

1.       a > b
2.       c > b
3.       a v c

i passi successivi mostrano la deduzione di b, con l'indicazione, a destra, dell'assioma o delle formule implicate nel Modus Ponens:

 

4

(a > b) > ((c v a) > (c v b) 

A4

5

  ((c v a) > (c v b)     

MP 1,4

6

(c v b) 

MP 3,5

7

  (c v b) > b      

A1

8

b 

MP 6,7

La procedura di deduzione può essere automatizzata, ma al crescere delle formule coinvolte, il tempo necessario a trovare la soluzione cresce rapidamente. La procedura può essere migliorata con accorgimenti euristici, analoghi a quelli utilizzati da un uomo che voglia ottenere la soluzione. Una procedura, facilmente implementabile su calcolatore, è quella che realizza il metodo reductio. Il metodo sostanzialmente verifica che la negazione di β falsifica almeno una delle formule appartenente a Φ, in questo caso β è deducibile, poiché per ipotesi tutte le formule appartenenti a Φ sono vere; se la negazione di β non falsifica Φ, β non è deducibile da Φ. Per una realizzazione del metodo reductio occorre:

1.       trasformare Φ e β in forma normale congiuntiva, cioè in and di or: Φ = φ1 ● φ2 ● … ● φj …,  e β = β1 ● β2 ● … ● βi …

2.       per ogni βi appartenente a β occorre verificare se βi è deducibile da Φ; ciò viene provato se, supposta falsa βi, almeno una φj risulta falsa, contraddicendo le ipotesi. βi è falsa imponendo opportunamente il valore Vero o Falso (V o F) ad ogni sua variabile.

3.       I valori assegnati alle variabili in βi sono assegnati anche, alle stesse variabili in Φ.

4.       Ogni φj può essere:

4.1         Falsa poiché tutte le variabili presenti sono valorizzate a falso, βi può essere deducibile da Φ.

4.2         Vera, se almeno una variabile presente ha valore vero, in tal caso occorre esaminare φj+1.

4.3         Indefinita, se ci sono ancora variabili non valorizzate (oltre ad eventuali variabili con valore falso). In questo caso occorre valorizzare le variabili in modo che rendano vera la formula: se le variabili in φj sono n, occorrono 2n-1 valorizzazioni. I valori assegnati alle variabili in φj vengono assegnati alle stesse varibili presenti nelle formule φk successive (k > j).

4.3.1  La verifica prosegue sulle formule successive a φj. Se per ogni assegnazione non si trova un φk falso, β non è deducibile.

Dall'esempio precedente:

1               Φ = (¬a v b) ● (¬c v b) ● (a v c);   β = b

2               Affinchè β sia falso b deve valere F.

3               Φ = (¬a v F) ● (¬c v F) ● (a v c)

4               φ1 = ¬a v F è indefinito

4.3  Alla variabile a viene imposto il valore F, perché ¬a; le formule successive diventano: (¬c v F) ● (F v c)

4     φ2 = ¬c v F è indefinito

4.3  Alla variabile c viene imposto il valore F, perché ¬c; la formula successiva diventa: (F v F)

4     φ3 = F v F φ3, contro le ipotesi, risulta falso, quindi β è derivabile da Φ.

Se Φ è inconsistente, perché ad esempio contiene una formula e la sua negazione, sia β che ¬β sono derivabili.

                                                         

1.3.3      Induzione

L'induzione è un tipo di ragionamento opposto al Modus Ponens; esso interviene nella pratica corrente, in quanto, considerando la relazione implica come una relazione causa effetto, e di fatto conoscendo solamente gli effetti, è necessario ipotizzare la causa: ad esempio un medico constata un insieme di sintomi in un paziente che gli fanno diagnosticare una malattia, che è presumibilmente vera ma non lo è formalmente; la situazione è del tipo:

"morbillo" > "febbre"

"morbillo" > "eritema"

"febbre" ● "eritema"

allora è possibile "morbillo" 

 [1] Le clausole di Horn sono facilmente interpretabili nella logica modale prescrittiva: se p un enunciato ed α una azione: if p then α, corrisponde a:  p > O(α) ha valore di verità "Vero", a meno di comportamento scorretto del programma, cioè, a fronte di una istruzione del tipo if p then α, con p "Vero", Oα è "Falso" perché l'azione α non viene eseguita. Il programma ha valore "Vero" anche nel caso in cui p è "Falso" e Oα è "Vero", ma ciò non corrisponde necessariamente ad un malfunzionamento, infatti α potrebbe essere stata eseguita in uno stato precedente.

[2] da Principia Mathematica di A. N. Whitehead e B. A. W. Russell 1910.

[3]  Ciò significa che esiste almeno un insieme di valori che attribuiti alle variabili presenti in Φ rendono tutte le componenti vere.