©Nicola Galesi – Draft

Appunti del corso di

Logica Matematica1

Nicola Galesi2

Ultimo aggiornamento: 7 Dicembre 2024

1
Corso di Laurea in Filosofia & Intelligenza Artificiale, a.a. 24-25
2
DIAG, Sapienza. galesi@[Link]
 WARNING/ATTENZIONE !
Si fa presente quanto segue

1. Questi sono appunti scritti dal docente durante il corso e quindi non soggetti a una revisione accurata. Possono
dunque includere errori e sviste. Nel caso si trovino errori e sviste si prega di segnalarle al docente stesso via
email con un mail con SUBJECT: REV NOTE LogMat
2. Le note sono destinate unicamente agli studenti del corso L OGICA M ATEMATICA del corso di Laurea in
Filosofia & Intelligenza Artificiale.
3. È fatto assoluto divieto a chiunque di farne alcun uso tranne quello di usarle per studiare il corso. In particolare
di distribuirle in qualunque forma e per qualunque ragione fino a quando io stesso non lo riterrò opportuno e
©Nicola Galesi – Draft

nel caso ne deciderò le forme. Se dovessi accorgermi che sono distribuite in qualunque forma sarò costretto a
toglierle e a proteggere i miei scritti per quanto parziali.

4. Le note saranno aggiornate nel tempo.

5. Queste dispense contengono materiale (includendo gli esercizi) originale del docente e materiale liberamente
tratto dai seguenti testi:
[1] E. Mendelson. Introduzione alla logica Matematica. Boringhieri, 1978.
[2] A.G. Hamilton. Logic for Mathematicians - Revised Edition. Cambridge University Press, 2000
[3] D. Van Dalen. Logic and Structure - Revised edition. Springer 2000
[4] A. Asperti e A. Ciabattoni. Logica a Informatica. McGraw Hil, 1997
[5] M.L. Schagrin, W.J, Rapaport, R.R. Dipert. Logica e Computer. McGraw Hil, 1997
[6] L. Carlucci. Note delle lezioni del corso di Logica Matematica. Draft, 2022
[7] N. Galesi, J. Toràn. A Gentle Introduction to Propositional Proof Complexity. Draft 2024

1
 Indice
©Nicola Galesi – Draft

1 Logica Proposizionale 3
1.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Connettivi Booleani . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Equivalenza e doppia implicazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Sintassi: linguaggio e formule proposizionali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Induzione strutturale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Assegnamenti, interpretazioni e Tavole di Verità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 Tavole di Verità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.2 TAUT, SAT, UNSAT e decidibilità della Logica proposizionale . . . . . . . . . . . . . . . . 8
1.4.3 Equivalenza semantica e leggi logiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Conseguenza logica e Teorema di Deduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Formalizzazione tramite formule proposizionali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.1 3-Colorabilità di un grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6.2 Principio dei Cassetti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.7 Sostituzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.8 Completezza funzionale e forme normali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.8.1 Forme normali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.9 Teorema di Compattezza: Cenni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2 Calcolo Proposizionale 22
2.1 Proprietà intuitive sistemi deduttivi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Sistemi deduttivi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.1 Sistemi Assiomatici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.2 Calcolo dei Sequenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Eliminazione del Taglio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4 Invertibilità delle regole di LK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 Un algoritmo per la ricerca di dimostrazioni in LK . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.6 Correttezza e Completezza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3 Logica del I° ordine 34

3.1 Limiti espressivi della Logica Proposizionale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2 Linguaggio del I° ordine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.1 Sostituzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 Semantica: interpretazioni e valore di verità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4 Verità, soddfisfacibilità e modelli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4.1 Paradosso del Barbiere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.5 Ragionare di Semantica nel metalinguaggio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.6 Forme Normali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.6.1 Equivalenza Logica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.6.2 Forma Prenessa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

2
 3.6.3 Forma di Skolem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.7 Esempi di linguaggi del I° ordine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.7.1 Uguaglianza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.7.2 Ordini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4 Calcolo dei Predicati 56

4.1 Regole intuitive per i quantificatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2 Calcolo dei sequenti per la logica dei predicati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.3 Invertibilità delle regole e rami di dimostrazione infiniti . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.4 Completezza e Correttezza del calcolo dei predicati . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.5 Semi-decidibilità del problema delle decisione per la logica dei predicati . . . . . . . . . . . . . . . . 63
©Nicola Galesi – Draft

5 Sistemi refutazionali proposizionali 64

5.1 Risoluzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.1.1 Proprietà generali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.1.2 Correttezza e Completezza della Risoluzione . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.1.3 Ricerca automatica di refutazioni in Risoluzione e problema SAT . . . . . . . . . . . . . . . 64
5.1.4 Programmazione Logica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

6 Il problema P versus NP e la complessità delle dimostrazioni 65

6.1 Algoritmi deterministici e non-deterministici: Macchine di Turing . . . . . . . . . . . . . . . . . . . 65
6.2 Le classi P e NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.3 SAT e NP-completezza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.4 Importanza matematica e filosofica del problema P vs NP . . . . . . . . . . . . . . . . . . . . . . . . 67
6.5 Complessità delle dimostrazioni logiche come approccio al problema P vs NP: Teorema di Cook-
Reckhow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

7 Cenni sui Teoremi di Gödel 68

8 Esercizi 69
8.1 Esercizi su logica proposizionale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
8.2 Esercizi su Calcolo proposizionale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
8.3 Esercizi su logica predicativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
8.3.1 Esercizi su semantica, verità, modelli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
8.3.2 Esercizi su semantica e forme normali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
8.4 Esercizi su Calcolo dei Predicati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
8.5 Esercizi di Ricapitolazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

3
 Capitolo 1

Logica Proposizionale
©Nicola Galesi – Draft

1.1 Introduzione
La Logica Matematica si occupa della validità di ragionamenti indipendentemente dal significato delle loro compo-
nenti. In quanto tale verranno presi in considerazioni (almeno) due aspetti: come stabilire la validità di una asserzione
e come stabilire la validità di una sequenza di asserzioni che forma un ragionamento, o in definitiva quando una
ragionamento può essere considerato corretto.
In linguaggio naturale una sentenza è un aggregato di parole di senso compiuto. Se la sentenza è una asserzione -
ad esempio due è un numero pari - allora la sentenza è detta dichiarativa. Ads esempio
• due è un numero pari,
• oggi piove,
√
• 2 è un numero razionale.
Le sentenze (o nomi, da Frege) denotano un qualche oggetto. Ad esempio
• quattro,
• il quadrato di due,
• il predecessore di cinque,
denotano lo stesso oggetto che in questo caso è il numero 4. Benché le frasi precedente denotino lo stesso oggetto il
loro senso è differente.
Ad esempio due algoritmi di ordinamento che ordinano un vettore (Merge sort e Quicksort) denotano lo stesso
oggetto, ma hanno senso diverso, che corripsonde al particollare algoritmo di ordinamento scelto.
In che modo la denotazione delle asserzioni rimane invariante tra i differenti sensi ?. Consideriamo il seguente
esempio: "quattro è il predecessore di cinque" e sostituiamo a "predecessore di 5" una asserzione con uguale denota-
zione. per esempio "quattro". otteniamo dunque una ulteriore asserzione data da "quattro è quattro". Cosa hanno in
comune le precedenti due asserzioni. Solo il fatto che sono vere.
Dal punto di vista classico dunque la denotazione associata ad una sentenza non può che essere un valore di verità:
V ERO oppure FALSO. Diremo dunque che il senso determina la denotazione e che ogni sentenza assertiva denota un
valore di verità (oggetto di indagine della Logica) ed esprime un senso (il quale tuttavia non è oggetto di indagine della
Logica).
Definizione 1 (P ROPOSIZIONI)

I nomi (o sentenze assertive) che denotano valori di verità sono dette PROPOSIZIONI.

4
 Lal Logica Proposizionale si occupa precisamente dell proposizioni, di come possono essere composte e mani-
polate e di come la loro composizione o manipolazione agisce sul valore di verità finale. Per tanto le proposizioni
possono essere di due tipi: ATOMICHE e COMPOSTE. Le prime sono proposizioni che non possono essere scomposte
ulteriormente, le seconde invece sono formate da proposizioni a partire dai CONNETTIVI LOGICI

1.2 Connettivi Booleani

Nel linguaggio naturale esempi di connettivi sono: "e", "oppure", "Se . . . allora" (implicazione), "non", "se e solo se"
(doppia implicazione) . . . 1 . L’operazione espressa dal connettivo "non" è la negazione. La proposizione ottenuta dalla
sua applicazione ad una proposizione è detta proposizione negata. Ad esempio
©Nicola Galesi – Draft

• la negata di "2 è un numero primo", è

• "2 non è un numero primo".

L’operazione espressa dal connettivo "e" è la congiunzione. Ad esempio

• "5 è un numero dispari e 5 è primo", è la congiunzione di
• "5 è un numero dispari" e "5 è primo".

L’operazione espressa dal connettivo "oppure" è la disgiunzione. Ad esempio

• "5 è un numero dispari oppure è primo", è ottenuta per disgiunzione da
• "5 è un numero dispari" e "5 è primo".
L’operazione espressa dal connettivo "se . . . allora" è la implicazione. La proposizione ottenuta dalla sua applica-
zione ad una proposizione è detta condizionale. Ad esempio
• "5 è un numero dispari allora 2 è primo", è una proposizione condizionale ottenuta per implicazione da
• "5 è un numero dispari" e "2 è primo". La proposizione "5 è un numero dispari" è detta premessa della
implicazione, mentre "2 è primo". è detta conclusione della implicazione.

1.2.1 Equivalenza e doppia implicazione

A volte possiamo scrivere delle proposizioni mediante l’uso del connettivo della equivalenza o doppia implicazione
espresso in italiano tramite la scrittura "se e solo se". Ad esempio

• "5 è un numero dispari se e solo se 2 è primo", è una equivalenza ottenuta dalle propisizioni
• "5 è un numero dispari" e "2 è primo".
Si osservi che è possibile anche definire l’operazione si "solo se", per esempi nella scrittura "5 è un numero dispari
se e solo se 2 è primo" può essere costruita come la congiunzione delle due proposizioni "5 è un numero dispari se 2
è primo" e "5 è un numero dispari solo se 2 è primo". Si noti che la prima corrisponde all’implicazione "se 2 è primo
allora "5 è un numero dispari", mentre la seconda "se 5 è un numero dispari allora 2 è primo"
1 Connettivi estenionali e nomi obliqui

5
 1.3 Sintassi: linguaggio e formule proposizionali
Il primo passo è quello di definire un linguaggio formale rigoroso che consenta un trattamento matematico della logica
proposizionale matematico. Definiremo dunque delle stringhe (chiamate formule ben formate), senza associare loro
alcun significato in modo da formalizzare matematicamente il concetto di proposizione. Per far ciò abbiamo bisogno
di definire un alfabeto e una grammatica, ovvero delle regole che consentono di formare stringhe corrette.
Le formule formule ottenute applicando i connettivi Booleani ad alcuni mattoncini atomici, detti variabili pro-
posizionali. Queste variabili rappresentano, intuitivamente, proposizioni non ulteriormente analizzabili in termini di
operatori logici come negazione, congiunzione, disgiunzione, implicazione o doppia implicazione. Una scelta di tali
variabili definisce un cosiddetto linguaggio proposizionale. I connettivi verranno rappresentati tramite i simboli

• ∧ congiunzione,
©Nicola Galesi – Draft

• ∨ disgiunzione,
• ¬ negazione,
• → implicazione,

• ↔ equivalenza,

Definizione 2 (L INGUAGGIO P ROPOSIZIONALE )

Un linguaggio proposizionale è un un insieme (infinito) L = {p1 , p2 , . . .} di simboli detti variabili proposi-

zionali in unione con l’insieme di simboli {¬, ∧, ∨, →, ↔, ⊥, (, )}. Le variabili pi sono detti simboli atomici,
i simboli ”(”, ”)” sono i simboli ausiliari.

Esempio 1. Immaginiamo di voler ragionare su grafi, ossia su strutture G = (V, E), con E ⊆ V × V che denota
la relazione d’arco (edge). In questo caso i fatti elementari sono naturalmente individuabili nella sussistenza di un
arco tra due punti. La scelta naturale di un linguaggio proposizionale in questo caso é quella che include una variabile
proposizionale pv,w per ogni v, w ∈ V . Il significato intuitivo di pv,w è che vale (v, w) ∈ E, ossia che v e w siano
adiacenti nel grafo.
Diamo adesso le regole che consentono di definire a partire dal linguaggio le stringhe sintatticamente corrette del
linguaggio. Verranno dette formule ben formate FBF. Le formule/proposizioni saranno rappresentate con lettere
maiuscole (per esempio A, B, C, . . . , P, Q . . .).
Le proposizioni saranno rappresentate con lettere maiuscole (per esempio A, B, C, . . . , P, Q . . .).
Definizione 3 (F ORMULE BEN F ORMATE - FBF)

FBF è il minimo insieme X tale che

• pi ∈ X per ongi simbolo atomico pi ,
• ⊥ ∈ X,

• Se P, Q ∈ X, allora (¬P ) ∈ X, (P ∨ Q) ∈ X ,(P → Q) ∈ X ,(P ↔ Q) ∈ X.

def
Esempio 2. A = ((p1 ∧ p2 ) → ((p3 ∨ p4 ) ∧ (¬p5 )))

Diamo un esempio del perché nella definizione di FBF è importante prendere il minimo insieme X che verifica le
quattro proprietà.
Proposizione 1. ¬⊥ ↛∈ FBF.

6
 Dimostrazione. Supponiamo per assurdo che ¬⊥ →∈ FBF dunque X ∪ {¬⊥ →} soddisfa le proprietà (1)-(4) della
Definizione precedente. Ma allora dovrebbe essere il minimo insieme che le verifica. Ma ciò non è vero perché anche
il solo X che è strettamente incluso in X ∪ {¬⊥ →} le soddisfa. Contraddizione.

In una una formula proposizionale è possibile ridurre il numero di parentesi dando, come avviene per le normali
espressioni algebriche, una regola di priorità tra i connettivi. La regola di priorità usata per i connettivi Booleani è la
seguente : ¬ ha maggiore priorità, poi, il connettivo ∧, quindi ∨ e infine → e ↔. Come ulteriore regola è bene dare
uguale priorità al∧ e al ∨ per non creare troppa confusione.

Esempio 3. ¬A ∧ B è la formula (¬A ∧ B). A ∧ B → C è la formula ((A ∧ B) → C). A ∧ B ∨ C → ¬C è la

formula (((A ∧ B) ∨ C) → (¬C)).
©Nicola Galesi – Draft

1.3.1 Induzione strutturale

Come abbiamo visto le FBF vengono definite attraverso una definizione induttiva che viene detta induzione strutturale.
Teorema 1. Sia A() una proprietà. A(P ) è vera per ogni FBF P se
1. (Caso Base) A è vera per ⊥ e per ogni variabile proposizionale pi

2. (Caso Induttivo) Se A è vera per le FBF A e B, allora A è vera per ¬A, A ∧ B, A ∨ B,A → B, A ↔ B.
Dimostrazione. Sia Y = {F : A(F ) è vera}. Quindi Y ⊆ FBF. D’altra parte siccome le formule in Y verificano la
definizione di FBF, deve essere che FBF ⊆ Y . Dunque Y = FBF.
Data una formula proposizionale F , un’importante classe di formule è quella delle sottoformule di F che intuiti-
vamente corrisponde a tutte quelle formule P che appaiono come componente di A.
Definizione 4 (S OTTOFORMULE )

Sia F una FBF. L’insieme delle sottoformule di F è così definito:

• Se F = pi oppure F = ⊥ allora le sottoformule di F sono F ,

• Se F è(¬P ), le sottoformule di F sono F stessa e le sottoformule di P .
• Se F é (P ∨ Q) oppure (P → Q) oppure (P ↔ Q) allora le sottoformule di F sono F stessa e le
sottoformule di P e quelle di Q.

1.4 Assegnamenti, interpretazioni e Tavole di Verità

Abbiamo visto che le proposizioni denotano valori di verità. Andiamo a vedere come definire il valore di verità di un
FBF. Innanzitutto le variabili proposizionali sono atomi che possono assumere il valore vero o falso. Noi denoteremo
il valore vero con 1 e il valore falso con 0. Ha quindi senso la seguente
Definizione 5 (A SSEGNAMENT 0)

Un ASSEGNAMENTO è una funzione α : L −→ {0, 1}

Esempio 4. Se L = {p1 , p2 , p3 } allora α1 e α2 sono due assegnamenti, con

α1 (p1 ) = 1, α1 (p2 ) = 0, α1 (p3 ) = 1

α2 (p1 ) = 0, α2 (p2 ) = 0, α2 (p3 ) = 0

7
 Esempio 5. Sia G il grafo G = (V, E) con V = {1, 2, 3} ed E = {(1, 1), (1, 2), (2, 3)}.

Definizione 6 (I NTERPRETAZIONE )

Una INTERPRETAZIONE è una funzione

v : FBF −→ {0, 1}
tale che

• (Base) v(pi ) ∈ {0, 1} e v(⊥) = 0 e

• (Induzione)
©Nicola Galesi – Draft


1 se v(P ) = 0
v(¬P ) =
0 se v(P ) = 1

1 se v(A) = v(B) = 1
v(A ∧ B) =
0 altrimenti

0 se v(A) = v(B) = 0
v(A ∨ B) =
1 altrimenti

1 se v(A) = v(B)
v(A ↔ B) =
0 altrimenti

0 se v(A) = 1 e v(B) = 0
v(A → B) =
1 altrimenti

Si osservi che l’implicazione è vera anche quando da una premessa falsa si evince una conclusione vera ovvero
quando non vi è connessione causale tra premessa e conseguenza. questo riprende la consuetudine matematica e
algebrica di di considerare vera proprietà vera a vuoto una proposizione ipotetica la cui premessa è falsa. Per esempio
Il fatto che ∅ ⊆ A per ogni insieme A discende dal fatto che a ∈ ∅ è sempre falso per ogni a e che B ⊆ A se e solo se
per ogni a a ∈ B → a ∈ A. Nel caso B = ∅ la premesse dell’implicazione è falso, pur tuttavia ∅ ⊆ A per ogni A.
Osserviamo ancora che se consideriamo i valori di verità 0 e 1 come numeri interi, il valore di verità di una FBF
può definirsi, nel caso v(¬P ) = 1 − v(P ), v(A ∧ P ) = min{v(A), v(B)}, v(A ∨ P ) = max{v(A), v(B)}.

1.4.1 Tavole di Verità

Esiste un altro modo per visualizzare il comportamento dei connettivi logici e che consente più facilmente di calcolare
il valore di verità di FBF complesse. Una TAVOLE DI VERITÀ è una tabella che descrive il valore di verità di una
formula in termini dei valori di verità delle proposizione atomiche che la compongono. Le tavole di verità per i
connettvi sono le seguenti:
A B A ∧ B A ∨ B ¬A
0 0 0 0 1
0 1 0 1 1
1 0 0 1 0
1 1 1 1 0
A B A→B A↔B ¬A
0 0 1 1 1
0 1 1 0 1
1 0 0 0 0
1 1 1 1 0

8
 Possiamo costruire tavole di verità piu complesse a partire da quelle per i connettivi:
def
Esempio 6. Costruiamo la tavola di verità per F = (A ∨ B) → (C ∨ (C → B))

A B C C→B C ∨ (C → B) A ∨ B F
0 0 0 1 1 1 1
0 0 1 0 0 0 1
0 1 0 1 1 0 1
0 1 1 1 1 0 1
1 0 0 1 1 1 1
1 0 1 0 0 0 1
1 1 0 1 1 0 1
©Nicola Galesi – Draft

1 1 1 1 1 1 1

1.4.2 TAUT, SAT, UNSAT e decidibilità della Logica proposizionale

Una FBF F è detta SODDISFACIBILE esiste almeno una interpretazione v che la rende vera, CONTRADDIZIONE o
INSODDISFACIBILE se nessuna interpretazione la rende vera, ovvero ogni interpretazione la rende falsa. Infine si dice
TAUTOLOGIA se è vera sotto ogni interpretazione. Capire se una formula F è in na delle tre categorie è immediato
dalla sua Tavola di Verità: è sufficiente controllare la colonna corrispondente ai valori di verità di F .
Consideriamo i seguenti insiemi di FBF
Definizione 7 (SAT, UNSAT, TAUT)

SAT = {F ∈ FBF : F soddisfacibile} = {F ∈ FBF : esiste almeno una v interpretazione tale che v(F ) = 1}

UNSAT = {F ∈ FBF : F insoddisfacibile} = {F ∈ FBF : non esiste alcuna interpretazione v tale che v(F ) = 1}

TAUT = {F ∈ FBF : F soddisfacibile} = {F ∈ FBF : per ogni interpretazione v sia ha v(F ) = 1}

A volte abusando del linguaggio, scriveremo che F è SAT per dire che F è soddisfacibile, ovvero che F ∈ SAT.
Ugualmente per TAUT e UNSAT.

Osservazione 1
Se F ∈ TAUT, allora ¬F ∈ UNSAT.
Dimostrazione.
F ∈ TAUT ⇔ per ogni interpretazione v, v(F ) = 1
⇔ per ogni interpretazione v, v(¬F ) = 0
⇔ ¬F ∈ UNSAT

Osserviamo che Se F ∈ SAT su ¬F non possiamo dire nulla di preciso.

Il problema di decidere se una formula F appartiene a SAT o meno è un problema fondamentale dell’informatica
a cui possono ricondotti - o per usare un termine formale efficientemente ridotti gran parte di problemi concreti di
pianificazione, logistica, e di reti. Osserviamo che la Tavole di verità forniscono un algorimto immediato per decidere
se una formula F ∈ SAT

9
 Algorithm 1 Algorithm A
Input: F ∈ FBF
Output: 1 se F ∈ SAT, 0 se F ̸∈ SAT

1. for all interpretazione v

2. if v(F ) = 1 Output: 1
3. end for
4. Output: 0

L’algoritmo presentato è un algoritmo deterministico2 che decide se una formula F è soddisfacibile. Si noti tuttavia
che nel caso peggiore, ovvero se la formula è F è in UNSAT, l’algoritmo deve verificare 2n assegnamenti, dove n è il
©Nicola Galesi – Draft

numero di variabili proposizionali presenti in F . È quindi naturale chiedersi se si può fare meglio e in particolare se è
possibile dare una algoritmo che decide SAT in un numero di passi che è al più polinomiale nel numero di atomi che
definiscono F . Fino ad ora nessuno è stato in grado di dimostrare che il problema di decidere SAT è intrinsecamente
esponenziale, ovvero non può essere risolto da un algoritmo che impieghi meno di un numero esponenziale di passi di
calcolo. Dimostrare che SAT è intrinsecamente esponenziale è uno dei problemi cardini dell’intera informatica. Tale
questione è strettamente connesso ad uno dei problemi fondamentali dell’Informatica e della Matematica, nonché a un
problema filosofico legato alla comprensione del pensiero umano. Il problema, che analizzeremo nell’ultimo capitolo
delle dispense, è il famoso problema P versus NP che richiede di sapere se la classe di complessità P è strettamente
inclusa nella classe di complessità NP (si veda Capitolo 11 per maggior dettagli).
Vediamo adesso un algoritmo analogo per decidere se un formula F ∈ TAUT ( osservarne le differenze)

Algorithm 2 Algorithm B
Input: F ∈ FBF
Output: 1 se F ∈ TAUT, 0 se F ̸∈ TAUT

1. for all interpretazione v

2. if v(F ) = 0 Output: 0
3. end for
4. Output: 1

1.4.3 Equivalenza semantica e leggi logiche

Due FBF sono equivalenti se il loro valore di verità coincide per ogni interpretazione. In linguaggio naturale scriviamo
A ≡ B, ma è chiaro che l’equivalenza è catturata dal connettivo ↔, nel senso che A e B sono equivalenti se A ↔ B
è una tauutologia. Tramite le tavole di verità si verfichino dunque le seguenti importanti leggi logiche
2 Si veda il Capitolo 11 a pagina 11 per la definizione di algoritmo deterministico e algoritmo non-deterministico.

10
 Teorema 1
Siano A, B, C formule proposizionali FBF. Allora valgono le seguente leggi logiche:
1. Associatività di ∧ e ∨: (A ∧ (B ∧ C)) ≡ ((A ∧ B) ∧ C) , (A ∨ (B ∨ C)) ≡ ((A ∨ B) ∨ C),
2. Idempotenza: A ∧ A ≡ A e A ∨ A ≡ A,
3. Commutatività: A ∧ B ≡ B ∧ A e A ∨ B ≡ B ∨ A,
4. Distributività: A ∧ (B ∨ C) ≡ (A ∨ B) ∧ (A ∨ C) e A ∨ (B ∧ C) ≡ (A ∧ B) ∨ (A ∧ C),
5. Assorbimento: A ∧ (A ∨ B) ≡ A e A ∨ (A ∧ B) ≡ A
6. Leggi de De Morgan ¬(A ∧ B) ≡ ¬A ∨ ¬B e ¬(A ∨ B) ≡ ¬A ∧ ¬B
7. Definizione implicazione: A → B ≡ (¬A ∨ B),
8. Doppia negazione: ¬¬A ≡ A,
©Nicola Galesi – Draft

9. Contrapposizione/trasposizione: (A → B) ≡ (¬B → ¬A).

1.5 Conseguenza logica e Teorema di Deduzione

Andiamo adesso a studiare e definire il concetto di conseguenza logica, ovvero in che modo una formula discende
logicamente da un insieme di formule.
Definizione 8 (T EORIA )

Una Teoria proposizionale T è in insieme (anche infinito) di FBF.

Definizione 9
Una assegnamento v soddisfa una teoria T di FBF se v rende vere tutte le formule di T. ovvero se ∀P ∈
T v(P ) = 1. Diremo in questo caso che v soddisfa T. Scriveremo in questo caso v |= T. In particolare se
T = {A} allora scriviamo v |= A.

Definizione 10 (Conseguenza Logica)

Sia T una teoria e P una formula. Diremo che P è conseguenza logica di T e scriveremo T |= A se ogni
assegnamento che soddisfa T soddisfa anche A. Quindi T |= A se per ogni assegnamento v: (v |= T ⇒ v |=
A).

Si noti che nella definizione non si richiede nulla sugli assegnamenti che non soddisfano T. In particolare se T non
ha assegnamenti che la soddisfano allora qualunque formula è conseguenza logica di T. Inoltre scriveremo T ̸|= A se
non è vero T |= A, ovvero se esiste un assegnamento v che soddisfa T ma non soddisfa A.
Osservazione 2 (Differenza tra → e |=)

Si osservi che mentre per il connettivo → in logica classica la formula (A → B) ∨ (B → A) è una tautologia
per qualunque due formule, ovvero è sempre vero che date due formule generiche A e B è sempre vero che
almeno una implica l’altra, ciò non è altrettanto vero per la nozione di conseguenza logica |=, ovvero non è
sempre vero che almeno una tra A |= B e B |= A è sempre vera. Si consideri per esempio A = {p1 } e
B = {p2 } con p1 e p2 variabili proposizionali. Si vede facilmente che A ̸|= B e anche che B ̸|= A.

11
 Proposizione 1 (Proprietà del |=)

Valgono le seguenti proprietà

1. T, A |= A,
2. T, B |= (A ∨ B) T, A |= (A ∨ B),
3. T, (A ∧ B) |= A e T, (A ∧ B) |= B,
4. T |= A e T |= B, allora T |= (A ∧ B),
5. T, A |= C e T, B |= C, allora T, (A ∨ B) |= C
6. T, A |= B, e T, B |= C allora T, A |= C,
7. T, A |= B, allora T |= (A → B),
8. T, A |= B e T, ¬A |= B, allora T |= B.
©Nicola Galesi – Draft

Dimostrazione. A scopo esemplificativo dimostriamo alcune delle precedenti proprietà:

Dimostriamo la (6) ovvero che T, A |= B, e T, B |= C allora T, A |= C. Supponiamo per assurdo che (1) T, A |= B, e (2) T, B |= C
valgano ma che (3) T, A ̸|= C. Da (3) abbiamo che esiste un assegnamento v̄ tale che v̄ |= T, A ma v̄(C) = 0. Poiché v̄ |= T, A allora
da (1) risulta che v̄(B) = 1 e dunque v̄ |= T, B. Quindi da (2) deve essere che v̄(C) = 1. Contraddizione.
Dimostriamo la (7), ovvero che T, A |= B, allora T |= (A → B). Supponiamo per assurdo che (1) T, A |= B ma che (2) T ̸|= (A →
B). Da (2) esiste un assegnamento v̄ tale che v̄ |= T ma v̄(A → B) = 0 e questo (dalla definizione di →) è se e solo se (sse) v̄(A) = 1
e v̄(B) = 0. Dunque v̄ |= T, A e quindi da (1) v̄ |= B, ovvero v̄(B) = 1 . Contraddizione.

Estendiamo il conceto di SAT, TAUT e UNSAT a insiemi di formule o teorie.

Definizione 11

Diremo che T è SAT se esiste una assegnamento v che soddisfa tutte le formule in T, ovvero in simboli v |= T.
Diremo che T è TAUT se ogni assegnamento v rende vere tutte le formule in T. In. questo caso scriviamo
|= T. Infine T è UNSAT se per ogni assegnamento v esiste almeno una formula F in T tale che v(F ) = 0. In
questo caos scriviamo ̸|= T.

Corollario 1 (Proprietà del |=)

Siano P e Q due FBF e T una teoria.

1. P |= Q ⇔ |= (P → Q)

2. T |= P ⇎|= T ∪ {¬P } UNSAT

Dimostrazione. L’implicazione (⇒) della (1) segue dalla Proposizione precedente (punto (7)). Dimostriamo l’implicazione contraria.
|= (P → Q) significa che (1) per ogni assegnamento v deve essere che v(P → Q) = 1. Per dimostrare che P |= Q dobbiamo far
vedere che se v(P ) = 1 allora v(Q) = 1, con v un assegnamento qualsiasi. Sia v un generico assegnamento tale che v(P ) = 1. Dunque
da (1) deve essere che v(Q) = 1.
Dimostriamo la (⇒) della (2). Dobbiamo dimostrare che ogni assegnamento v rende falsa almeno una formula in T ∪ {¬P }. Se v rende
falsa una formula in T allora l’asserto è dimostrato. Se v rende vera ogni formula in T allora, dall’ipotesi, v(¬A) = 1, ovvero v(A) = 0
e l’asserto è dimostrato.
Per l’implicazione contraria (⇐) della (2) osserviamo che per ipotesi ogni v rende falsa almeno una formula in T ∪ {¬P }. Se v rende
sempre falsa almeno una formula in T, allora è cmq vero che T |= P . Se v rende sempre vere tutte le formule di T allora siccome
T ∪ {¬P } è UNSAT deve essere che v(¬A) = 0, ovvero v(A) = 1. Abbiamo quindi dimostrato che ogni assegnamento che rende vera
T rende vera anche P .

12
 Proposizione 2

Sono equivalenti le seguenti proprietà:

1. T è SAT,

2. per ogni formula A si ha che T |= A ⇒ T ̸|= ¬A,

3. esiste una formula A tale che T ̸|= A
Dimostrazione. (1 ⇒ 2). Supponiamo per assurdo che esiste una FBF A tale che T |= A e T |= ¬A. Allora ogni assegnamento v |= T
rende A sia vera che falsa. Quindi se esiste almeno un assegnamento che soddisfa T abbiamo una contraddizione. Ma questo ultimo fatto
è vero perché T è SAT.
(2 ⇒ 3). Supponiamo per assurdo che T |= A per ogni formula A. Quindi T implica logicamente tutte le formule. In particolare ¬A.
©Nicola Galesi – Draft

Dunque T |= ¬A. Ma l’ipotesi ci dice che se T |= A allora T ̸|= ¬A. Contraddizione.

(3 ⇒ 1). Per esercizio.

Teorema 2 (D EDUZIONE S EMANTICA)

Sia n ∈ N. Se {P1 , . . . , Pn } |= Q, allora

1. {P1 , . . . , Pn−1 } |= (Pn → Q) e in particolare |= (P1 → (P2 → (· · · (Pn−1 → (Pn → Q)) · · · ),

2. |= (P1 ∧ · · · ∧ Pn ) → Q
Dimostrazione. La (1) segue da ripetute applicazioni di una proposizione precedente. Per la (2) supponiamo per assurdo che ̸|= (P1 ∧
· · · ∧ Pn ) → Q, ovvero che esiste un assegnamento v̄ tale che v̄ |= (P1 ∧ · · · ∧ Pn ) ma v̄(Q) = 0. Questo contraddice l’ipotesi che
{P1 , . . . , Pn } |= Q (perché?)

1.6 Formalizzazione tramite formule proposizionali

Vogliamo capire come formalizzare proprietà o teoremi mediante formule proposizionali. Ovvero vogliamo costruire
delle formule che sono soddisfacibili sempre e quando le proprotà siano vere e quindi nel caso particolare di teoremi,
siano sempre ver, ovvero delle tautologie.
Ricordiamo che una relazione binaria R su insieme supporto X è un sottoinsieme di X 2 . Come abbiamo visto
precedentemente esiste un modo molto semplice per formalizzare il fatto che gli elementi di un insieme Y ⊆ X veri-
ficano la relazione R. È sufficiente introdurre variabili proposizionali pa,b ∀a, b ∈ X e stabilire che l’intepretazione
di pa,b catturi il fatto che (a, b) ∈ R

v(pa,b ) = 1 ⇔ (a, b) ∈ R
Introduciamo ora le V seguenti notazioni. Sia X = {x1 , x2 , . . .} un insieme e siano
W Px delle FBF definite per ogni
elemento x ∈ X. Con x∈X Px intendiamo la formula (Px1 ∧ Px2 ∧ · · · ) e con x∈X Px intendiamo la formula
(Px1 ∨ Px2 ∨ · · · ). Si noti che le parentesi non sono importanti grazie alle proprietà commutativa e associativa di ∧ e
∨.
Sia data una relazione binari R su X e supponiamo dunque di voler codificare ad esempio la proprietà

∀b ∈ Y : (a, b) ∈ R

Si osservi che tale proprietà asserisce che la coppia (a, b) ∈ R per ogni b ∈ Y , ovvero che, se Y = {b1 , b2 , b3 . . .}
deve essere vera che (pa,b1 ∧ pa,b2 ∧ pa,b3 ∧ · · · ). Quindi tale proprietà viene catturata dalla formula
^
pa,b
b∈Y

13
 Analogamente se volessimo catturare la proprietà

∃b ∈ Y : (a, b) ∈ R

osserviamo che tale proprietà asserisce che per almeno un b ∈ Y la coppia (a, b) ∈ R, ovvero che, se Y =
{b1 , b2 , b3 . . .} deve essere vera che (pa,b1 ∨ pa,b2 ∨ pa,b3 ∨ · · · ). Quindi tale proprietà viene catturata dalla formula
_
pa,b
b∈Y

Infine le proprietà
1. ∀x ∈ X∃y ∈ Y : (x, y) ∈ R e
©Nicola Galesi – Draft

2. ∃x ∈ X∀y ∈ Y : (x, y) ∈ R,
3. ∃x ∈ X∃y ∈ Y : (x, y) ∈ R,
4. ∀x ∈ X∀y ∈ Y : (x, y) ∈ R,
sono catturate rispettivamente dalle formule
V W
1. x∈X y∈Y px,y
W V
2. x∈X y∈Y px,y
W W
3. x∈X y∈Y px,y
V V
4. x∈X y∈Y px,y

1.6.1 3-Colorabilità di un grafo

Sia G = (V, E) un grafo (diretto) dove, si ricorda, che E ⊆ V 2 .
Definizione 12

Sia Ck = {c1 , · · · ck } un insieme di k ≥ 2 colori e sia G = (V, E) un grafo. Una k- COLORAZIONE di un

grafo è una funzione f : V −→ Ck tale che

f (v) ̸= f (w) ∀(v, w) ∈ E

Figura 1.1: Esempi di 3-colorazioni e 4-colorazioni di grafi

14
 Problema 1

Sia dato un grafo G = (V, E). Costruire una formula proposizionale 3 − Col(G) tale che

3 − Col(G) ∈ SAT ⇔ G è 3-colorabile

Dimostrazione. Come prima cosa decidiamo quali variabili proposizionali usare e la loro semantica. La relazione che cattura il nostro
problema in questo caso è la seguente: consideriamo coppie (v, c) ∈ V × C3 . Una coppia è in relazione se f (v) = c. Dunque le variabili
saranno del tipo:
pv,c dove v ∈ V e c ∈ C3
Dunque le variabili pv,c intendono catturare il fatto che f (v) = c. Dobbiamo ora catturare le proprietà della f . Ovvero:
1. f è una funzione. il che significa che per ogni v ∈ V esiste ed unico un c ∈ C3 tale che f (v) = c.
2. f (v) ̸= f (w) lì dove (v, w) ∈ E
©Nicola Galesi – Draft

Per essere più precisi la (1) corrisponde a dire:

1. per ogni v ∈ V esiste almeno un c ∈ C3 tale che f (v) = c, e
2. per ogni c1 ̸= c2 ∈ C3 se f (v) = c1 ⇒ f (v) ̸= c2
Invece la (3) corrisponde a dire che se per ogni (v, w) ∈ E:
1. f (v) = c1 ⇒ f (w) = c2 ∨ f (w) = c3 , e
2. f (v) = c2 ⇒ f (w) = c1 ∨ f (w) = c3 , e
3. f (v) = c3 ⇒ f (w) = c1 ∨ f (w) = c2 , e
A questo punto possiamo scrivere la nostra formula ricordando che f (v) = c è codificato come la variabile porosizionale pv,c . La prima
formula è
def ^ _ ^
A = pv,c ovvero (pv,c1 ∨ pv,c2 ∨ pv,c3 )
v∈V c∈C3 v∈V
La seconda formula può essere scritta come
def ^ ^
B = (pv,c1 → ¬pv,c2 )
v∈V c1 ̸=c2 ∈C3

La terza formula può essere scritta come

def ^
C = [(pv,c1 → (pw,c2 ∨ pw,c3 )) ∧ (pv,c2 → (pw,c1 ∨ pw,c3 )) ∧ (pv,c3 → (pw,c1 ∨ pw,c2 ))]
(v,w)∈E

Infine la formula Col(G) deve verifcare le tre formule contemporanemaente, dunque

def
3 − Col(G) = A ∧ B ∧ C

Esempio 1

1. Scrivere la formula 2 − Col(G) per il grafo G = ({v, w}, (v, w)) è verificare che è soddisfacibile.
2. Scrivere la formula 2 − Col(G) per il grafo G = ({1, 2, 3}, {(1, 2), (2, 3), (1, 3)}) e verificare che è
UNSAT.

1.6.2 Principio dei Cassetti

Vediamo un altro esempio di formalizzazione.
Definizione 13 (Principio Cassetti - versione informale)

Se n + 1 oggetti devono essere sistemati in n cassetti, allora almeno un cassetto conterrà due oggetti.

Andiamo adesso a dare una formulazione più matematica di tale principio in modo da riuscire più facilmente a
formalizzarlo come una formula proposizionale. Per prima cosa usiamo la seguente notazione [n] = {1, 2, 3 . . . , n}.

15
 Possiamo dunque pensare alla sistemazione di n + 1 oggetti in n cassetti come una mapping f : [n + 1] −→ [n]. Si
noti che f non deve essere necessariamente una funzione, ovvero ogni elemento dominio [n + 1] mappato in un ed un
solo elemento del codominio [n]: il principio continua a rimanere vero anche in questo caso. Dunque è sufficiente che
f mappi ogni elemento del dominio in qualche elemento del codominio.
Definizione 14 (Principio dei Cassetti - Pigeonhole Principle - formale)

Sia f : [n + 1] −→ [n], allora ci saranno i, i′ ∈ [n + 1] con i ̸= i′ e ci sarà j ∈ [n] tale che f (i) = j e
f (i′ ) = j.

Per prima cosa riscriviamo Il principio usando i quantificatori e un linguaggio logico:

©Nicola Galesi – Draft

f : [n + 1] −→ [n] ⇒ ∃i, i′ ∈ [n + 1]i ̸= i′ ∃j ∈ [n] : f (i) = j ∧ f (i′ ) = j

Ora identifichiamo la relazione che definisce il principio. La funzione f stessa definisce la relazione: i ∈ [n + 1] è
in relazione con j ∈ [n] se f (i) = j. si tratta di una relazione binaria su [n+1]×[n]. Dunque le variabili proposizionali
che useremo saranno del tipo:

pi,j i ∈ [n + 1], j ∈ [n]

Con la seguente semantica:

pi,j = 1 ⇔ f (i) = j ovvero i è in relazione con j

Nel cercare la formula PHPn+1

n che codifica il principio dei cassetti osserviamo che ha la forma del tipo A ⇒ B
dove A codifica che f è una funzione da [n + 1] a [n] e B codifica il resto, ovvero ∃i, i′ ∈ [n + 1]i ̸= i′ ∃j ∈ [n] :
f (i) = j ∧ f (i′ ) = j.
def
^ _
A = pi,j
i∈[n+1] i∈[n]

Invece la B è:
def
_ _
B = (pi′ ,j ∧ pi′ ,j )
i,i′ ∈[n+1],i̸=i′ j∈[n]

Problema 2
Codificare il Principio dei Cassetti nella versione in cui f è una funzione ( e non un mapping) ed è suriettivaa .
a Aiuto: Perché f sia una funzione non deve verificarsi che un oggetto possa essere messo in più di un cassetto. Perché la funzione sia

suriettiva deve verificarsi che in ogni cassetto venga riposto almeno un oggetto.

1.7 Sostituzioni
Definizione 15

Due FBF P e Q si dicono EQUIVALENTI se v(P ) = v(Q) per ogni interpretazione v.

Corollario 2
Due FBF P e Q si dicono EQUIVALENTI se e solo se P ↔ Q ∈ TAUT-

16
 Definizione 16
Sia F una FBF e sia p1 una variabile proposizionale che occorre (anche 0 volte) in F ( a volte denotato con
F (p1 )). Sia Q una FBF. Si definisce F [Q/p1 ] la formula ottenuta da F sostituendo simultaneamente in F
ogni occorrenza di p1 con la formula Q.

Si osservi che se p1 non occorre in F allora F [Q/p1 ] è semplicemente F .

Vediamo alcuni esempi di sostituzione.
Esempio 2

def
Sia F la formula (p1 ∨ p2 ) → p1 e sia Q = (p3 ∧ p4 ). Allora F [Q/p1 ] = ((p3 ∧ p4 ) → p2 ) → (p3 ∧ p4 ).
©Nicola Galesi – Draft

La sostituzione può essere applicata contemporaneamente a più variabili. Per esempio sia F (p1 , p2 ) la formula
def def def
(p1 → p2 ) e sia Q1 = (p3 ∨ p4 ) e Q2 = (p5 → p6 ). Allora F [Q1 /p1 , Q2 /p2 ] = (p3 ∨ p4 ) → (p5 → p6 ).

Ls sostituzione può anche essere applicata ricorsivamente. Per esempio sia sia F la formula p1 → p2 allora
def
F [F/p1 , F/p2 ] = (p1 → p2 ) → (p1 → p2 )

La sostituzione di formule equivalenti non altera il valore di verità di una formula. Infatti
Proposizione 3

Siano P e Q due FBF e v un’interpretazione tale che v(P ) = v(Q). Sia R una terza FBF. Allora si ha che
v(R[P/p1 ]) = v(R[Q/p1 ]).
Dimostrazione. La dimostrazione è per induzione strutturale su R. Nel caso base R è: ⊥ oppure p1 oppure p2 con
p2 ̸= p1 . Se R = ⊥ oppure R = p2 non c’é nulla da dimostrare visto che R[P/p1 ] = R[Q/p1 ] = R. Se R = p1 , allora
R[P/p1 ] = P e R[Q/p1 ] = Q e il risultato segue dall’ipotesi su P e Q.
Nel caso induttivo consideriamo il caso in cui R = (A ∧ B). Per ipotesi di induzione abbiamo che v(A[P/p1 ]) =
v(A[Q/p1 ]) e v(B[P/p1 ]) = v(B[Q/p1 ]). Per ipotesi di induzione v si comporta su (A ∧ B)[P/p1 ] esattamente come
su (A ∧ B)[Q/p1 ], da cui la tesi. Il resto dei casi è analogo e lasciato per esercizio.

Vediamo come può essere utile la precedente proprietà.

Esempio 3

def def
Sia ⊤ = ¬⊥. Dimostrare che per ogni FBF Q e per ogni atomo p1 la formula Q = P → (p1 → P [⊤/p1 )])
è una tautologia, ovvero è in TAUT.
Dimostrazione. Poiché Q è una implicazione dobbiamo solo fare vedere che per un’interpretazione v per cui si ha che
v(P ) = 1 allora v(p1 → P [⊤/p1 )]) = 1. Sia dunque v un’interpretazione per cui v(P ) = 1. Distinguiamo due casi.
• v(p1 ) = 0. In questo caso v(p1 → P [⊤/p1 )]) = 1 e la tesi è dimostrata.
• v(p1 ) = 1. v(p1 ) = v(⊤). Quindi dalla proposizione precedente v(P [⊤/p1 ]) = v(P [p1 /p1 ]) = v(P ) = 1.
Dunque v(p1 → P [⊤/p1 )]) = 1 e la tesi è dimostrata.

17
 1.8 Completezza funzionale e forme normali
L’insieme di connettivi logici che abbiamo usato fino ad ora per costruire formule FBF è {¬, ∧, ∨, →, ↔, ⊥}. Ta-
le insieme viene detto BASE. Vedremo ora cosa significa che una base permette di costruire qualsiasi formula
proposizionale e sarà quindi detta una base (funzionalmente) completa ed inoltre vari esempi di basi complete.

Premettiamo una notazione. Sia F (p1 , . . . , pn ) una FBF definita a partire dagli atomi p1 , . . . , pn . Siano a1 . . . , an ∈
{0, 1} n valori di verità, che scriviamo anche come ⃗a = (a1 , . . . , an ). Sia v⃗a (F ) il valore di verità (interpretazione)
di F quando agli atomi p1 , . . . , pn viene dato l’assegnamento ai , in altre parole quando v⃗a (pi ) = ai .
Definizione 17 (F UNZIONE DI VERITÀ)
©Nicola Galesi – Draft

Una FBF F (p1 , . . . , pn ) definita a partire dagli atomi p1 , . . . , pn definisce una FUNZIONE B OOLEANA fF :
{0, 1}n −→ {0, 1}: detta FUZIONE DI VERITÀdefinita da:

fF (a1 . . . , an ) = v⃗a (F ).

Anche i connettivi definiscono delle funzioni Booleane. Ad esempio la congiunzione ∧ definisce la funzione
Booleana f∧ definita f(p1 ∧p2 ) e cosi per ogni altro connettivo.
Definizione 18
Un connettivo si dice DERIVABILE DALLA BASE B se possiamo definire la funzione di verità a partire da le
funzioni di verità dei connettivi nella base B.

Esempio 4

Per la legge logica p1 → p2 ≡ ¬p1 ∨p2 , il connettivo dell’implicazione → è derivabile dalla base B = {∨, ¬}.
Per la legge logica di De Morgan ¬(A ∨ B) ≡ ¬A ∧ ¬B e la legge della doppia negazione ¬¬A ⇔ A,
otteniamo che A ∨ B ≡ ¬(¬A ∧ ¬B) e dunque il connettivo ∨ della disgiunzione è derivabile dalla base
B = {∧, ¬}.

Definizione 19 (BASE COMPLETA)

Un insieme di connettivi K si dice FUZIONALMENTE COMPLETO se per ogni funzione di verità (o Booleana)
f : {0, 1}n −→ {0, 1} esiste una formula F costruita da n atomi usando solo i connettivi di K tale che
f = fF .

Nel seguito vedremo come basi come B1 = {∧, ¬}, B2 = {∨, ¬}, B3 {→, ¬} sono basi complete, ovvero consen-
tono di derivare qualsiasi funzione di verità. Prima però introduciamo il concetto di forme normali e poi dimostriamo
il seguente Teorema
Teorema 3 (BASI COMPLETE )

B1 = {∧, ¬} e B2 = {∨, ¬} sono basi funzionalemente complete.

1.8.1 Forme normali

Alcune terminologie. Un LETTERALE è una variabile proposizionale oppure la negazione di un variabile proposizio-
nale.
Una CLAUSOLA è una disgiunzione di letterali. Un TERMINE è una congiunzione di letterali. In genere denoteremo
un letterale con il simbolo ℓ.

18
 Esempio 5

(p1 ∨ ¬p2 ∨ p3 ) è una clausola. (¬p1 ∧ ¬p2 ∧ p3 ) è un termine.

Definizione 20 (F ORME N ORMALI C ONGIUNTIVE E D ISGIUNTIVE)

Una FBF F si dice in F ORMA N ORMALE C ONGIUNTIVA (una CNF) se è una congiunzione di clausole.
Ovvero
def
F = (C1 ∧ C2 ∧ · · · ∧ Cm ) dove le Ci sono clausole e m ≥ 0.
Una FBF F si dice in F ORMA N ORMALE D ISGIUNTIVA (una DNF) se è una disgiunzione di termini. Ovvero
def
©Nicola Galesi – Draft

F = (T1 ∨ T2 ∨ · · · ∨ Tm ) dove Ti sono termini e m ≥ 0.

Ogni formula FBF può essere trasformata in una FBF. Andiamo a discutere l’algoritmo che consente di trasformare
una qualunque formula in una CNF o in una DNF
Teorema 4

Per ogni FBF F definita sulla base B = {∧, ∨, →, ↔ ¬, ⊥} esiste una formula F C in CNF tale che F ≡ F C
e una formula F D in DNF tale che F ≡ F D .
Dimostrazione. La dimostrazione è data da un algoritmo che utlizzando le equivalenze logiche, trasforma passo dopo
passo la formula F originale in una CNF F C (rispettivamente in una DNF F D ). L’algoritmo esegue i seguenti passi di
sostituzione in ordine
1. (eliminazione di ⊥). Rimpiazzare tutti i simboli ⊥ con la formula (p ∧ ¬p) dove p è un atomo,
2. (eliminazione di ↔). Rimpiazzare ogni occorrenza di una formula (A ↔ B) con la formula (A → B) ∧ (B → A),
3. (eliminazione di →). Rimpiazzare ogni occorrenza di una formula (A → B) con la formula (¬A ∨ B),
4. (spostamento di ¬ davanti agli atomi). Ripetere i seguenti tre passi fin quando tutte le negazioni sono davanti ad
atomi:
(a) Rimpiazzare ogni occorrenza di una formula ¬¬A con la formula A.
(b) Rimpiazzare ogni occorrenza di una formula ¬(A ∧ B) con la formula (¬A ∨ ¬B).
(c) Rimpiazzare ogni occorrenza di una formula ¬(A ∨ B) con la formula (¬A ∧ ¬B)
5. Esegui uno dei due passi a secondo se si vuole ottenere una CNF o una DNF
(a) trasforma in congiunzione per CNF. Usare la distributività del ∨ sul ∧ (A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)
per trasformare la formula in una congiunzione di disgiunzioni,
(b) trasforma in congiunzione per DNF. Usare la distributività del ∧ sul ∨ (A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C)
per trasformare la formula in una disgiunzione di congiunzioni

Esempio 6

def
Sia = (p1 ∨ ¬p2 ) → p3 . L’algoritmo esegue le seguenti trasformazioni

(p1 ∨ ¬p2 ) → p3 ≡ ¬(p1 ∨ ¬p2 ) ∨ p3

≡ (¬p1 ∧ ¬¬p2 ) ∨ p3
≡ (¬p1 ∧ p2 ) ∨ p3 DNF
≡ (¬p1 ∨ p3 ) ∧ (p3 ∨ p2 ) CNF

19
 Facciamo alcune osservazioni sulla efficienza computazionale di trasformare una FBF F in una CNF o DNF. A
questo scopo consideriamo (per ora informalmente) la dimensione di una formula come il numero di simboli (del
linguaggio) in essa contenuti. Nonostante la semplicità dell’algoritmo si osservi che il passo finale (quello che usa
al distributività) potrebbe accrescere di molto la dimensione della formula. Se consideriamo l’esempio precedente
osserviamo che l’atomo p3 nella CNF si ripete due volte mentre nella DNF o nella formula originale è presente solo
una volta. Dunque uno dei problema che può portare all’esplosione della dimensione della formula e quindi a una
inefficienza della trasformazione in forme normali può risedere nel dover eliminare tramite distributività molti livelli
def
di indentazione di parentesi. Si consideri il seguente esempio: F = (p1 ∧ p2 ) ∨ ((p4 ∧ p5 ) ∨ (p6 ∧ p7 )). Come si può
verificare facilmente la CNF di questa formula è la formula
def
F C = (p1 ∨p4 ∨p6 )∧(p1 ∨p4 ∨p7 )∧(p1 ∨p5 ∨p6 )∧(p1 ∨p5 ∨p7 )∧(p2 ∨p4 ∨p6 )∧(p2 ∨p4 ∨p7 )∧(p2 ∨p5 ∨p6 )∧(p2 ∨p5 ∨p7 )
©Nicola Galesi – Draft

Si osservi che molti letterali sono ripetuti molte volte in F C la dimensione è passata da 19 (quella di F ) a 56 (quella
di F C ). Tale incremento della dimensione di F può essere addirittura esponenziale nella dimensione di F . Quindi la
maggiore semplicità della forma normale richiede un costo computazionale da pagare (si veda anche l’esempio 11).
Vediamo ora un altro metodo per costruire la CNF o al DNF equivalente alla formula F che rende più evidente
il fatto che la dimensione di F C o F D potrebbe essere esponenziale nella dimensione di F . Supponiamo F sia una
formula definita su n variabili atomiche p1 , . . . , pn . Consideriamo la seguente notazione: Se ⃗a = (a1 , . . . an ) ∈
{0, 1}n è un assegnamento v⃗a alle n variabili p1 , . . . pn , ovvero v(pi ) = ai per ogni i ∈ [n]. Sia T⃗a il termine
 
def
^ ^
T⃗a =  pi ∧ ¬pi 
i∈[n]:ai =1 i∈[n]:ai =0

sia C⃗a la clausola  

def
_ _
C⃗a =  ¬pi ∨ pi 
i∈[n]:ai =1 i∈[n]:ai =0

Algorithm 3 Algoritmo per CNF

Input: F ∈ FBF
Output: F C

FC = ⊤
1. Scrivere la Tavola di Verità di F
2. for all assegnamento ⃗a alle variabili di F
3. if v⃗a (F ) = 0
4. then F C = F C ∧ C⃗a
5. end for
6. Rimuovi il simbolo ⊤ iniziale
7. Output: F C

20
 Algorithm 4 Algoritmo per DNF
Input: F ∈ FBF
Output: F D

FD = ⊥
1. Scrivere la Tavola di Verità di F
2. for all assegnamento ⃗a alle variabili di F
3. if v⃗a (F ) = 1
4. then F D = F D ∨ T⃗a
5. end for
6. Rimuovi il simbolo ⊥ iniziale
©Nicola Galesi – Draft

7. Output: F D

Da questi due algoritmi si evince molto facilmente che se una formula F è definita su n atomi la sua CNF o la sua
DNF equivalenti potrebbero avere 2n clausole o termini proprio nei casi in cui sotto ogni assegnamento la F vale 0
(rispettivamente 1 per DNF).
Esempio 7

Costruiamo la CNF associata alla seguente tavola di verità per F

p1 p2 p3 F
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0

F C = (p1 ∨ p2 ∨ ¬p3 ) ∧ (¬p1 ∨ p2 ∨ p3 ) ∧ (¬p1 ∨ p2 ∨ ¬p3 ) ∧ (p1 ∨ p2 ∨ p3 )

Esercizio 1

Calcolare la Tavola di Verità di F C e verificare che è proprio quella di F . Dedurne una dimostrazione generale
che F la sua CNF F C ottenuta dall’algoritmo sono equivalenti. Ripetere anche per la DNF F D .

1.9 Teorema di Compattezza: Cenni

Il Teorema di compattezza si interessa della soddisfacibilità di insiemi infiniti di formule. Diremo che una
Definizione 21
una teoria T è FINITAMENTE SODDISFACIBILE se ogni suo sottoinsieme finito lo è.

Osserviamo che la nozione di conseguenza logica è monotona, ovvero

21
 Proposizione 4

Se T |= A e T ⊆ T′ allora T′ |= A

Teorema 5
Un insieme T è soddisfacibile se e soltanto se è finitamente soddisfacibile.

Una implicazione del teorema è (⇒) è immediata. L’altra implicazione non la dimostriamo (si veda un qualunque
libro). è importante menzionare i due corollari.
Corollario 3
©Nicola Galesi – Draft

Un insieme di formule T è insodddisfacibile se e solo se esiste un sottoinsieme finito T′ che lo è

Corollario 4

Sia T un insieme di FBF e P una FBF. T |= P se e solo se esiste un sottoinsieme finito T′ di T tale che
T′ |= P

22
 Capitolo 2

Calcolo Proposizionale
©Nicola Galesi – Draft

Immaginiamo di voler dimostrare che se A → B e A → (B → C), allora A → C. un modo di dimostrarla è quella

di costruire la Tavola id verità delle formula ((A → B) ∧ (A → (B → C))) → (A → C) e verificare che si tratta di
una tautologia.
Tuttavia possiamo pensarla anche in questo modo: vogliamo dimostrare che dea A discende C usando come ipotesi
che A → B e A → (B → C). Infatti
1. se assumo A, allora avendo come ipotesi che A → B derivo B.
2. ancora se assumo A, allora avendo come ipotesi A → (B → C), derivo (B → C)
3. avendo derivato B al passo (1) e (B → C) al passo (2) posso quindi ottenere C
Uno dei problemi principali della logica è quello di definire dei sistemi formali di derivazione che consentono di
formalizzare ed esprimere dei ragionamenti tipo quello precedente. Tali sistema devono essere definite a partire da
alcune semplici regole che permettono di dedurre una conclusione a partire da certe premesse mediante una sequenza
di passi elementari di ragionamento, ognuno dei quali deve essere catturato da una delle regole suddette.
Prima di descrivere intuitivamente tali regole ragioniamo su cosa ci aspettiamo da un sistema di calcolo proposi-
zionale. Data la nozione di validità ci aspettiamo che
1. qualunque formula valida, ovvero ogni tautologia, possa essere derivata nel sistema di calcolo. Parleremo di
COMPLETEZZA di un calcolo logico.

2. il sistema possa derivare solo formule valide. Parleremo di CORRETTEZZA del calcolo logico.
Dedicheremo una Sezione a queste due importanti proprietà e vedremo com dimostrarle per certi calcoli logici.
Dedichiamoci ora alle proprietà intuitive che dovrebbe avere un sistema deduttivo

2.1 Proprietà intuitive sistemi deduttivi

Per prima cosa introduciamo la notazione

A1 , . . . An ⊢ B
per indicare, la momento in mod informale, che nel sistema in oggetto siamo in grado di produrre una dimostrazione
di B usando c ome ipotesi le formule A1 , . . . An .
Per alcuni connettivi è facile dedurre delle regole che consentono di definire le proprietà attese dal sistema di
calcolo e che rispecchiano la tavola di verità dei connettivi stessi.
Per esempio per la congiunzione ci attendiamo che le seguenti regole devono essere soddisfatte
1. A ∧ B ⊢ A. regola del (e, ∧) (eliminazione del ∧),

23
 2. A ∧ B ⊢ B. regola del (e, ∧),
3. A, B ⊢ A ∧ B. regola del (i, ∧) (introduzione del ∧).
Per il caso della disgiunzione la situazione è differente. Infatti se da un lato l’introduzione dell ∨ è intuitiva
1. A ⊢ A ∨ B. (i, ∨)

2. B ⊢ A ∨ B. (i, ∨),
il caso dell’eliminazione dell ∨ non è facile da trattare. Infatti non sembra facile capire di che premesse abbiamo
bisogno per eliminare un ∨ da una formula. Tuttavia, introducendo una terza formula C possiamo esprimere in forma
diretta il seguente ragionamento: se da A deriviamo C e da B deriviamo C, allora da A ∨ B posso derivare C. Si
©Nicola Galesi – Draft

oasserv che in C in qualche modo abbaimo elimenato la ∨ tra A e B. Tale ragionamento da luogo alla seguente regola
detta condizionale
se A ⊢ C e B ⊢ C, allora A ∨ B ⊢ C

Consideriamo ora il connettivo dell’implicazione →. Per eliminare una implicazione è sufficiente avere disponibili
le premesse di tale implicazione. Dunque vale la seguente regola:

A, A → B ⊢ B (e, →)

Viceversa quando possiamo concludere che A → B ? La risposte naturale è dire quando da A sappiamo derivare B.
Dunque tale ragionamento porta alla seguente regola condizionale:

se A ⊢ B, allora ⊢ A → B (i, →)
Prima di passare a trattare la regola per il connettivo della negazione ¬, introduciamo una regola che serve per
comporre dimostrazioni e deduzioni, con la seguente idea. Se da un insieme di formule T sappiamo dedurre una
formula A e da A sappiamo dedurre una formula B allora da T possiamo dedurre B. Tale regola è detta REGOLA DEL
TAGLIO e possiamo esprimerla in modo più generale in questo modo

se T ⊢ A e T, A ⊢ B, allora T ⊢ B (taglio)
Veniamo adesso al connettivo della negazione. La prima difficoltà risiede nel capire come introdurre la negazione.
Infatti stando alla analogia tra la derivazione e la validità (o equivalenetmente tra falsità e non derivabilità) usata fino
ad ora dovremmo dire che la negazione può essere introdotta davanti ad una formula se sappiamo che quella formula
non è derivabile. Ion simoboli dovremmo dire che ⊢ ¬A quando ̸⊢ A. Ma noi stiamo costruendo una teoria per ⊢ e
non sappiamo cosa significhi ̸⊢. Per questo motivo si introduce la seguente definizione
Definizione 22
Una teoria formale è INCONSISTENTE quando permette di derivare qualunque formule A (quindi in particolare
sia la formula A che la formula ¬A)

Introduciamo nel sistema una costante ⊥ che denota inconsistenza e quindi ne diamo una regola che ne permette
l’uso nel sistema e che cattura la sua definizione:

⊥⊢A ∀A FBF (e, ⊥)

Quindi, introdotto tale simbolo nella teoria e le regole per manipolarla, possiamo ora dare la regola per l’introdu-
zione della negazione, usando l’idea che A un formula non è derivabile quando crea inconistenza. E dunque la regola
sarà una regola condizionale del tipo

se A ⊢ B, allora ⊢ ¬A (i, ¬)

24
 Ovviamene dobbiamo anche essere in grado di eliminare la ¬ da una formula. Anche in questo ci viene in aiuto
l’inconsistenza
A, ¬A ⊢ ⊥ (e,¬)
Osserviamo però che in logica classica dovrebbe valere una terza regola che dica
A ⊢ B e ¬A ⊢ B, allora ⊢ B
Con qualche semplice ragionamento, che qui si omette) usando le regole introdotte precedentemente si può
osservare che tale regola è equivalente alla regola che implementa in una teoria formale ilragionamento per assurdo

se ¬A ⊢ ⊥ allora ⊢ A (RAA)
La regola (RAA) è importante perché pone la questione filosofica se sia corretto o meno considerare come dimo-
©Nicola Galesi – Draft

strazione di una formula A una dimostrazione che la formula ¬A porta a una contraddizione. Dal punto di vista della
logica matematica i sistemi in cui la regola (RAA) non viene accettata sono dette logiche costruttiviste o intuizioniste.
La logica intuizionista è una branca della logica con parecchie applicazioni e connessioni informatiche, ma non la
tratteremo in questo corso. Le logiche dove (RAA) è accettata vengono dette logiche classiche e sono l’oggetto del
nostro corso.

2.2 Sistemi deduttivi

In questa sezione andremo ad introdurre due sistemi di calcolo proposizionali deduttivi. I sistemi deduttivi sono sistemi
in cui si vuole dedurre una tautologia finale. Più avanti vedremo il caso di un sistema refutazionale, ovvero un sistema
che partendo dalla negazione di una tautologia permette di derivare il ⊥, ovvero una inconsistenza.

2.2.1 Sistemi Assiomatici

Nei Sistemi Assiomatici vi è un’unica regola e una serie di assiomi (o per meglio dire schemi di assiomi) che permettono
di derivare qualunque tautologia. Sia la regola che gli assiomi non sono altro che implementazioni delle regole intuitive
cha abbiamo visto precedentemente. I sistemi assiomatici sono anche noti con il nome di Sistemi di Hilbert o Sistemi
di Frege

Innanzitutto nei sistemi assiomatici l’unica regola di inferenza è il Modus Ponens

A A→B
B
Più precisamente il Modus Ponens è uno schema di regola, infatti può essere applicato ad ogni istanza delle formule
A e B. Si oti che il Modus Ponens altro non è che l’implementazione della regola (e,→).
Per introdurre gli assiomi, assumiamo per un momento di aver a disposizione la seguente regola condizionale (i,→)
nel nostro sistema assiomatico. In seguito faremo vedere come eliminarlo al costo di aggiungere degli altri assiomi.
Tale regola dice che A, A → B ⊢ B, che nei sistemi assiomatici scriviamo come:

se A ⊢ B, allora ⊢ A → B
Proposizione 5

Se in un sistema assiomatico assumiamo la regola (i,→), allora

A ⊢ B se e soltanto se ⊢ A → B

Dimostrazione. L’implicazione (⇒) è immediata dalla regola assunta. Per l’altra implicazione supponiamo di avere che
⊢ A → B. Dalla regola del Modus Ponens abbiamo che A, A → B ⊢ B, e quindoi dalle regola del taglio abbiamo che
A ⊢ B.

25
 Sfruttando la precedente proposizione ogni regola intuitiva della forma A1 , . . . , An ⊢ A può essere equivalen-
temente sostituita da ⊢ A1 → (A2 → (· · · An−1 → (An → B)) · · · ). D’altra parte ogni regola ogni regola
condizionale può essere sostituita anche essa dalla derivabilità di una formula: per esempio la regola "A ⊢ C e
B ⊢ C allora A ∨ B ⊢ C può equivalentemente essere sostituita da A → C, B → C ⊢ A ∨ B ⊢ C e dunque
⊢ ((A → C) → ((B → C) → (A ∨ B → C))).
Dunque applicando il precedente ragionamento alle regole intuitive otteniamo le seguenti regole per gli assiomi
nei Sistemi Assiomatici, che, come per il caso del Modus Ponens, sono schemi di assioma visto che possono
Definizione 23 (S CHEMI DI ASSIOMA PER IL S ISTEMA A SSIOMATICO )

1. (A ∧ B) → B (∧, e)
2. (A ∧ B) → A (∧, e)
©Nicola Galesi – Draft

3. A → (B → (A ∧ B)) (∧, i)
4. A→A∨B (∨, e)
5. B → A∨ (∨, e)
6. (A → C) → ((B → C) → (A ∨ B → C)) (∨, i)
7. ⊥→A (⊥, e)
8. (A → ⊥) → ¬A (¬, i)
9. A → (¬A → ⊥) (¬, e)
10. (¬A → ⊥) → A (RAA)

Tuttavia ricordiamo che alla scopo di potere avere equivalenza tra A ⊢ C e A → C abbiamo assunto la regola
condizionale di introduzione del →, che asserisce che :
A⊢C⇒A→C
Vediamo ora come tale regola condizionale può essere eliminata aggiungendo altri tre schemi di assioma alla
precedente lista.
Teorema 2. Supponiamo che valga A ⊢ C. Se nel sistema assiomatico aggiungiamo gli schemi di assioma
1. A → A
2. A → (B → A)
3. (A → (B → C)) → (A → B) → (A → C)),
allora è derivabile
A → C.
Dimostrazione. Sia π una dimostrazione di A ⊢ B. Costruiamo una dimostrazione π ′ di A → B senza usare la
regola condizionale (→, i). Ragioniamo per induzione sul numero k di regole (→, e) (Modus Ponens) usate in π e
costruiamo π ′ .
Caso Base. k = 0. Quindi A ⊢ C è ottenuto senza Modus Ponens e quindi ci sono due casi:
1. C = A,
2. C è un’assioma
Nel primo caso per derivare A → A usiamo l’assioma (1). Nel secondo caso sappiamo che è derivabile C. Quindi
usiamo l’assioma (2) nella istanza C → (A → C) e dopo un applicazione di Modus Ponens otteniamo A → C
C C → (A → C)
A→C
Nel caso induttivo supponiamo il teorema sia vero per k = n e dimostriamolo per k = n + 1. Supponiamo che in
π l’ultimo modus ponens usato sia della forma
.. ..
. .
A⊢B A⊢B→C
A⊢C

26
 Siano π1 e π2 le due dimostrazione che terminano rispettivamente in A ⊢ B e A ⊢ B → C. Poiché in π ci sono
n + 1 Modus Ponens, allora in π1 e π2 ci sono al più n Modus Ponens. Quindi per ipotesi di induzione Per ipotesi di
induzione abbiamo due dimostrazioni nel Calcolo Assiomatico π1′ e π2′ rispettivamente di A → C e A → (B → C).

·· ′
·· π2
·· ′
·· π1 A → (B → C) (A → B) → C)((A → B) → (A → C))
A→B (A → B) → (A → C)
A→C
©Nicola Galesi – Draft

Quindi il precedente teorema ci garantisce di non dover usare la regola intuitiva (→, i) in un calcolo assiomatico
a patto di introdurre altre tre nuovi schemi di assioma. Di fatto poi l’assioma A → A può essere ottenuto a partire da
una dimostrazione dagli altri due e quindi non è strettamente necessario.
Proposizione 2. A → A è derivabile nel calcolo assiomatico.
Dimostrazione.
1. A → ((A → A) → A) → ((A → (A → A)) → (A → A)) ax
2. A → ((A → A) → A) ax
3. ((A → (A → A)) → (A → A)) MP(1,2)
4. A → (A → A) ax
5. A→A MP(3,4)

Dunque in in conclusione gli assiomi per un calcolo assiomatico sono

Definizione 24 (S CHEMI DI ASSIOMA PER IL S ISTEMA A SSIOMATICO )

1. (A ∧ B) → B (∧, e)
2. (A ∧ B) → A (∧, e)
3. A → (B → (A ∧ B)) (∧, i)
4. A→A∨B (∨, e)
5. B → A∨ (∨, e)
6. (A → C) → ((B → C) → (A ∨ B → C)) (∨, i)
7. ⊥→A (⊥, e)
8. (A → ⊥) → ¬A (¬, i)
9. A → (¬A → ⊥) (¬, e)
10. (¬A → ⊥) → A (RAA)
11. A → (B → A) (→, i)
12. (A → (B → C)) → ((A → B) → (A → C)) (→, e)

Esercizio 2
Dimostrare la formula A ∨ ¬A in un sistema assiomatico

Un ultimo commento sui sistemi assiomatici riguarda l’insiemi di assiomi che possono essere usati. Partendo da
differenti basi funzionalmente complete di connettivi è possibile definire differenti insiemi di schemi di assioma per
un calcolo assiomatico che risulti essere corretto e completo (si veda il capitolo seguente). Per esempio è possibile
definire un sistema assiomatico corretto e completo per la base funzionalmente completa {→, ¬} con solo tre assiomi:

27
 1. (A → B) → ((B → C) → (A → C))
2. (¬A → A) → A
3. A → (¬A → B)

2.2.2 Calcolo dei Sequenti

Come abbiamo visto trovare dimostrazioni in un sistema assiomatico non è né facile né intuitivo. Introduciamo ora
un nuovo calcolo deduttivo, introdotto, da Gentzen, che ha la caratteristiche di avere solo regole di introduzione dei
connettivi e grazie a questa ed altre importanti proprietà garantirà un maniera automatica di trovare dimostrazione di
tautologie. il concetto principale id questo calcolo e il concetto di sequente
©Nicola Galesi – Draft

Definizione 25
Un sequente è una epsressione del tipo Γ ⊢ ∆dove Γ e ∆ sono multiinsiemi a di formule ben formate.
a Un multiinsieme e un insieme in cui diverse occorrenze dello stesso elemento sono differenti. Ad esempio {1, 1, 1} è un multiinsime.

Un sequenete della forma A1 , ldots, An ⊢ B1 , . . . Bm intuitivamente asserisce che da A∧ · · · ∧ An è derivabile

B1 ∨ · · · ∨ Bm e quindi che (A∧ · · · ∧ An ) → (B1 ∨ · · · ∨ Bm ) è valida. Nel calcolo dei sequenti non si fa uso del
simbolo ⊥ e invece per dire che A → ⊥ si usa il sequente in cui ∆ è vuoto, ovvero A ⊢. Analogomente per⊢ A
significa che A è derivabile senza ipotesi e dunque è una tautologia.
Nel C ALCOLO DEI S EQUENTI (LK) una regola logica è della forma SS41 o S1 S3 S2 , dove gli Si sono sequenti, S1
e S2 sono dette premesse della regola e S3 e S4 conclusioni della regola.
Nel calcolo dei sequenti vi è un solo assioma della forma.

A⊢A

dove A è una formula. Le regole di LK si suddividono in 3 categorie:

1. regole strutturali, ovvero regole che consentono la manipolazione delle formule nei sequenti
2. regole logiche, ovvero regole che introducono i connettivi nel nella parte sinistra e destra del sequente.

3. regola del taglio (cut) che implementa la eliminazione della implicazione.

Le regole si distinguono in regole a destra e a sinistra a seconda che la regola operi sul sequente a destra e a
sinistra.
Andiamo a discutere separatamente le tre classi di regole e gli assiomi:
Assiomi

A⊢A

Regole strutturali
Contrazione
Γ, A, A ⊢ ∆ Γ ⊢ ∆, A, A
sx dx
Γ, A ⊢ ∆ Γ ⊢ ∆, A

Permutazione
Γ, A, B ⊢ ∆ Γ ⊢ ∆, A, B
sx dx
Γ, B, A ⊢ ∆ Γ ⊢ ∆, B, A

Indebolimento

28
 Γ⊢∆ Γ⊢∆
sx dx
Γ, A ⊢ ∆ Γ ⊢ ∆, A
Le regole logiche si distinguono a secondo del connettivo da introdurre
Regole logiche
Congiunzione
Γ, A, B ⊢ ∆ Γ ⊢ ∆, A Γ ⊢ ∆, B
sx dx
Γ, A ∧ B ⊢ ∆ Γ ⊢ ∆, A ∧ B

Disgiunzione
Γ, A ⊢ ∆ Γ, B ⊢ ∆ Γ ⊢ ∆, A, B
©Nicola Galesi – Draft

sx dx
Γ, A ∨ B ⊢ ∆ Γ ⊢ ∆, A ∨ B

Implicazione
Γ ⊢ ∆, A Γ, B ⊢ ∆ Γ, A ⊢ ∆, B
sx dx
Γ, A → B ⊢ ∆ Γ ⊢ ∆, A → B

Negazione
Γ ⊢ ∆, A Γ, A ⊢ ∆
dx dx
Γ, ¬A ⊢ ∆ Γ ⊢ ∆, ¬A

Regola del Taglio

Γ ⊢ ∆, A Γ′ , A ⊢ ∆′
cut
Γ, Γ′ ⊢ ∆, ∆′
Vediamo degli esempi di derivazione
Esempio 8

Proviamo che è derivabile ⊢ (A ∧ B) → (B ∧ A).

B⊢B A⊢A
(w,l) (w,l)
A, B ⊢ B A, B ⊢ A
(∧, l) (∧, l)
A∧B ⊢B A∧B ⊢A
(∧, dx)
A∧B ⊢B∧A
(→, dx)
⊢ (A ∧ B) → (B ∧ A)

Esempio 9

Proviamo che è derivabile ¬(A ∨ B) ⊢ ¬A ∧ ¬B.

2.3 Eliminazione del Taglio

Uno dei teoremi fondamentali del calcolo dei sequenti afferma che la regola del taglio non è strettamente necessaria.

29
 Teorema 6 (E LIMINAZIONE DEL TAGLIO - G ENTZEN H AUPTSATZ)

Se un sequente Γ ⊢ ∆ è derivabile in LK, allora è derivabile nel sistema LK− , ovvero in LK senza la regola
del taglio.

Osserviamo che tale teorema insieme con la definizione delle regole logiche implica una importantissima proprietà
per il calcolo dei sequenti LK
Proposizione 6 (P ROPRIETÀ DELLA SOTTOFORMULA)

Una dimostrazione del sequente Γ ⊢ ∆ in LK − , ovvero senza tagli, contiene solo sequenti formati da
sottoformule di formule contenute in Γ e ∆.
©Nicola Galesi – Draft

Tale proprietà è un evidente conseguenza delle regole di LK − in cui i connettivi sono solo introdotti e mai eli-
minati. Tale proprietà conferisce a LK − una natura "costruttiva" che molte importanti ripercussioni sulla natura del
processo inferenziale in LK e sulla ricerca automatica delle dimostrazioni in LK .

2.4 Invertibilità delle regole di LK

Come abbiamo visto valgono le due proprietà in LK
1. Ogni sequente derivabile in LK è derivabile senza tagli,
2. in una derivazione in LK− compaiono solo sottoformule del sequente derivato.
In realtà la seconda proprietà può essere ulteriormente raffinata. Consideriamo per esempio la derivazione di un
sequente della forma ⊢ A → B. Risulta chiaro che se la dimostrazione si conclude con il sequente ⊢ A ∧ C → A ∨ D,
allora necessariamente l’ultima regola applicata è quella che introduce il connettivo → a destra. e pertanto l’ultimo
passo della dimostrazione è stato un passo della forma:

A∧C ⊢A∨D
⊢A∧C →A∨D
Analizziamo il sequente A ∧ C ⊢ A ∨ D. L’ultima regola applicata è necessriamente una introduzione del ∧ a sinistra,
oppure una introduzione del ∨ a destra. Decidiamo di trattare prima le regole a sinistra: dunque il nostro sequente
deve necessariamente discendere dal sequente A, C ⊢ A ∨ D, ovvero dal passo di derivazione

A, C ⊢ A ∨ D
A∧C ⊢A∨D
A questo punto nel sequente a sinistra non abbiamo più connettivi e possiamo passare all’analisi delle formule alla
destra del sequente. Si vede immediatamente che essendo il connettivo principale delle formula a destra del sequente
un ∨, l’unica regola possible ad essere stata applicata per ottenere quel una sequente è l’introduzione dell ∨ a destra.
Tale regola ci dice che il precedente passo di derivazione è
A, C ⊢ A, D
A, C ⊢ A ∨ D
A questo punto le formule nel sequente sia a sinistra che a destra non hanno più connettivi e sono variabili propo-
sizionali. Le uniche regole applicabili per ottenere l’ultimo sequente sono dunque quelle strutturali. La contrazione
non può essere visto che solo introdurebbe lo stesso atomo e dunque l’unica regola possibile è quella del weakening.
Infatti

A ⊢ A, D
A, C ⊢ A, D

30
 e
A⊢A
A ⊢ A, D
Che ci conduce ad un assioma e dunque non abbiamo più nulla da fare.

2.5 Un algoritmo per la ricerca di dimostrazioni in LK

Questo esempio mostra in modo intuitivo un algoritmo che dato un sequente Γ ⊢ ∆ derivabile procede alla costruzione
una di derivazione senza tagli in LK di Γ ⊢ ∆ procedendo all’indietro applicando la regola del connettivo principale
della formula che vogliamo trattare. Di fatto questo algoritmo produce una derivazione di Γ ⊢ ∆ in LK− .
©Nicola Galesi – Draft

Vediamo l’algoritmo con qualche dettaglio in più.

Definizione 26 (connettivo principale di una formula)

Definiamo il connettivo principale di una FBF F per induzione strutturale

1. se F è atomica non ci sono connettivi

2. se F non è atomica, allora F è della forma ¬F1 , oppure F1 ∧ F2 o F1 ∨ F2 , F1 → F2 . In questo caso il

connettivo principale di F è rispettivamente ¬, ∧, ∨, →.

Diamo di seguito lo pseudocodice di un algoritmo che ricerca dimostrazioni di un sequente o dice che non esistono,
e in cui usiamo l’euristica di decostruire prima le formule a sinistra del sequente e poi quelle a destra. Inoltre useremo
la seguente proprietà per terminare la dimostrazione:
Chiamiamo un sequente Γ ⊢ ∆ che contiene solo atomi proposizonali un sequente atomico.
Proposizione 7

Se Γ ⊢ ∆ è atomico, allora Γ ⊢ ∆ è derivabile se e solo se esiste un atomo P che appare sia in ∆ che in
Γ. In questo caso la derivazione di Γ ⊢ ∆ si ottiene dall’assioma P ⊢ P dopo aver applicato i necessari
indebolimenti a destra e sinistra. Chiameremo un sequente Γ ⊢ ∆ che contiene un letterale P sia in Γ che in
∆ un Assioma Debole.

31
 Algorithm 5 Ricerca di dimostrazioni in LK−
Input: Γ ⊢ ∆
Output: derivazione di Γ ⊢ ∆ oppure "non derivabile"

1. X = {Γ ⊢ ∆}.
2. while ci sono sequenti Γ′ ⊢ ∆′ non atomici in X
3. while ci sono formule non atomiche in ∆′
4. while ci sono formule non atomiche in Γ′
5. - Sia A la formula più a destra in Γ′ e ◦ il suo connettivo principale
def
6. ovvero Γ′ ⊢ ∆′ = Γ′′ , A ⊢ ∆′
8. - inverti la regola a sinistra del connettivo ◦ di A
©Nicola Galesi – Draft

9. - rimuovi il sequente Γ′ ⊢ ∆′ da X
10. - Aggiungi ad X i sequenti premesse della regola (◦, s) per ottenere A
11. end while
12 - Sia B la formula più a destra in ∆′ e ◦ il suo connettivo principale
def
13. ovvero Γ′ ⊢ ∆′ = Γ′ ⊢ ∆′′ , B
14. - inverti la regola a destra del connettivo ◦ di A
15. - rimuovi il sequente Γ′ ⊢ ∆′ da X
16. - Aggiungi ad X i sequenti premesse della regola (◦, d) per ottenere B
17. end while
18. if in X tutti gli assiomi sono deboli
19. then Γ ⊢ ∆ è derivabile e la derivazione si ottiene dalla derivabiltà degli assiomi deboli
e dalla inversioni effetuate delle varie regole.
18. else Γ ⊢ ∆ non è derivabile.

2.6 Correttezza e Completezza

Fino ad ora abbiamo introdotto dei calcoli sintattici per la logica proposizionale. Nell’introdurre le regole intuitive
abbiamo chiarito almeno informalmente che il legame che vogliamo mantenere con la semantica è che tutto ciò che è
derivabile è valido. In particolare vorremmo mantenere solido il legame tra

D ERIVABILITÀ VALIDITÀ

⊢A |= A
In questa sezione andiamo a chiarire con precisione il legame tra sintassi dei calcoli logici e semantica della logica
proposizionale. In particolare andiamo a chiarire con precisione le seguenti relazioni
C ALCOLO S EMANTICA
D ERIVABILITÀ(Γ ⊢ A) CONSEGUENZA SEMANTICA (Γ |= A)

T EOREMA(⊢ A) TAUT(|= A)

C ONSISTENZA(Γ ̸⊢ ⊥) SAT(Γ ̸|= A)

I NCONSISTENZA(Γ ⊢ ⊥) UNSAT (Γ |= ⊥)

Ricordiamo alcune definizioni che abbiamo già visto

32
 Definizione 27

Siano Γ e ∆ due insiemi di FBF . Scriveremo che Γ |= ∆ e diremo ∆ SAT in Γ se per ogni assegnamento v
risulta ^ _
v( A) = 1 ⇒ v( B) = 1,
A∈Γ B∈∆

ovvero: per ogni assegnamento v se v soddisfa tutte le formule in Γ, allora v soddisfa almeno una formula in
∆.

La prima importante proprietà dei calcoli logici asserisce che tutto ciò che è derivabile è valido. Questa proprieta
è nota come correttezza di un calcolo logico.
©Nicola Galesi – Draft

Teorema 7 (C ORRETTEZZA)

Se Γ ⊢ ∆ è derivabile in LK, allora Γ |= ∆.

Dimostrazione. Per prima cosa dimostriamo

1. gli assiomi in LK sono validi

2. tutte le regole di inferenza preservano la validità: ovvero che se Γ ⊢ ∆ è il sequente conclusione di una regola
con premesse i sequenti Γ′ ⊢ ∆′ e Γ′′ ⊢ ∆′′ , allora se Γ′ |= ∆′ e Γ′′ |= ∆′′ allora anche Γ |= ∆.
Il caso dell assioma A ⊢ A è immediato, visto che A |= A.
Per le regole si ragiona per tutte in modo molto simile e presentiamo il caso della introduzione del ∨ a sinistra. La
regola è
Γ, A ⊢ ∆ Γ, B ⊢ ∆
Γ, A ∨ B ⊢ ∆
Assumiamo di sapere che
1. Γ, A |= ∆ e
2. Γ, B |= ∆.
Dobbiamo dimostrare che Γ, A ∨ B |= ∆. Ragioniamo per assurdo e supponiamo che, sotto le due ipotesi (1) e (2),
esiste un assegnamento v̄ tale che v̄ soddisfa tutte le formule in Γ, A ∨ B e falsifica tutte le formule in ∆. Dunque
v̄(A ∨ B) = 1. Quindi per almeno una tra A e B, senza perdita di generalità diciamo A, deve essere che v̄(A) = 1.
Dunque v̄ soddisfa tutte le formule in Γ, soddisfa A e quindi soddisfa tutte le formule in Γ, A. Per ipotesi (1) v̄ deve
quindi soddisfare almeno una formula in ∆. Ma questo contraddice il fatto che per ipotesi di assurdo, v̄ falsifica tutte
le formule in ∆. Dunque deve essere che Γ, A ∨ B |= ∆.

L’asserzione può essere dimostrata per le altre regole seguendo un ragionamento analogo. Concludiamo adesso
la dimostrazione: sia π una dimostrazione in LK di Γ ⊢ ∆. La dimostrazione che Γ |= ∆ procede per induzione
strutturale su π dimostrando che per tutti i sequenti Γ ⊢ ∆ in π, in particolare per l’ultimo, vale che Γ |= ∆.
1. Nel caso base π è un assioma del tipo A ⊢ A e quindi A |= A segue per quanto detto prima.

2. Al passo induttivo sia Γ ⊢ ∆ ottenuta da una regola con premesse Γ′ ⊢ ∆′ e Γ′′ ⊢ ∆′′ . Per ipotesi di induzione
sappiamo che Γ′ |= ∆′ e Γ′′ |= ∆′′ e quindi per il claim precedente deve valere Γ |= ∆.

33
 Ovviamente da un calcolo logico che permetta di catturare il concetto semantico di validità ci aspettiamo una
proprietà più forte di sapere che tutto ciò che è derivabile è valido: vorremo sapere anche che tutto ciò che è valido
ammette una dimostrazione nel calcolo logico. Tale proprietà prende il nome di COMPLETEZZA in quanto un calcolo
logico permette di derivare tutte le formule in TAUT completamente.
Teorema 8 (C OMPLETEZZA - CASO FINITO)

Sia Γ un insieme finito di formule. Se Γ |= ∆ allora Γ ⊢ ∆ è derivabile in LK

Dimostrazione. (Cenni) Sia Γ ⊢ ∆ un sequente valido. Usiamo l’algoritmo 4.4 a pagina 61 per ricostruire all’indietro
una derivazione in LK− di Γ ⊢ ∆. Ad ogni passo il numero di connettivi in Γ ⊢ ∆ diminuisce di 1 perché ogni regola
©Nicola Galesi – Draft

percorsa all’indietro elimina il connettivo principale di una formula di Γ ⊢ ∆. Dunque, il processo termina (in quanto Γ
e ∆ sono finiti e dunque ci sarà un momento in i sequenti correnti (ovvero l’insieme X nella algoritmo 4.4 ) contengono
solo formule atomiche. Siccome Γ ⊢ ∆ è valido e la validità e preservata anche quando le regole sono invertite
(Dimostrarlo per esercizio), allora i sequenti finali sono Assiomi Deboli che possono essere derivati per indebolimento
(si veda la Proposizione 7 a pagina 30). Dunque l’algoritmo 4.4 permette di ricostruire una dimostrazione per ogni
sequente valido e dunque e completo.
Nel caso di insiemi infiniti la completezza usa il Teorema di Compattezza.
Teorema 9 (C OMPLETEZZA)

Se Γ |= ∆ allora Γ ⊢ ∆ è derivabile in LK

Dimostrazione. (Cenni) Se Γ e infinito e Γ ⊢ ∆ allora, per il Teorema di Compattezza, esiste un insieme finito Γ′ ⊆ Γ
tale che Γ′ |= ∆. Dunque per il teorema di completezza finito si ha che Γ′ ⊢ ∆ è derivabile in LK e quindi anche
Γ |= ∆.

34
 Capitolo 3

Logica del I° ordine

©Nicola Galesi – Draft

3.1 Limiti espressivi della Logica Proposizionale

Come abbiamo visto in alcuni esempi di formalizzazione in logica proposizionale, tale logica consente di gestire
ragionamenti che coinvolgono generalità solo nel caso in cui tale generalità viene espressa su un dominio finito (si
veda per esempio la formalizzazione del principio del Pigeonhole. Dunque non vi è modo di formalizzare proprietà su
domini infiniti in logica proposizionale a meno di non usare formule non finite che quindi non possiamo trattare con
gli strumenti delle logica proposizionale classica.
Esempio 10

Per scrivere una formula che esprima che: "ogni intero inferiore a 5 è inferiore a 10", possiamo usare delle
variabili proposizionali del tipo pi,j e che esprimono che i < j. Quindi per esprime la precedente asserzione
dovremmo scrivere una formula del tipo

· · · (p−2,5 → p−2,10 ) ∧ (p−1,5 → p−1,10 ) ∧ (p0,5 → p0,10 ) ∧ (p1,5 → p1,10 ) · · · .

Avremmo quindi bisogno di una formula infinitamente lunga per poter formalizzare l’asserzione usando le
variabili pi,j

Un’altra ragione della limitatezza espressiva della logica proposizionale è che la tale logica si limita a considerare
le proposizioni come funzioni ( connettivi) degli atomi proposizionali senza permettere ulteriori scomposizioni di tali
atomi. Questo porta a problemi di aggiornamento dell formule nel caso di implementazione di modelli che cambiano
nel tempo. Vediamo un esempio.
Supponiamo di avere un base di dati1 costituita da un insieme di individui I e da alcune tabelle che formalizzano
relazioni tra tali individui: per esempio

• A ⊆ I × I tale che (i, j) ∈ A se e solo se "i è amico di j".

• F ⊆ I × I tale che (i, j) ∈ F se e solo se "i è figlio di j".
• S ⊆ I × I tale che (i, j) ∈ S se e solo se "i è sorella/fratello di j"

Se formalizziamo tali relazioni tramite atomi proposizionali e costruiamo delle formule per determinate interro-
gazioni alla base di dati (DB), allora ogni volta che il dominio I della basa di dati viene aggiornato (cosa che capita
1 Molto brevemente e informalmente una base di dati, nella sua formalizzazione più semplice, è un oggetto formato da un dominio e da un insieme

di relazioni sugli oggetti del dominio espresse mediante tabelle. Una base di dati può essere interrogata mediante delle query (interrogazioni), che
sono formule logiche e che consentono di estrapolare informazioni dalla base di dati. Per esempio si pensi a una base di dati degli utenti di un
banca in cui vengono salvate informazioni personali come indirizzo di residenza, date di nascita ecc. Una interrogazione a questa base di dati è, per
esempio, quella che richiede tutti gli utenti residenti di una città, o tutti quelli nati in certo di range di anni, ecc.

35
 sovente visto che un DB è un oggetto dinamico) dovremo anche modificare le formule che formalizzano le query.
Questa è un operazione altamente inefficiente. Vedremo infatti che tramite logica del I° ordine una query può essere
codificata da una formula indipendente dal dominio del DB.
Vediamo come si risolvono tali problemi nella logica dei predicati.
In un linguaggio del I° ordine L consideriamo simboli di predicato che permettono di codificare le relazioni che
intendiamo codificare: per esempio nell’esempio del DB possiamo considerare di avere tre simboli di predicato che
chiamo (per semplicità) con lo stesso nome della relazione che formalizzano: A,F ,S. Ovviamente ai simboli di
predicato del linguaggio L è associata una arità k che individua se il simbolo formalizza una relazione inclusa in I k .
Supponiamo di avere degli individui specifici del dominio I: per esempio Marco, Laura, Gianni. Ognuno di questi
può essere formlizzato in L mediante un simbolo di costante, per esempio nel nostro esempio scriviamo m per Marco,
l per Laura g per Gianni. Usiamo predicati e costanti per esprimere delle proposizioni semplici. Per esempio per dire
©Nicola Galesi – Draft

1. Marco è amico di Laura,

2. Gianni è fratello di Marco,
3. Laura non è figlia di Gianni
possiamo formalizzare rispettivamente con le formule
1. A(m, l),
2. S(g, m),
3. ¬F (l, g)
Notiamo che tali formule possono essere interpretate nel DB e risultare vere o false a seconda che le relazioni
espresse si verifichino o meno.
Quindi
(Idea semantica)

Le formule sono vere se i valori associati alle costanti che le definiscono sono nel dominio I nella relazione
corrispondente al simbolo di predicato che le definisce

Inoltre tramite i connettivi è possibile esprimere anche proposizioni più complesse per esempio
1. Se Marco è figlio di Laura allora Gianni non è amico di Marco,
2. Se Marco e Laura sono figli di Gianni, allora sono fratelli.
formalizzate dalle formule
1. F (m, l) → ¬A(g, m),
2. F (m, g) ∧ F (l, g) → S(m, l)
Esplorando altre limitatezze della logica proposizionale, consideriamo che nell’esempio DB siamo interessati al-
l’insieme degli amici di Marco. Siamo quindo interessati all’insieme {i ∈ I : A(i, m)}. In un linguaggio del primo
ordine posso catturare oggetti del genere attraverso il concetto di variabile. Ovvero nel linguaggio introduco delle
variabili che di fatto codificano delle variabili sugli elementi del dominio I e che consentono di catturare attraverso il
nome A(x, m) proprio l’insieme degli amici di Marco nel dominio D, visto che x rappresenta un qualsiasi elemento
in I. Anticipiamo ma lo vedremo in dettglio più avanti che tale variabile x viene detta libera nella formula A(x, m) .
(Idea semantica)

L’insieme degli amici di Marco coincide con l’insieme di valori i ∈ I che rendono vera la formula A(x, m),
quando a x si sostituisce la costante ci del linguaggio associata all’elemento i del dominio.

Ricapitolando fino ad ora abbiamo visto che in un linguaggio del I° ordine includeremo

36
 1. simboli di costante,
2. simboli di predicato,
3. variabili
Si intuisce che al momento una formula nella logica dei predicati è un predicato applicato a costanti o variabili oppure
la composizioni di più formule mediante connettivi. Vedremo che il linguaggio è ancora più generale, ma per ora
andiamo a discutere come nella logica dei predicati è possibilie catturare asserzioni universali o esistenziali in maniera
semplice, finita ed efficiente. Per introdurli vediamo un esempio. Consideriamo di voler trovare l’insieme degli
amici degli amici di Marco, ovvero l’insieme {i ∈ I : i è amico di un amico di Marco}. Per avvicinarci alla sua
formalizzazione logica consideriamo come esprimere tale insieme in un linguaggio formale matematico:
©Nicola Galesi – Draft

{i ∈ I : ∃j ∈ I t.c. A(i, j) e A(j, m)}

In un linguaggio del I° ordine possiamo usare i simboli di quantificazione ∀e ∃ come faremmo nel linguaggio
formale matematico e scrivere quindi una formula che cattura il precedente insieme come

∃y(A(x, y) ∧ A(y, m).

Si noti ancora che in questa formula la variabile è di nuovo una variabile libera mentre la variabile y vien detta
vincolata in quanto vincolata al quantificatore esistenziale ∃y che agisce sulla variabile y e che quindi ne controlla la
variabilità sul dominio secondo la quantificazione esistenziale che ricordiamo corrisponde a una disgiunzione.
(Idea semantica)

L’insieme degli amici degli amici i Marco coincide con l’insieme di valori i ∈ I che rendono vera la formula
∃y(A(x, y) ∧ A(y, m) quando a x si sostituisce la costante ci del linguaggio associata all’elemento i del
dominio.

Continuando con l’esempio del DB, potremmo essere interessati a sottomettere delle query che richiedono una
risposta binaria SI/NO. Per esempio a query del tipo "Marco ha figli ?". Tali query possono essere formalizzate
usando un quantificatore esistenziale mediante la formula

∃xF (x, m)

(Idea semantica)

La formula ∃xF (x, m) è vera se e solo se esiste un i ∈ I che è figlio di Marco.

Esercizio 3
Scrivere una formula del I° ordine che catturi la query binaria "Marco ha nipoti ?"

Consideriamo ora un altro esempio. Supponiamo di voler catturare l’asserzione "x + 1 > x" sul dominio D = N
dei numeri interi. La relazione < può essere catturata da un simbolo predicato binario M (x, y). Ma come possiamo
codificare la funzione +.? A questo fine, come fatto per i predicati e le costanti vengono introdotti nel linguaggio
dei simboli di funzione f, g, . . . , atti a catturare sintatticamente le funzioni eventualmente coinvolte in asserzioni sul
dominio. Ricordiamo che una funzione è una mappa da Dk a D tal che ogni elemento del dominio è mappato in un
solo elemento del codominio. Dunque ai simboli di funzione f del linguaggio, come nel caso dei simboli di predicati,
viene associata una arità k tale che il simbolo f interpreta la funzione f : Dk −→ D. Per esempio la somma + è
una fuzione da N2 → N e dunque se nel linguaggio introduciamo un simbolo f per formalizzarla avrà arità 2. Come
nel linguaggio matemtico dove abbiamo espressioni del tipo x + y, x + 4, (x + 4) + y, i simboli di funzioni possono
essere applicati nel linguaggio a costanti, variabili o a ulteriori termini.

37
 Nell esempio precedente, posto che usiamo il simbolo f (x, y) per catturare la somma e il simbolo di costante 1
per catturare il naturale 1, la formula che cattura l’asserzione è:

M (f (x, 1), x)

il precedente esempio quindi ci fa intuire che in un linguaggio del I° ordine che possa catturare strutture matemati-
che di differenti tipi (quali gruppi, anelli, ordini ecc.) c’è bisogno di catturare il concetto di funzione e quindi avremo
bisogno di simboli di fuzione.
Vediamo un ultimo esempio: supponiamo di voler formalizzare in una logica del I° ordine le seguenti asserzioni:
1. Ogni multiplo di 100 e multiplo di 10,
©Nicola Galesi – Draft

2. 25 non è multiplo di 10,

3. Dunque 25 non è multiplo di 100
Se ci dotiamo del simbolo di predicato M (x, y) per dire che x è un multiplo di y e costanti 25, 20, 100. Allora le
tre formule sono ∀x(M (x, 100) → M (x, 10)), ¬M (25, 10), ¬M (25, 100). Osserviamo però che matematicamente
esiste un modo preciso di dire che x è multiplo di y: ovvero che esiste un k ∈ N tale che x = k · y. Quindi potremmo
modificare la nostra formalizzaione in questo modo più preciso: introdurre nel linguaggio un simbolo di funzione
p(x, y) che cattura il prodotto di x per y, introdurre un simbolo di predicato E(x, y) cha catturi che x = y. Dunque
l’asserzione "x è multiplo di y" può essere formalizzata dalla formula

∃z(E(x, p(z, y)))

per cui le tre formule diventerebbero in questo nuovo linguaggio

1. ∀x(∃z(E(x, p(z, 100))) → ∃z(E(x, p(z, 10)))),

2. ¬∃z(E(25, p(z, 10)))

3. ¬∃z(E(25, p(z, 100)))

Esercizio 4
Formalizzare in un linguaggio del I° ordine per la teoria degli insiemi (ovvero per formalizzare asserzioni su
insimei) che contiene un simbolo di predicato binario A(x, y) per dire che x ∈ y le seguenti asserzioni

1. esiste l’insieme vuoto,

2. ogni insieme x è sottoinsieme di qualche insieme y,
3. per ogni insieme x esiste l’insieme complemento di x,

4. esiste un insieme che è sottoinsieme di tutti gli insiemi.

3.2 Linguaggio del I° ordine

Definiamo per prima cosa la sintassi per la logica del I° ordine

38
 Definizione 28
Un linguaggio L per la logica del I° ordine è definito da un alfabeto composto da
1. un insieme di simboli di costante a, b, c, . . .,

2. un insime VAR di simboli di variabili x, y, z, . . .,

3. un insieme di simboli di funzione f, g, h . . .,
4. un insieme di simboli di predicato A, B, C . . ..

5. Connettivi:∧, ∨¬, →, ⊥
©Nicola Galesi – Draft

6. Quantificatori: ∀, ∃
7. Simboli ausiliari : (, )

Andiamo a definire l’insieme dei termini del linguaggio TERL . Si noti che differenti alfabeti definiscono differenti
linguaggi. Quindi supporremo definito il nostro linguaggio e ometteremo di specificarlo ogni volta
Definizione 29
TER è il minimo insieme definito induttivamente come segue:
1. Ogni costante appartiene ad X,

2. Ogni variabile appartiene ad X,

3. se t1 , . . . tn sono n termini e f è un simbolo di funzione di arità n, allora f (t1 , . . . , tn ) appartiene ad X.

Si osservi che le costanti possono essere considerate come funzioni di arità 0. Definiamo ora le formule ben
formate FBFL per la logica del I° ordine nel linguaggio L.
Definizione 30
FBF è il minimo insieme X definito induttivamente come segue:
1. ⊥ ∈ X,
2. se t1 , . . . tn ∈ TER e A è un simbolo di predicato di arità n, allora A(t1 , . . . , tn ) ∈ X

3. se F, G ∈ X, e x ∈ VAR allora
(a) ¬F ∈ X,
(b) F ∧ G, F ∨ G, F → G ∈ X,
(c) Se (∀xF ), (∃xF ) ∈ X.

Se una formula è ottenuta dai casi (1) o (2) è detta Formula Atomica.

39
 Esempio 11

Trasformiamo in FBF le seguenti asserzioni:

1. Ogni numero naturale è un numero intero,
2. esiste un numero che non è naturale

3. Per ogni numero x esiste un numero y tale che x < y.

Denotiamo con A il predicato "essere un numero naturale". con B il predicato "essere un numero intero" e
con M la relazione "essere minore di ". Quindi
©Nicola Galesi – Draft

1. ∀x(A(x) → B(x)),

2. ∃x¬A(x),
3. ∀x∃yM (x, y)

Come nel caso proposizionale andiamo a definire il concetto di sottoformula

Definizione 31

Sia F una FBF. l’insieme Su(F ) dell sottormule di F è definito induttivamente come segue
1. se F è una formula atomica, allora Su(f ) = {F }

2. se F è ¬F1 allora Su(F ) = {F } ∪ Su(F1 ). Se F è (F1 ◦ F2 ) per qualche connettivo ◦ allora Su(F ) =
{F } ∪ Su(F1 ) ∪ Su(F2 )
3. Se F è ∀xF1 o ∃xF1 , allora Su(F ) = {F } ∪ Su(F1 )

Esercizio 5

Trovare Su(F ) per F ∃xA(f (x), y) ∧ ¬∀yB(f (y), y)

Consideriamo la formula ∀xQ. Intuitivamente afferma che Q è vera per ogni elemento del dominio. quindi ci
aspettiamo che la formula Q sia vera ogni qualvolta che ad x sostituiamo un termine t. I quantificatori stabiliscono dei
legami tra la variabili quantificata e le sue occorrenze all’interno dell formula che dipendono dalla formula.
Per esempio nella formula
∀x(x + 1 = 3) ∧ x = 6
risulta chiaro che l’occorrenza della x nel termine x + 1 = 3 è nel campo di azione del quantificatore ∀x mentre
l’occorrenza della x nel termine x = 6 non lo è. Una variabile che appare nel campo d’azine di un quantificatore
si dirà variabile legata. Invece variabili non legate si dicono variabili libere. Andiamo a definire con precisione gli
insiemi delle variabili libere e legate

40
 Definizione 32

Sia t ∈ TER, allora l’insieme F V (t) delle variabili libere di t è definito induttivamente come segue:

1. se x ∈ VAR, allora F V (x) = {x},

2. se c è una costante, allora F V (c) = ∅
3. F V (t1 , . . . , fn ) = F V (t1 ) ∪ . . . ∪ F V (tn )

Sia F una FBF. Allora F V (F ) è definito induttivamente come segue

1. F V (⊥) = ∅
©Nicola Galesi – Draft

2. F V (A(t1 , . . . , tn ) = F V (t1 ) ∪ . . . ∪ F V (tn )

3. F V (¬F1 ) = F V (F1 ) e F V (F1 ◦ F2 ) = F V (F1 ) cupF V (F2 )

4. F V (∀xF1 ) = F V (F1 ) \ {x}, F V (∃xF1 ) = F V (F1 ) \ {x}.

3.2.1 Sostituzioni
Osserviamo che i nomi delle variabili quantificate assumono il ruolo di parametri formali cone nella definizione dei
parametri nell funzioni nei linguaggi di programmazione. Per esempio scrivere ∀xA(x) e ∀yA(y) è del tutto equi-
valente. Quindi, esattamente come nella definizione di una funzione in un linguaggio di programmazione, possiamo
cambiare il nome della variabile a patto di cambiare tutti i riferimenti a quella variabile nel campo d’azione del quan-
tificatore in modo consistente. Per esempio è chiaro che la formula ∀x(x ≤ 5 ∧ x ≥ 6) non è equivalente alla formula
∀y(y ≤ 5 ∧ x ≥ 6). Nella seconda formula la seconda occorrenza della variabile x nel campo d’azione del quan-
tificatore è diventata una variabile libera, mente nella prima formula era una variabile vincolata. Andiamo quindi a
dare la definizione di sotituzione di una variabile in una formula. Osserviamo che le variabili del linguaggio saranno
interpretate come variabili sul dominio dell’interpretazione e dunque ha senso che in una formula vengano sostituite
per dei termini che sono interpretati o come variabili sul dominio o come elementi del dominio.

Definizione 33 (SOSTITUZIONE IN TERMINI )

Siano s, t due termini in TER. allora s[t/x] è il termine ottenuto rimpiazzando in s tutte le occorrenze di x
con il termine t. Ovvero:
1. se s = y, allora s[t/x] = y,
2. se s = x, allora s[t/x] = t

3. se s = c, allora s[t/x] = c
4. se s = f (t1 , . . . , tn ), allora s[t/x] = f (t1 [t/x], . . . , tn [t/x])

Guardiamo ora alla caso della sostituzione di un variabile in una formula. Dobbiamo fare attenzione al caso in cui
la variabile che vogliamo sostituire, dopo la sostituzione, non cambi ruolo e per esempio da libera diventi vincolata.
def
Per esempio nella formula = = ∃x(x < y) se effettuiamo la sostituzione P [x/y] otterremmo la formula ∃x(x < x)
che assume tutto altro significato rispetto alla precedente e la variabili y passa dall’essere libera all’essere legata. C’è
un modo molto semplice di risolvere questo problema: (1) Prima della sostituzione di y con x rinominiamo (ovvero
sostituiamo) x con un altra variabile differente da x e da y. Vediamo la corretta definizione:

41
 Definizione 34 (SOSTITUZIONE IN FORMULE )

Sia P una FBF e t un termine.

1. se P = ⊥, allora P [t/x] = ⊥,
2. se P = A(t1 . . . , tn ), allora P [t/x] = A(t1 [t/x] . . . , tn [t/x]),
3. se P = ¬P (rispettivamente P = (P1 ◦ P2 ) per ◦ ∈ {∧, ∨, →}), allora P [t/x] = ¬P1 [t/x]
(rispettivamente P = (P1 [t/x] ◦ P2 [t/x]),

4. se P = ∀yQ (rispettivamente ∃yQ), allora

©Nicola Galesi – Draft


 ∀yQ[t/x] se x ̸= y e y ̸∈ F V (T )
∀yQ[t/x] = ∀zQ[z/y][t/x] se x ̸= y, y ∈ F V (T ), z non occorre in Q e t
∀yQ x=y


e rispettivamente

 ∃yQ[t/x] se x ̸= y e y ̸∈ F V (T )
∃yQ[t/x] = ∃zQ[z/y][t/x] se x ̸= y, y ∈ F V (T ), z non occorre in Q e t
∃yQ x=y


Vediamo un esempio
Esempio 12

def
Sia P = ∀x(A(x) → B(f (y), x)). e sia t = g(x). Allora
1. P [t/y] = ∀z(A(z) → B(f (g(x)), z)),

2. P [t/x] = P essendo x una variabile legata in P .

Osserviamo che la sostituzione di più variabili può essere simultanea oppure sequenziale e l’effetto sulla formula
può essere differente. Con la scrittura P [t1 . . . , tn /x1 . . . , xn ] denotiamo la formula in cui le variabili x1 , . . . , xn sono
sostituite simultaneamente per i termini t1 , . . . , tn . Vediamo un esempio in cui tale sostituzione si comporta in modo
differente dalla sostituzione in sequenza delle variabili.

1. A(x0 , x1 [x1 , x0 /x0 , x1 ] = A(x1 , x0 ), ma

2. A(x0 , x1 [x1 /x0 ][x0 /x1 ] = A(x1 , x1 )[x0 /x1 ] = A(x1 , x1 ).

3.3 Semantica: interpretazioni e valore di verità

Andiamo a dare ora un significato, una semantica, agli oggetti sintattici - le formule della logica del I° ordine. Abbiamo
visto che il linguaggio dei predicati è sufficientemente ampio per accogliere le definizioni di strutture matematiche
quali gruppi, ordine, anelli, basi di dati ecc. Andiamo quindi a dare definizione precise per trattare la semantica nel
caso predicativo

42
 Definizione 35 (S TRUTTURA)

Una struttura S è una coppia (DS , IS ) = (D, I) dove:

1. D è un qualunque insieme non vuoto detto D OMINIO,

2. I è una mappa che associa
(a) ad ogni simbolo di costante c in L un elemento cS ∈ D nel dominio.
(b) ad ogni simbolo di funzione f in L di arità k una funzione fS : Dk −→ D.
(c) ad ogni simbolo di predicato B in L di arità k una relazione k-aria BS su D, ovvero una funzione
BS : Dk −→ {0, 1}.
©Nicola Galesi – Draft

Tuttavia una formula del I° ordine è definita anche a partire da variabili e quindi non è possibile avendo solo una
struttura a disposizione assegnare dei valori di verità a delle formule. Ciò potrà essere fatto solo in presenza di una
precisa assegnazione alle variabili di valori dle dominio. Ovviamente questo può essere fatto in molti modi diversi.
Consideriamo dunque la seguente definizione
Definizione 36 (A MBIENTE)

Una AMBIENTE αS per una struttura S = (D, I) è una funzione delle variabili in D ovvero αS : VAR −→ D.

Ovviamente in un ambiente α per una struttura S è possibile che per alcune variabili sia già deciso un valore del
dominio associato. In questo caso scriveremo
α[a/x]
per denotare l’ambiente α dove alla variabile x è stato assegnato il valore a del dominio. Vale a dire:

α[a/x](y) = α(y) x ̸= y
α[a/x](y) = a x=y

Definizione 37 (I NTERPRETAZIONE)

Una I NTERPRETAZIONE I per un linguaggio L del I° ordine è una coppia I = (S, α) dove S è una struttura
e α un ambiente per S.

Esempio 13

def
Sia P = ∀x(A(x, f (x)) ∨ B(g(c, y)) dove A è un (simbolo di ) predicato binario, B un (simbolo di)
predicato unario, c una costante e f e g due simboli di funzione di arità rispettivamente 1 e 2. Conside-
riamo l’interpretazione (S, α) dove S = (D, I) e dove D = Z, AS = {(m, n) | m, n ∈ D, m > n},
B S = {n ∈ D | n primo }, cS = 2, f S : n 7→ n + 1, g S : (m, n) 7→ m + n e α(y) = 1.
In questa interpretazione P assume il significato di "Per ogni intero x x > x + 1, oppure 2 + 1 è un numero
primo" e vediamo essere, nell’interpretazione, una formula vera in quanto 2 + 1 è sempre primo.

Anche se intuiamo come dare un valore di verità a una formula, al momento non abbiamo alcuno strumento
formale per valutare il valore di verità di una formula sotto una data interpretazione I = (S, α). Per esempio è chiaro
che la precedente formula potrebbe risultare falsa in una interpretazione dove, rispetto alla precedente, solo cambia
l’interpretazione del simbolo di predicato B e diventa {n ∈ D | n = 0}.

43
 Definizione 38 (VALORE DI UN TERMINE SOTTO UN ’ INTERPRETAZIONE )

Sia I = (S, α) una interpretazione. Sia t un termine in TER. Il valore di t nell’interpretazione I è una
funzione

JtKI : TER −→ D
definita induttivamente come segue (per semplicità di scrittura scriviamo JtK invece di JtKI )
1. Se t = x, allora JtK = α(x),
2. se t = c, allora JtK = cS
©Nicola Galesi – Draft

3. Se t = f (t1 , . . . , tn ), con t1 , . . . , tn ∈ TER e f un simbolo di funzione di arità n, allora JtK =

f (Jt1 K, . . . , Jtn K).

A questo punto siamo pronti per definire come calcolare il valore di verità di una formula del I° ordine sotto una
interpretazione I .
Definizione 39 (VALORE DI VERITÀ DI UNA FORMULA )

Sia I = (S, α) una interpretazione. Sia F una formula in FBF. Il valore di verità di F sotto l’interpretazione
I è una funzione v I : FBF −→ {0, 1} definita come segue (scriveremo v per v I ):

0 F =⊥


A(Jt1 K, . . . , Jtn K) F = A(t1 , . . . , tn )




min(v(F1 ), v(F2 )) F = F1 ∧ F2




max(v(F1 ), v(F2 )) F = F1 ∨ F2



v(F ) = max(1 − v(F1 ), v(F2 )) F = F1 → F2
1 − v(F1 ) F = ¬F1




min{v (S,α[a/x]) (F1 )} = ∀xF1



 F

 a∈D
 max{v (S,α[a/x]) (F1 )}

F = ∃xF1
a∈D

Osserviamo che l’interpretazione del quantificatore universale riflette quella della congiunzione e può essere visto
come una congiunzione iterata su tutti gli elementi del dominio. Parimenti il quantficatore esistenziale corrisponde a
una disgiunzione.
Osservazione 3
A differenza di quanto avviene per la logica proposizionale notiamo che la definizione on consente di determi-
nare in modo effettivo (ovvero algoritmico) una valore di verità per una formula, in quanto il dominio potrebbe
essere composto da infiniti elementi e quindi occorrerebbero infiniti controlli.

Inoltre è importante osservare che il valore di verita v(F ) di una formula F in una interpretazione I = (S, α)
dipende dall’ambiente α ovvero da come le variabili libere di F vengono mappate nel dominio dal α. Le prossime due
proprietà definiscono questa caratteristica.
Lemma 1. Sia t un termine tale che F V (t) = {y1 , . . . , yn } e sia S una struttura. Se α, β sono due ambienti per S
tali che α(yi ) = β(yi ) per ogni i = 1, . . . , n, allora JtK(S,α) = JtK(S,β) .
Dimostrazione. Per induzione strutturale sulla definizione di t. Per esercizio.
Lemma 2. Sia F una formula tale che F V (A) = {y1 , . . . , yn } e sia S una struttura. Se α, β sono due ambienti per S
tali che α(yi ) = β(yi ) per ogni i = 1, . . . , n, allora v (S,α) (F ) = v (S,β) (F ).

44
 Dimostrazione. Per induzione strutturale sulla definizione di t. Per esercizio.
JtK

3.4 Verità, soddfisfacibilità e modelli

Iniziamo con il capire il concetto di soddisfaciblità e verità
Definizione 40
Sia F una FBF.
©Nicola Galesi – Draft

1. F è SODDISFATTA in una struttura S rispetto all’ambiente α. Se v (S,α) (F ) = 1. In questo caso

scriviamo (S, α) |= F .
2. F è S ODDISFACIBILE in una struttura S se esiste un ambiente α tale che (S, α) |= F .
3. F è S ODDISFACIBILE se esiste una struttura S tale che F è soddisfacibile in S.
4. F è V ERA in una struttura S se per ogni ambiente α, (S, α) |= F . In tale caso diremo che (S, α) è un
M ODELLO per F
5. F è VALIDA se è vera in ogni struttura.

Generalizziamo la precedente temrinologie a insiemi di formule.

Definizione 41
Sia Γ un insieme di FBF.
1. Γ SODDISFACIBILE se esiste una interpretazione I = (S, α) tale che per ogni F ∈ Γ si ha che I |= F .
2. Una interpretazione I = (S, α) è un M ODELLO per Γ se per ogni F ∈ Γ si ha che I |= F . In questo
caso scriviamo I |= Γ.

3. Γ è VALIDO se ogni interpretazione è modello per Γ in questo caso scriviamo |= Γ.

Definizione 42 (C ONSEGUENZA L OGICA)

Diremo che la formula Q è Conseguenza Logica delle formule in Γ, se per ogni intepretazione I = (S, α)
(ovvero per ogni struttura S e per ogni ambiente α) si ha che: se per ogni F , I |= F , allora I |= Q.

3.4.1 Paradosso del Barbiere

Definizione 43
Una FBF del I°ordine F è FALSA in una struttura S se non è soddisfacibile in S, ovvero se non esiste alcun
ambiente α tale che (S, α) |= F . Inoltre F è I NSODDISFACIBILE se non è soddisfacibile, ovvero è falsa in
ogni struttura.

Il seguente teorema viene lasciato eper esercizio.

45
 Teorema 10
Siano Γ un insieme di FBF e sia F una FBF. Allora
1. F valida se eoslo se ¬F insoddisfacibile.

2. F è soddisfacibile se e solo se ¬F non e valida.

3. Γ |= F se e solo Γ ∪ {¬F } insoddisfabile

Vediamo un esempio di formula insoddisfacibile. Consideriamo il seguente paradosso

Esempio 14 (PARADOSSO DEL BARBIERE DI B. RUSSEL)
©Nicola Galesi – Draft

In una piccola città vi è un solo barbiere e vige la seguente regola: il barbiere rade tutti e soli quegli uomini
del paese che non si radono da soli. Vediamo che tipo di paradosso implica tale regola.
Sia X l’insieme di tutte gli uomini del paese che non si radono da soli.

Il concetto di insieme era definito, prima di sviluppare al teoria assiomatica degli insiemi, come una collezione
per la quale possiamo decidere senza ambiguità ed universalmente, se un qualunque oggetto gli appartiene o meno.
Vedremo che tale definizione può produrre un paradosso, nel senso che esistono delle collezioni che non sono insiemi
nella definizione che abbiamo dato.
Il paradosso è noto anche come Paradosso del Barbiere di Bertrand Russel (un importante Logico e Filosofo
vissuto nel 1900).
(Paradosso di Russel – versione informale)

In un villaggio abita un solo barbiere. Il barbiere rade tutti e solamente gli uomini del villaggio che non si
radono da soli.
La domanda che cu si pone è la seguente: a quale insieme appartiene il barbiere ? A quello degli uomini che
si radono da soli, oppure a quello degli uomini che si fanno radere dal barbiere ?

La versione formale della contraddizione è la seguente

Esempio 15(Paradosso di Russel – versione formale)

Sia A = {X : X è un insieme e X ̸∈ X}. Ci si chiede: quali dei due casi è vero?

1. A ∈ A,

2. A ̸∈ A
Risposta: nessuno dei due casi. Dunque A non è un insieme.

Tale risultato ha minato le basi della matematica, che però ha continuato ad usare la definizione (intuitiva) di
insieme, evitando tali paradossi. Invece per avere una definizione matematicamente corretta di insieme si è introdotta
una teoria assiomatica degli insiemi (detta di Zermelo-Fraenkel) dove l’assunzione di alcuni assiomi evita il sorgere
di tali paradossi. (L’assunzione di assiomi per definire una teoria non è nuova. Per e sempio la geometria euclidea si
fonda su assiomi indimostrabili, per esempio l’assioma che afferma che due rette parallele non si incontrano mai).
È interessante notare due cose: primo, che il criterio con cui tale paradosso è formulato, discende direttamente
dalla cosidetta TECNICA DI D IAGONALIZZAZIONE introdotta da G. Cantor per dimostrare hce i numeri reali non
sono numerabili ovvero hanno un numero infinito di elementi di ordine maggiore di qeulli dei numeri naturali. (2)
evoluzioni di questo paradosso hanno portato nel corso del 1900 ha importanti risultati della matematica (Teoremi
di Incompletezza di Kurt Gödel) e importanti risultati della informatica (esistono problemi che non sono decidibili,

46
 ovvero per i quali non esiste un algoritmo che può risolverli, per esempio il ben noto Problema della Fermata di un
Algoritmo).

A noi interessa vedere che come il Paradosso del Barbiere formulato come una formula del I° ordine porti a una
formula insoddisfabile. Formalizziamo il Paradosso del Barbiere utilizzando il seguente linguaggio:

1. R(x, y) è un simbolo di predicato binario (interpretato come "x rade y".

2. b è un simbolo di costante (che rappresenta il barbiere)
Dunque al formliazzazione ha dure parti
1. Il barbiere rade tutti coloro che non si radono da soli. Tale asserzione può essere formulata come
©Nicola Galesi – Draft

∀x(¬R(x, x) → R(b, x))

2. Il barbiere rade solo coloro che non si radono da soli. Tale asserzione può essere formulata come

∀x(R(b, x) → ¬R(x, x))

Quindi la formala può essere scritta come

def
F = ∀x(¬R(x, x) → R(b, x)) ∧ ∀x(R(b, x) → ¬R(x, x))

Per dimostrare che è insoddisfacibile supponiamo per assurdo che sia soddisfacibile ovvero che ammetta un
modello, vale a dire che esiste una interpretazione I = (S, α), tale che I |= F . Dunque deve essere che:
1. I |= ∀x(¬R(x, x) → R(b, x))

2. I |= ∀x(R(b, x) → ¬R(x, x)
Consideriamo la prima. Dalla definizione di valore di verità deve essere che

min{max(R(a, a), R(b, a)) | a ∈ DS } = 1

Quindi, poiché b ∈ DS , in particolare deve essere che

max(R(b, b), R(b, b)) = 1

ovvero che R(b, b) = 1. Consideriamo ora la seconda, dalla definizione di valore di verità deve essere

min{max(1 − R(b, a), 1 − R(a, a)) | a ∈ DS } = 1

Dunque, deve essere che

max(1 − R(b, b), 1 − R(b, b)) = 1
ovvero che R(b, b) = 0. In conclusione sotto l’ipotesi per assurdo che la formula fosse soddisfacible nella interpreta-
zione I otteniamo che sotto I la formula R(b, b) risulta sia vera che falsa. E questa è una contraddizione.

3.5 Ragionare di Semantica nel metalinguaggio

Andremo a veder adesso la connessione formale per ragionare di dimostrazioni di soddisfaciblita, validità e insoddi-
facibilita di formule in logica del I° ordine. COnsideriamo

47
 Definizione 44

Data una FBF F tale che F V (F ) = {x1 , . . . , xn }, definiamo

def
• chiusura universale di F la formula chiusa Cl(F ) = ∀x1 · · · ∀xn F .
def
• chiusura esistenziale di F la formula chiusa Ex(F ) = ∃x1 · · · ∃xn F .

Lasciamo per esercizio le seguenti proprietà:

Lemma 3. Sia F una FBF tale che F V (F ) = {x1 , . . . , xn }, Valgono le seguenti tre proprietà
©Nicola Galesi – Draft

1. per ogni interpretazione I , I |= F se e solo se I |= Cl(F ).

2. F valida se e solo se Cl(F ) lo è.

3. F è soddisfacibile se e solo se Ex(F ) lo è.

Il prossimo teorema asserisce che nelle dimostrazione sulla verità/soddisfacibilità/validità di formule è possibile
sostituire i connettivi e quantificatori con i corrispttivi termini del metalinguaggio e interpretare gli atomi verificando
le relazioni nella struttura
Teorema 11

Per ogni FBF F e G e per ogni interpretazione I = (S, α) valgono le seguenti proprietà:

1. I |= F ∧ G se e solo se I |= F e I |= G.
2. I |= F ∨ G se e solo se I |= F o I |= G.
3. I |= F → G se e solo se (I |= F ⇒ I |= G).

4. I |= ¬F se e solo se I ̸|= F .
5. (S, α) |= ∀xF se e solo se (S, α[a/x] ) |= F per ogni a ∈ DS .
6. (S, α) |= ∃xF se e solo se (S, α[a/x] ) |= F per qualche a ∈ DS .

Dimostrazione. Diamo la dimostrazione della (3). Tutte le altre seguono da ragionamenti simili. Dimostriamo prima
che se I |= F → G, allora (I |= F ⇒ I |= G). Abbreviamo v I (F ) con v(F ). Dunque supponaimo che
v(F ) = 1 e per ipotesi sappiamo che v(F → G) = 1, vale a dire che max(1 − v(F ), v(G)) = 1. Dunque deve essere
che v(G) = 1 e quindi I |= G.
Per l’altra implicazione supponiamo per assurdo che I ̸|= F → G. Dunque max(1 − v(F ), v(G)) = 0. Dunque
deve essere che 1 − v(F ) = 0 (e quindi v(F ) = 1) e v(G) = 0. Dunque I |= F e I ̸|= G che contraddice
l’ipotesi.
Vediamo degli esempi.

48
 Esempio 16

Sia F la formula ∀x∀y∃zC(f (x, y, ), z). Consideriamo la seguente interpretazione (S, α):

1. DS = Z
2. f S = (x, y) 7→ x − y
3. C S = {(n, m) | n, m ∈ DS , n = m}
Sotto questa interpretazione la formula precedente può essere scritta (nel metalinguaggio) come: per ogni
n, m ∈ Z esiste un numero p ∈ Z tale che p = n − m. Tale proprietà è chiaramente vera e possiamo quindi
concludere che (S, α) |= F . Dunque F è soddisfacibile in quanto possiede un modello.
©Nicola Galesi – Draft

Esempio 17

Vogliamo dimostrare che la formula

def
F = ∃x∀yA(x, y) → ∀y∃xA(x, y)

è valida.
Consideriamo una generica interpretazione (S, α) con DS = D. Dal Teorema precedente si ha che (S, α) |=
[a/x][b/y]
F se e solo se per qualche a ∈ D si ha che per ogni b ∈ D si ha che v (S,α )
(A(x, y)) = 1 implica che
[d/x][c/y]
(S,α )
per ogni c ∈ D esiste un d ∈ D tale che v (A(x, y)) = 1

Esempio 18

Si consideri il seguente esempio

def
F = (∃xA(x) → ∀xB(x)) → ∀x(A(x) → B(x))

Si osservi che la formula (∃xA(x) → ∀xB(x)) asserisce che se esiste un elemento del dominio a che rende
vera A(a), allora B(x) è vera per ogni elemento x del dominio. Facciamo vedere come usare la precedente
osserrvazione per verificare che la formula ∀x(A(x) → B(x)) è sempre vera. Sia b un generico elemento del
dominio. Se A(b) è falsa allora A(b) → B(b) è vera. Se A(b) è falsa, allora esiste un elemento del dominio
che rende vera A e quindi dalla discussione precedente si che B(x) è vera per ogni elemento del dominio e
quindi anche B(b) sarà vera. Concludiamo quindi che che (∃xA(x) → ∀xB(x)) → ∀x(A(x) → B(x)) è
sempre vera, ovvero la formula è valida.

In general dimostrare che una formula è valida ragionando sulla semantica non è sempre né facile né divertente. Di
fatto grazie al teorema di completezza per il calcolo dei predicati dimostrare una formula è equivalente a dimostrarne
la validità. Invece ragionare con la semantica è di molto aiuto nel momento in cui si vuole dimostrare che una formula
non è valida e per tanto va dimostrato che esiste qualche interpretazione in cui la formula è falsa. Vediamo un esempio

49
 Esempio 19

Consideriamo la formula
def
F = ∃x(A(x) → B(x)) → (∃xA(x) → ∃xB(x))

Prima di tutto ragioniamo sul fatto che tale formula non appare essere valida. Infatti, il fatto che esista un a nel
dominio tale che A(a) → B(a) è vera, non esclude affatto che B(a) possa essere falsa per ogni a nel dominio
(infatti potrebbe essere che A(a) sia falsa). Inoltre A(x) potrebbe essere vera per qualche altro elemento nel
dominio. Dunque sotto l’ipotesi che ∃x(A(x) → B(x)) sia vera non possiamo escludere che B(x) sia falsa
per ogni elemento nel dominio mentre esiste un elemento a tale che A(a) sia vera. Ma allora la conclusione
della formula è falsa. Dunque la formula non è valida.
©Nicola Galesi – Draft

Andiamo ora a costruire una interpretazione in cui F è falsa. F è della forma F1 → F2 . dunque per risultare
falsa sotto l’interpretazione I deve essere che I |= F1 e I ̸|= F2 . Ancora, F2 è della forma G1 → G2 ,
dunque perché I ̸|= F2 deve risultare che I |= G1 e I ̸|= G2 . Poiché G2 è la formula ∃xB(x), se scegliamo
di interpretare in I il predicato B come la relazione vuota, ci assicuriamo che I ̸|= G2 . Invece per avere
I |= G1 , poiche G1 è la formula ∃xA(x) il predicato A deve essere interpretato come una relazione non
vuota.
Ora I deve essere tale che I |= F1 e F1 è la formula ∃x(A(x) → B(x)). È sufficiente fare in modo che per
almeno un elemento a nel dominio A(a) risulti falsa per ottenere che ∃x(A(x) → B(x)) sia vera. Dunque in
I è sufficente intperetare il predicato A in modo che per almeno un elemento A sia falsa.
In conclusione per rendere la formula F falsa sotto I sarà sufficiente interpretare il predicato B come la
relazione vuota e fare in modo che A corriposnda a una relazione che risulta essere essere vera per almeno un
elemento nel dominio e falsa per almeno un altro elemento nel dominio.
Dunque possiamo scelgliere I come segue

1. D = N
2. A(x) = {x ∈ N | x pari}
3. B(x) = ∅

3.6 Forme Normali

Una formula del primo ordine può essere difficile da leggere a causa dei molti quantificatori che possono essere
presenti. In questa sezione andiamo a vedere come le formule del primo ordine possono essere trasformate in una
forma normale semanticamente equivalente in cui tutti i quantificatori compaiono solo davanti al corpo della formula
che coì non contiene più quantificatori. Per prima cosa andiamo a studiare l’equivalenza semantica in formule del I°
ordine dove, rispetto al caso proposizionale, la situazione è complicata dai quantificatori e dalle variabili libere.

3.6.1 Equivalenza Logica

Per prima cosa diamo la definizione di equivalenza logica
Definizione 45
Due FBF P e Q sono SEMANTICAMENTE EQUIVALENTI, e scriveremo P ≡ Q se per ogni interpretazione
I = (S, α) risulta che
v (S,α)) (P ) = v (S,α)) (Q)

50
 Esercizio 6

Far vedere che P ≡ Q se e solo se |= P ↔ Q

Come primo esempio andiamo a vedere che se rinominiamo la variabile quantificato e nel campo d’azione del
quantificatore con un altro nome si ottiene una formula equivalente.
A tale scopo è necessario il seguente importante lemma di sostituzione il cui significato informale è il seguente: se
in un termine t sostituiamo la variabile x per una nuova variabile y, allora l’interpretazione di t non cambia. Parimenti
se in una formula P operiamo la stessa sostituzione il valore di verità di P non cambia. In relata è sufficiente richiedere
solo che la variabile y non appaia libera in t e P , ma noi vedremo il caso in cui y è una nuova variabile.
Lemma 4. Siano t un termine, y una variabile, P una formula e (S, α) una interpretazione. Allora
©Nicola Galesi – Draft

1. se y non occorre libera in t, allora JtKα[a/x] = Jt[y/x]Kα[a/y] .

2. se y non occorre libera in t, allora v (S,α[a/x]) (P ) = v (S,α[a/y]) (P [y/x])

La dimostrazione del precedente lemma è per induzione strutturale sul termine sulla formula. (Per esercizio si può
fare il caso in cui y non occorre invece di non occorre libera)
Dal precedente Lemma si ricava direttamente le seguenti proprietà.
Teorema 12 (Rinominare variabili quantificate)

Sia P una formula e z una variabile che non occorre in P .

1. ∃xP ≡ ∃zP [z/x]
2. ∀xP ≡ ∀zP [z/x]

Il seguente teorema generalizza le leggi di De Morgan al caso dei quantificatori

Teorema 13 (Leggi de Morgan)

Sia P una FBF

1. ¬∃xP ≡ ∀x¬P
2. ¬∀xP ≡ ∃x¬P

3. ∃xP ≡ ¬∃x¬P
4. ∀xP ≡ ¬∀x¬P
Dimostrazione. Dimostriamo la (2), le altre seguono per dimostrazioni simili. Per il Teorema 11 (S, α) |=
¬∀xP se e solo se (S, α) ̸|= ∀xP e questo se e solo se esiste un b inD tale che (S, α[b/x]) ̸|= P . Questo è
equivalente a dire che (S, α[b/x]) |= ¬P e questo se e solo se (S, α) |= ∃x¬P .

Il prossimo teorema asserisce che l’ordine dei quantificatori dello stesso tipo è irrilevante

51
 Teorema 14 (ordine quantificatori simili)

Sia P una FBF, allora:

1. ∀x∀yP ≡ ∀y∀xP
2. ∃x∃yP ≡ ∃y∃xP

3. ∀xP ≡ P se x ̸∈ F V (P )
4. ∃xP ≡ P se x ̸∈ F V (P )

Il prossimo teorema consente id distribuire i quantifcatori rispetto ai connetiivi di ∧ e ∨. Tuttavia dobbiamo

©Nicola Galesi – Draft

ricordare che il ∀ è analogo a un ∧ e il ∃ un ∨. dunque va fatta attenzione a come distribuire i quantificatori rispetto a
un connettivo non analogo
Teorema 15 (Distributività)

Sia P, Q due FBF, allora:

1. ∀x(P1 ∧ P2 ) ≡ ∀xP1 ∧ ∀xP2
2. ∃x(P1 ∨ P2 ) ≡ ∃xP1 ∨ ∃xP2
3. ∀x(P1 ∨ P2 ) ≡ ∀xP1 ∨ P2 se x ̸∈ F V (P2 )

4. ∃x(P1 ∧ P2 ) ≡ ∃xP1 ∧ P2 se x ̸∈ F V (P2 )

Dimostrazione. Dimostriamo la numero (3), le altre seguono in modo analago. Dal Teorema 11 per ogni interpreta-
zione (S, α) risulta che (S, α) |= ∀xP1 ∨ P2 se e solo se

(S, α) |= ∀xP1 oppure (S, α) |= P2 (1)

Poiché x ̸∈ F V (P2 ) e poiché (S, α) |= P2 allora anche (S, α[b/x]) |= P2 per ogni elemento b ∈ D nel dominio.
Inoltre da (1) si ha che

per ogni b ∈ D (S, α[b/x]) |= P1 oppure per ogni b ∈ D (S, α[b/x]) |= P2

quindi
per ogni b ∈ D (S, α[b/x]) |= P1 ∨ P2
e quindi, infine
(S, α) |= ∀x(P1 ∨ P2 )

Teorema 16 (Connettivi ∧ e ∨)

Sia P, Q due FBF, allora:

1. ♢1 xP ∨ ♢2 xQ ≡ ♢1 x♢2 z(P1 ∨ P2 [z/x])

2. ♢1 xP ∧ ♢2 xQ ≡ ♢1 x♢2 z(P1 ∧ P2 [z/x])

dove ♢1 , ♢2 ∈ {∀, ∃} e z ̸∈ F V (P1 ) ∪ F V (P2 )

52
 Teorema 17(Connettivo →)

Se x ̸∈ F V (Q), allora

1. ∀xP → Q ≡ ∃x(P → Q).

2. ∃xP → Q ≡ ∀x(P → Q).
3. Q → ∀xP ≡ ∀x(Q → P ).
4. Q → ∃xP ≡ ∃x(Q → P ).
©Nicola Galesi – Draft

3.6.2 Forma Prenessa

Le preceedenti leggi logiche suggeriscono che in un formula del I° ordine i quantificatori possono essere mossi nella
formula (mantenendo l’equivalenza logica) verso l’esterno a patto di rispettare vincolo imposti dalle variabili libere.
Una formula in tale forma si dice forma normale prenessa.
Definizione 46
una FBF F è in FORMA NORMALE PRENESSA (FNP) se ha la forma del tipo

♢1 x1 ♢2 x2 · · · ♢n xn P

con n ≥ 0 e ♢i ∈ {∀, ∃} e P non contiene quantificatori. In questo caso P è detta MATRICE DI F e

♢1 x1 ♢2 x2 · · · ♢n xn PREFISSO di F .

Esempio 20

La formula ∀x∃y∀z(A(x, y) ∨ B(z) → C(f (x, y), z)) è in forma normale prenessa.

Teorema 18
Per ogni FBF F esiste una formula equivalente F ∗ in forma nomale prenessa.

Dimostrazione. Si procede per induzione strutturale su F

1. (caso Base) se F è atomica, allora F ∗ è proprio F .
2. se F = ¬F1 , allora per ipotesi induttiva abbiamo F1∗ in FNP e quindi F ∗ = ¬F1∗

3. se F = F1 ◦ F2 , allora per ipotesi induttiva abbiamo F1∗ e F2∗ in FNP e quindi F ∗ = F1∗ ◦ F2∗ .
4. Se F = ∀xF1 , allora abbiamo F1∗ in FNP e quindi F ∗ = ∀xF1∗
5. Se F = ∃xF1 , allora abbiamo F1∗ in FNP e quindi F ∗ = ∃xF1∗

53
 Esempio 21

def
Costruiamo la FNP della formula F = ∀xA(x) → ¬∀yB(y)

∀xA(x) → ¬∀yB(y) ≡ ∀xA(x) → ∃y¬B(y)

≡ ∃y(∀xA(x) → ¬B(y))
≡ ∃x∃y(A(x) → ¬B(y))

3.6.3 Forma di Skolem

©Nicola Galesi – Draft

Consideriamo una formula FBF della forma ∃xA(x) con A(x) un predicato unario. Osserviamo che se ∃xA(x) è
soddisfacibile, allora esiste una interpretazione I per la quale esiste un elemento a del dominio tale che A[a/x]
risulta vera, ovvero soddisfacibile. D’altra parte se un predicato B(x) è vero per un elemento b del dominio in una
data intepretazione I , ovvero B[b/x] è vera in I , dunque soddisfacibile, allora anche la formula ∃xB(x) sarà
soddisfacibile, in quanto vera sotto l’interpretazione I .
In questo capitolo analizzeremo dunque la possibilità di ulteriormente semplificare una FBF in forma normale
prenessa togliendo i quantificatori esistenziali e sostituendo le variabile quantificate esistenzialmente con un termine
la cui interpretazione dovrebbe essere quella della elemento del dominio che la rende vera la formula come negli
esempi precedenti. Anticipiamo però due osservazioni molto importanti:
1. Al contrario della formula prenessa togliendo i quantificatori esistenziali e sostituendo le corispondenti variabili
per dei termini non potremo ottenere una formula semanticamente equivalente- tuttavia saremo in grado di
preservare la soddisfacibilità della formula.
2. Nel rimuovere i quantiicatori esistenziali bisogna fare molta attenzione ai quantificatori universali che nella
formula in forma normale prenessa precedono il quantificatore esistenziale che vigliamo togliere. Per capirne il
motivo consideriamo un esempio, la definizione di limite di una successione, ovvero che lim an = ℓ, la quale
n→N
asserisce che
∀ϵ > 0 ∃n0 ∈ N tale che ∀n ∈ N, n ≥ n0 si ha che |an − ℓ| < ϵ

Osserviamo che nel verificare che effettivamente lim an = ℓ, fissato un ϵ > 0 generico dobbiamo trovare
n→N
un n0 tale che |an − ℓ| < ϵ per ogni n ≥ n0 . dunque per trovare tale n0 partiamo dal voler soddisfare che
|an0 − ℓ| < ϵ e dunque il valore di n0 che troviamo dipende da ϵ. Dunque osserviamo che se volessimo
eliminare il quantificatore esistenziale di questa definizione il termine che dobbiamo sostituire a n0 dipende da
ϵ ovvero è una funzione ϵ. ϵ è un parametro quantificato universalmente che nella formulazione della proprietà
appare prima del quantificatore esistenziale. Questa dipendenza deve essere chiaramente esplicitata quando
sostitutiamo la variabile quantificata per un termine.

Definizione 47 (F ORMA DI S KOLEM)

def
Sia P una FBF in forma normale prenessa, cioè P = ♢1 x1 ♢2 x2 · · · ♢n xn P1 . Si dice F ORMA DI S KOLEM
di P , P S la FBF ottenuta con il seguente procedimento detto skolemizzazione: per ogni occorrenza di un
quantificatore esistenziale ♢i

1. se ♢i non è nel campo di azione di alcun quantificatore universale si inotrudce una costante c che non
appare in P1 si cancella ♢i xi dal prefisso e si sostituisce c a xi in P1 , ovvero P [c/xi ].
2. Se invece ♢i compare nel campo di azione dei quantificatori universali ♢i,1 . . . , ♢i,m , allora si introduce
un simbolo di funzione m-ario g, si cancella si cancella ♢i xi dal prefisso e si sostituisce g(xi,1 , . . . xi,1 )
a xi in P1 , ovvero P [g(xi,1 , . . . xi,1 )/xi ].

54
 Esempio 22

La FBF ∃x∀y∀z∃tB(x, y, z, t) ha la seguente forma di Skolem

∀y∀zB(c, y, z, f (y, z))

Teorema 19

Per ogni FBF F F è soddisfacibile se e solo se P S lo è

Il seguente corollario è molto important per soddisfare formule aperte, ovvero che contengono variabili libere.
©Nicola Galesi – Draft

Corollario 5

Sia P una FBF. È possibile trasformarla in un FBF P ′ chiusa ed in forma di Skolem soddisfacibile se e solo
se P lo è.

Dimostrazione. Siano F V (P ) = {x1 , . . . , xn }. Per il Lemma 3 (pagina 47) P è soddisfacibile se e solo se ∃x1 . . . ∃xn P
lo è. Posto P ′ = (∃x1 . . . ∃xn P )S , l’asserto segue dal teorema precedente.

3.7 Esempi di linguaggi del I° ordine

Costruiamo ora delle teorie del primo ordine per determinate strutture matematiche considerando dei S ISTEMA A S -
SIOMATII . Ovvero costruiremo di linguaggi del primo ordine generalizzati in cui oltre l’usuale linguaggio del primo
ordine si considerano delle formule detti A SSIOMI che definsicono la struttura matematica consentiranno di derivare
proprietà in calcoli logici del I ordine.

3.7.1 Uguaglianza
Un predicato di particolare rilevanza è l’uguaglianza. Per le sue caratteristiche generalli molto spesso tale predicato
viene considerato dal punto di vista logico, come un particolare simbolo logico dell’alfabeto del linguaggio (che
dunque richiede una specific interpretazione) piuttosto che come un semplice simbolo di predicato. Parleremo in
questo caos i logiche con uguaglianza.
Se si vuole trattare l’uguaglianza come un normale simbolo di predicato allora si deve cercare di assiomatizzarne
le proprietà caratteristiche che lo definiscono. Quest possono esser descritte al primo ordine dalle seguenti formule
assiomi
1. ∀xx = x

2. ∀x∀y(x = y → y = x)
3. ∀x∀y∀z(x = y ∧ y = z → x = z)
4. per ogni simbolo di funzione f n-ario del linguaggio:

∀x1 . . . ∀xn ∀y1 . . . ∀yn (x1 = y1 ∧ · · · ∧ xn = yn → f (x1 . . . , xn ) = f (y1 , . . . , yn ))

5. per ogni simbolo di predicato A n-ario del linguaggio:

∀x1 . . . ∀xn ∀y1 . . . ∀yn (x1 = y1 ∧ · · · ∧ xn = yn → A(x1 . . . , xn ) = A(y1 , . . . , yn ))

55
 i primi tre assiomi asseriscono che il predicato di uguaglianza è una relazione d’equivalenza, gli ultimi due che
una congruenza rispetto a tutti i simboli di funzione e di predicato. In ogni teoria che usa il predicato di uguaglianza
si assumono implicitamente i precedenti assiomi
Per la teoria dei numeri, l’alfabeto si compone di un solo simbolo 0 interpretato come 0 di una solo simbolo di
funzione s interpretato come la funzione successore n 7→ n + 1 e del predicato di uguaglianza. Gli assiomi che
caratterizzano la teoria dei numeri sono:
1. ∀x(¬(0 = s(x)))
2. ∀x∀y(s(x) = s(y) → x = y)
3. ∀x(x + 0 = x)
©Nicola Galesi – Draft

4. ∀x∀y(x + s(y) = s(x + y))

5. ∀x(x ∗ 0 = 0)
6. ∀x∀y(x ∗ s(y) = x + (x ∗ y))
7. per ogni predicato unario P (x) con variabile libera x

[P (0) ∧ (∀x(P (x) → P (s(x))))] → ∀xP (x)

I primi due assiomi definiscono la funzione successore. Glia assiomi 3) e 4) definiscono in modo ricorsivo la
somma + sui numeri naturali ( 3 il caso base e 4 il caso induttivo). Gli assiomi 5) e (6) definiscono il prodotto di
due numeri naturali sempre in modo ricorsivo ( 6 il caso base e 7 il caso induttivo). L’assioma 7 , che è uno schema
di assioma (perche vale per ogni predicato unario P ) definisce il principio di induzione sui numeri naturali. Come
vedremo nel prossimo capitolo consente di formalizzare in un calcolo del I ordine dimostrazioni per induzione di
properità sui numeri naturali.

3.7.2 Ordini

56
 Capitolo 4

Calcolo dei Predicati

©Nicola Galesi – Draft

Abbiamo visto nel precedente caapitolo come i quantificatori e i predicati conducano a una logica molto più espressiva
dei quella proposizionale. Andiamo adesso a capire le regole dei calcoli logici per logiche del primo ordine con i
quantificatori. Come abbiamo fatto per i connettivi andiamo a discutere come inroudrre ed eliminare quantificatori

4.1 Regole intuitive per i quantificatori

Per prima cosa trattiamo il caso del quantificatore universale. Se consideriamo una formula ∀xA, intuitivametne stiamo
dicendo che la formula A deve essere vera per ogni elemento del dominio di una qualunque interpretazione. Dunque
ha senso che sia A[t/x] per un qualunque termine t. Quindi la regola intuitiva di eliminazione del quantificatore
universale è del tipo

∀xA ⊢ A[t/x]
Viceversa quando possiamo sperare di introdurre un quantificatore davanti ad una formula A ? È chiaro che
avendo derivato solo A[t/x] epr uno specifico termine t non è sufficiente per poter concludere ∀xA(x). D’altra
parte se abbiamo derivato la formula A[y/x] dove y è una variabile libera in A, allora visto che l’ambiente di una
intepretatzione può assegnare ad y un qualunque valore del dominio, ha senso poter concludere che siamo ∀xA(x) è
vera. Quindi potremmo concludere che la regola intuitiva di introduzione del quantificatore universale è

se Γ ⊢ A[y/x], allora Γ ⊢ ∀xA[x]

Tuttavia potrebbe sorgere un altro problema: cosa succede se y appare come variabile libera anche in Γ? potrebbe
perdersi al generalità del ragionamento logico. Infatti consideriamo il seguente esempio:
Esempio 23

Consideriamo la seguente asserzione: "Se y è pari, allora il successore di y è dispari. In una formula del primo
ordine potremmo tradurla come P (y) → D(S(y)), dove P (y) sta per "y pari" D(y) per "y dispari" e S(y) è
il successore di y.
Se fosse corretta la regola vista sopra, poteremo derivare una formula del tipo: P (y) → ∀xD(S(x)) che è
evidentemente una formula falsa in una interpretazione come quella descritta prima.

Il problema qui è che nella prima formula le occorrenze della variabile y in P (y) e in D(S(y)) sono correlate
tra loro e y appare libera in tutta la formula. Mettendo un quantificatore solo davanti alla seconda formula e di fatto
legando la seconda occorrenza della y (che viene chiamata x) recidiamo la correlazione, che però era necessaria per
mantenere la struttura logica della formula. Dunque per poter applicare la introduzione di un quantificatore universale
alla conclusione di una formula c’è necessita che la variabile libera che andiamo a legare con il quantificatore non

57
 appaia libera nella premessa delle formula. Dunque in conclusione la regola di introduzione del ∀ possiamo definirla
in questo modo:

se Γ ⊢ A[y/x], allora Γ ⊢ ∀xA[x] y ̸∈ F V (Γ)

Veniamo invece al caso del quantificatore esistenziale. Per dualità risulta logicamente molto chiara ed intuitiva la
regola di introduzione del ∃. Infatti se abbiamo derivato la formula A[t/x] dove a x è sostituito un qualunque temine t
allora è logicamente vero logico dire che esiste un elemento a del dominio per cui la formula A[a/x] è vera. e quindi
ha senso dire che ∃xA(x). Dunque possiamo esprimere la regola di introduzione del ∃ come segue:

A[t/x] ⊢ ∃xA
©Nicola Galesi – Draft

Vediamo invece il caso opposto. Cosa possiamo concludere se abbiamo derivato ∃xA?. Ricordiamo che l’esistenziale
è logicamente a una disgiunzione potenzialmente infinita. Ricordando la regola di eliminazione del ∨ nel calcolo
proposizionale potemmo dire che la regola potrebbe essere qualcosa del tipo

se ΓA[y/x] ⊢ C e ∃xA, allora Γ ⊢ C.

Osserviamo per prima cosa come semplificare tale regola. Notiamo che se modifichiamo la conclusione della
regola in Γ, ∃xA ⊢ C, allora potremo ottenere la conclusione originale Γ ⊢ C semplicemente operando un taglio
(eliminazione del →) usando la derivazione di ∃xA. Dunque esprimiamo la regola in modo più compatto dicendo che

se ΓA[y/x] ⊢ C , allora Γ, ∃xA ⊢ C

Tuttavia, come nel caso del ∀, sorge un altro problema legato alla variabile y nella formula premessa della re-
gola. Se infatti y appare libera anche in Γ, allora si presenterebbe un problema del tutto analogo a quello visto
precedentemente.
Esempio 24

Ancora con l’esempio di prima: da P (y) ⊢ D(S(y)) potremo concludere che ∃xP (x) ⊢ D(S(y)) da cui
potremo concludere che ∃xP (x) ⊢ ∀xD(S(x)) che è una formula evidentemente falsa.

Dunque anche in questo caso c’è necessita che la variabile y non appaia libera in Γ. E la regola deve essere espressa
come segue:
se ΓA[y/x] ⊢ C , allora Γ, ∃xA ⊢ C y ̸∈ F V (Γ)

4.2 Calcolo dei sequenti per la logica dei predicati

Iniziamo discutendo la regole del ∀. Ricordiamo che nel calcolo dei sequenti non vi sono introduzione ed eliminazione
dei connettivi ma solo introduzione a destra e sinistra. Inoltre è utile ricordare che la semantica di un sequente della
forma A1 , . . . , An ⊢ B1 , . . . , Bm equivale alla formula A1 ∧. . .∧An → B1 ∨. . . Bm . Dunque la differenza tra l’intro-
duzione del ∧ (rispettivamente del ∨) a destra e sinistra troverà analogia nel caso dei quantificatori ∀ (rispettivamente
∃). Iniziamo dal ∀.
Essendo semanticamente equivalente a un congiunzione la regola del introduzione del ∀ a sinistra è piusstto
naturale

Γ, A[t/x] ⊢ ∆
(∀, sx)
Γ, ∀xA ⊢ ∆
In termini informali tale regola può essere letta nel seguente modo: se a sinistra del sequente ho derivato la formula
A dove al posto di x compare una costante qualunque, allora posso derivare la formula A per una qualunque costante
e dunque ∀xA. D’altra parte per introdurre a sinistra un ∀ dobbiamo richiedere qualcosa di più. Infatti per poter

58
 introdurre un ∧ su infinite formula A(x) dovremmo richiedere che Γ, A[c/x] ⊢ ∆ è derivabile per ogni costante c nel
dominio. Ma nel callcolo die predicati questo può essere detto facilmente e in maniera compatta dicendo che abbiamo
derivato Γ, A[y/x] ⊢ ∆ dove y è una variabile libera in A. D’altra parte abbiamo visto dagli esempi precedenti che
quella variabile y non deve interferire con altre variabili libero con lo stesso nome in Γ e ∆. Dunque la regola della
introduzione del ∀ a sinistra può essere scritta come segue:

Γ ⊢ A[y/x], ∆
(∀, dx) y ̸∈ F V (Γ) ∪ F V (∆)
Γ ⊢ ∀xA∆
Il caso dell’ ∃ è duale al caso del ∀ cosi come l’∨ è duale al caso del ∧. Dunque le regole per il quantificatore ∃
sono :
Γ ⊢ A[t/x], ∆
(∃, dx)
©Nicola Galesi – Draft

Γ ⊢ ∃xA∆
e

Γ, A[y/x], ⊢ ∆
(∃, sx) y ̸∈ F V (Γ) ∪ F V (∆)
Γ, ∃xA, ⊢ ∆
Nel complesso le regole del calcolo sequenti (per i connettivi) per il caso predicativo sono riassunte nella tavola

Regole per i connettivi del Calcolo dei Sequenti nel caso predicativo

Γ, A, B ⊢ ∆ Γ ⊢ A, ∆ Γ, B ⊢ ∆
(∧,l) (∧, r)
Γ, A ∧ B ⊢ ∆ Γ ⊢ ∆, A ∧ B

Γ, A ⊢ ∆ Γ, B ⊢ ∆ Γ ⊢ A, B∆
(∨,l) (∨, r)
Γ, A ∨ B ⊢ ∆ Γ ⊢ ∆, A ∨ B

Γ ⊢ A, ∆ Γ, B ⊢ ∆ Γ, A ⊢ B∆
(→,l) (→, r)
Γ, A → B ⊢ ∆ Γ ⊢ ∆, A → B

Γ ⊢ ∆, A Γ, A ⊢ ∆
(¬,l) (¬, r)
Γ, ¬A ⊢ ∆ Γ ⊢ ∆, ¬A

Γ, A[t/x] ⊢ ∆ Γ ⊢ ∆, A[y/x]
(∀,l) (∀, r)
Γ, ∀xA ⊢ ∆ Γ ⊢ ∆, ∀xA

Γ, A[y/x] ⊢ ∆ Γ ⊢ ∆, A[t/x]
(∃,l) (∃, r)
Γ, ∃xA ⊢ ∆ Γ ⊢ ∆, ∃xA

Si ricordi che nelle regole (∀, r) e (∃, l) la variabile y non deve occorrere libera né in Γ né in ∆. Le regole strutturali, cioè
di manipolazione delle formule nei sequenti e la regole del weakening rimangono identiche al caso proposizionale.

Vediamo alcuni esempi di derivazione:

59
 Esempio 25
©Nicola Galesi – Draft

Esempio 26

4.3 Invertibilità delle regole e rami di dimostrazione infiniti

Al contrario del caso proposizionale in cui abbiamo visto che le regole del calcolo dei sequenti sono invertibili, nel
caso predicativo si presentano dei problemi nei casi delle regole del ∀ e delle ∃. Capiamo con degli esempi quali sono
questi problemi e perché porteranno a un algoritmo di ricerca di dimostrazione nel caso predicativo che potrebbe, in
certi casi, non terminare mai.
Consideriamo la seguente refutazione

A(t1 ) ⊢ A(t1 ) A(t2 ) ⊢ A(t2 )

A(t1 ) ⊢ ∃xA(x) A(t2 ) ⊢ ∃xA(x)
A(t1 ) ∨ A(t2 ) ⊢ ∃xA(x)

Osserviamo che non esiste modo di derivare questo sequente applicando la regole di introduzione dell’ ∃ a destra
come ultima regola. Infatti se nella ricerca di una dimostrazione all’indietro cerchiamo di risolvere il quantificatore
esistenziale avremmo un sequente del tipo

60
 A(t1 ) ∨ A(t2 ) ⊢ A(t3 ).
Tale sequente, anche nel caso in cui t3 fosse uno tra t1 e t2 , non è derivabile. Dunque, con le regole appena
date, se il nostro algoritmo di ricerca di una dimostrazione si trova in un simile caso, l’algoritmo non funzionerebbe
correttamente.
Vediamo come risolvere un tale problema e argomentiamo come, tuttavia, sorge un ulteriore problema.
Una maniera di risolvere il problema è quello di modificare la regole (∃, r) nella seguente regola ridondante

Γ ⊢ ∆, A[x/t1 ], . . . A[x/tn ]
(∃, r)′
Γ ⊢ ∆, ∃xA(x)
©Nicola Galesi – Draft

Ovviamente tale regola non ha senso dato che i termini possono essere infiniti e dunque possiamo pensare di codificare
tale regola in una regola compatta del seguente tipo

Γ ⊢ ∆, A[x/t], ∃xA(x)
(∃, r)′′
Γ ⊢ ∆, ∃xA(x)
Tale regola ora permette di risolvere l’esempio precedente risolvendo come prima regola la regola dell’∃ a sinistra.
Infatti è valida la seguente derivazione

A(t1 ) ⊢ A(t1 ), A(t2 ), ∃xA(x) A(t2 ) ⊢ A(t1 ), A(t2 ), ∃xA(x)

A(t1 ) ∨ A(t2 ) ⊢ A(t1 ), A(t2 ), ∃xA(x)
A(t1 ) ∨ A(t2 ) ⊢ A(t2 ), ∃A(x)
A(t1 ) ∨ A(t2 ) ⊢ ∃A(x)

Ovviamente simmetricamente alla regola (∃, r)′′ possiamo definire la regola del (∀, l)′′ come segue

Γ, A[t/x], ∀xA ⊢ ∆
(∀, l)′′
Γ, ∀xA ⊢ ∆

Le regole (∃, r)′′ e (∀, l)′′ sono reversibili nel senso che vale il seguente Teorema la cui dimostrazione è lasciata
per esercizio e che è una proprietà fondamentale per dimostrare che l’algoritmo di ricerca di una dimostrazione nel
caso proposizionale termina sempre.
Teorema 20

Le regole (∃, r)′′ e (∀, l)′′ sono reversibili. Ovvero la conclusione di ogni regola è valida se e soltanto se la
premessa è valida.

Quindi le regole (∃, r)′′ e (∀, l)′′ sono equivalenti alle regole originali, permettono di risolvere il problema visto
sopra e sono regole reversibili e quindi a prima vista sembrano consentire di ottenere un algoritmo di ricerca di
dimostrazioni nel caso predicativo simlie a quello del caso proposizionale.
Vediamo con un esempio che invece non è cosi. Consideriamo il seguente sequente:

∀xA ⊢ ∀x(A(x) ∨ B)
Osserviamo che tale sequente può essere dimostrato con le regole originali con la seguente dimostrazione:

A(x) ⊢ A(x), B
A(x) ⊢ A(x) ∨ B
(∀, l)
∀xA ⊢ (A(x) ∨ B)
(∀, r)
∀xA ⊢ ∀x(A(x) ∨ B)

61
 Tuttavia l’ordine in cui applichiamo le regole (∀, r) e (∀, l) non può essere invertito perché la variabile x appare
libera. Invece se usiamo la regola (∀, l)′′ , l’odine in cui applichiamo cui regole (∀, r) e (∀, l)′′ può essere invertito.
Tuttavia sorge un ulteriore problema che infine è intrinseco al sistema logico. Per risolvere il ∀xA(x) a sinistra
potremmo dover introdurre una sequenza infinita di formule A(t−i ) Infatti

A(t1 ), A(t2 ), . . . , A(tn ), ∀xA(x) ⊢ A(x), B

··
··
A(t1 ), A(t2 ), ∀xA(x) ⊢ A(x), B
A(t1 ), ∀xA(x) ⊢ A(x) ∨ B
(∀, r)
A(t), ∀xA(x) ⊢ ∀x(A(x) ∨ B)
(∀, l)′′
©Nicola Galesi – Draft

∀xA(x) ⊢ ∀x(A(x) ∨ B)
Dunque se immaginiamo un algoritmo che tenta di risolvere prima il ∀ a sinistra, tale algoritmo, come nell’esempio
precedente potrebbe entrare in un loop infinito che lo porta ad creare sempre un nuovo sequente con una formula in
più ad ogni iterazione. In un ipotetico albero di dimostrazione di un sequente prodotto dall’algoritmo di ricerca di
una dimostrazione questa situazione corrisponde alla creazione di un ramo infinitamente lungo in tale dimostrazione.
Vedremo che tale problema è intrinseco al calcolo dei predicati e vedremo che porta alla semidecidiblità del problema
della decisione nel calcolo dei predicati.

4.4 Completezza e Correttezza del calcolo dei predicati

La dimostrazione del Teorema di Correttezza per il calcolo dei Sequenti predicativo segue le stesse linee del caso
proposizionale e dunque si alscia la sua dimostrazione per esercizio
Teorema 21 (Correttezza Calcolo Sequenti predicativo)

Γ ⊢ ∆ → Γ |= ∆.

Come fatto per il caso proposizionale prima di vedere la completezza vediamo un algoritmo per la ricerca di
dimostrazioni nel caso predicativo

Algorithm 6 Ricerca di dimostrazioni in LK predicativo senza cut

Input: Γ ⊢ ∆
Output: derivazione di Γ ⊢ ∆ oppure NON TERMINAZIONE

1. i = 0 (contatore per decidere se trattare sequente a sinistra o a destra del sequente corrente)
2. Q = {Γ ⊢ ∆}. (Coda dove salvare i sequenti ancora da trattare)
3. FAIL= false (variabile che controlla se un sequente atomico non è uno pseudo assioma)
4. while Q ̸= ∅ oppure FAIL ̸= true
5. Preleva il primo sequente nella coda Q e sia esso Γ∗ ⊢ ∆∗
6. if i mod 2 = 0 Θ ← Γ∗
7. if i mod 2 = 1 Θ ← ∆∗
8. if Θ è un sequente atomico e se Θ non è un pseudo-assioma
9. then FAIL = true
10. else
11. Sia D la formula più a destra in Θ.
12. Risolvi il connettivo principale di D applicando la corrispondente regola
e ottieni i sequenti premessa (o il sequente premessa se la regola è unaria)
di Γ∗ ⊢ ∆∗ . Siano Γ′ ⊢ ∆′ e Γ′′ ⊢ ∆′′ .
13. Aggiungi Γ′ ⊢ ∆′ e Γ′′ ⊢ ∆′′ in coda alla coda Q

62
 Discutiamo con precisione la terminazione del precedente algoritmo.
Osservazione 4 (Terminazione dell’algoritmo di ricerca dimostrazioni)

Ci sono due modi in cui l’algoritmo può terminare

1. La variabile FAIL assume il valore true in qualche momento. Ciò vuol dire che nell’albero di dimostra-
zione siamo arrivati ad avere una foglia quindi un sequente atomico Γf ⊢ ∆f dove però Γf ∩ ∆f = ∅
che significa che non è un pseudo assioma. Dunque in questo caso terminiamo dicendo che il sequente
in input Γ ⊢ ∆ non è derivabile.

2. L’algoritmo può terminare se la coda Q è vuota. Ciò accade solo se tutti sequenti aggiunti nel corso
dell’algoritmo sono stati trattati e hanno portato sempre ad foglie che sono pseudo assiomi. In questo
©Nicola Galesi – Draft

caso l’algoritmo temrina e produce in output una dimostrazione del sequente.

3. Tuttavia l’algoritmo potrebbe non terminare mai, come abbiamo visto nell’esempio precedente, sem-
plicememte perché la coda Q non diventa mai vuota ma tutte le foglie trovate sono sempre pseudo
assiomi. In questo ultimo caso l’algoritmo potrebbe non terminare e produrre un ramo di dimostrazione
infinito.

Infine osserviamo un altro punto che abbiamo accennato nella descrizione dell’algoritmo: Quando trattiamo le
regole del ∀ e dell’∃ come scegliamo le variabili y e i termini t per costruire le premesse delle regole ? useremo la
seguente regola
1. Definiamo un ordine delle variabili y e dei termini t e scegliamo la prima variabile y nell’ordine che va bene per
la regola, ovvero non appare libera nel resto del sequente da trattare.
2. Inoltre ogni volta che risolviamo un quantificatore scegliamo il primo termine (in accordo all’ordine) nella lista
che non è stato ancora utilizzato. Per esempio nella regola

Γ ⊢ ∆, A[x/t], ∃xA(x)
(∃, r)′′
Γ ⊢ ∆, ∃xA(x)

t dovrà essere il primo termine nella enumerazione ordinata dei termini del linguaggio che non è stato ancora
usato.
Vediamo come applicare il predente algoritmo per dimostrare il Teorema di Completezza.
Teorema 22 (Teorema di Completezza)

Γ |= ∆ ⇒ Γ ⊢ ∆

Dimostrazione. (Cenni)
Chiamiamo un albero di dimostrazione per Γ ⊢ ∆ generato dall’algoritmo precedente CHIUSO se tutte le foglie
sono pseudoassiomi, ovvero contengono solo formule atomiche ed es iste una formula che occorre sia nel sequente
premessa che in quello conseguenza. L’albero lo diremo APERTO se invece qualche foglia contiene
1. un sequente atomico Γ′ ⊢ ∆′ dove Γ′ e ∆′ contengono formule differenti; oppure
2. esiste almeno un ramo infinito di sequenti nell’albero.
applichiamo l’algoritmo precedente a Γ ⊢ ∆. Nel primo caso l’algoritmo produce una dimostrazione di Γ ⊢ ∆ e
la dimostrazione del teorema è conclusa.
Dunque per dimostrare il teorema è sufficiente far vedere che se l’albero generato dall’algoritmo non è chiuso,
allora Γ ̸|= ∆. Questo prova completemente il teorema. Per far vedere che nel secondo caso Γ ̸|= ∆ dobbiamo trovare

63
 una interpretazione che soddisfa Γ ma falsifica ∆. Osserviamo che nel secondo caso nell’albero o c’è un cammino che
porta ad un sequente atomico non pseudo assioma oppure esiste un cammino infinito. Sia Sp = {Γ1 ⊢ ∆1 , . . . , Γn ⊢
∆n . . .} l’insieme (possibilmente infinito) dei sequenti che appaiono nel cammino p. Siano S (e rispettivamente D)
l’insieme delle formule atomiche che occorrono nei sequenti Γi in Sp (rispettivamente nei seuqeti ∆i )
Si puo fare vedere che
Proposizione 3. S ∩ D = ∅.
Tale proprietà consente di definire una interpretazione I = (S, α) cosiddetta CANONICA dove come dominio D
def
si sceglie l’insieme dei termini del linguaggio e come ambiente la funzione α(x) = x e definito in questo modo
1. JcK = c per ogni simbolo di costante c
©Nicola Galesi – Draft

2. Jf (t1 , . . . , tn )K = f (Jt1 K, . . . , Jtn K) per ogni simbolo di funzione n-aria f

3. I (P (t1 . . . , tn )) = 1 se e solo se P I (t1 , . . . , tn ) ∈ S, per ogni simbolo di predicato n-ario P

È possibile dimostrare (ma la dimostrazione è tralasciata) che sotto questa interpretazione valgono le seguenti due
proprietà:
1. I |= Γ;
2. I ̸|= ∆.
Abbiamo dunque trovato una interpretazione che soddisfa Γ ma non soddisfa ∆. Il teorema di completezza è dimo-
strato

4.5 Semi-decidibilità del problema delle decisione per la logica dei predicati
Andiamo a vedere cosa permette di concludere il Teorema di Completezza per il problema delle Decisione nel caso
predicativo, ovvero decidere se una data formula è valida oppure no.
Per prima cosa ricordiamo, come già ricordato in precedenza, che decidere per via semantica (come si può fare
nel caso proposizionale testando il valore di una formula sotto tutti gli assegnamenti) se una formula è valida nel caso
predicativo non è possibile finitamente per via del fatto che le interpretazioni sono infinite e per il fatto che i domini
possono essere insiemi infinti.
Al contrario il problema della derivabilità (ovvero decdiere se una formula F è derivabile oppure no) è SEMI -
DECIDIBILE . Ciò significa che possiamo dare un algoritmo (che abbiamo mostrato precedentemente per il calcolo dei
sequenti) che
1. risponde affermitavemnte con una dimostrazione di F nel caso in cui la formula è derivabile. quindi possiamo
sapere se ⊢ F
2. ma che potrebbe non femrarsi mai nel caso in cui ̸⊢ F . Dunque non è mai possibile concludere con sicurezza
che ̸⊢ F
Diremo in questo caso che il problema della dervibalità è SEMI - DECIDIBILE. Grazie la Teorema di Completezza
possiamo concludere che anche il problema delle decisione è semi-decidibile, inffatti la completezza garantisce he
⊢ F se e solo se |= F . Dunque il problema della decisione è almeno semi-decidibile. Ma è è possibile dire qualcosa di
meglio. Possiamo forse dimostrare che lil problema della decisione è decidibile. a tale domanda risponde il Teorema
di Church la cui dimostrazione usa trumenti che esulano da questo corso
Teorema 23 (Church)

Non esiste alcun algoritmo che consente di DECIDERE la validità di una qualunque formula del I ordine.

64
 Capitolo 5

Sistemi refutazionali proposizionali

©Nicola Galesi – Draft

In questo capitolo andremo a trattare sistemi di calcolo proposizionali refutazionali. La principale differenza rispetto
ai sistemi deduttivi come i sistemi assiomatici o il calcolo dei sequenti consiste consite nel fatto che in un sistema
refutazionale, invece di produrre una derivazione della formula (tautologica) che si vuole dedurre, si deduce un falsità
elementare a partire da alcuni assiomi che corrispondono alla negazione della tautologia (ovvero una formula insoddi-
facibile). Consideriamo il seguente esempio. Il principio della piccionaia PHPn+1
n è codificato dalla seguente formula
(si veda il Capitolo 11)
def
^ _ _
PHPn+1
n = pi,j → (pi1 ,j ∧ pi2 ,j )
i∈[n+1] j∈[n] i1 ,i2 ∈[n+1],i1 ̸=i2

PHPn+1
n è una tautologia, dunque ¬ PHPnn+1 è una formula insoddisfacibile. Osserviamo che
^ _ _
PHPn+1n = ¬( pi,j ) ∨ (pi1 ,j ∧ pi2 ,j )
i∈[n+1] j∈[n] i1 ,i2 ∈[n+1],i1 ̸=i2

e dunque ¬ PHPn+1
n è la formula:
^ _ ^
¬ PHPn+1
n = pi,j ∧ (¬pi1 ,j ∨ ¬pi2 ,j )
i∈[n+1] j∈[n] i1 ,i2 ∈[n+1],i1 ̸=i2

Dunque ¬ PHPn+1n è una formula CNF.

Una derivazione in un sistema refutazionale che lavora solo su clausole usa come assiomi le clausole che defini-
scono la negazione della formula da derivare e applicanod una regola logica appropriata tenta did derivare una falsità
in forma semplice in forma di clausole, per esempio la clausola vuota □.

5.1 Risoluzione
La R ISOLUZIONE è un calcolo proposizionale refutazionale che lavoro solo su clausole e quindi per formule in CNF.
La risoluzione è basta su un’unica regola, la regola di Risoluzione

5.1.1 Proprietà generali

5.1.2 Correttezza e Completezza della Risoluzione
5.1.3 Ricerca automatica di refutazioni in Risoluzione e problema SAT
5.1.4 Programmazione Logica

65
 Capitolo 6

Il problema P versus NP e la complessità

©Nicola Galesi – Draft

delle dimostrazioni

6.1 Algoritmi deterministici e non-deterministici: Macchine di Turing

Una M ACCHINA DI T URING (TM) è un dispositivo ideale composto

1. da un nastro infinito formato da infinite celle adiacenti su cui possono essere scritti dei simboli di un alfabeto
(tipicamente 0 e 1.)
2. una testina di lettura/scrittura che si muove sul nastro da una cella ad una delle due celle adiacenti e che consente
di scrivere nella cella puntata dalla testina un carattere dell’alfabeto oppure di leggere il carattere presente nella
cella puntata dalla testina.

3. Una memoria finita definita da uno stato che appartiene a un insieme finito di stati nei quali la TM si può
trovare.
Una TM opera, nel seguente modo:
(Funzionamento di TM)

In funzione del simbolo a letto nella cella puntata dalla testina di lettura/scrittura e dello stato q in cui la TM
si trova, la TM orper come segue:

1. Scrive un nuovo simbolo nella cella puntata dalla testina;

2. cambia la stato in cui si trova (o rimane nello stesso stato);
3. esegue un movimento della testina a destra o a sinistra della cella puntata e punta a una nuova cella.
Per capire quando inizia e quando termina una computazione,

1. la TM capirà di avere finito una computazione quando entra in uno degli stati speciali detti stati di
terminazione. In quel caso la computazione termina.
2. All’inizio della computazione la TM si troverà in uno stato speciale detto stato iniziale

Per formalizzare attraverso una struttura matematica una TM e il suo funzionamento procediamo come segue. Ci
dotiamo di

1. Un alfabeto Σ, tipicamente Σ = {0, 1};

66
 2. un insieme finito di stati Q = {q0 , . . . , qn } di cui fanno parte tre stati speciali: q0 detto stato iniziale, qY uno
stato finale di accettazione dell’input e qN uno stato finale di rifiuto dell’input.
3. Una funzione di transizione δ che modella il funzionamento della TM quindi δ : Q × Σ −→ Q × Σ × {L, R}
dove {L, R} indica un movimento a sinistra L (rispettivamente a destra R ) della testina della TM in quella
transizione, anche detto passo singolo di computazione della TM. Dunque ad esempio con l’espressione

δ(q, a) = (p, b, R)

si intende che se la TM si trova nello stato q e la testina punta ad una cella contenente il simbolo a, la TM si
porta nello stato p, scrive il carattere b nella cella correntemente puntata e muove la testina di letture/scrittura
a destra di una cella.
©Nicola Galesi – Draft

A volte la TM può usare dei simboli di nastro in più rispetto all’alfabeto Σ, che è l’alfabeto su cui è codificato
l’input. Per esempio nelle celle di nastro tipicamente per comodità usiamo dei simboli di separazione come # o
simboli di cella vuota come □. Quindi in una definizione di TM tipicamente usiamo anche un altro alfabeto Γ, detto
alfabeto di nastro, che include tutti i simboli che possiamo scrivere sul nastro, incluso l’input. Quindi Σ ⊆ Γ. 1 .
Definizione 48 (Macchina di Turing)

Una macchina di Turing è una tupla del tipo

(Σ, Γ, Q, δ, q0 , qy , qn )

dove
1. Σ è l’alfabeto di input;
2. Γ è l’alfabeto di nastro con Σ ⊆ Γ
3. Q è un insieme finito di stati

4. δ : Q × Σ −→ Q × Σ × {L, R} è la funzione di transizione

5. q0 ∈ Q è lo stato iniziale
6. qY , qN ∈ Q sono gli stati finali di accettazione e rifiuto.

Definizione 49 (Computazione di una TM decisore di linguaggi)

Una TM computa su una data stringa di input ω ∈ Σ∗ nel seguente modo

1. Inizialmente l’input ω è contenuto sul nastro della TM, la testina è posizionata sul simbolo più a sinistra
dell’input e la TM si trova nello stato q0 .
2. La TM applica la funzione di transizione δ mentre è possibile
3. Quando lo stato raggiunto è qy la TM si ferma è accetta l’input. Quando lo stato raggiunto è qn la TM
si ferma è rifiuta l’input.

Diamo una serie di osservazioni importanti. Iniziamo con la definizione di configurazione

1 Ovviamente tutti i simboli in Γ possono essere codificati in binario e dunque in definitiva possamo sempre e solo considerare l’alfabeto {0, 1}

67
 Definizione 50 (Configurazione)

Una configurazione di una computazione di una TM è una stringa Ct che descrive la computazione in un dato
istante t della computazione. Ct deve contenere le seguenti informazioni
1. il contenuto del nastro all’istante t, questa sarà una stringa in Γ∗ , ovvero sull’alfabeto di nastro.

2. lo stato q in cui si trova M all’istante t

3. la cella puntata dalla testina di lettura
Per codificare lo stato e la posizione della
©Nicola Galesi – Draft

1. L’insieme delle stringhe accettate da una TM M è il il linguaggio accettato da M ed è denotato come L(M ).
Si osservi che un linguaggio è un sottoinsieme delle stringhe definite su Σ∗ . Per tanto possiamo definire

L(M ) = {ω ∈ Σ∗ | M accetta ω}

2. la definizione di TM cha abbiamo dato è quella di TM DETERMINISTICA. Ovvero: ogni passo di computazione
e determinsiticamente definito dalla CONFIGURAZIONE corrente.

6.2 Le classi P e NP
6.3 SAT e NP-completezza
6.4 Importanza matematica e filosofica del problema P vs NP
6.5 Complessità delle dimostrazioni logiche come approccio al problema P
vs NP: Teorema di Cook-Reckhow

68
 Capitolo 7

Cenni sui Teoremi di Gödel

©Nicola Galesi – Draft

69
 Capitolo 8

Esercizi
©Nicola Galesi – Draft

8.1 Esercizi su logica proposizionale

Esercizio 7

Eliminare quando è possibile le parentesi dalle seguenti formule

1. ((A ∧ B) → (¬C)).
2. (A → (B → (¬C)).
3. ((A ∧ B) ∨ (C → D))

Esercizio 8

Dimostrare che ogni FBF contiene lo stesso numero di parentesi chiuse e aperte

Esercizio 9

Usando le Tavole di Verità dire quali delle seguenti formule sono tautologie e quali insoddisfacibili e quali soddisfacibili
1. ¬(A → ¬A)
2. ¬A → A
3. ⊥ → A
4. A ∨ B → A ∧ B
5. A → (B → C)) → ((A → B) → (A → C))

Esercizio 10

Il seguente insiem di FBF è soddisfacibile ?. Dimostrare la risposta

{p1 ∨ p2 , ¬p2 ∨ ¬p3 , p3 ∨ p4 , ¬p4 ∨ p5 }

Esercizio 11

Dimostrare che B ∨ C ∈ SAT se e soltanto se (B ∨ A) ∧ (C ∨ ¬A) ∈ SAT

70
 Esercizio 12

Sono equivalenti le due proposizioni ?

1. A |= B,
2. Se |= A allora |= B.

Esercizio 13

Dimostrare formalizzando in formule proposizionali che la asserzione "Lucia è spagnola" segue dalle seguenti ipotesi:
1. "Se Carlo è americano e Giovanni non è francese, allora Elena è tedesca",
2. "Se Elena è tedesca, allora Lucia è spagnola oppure Giovanni è francese ",
©Nicola Galesi – Draft

3. "Se Lucia non è spagnola, allora Carlo è americano",

4. "Giovanni non è francese".

Esercizio 14

Trovare le CNF e DNF delle seguenti formule:

1. (A → B) → (B → ¬C),
2. ¬(A ↔ B)
3. ¬(A ∧ B ∧ (C → D))

Esercizio 15 (Difficile)

Formalizzare in una formula proposizionale Cliquek (G) l’asserzione che un grafo G = (V, E) contiene una k-CLIQUE.
Dare esempi di grafi sui quali la formula è soddisfacibile e esempi di grafi sui quali è insoddisfacibile e dimostrarlo. Si
ricorda che un grafo G forma una k-CLIQUE se esistono k vertici distinti v1 , . . . , vk in V tale che (vi , vj ) ∈ E per ogni
i, j ∈ {1, . . . , k} con i ̸= j.

71
 8.2 Esercizi su Calcolo proposizionale
Esercizio 16

Dimostrare che la regola di riduzione all’assurdo ("Se ⊢ (¬A → ⊥) allora ⊢ A") è equivalente alla regola ¬¬A ⊢ A

Esercizio 17

Dimostrare che le seguenti formule sono derivabili in un un sistema deduttivo proposizionale

1. A ∧ B → A ∨ B.
2. A ∧ (B ∧ C) → (A ∧ B) ∧ C.
©Nicola Galesi – Draft

3. ¬(A ∧ ¬A)

Esercizio 18

Si considerino le seguenti proposizioni

1. Se Franca è una elettricista, allora Giorgio è un idraulico oppure Elena è un’insegnante
2. Se Giorgio è un idraulico allora Lucia non fa la giornalista oppure Elena è un’insegnante
3. Se Lucia fa la giornalista, allora Franca è una elettricista
4. Lucia fa la commessa
5. Elena è un’isegnante
Dimostrare che (1),(2),(3),(4) ⊢ (5) nel calcolo dei sequenti

Esercizio 19

Si consideri le seguente definizione.

Definizione 51

Un insieme di proposizioni Γ è consistente se Γ ̸⊢ ⊥; È inconsistente se non è consistente, ovvero se Γ ⊢ ⊥.

Dimostrare che le seguenti tre proprietà sono equivalenti

1. Γ è inconsistente
2. Esiste una proposizione P tale che Γ ⊢ P e Γ ⊢ ¬P
3. Per ogni proposizione P , Γ ⊢ P

Esercizio 20

Dimostrare che se un insieme di formule Γ è soddisfacibile, allora è consistente. Stabilire quali dei seguenti insiemi sono
consistenti
1. {A → B, C → D, D → E, E → ¬A},
2. {A ∨ B → C, A, B → ¬C, B},
3. {A ∨ B → C, A, B → ¬C, C},

72
 8.3 Esercizi su logica predicativa
Esercizio 21

Formalizzare in un linguaggio del primo ordine che formalizza proposizione su grafi le seguente asserzioni
1. Esiste un vertice isolato,
2. i vertici sono tutti connessi tra loro,
3. non esistono archi tra un vertici e se stesso

Esercizio 22

In un linguaggio predicativo per la geometrica dove il predicato P (x) formalizza che x è un punto, R(x) formalizza che
©Nicola Galesi – Draft

x è una retta, L(x, y) che x giace su y, C(x, y, z) che x, y, z sono collineari e I(x, y) che x = y dire a che asserzione
corrispondono le seguenti formule
1. ∀x(P (x) → ¬R(x))
2. ∀x∀y(L(x, y) → (P (x) ∧ R(y))
e formalizzare in formule le seguenti asserzioni
1. Tre punti collineari giacciono sulla stessa retta,
2. rette e punti non sono mai uguali,
3. per due punti distinti passa una e una sola retta.

Esercizio 23

Formalizzare in formule del linguaggio predicativo le seguenti asserzioni in linguaggio naturale:

1. Qualche genio è scapolo,
2. qualche studente non è scapolo
3. qualche studente non è un genio
4. Qualche uomo è un genio. Nessuna scimmia è un uomo, dunque qualche scimmia non è un genio
5. Qualche uomo è un genio, Nessuna scimmia è un uomo, dunque nessuna scimmia è un genio.

Esercizio 24

Formalizzare in formule del linguaggio predicativo le seguenti asserzioni in linguaggio naturale:

1. Nessuno studente di Matematica è più intelligente di tutti gli studenti di Filosofia,
2. Dunque qualche studente di Filosofia è più intelligente di ogni studente di Matematica

Esercizio 25

Formalizzare le proposizioni seguenti con enunciati nel linguaggio predicativo composto da un solo simbolo ∈ (x, y) di
relazione binaria il cui significato intuitivo è x ∈ y. Per esempio in questo linguaggio, "Esiste l’insieme vuoto" si esprime
con l’enunciato ∃x∀y¬(y ∈ x) (esiste un insieme, x tale che nessun y è elemento di x).
1. Ogni insieme x sottoinsieme di un qualche insieme y.
2. Per ogni insieme x esiste l’insieme y complemento di x.
3. Per ogni coppia di insiemi x e y esiste l’insieme intersezione x ∩ y,
4. Esiste un insieme che è sottoinsieme di tutti gli insiemi.

73
 8.3.1 Esercizi su semantica, verità, modelli
Esercizio 26

Stabilire il valore di verità delle formule:

1. ∀x(E(x) ∨ O(x))
2. ∃x(E(x) ∨ O(x))
3. ∀x(E(x) ∧ O(x))
4. ∀x(E(x) → O(x))
nel modello in cui il dominio è l’insieme dei numeri interi e i predicati E e O sono interpretati com predicati unari tali che
con E(x) si intende "x è pari" e con O(x) si intende "x è dispari.
©Nicola Galesi – Draft

Esercizio 27

Stabilire il valore di verità delle formule:

1. ∀x(E(x) → ∀yG(x, y))
2. ∃x∀yG(x, y))
3. ∀x(E(x) → ∀yG(x, y)
4. ∀y∃xG(x, y))
nel modello in cui il dominio è l’insieme dei numeri interi e i predicati E e G sono interpretati come la classe degli interi
pari e G(x, y) la relazione "x ≥ y.

Esercizio 28

Stabilire il valore di verità delle formule:

1. ∀x∀y∀z(B(x, y, z) → B(y, x, z))
2. ∀x∃y(B(x, x, z) → B(y, x, z))
3. ∀x∃yA(x, y) → ∀x¬B(x, x, c)
4. ∀x∃y¬A(x, y) → ∃y¬A(y, c)
nel modello in cui il dominio è l’insieme dei numeri naturali, A(x, y) è interpretato come il predicato "x ≥ y, c è una
costante, e B(x, y, z) interpretato come x + y = z.

Esercizio 29

Stabilire il valore di verità delle formule:

1. ∀x∀y∀z(B(x, y, z) → B(y, x, z))
2. ∀x∃y(B(x, x, z) → B(y, x, z))
3. ∀x∃yA(x, y) → ∀x¬B(x, x, c)
4. ∀x∃y¬A(x, y) → ∃y¬A(y, c)
nel modello in cui il dominio è l’insieme dei numeri naturali, A(x, y) è interpretato come il predicato "x ≥ y", c è una
costante, e B(x, y, z) interpretato come x + y = z.

74
 8.3.2 Esercizi su semantica e forme normali
Esercizio 30

Stabilire quali delle seguenti formule sono valide e quali semplicemente soddisfacibili. Nel seconodo caso fornire un
esempio di interpretazione che non ne é un modello.
1. (∃xA(x) → ∀xB(x)) → ∀x(A(x) → B(x)).
2. (∃xA(x) → ∃xB(x)) → ∀x(A(x) → B(x)).
3. (∃xA(x) → ∃xB(x)) → ∃x(A(x) → B(x)).
4. ∃x(A(x) → B(x)) → (∀xA(x) → ∀xB(x)).
5. ∃x(A(x) → B(x)) → (∀xA(x) → ∃xB(x)).
6. ∃x(A(x) → B(x)) → (∃xA(x) → ∃xB(x)).
©Nicola Galesi – Draft

7. ∀x(A(x) → B(x)) → (∃xA(x) → ∀xB(x)).

8. ∀x(A(x) → B(x)) → (∀xA(x) → ∀xB(x)).
9. (∀xA(x) → ∀xB(x)) → ∀x(A(x) → B(x)).
10. (∀xA(x) → ∃xB(x)) → ∃x(A(x) → B(x)).
11. (∀xA(x) → ∃xB(x)) → ∀x(A(x) → B(x)).

Esercizio 31

Quali delle seguenti formule sono valide ?

1. ∃xA(x) → ∀xA(x)
2. ∀xA(x) → ∃xA(x)
3. ∀x∃yA(x, y) → ∃x∀yA(x, y)
4. ∃x∀yA(x, y) → ∀x∃yA(x, y)
5. ∃x∀yA(x, y) → ∃x∀yA(x, y)

Esercizio 32

Data la formula della logica dei predicati con uguaglianza

∀p∀q((A(p, q) ∧ p ̸= a) → ∃xy(f (x, y) = f (p, q) ∧ g(x, y) = p))

stabilire se è soddisfatta nelle seguenti interpretazioni

1. (U, α) dove DU = {1, 3, 5, 7, 9, · · · }, aU = 19, f U = (x, y) 7→ xy , g U = (x, y) 7→ x · y e AU = {(n, m) | n ≤
m}.
2. (U, α) dove DU = N, aU = 1, f U = (x, y) 7→ x + y, g U = (x, y) 7→ x · y e AU = {(n, m) | n ≤ m}.
3. (U, α) dove DU = R, aU = 0, f U = (x, y) 7→ x + y, g U = (x, y) 7→ x · y e AU = {(n, m) | n ≥ m}.

75
 Esercizio 33

Trasformare in forma di Skolem le seguenti FBF

1. ∀y(∃xA(x, y) → B(y, x)) ∧ ∃y(∀xC(x, y) ∨ B(x, y)).
2. ∃x∀y∃zD(x, y, z) ∨ ∃x∀yA(x, y) ∧ ¬∃x∃yB(x, y).
3. ¬(∀x∃yA(x, y) → ∃x∃yB(x, y)) ∧ ∀x¬∃yB(y, x)

Soluzione

Esercizio 2
∃x∀y∃zD(x, y, z) ∨ ∃x∀yA(x, y) ∧ ¬∃x∃yB(x, y)
©Nicola Galesi – Draft

∃x∀y∃zD(x, y, z) ∨ (∃x∀yA(x, y) ∧ ¬∃x∃yB(x, y)) parentesi

∃x∀y∃zD(x, y, z) ∨ (∃x∀yA(x, y) ∧ ∀x∀y¬B(x, y)) regola ¬
∃x∀y∃zD(x, y, z) ∨ ∃x∀z(∀yA(x, y) ∧ ∀y¬B(z, y)) Teo 16
∃x∀y∃zD(x, y, z) ∨ ∃x∀z∀y∀t(A(x, y) ∧ ¬B(z, t)) Teo 16
∃x∃x1 (∀y∃zD(x, y, z) ∨ ∀z∀y∀t(A(x1 , y) ∧ ¬B(z, t))) Teo 16, x1 ̸∈ F V
∃x∃x1 (∀y∃zD(x, y, z) ∨ ∀z1 ∀y1 ∀t(A(x1 , y1 ) ∧ ¬B(z1 , t))) sost. varabili
∃x∃x1 ∀y∀z1 (∃zD(x, y, z) ∨ ∀y1 ∀t(A(x1 , y1 ) ∧ ¬B(z1 , t))) Teo 16
∃x∃x1 ∀y∀z1 ∃z∀y1 (D(x, y, z) ∨ ∀t(A(x1 , y1 ) ∧ ¬B(z1 , t))) Teo 16
∃x∃x1 ∀y∀z1 ∃z∀y1 ∀t(D(x, y, z) ∨ (A(x1 , y1 ) ∧ ¬B(z1 , t))) Teo 15, t ̸∈ F V (D(x, y, z))
Adesso poniamo x = c, x1 = c1 e z = f (y, z1 ), e otteniamo

∀y∀z1 ∀y1 ∀t(D(c, y, f (y, z1 ) ∨ (A(c1 , y1 ) ∧ ¬B(z1 , t)))

Esercizio 3
¬(∀x∃yA(x, y) → ∃x∃yB(x, y)) ∧ ∀x¬∃yB(y, x)
¬(¬∀x∃yA(x, y) ∨ ∃x∃yB(x, y)) ∧ ∀x¬∃yB(y, x) A → B ≡ ¬A ∨ B
(∀x∃yA(x, y) ∧ ¬∃x∃yB(x, y))) ∧ ∀x¬∃yB(y, x) De Morgan
(∀x∀x1 (∃yA(x, y) ∧ ∀y¬B(x1 , y))) ∧ ∀x∀y¬B(y, x) Teo 16
∀x∀x1 ∃y∀y1 (A(x, y) ∧ ¬B(x1 , y1 )) ∧ ∀x∀y¬B(y, x) Teo 16
∀x∀x1 ∃y∀y1 (A(x, y) ∧ ¬B(x1 , y1 )) ∧ ∀x2 ∀y2 ¬B(y2 , x1 ) sost. variabili
∀x∀x1 ∃y∀y1 ∀x2 ∀y2 ((A(x, y) ∧ ¬B(x1 , y1 )) ∧ ¬B(y2 , x1 )) Teo 15
Basta porre y = f (x, x1 ) e otteniamo
∀x∀x1 ∀y1 ∀x2 ∀y2 ((A(x, f (x, x1 )) ∧ ¬B(x1 , y1 )) ∧ ¬B(y2 , x1 ))

76
 8.4 Esercizi su Calcolo dei Predicati
Esercizio 34

Un Gruppo è una struttura matematica formata da un insieme X e un operazione ⋆ su elementi di X che verifica alcune
proprietà:
1. associatività di ⋆: ovvero a ⋆ (b ⋆ c) = (a ⋆ b) ⋆ c per ogni a, b, c ∈ X
2. esistenza dell’elemento neutro: ovvero esiste un elemento e ∈ X tale che a ⋆ e = e ⋆ e = a per ogni a ∈ X
3. esistenza dell’inverso: ovvero per ogni a ∈ X esiste un elemento in X (denotato con a−1 ) tale che a ⋆ a−1 =
a−1 ⋆ a = e
Infine il grupo viene detto A BELIANO se ⋆ verifica anche la proprietà commutativa. ovvero
©Nicola Galesi – Draft

a ⋆ b = b ⋆ a per ogni a, b ∈ X

Definire degli assiomi che definiscono un linguaggio del primo ordine con uguaglianza per catturare il concetto formale di
gruppo

Esercizio 35
def
Sia F (x) una FBF dove x appare libera e sia F (a) = F [a/x]. Dimostrare che il sequente

(¬F (a) ∨ ∃xF (x)), ∃xF (x) → P ⊢ F (a) → P

è valido.

Esercizio 36

Dimostrare nel calcolo dei predicati la validità del seguente ragionamento

1. Tutti gli uomini sono mortali
2. Socrate è un uomo
3. Dunque Socrate è mortale

Esercizio 37
def
Sia F (x) una FBF dove x appare libera e sia F (a) = F [a/x]. Dimostrare il sequente

¬F (a) ⊢ ¬∀xF (x)

Esercizio 38

Dimostrare la validità del seguente ragionamento

1. Tutti i pesci sono furbi
2. Tutte le sardine sono pesci
3. Tutte le sardine sono furbe

Esercizio 39

Dimostrare il sequente:
∀x(F (x) → G(x)), ∀x(G(x) → H(x)) ⊢ ∀x(F (x) → H(x))

77
 Esercizio 40

Dimostrare il sequente:
∀x(F (x) → G(x) ∨ H(x)), ∀x¬G(x) ⊢ ∀xF (x) → ∀xH(x)
©Nicola Galesi – Draft

78
 8.5 Esercizi di Ricapitolazione
Esercizio 41
Dire se le seguenti formule sono valide o meno e giustificare la risposta, ovvero fornire una intrpretziome che
le falsifica oppure provarne la validità (ma non con dimostrazione nel calcolo dei sequenti)
1. ∀x∃yA(x, y) → ∃y∀xA(x, y)
2. ∀x∀y(A(x, y) → A(y, x))

Esercizio 42
©Nicola Galesi – Draft

Definire un linguaggio e formalizzare in formule del I ordine le seguenti asserzioni prima usando solo
quantifcatori esistenziali e poi usando solo quantificatori universali
1. Tutti gli uccelli volano

2. Nessun uomo è un isola

3. Alcuni numeri non sono razionali

Esercizio 43
def def def
Si consideri il seguente linguaggio del primo ordine a = 0, A(x, y) = x = y,f1 (x) = S(x) (S(x) è la
def
funzione successore, ovvero S(x) = x + 1), f2 (x, y) = x + y, f3 (x, y) = x · y. Trovare, dove possibile
interpretazioni che soddisfano e interpretazioni che non soddisfano le seguenti formule

1. A(f2 (x, y), f3 (x, y))

2. A(f2 (x, a), y) → A(f2 (x, y), z)
3. ∀xA(f3 (x, y), z)

Esercizio 44 (* Difficile)

Sia A(x) una formula del primo ordine in cui x appare libera e sia t un termine che è libero per x in A(x)
(ovvero in cui x non occorre libera nell campo di azione di un quantificatore ∀y con y un variabile in t.
Supponiamo che α è un ambiente tale che α(x) = JtK. Dimostrare che α soddisfa A(x) se e solo se α soddisfa
A(x)[x/t]

Esercizio 45 (* Difficile)

Si consideri il linguaggio della dell’aritmetica di Peano. Scrivere formule in tale linguaggio che formalizzano
le seguenti asserzioni
1. m, n ∈ N non hanno fattori comuni
2. n non è un numero primo

3. m = min(p, q)

79
 Esercizio 46

Sia f : [n] −→ [n + 1], n ∈ N una mappa. Formalizzare i seguenti enunciati su f , per n = 3, usando il
linguaggio proposizionale composto da variabili xi,j per i ∈ {1, 2, 3} e j ∈ {1, 2, 3, 4} dove xi,j = 1 se e
solo se f (i) = j

1. f è la funzione costante con dominio {1, 2, 3} e valore 4.

2. f è una relazione funzionale (i.e., una funzione) con dominio {1, 2, 3} e immagine contenuta in
{1, 2, 3, 4}.
3. f è una funzione suriettiva con dominio contenuto in {1, 2, 3} e codominio {1, 2, 3, 4}.
©Nicola Galesi – Draft

4. f è una funzione iniettiva con dominio {1, 2, 3} e codominio {1, 2, 3, 4}.

Esercizio 47
Formalizzare i seguenti enunciati usando il linguaggio proposizionale composto da variabili ai e bi con i ∈
{1, 2, 3, 4} con significato intuitivo i ∈ A e i ∈ B, rispettivamente.

1. A è un sottoinsieme non vuoto di {1, 2, 3, 4}.

2. A e B sono sottoinsiemi non vuoti di {1, 2, 3, 4} tali che A ∩ B = ∅.
3. A e B sono sottoinsiemi non vuoti di {1, 2, 3, 4}. tali che A ∪ B = {1, 2, 3, 4}.

4. A e B sono sottoinsiemi non vuoti di {1, 2, 3, 4}. tali che A ⊆ B e A ̸= B.

Esercizio 48
Trasformare in forma normale prenessa le seguenti formule

1. A(x) → ∀yA(x, y)
2. (∀xA(x, y) → ¬∃yA(y)) → ∀x∀yB(x, y)

Esercizio 49
Vero o Falso?
1. ((p1 → p2 ) ∧ (¬p3 → ¬p2 ) ∧ (p1 ∧ ¬p3 )) ∈ UNSAT;
2. Se ¬A è una tautologia allora A ∨ (A → C) è una tautologia;

3. Se A non è insoddisfacibile allora esiste un B soddisfacibile tale che B |= A e A ̸|= B.

80
 Esercizio 50

Consideriamo il linguaggio composto da una costante c, da un simbolo di relazione a due posti S(x, y) e da un
simbolo di relazione a tre posti R(x, y, z). Per ognuno degli enunciati seguenti descrivere una interpretazione
in cui l’enunciato è vero e una in cui è falso.
1. ∀x∃y∀z(S(x, c) → R(x, y, z)).
2. ∃y∀x∀z(S(x, c) → R(x, y, z)).

3. ∀x∀y(S(x, y) → S(y, x)).

©Nicola Galesi – Draft

Esercizio 51
Si considerino i seguenti due nuovi connettivi proposizionali ⊙ e ⊖ definiti rispettivamente da x ⊙ y = 1 se
e solo se x = 0 ∧ y = 0 e x ⊖ y = 0 se e solo se x = 1 ∧ y = 1 Dimostrare che le due basi B1 = {⊙} e
B2 = {⊖} sono complete (usare i simboli di verità ⊤ e ⊥ e le leggi logiche associate.)

81
 ©Nicola Galesi – Draft

Bibliografia

82