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.
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
|
|
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:
|
|
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 ¬β) |
″ |
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 |
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).
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.
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:
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
da 2 e 3: p¬q v pq = p(¬q v q) = p
La formula semplificata è quindi: ¬p¬qr v p.
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.
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.
[3] Ciò significa
che esiste almeno un insieme di valori che attribuiti alle variabili presenti
in Φ rendono tutte le componenti vere.