Qualche esempio di tableaux
pp. 29-30
Esercizio n. 2
• Si parte dalla formula
(x(U(x) M(x))  U(s))  M(s)
• La si nega (cioè: si scrive la formula per
intero tra due parentesi e davanti si pone
la negazione):
¬((x(U(x) M(x))  U(s))  M(s))
È in fnn
(forma normale negativa)?
NO, perché
contiene il simbolo dell’implicazione e
Il simbolo di negazione non compare
sempre “attaccato” ad un simbolo di
predicato.
ALLORA
Dobbiamo applicare le regole di riscrittura
(di p. 25, cui è utile aggiungere, per snellire i
conti, anche quella relativa alla negazione
dell’implicazione – che riportiamo qua per
prima)
Regole di riscrittura
1) ¬(CD) ~~> (C  ¬D)
2) (CD) ~~> (¬C  D)
3) ¬¬C ~~> C
4) ¬(C  D) ~~> (¬C  ¬D)
5) ¬(C  D) ~~> (¬C  ¬D)
6) ¬xC ~~> x ¬C
7) ¬xC ~~>  x ¬C
La nostra formula
• è del tipo ¬(CD), dove
• “C” è x(U(x) M(x))  U(s)
e
• “D” è M(s)
Dunque applichiamo la regola 1)
• Ottenendo:
• C  ¬D.
cioè
• (x(U(x) M(x))  U(s))  ¬M(s).
Ora applichiamo la regola 2)
DENTRO la formula precedente:
(x(U(x) M(x))  U(s))  ¬M(s)
a
U(x) M(x)
E otteniamo
¬CD
Cioè
(x (¬U(x)  M(x))  U(s))  ¬M(s).
(x (¬U(x)  M(x))  U(s))  ¬M(s)
è in fnn
Dunque ora si può partire a costruire l’albero
di refutazione (=il tableau)
applicando le regole di espansione di p. 28
Regole di espansione
, B  C
, B , C
, xB
, B(c / x))
, B  C
, B , C
, xB
, B(t / x), xB
In quale ordine applicare le
regole?
Quello in cui sono state presentate:
Congiunzione, disgiunzione, quantificatore
esistenziale, quantificatore universale
ATTENZIONE
• Quando si applicano le regole di riscrittura
sé può (anzi, si deve) guardare dentro le
parentesi (per scoprire qual è il connettivo
principale e applicare le regola opportuna).
• INVECE, quando si applicano le regole di
espansione E’ ASSOLUTAMENTE
VIETATO GUARDARE DENTRO LE
PARENTESI per applicare le regole ai
connettivi principali che vi stanno dentro.
Esempi
• x(P(x)  Qx) è una formula del tipo:
xB.
Cioè occorre applicare ad essa la regole di espansione per
il quantificatore universale e NON quella per la
disgiunzione (che non siamo autorizzati a ‘vedere’ in
quanto è chiusa tra parentesi)
x(Px)  Q(x) è una formula del tipo:
 xB.
Cioè occorre applicare ad essa la regole di espansione per
il quantificatore esistenziale e NON quella per la
congiunzione (che non siamo autorizzati a ‘vedere’ in
quanto è chiusa tra parentesi)
Che cosa significano le singole
regole di espansione?
• Nella riga più in alto viene espressa la
situazione del tableau al momento in cui
andiamo ad operare. La formula
contenente il connettivo o il quantificatore
su cui si vuole operare è isolata tramite
una virgola dal resto dell’espressione, che
viene simboleggiato con Γ.
Esempio
• Per esempio, se troviamo scritto
Γ, P  Q
Significa che noi adesso stiamo per lavorare
sulla formula P  Q, che ci compare
eventualmente assieme ad altre formule Γ,
separata da esse da una virgola.
• Nella seconda riga, in basso, è segnato il
funzionamento della regola, cioè quello
che noi andremo effettivamente a scrivere
applicando quella regola.
In particolare
• Se abbiamo:
Γ, P Q
__________
• Γ, P , Q
significherà
• che, se vogliamo lavorare su una
congiunzione,
• Semplicemente alla riga successiva
scriveremo tutto il resto dell’espressione
(cioè Γ) e poi i due congiunti separati da
una virgola.
disgiunzione
•
•
•
•
Se abbiamo
Γ, P  Q
--------------Γ, P |Γ, Q
significa
• che, se vogliamo lavorare su una disgiunzione,
• alla riga successiva opereremo una biforcazione
della nostra diramazione e su un ramo
scriveremo tutto il resto dell’espressione (senza
la disgiunzione,cioè Γ) con uno dei disgiunti (P,
separato da una virgola); sull’altro ramo
scriveremo di nuovo tutto il resto
dell’espressione (senza la disgiunzione,cioè Γ) e
poi l’altro disgiunto (Q, separato da una virgola).
Quantificatore esistenziale
• Γ, xB
• ---------• Γ, B(c/x)
significa
• che, se vogliamo lavorare su un
quantificatore esistenziale,
• alla riga successiva trascriveremo il resto
dell’espressione (cioè Γ) e poi, separata
da una virgola, l’esemplificazione del
quantificatore, cioè non si scrive x, ma
solo quanto viene dopo, sostituendo in
esso la x con un simbolo di costante
NUOVO
Per esempio
•
•
•
•
Γ, x(P(x)  Q(x))
Diventa
Γ, P(c)  Q(c)
Purché c non sia mai stata usata prima
Quantificatore universale
• Γ, xB
• ---------• Γ, xB ,B(t/x)
significa
• che, se vogliamo lavorare su un quantificatore
universale,
• alla riga successiva trascriveremo tutta
l’espressione (cioè sia Γ sia xB) e poi, separata
da una virgola, IN AGGIUNTA, l’esemplificazione
del quantificatore, cioè non si scrive (un’altra
volta!) x, ma solo quanto viene dopo,
sostituendo in esso la x con un simbolo di
costante possibilmente VECCHIO.
Per esempio
•
•
•
•
Γ, x(P(x)  Q(x))
diventa
Γ, x(P(x)  Q(x)), P(a)  Q(a)
Dove ‘a’ è una costante già presente nella
dimostrazione (possibilmente, per ragioni
di economicità, cioè per rendere più breve
la dimostrazione).
Torniamo alla formula che stavamo
considerando
Cioè a
(x (¬U(x)  M(x))  U(s))  ¬M(s)
Applichiamo la regola per la
congiunzione una prima volta
Su
(x (¬U(x)  M(x))  U(s))  ¬M(s)
ottenendo:
x (¬U(x)  M(x))  U(s) , ¬M(s)
Una precisazione sulle parentesi
• Quando siamo passati da
(x (¬U(x)  M(x))  U(s))  ¬M(s)
a
x (¬U(x)  M(x))  U(s) , ¬M(s)
abbiamo tolto le parentesi qui segnate in verde, perché
esse servivano solo a chiarire che l’espressione che
contenevano formava un tutto unico (che si aggiungeva
a ¬M(s) ) ed era una congiunzione di x (¬U(x)  M(x)) e
U(s).
Quando ¬M(s) compare preceduto da una virgola, non c’è
più bisogno di precisare che è separato da ciò che sta
prima di esso, che è un’unica formula (cioè x (¬U(x) 
M(x))  U(s) ) per suo conto.
E una seconda
• Su
x (¬U(x)  M(x))  U(s), ¬M(s)
• Ottenendo
x (¬U(x)  M(x)), U(s), ¬M(s)
Applichiamo la regola per il
quantificatore universale
E otteniamo:
x (¬U(x)  M(x)), U(s), ¬M(s),
¬U(s)  M(s).
Applichiamo la regola per la
disgiunzione
• in
x (¬U(x)  M(x)), U(s), ¬M(s), ¬U(s) 
M(s).
e otteniamo la biforcazione:
x (¬U(x)  M(x)), U(s), ¬M(s), ¬U(s)
e
x (¬U(x)  M(x)), U(s), ¬M(s), M(s)
• In
x (¬U(x)  M(x)), U(s), ¬M(s), ¬U(s)
notiamo la contraddizione in rosso e,
dunque, chiudiamo il ramo.
In
x (¬U(x)  M(x)), U(s), ¬M(s), M(s)
notiamo la contraddizione in rosso e,
dunque, chiudiamo il ramo.
ATTENZIONE
• C’è contraddizione solo quando si hanno
due formule di cui una sia atomica e l’altra
la sua negazione SEPARATE DA UNA
VIRGOLA.
Per esempio
• C’è contraddizione se ho le due
contraddittorie:
• P(x), ¬ P(x)
• Non c’è contraddizione se ho:
• P(x), ¬ P(x)  Q(x)
perché ¬ P(x) appare dentro una
congiunzione, non è tra due virgole.
Osserviamo
• Che entrambi i nodi finali dell’albero
“chiudono”, cioè terminano con una
contraddizione e, dunque, dichiariamo
insoddisfacibile l’enunciato:
(x (¬U(x)  M(x))  U(s))  ¬M(s)
che costituiva la fnn di
¬(x(U(x) M(x))  U(s))  M(s))
Se questo è insoddisfacibile, allora risulta
essere logicamente valido
l’enunciato di partenza:
x (¬U(x)  M(x))  U(s))  ¬M(s)
Nuovo esempio di tableau
3)
Si parte da
(x(P(x)Q(x)) (xP(x)  xQ(x))
Lo si nega
• Ottenendo:
¬((x(P(x)Q(x))) (xP(x)  xQ(x))).
È in fnn
(forma normale negativa)?
NO, perché
contiene il simbolo dell’implicazione e
Il simbolo di negazione non compare
sempre “attaccato” ad un simbolo di
predicato.
ALLORA
• Dobbiamo applicare le regole di riscrittura
La nostra formula
È del tipo ¬(CD), dove
“C” è x(P(x)Q(x))
e
“D” è xP(x)  xQ(x)
Dunque applichiamo la regola 1)
e otteniamo:
C  ¬D
cioè
x(P(x)Q(x))  ¬ (xP(x)  xQ(x))
Applichiamo la regola 5)
A
x(P(x)Q(x))  ¬ (xP(x)  xQ(x))
sul secondo membro della formula
(evidenziato in blu),
Ottenendo
x(P(x)Q(x))  (¬xP(x)  ¬xQ(x)).
Applichiamo la regola 6)
A
x(P(x)Q(x))  (¬xP(x)  ¬xQ(x)).
alle sottoformule evidenziate in blu
ottenendo:
x(P(x)Q(x))  (x¬P(x)  x¬Q(x)).
x(P(x)Q(x))  (x¬P(x)  x¬Q(x))
è in fnn
Dunque ora si può partire a costruire l’albero
di refutazione (=il tableau)
applicando le regole di espansione di p. 28
applichiamo la regola per la
congiunzione
Su
x(P(x)Q(x))  (x¬P(x)  x¬Q(x))
e otteniamo
x(P(x)Q(x)), x¬P(x)  x¬Q(x)
Poi applichiamo la regola per la
disgiunzione
a
x¬P(x)  x¬Q(x)
Ottenendo la biforcazione:
1) x(P(x)Q(x)), x¬P(x)
2) x(P(x)Q(x)), x¬Q(x)
Cominciamo ad occuparci del ramo
che contiene la 1)
applichiamo ad essa la regola per
l’esistenziale
Da
x(P(x)Q(x)), x¬P(x)
otteniamo
x(P(x)Q(x)), ¬P(a).
Applichiamo ora la regola per il
quantificatore universale
• Da
x(P(x)Q(x)), ¬P(a).
Otteniamo
• x(P(x)Q(x)), P(a) Q(a) , ¬P(a) .
Applichiamo ora la regola per la
congiunzione
•
•
•
•
•
•
Su
P(a) Q(a)
In
x(P(x)Q(x)), P(a) Q(a) , ¬P(a) .
Ottenendo
x(P(x)Q(x)), P(a) , Q(a) , ¬P(a)
Questo nodo
• Contiene una contraddizione (P(a) e
¬P(a)).
• Dunque chiude
Passiamo ad occuparci del ramo
che contiene la 2)
applichiamo ad essa la regola per
l’esistenziale
Da
x(P(x)Q(x)), x¬Q(x)
otteniamo
x(P(x)Q(x)), ¬Q(a).
Applichiamo ora la regola per il
quantificatore universale
• Da
x(P(x)Q(x)), ¬Q(a).
Otteniamo
• x(P(x)Q(x)), P(a) Q(a) , ¬Q(a) .
Applichiamo ora la regola per la
congiunzione
•
•
•
•
•
•
Su
P(a) Q(a)
In
x(P(x)Q(x)), P(a) Q(a) , ¬Q(a) .
Ottenendo
x(P(x)Q(x)), P(a) , Q(a) , ¬Q(a).
Anche questo nodo
• Contiene una contraddizione (P(a) e
¬P(a)).
• Dunque chiude
Osserviamo
• Che entrambi i nodi finali dell’albero
“chiudono”, cioè terminano con una
contraddizione e, dunque, dichiariamo
insoddisfacibile l’enunciato:
• x(P(x)Q(x))  (x¬P(x)  x¬Q(x))
che costituiva la fnn di:
¬((x(P(x)Q(x))) (xP(x) 
xQ(x))).
• Se questo è insoddisfacibile, allora
Risulta logicamente valido l’enunciato:
(x(P(x)Q(x))) (xP(x)  xQ(x)).
Esempio 4
• Si parte dalla formula
• x(yP(y) P(x)).
• La si nega ottenendo:
¬(x(yP(y) P(x)))
Che si può semplicemente scrivere come
¬x(yP(y) P(x))
Perché non esiste un’altra possibilità di
lettura.
È in fnn
(forma normale negativa)?
NO, perché
contiene il simbolo dell’implicazione e
Il simbolo di negazione non compare
sempre “attaccato” ad un simbolo di
predicato.
La nostra formula
È del tipo
¬xC,
Dove
C
è
yP(y) P(x))
Applichiamo dunque la regola di
riscrittura 7)
•
•
•
•
DA
¬x(yP(y) P(x))
OTTENIAMO
x¬(yP(y) P(x))
Applichiamo la regola di riscrittura
1
• Alla sottoformula
¬(yP(y) P(x))
In
• x¬(yP(y) P(x)) ,
dove
• C sarà yP(y) e D sarà P(x)
ottenendo:
x(C  ¬D)
cioè
x(yP(y)  ¬P(x))
Questa è in fnn
Dunque ora si può partire a costruire l’albero
di refutazione
applicando le regole di espansione
Applichiamo la regola di espansione del
quantificatore universale
•
•
•
•
A
x(yP(y)  ¬P(x))
Ottenendo
x(yP(y)  ¬P(x)), yP(y)  ¬P(c).
Applichiamo la regola di
espansione della congiunzione
in
• x(yP(y)  ¬P(x)), yP(y)  ¬P(c).
ottenendo:
• x(yP(y)  ¬P(x)), yP(y), ¬P(c).
Ora applichiamo la regola di espansione del
quantificatore esistenziale
•
•
•
•
In
x(yP(y)  ¬P(x)), yP(y), ¬P(c).
Ottenendo
x(yP(y)  ¬P(x)), P(a), ¬P(c).
Riapplichiamo la regola di espansione del
quantificatore universale
in
x(yP(y)  ¬P(x)), P(a), ¬P(c).
Ottenendo
x(yP(y)  ¬P(x)), yP(y)  ¬P(a), P(a), ¬P(c).
[la prima volta avevamo esemplificato il
quantificatore universale con la costante “c”; ora
l’abbiamo esemplificato con la costante “a” che
era stata introdotta nel frattempo]
Applichiamo la regola della
congiunzione
• In
x(yP(y)  ¬P(x)), yP(y)  ¬P(a), P(a),
¬P(c)
Ottenendo
x(yP(y)  ¬P(x)), yP(y) , ¬P(a), P(a),
¬P(c)
Qui abbiamo la contraddizione P(a) e ¬ P(a),
Dunque il nodo chiude.
Dunque
dichiariamo insoddisfacibile l’enunciato:
x(yP(y)  ¬P(x))
che costituiva la fnn di
¬x(yP(y) P(x))
• Se questo è insoddisfacibile, allora
risulta logicamente valido l’enunciato
iniziale:
x(yP(y) P(x))