Linguaggi L1, L2 & condizioni di verità

Sistemi formali e proprietà ‘metalogiche’

[In]Completezza, [In]Decidibilità

Logica & Calcolabilità

Cognizione & Computazione: le origini delle
Scienze Cognitive
•
•
•
•
•
Riassunto delle puntate precedenti:
Definizioni (informali) di proposizione,
argomento, mondo possibile.
Definizione (informale) di argomento valido
e corretto
Definizione (formale) del linguaggio L1 della
logica proposizionale
Definizione (formale) del concetto di
proposizione in L1.
Definizione (formale) dell’algoritmo delle
tavole di verità.
Estensione della logica proposizionale:
la logica dei predicati (o predicativa o del I
ordine)
Con la logica dei predicati è possibile trattare
la struttura logica di argomenti più complessi,
in particolare di argomenti che contengono
importanti operatori logici detti quantificatori
(operatori che determinano l’estensione
dell’insieme di oggetti che soddisfano una
certa proprietà).
L’introduzione del linguaggio artificiale L1
permette di fornire un’analisi logica astratta di
un’ampia classe di proposizioni e delle loro
condizioni di verità.
Questo consente a sua volta di verificare la
validità di argomentazioni che abbiano come
premesse e conclusioni un certo numero di
proposizioni di L1.
Riprendiamo tuttavia l’argomentazione
Tutti gli uomini sono mortali
Socrate è un uomo
quindi
Socrate è mortale
e chiediamoci:
1) è possibile tradurre l’argomentazione nel
linguaggio L1?
2) se è possibile, la traduzione è in grado di
conservare la validità dell’argomento?
Traduzione in L1
Linguaggio naturale
L1
Tutti gli uomini sono mortali
Socrate è un uomo
quindi
Socrate è mortale
p
q

r
Questa traduzione è l’unica possibile, perché
le proposizioni dell’argomento sono atomiche
e devono quindi essere rappresentate da
lettere proposizionali.
Conservazione della validità
La traduzione in L1 è dunque possibile: ma
conserva anche la validità?
Per la traduzione, conservare la validità
significa che – anche per l’argomento in L1 –
se le premesse sono vere allora deve essere
vera anche la conclusione.
In realtà, tutto ciò che può fare la traduzione è
formulare le proposizioni in linguaggio
naturale come lettere proposizionali, e di per
sé le semplici lettere p e q non sono
‘costrette’ a implicare con necessità r.
In altri termini, non è contraddittorio
ammettere che esista un assegnazione di
valori di verità a p, q e r tale che
p
q

r
Dove sta il problema?
V
V
F
Il problema sta nel fatto che in L1 le proposizioni
p, q e r devono essere trattate come atomiche,
perché non contengono alcun connettivo. Ma
ciò che garantisce la validità dell’argomento
Tutti gli uomini sono mortali
Socrate è un uomo
quindi
Socrate è mortale
dipende proprio dalla struttura interna di queste
proposizioni.
Per estendere l’insieme di proposizioni che è
possibile analizzare dal punto di vista della
logica, occorre allora analizzare la struttura
interna delle proposizioni atomiche.
Questo passo porterà ad estendere il
linguaggio L1 in un nuovo linguaggio artificiale
(L2), capace di rendere conto della validità di
argomenti come
Tutti gli uomini sono mortali
Socrate è un uomo
quindi
Socrate è mortale
Per analizzare la struttura interna di una
proposizione atomica, ricorreremo a uno
strumento di antica tradizione - lo schema
soggetto-predicato. Consideriamo la semplice
proposizione
“l’erba è verde”
In base allo schema soggetto-predicato, avremo
“erba”  soggetto
“essere verde”  predicato
Il ‘predicato’ non è altro che una proprietà
attribuita al soggetto.
Proposizioni come “l’erba è verde” non sono
tuttavia l’unico tipo di proposizioni di cui
possiamo indagare la struttura interna.
Consideriamo infatti una proposizione come
“Mario è più alto di Carlo”
Un’applicazione dello schema soggettopredicato prescriverebbe
“Mario”  soggetto
“essere più alto di Carlo”  predicato
Il significato intuitivo della proposizione
sembra però compatibile anche con la
scomposizione
“Carlo”  soggetto
“essere più basso di Mario”  predicato
Sembra dunque che uno stesso contenuto
concettuale sia associato a due proposizioni
con due soggetti diversi: con quale criterio
scegliere?
Contenuto concettuale della proposizione
?
soggetto: Mario
predicato: essere più alto
di Carlo
?
soggetto: Carlo
predicato: essere più
basso di Mario
Soluzione naturale: il contenuto concettuale
della proposizione riguarda una relazione tra
due soggetti. Questo implica che lo schema
dovrà contemplare almeno due casi possibili:
• Predicato attribuito a un soggetto: si tratta di
una proprietà di quel soggetto
• Predicato attribuito a n soggetti: si tratta di
una relazione che sussiste tra quei soggetti
Una generica proposizione atomica può
parlare allora di uno o più soggetti: si definisce
termine singolare ogni espressione che si
riferisca a un soggetto singolo.
•
•
•
•
Termini Singolari
Nomi propri (“Mario”, “Carlo”, ecc.)
Pronomi dimostrativi ed espressioni che
cominciano con un aggettivo dimostrativo
(“questo”, “quel tavolo”)
Pronomi personali singolari (“io”, “egli”, ecc.)
Descrizioni definite, vale a dire espressioni che
cominciano con un articolo determinativo
singolare (“il presidente della Repubblica”, “il
sindaco di Berlino”, ecc.)
Consideriamo i seguenti esempi.
Mario è alto
Mario e Carlo sono fratelli
Mario è più alto di Carlo
Il predicato è ‘ciò che resta’ quando vengono
eliminati dalla proposizione i termini singolari:
..... è alto
..... e ..... sono fratelli
..... è più alto di .....
..... è alto
Predicato a 1 posto
(proprietà)
..... e ..... sono fratelli
Predicato a 2 posti
(relazione)
..... è più alto di .....
Predicato a 2 posti
(relazione)
Attenzione! La relazione ‘essere fratelli’ è
simmetrica (l’ordine non conta), ma quella
‘essere più alto di’ non lo è.
Estensione del linguaggio artificiale L1 al
linguaggio artificiale L2: si tiene conto
dell’analisi logica interna delle proposizioni.
Linguaggio L2 – Prima parte
1. Un insieme, eventualmente infinito, di lettere
per predicati P, Q, R, ...
2. Un insieme di lettere per termini singolari a,
b, c, ... (eventualmente con apici e indici)
3. I connettivi e i simboli speciali di L1, vale a
dire parentesi e virgole.
Siamo ora in grado di dare la (prima parte
della) definizione di proposizione in L2:
Proposizione di L2 – Prima parte
1. Se P è un predicato a n posti e a1, ... , an
sono termini singolari, Pa1 ... an è una
proposizione atomica di L2.
2. Se A è una proposizione di L2, allora  A è
una proposizione di L2.
3. Se A e B sono proposizioni di L2, allora A  B,
A  B, A  B sono proposizioni di L2.
Riassumendo:
Mario = m
(termine singolare)
 Mario è alto = Am
è alto = A
(pred. a 1 posto)
proposizione atomica di L2 (I parte)
Attenzione! Am è un esempio della forma generale
Pa1 ... an: infatti si pone P=A e a1 = m (ricordiamo che
in questo caso n=1).
Mario, Carlo = m, c
(termini singolari)
 Mario e Carlo sono
fratelli = Fmc
sono fratelli = F
(pred. a 2 posti)
proposizione atomica di L2 (I parte)
Attenzione! Fmc è un esempio della forma generale
Pa1 ... an: infatti si pone P=F, a1=m, a2 = c (ricordiamo
che in questo caso n=2).
Torniamo al nostro argomento
Tutti gli uomini sono mortali
Socrate è un uomo
quindi
Socrate è mortale
Il linguaggio L1 non è in grado di esprimere la
struttura interna di nessuna delle proposizioni
dell’argomento, mentre il linguaggio L2-prima
parte è in grado di esprimere la struttura della
seconda premessa e della conclusione.
Come fare con la prima premessa?
Essa appare cruciale, perché esprime la
validità di una proprietà per tutti gli individui
di un certo insieme.
Perché il linguaggio L2 possa esprimere
questo tipo di proposizioni, sarà necessaria
una riformulazione della proposizione stessa
nei seguenti termini:
Per ogni possibile x, se x è un uomo allora x è
mortale.
Questa riformulazione introduce due nozioni
essenziali che dovranno far parte del
linguaggio L2: le variabili e i quantificatori.
Una variabile non è altro che un termine
singolare generico, cioè un termine che può
assumere valori diversi: quando per esempio
si dice che
x+y = y+x,
si intende con ciò che quella uguaglianza è
valida per qualunque numero si decida di
sostituire a x e y.
Un quantificatore è invece un operatore
logico presente in proposizioni che affermano
per quanti individui di un dato insieme
valgono una certa proprietà P o una certa
relazione Pn. Introdurremo due quantificatori:
Quantificatore universale
xPx  “per ogni x, x è P”
Quantificatore esistenziale 
xPx  “esiste un x che è P”
L’estensione completa di L1 porterà dunque
alla seguente definizione:
Linguaggio L2 – Seconda parte
1. Un insieme, eventualmente infinito, di lettere
per predicati P, Q, R, ...
2. Un insieme di lettere per termini singolari a,
b, c, ... (eventualmente con apici e indici) e per
variabili x, y, z, ... (eventualmente con apici e
indici)
3. I connettivi di L1, i simboli speciali di L1 (vale
a dire parentesi e virgole) e i quantificatori 
(per ogni) e  (esiste)
In analogia con la definizione del linguaggio
L1, vorremmo ora definire l’insieme delle
proposizioni ammesse in L2.
Attenzione! L’introduzione dei
quantificatori ci costringe a una
generalizzazione della nozione di
proposizione.
Nel caso, poniamo, del connettivo di
congiunzione , la proposizione AB viene
generata dall’applicazione di  a due elementi
(A,B) che sono già singolarmente delle
proposizioni a tutti gli effetti, cioè
 : A,B A  B
Consideriamo invece
“per ogni x, x soddisfa la proprietà P”
che formalmente si esprime come xPx.
Se volessimo trattare i quantificatori nello
stesso modo dei connettivi, dovremmo
intendere i quantificatori come operatori che
vengono applicati ad elementi ‘di base’ come
Px, cioè (nel caso di ) qualcosa del tipo
: Px x Px
Ma in questo caso, l’espressione x Px non
può essere considerata come un’applicazione
di  a una proposizione, per il semplice
motivo che Px non è una proposizione, non è
cioè qualcosa di cui possiamo chiederci se è
vera o falsa.
Possiamo infatti chiederci:
“Socrate è un uomo” è vera o falsa?
Ma non possiamo chiederci:
“x è un uomo” è vera o falsa?
Potremo farlo solo quando avremo sostituito
x con un termine singolare, cioè fino a quando
non specifichiamo di quale soggetto stiamo
parlando.
Dovremo allora parlare di formule di L2: una
volta introdotta questa definizione più
generale, sarà possibile isolare le proposizioni
di L2 come casi particolari di formule.
Formula di L2
1. Se P è un predicato a n posti e t1, ... , tn sono
termini singolari o variabili, Pt1 ... tn è una
formula di L2.
2. Se A è una formula di L2, allora  A è una
formula di L2.
3. Se A e B sono formule di L2, allora A  B,
A  B, A  B sono formule di L2.
4. Se A è una formula di L2, allora xA e xA
sono formule di L2.
5. Nient’altro è una formula di L2.
Ricordiamo: ciascuno dei t1 ... tn che ricorrono
nell’espressione Pt1 ... tn può essere o un
termine singolare () o una variabile ():
Pt1 ... tn, con t1 = a1, t1 = a2,..., tn-1 = an-1, tn = an
Pt1 ... tn, con t1 = x1, t2 = a2,..., tn-1 = an-1, tn = an
............
............
Pt1 ... tn, con t1 = x1, t2 = x2, ..., tn-1 = xn-1, tn = an
Pt1 ... tn, con t1 = x1, t2 = x2, ..., tn-1 = xn-1, tn = xn
Da
[Se P è un predicato a n posti e a1, ... , an sono
termini singolari, allora Pa1 ... an è una
proposizione atomica di L2] – punto 1, def. di
prop di L2 – Prima parte
e
[Se P è un predicato a n posti e t1, ... , tn sono
termini singolari o variabili, Pt1 ... tn è una
formula di L2] – punto 1, def. di formula di L2
segue che
Sono proposizioni tutte le formule che non
contengono variabili.
Il problema è a questo punto il seguente:
quale condizione deve soddisfare una formula
con variabili per essere una proposizione?
Prendiamo la formula “x è mortale”: essa non
soddisfa la caratteristica fondamentale di una
proposizione, perché non ha senso chiedersi
se “x è mortale” sia vera o falsa.
L’ambiguità può essere allora eliminata in due
modi:
1) per sostituzione
2) per quantificazione
In entrambi i casi, quello che si ottiene è la
trasformazione di una formula in una
proposizione.
(1) SOSTITUZIONE – È possibile sostituire in
“x è mortale”
la variabile x con un termine singolare (p. es.
“Socrate”) e ottenere così
“Socrate è mortale”
Se t è un generico termine singolare, si indica
con P[x/t] l’operazione di sostituzione della
variabile x con il termine singolare t nella
formula Px: nell’esempio sopra, scriveremo
dunque M[x/s], dove M è la lettera
predicativa per «essere mortale» e s è il
termine singolare che indica Socrate.
(2) QUANTIFICAZIONE – È possibile non
sostituire x direttamente con un termine
singolare, ma ricondurre la variabile sotto
l’azione di un quantificatore. Nell’esempio
sopra:
“x è mortale”  “per ogni x, x è mortale”
Mentre cioè non potevamo chiederci se “x è
mortale” è vera o falsa, possiamo chiederci se
“per ogni x, x è mortale” è vera o falsa.
Una variabile che in una formula è sottoposta
all’azione di un quantificatore si dice
vincolata.
Riassumendo:
Nella procedura
“x è mortale”  “Socrate è mortale”
la variabile x è sostituita.
Nella procedura
“x è mortale”  “per ogni x, x è mortale”
la variabile x è vincolata, cioè ricondotta sotto
l’azione di un quantificatore.
Variabili vincolate o libere
Una variabile che compare in una formula B di
L2 è detta vincolata se è contenuta in una
parte di B della forma xA o xA. Una
variabile che compare non vincolata in una
formula A di L2 è detta libera in A.
Proposizione di L2 – Seconda parte
Una formula A di L2 è una proposizione se
nessuna variabile compare libera in A.
Linguaggio L1
Linguaggio L2
Condizioni di verità
di proposizioni di L1
Condizioni di verità
di proposizioni di L2
Tavole di verità
?
(connettivi verofunzionali)
Le condizioni di verità per proposizioni di L2
dovranno tenere conto della struttura interna
delle proposizioni stesse.
Qual’è l’intuizione che sta dietro le condizioni
di verità per proposizioni di L2? Consideriamo
una semplice proposizione atomica di L2 come
Pa, dove
P = predicato a 1 posto (proprietà )
a = termine singolare ( individuo)
Possiamo immaginare che P rappresenti una
specifica proprietà e che a rappresenti uno
specifico individuo secondo una particolare
interpretazione (o mondo possibile).
LINGUAGGIO
m
A
MONDO
W(m)
W(A)
W
Es.:
“Mario”
nome
Mario
persona
“alto”
predicato
altezza
proprietà
Dunque un’interpretazione o mondo
possibile W non è altro che un certo modo di
associare elementi del linguaggio (in questo
caso L2) a elementi del mondo che il
linguaggio descrive.
Allora una proposizione di L2 come Am
(formalizzazione di “Mario è alto”) è:
• vera in W quando W(m) – cioè l’oggetto
associato da W ad m – soddisfa la proprietà
associata da W a A [cioè quando “Mario” è il
nome di un individuo alto];
• falsa in W, altrimenti.
Più in generale, un’interpretazione W
sensata per L2 dovrà:
•
•
specificare
quali
sono
gli
oggetti
rappresentati dai termini singolari di L2
specificare quali sono le proprietà e
relazioni rappresentate da ogni predicato di
L2.
Interpretazione
Un’interpretazione di un linguaggio logico L è
una struttura W = D, f dove:
1. D è un insieme non vuoto, detto dominio;
2. f è una funzione che a ogni termine t di L
associa un elemento f(t) del dominio D e che a
ogni predicato P di L associa una proprietà o
relazione che sussiste per elementi di D.
Interpretazione W = D, f del linguaggio L
Linguaggio L
Dominio D
f
mL
AL
f(m)  D
f(A) vale per
elementi di D
Interpretazione estensionale dei predicati
Proposizione «l’erba è verde», dove
V:= predicato «verde», e:= termine singolare «erba»
«Ve» è vera nell’interpretazione W = D, f quando
f(e) appartiene a f(V)
cioè quando l’individuo che la f associa al termine singolare «e»
appartiene all’insieme che f associa al predicato V.
Proprietà «essere verde» in W:
l’insieme degli oggetti verdi di D
D
Abbiamo visto cosa significa che una
proposizione Pa di un linguaggio L è vera in
un’interpretazione W: significa che W(a)
soddisfa effettivamente la proprietà W(P).
E nel caso di una proposizione composta del
tipo Pa  Qb ? L’estensione è semplice:
Pa  Qb è vera in W quando
Pa è vera in W e Qb è vera in W,
cioè quando
W(a) soddisfa la proprietà W(P) e
W(b) soddisfa la proprietà W(Q).
Condizioni di verità per proposizioni di L2
Sia W = D, f un’interpretazione di L2.
Supponiamo per semplicità che, ogni volta che
occorre una formula del tipo Px, sia possibile
effettuare la relativa sostituzione P[x/t].
Possiamo allora definire il valore di verità
valW(A) di una generica formula A in
un’interpretazione W come segue:
1. valW(Pt) = V (dove t può essere una variabile o
un termine singolare) se f(t) soddisfa la
proprietà f(P), altrimenti valW(Pt) = F.
2.valW(Pt1 ... tn) = V (dove t1 ... tn possono essere
variabili o termini singolari) se f(t1)...f(tn)
stanno nella relazione f(P), altrimenti
valW(Pt1...tn)=F.
3. valW ( A) = V se valW (A) = F, altrimenti
valW ( A) = F.
4. valW (A B) = V se valW (A)=V e valW(B)=V,
altrimenti valW (A B) = F.
5. valW(A  B) = F se valW(A) = F e valW(B) = F,
altrimenti valW(A  B) = V.
6. valW(A B) = F se valW(A) = V e valW(B)=F,
altrimenti valW(A B) = V.
7. valW(xAx) = V se valW(A[x/a]) = V per
ogni sostituzione di x con un termine singolare
a, altrimenti valW(xAx) = F.
8. valW(xAx) = V se valW(A[x/a]) = V per
almeno una sostituzione di x con un termine
singolare a, altrimenti valW (xAx) = F.
Analogia fondamentale
Logica proposizionale
Possibili assegnazioni di V,F alle prop. A, B, C,..

MONDI POSSIBILI

Possibili interpretazioni W = D, f
Logica predicativa
Una formula A è conseguenza logica di una
formula B
B⊨A
se per qualsiasi interpretazione W tale che
valW (B) = V vale anche valW (A) = V.
Una formula A di L2 è valida (e lo indicheremo
con ⊨ A) se e solo se valW (A) = V per ogni W,
cioè se A è vera in ogni interpretazione.
A questo punto possiamo tradurre il nostro
argomento in L2 conservandone la validità.
Linguaggio naturale
Tutti gli uomini sono mortali
Socrate è un uomo
quindi
Socrate è mortale
L2
x(Ux Mx)
U[x/s]

M[x/s]
In entrambi i casi, se sono vere le premesse
allora è necessariamente vera anche la
conclusione.