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) ¬(CD) ~~> (C ¬D)

2) (CD) ~~> (¬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 ¬(CD), 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)aU(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

CB

CB

,,

,

CB

CB

,,

,

Regole di espansione

))/(,

,

xcB

xB

xBxtB

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 QSignifica 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)

ax (¬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 tableau3)

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 ¬(CD), 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 otteniamox(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).

Otteniamox(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) .

• Ottenendox(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).

Otteniamox(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) .

• Ottenendox(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))

• OTTENIAMOx¬(yP(y) P(x))

Applichiamo la regola di riscrittura 1

• Alla sottoformula

¬(yP(y) P(x))

Inx¬(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

• Ax(yP(y) ¬P(x))

• Ottenendox(yP(y) ¬P(x)), yP(y) ¬P(c).

Applichiamo la regola di espansione della congiunzione

inx(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

• Inx(yP(y) ¬P(x)), yP(y), ¬P(c).

• Ottenendox(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))