Logica del Primo Ordine Mattia Natali 7 luglio 2011

(1)

Mattia Natali 7 luglio 2011

Indice

1 Definizioni 2

1.1 Alfabeto del linguaggio del primo ordine . . . 2

1.2 Termini . . . 2

1.3 Formula atomica . . . 2

1.4 Formule ben formate (f.b.f.) . . . 3

1.4.1 Esempi: . . . 3

1.5 Precedenze dei connettivi . . . 3

1.5.1 Esempio: . . . 3

1.6 Sottoformule di una f.b.f. . . 4

1.7 Albero di derivazione . . . 4

1.8 Campo d’azione . . . 4

1.8.1 Variabili libere e vincolate . . . 5

1.9 Chiusure . . . 5

1.9.1 Chiusura universale . . . 5

1.9.2 Chiusura esistenziale . . . 5

1.10Interpretazione . . . 6

1.10.1Esempio: . . . 6

1.11Assegnamento di valori . . . 6

1.11.1Esempio: . . . 7

1.12Soddisfazione di una formula . . . 7

1.12.1Esempio . . . 7

1.13Vero, falso, soddisfacibile rispetto ad un’interpretazione . . . 8

1.13.1Metodo per verificare che f.b.f. è logicamente valida . . . 8

1.14Insiemi di f.b.f. . . 9

1.15Formula normale prenessa . . . 9

1.15.1Esempio: . . . 10

1.15.2Formula di Skolem . . . 10

1.15.3Esempio formula di Skolem . . . 11

2 Clausole 11 2.1 Sostituzione . . . 11

2.1.1 Esempio . . . 12

2.2 Prodotto di sostituzioni . . . 12

2.2.1 Unificatore più generale: . . . 12

2.2.2 Esempio . . . 12

2.2.3 Algoritmo per determinare l’unificatore generale . . . 12

2.3 Risolvente . . . 13

2.3.1 Esempio . . . 13

(2)

2.3.2 Risolvente . . . 14

3 Teoria formale K 14 3.1 Simboli . . . 14

3.2 Formule ben formate . . . 14

3.3 Assiomi . . . 14

3.4 Regole di inferenza . . . 15

3.5 Aggiunte con identità . . . 15

3.5.1 Quantificatore esistenziale . . . 15 Nella logica proposizionale potevamo assegnare una tavola di verità alle varie lettere enunciative nelle varie interpretazioni, nella logica del primo ordine non è più possibile.

1 Definizioni

1.1 Alfabeto del linguaggio del primo ordine

• Costanti: a, b, c, . . .

• Variabili: x, y, z, . . .

• Lettere funzionali: f_iⁿ, l’apice n indica l’arità. Esempio f₁²(. . . , . . . ) avremo 2 argomenti mentre il pedice serve per distinguere le lettere funzionali esempio f16= f2.

• Lettere predicative: Aⁿi n indica ancora l’arità e il pedice serve a distinguere le varie lettere predicative.

• Connettivi: ∼, ∧, ∨, ⇒, ⇔.

• Quantificatori: quantificatore universale ∀, quantificatore esistenziale ∃. In genere sono subito seguiti da una variabile.

• Simboli ausiliari: (, ).

1.2 Termini

I termini sono un insieme di espressioni e vengono definiti in modo ricorsivo

• Le costanti sono termini.

• Le variabili sono termini.

• Se t₁, t₂, . . . , t_n sono termini, allora f_iⁿ(t₁, t₂, . . . , t_n) è un termine. Ossia abbiamo lettere funzionali con i termini come argomenti.

• Nient’altro è un termine.

1.3 Formula atomica

Siano termini t1, t2, . . . tn, allora A_jⁿ(t1, t2, . . . , tn) è una formula atomica. Non è previsto che vi siano come argomenti delle lettere predicative (solo funzionali come definito in §1.2). La formula atomica costituisce l’elemento base per le formule più complesse.

(3)

1.4 Formule ben formate (f.b.f.)

• Ogni formula atomica è una formula ben formata.

• Se F è una f.b.f. allora (∼ F ) , (∀xF ), (∃xF ) sono f.b.f.

• Se F, G sono f.b.f. allora (F ∧ F ), (F ∨ G), (F ⇒ G), (F ⇔ G) sono f.b.f.

• Nient’altro è una f.b.f.

1.4.1 Esempi:

• Costanti: a, b, c.

• Variabili: x, y.

• Lettere funzionali: f₁², f₂³.

• Lettere predicative: A¹₁, A²₂.

• Siccome stiamo dicendo che f₁²(x, y) ha arità 2 non possiamo scrivere f₁²(x, y, a) perchè deve avere due argomenti.

• f₁² f₂³(x, y, a) , x è ancora un termine perchè f₂³ha arità 3 mentre f₁² ha arità 2 e il tutto è coerente.

• f₁² A²₂(x, y) , x

non è un termine perchè come argomento ha una lettera predicativa e quindi per definizione non può essere un termine.

• A¹₁ f₁²(a, b) è una lettera predicativa corretta perchè ha come argomenti un termine.

• A¹₁ f₁²(a, b) ∧ A²₂ f₁²(x, y) , a è una lettera predicativa corretta mentre A¹₁ f₁²(a, b) ∃x∧A²₂ f₁²(x, y) , a non lo è perchè∃x deve essere all’inizio, per essere corretta quindi deve essere ∃xA¹₁ f₁²(a, b)∧

A²₂ f₁²(x, y) , a , solitamente dopo il quantificatore esistenziale ci sono le variabili (non ha

senso scrivere una costante). Supponiamo∃xA¹₁ f₁²(a, b) ∧

termine z }| {

f₁²(x, y) non è una f.b.f. perchè abbiamo un termine al posto di una formula atomica.

1.5 Precedenze dei connettivi

(∼, ∀, ∃) , ∧, ∨, ⇒, ⇔.

Se non metto la parentesi in∃x

∃x

z }| {

A¹₁ f₁²(a, b) ∧A²₂ f₁²(x, y) , a l’esiste si riferisce solo alla prima parte.

1.5.1 Esempio:

A²₂(a, b) ∨ ∃y A²₁ f₁²(x, y) , f₂²(a, x) ⇒ ∀x ∼ A²₁ f₁² x, f₂²(a, x) , b ∧ A²₂(x, x)

possiamo cancellare la parentesi esterna della prima

ma l’or ha la precedenza sull’implica, quindi

(4)

possiamo anche eliminare la parentesi di∃y perchè ha già la precedenza

eliminiamo anche quella dopo∃y

A²₂(a, b) ∨ ∃yA²₁ f₁²(x, y) , f₂²(a, x) ⇒ ∀x ∼ A²₁ f₁² x, f₂²(a, x) , b ∧ A²₂(x, x)

nel secondo termine possiamo togliere quella più esterna perchè il ∀x ha la precedenza sul- l’implica, possiamo togliere anche la parentesi prima del not, perchè ha la precedenza sul ∧ quindi

qui non possiamo semplificare altro perchè se togliessimo la parentesi a destra del∀x cambie- rebbe il senso della frase, infatti si riferirebbe solo alla prima formula atomica.

1.6 Sottoformule di una f.b.f.

• Se F è una formula atomica, Stf m (F ) = {F }.

• Se F è (∼ G) oppure (∀xG) oppure (∃xG), allora Stf m (F ) = {F } ∪ Stf m (G), ossia prendiamo solo le formule atomiche senza not, esiste ecc.

• Se F è (G ∧ H) oppure (G ∨ G) oppure (G ⇒ G) oppure (G ⇔ H), allora Stf m (F ) = {F } ∪ Stf m (G) ∪ Stf m (H).

1.7 Albero di derivazione

Scriviamo l’albero di derivazione (di struttura) di

⇒

∨ ∀x

A²₂(a, b) ∃y ∧

A²₁ f₁²(x, y) , f₂²(a, x)

∼ A²₂(x, x)

A²₁ f₁² x, f₁²(a, x) , b

1.8 Campo d’azione

È la sottoformula sulla quale agisce il quantificatore. Abbiamo visto prima che la parentesi del

∀x era importante per determinare il suo campo d’azione.

(5)

1.8.1 Variabili libere e vincolate

Le variabili libere non sono quantificate da un quantificatore, altrimenti si definiscono vinco- late, per esempio:

A²₂(a, b)∨∃yA²₁



f₁²



 x

|{z}

L

, y

|{z}

V



, f₂²



a, x

|{z}

L







⇒ ∀x



∼ A²₁



f₁²



 x

|{z}

V

, f₂²



a, x

|{z}

V







, b



∧ A²₂



 x

|{z}

V

, x

|{z}

V









• Un termine t è libero per una variabile x in una formula A se nessuna occorrenza libera della variabile x in A cade nel campo d’azione di un quantificatore che quantifica una variabile che compare nel termine t.

• Versione alternativa: dati A formula, t termini, x variabili, diciamo che t è libero per x in A se t non contiene alcuna variabile y tale che qualche occorrenza libera di x cade sotto al raggio di un quantificatore Q (y).

• Per convenzione viene definita vincolata anche l’occorrenza della variabile che compare vicino al quantificatore.

Sempre prendendo il nostro esempio

A²₂(a, b) ∨ ∃yA²₁





f₁²(x, y)

| {z } libero?

, f₂²(a, x)





⇒ ∀x ∼ A²₁ f₁² x, f₂²(a, x) , b ∧ A²₂(x, x)

non c’è nessuna occorrenza libera di y quindi f₁²(x, y) è libero per y, mentre non lo è per x perchè abbiamo x libera nel campo d’azione del quantificatore ∃y.

1.9 Chiusure

Una formula in cui non ci sono occorrenze libere di variabili si dice chiusa.

1.9.1 Chiusura universale

Mettiamo davanti alla formula dei quantificatori universali che quantificano le variabili libere, quindi

∀x A²₂(a, b) ∨ ∃yA²₁ f₁²(x, y) , f₂²(a, x) ⇒ ∀x ∼ A²₁ f₁² x, f₂²(a, x) , b ∧ A²₂(x, x)

vogliamo far notare che il primo ∀x si riferisce solo alle occorrenze libere di x e non a quelle vincolate dall’altro quantificatore ∀x che compare a destra dell’implica, lo dobbiamo pensare a una parte a se stante, altrimenti cambieremmo il senso della frase. In definitiva la chiusura universale si riferisce solo alle variabili libere. Se nella formula ci fossero state altre variabili libere dovevamo aggiungere anche quelle.

1.9.2 Chiusura esistenziale

Mettiamo davanti alla formula dei quantificatori esistenziali che quantificano le variabili libere, quindi sempre usando il nostro esempio

∃x A²₂(a, b) ∨ ∃yA²₁ f₁²(x, y) , f₂²(a, x) ⇒ ∀x ∼ A²₁ f₁² x, f₂²(a, x) , b ∧ A²₂(x, x)

(6)

1.10 Interpretazione

Non è nient’altro che una coppia < D, I > con D = dominio e I = leggi che possono esse- re I₁, I₂, I₃, le leggi possono essere viste come delle funzioni. Per esempio la prima legge I₁ attribuisce un valore alle varie costanti dei valori del dominio, I₂ associa delle operazioni alle lettere funzionali, I3 associa delle relazioni (=, ≥, < ecc) alle lettere predicative.

1.10.1 Esempio:

A²₂(a, b) ∨ ∃yA²₁ f₁²(x, y) , f₂²(a, x) ⇒ ∀x ∼ A²₁ f₁² x, f₂²(a, x) , b ∧ A²₂(x, x) Dominio: D = N.

I1 =

a → 1 b → 2 I2 =

f₁²(s, r) → s · r f₂²(s, r) → s + r I₃ =

A²₁(s, r) → s = r A²₂(s, r) → s < r se vogliamo essere ancora più precisi scriviamo

I1(a) = 1 I₁(b) = 2 I2 f₁²

= ’· ’ I2 f₂²

= ’ + ’ I3 A²₁

= ’ = ’ I₃ A²₂

= ’ < ’ ma per gli esami va bene solo la prima parte delle definizioni.

Poi dobbiamo scrivere a parole quello che è scritto formalmente nella formula: “Se 1 < 2 oppure esiste y ∈ N tale che x · y = 1 + x, allora per ogni x ∈ N, x · (1 + x) 6= 2 e x < x”. Ora dobbiamo verificare se è vera o falsa. In questo caso è sempre falsa, perchè 1 < 2 è sempre vero mentre il conseguente è sempre falso perchè x < x è sempre falso.

1.11 Assegnamento di valori

È una funzione che ad ogni variabile assegna un valore del dominio. Indichiamo con V ar l’insieme delle variabili: s : V ar → D, l’assegnamento vero e proprio è s (x) = 5, s (y) = 9. Possiamo estendere l’assegnamento con s^∗ : T er → D, ad ogni termine associa un valore. Ma siccome agisce sui termini dobbiamo verificare come si comporta con le costanti (attribuirà il valore che già assegnava prima):

1. s^∗(c) = I1(c) per ogni costante c.

2. s^∗(x) = s (x) per ogni variabile x.

3. s^∗(f_iⁿ(t1t2, . . . , tn)) = I2(f_iⁿ) (s^∗(t1) , . . . , s^∗(tn)) se vediamo inizialmente avevamo detto che I2agiva sulle lettere funzionali.

(7)

1.11.1 Esempio:

A²₂(a, b) ∨ ∃yA²₁ f₁²(x, y) , f₂²(a, x) ⇒ ∀x ∼ A²₁ f₁² x, f₂²(a, x) , b ∧ A²₂(x, x) 1. s^∗(a) = I₁(a) = 1, s^∗(b) = I₁(b) = 2.

2. s^∗(x) = s (x) = 5, s^∗(y) = s (y) = 9.

3. Le lettere predicative non le considero,

s^∗ f₁²(x, y) = I2 f₁² (s^∗(x) , s^∗(y)) = · (5, 9) = 5 · 9 = 45 s^∗ f₂²(a, y) = I2 f₂² (s^∗(a) , s^∗(y)) = + (1, 5) = 1 + 5 = 6 ma 45 6= 6 e quindi non è soddisfatta la formula.

4. A₁² f₁²(x, y) , f₂²(a, x) = s^∗ f₁²(x, y) , s^∗ f₂²(a, x) = (45, 6) ∈ I3 A²₁? No perchè non appar- tiene alla relazione che interpreta l’uguaglianza (46 6= 6). Non soddisfa questa formula atomica.

1.12 Soddisfazione di una formula

Consideriamo Aⁿ_i (t₁, t₂, . . . , t_n) formula atomica con t₁, t₂, . . . , t_n termini. Abbiamo anche un’interpretazione < D, I > e s : V ar → D assegnamento. s soddisfa la formula atomica Aⁿ_i (t₁, t₂, . . . , t_n) se e solo se la n-upla (s^∗(t₁) , . . . , s^∗(t_n)) ∈ I₃(Aⁿ_i).

Sia data < D, I > interpretazione, F, G, H f.b.f, sia dato un assegnamento di variabili s : V ar → D.

• Se F è G ∧ H, allora s soddisfa F se e solo se s soddisfa sia G che H.

• Se F è G ∨ H, s soddisfa F se e solo se s soddisfa G oppure H.

• Se F è G ⇒ H, s soddisfa F se e solo se s soddisfa H oppure s non soddisfa G.

• Se F è G ⇔ H, s soddisfa F se e solo se s soddisfa G e H oppure s non soddisfa nè G nè H.

• Se F è (∀xG), s soddisfa F se e solo se ogni assegnamento di valori alle variabili s⁰ che differisce da s al più per il valore assegnato alla variabile x soddisfa la formula G.

• Se F è (∃xG), s soddisfa F se e solo se esiste un assegnamento di valori alle variabili s⁰ che differisce al più per il valore assegnato alla variabile x e che questo assegnamento soddisfa G.

1.12.1 Esempio

∀x A¹₁(x) ∧ A²₁(y, y), Avendo < D, I > prendiamo D = N, siccome non ci sono costanti e lettere funzionali non abbiamo bisogno di I1, I2. I3 sarà: A¹₁(s) → “s è un numero primo”. Abbiamo un assegnamento di valori alle variabili s : {x, y, t} → N, le immagini saranno







s (x) = 2 s (y) = 7 s (t) = 6

(8)

Come abbiamo scritto prima nella definizione s soddisfa ∀x a¹₁(x) ∧ A²₁(y, t) se e solo se ogni as-

segnamento di valori alle variabili

s⁰: {x, y, t} → N s⁰(x) = . . .

s⁰(y) = 7 s⁰(t) = 6

soddisfa la formula A¹₁(x)∧A²₁(y, t). Ora pren-

diamo un x a caso s⁰(x) = 4 perchè “per ogni”, in questo caso

4è numero primo? NO z }| {

A¹₁(x) ∧ A²₁(y, t)

| {z }

7>6

. s⁰ non soddisfa la formula. In pratica devo cercare un numero che non va bene, se non lo trovo allora vado avanti. Se invece di∀ avessimo avuto ∃ dovevamo cercare almeno una variabile che soddisfava la formula, se la troviamo va bene.

1.13 Vero, falso, soddisfacibile rispetto ad un’interpretazione

Consideriamo < D, I >, F f.b.f.:

• F è vera nell’interpretazione < D, I > se e solo se ogni assegnamento s soddisfa F .

• F è soddisfacibile nell’interpretazione < D, I > se esiste un assegnamento s che soddisfa F .

• F è falsa o insoddisfacibile nell’interpretazione < D, I > se nessun assegnamento di valori alle variabili soddisfa F .

Una formula vera è ovviamente anche soddisfacibile. Ora vediamo le f.b.f. in generale senza una determinata interpretazione:

• F è (logicamente) valida ( F ) se è vera in tutte le interpretazioni.

• F è insoddisfacibile (o logicamente contraddittoria) se è falsa in tutte le interpreta- zioni.

Osservazione: la formula F è logicamente valida se e solo se ∼ F è insoddisfacibile. Se tutte le variabili sono vincolate, se la formula è chiusa allora o è vera o è falsa, non può essere soddisfacibile ma non vera.

• La chiusura universale di F è vera se e solo se F è vera in < D, I >.

• La chiusura esistenziale di F è vera se e solo se F è soddisfacibile in < D, I >.

1.13.1 Metodo per verificare che f.b.f. è logicamente valida

Una f.b.f. è logicamente valida se è una tautologia nella logica proposizionale. Per verificare questo sostituiamo, al posto delle formule del primo ordine, le lettere della logica proposizio- nale, questo si chiama esempio di tautologia.

Esempio:

∀xA²(x, y) ⇒ B²(x, y) ⇒ C¹(x) ⇒∼ B²(x, y) ⇒ C¹(x) ⇒∼ (∀x) A²(x, y) introduco la lettera enunciativa e le sostituisco

A → ∀xA²(x, y) B → B²(x, y) C → C (x)

(9)

quindi la nostra formula sarà

(A ⇒ B) ⇒ ((C ⇒∼ B) ⇒ (C ⇒∼ A))

se riesco a verificare che essa è una tautologia allora anche la formula di partenza lo sarà. In questo caso è una tautologia quindi anche la formula di partenza è una tautologia quindi è una formula logicamente valida

1.14 Insiemi di f.b.f.

Sia < D, I > interpretazione, F f.b.f. e s assegnamento.

• < D, I, s > è un modello per F se e solo se soddisfa F in < D, I >.

Sia Γ insieme di f.b.f.:

• < D, I, s > è un modello per Γ se e e solo se < D, I, s > è modello per ogni formula di Γ.

• Γ F se e solo se ogni modello di Γ è modello anche per F . Teorema. Γ ∪ {G} F se e solo se Γ G ⇒ F

F ≡ G sono semanticamente equivalenti se e solo se F G e G F . Osservazione: F ≡ G se e solo se F ⇔ G è logicamente valida.

1.15 Formula normale prenessa

È una formula in cui i quantificatori figurano soltanto in testa alla formula ossia:

(Q₁x₁) (Q₂x₂) . . . (Q_nx_n)

| {z }

prefisso

F

|{z}

matrice

dove Q1, Q2, . . . Qn sono quantificatori. Per trasformare una formula in normale prenessa usere- mo queste equivalenze

1. ∼ ∀xF (x) ≡ ∃x ∼ F (x);

2. ∼ ∃xF (x) ≡ ∀x ∼ F (x);

3. ∀xF (x) ∧ G ≡ ∀y (F [^y/x] ∧ G); Vedi nota sotto.

4. ∃xF (x) ∧ G ≡ ∃y (F [^y/x] ∧ G);

5. ∀xF (x) ∨ G ≡ ∀y (F [^y/x] ∨ G);

6. ∃xF (x) ∨ G ≡ ∃y (F [^y/x] ∨ G);

7. ∀xF (x) ⇒ G ≡ ∃y (F [^y/x] ⇒ G);

8. ∃xF (x) ⇒ G ≡ ∀y (F [^y/x] ⇒ G);

9. G ⇒ ∀xF (x) ≡ ∀y (G ⇒ F [^y/x]);

10. G ⇒ ∃xF (x) ≡ ∃y (G ⇒ F [^y/x]).

11. Per la coimplicazione ricorda che F ⇔ G ≡ (F ⇒ G) ∧ (G ⇒ F )

(10)

Nota: Se F (x) è una formula in cui abbiamo x variabile libera e y è una variabile tale che y è un termine libero per x in F (x), rinominiamo tutte le occorrenze libere di x con y nella formula F (non modificare quelle vincolate). La nuova formula si scriverà F [^y/x]. Si osservi che se G non contiene occorrenze libere di x non serve fare il cambio di nome della variabile. In pratica se notiamo che in entrambe le formule abbiamo x libere dobbiamo applicare la sostituzione F [^y/x] per evitare ambiguità, visto che sono 2 variabili distinte.

Infine ricorda che i quantificatori si riferiscono solo alla sottoformula che segue se non ci sono parentesi.

1.15.1 Esempio:

∀x

campo d’azione del quantif.

z }| {

A²₁ x, f₁²(y, z) ∨ A²₂(x, y)

⇒ ∀xA²₁ x, f₁²(y, z) ∨ ∀xA²₂(x, y)

notiamo che la formula dopo l’implica abbiamo che tutte le x sono vincolate, quindi non dobbiamo rinominare nessuna variabile, inoltre gli ultimi due quantificatori dobbiamo portarli al- l’esterno usando le equivalenze scritte sopra, quindi:

∃x





 A²₁ x, f₁²(y, z) ∨ A²₂(x, y) ⇒ ∀x





A²₁ x, f₁²(y, z)

| {z }

G

∨∀xA²₂(x, y)













ora l’ultimo quantificatore lo dobbiamo portare fuori, stiamo attenti a verificare che non ci siano occorrenze libere di x, notiamo che nella formula G abbiamo un occorrenza libera di x (in realtà è vincolata dal quantificatore esterno, ma facendo le equivalenze noi “non vediamo” il quantificatore perchè è esterno alla nostra equivalenza che stiamo per effettuare, quindi:

∃x A²₁ x, f₁²(y, z) ∨ A²₂(x, y) ⇒ ∀x∀v A²₁ x, f₁²(y, z) ∨ A²₂(v, y)

stando sempre attenti se non abbiamo delle variabili libere abbiamo che

∃x∀w∀v

| {z } prefisso

A²₁ x, f₁²(y, z) ∨ A²₂(x, y) ⇒ A²₁ w, f₁²(y, z) ∨ A²₂(v, y)

| {z }

matrice 1.15.2 Formula di Skolem

Il primo passo è di scrivere la formula nella forma normale prenessa, poi dobbiamo eli- minare i quantificatori esistenziali con cui inizia la formula, e le variabili dei quantificatori diventano delle costanti. I quantificatori universali non la modifichiamo. Se il quantificatore esistenziale viene dopo al quantificatore universale dobbiamo utilizzare un altro modo. Cancello il quantificatore esistenziale e tutte le occorrenze della variabile del quantificatore esistenziale lo cambiamo con una lettera funzionale di arità n dove n è il numero di quantificatori universali che precedono il quantificatore esistenziale. Per esempio:

∀x∀y>

z → f²(x, y)

∃zF

Si osservi che se si prende una formula A non chiusa, se ne trova la forma di Skolem A’ e poi si fa la chiusura universale di A’, questa non è la forma di Skolem della chiusura universale di A.

(11)

1.15.3 Esempio formula di Skolem

∃x

|{z}

x→c

∀y∀z ∃w

|{z}

w→f₁²(y,z)

∃v A²₁(x, y) ∧ A²₁(v, z) ⇒ A³₁(x, u, v)

modificando i primi due quantificatori esistenziali abbiamo:

∀y∀z ∃v

|{z}

v→f₂²(y,z)

A²₁(c, y) ∧ A²₁(v, z) ⇒ A³₁ c, f₁²(y, z) , v

quindi alla fine avremo

∀y∀z A²₁(c, y) ∧ A²₁ f₂²(y, z) , z ⇒ A³₁ c, f₁²(y, z) , f₂²(y, z)

in generale la formula di Skolem e la formula iniziale non sono semanticamente equi- valenti. Grazie ad un teorema sappiamo che se una formula è soddisfacibile per qualche interpretazione anche la formula di Skolem lo sarà.

2 Clausole

Diamo alcune definizioni:

• Si dice letterale una formula atomica (letterale positivo) o la negazione di una formula atomica (letterale negativo).

• Si dice clausola la disgiunzione (finita) di letterali.

• Una clausola viene rappresentata come insieme di letterali; una clausola che non contiene letterali si dice vuota e si indica con .

• Una f.b.f. chiusa in forma normale di Skolem si dice in forma a clausole se la sua matrice è scritta come congiunzione di clausole, in tal caso la matrice della f.b.f. sarà denotata come insieme di insiemi.

• Ogni formula chiusa in forma normale di Skolem ammette una formula equivalente in forma a clausole.

2.1 Sostituzione

Una sostituzione è un insieme di sostituzioni di questo tipo σ = {^t¹/x₁,^t²/x₂, . . . ,^t^k/x_k}, se i 6= j allora xi 6= xj ossia sono tutte variabili distinte. Supponiamo di avere un linguaggio del primo ordine L, vuol dire che abbiamo fissato un alfabeto di simboli (come abbiamo sempre fatto), indichiamo con E un espressione del linguaggio L qualsiasi (potrebbe anche non aver senso, ossia può anche non essere f.b.f.). Eσ significa applicare la trasformazione σ alla nostra espressione E, per esempio se

E = f₁²(x, y) σ = {^c/x}

allora abbiamo Eσ = f₁²(c, y). Ricorda chele sostituzioni si applicano solo alle variabili e non alle costanti o lettere funzionali.

Se invece abbiamo un insieme di espressioni lavoriamo allo stesso modo, per esempio se abbiamo:

{E1, E2, . . . , En} insieme di espressioni di L

si dice che è unificabile se esiste una sostituzione σ tale che applicando σ a tutte queste espressioni (E1σ = E2σ = . . . = Enσ) otteniamo sempre la stessa espressione, σ in tal caso si chiama unificatore. Possiamo notare anche che se l’unificatore esiste non è unico.

(12)

2.1.1 Esempio

Abbiamo

E₁ = f₁²(x, a) E2 = f₁²(y, z)

l’insieme delle espressioni è{E1, E₂} applichiamo la seguente sostituzione σ1= {^x/y,^a/z} avremo che

E₁σ = f₁²(x, a) E2σ = f₁²(x, a)

quindi E1σ1 = E2σ1 quindi σ1 è unificatore e abbiamo unificato le formule. Ma ne possiamo trovare altre di unificatori percè non è unico.

2.2 Prodotto di sostituzioni

Abbiamo σ = {^t¹/x₁,^t²/x₂, . . . ,^t^k/x_k}, θ = {û¹/y₁,û²/y₂, . . . ,û^h/y_h} il prodotto di sostituzioni è

• Se tiθ = xi allora cancelliamo^tⁱ^θ/x_i.

• Se yj = xiallora cancelliamo^u^j/y_j.

2.2.1 Unificatore più generale:

{E1, E2, . . . , En} insieme di espressioni su L unificabile, e poi sia σ un unificatore. Allora diciamo che σ è un unificatore più generale se per ogni altro unificatore θ esiste una sostituzione ρ tale che θ = σ · ρ.

2.2.2 Esempio

Abbiamo che σ₃= σ₁· {^a/x,^a/y}

| {z }

ρ

. σ₃= {â/x,â/y,â/z}, σ₁= {^x/y,â/z}, ρ = {â/x,â/y} abbiamo che

{^x/y,^a/z}

| {z }

σ₁

· {^a/x,^a/y}

| {z }

ρ

= {^xρ/y,âρ/z,â/x,â/y} =n

a/y,â/z,â/x,â/y

o

= σ3

2.2.3 Algoritmo per determinare l’unificatore generale

E₁ = f³ x, y, f²(a, x) E2 = f³ b, x, f²(a, c)

iniziamo a leggere da sinistra a destra dall’alto verso il basso. Quindi leggiamo f³, f³ se sono tutti uguali andiamo avanti, poi leggiamo x, b: al posto della variabile sostituiamo il termine che stiamo considerando, quindi σ₁= {^b/x} quindi otteniamo

E1σ1 = f³ b, y, f²(a, x) E₂σ₁ = f³ b, b, f²(a, c)

(13)

vado avanti a leggere e trovo y, b sostituisco i termini con la variabile che ho letto ossia σ2= {^b/y} (E1σ1) σ2 = f³ b, b, f²(a, b)

(E2σ1) σ2 = f³ b, b, f²(a, c)

ora leggiamo che abbiamo a, a e va bene. Poi leggiamo b, c sono due costanti e le costanti non possono essere sostituite, quindi le formule non sono unificabili. Se troviamo una lettera funzionale la dobbiamo inserire alle varie variabili che troviamo in verticale.

2.3 Risolvente

La risolvente di due clausole C1e C2si calcola in questo modo:

1. Separazione delle variabili: prima di tutto bisogna scrivere in forma a clausole di Skolem usando solo la matrice. Applico le sostituzioni σ1, σ₂, quindi avremo C1σ₁ e C2σ₂, in modo tale che non vi siano più variabili con lo stesso nome tra C₁, C₂. In altre parole se nella prima e seconda formula abbiamo x le rinominiamo rispettivamente x₁, x₂ per evitare sovrapposizione di nomi.

2. Fattorizzazione: significa vedere se ci sono dei letterali L1, L2, . . . , Lkdi C1σ1e Lk+1, Lk+2, . . . , Lk+h

letterali di C2σ2 tali che l’insieme L1, L2, . . . , Lk, Lk+1, Lk+2, . . . , Lk+h sia unificabile e che quindi siamo in grado di trovare un unificatore più generale σ. La barra significa che sono negati. Lk+i significa Aⁿ_k+i(. . . ) se Lk+i significa ∼ Ak+i(. . . ). Sia infine L = L1σ = L2σ =

· · · = Lkσ = Lk+iσ = · · · = Lk+hσ quello che otteniamo.

3. Risolvente: R = ((C1σ1) σ\ {L}) ∪ ((C2σ2) σ\ {∼ L}).

2.3.1 Esempio

C₁ = A²₁(x, a) , A²₁(z, y) , A¹₁(a) C2 = ∼ A²₁ f₁²(x) , y , A²₂(x, b)

Notiamo che in entrambi gli insiemi di clausole abbiamo x, y, applichiamo quindi la sostituzione σ₂= {^v/x,^w/y}

così da rinominare le variabili in C₂

C2σ2=∼ A²₁ f₁¹(v) , w , A²₂(v, b)

Ora cerchiamo un unificatore più generale delle formule con l’algoritmo che abbiamo analizzato prima e vediamo che tale unificatore è

σ =_f1

1(v)/x,^f1¹(v)/z,^a/y,^a/w così otteniamo

C₁σ = n

A²₁ f₁¹(v) , a ,

A²₁ f₁¹(v) , a, A¹₁(a)o (C2σ2) σ = ∼ A²₁ f₁¹(v) , a , A²₂ f₁¹(v) , b quindi la risolvente sarà:

R =A¹₁(a) , A²₂ f₁¹(v) , b

(14)

2.3.2 Risolvente

Sia Γ insieme di clausole, C clausola. Derivazione della clausola C a partire da Γ, ossia Γ `R C è come la logica proposizionale.

Teorema. Sia Γ un insieme di clausole Γ è insoddisfacibile se e solo se Γ `R.

Questo teorema è importante perchè sappiamo che F è conseguenza semantica di Γ (Γ F ) se e solo se Γ ∪ {∼ F } è insoddisfacibile.

F è logicamente valida ( F ) se e solo se ∼ F è insoddisfacibile, ma ∼ F è insoddisfacibile se e solo se{∼ F }^C`R. Non è detto che riusciamo nell’intento perchè non è decidibile.

3 Teoria formale K

Sia A f.b.f., Γ insieme di f.b.f., Γ `H A.

• Se Γ `H A allora Γ A (correttezza);

• Se Γ A allora Γ `H A (completezza).

3.1 Simboli

• Lettere enunciative: A, B, . . . ;

• Connettivi: ∼, ⇒;

• Quantificatore universale: ∀x;

• Simboli ausiliari: (, ).

3.2 Formule ben formate

• Lettere enunciative.

• Se A è f.b.f. allora ∼ A è f.b.f.;

• Se A è f.b.f. allora ∀xA è f.b.f.;

• Se A, B sono f.b.f. allora A ⇒ B è f.b.f.

• Nient’altro è f.b.f.

3.3 Assiomi

1. A ⇒ (B ⇒ A);

2. (A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C));

3. (∼ A ⇒∼ B) ⇒ ((∼ A ⇒ B) ⇒ A);

4. (∀xA (x)) ⇒ A (^t/x) con t termine libero per x;

5. ∀x (A ⇒ B) ⇒ (A ⇒ ∀xB) (A non contiene occorrenze libere di x).

(15)

3.4 Regole di inferenza

• Modus Ponens (MP): dalle formule A e A ⇒ B si riscrive B.

• Generalizzazione (Gen): dalla formula A si riscrive ∀xA.

Se Γ `K A allora Γ A: questo mi dice che la teoria formale K è corretta. Viceversa se Γ A allora Γ `K A (completa). Ricordo inoltre che la teoria formale K non è decidibile, ossia non esiste alcun algoritmo che con un numero finito di passi permette di decidere se una data formula è un teorema o non è un teorema della teoria.

3.5 Aggiunte con identità

Sia A²₁teoria del primo ordine con identità aggiungiamo anche gli assiomi 1. ∀xA²₁(x, x);

2. A²₁(x, y) ⇒ (A (x, x) ⇒ A (x, [^y/x])).

3.5.1 Quantificatore esistenziale

∃! oppure ∃| è l’abbreviazione di ∃x A (x) ∧ ∀y A (y) ⇒ A²₁(x, y) ma questo lo possiamo scrivere solo nelle teorie formali con identità.