CAPITOLO 7 LOGICA CLASSICA DEI PREDICATI: SEMANTICA 1

CAPITOLO 7
LOGICA CLASSICA DEI PREDICATI: SEMANTICA
1. Verso la logica del primo ordine: funzioni proposizionali e
quantificatori
L’ analisi ”Booleana” del linguaggio che ha condotto alla formalizzazione della logica
proposizionale studia la nozione di conseguenza logica e la nozione di deduzione solo in
riferimento ai connettivi logici proposizionali. Un’ argomentazione valida quale quella
della forma di un sillogismo di forma barbara:
– (1. premessa) Ogni a `e b,
– (2. premessa) ogni b `e c,
– (conclusione) ogni a `e c
non si puo’ analizzare in termini proposizionali: le tre proposizioni si possono presentare come ”atomi” proposizionali, (nessuna di loro contiene esplicitamente dei connettivi) e la logica proposizionale non si applica. Oppure , si pensi all’ altrettanto valida
argomentazione:
–(premessa) Ogni a `e sia b che c;
–(conclusione) Ogni a `e b.
Una piu’ completa analisi logica del linguaggio, dovuta tra gli altri a G. Frege,
B.Russell, G. Peano ci aveva portato gia’ nel capitolo 2 ad individuare le due nozioni
basilari di
–funzione proposizionale e di
–quantificazione
mediante le quali, portate ad un certo livello di astrazione, si formula la logica dei
predicati. la restrizione principale che faremo e’ sull’ applicare i quantifictori solo ad un
livello (e si parla di logica del ( primo) ordine).
Nel seguito, specificheremo in modo preciso sia la nozione di ”dominio” per le variabili
(struttura), che quella di ”espressione denotante” (termine) che quella di ” funzione
proposizionale ” (formula).
2. Strutture del primo ordine
L ’idea e’ quella di avere un insieme in cui si diano certe operazioni e certe relazioni,
ed eventualmente certi elementi come privilegiati. Per descrivere la struttura conviene
intanto individuare quante sono le operazioni e per ciascuna di loro su quanti argomenti
opera (la sua ” ariet´a”: se sia unaria, ternaria, etc.); e similmente per le relazioni.
1
2
CAPITOLO 7
Una segnatura o tipo di strutture e’ dato da una quaterna τ =< R, F, C, ar > in cui
R, F, C sono insiemi a due a due disgiunti ed ar e’ una funzione da R∪F verso l’ insieme
ω dei numeri naturali. Per n ∈ ω, porremo:
Rn = {R ∈ R|ar(R) = n};
Fn = {f ∈ R|ar(f ) = n}.
Gli elementi di R, F, C si chiamano rispettivamente segni di predicato (o relazione), segni
di funzione, segni di costante; la funzione ar d’`a l’ariet`
a del segno su cui si applica: se
il valore e’ n, si parla di segno di arieta’ n o n−ario (n = 0, 1, 2, ..., danno segni zeroari,
unari, binari,.... ).
Tali segni astratti diventeranno dotati di significato una volta considerata la seguente
nozione Una struttura A della segnatura τ , o una realizzazione di τ, e’ costituita da:
(1) un insieme non vuoto A (sostegno o insieme base) della struttura;
(2) per ciascun R ∈ R, una relazione n–aria in A, cioe’ un sottinsieme RA ⊆ An ,
detta la realizzazione del segno R in A;
(3) per ciascun f ∈ F , una operazione n–aria in A, cioe’ una funzione fA da An
verso A detta la realizzazione del segno f in A;
(4) per ciascun c ∈ C, un elemento cA in A detto la realizzazione del segno c in A.
Si user`a sistematicamente la stessa lettera per la struttura (in corsivo A) e per il suo
insieme base (in stampatello A).
Questa nozione copre molti dominii di studio e situazioni trattate in matematica. Le
strutture algebriche (gruppi, anelli, campi, campi ordinati, spazi vettoriali, ...) o i tipi
di dati piu’ comuni si possono presentare come realizzazioni di opportune segnature. Il
campo dei reali o quello dei complessi, con tutte le operazioni e relazioni che si vogliano,
possono essere presentati in tal modo. La stessa teoria degli insiemi si presenta come
riferita a domini del primo ordine con una relazione binaria per l’ appartenenza. (Tuttavia, la nozione di spazio topologico, non ha una presentazione naturale come struttura
del primo ordine, sopratutto se sia formulata in modo da esprimere gli assiomi sia sui
punti che sugli insiemi di punti: avremo allora variabili e quantificatoti sia per individui
che per insiemi di individui, ossia una tipica situazione di secondo ordine.)
Ma anche in altri settori, gli oggetti di studio si possono presentare come ”strutturati”
secondo tale nozione. Per esempio, alcune parti dello studio delle parentele potrebbero
essere presentate come strutture sull’ insieme degli esseri umani U , con le relazioni e
funzioni che interessano , quali p, segno di funzione unaria per ”il padre di...”, o F G,
segno di relazione binaria per ”— e’ figlio di ...”, o altre
In particolare in matematica, ma e’ utile in generale, conviene avere sempre disponibile
un segno di relazione binaria per l’ uguaglianza; porremo allora la seguente
Convenzione: in qualunque segnatura e’ sempre presente un segno di relazione bi.
.
naria per l’uguaglianza =∈ R2 ; in qualunque struttura A la realizzazione di = e’ la
.
relazione identica (=)A = {< a, a > |a ∈ A}. Gli altri segni della segnatura si chiamano a volta i segni proprii di τ. Quando si specifica una segnatura, non indichiamo
CAPITOLO 7
3
.
esplicitamente la presenza di =∈ R ma indichiamo solo i segni proprii di relazione.
NOTA
Come trattare le realizzazioni dei segni in R0 , se ve ne sono? Una relazione zeroaria in un
insieme A e’ per definizione un sottinsieme di A0 , ossia di A∅ ; vi sono esattamente due tali
sottinsiemi: ∅ = 0 e {∅} = 1. In altre parole la realizzazione in una struttura di un segno di
relazione zeroario e’ (assimilabile a) un valore di verita’; pertanto un segno di relazione zeroaria
si puo’ trattare come (se fosse) una variabile proposizionale.
Come trattare le realizzazioni dei segni in F0 , se ve ne sono? Una operazione zeroaria in un
insieme A e’ una funzione da A0 = {∅} verso A, quindi essa non fa che scegliere un elemento
di A; i segni di funzione zeroaria, quindi sono (un modo diverso per avere) segni di costante.
Come trattare le operazioni parziali che possono interessare in una struttura? Per esse,
nella nostra definizione, non abbiamo provveduto a fornirci di segni nella segnatura: si possono
trattare come relazioni, ossia si considera la relazione che e’ il grafico delle oprerazione parziale;
per questa possiamo ben prevedere un segno in R.
Naturalmente, si potrebbe far lo stesso anche per le operazioni totali, n– arie, che sono
attualmente le realizzazioni dei segni in F, trattandole come relazioni n + 1–arie; tuttavia
certamente si perderebbe in immediatezza di espressione, ed e’ ormai tradizionale ammettere
segni per operazioni fin dall’ inizio.
ESEMPI.
1. Se F = C = ∅, si parla di strutture puramente relazionali. Per esempio , i poset
< A, ≤A > sono di una segnatura puramente relazionale, con un sol segno di relazione,
binaria ( ar(≤) = 2).
2. Se R = ∅ si parla di segnatura algebrica nel senso dell’ algebra universale.
3. In una segnatura con R = {R, T }, F = {f, g, h}C = {c}, ar(R) = 3, a(T ) =
2, ar(f ) = ar(g) = 2, ar(h) = 1, abbiamo due segni di relazione a 2 e tre posti, due segni
di operazioni binarie, un segno di operazione unaria ed un segno di costante.
Un esempio di struttura per questa segnatura: sostegno, l’insieme ω; la realizzazione
di R sia la relazione che vale tra n, m, k ∈ ω se n ´e primo e divide il prodotto mk; la
realizzazione di T sia l’usuale relazione d’ordine ≤;, la realizzazione di f sia l’ addizione,
di g sia la moltiplicazione, di h sia il moltiplicare per 2; e la realizzazione di c sia il
numero 7. (Tanto per dare l’ idea della estrema generalita’ delle nozioni in gioco.)
3. Linguaggi formali del primo ordine
Per ogni data segnatura τ =< R, F, C, ar > di strutture, introduciamo un alfabeto per
τ : esso conterra’ oltre ai segni presenti nella segnatura, i segni logici ed ausiliari come
segue:
– un segno di variabile individuale xi per ı ∈ ω; porremo V AR = {xi |i ∈ ω}.
– segni per i connettivi: ∨, ∧, →, ¬, ⊥;
– segni per i quantificatori universale ed esistenziale: ∀, ∃;
4
CAPITOLO 7
– segni di interpunzione: parentesi destra e sinistra, ”(” e ”)”, e la virgola ”,” .
Diversi linguaggi del primo ordine diﬀeriscono pertanto solo per i segni della segnatura;
per precisione, si puo’ indicare con L(τ ) il linguaggio per la segnatura τ. Una struttura A
di segnatura τ viene anche detta una struttura (in alcuni testi, dicesi anche un modello)
per L(τ ).
Come al solito, usiamo “ ” per indicare un generico segno di connettivo; ed a volte
usiamo “Q” per indicare uno dei due quantificatori.
4. Termini
In corrispondenza della nozione informale di (schema di ) ”espressione denotante”
avremo la seguente definizione dei termini del linguaggio L(τ ): sono i termini (ved.
cap.3) della segnatura (algebrica)< F, C, ar > . Questi sono ”schemi” nel senso che
possono contenere segni di variabile; una volta data una struttura ed assegnati valori a
tali variabili, avremo una espressioine che denota un elemento della struttura.
Ripetiamo per comodita’ la definizione induttiva:
(1) ogni segno di variabile xi e ogni segno di costante c ∈ C ´e un termine;
(2) per ogni f ∈ F con ar(f ) = n, se t0 , . . . , tnα −1 sono termini anche la sequenza
finita di segni:
f (t0 , . . . , tnα −1 )
[ ottenuta giustapponendo il segno f poi (, poi la sequenza di segni che compongono t0 , poi una virgola, etc. etc..] ´e un termine.
(3) niente altro `e un termine se non ottenuto dall’ uso delle clausole precedenti.
I segni di variabile e di costante si chiamano a volte termini atomici; gli altri termini
si dicono termini composti. Nel caso che un termine non contenga alcuna occorrenza di
segni di variabile, si chiama termine costante.
Con T ERM e T ERMc denoteremo l’insieme dei termini e dei termini costanti; il
secondo puo’ essere vuoto, se la segnatura non prevede alcun segno di costante ed alcun segno di funzione zeroario. Se necessario, per specificare la segnatura, potremmo
denotarli con T ERM (τ ), T ERMc (τ ).
Come al solito, potremo dimostrare proprieta’ dei termini o dei termini costanti per
induzione sui termini ; ed anche definire funzioni in T ERM per induzione.
Come prima applicazione, definiamo l’ insieme F V (t) dei segni di variabile che hanno
almeno un’occorrenza in un termine t :
–F V (c) = ∅, se c ∈ C.
–F V (xi ) = {xi } per i ∈ ω.
–F V (f (t1 , . . . , tn )) = F V (t1 ) ∪ · · · ∪ F V (tn ) per n ∈ ω, f ∈ Fn , ti ∈ T ERM.
Ricordiamo che una funzione σ da T ERM verso T ERM si dice una sostituzione se
per ogni c ∈ C, σ(c) = c, e per ogni n ∈ ω, ti ∈ T ERM ed f ∈ Fn , si ha
σ(f (t1 , . . . , tn )) = f (σ(t1 ), . . . , σ(tn )).
CAPITOLO 7
5
Proposizione 1.
(1) Le sostituzioni in T ERM sono completamente determinate
dal loro comportamento su V AR, ossia se σ, σ ′ sono sostituzioni e per ogni i ∈
ω, σ(xi ) = σ ′ (xi ), allora σ(t) = σ ′ (t) per ogni t ∈ T ERM.
(2) Data una funzione σ0 da V AR verso T ERM esiste esattamente una sostituzione
σ che estende σ0 .
(3) Se σ, σ ′ sono sostituzioni, t ∈ T ERM, e per ogni xi ∈ F V (t), σ(xi ) = σ ′ (xi ),
allora σ(t) = σ ′ (t).
Si tratta di risultati gi´a visti nel cap.3 (oppure si dimostrano per induzione come
esercizi).
Di solito si considerano sostituzioni σ in cui supp(σ) = {xi |σ(xi ) ̸= xi } sia finito. La
notazione in tal caso e’ indicata come [t1 , . . . , tn /xi1 , . . . , xin ], postfissa, sottintendendo
che per i ̸= i1 , . . . , in , σ(xi ) = xi e che tj = σ(xij ).
La composizione di sostituzioni produce sostituzioni; tuttavia si noti che in generale
t[t0 , t1 /x0 , x1 ],
(t[t0 /x0 ])[t1 /x1 ],
(t[t1 /x1 ])[t0 /x0 ]
sono tra loro diversi. (Si prenda t = f (x0 , x1 ), t0 = x1 , t1 = x0 .)
5. Interpretazione dei termini
Il significato di un termine si ottiene quando i suoi componenti ne abbiano ottenuto
uno; e pertanto occorre avere dato significato ai segni di costante, di variabile e di
operazione presenti nel termine. Occurrer´a riferirsi ad una struttura A per il dato
linguaggio L.
L’ ingrediente principale e’ allora dato da una lettura o interpretazione per le variabilii
in A, che per definizione e’ una funzione I da V AR in A, l’ insieme sostegno della
struttura. Porremo IN T (A) = {I|I : V AR 7→ A}. Dal teorema di definizione per
induzione su T ERM avremo:
Proposizione 2. Sia I ∈ IN T (A); esiste un’ unica estensione di I su T ERM tale che
(1) I(c) = (c)A per c ∈ C;
(2) I(f (t1 , . . . , tn )) = (f )A (I(t1 ), . . . , I(tn )), per n ∈ ω, f ∈ Fn , Ti ∈ T ERM.
Nota. Insistiamo sul cosa indica la clasuola 2 qui sopra. A sinistra, come argomento di I
compare il termine composto f (t1 , . . . , tn ) -cio`e una sequenza finita di segni dell’ alfabeto per la
segnatura < F, C, ar > ; persino le parentesi sono solo segni formali-. A sinistra invece abbiamo
una eﬀettiva operazione n−aria nell’ insieme base A, quella che si `e scelta come realizzazione
in A del segno di funzione f ; essa `e applicata ad una n−pla di elementi di A, che sono (per
ipotesi induttiva ) ordinatamente I(t1 ), . . . , I(tn ).
Potremmo alternativamente chiamare interpretazione o lettura dei termini in A una
funzione I : T ERM 7→ A che soddisfi 1 e 2. Allora si scoprirebbe che una lettura e’
completamente determinata dalla sua restrizione a V AR. Se I e’ una interpretazione in
6
CAPITOLO 7
A, spesso denoteremo I(t) con tI oppure piu’ chiaramente con tA,I : tale elemento di A
e’ il valore o la lettura o l’ interpretazione del termine t in A sotto I.
I termini costanti ricevono un’ interpretazione univoca in una struttura: se t ∈
T ERMc , sotto qualunque lettura I ∈ IN T (A), tA,I e’ sempre lo stesso elemento di
A, detto allora il valore di t in A, che si pu`o indicare con tA .
Interpretazioni e sostituzioni interagiscono in modo semplice:
Proposizione 3. Sia I una lettura dei termini in A, e sia σ una sostituzione in T ERM ;
se I σ : V AR 7→ A e’ definito da: I σ (xi ) = I(σ(xi )), allora per ogni termine t si ha :
(σ(t))A,I = tA,I .
σ
La dimostrazione, una semplice induzione su t, e’ lasciata al lettore. Con la stessa
tecnica si dimostra che:
Proposizione 4. Se I, I ′ ∈ IN T (A), t ∈ T ERM e I(x) = I ′ (x) per x ∈ F V (t), allora
′
tA,I = tA,I .
A volte, dati un termine t ed una struttura A conviene pensare a t come una notazione
o un simbolo per una operazione nell’ insieme A. Precisamente, se F V (t) = {x1 , . . . , xn },
a t corrisponde la funzione op(tA ) : An 7→ A definita da
op(tA )(a1 , . . . , an ) = tA,I ,
essendo I una lettura tale che I(xi ) = ai . (La definizione ´e ben data ... )
Un cambiamento di variabili e’ un’ applicazione iniettiva σ di V AR in V AR; anche
in questo caso essa ha una unica estensione ad una sostituzione. Il lettore dimostrera’
facilmente che se σ e’ un cambiamento di variabili e t ∈ T ERM , allora per ogni struttura
A, le due funzioni op(tA ), op((σ(t))A ) coincidono. Si noti pero’ che in una generica lettura
I, si pu`o avere: tA,I ̸= (σt)A,I .
Le operazioni in A della forma op(t) per un qualche termine t si chiamano a volte
polinomi (o funzioni polinomiali) su A.
Esempio.
Si abbia una segnatura con segni (infissi) di operazioni binarie +, −, sia t := x+(y −z)
e il cambiamento di variabili σ consista nello scambiare tra loro y con z. Nella struttura
usuale < Z, +, − > e sotto l’ interpretazione I(x) = 3, I(y) = 4, I(z) = 5, avremo
I(t) = 2, mentre I(σ(t)) = I(x + (z − y)) = 4. Invece le due funzioni da Z 3 verso Z
definite da t e da σ(t) sono la stessa funzione, ossia sono il polinomio che ad a, b, c ∈ Z
associa a + (b − c) -qui i segni denotano le usuali operazioni aritmetiche.6. Formule
Particolari sequenze finite di segni dell’ alfabeto di un linguaggio L di segnatura
< RF, C > costituiscono le formule atomiche di L, in corrispondenza della nozione di
”funzione proposizionale basilare”.
La definizione e’ la seguente: se ti ∈ T ERM, R ∈ Rn , allora R(t1 , . . . tn ) e’ una
formula atomica di L; inoltre ⊥ e’ una formula atomica di L.
CAPITOLO 7
7
Denoteremo con AT F ORM, o se necessario con AT F ORM (L), l’ insieme delle formule atomiche di L.
.
.
.
Nel caso che R sia =, scriveremo di solito t1 = t2 invece di = (t1 , t2 ). Si noti che se
R ∈ R0 , allora R e’ gia’ una formula atomica. (I segni di relazione zeroari si comportano,
in un certo senso, come delle variabili proposizionali.)
Definizione 1. Le formule di L son definite induttivamente da:
(1) ogni formula atomica di L e’ una formula di L;
(2) se φ, ψ sono formule di L , anche
(φ ∨ ψ), (φ ∧ ψ), (φ → ψ), (φ ↔ ψ), (¬φ)
sono formule di L;
(3) se φ e’ una formula di L, ed n ∈ ω, anche
(∀xn φ), (∃xn φ)
son formule di L,
(4) niente altro e’ una formula di L, se non ottenuto dalle clausole precedenti.
Indicheremo con F ORM , o se necessario con F ORM (L), l’ insieme delle formule del
linguaggo L.
Nell’ esibizione di formule, limiteremo l’ uso delle parentesi, con convenzioni simili
al caso di P ROP , badando naturalmente a conservare la leggibilita’ unica: quando nel
metalinguaggio descriviamo una formula, l’ unica cosa che conti e’ che tale formula sia
univocamente determinata.
Data la definizione induttiva, avremo la possibilita’ di dimostrare proprieta’ delle
formule per induzione. Circa le definizioni per induzione sulle formule, occorrera’ un
teorema del seguente tenore:
Proposizione 5. (Teorema sulle definizioni per induzione su F ORM )
Siano dati: un insieme B non vuoto, e, per = ∨, ∧, →, ↔ certe operazioni binarie
H in B; un’ operazione unaria H¬ in B; un elemento H⊥ ∈ B; per ogni c ∈ C, un
elemento cB ∈ B; ed infine per ogni i ∈ ω, operazioni unarie H∀i , H∃i in B. Per ogni
funzione G da AT F OR verso B,tale che G(⊥) = H⊥ , esiste un’ unica estensione di G
su F ORM, in modo che per φ, ψ ∈ F ORM, i ∈ ω,
(1) G(φ ψ) = H (G(φ), Gψ)), per = ∨, ∧, →, ↔,
(2) G(¬φ) = H¬ (φ);
(3) G(∀xi φ) = H∀i (G(φ)), G(∃xi φ) = H∃i (G(φ)).
La dimostrazione seguirebbe sempre il solito schema, come nel caso di T ERM, e viene
lasciata al lettore.
Per induzione su F ORM si definiscono alcune importanti nozioni. Intanto la nozione
di sottoformula: l’ unica sottoformula di una formula atomica α e’ α stessa; le sottoformule di α β sono la formula stessa e le sottoformule di α e di β; le sottoformule di ¬α
sono la formula stessa e le sottoformule di α; le sottoformule di ∀x α e di ∃x α sono la
formula stessa e le sottoformule di α.
8
CAPITOLO 7
7. Variabili libere e vincolate
Che un segno di variabile abbia un’ occorrenza in un termine o in una formula e’
nozione intuitivamente ovvia: esso e’ usato nella costruzione del termine o della formula.
E’ un poco piu’ delicato dare la nozione di cosa sia una precisa occorrenza di un segno
di variabile in una formula e distinguere tra le varie occorrenze di uno stesso segno: in
generale si ha una nozione intuitivamente chiara; per rendere la cosa precisa, si potrebbe
procedere come nel cap 3.
Si osservi che x puo’ avere in una formula sia occorrenze ”libere” ossia non soggette
all’ azione di quantificatori, che ”vincolate”: per esempio nella formula:
(∃y R(x, y)) → (∀x(¬R(x, y) ∧ R(z, y))
la prima e seconda occorrenza di y sono vincolate, le altre due sono libere, la 1a occorrenza di x e’ libera, le altre sono vincolate e quelle di z sono libere. Intuitivamente , e
vedremo poi che anche tecnicamente, le occorrenze
∫ vincolate∫ non hanno individualita’
(in modo simile a quando in analisi matematica f (x)dx = f (y)dy) : e’ intuitivo che
la formula precedente “dica la stessa cosa ” della seguente:
(∃y R(x, y)) → (∀w(¬R(w, y) ∧ R(z, y))
od anche della seguente:
(∃w R(x, w)) → (∀w(¬R(w, y) ∧ R(z, y)),
ottenute “cambiando nome” alle occorrenze vincolate di variabili. Si noti pero’ che
questo cambio di nomi alle variabili vincolate non deve interferire con le occorrenze
libere: la seguente invero avra’ significato ben diverso:
(∃x R(x, x)) → (∀y(¬R(y, y) ∧ R(z, y))
Appare opportuno, e vedremo come si possa realizzare, che in una formula si eviti che
una stessa variabile abbia occorrenze sia libere che vincolate.
Per induzione si definisce per ogni formula α l’ insieme F V (α) dei (segni di) variabili
che hanno almeno un’ occorrenza libera in α:
– se α e’ atomica , F V (⊥) = ∅; e F V (R(t1 , . . . , tn ) = F V (ti ) ∪ · · · ∪ F V (tn ) se
R ∈ Rn , ti ∈ T ERM.
– F V (α β) = F V (α) ∪ F V (β); F V (¬α) = F V (α);
– F V (∀x α) = F V (∃x α) = F V (α) \ {x}.
Questa nozione e’ a sua volta importante nel definire la sostituzione di variabili con
termini in una formula; l ’idea e’ infatti che solo le occorrenze libere di una variabile
siano sostituibili con termini.
Siano x, t rispettivamente una variabile ed un termine. La sostituzione α[t/x] di x con
t in una formula α e’ definita per induzione sulla formula:
(1) se α e’ atomica: ⊥[t/x] = ⊥; R(t1 , . . . , tn )[t/x] = R(t1 [t/x], . . . , tn [t/x]);
CAPITOLO 7
9
(2) (α β)[t/x] = α[t/x] β[t/x]; (¬α)[t/x] = ¬(α[t/x]);
(3) se α = Qy γ, Q = ∀, ∃, ed x = y allora α[t/x] = α; se invece x ̸= y, allora
α[t/x] = Qy (γ[t/x]).
In modo simile, si definirebbe la sostituzione simultanea α[t1 , . . . , tn /x1 , . . . , xn ]. Si
noti che [x1 , . . . , xn /x1 , . . . , xn ] ´e la sostituzione identica.
Per esempio:
R(x) → Q(x, y)[f (x, y), g(y)/x, y] = R(f (x, y)) → Q(f (x, y), g(y))
mentre
R(x) → Q(x, y)[f (x, y)/x][g(x)/y] = R(f (x, g(y))) → Q(f (x, g(y), g(y)).
Eﬀettuando una sostituzione puo’ capitare che una variabile del termine sostituendo
finisca in α per essere sotto l’azione di un quantificatore. Per esempio,
.
.
(∃x (x = y))[g(x)/y] = ∃x (x = g(x)).
Questo e’ a volte foriero di problemi; invero fara’ comodo, nelle interpretazioni delle formule, poter avere che se una formula e’ sempre soddisfatta in una struttura ( per esempio
.
la ∃x (x = y) sara’ valida comunque si interpreti y) allora rimane valida in quella strut.
tura anche dopo una sostituzione ( ∃x (x = g(x)) invece non e’ valida se, per esempio,
si tratta di una algebra di Boole, e l’operazione che realizza g e’ la complementazione.
E’ pertanto necessario tenere sotto controllo la situazione, mediante la seguente nozione:
il termine t e’ libero per x in una formula α ( a volte abbreviamo in LIB(t, x, α)) se, sinteticamente, nessuna variabile di t diventa vincolata in α[t/x]. La definizione induttiva
della relazione LIB(t, x, α)) ´e la seguente:
(1) se α e’ atomica, ´e sempre LIB(t, x, α) ;
(2) LIB(t, x, α
β) se e solo se LIB(t, x, α) e LIB(t, x, β); LIB(t, x, ¬α) sse
LIB(t, x, α);
(3) LIB(t, x, Qy α) sse y ∈
/ F V (t) e LIB(t, x, α).
Nozioni simili si usano anche per la sostituzione simultanea di pi´
u variabili con termini.
8. Formule chiuse
Tra le formule, si distinguono quelle che non hanno occorrenze di variabili libere:
α ∈ F ORM e’ una formula chiusa o un enunciato del linguaggio L se F V (α) = ∅.
(Nelle interpretazioni su una data struttura di cui al seguente paragrafo gli enunciati
sono quelle espressioni portatrici di senso e che esprimono una proposizione, come in
genere le formule esprimono funzioni proposizionali proposizionali.)
Si noti che una formula atomica R(t1 , . . . , tn ) e’ un enunciato sse i termini ti sono
tutti chiusi. Se in L non vi sono segni di operazione zeroarie ne’ di costanti, l’ unico
enunciato atomico sara’ ⊥. In generale, in un enunciato o non vi e’ alcuna occorrenza di
variabile, oppure qualunque occorrenza di variabile e’ vincolata.
10
CAPITOLO 7
Con SEN T o se necessario con SEN T (L) denotiamo l’ insieme degli enunciati del
linguaggio L.
Infine, una formula α si chiama aperta se non contiene alcun quantificatore: cioe’ se
e’ atomica o e’ una combinazione booleana (cioe’ mediante i soli connettivi) di formule
atomiche. Si noti che una formula puo essere sia aperta che chiusa, per esempio: una
formula atomica chiusa.
9. Interpretazione delle formule
para
PREMESSA. L ’interpretazione delle formule di un linguaggio L in una struttura per L
consente di ricostruire una nozione precisa di funzione proposizionale (o perlomeno di alcuni
aspetti di tale nozione linguistica). In pratica, per noi un ”funzione proposizionale del primo
ordine nelle variabili x1 , . . . , xn ” sara’ una coppia (α, A) con α formula di un linguaggio L, con
F V (α) = {x1 , . . . , xn }, ed A una struttura per L.
Data una struttura A per il linguaggio L, il punto di partenza sara’ una interpretazione delle
variabili in A , ossia una funzione I : V AR 7→ A. Con IN T (A) denotiano l’insieme di tutte le
interpretazioni delle variabili in A.
L’ obiettivo e’ di definire quando una formula α e’ “soddisfatta” o “valida” in A sotto l’
interpretazione I. Tale definizione andr´a necessariamente prodotta per induzione sulle formule.
Per applicare il teorema di definizione per induzione sulle formule, ci interesseremo, per una
formula α , ad un certo insieme di interpretazioni: quelle le interpretazioni che la ”rendono
valida in” A.
Per es.: α = R(x, y) → ¬Q(y); se R, Q sono simboli di predicati, e nella struttura A sono
letti come RA ⊆ A × A, QA ⊆ A, ed I manda x ad a ∈ A, y a b ∈ A, che I ”rende valida”
α significa che (a, b) ∈ RA comporta b ∈ QA , ossia che b ∈ QA oppure (a, b) ∈
/ RA . Con i
quantificari, per´o, la faccenda e’ meno immediata. Per es.: β = ∀xα = ∀x(R(x, y) → ¬Q(y));
quando avremo che I ”rende valida” β in A?. L’ idea e’ che α debba valere per ogni possibile
valore assegnato da I ad x. Ma la I ´e una data interpretazione; essa assegna ad x uno ed un
sol preciso valore in A. Bisognera’ allora considerare tutte le interpretazioni possibili che sulle
variabili diverse da x coincidono con I: la β sara’ ”resa valida” da I in A se e solo se qualunque
di queste altre speciali interpretazioni (le chiameremo: varianti di I rispetto ad x) rende valida
la formula α in A: questo consentira’ il passo induttivo del quantificatore ∀. In questo passo
induttivo abbiamo a che fare non solo con I, ma con l ’insieme di tutte le sue varianti su x.
Quindi l’ applicazione del teorema sulle definizioni induttive va precisato come segue.
9.1. Fissiamo una struttura A.
Consideriamo l’ algebra insiemistica booleana su H = P(IN T (A)) dei sottoinsiemi di
IN T (A).
Le operazioni H corrispondenti ai connettivi, sono quelle insiemistiche: unione per
H∨ , complementazione per H¬ , intersezione per H∧ Circa H→ , come in ogni algebra di
boole: Hf r(S, T ) = (IN T \ S) ∪ T.
Per introdurre le H∀n , H∃ n , , una per ogni variabile xn , usiamo la seguente nozione:
se I, I ′ ∈ IN T (A), diciamo che I, I ′ diﬀeriscono al piu’ su una certa variabile x, e lo
CAPITOLO 7
11
denotiamo con
I ′ =x I,
se per ogni variabile y diversa da x, I(y) = I ′ (y). Una tale I ′ si dira’ una variante di I
sulla variabile x. Ci sono tante varianti di I su x quanti sono gli elementi dell’ insieme
base A della struttura; anzi, per a ∈ A conviene indicare con Ixa quella variante di I che
manda x in a. Le varianti di I su x (sempre in riferimento alla stessa strutturaA), sono
quindi {Ixa |a ∈ A}.
Dopo di che , per S ⊆ IN T (A), definiamo:
H∀n (S) = {I| per ogni I ′ , (I ′ =xn I ⇒ I ′ ∈ S)} = {I|Ixan ∈ S per ogni a ∈ A};
H∃ n (S) = {I|per qualche I ′ ∈ S, I ′ =n I} = {I|Ixan ∈ S per qualche a ∈ A}.
Cominciamo ora dalle formule atomiche. Con V AL(α) ⊆ IN T (A) [ o, per maggior
chiarezza dovremmo scrivere: V AL(α, A) : tutto dipende dalla data struttura A], indichiamo l’ insieme delle interpretazioni che rendono valida α in A ; la definizione per
α atomica e’ la seguente:
(1) V AL(⊥) = ∅;
.
(2) V AL(t = t′ ) = {I|tA,I = t′A,I };
A,I
(3) V AL(R(t1 , . . . , tn )) = {I| < tA,I
>∈ RA },
1 , . . . , tn
per ogni n ∈ ω, R ∈ Rn , t, t′ , ti ∈ T ERM.
Abbiamo cosi’ una funzione V AL dall’insieme delle formule atomiche verso H.
.
Si noti che = viene interpretato come l ’identita’, e che per la formula atomica generica
occorrera’ prima valutare i termini e poi utilizzare la relazione che realizza in A il segno
di relazione R ∈ Rn .
A questo punto il teorema di definizione per induzione sulle formule assicura che esiste
un’ unica estensione di V AL a F ORM , che denoteremo ancora con V AL, tale che:
V AL(α ∧ β) = V AL(α) ∩ V AL(β);
V AL(α ∨ β) = V AL(α) ∪ V AL(β);
V AL(α → β) = (IN T (A) \ V AL(α)) ∪ V AL(β);
V AL(α ↔ β) = ((IN T (A) \ V AL(α)) ∪ V AL(β)) ∩ ((IN T (A) \ V AL(β)) ∪
V AL(α));
(5) V AL(¬α) = IN T (A) \ V AL(α);
(6) V AL(∀ xn α) = H∀ n (V AL(α)), cio´e: I ∈ V AL(∀xα) sse {Ixa |a ∈ A} ⊆ V AL(α);
(7) V AL(∃ xn α) = H∃ n (V AL(α)), cio´e: I ∈ V AL(∃xψ sse {Ixa |a ∈ A} ∩ V AL(α) ̸=
∅.
(1)
(2)
(3)
(4)
Circa il connettivo↔, sara’ considerato come definito mediante → e ∧. La nozione
basilare della semantica del primo ordine e’:
12
CAPITOLO 7
Definizione 2. La formula α e’ soddisfatta da o e’ vera nella o e’ valida nella struttura
A sotto l’interpretazione I se I ∈ V AL(α); questa circostanza sara’ denotata da:
A, I |= α
oppure da
|=A,I α;
o a volte – riutilizzando i valori di verita´a –, da
[[α]]A,I = 1.
Quando invece I ∈
/ V AL(α), scriveremo
A, I ̸|= α oppure ̸|=A,I α oppure [[α]]vvA,I = 0.
Quando il contesto determina la struttura A, scriviamo anche semplicemente: I |= α
oppure I ̸|= α.
E’ chiaro a questo punto che la coppia “ α, A” sia una espressione formale precisa per
una funzione proposizionale : dare valore alle variabili si realizza mediante la scelta di una
interpretazione I e si otterra’ il valore V ERO se e solo se A, I |= α.
In pratica e’ utile formulare alla maniera classica di A. Tarski le proprieta’ fondamentali della relazione come segue:
Proposizione 6. Per I ∈ IN T (A), α, β ∈ F ORM si ha:
(1) se α e’ atomica:
i A, I ̸|= ⊥;
.
ii A, I |= (t = t′ ) sse tA,I = t′A,I ;
A,I
>∈ RA ;
iii A, I |= R(t1 , . . . , tn ) sse < tA,I
1 , . . . , t1
(2) A, I |= α ∧ β sse A, I |= α e A, I |= β;
(3) A, I |= α ∨ β sse A, I |= α oppure A, I |= β;
(4) A, I |= α → β sse ( A, I ̸|= α oppure A, I |= β);
(5) A, I |= α ↔ β sse ( A, I |= α sse A, I |= β);
(6) A, I |= ¬α sse A, I ̸|= α;
(7) A, I |= ∀x α sse per ogni I ′ che diﬀerisca da I al piu’ su x, si ha A, I ′ |= α;
(8) A, I |= ∃x α sse per almeno un I ′ che diﬀerisca da I al piu’ su x, si ha A, I ′ |= α.
La dimostrazione consiste in un’ ovvia rilettura delle clausole di definizione della
funzione V AL.
NOTA. Comunemente l’ enunciato della proposizione 6 si trova dato come definizione ”
per induzione su α” della relazione ternaria ”A, I |= α” tra strutture, interpretazioni, formule.
Nelle clausole (7) e (8) l’ ipotesi induttiva non solo si riferisce ad α ma anche alle interpretazioni
che diﬀeriscono da I al pi´
u su x; infatti in tale passo induttivi, si da’ per scontato che conosciamo
gia’ tutte le interpretazioni I ′ , che siano varianti di I su xn , e per le quali –per ipotesi induttiva,
sappiamo gia’ cosa significhi che A, I ′ |= α valga.
CAPITOLO 7
13
Il lavoro fatto prima con gli insiemi V AL(α) ´e un modo per rendere chiara l’applicazione
del teorema sulle definizioni per induzione sulle formule che sta dietro una tale definizione.
Il fatto che la A, I |= α sia definita per induzione su α, consente di procedere con
dimostrazioni per induzione sulla formula e la prima osservazione molto importante e’
che interpretando una formula, le uniche variabili che interessano sono quelle che hanno
occorrenze libere nella formula:
Proposizione 7. Se I, I ′ ∈ IN T (A), e per ogni x ∈ F V (α), I(x) = I ′ (x), allora
A, I |= α sse A, I ′ |= α.
DIM. Per il caso atomico, si usa l ’analogo risultato per i termini (prop.5). Per i
connettivi, il passo induttivo e’ pressoche’ ovvio: per es.:sono equivalenti le seguenti:
– A, I |= (α ∨ β) sse –per definizione–
– A, I |= α oppure A, I |= β sse – per ipotesi induttiva–
– A, I ′ |= α oppure A, I ′ |= β sse– per definizione
A, I ′ |= (α ∨ β).
Sia ora A, I |= ∀ x ψ. Avremo che I, I ′ coincidono su F V (ψ) \ {x}.
Dobbiamo mostrare che A, I ′ |= ∀xψ, cioe’ dobbiamo mostrare che se I ′′ ´e una
qualunque interpretazione tale cheI ′′ = xI ′ ; si ha A, I ′′ |= ψ.
Data una tale I ′′ , si definisca I ′′′ come variante di I su x, salvo che I ′′′ (x) = I ′′ (x).
Avremo I ′′′ =x I, e pertanto A, I ′′′ |= ψ. Ma I ′′′ , I ′′ coincidono su F V (ψ), e pertanto per
ipotesi induttiva, A, I ′′ |= ψ. Per l’ arbitrarieta’ di I ′′ concludiamo (per definizione) che
A, I ′ |= ∀x ψ.
L’altro verso, come pure il caso di ∃, si trattano in modo simile.
Per es.: la formula
α = ∃xR(x, y)
puo’ essere interpretata in una qualunque struttura in cui si sia fissata una relazione binaria
come realizzazione del segno R.
1.Consideriamo i numeri naturali, e R(n, m) si intenda come “n < m”. Nell’ interpretazione
di y := 2, la formula e’ soddisfatta. Nell’ interpretazione di y := 0, non e’ soddisfatta
2. Sempre sul dominio dei naturali, leggiamo ora R(n, m) come “n ̸= 1 e n divide m”. L’
interpretazione y := m rende valida la formula se e solo se m non e’ un numero primo.
3.Sempre sullo stesso dominio, R(n, m) si realizzi come “n ≤ m ”. Ora la formula e’
soddisfatta da qualunque interpretazione della y.
4. Se cambiamo dominio, e prendiamo l’ umanit´a, con aRb per ”a ´e figlio di b” allora α e’
soddisfatta in una interpretazione I se e solo se I(y) ´e un genitore di qualcuno.
Vedremo presto come con le formule del primo ordine si possono formalizzare svariate proprieta’ e funzioni proposizionali su una data struttura, o su una classe di strutture.
La prop. 7 consente un’ utile notazione: sia φ una formula con F V (φ) ⊆ {x1 , . . . , xn };
e siano a1 , . . . , an elementi (non necessariamente distinti) di A; scriveremo:
14
CAPITOLO 7
(♣)
A |= φ(a1 , . . . , an )
per abbreviare che in una (qualunque) interpretazione I tale che I(x1 ) = ai , i =
1, . . . , n, si ha A, I |= φ. Si noti che di per s´e, la scrittura φ(a1 , . . . , an ) e’ priva di
senso: in particolare non indica certo che stiamo sostituendo alle variabili elementi di
A, che sarebbe un grave errore sintattico; alle variabili possiamo solo sostituire termini
del linguaggio.
10. Modelli, Soddisfacibilita’ Conseguenza logica
Dalla Prop. 7, segue immediatamente:
Corollario 1. Se α ´e un enunciato (formula chiusa), il suo esser valida o meno in una
struttura A non dipende dall’ interpretazione I, poiche’ F V (α) = ∅ : o si ha V AL(α) = ∅
oppure V AL(α) = IN T (A).
Ossia un enunciato α e’ valido in A sotto qualunque interpretazione delle variabili, o
sotto nessuna.
Definizione 3. Per un enunciato α scriveremo
A |= α
e diremo anche che A e’ un modello di α, se c’e’ una intepretazione I ∈ IN T (A) con
A, I |= α; equivalentemente, se per ogni I ∈ IN T (A), A, I |= α.
Questa notazione e’ anche in accordo con(♣), con n = 0.
Se A non e’ un modello di α, scriviamo A ̸|= α; si noti che, essendo α un enunciato,
questo equivale a A |= ¬α.
Definizione 4. Se Γ e’ un insieme di enunciati, si dice che A e’ modello di Γ e scriviamo:
A |= Γ
quando tutte le formule di Γ sono valide in A.
La nozione di “modello” si puo’ estendere a formule qualunque. All’ uopo, definiamo
la cosidetta chiusura universale ∀ α di una formula α, che consiste nel premettere alla
formula la quantificazione universale di ciascuna delle variabili in F V (α). Per fissare le
idee se F V (α) = {xi1 , . . . , xin }, con l’ ordine alfabetico i1 < · · · < in , definiamo
∀ α = ∀xi1 (. . . (∀xin α) . . . ).
Definizione 5. Per una formula qualunque α diremo che A e’ modello di α se A |= ∀α.
Se Γ ⊆ F ORM, diremo che A `e modello di γ se A |= ∀γ per ogni γ ∈ Γ.
Per esempio:
1. I modelli della formula
R(x, y) → R(y, x)
CAPITOLO 7
15
sono esattamente le strutture in cui il segno di relazione R si realizza in una relazione
simmetrica; mentre i modelli di:
.
¬R(x, x)∧(R(x, y)∧R(y, z) → R(x, z))∧(R(x, y) → ¬R(y, x)) wedge((x = y)∨R(x, y)∨R(y, x))
sono le strutture in cui R si realizza come relazione d’ ordine stretto totale.
2. Fissato un numero naturale k ≥ 1, in modo simile, si puo’ scrivere una formula ϑk
che esprima: ”ci sono almeno k elementi”:
∧
.
∃x1 . . . ∃xk ( (¬(xi = xj )|i, j ≤ k, i ̸= j)) :
i modelli di ϑ sono le strutture contenenti almeno k elementi. Per definizione, avremo
che anche i modelli della formula:
∧
.
(¬(xi = xj )|i, j ≤ k, i ̸= j)
sono le strutture con almeno k elementi.
Altrettanto importante e’ la nozione di soddisfacibilita’:
Definizione 6. Una formula α e’ soddisfacibile in una struttura A se esiste un interpretazione I per le variabili tale che A, I |= α. Se α e’ un enunciato, equivale a dire che
A e’ un modello di α.Una formula α e’ soddisfacibile se e’ soddisfacibile in una qualche
struttura.
Per collegare le due nozioni, si introduce, in modo analogo alla chiusura universale,
la chiusura esistenziale ∃α di una formula α; se F V (α) = {xi1 , . . . , xin }, con l’ ordine
alfabetico i1 < · · · < in , definiamo
∃ α = ∃xi1 (. . . (∃xin α) . . . ).
E’ allora evidente che α e’ soddisfacibile in A se e solo se A e’ un modello di ∃ α. La
formula α e’ soddisfacibile sse ∃ α ha un modello. Se α non e’ soddisfacibile, si dice che
α e’ insoddisfacibile.
Definizione 7. Un insieme Γ ⊆ F ORM e’ soddisfacibile se esistono una struttura A
ed un’ interpretazione I su A tali che per ogni φ ∈ Γ, A, I |= φ.
Se Γ ⊆ SEN T e’ un insieme di enunciati, esso e’ soddisfacibile se e solo se esso ha un
modello.
Γ ⊆ F ORM ´e insoddisfacibile se Γ non e’ soddisfacibile, ossia per ogni struttura A
esistono una formula γ ∈ Γ ed un’ interpretazione I su A tali che A, I ̸|= γ.
Se Γ ⊆ SEN T e’ un insieme di enunciati, esso e’ insoddisfacibile se e solo se non ha
alcun modello, se e solo se per ogni struttura A esiste una formula γ ∈ Γ tale che A ̸|= γ.
16
CAPITOLO 7
Definizione 8. Diremo che α sia una conseguenza logica ( o censeguenza semantica) di
un insieme Γ di formule, e lo denoteremo con:
Γ |= α,
se per ogni struttura A, e per ogni interpretazione I, se
A, I |= γ
per ogni
γ ∈ Γ,
allora A, I |= α.
Se Γ e’ finito = {γ1 , . . . , γn }, scriviamo a volte γ1 , . . . , γn |= α invece di Γ |= α.
Γ, ψ |= α sta per Γ ∪ {ψ} |= α. Se Γ = ∅, scriviamo |= α.
La negazione di Γ |= α si denota con: Γ ̸|= α. Questo significa che esistono una A ed
una I ∈ IN T (A), tali che I |= γ per ogni γ ∈ Γ, mentre I ̸|= α..
Se Γ ⊆ SEN T e’ un insieme di enunciati, ed α´e un enunciato, Γ |= α se e solo se ogni
modello di Γ ´e modello anche di α.
Una formula per cui |= α si chiama una formula logicamente o universalmente valida
ovvero una verita’ logica. Si noti che α e’ una verita’ logica se e solo se ∀ α e’ una verita’
logica.
Proposizione 8.
(1) Γ ̸|= α sse Γ ∪ {¬α} e’ soddisfacibile;
(2) Γ |= α sse Γ ∪ {¬α} e’ insoddisfacibile;
(3) Γ |= ¬α sse Γ ∪ {α} e’ insoddisfacibile;
(4) α e’ insoddisfacibile sse ¬α e’ una verita’ logica; α e’ una verita’ logica sse ¬α
e’ insoddisfacibile.
(5) ¬α soddisfacibile non comporta che α sia insoddisfacibile.
(6) α soddisfacibile e β soddisfacibile non sempre comportano che α∧β soddisfacibile.
(7) Da α soddisfacibile e α → β soddisfacibile non sempre consegue β soddisfacibile.
(8) Puo’ capitare che ne’ α ne’ ¬α siano verita’ logiche.
DIM La dimostrazione, del resto molto semplice, di 1,2,3,4 e’ lasciata per esercizio
.
al lettore. Per 5, si prenda per α la formula x = y : sia α che ¬α sono ovviamente soddisfacibili. Per lo stesso motivo, si ha la 6: α ∧ ¬α essendo chiaramente insoddisfacibile.
Per la 7: α ed α → ⊥ sono soddisfacibili, mentre ⊥ non lo `e. Infine la 8: n´e tale α
n´e ¬α sono verita’ logiche; la prima comporterebbe che tutte le strutture hanno un sol
.
elemento; ¬(x = y) e’ falsa in qualunque interpretazione I con I(x) = I(y).
´ espressiva del linguaggio del primo ordine
11. Capacita
´ comodo scrivere φ(x1 , . . . , xn ) per denotare che F v(φ) ⊆ {x1 , . . . xn }. In tale cirE
costanza se t1 , . . . , tn sono termini, ´e comodo scrivere φ(t1 , . . . , tn ) invece che
φ[t1 , . . . , tn /x1 , . . . , xn ].
In generale, quando scriviamo una formula φ(x, y, z, ...) diamo per inteso che le variabili
sono tutte distinte tra loro e distinte dalle variabili che occorrono vincolate in φ, ossia
entro l’azione di quantificatori. Per esempio se φ(x) = ∃y¬R(x, y), con R segno di
CAPITOLO 7
17
relazione binaria, diamo per scontato che x, y sono variabili diverse; se f (z, x) ´e un
termine, con φ(f (z, x)) si intende la formula
∃y¬R(f (z, x), y).
(Succede qualcosa di spiacevole se il termine sostituito ad x contiene una y che sia’ quantificata in φ(x) : per ora, stiamo attenti a diﬀerenziare per chiarezza in una sostituzione
[t/x in varphi e’ buona norma badare che t sia libero per x in φ.).
Una formula φ con esattamente le n variabili libere distinte x1 , . . . , xn intuitivamente
”esprime una relazione n-aria”. Precisamente: data una struttura A per il linguaggio di
φ, possiamo dire che a1 , . . . , an soddisfano φ in A se per l’ interpretazione I su A che
assegna a ciascuna xi il valore ai , si ha A, I |= φ. Un enunciato ψ esprime semplicemente
una proprieta’ della struttura: o e’ valido in A o no. E’ abitutale esprimere proprieta’
di A, a volte, con formule contenenti variabili libere: come si e’ visto, in tal caso si
intende la chiusura universale della formula; per esempio per un’ operazione binaria +
.
le strutture in cui essa e’ commutativa sono i modelli di : = (x, y) = (f (y, x); che,
.
naturalmente uno scriverebbe in forma infissa: x + y = y + x..
11.1. Possiamo descrivere ”esiste esattamente un oggetto tale che φ(x) :”
.
∃x(φ ∧ ∀z(φ[z/x] → z = x));
oppure ”φ(x) vale per almeno due oggetti”:
.
∃x∃y(φ ∧ φ[y/x] ∧ ¬(x = y))
oppure”φ(x) vale per esattamente due oggetti”:
.
.
.
∃x∃y(φ ∧ φ[y/x] ∧ ¬(x = y) ∧ ∀z(φ(z) → (z = x ∨ z = y))).
11.2. Fissato un numero naturale k ≥ 1, in modo simile, si puo’ scrivere una formula
chiusa ϑk che esprima: ”ci sono almeno k elementi”:
∧
.
∃x1 . . . ∃xk ( (¬(xi = xj |i, j ≤ k, i ̸= j)).
Se poi Ω = {ϑk |k ∈ ω, k ≥ 1} , i modelli di Ω sono le strutture infinite. (Vedremo piu’
avanti che invece non esiste alcun insieme di enunciati i cui modelli siano esattamente
le strutture finite.)
Per esprimere ”ci sono esattamente k elementi”, potremmo prendere:
∧
∨ .
.
( (¬(xi = xj )|i, j ≤ k, i ̸= j)) ∧ ∀y( (y = xi |i = 1, . . . , k))
18
CAPITOLO 7
11.3. Molti assiomi di strutture matematiche si scrivono al primo ordine nel relativo
linguaggio. Per esempio, la nozione di gruppo, in un linguaggio con solo un segno di
funzione binaria f si esprimerebbe dicendo che un gruppo e’ una struttura per tale
linguaggio che e’ modello delle formule:
.
– f (x, f (y, z)) = f (f (x, y), z) ( e si intende: la chiusura universale);
.
.
.
.
– ∃x(∀y(f (x, y) = y ∧ f (y, x) = y) ∧ ∃z(f (y, z) = x ∧ f (z, x) = x)).
Se cambiamo linguaggio, ed abbiamo oltre ad f, anche un segno di funzione unaria h
(per l ’inverso) ed una costante c (per l’elemento neutro), un gruppo sara’ un modello
di :
.
.
.
.
.
f (x, f (y, z)) = f (f (x, y), z) ∧ f (x, h(x)) = c ∧ f (h(x), x) = c ∧ f (x, c) = x ∧ f (c, x) = x;
e ora si tratta di una congiunzione di relazioni atomiche di identita’.
11.4. I detti popolari si prestano ad esercitarsi nel formulare esempi di formule di primo
ordine in adeguati linguaggi. ”Non c’e’ due senza tre” :
.
.
.
∃x∃y(¬(x = y) ∧ φ(x)φ(y)) → ∃z(¬x = y ∧ y = z ∧ φ(z)) :
esprime che se due oggetti distinti soddisfano φ, allora ce ne n’´e un terzo (ammesso
che questo sia il senso del detto). ”Chi non risica non rosica”: se R, S sono segni di
predicato unarii per ”risica” e ”rosica”:
(0)
∀x(¬R(x) → ¬S(x).
La stessa formula in ambiete diverso avra’ tutt’ altro significato. Per esempio sui
reali R, e se R denota ”essere positivo” ed S denota ”essere il quadrato di un numero
razionale”, la formula (0) e’ valida. Se invece R denota ”essere positivo” ed S denota
”avere una radice cubica” , la stessa formula (0) non e’ valida.
11.5. Consideriamo una normale equazione
(∗) 2x3 + x2 + 2 = 0
sul campo reale R.
Essa non e’ altro che una funzione proposizionale sui reali con una variabile libera: per
certi valori sara’ falsa e per altri sara’ vera. Vediamo come essa non sia altro che una
formula atomica di un opportuno linguaggio. Per esempio consideriamo il linguaggio
.
L1 con due soli segni di operazione binaria :f, g, nessun segno di relazione (salvo =) e
due segni di costante c, d. R diventa una struttura per questo linguaggio interpretando f
come l’ addizione, g come la motiplicazione, a come 0, e d come 1. Vediamo di scrivere (∗)
come formula atomica di questo linguaggio: siccome + e’ binaria dobbiamo raggruppare
i termini, che in (∗) sono scritti di seguito (utilizzando l’ associativita’ di +, ·)
φ:
.
f (g(f (d, d), g(x, g(x, x))), f (g(x, x), f (d, d)) = a.
CAPITOLO 7
19
Questa formula φ rappresenta (∗) nel senso che risolvere (∗) significa: trovare tutte le
interpretazioni I tali che
R, I |= φ.
Siccome φ ha solo x libera, in pratica significa trovare quali valori assegnati a x
rendono soddisfatta φ in R.
Se avessimo dei coeﬃcienti generici come in:
(∗∗) a1 x3 + a2 x2 + a3 = 0
e lavorando nello stesso linguaggio L1 , allora i coeﬃcienti diventano altre variabili
distinte y1 , y2 , y3 e diverse da x :
ψ:
.
f (g(y1 , g(x, g(x, x))), f (g(y2 , g(x, x)), y3 )) = a.
Abbiamo 4 variabili libere; risolvere (∗∗) per coeﬃcienti generici ai adesso significa:
fissati comunque valori reali a1 , a2 , a3 ∈ R, trovare tutte le interpretazioni I che assegnano I(yi ) = ai e che soddisfano ψ.
Cambiamo linguaggio: in L2 ci sono solo due segni di operazione unaria h, k uno di
operazione binaria f e la costante d, che in R si leggono come: elevare al cubo, elevare
al quadrato, l’addizione e il numero 1. Stavolta non abbiamo una costante per lo zero.
Tuttavia 0 e’ elemeto neutro per l’ addizione: la nostra equazione in L2 si puo’ scrivere
prendendo le variabili x, y distinte:
δ:
.
∀yf (f (f (f (h(x), h(x)), k(x)), f (d, d)), y) = y,
Abbiamo aggirato l’ assenza della costante per zero, dicendo che ”per ogni y, (2x3 + x2 +
2) + y e’ uguale a y”. Le soluzioni di (∗) in R sono esattamente le interpretazioni I tali
che R, I |= δ.
.
11.6. Nel linguaggio (oltre il segno di uguaglianza =) c’´e un segno di funzione binaria f
che nel dominio dei numeri reali si interpreti come l’ operazione di moltiplicazione. Scrivere una formula D(x, y) con x, y variabili libere che nello stesso dominio sia soddisfatta
se e solo se si assegna ad x un valore positivo e ad y l’inverso del valore di x.
Possiamo descrivere ”x e’ positivo” come: x ´e il quadrato di un numero diverso da
zero”. Possiamo descrivere ”b ´e zero” come: per ogni reale a, ab = a. Che a sia inverso
di b si puo’ espimere : ab = 1; e c e’ uguale a 1” si puo’ descrivere come ”per ogni d
reale, dc = d. Alla fine ecco una possibile formula per D(x, y) :
.
.
.
(∃z(f (z, z) = x ∧ (∀v(∀w(f (w, v) = v) → ¬(z = v))))) ∧ (∀w(f (f (x, y), w) = w))
20
CAPITOLO 7
11.7. Nel linguaggio c’e un segno di relazione binaria R; sul dominio degli esseri umani,
si interpreti come: aRb se e solo se a e’ figlio di b. Scriviamo una formula φ(x) soddisfatta
esattamente da coloro che non hanno (avuto mai) cugini. Un cugino/a di x e’ figlio/a
di uno/a zio/a di x, ed uno/a zio/a di x e’ figlio/a di un/a nonno/a di x:
.
¬(∃y∃z∃v∃w∃w(R(x, y) ∧ R(y, z) ∧ R(v, z) ∧ ¬(v = y) ∧ R(w, v)).
.
Il punto cruciale qui era ¬(v = y), altrimenti avremmo scritto che x non ha nonni .... .
11.8. Avendo (oltre il segno di uguaglianza) solo: una costante c ed un segno R(x, y)
di relazione binaria, che nel dominio dei numeri interi si interpretano come lo zero e l’
usuale relazione ≤, , scrivere una formula P (x) con una sola variabile libera x che nello
stesso dominio descriva la proprieta’: ”x e’ minore di -1 ”.
Cominciamo a descrivere ”a ´e uguale a −1”; negli interi significa: a ≤ 0 ma nessun b
esiste tale che a < b < 0. Quindi una possibile formula P (x) :
.
.
.
∃y(R(y, c) ∧ ¬∃z(R(y, z) ∧ R(z, c) ∧ (¬(y = z)) ∧ (¬(z = c))) ∧ R(x, y) ∧ ¬(x = y)).
12. Prime proprieta’ della logica del primo ordine
Sar´a importante la seguente
CONVENZIONE A meno che non sia indicato diversamente, ogni volta
che si considera una formula assoggettata ad una sostituzione , quale α[t/x] o
in genere α[t1 , . . . , tn /x1 , . . . , xn ], si da’ per scontato che il termine t sia libero
per x in α, o che i termini t1 , . . . , tn siano liberi per x1 , . . . , xn in α. Vedremo
presto che questa convenzione, per quanto attiene a studiare relazioni di conseguenza
logica, non ´e restrittiva.
12.1. Cominciamo con un lemma tecnico di uso frequente che collega interpretazioni e
sostituzioni:
Lemma 1. Siano α una formula e t un termine libero per x in α. Qualunque sia I
un’ interpretazione in una struttura A, si consideri l’ interpretazione I ϵ = Ixb con da
b = (t)A,I . Allora
A, I ϵ |= α sse A, I |= α[t/x].
dim Per induzione sulla formula α. Caso atomico: se α = ⊥, la cosa e’ ovvia. Sia
.
α = t = t′ . Il risultato consegue dalla proposizione 4 nel caso α = R(⃗t).
Caso booleano: α = φ ψ o α = ¬φ : il risultato e’ pressoche’ ovvio.
Quantificatori. Sia α = ∃yφ.
1.caso: x = y, oppure x ̸= ma x ∈
/ F V (φ). Si tratta di mostrare che
A, I ϵ |= ∃xφ sse A, I |= ∃xφ,
il che e’ ovvio dal fatto che Ixb =x I.
CAPITOLO 7
21
2.caso: x ̸= e x ∈ F V (φ). Si noti che allora t non puo’ contenere la variabile y :
quindi b non dipende dal valore attribuito ad y. Supponiamo che A, Ixb |= ∃yφ. (Nel
b,c
seguito evitiamo di menzionare A.) Allora esiste un c ∈ A, tale che si ha Ix,y
|= φ.
′
c
′b
b,c
c,b
c,b
Consideriamo I = Iy : ovviamente I x = Ix,y = Iy,x ; Quindi Iy,x |= φ. Per l’ipotesi
induttiva applicata alla formula φ ed all’ interpretazione Iyc , e osservando che Iyc (t) = b,
avremo: esiste c ∈ A tale che A, Iyc |= φ[t/x]; ed infine, per definizione A, I |= ∃y(φ[t/x]).
Ma ∃y(φ[t/x]) = (∃yφ)[t/x]).
Supponiamo viceversa che A, I |= ∃y(φ[t/x]); allora per qualche c ∈ A, avremo
A, Iyc |= φ[t/x].
Per ipotesi induttiva applicata a φ ed alla interpretazione Iyc (notando che Iyc (t) = b),
b,c
b,c
c,b
c,b
|= φ.
|= φ; ma ovviamente Iy,x
= Ix,y
; quindi esiste c ∈ A tale che Ix,y
otteniamo Iy,x
b
Per definizione, conlcudiamo che Ix |= ∃yφ.
Per il caso di ∀ si ragiona analogamente. Lasciamo per esercizio al lettore di formulare e dimostrare un lemma simile per il caso
di una sostituzione simultanea [⃗t/⃗x].
Ecco alcune applicazioni di questo lemma:
Proposizione 9. Se (secondo la convenzione) y e’ libera per x in α e y ∈
/ F V (α), si
ha:
|= ∀x α ↔ ∀y (α[y/x]);
|= ∃x α ↔ ∃y (α[y/x]);
DIM. Si tratta di dimostrare che per ogni struttura A e per ogni interpretazione
I ∈ IN T (A) si ha
A, I |= ∀x α sse A, I |= ∀y (α[y/x]).
Per l’implicazione “⇒”, sia I ′ =y I : occorre provare che I ′ |= α[y/x]. Bastera’, per il
lemma, provare che (I ′ )ϵ |= α, ove ora (I ′ )ϵ =x I ′ , e (I ′ )ϵ (x) = I ′ (y). Poich´e y ∈
/ F V (α),
si verifica facilmente che (I ′ )ϵ =x I; per cui la tesi segue dall’ interpretazione di ∀x.
Per l’implicazione “⇐”, sia I ′ =x I; occorre provare che I ′ |= α. Consideriamo I ′′ =y I,
con I ′′ (y) = I ′ (x). E’ facile controllare che I ′ =y (I ′′ )ϵ ; avremo allora da una parte, per
potesi, I ′′ |= α[y/x], per cui, dal lemma, otteniamo (I ′′ )ϵ |= α, ed infine I ′ |= α poiche’
y∈
/ F V (α).
Lasciamo l’ analoga prova per ∃ al lettore. Corollario 2. Se y, z ∈
/ F V (α), si ha
|= ∀z (α[z/x]) ↔ ∀y (α[y/x]);
|= ∃z (α[z/x]) ↔ ∃y (α[y/x]);
Questo rende precisa l’ idea intuitiva che le variabili quantificate non hanno indivudualit´a.
22
CAPITOLO 7
Definizione 9. Definiamo ≈ (equivalenza logica) tra formule ponendo, per α, β ∈
F ORM, α ≈ β sse |= α ↔ β.
Corollario 3. (Separazione di variabili libere/vincolate.) Per ogni formula α possiamo
determinare una α′ ≈ α, e tale che in α′ nessuna variabile abbia occorrenze sia libere
che vincolate.
Baster´a invero cambiar nome a tutte le variabili vincolate in α, scegliendo nuove
variabili, che non abbiano alcuna occorrenza in α : qui si fa uso del fatto che si hanno
infiniti segni di variabile a disposizione.
12.2. ISTANZE PROPOSIZIONALI.
Come conseguenza del teorema di definizione per induzione su P ROP avremo che
per ogni funzione G : AT P 7→ F ORM esiste esattamente un’ estensione di G a P ROP
tale che G(A B) = G(α) G(β), G(¬A) = ¬G(α), G(⊥) = ⊥, (α, β ∈ P ROP ). Una
tal G si chiama una istanziazione da P ROP a F ORM. Diremo che α ∈ F ORM e’
una istanza di φ ∈ P ROP se esiste una siﬀatta G tale che α = G(φ); diremo che α `e
una istanza atomica di φ ∈ P ROP se esiste una siﬀatta G tale che α = G(φ) ma con
G(AT P ) ⊆ AT F ORM, (ossia G porta lettere proposizionali in formule atomiche). Se φ
´e una istanza di A ∈ P ROP, e’ suggestivo dire che φ ” ha la stessa forma proposizionale
di ” A. La seguente proposizione fornisce casi di conseguenza logica o di leggi logiche
del primo ordine come “istanze” di conseguenze logiche o leggi logiche proposizionali
(usiamo |=0 per la relazione di conseguenza tra formula proposizionali):
Proposizione 10.
(1) Se Γ ∪ {α} ⊆ P ROP, G e’ un’ istanziazione da P ROP a
F ORM e se Γ |=0 α allora G(Γ) |= G(α).
(2) Se α ∈ F ORM e’ un’ istanza di una tautologia proposizionale, allora |= α.
DIM. Sia A una struttura qualunque, ed I ∈ IN T (A). Si supponga che I |= G(γ)
per ogni γ ∈ Γ. Tesi: I |= G(α). Definiamo la valutazione proposizionale v mediante:
v(pi ) = 1 sse I |= G(pi ). E’ presto visto, per induzione su P ROP, che allora v(φ) = 1
sse I |= G(φ), per ogni φ ∈ P ROP. Allora avremo v(γ)) = 1 per γ ∈ Γ; onde v(α) = 1
per ipotesi, e quindi I |= G(a). La seconda parte segue immediatamente. E’ chiaro che dalla proposizione precedente, possiamo ottenere facilmente casi di equivalenza logica instanziando equivalenze proposizionali. Per esempio, quali che siano le
formule α, β, si ha |= ¬(α → β) → ¬β, poich´e questa ha la forma di una tautologia
¬(A → B) → ¬B.
Inoltre si ha:
Proposizione 11. Per ogni formula α si ha:
(1) ¬∀x α ≈ ∃x ¬α
(2) ¬∃x α ≈ ∀x ¬α
(3) ∀x α ≈ ¬∃x ¬α
(4) ∃x α ≈ ¬∀x ¬α
(5) ∀x∀y α ≈ ∀y∀x α
CAPITOLO 7
23
(6) ∃x∃y α ≈ ∃y∃x α
(7) Se x ∈
/ F V (α), ∀x α ≈ α; ∃x α ≈ α.
Dim. Vediamo alcuni casi, lasciando gli altri per esercizio al lettore. (1):Sia I una
interpretazione su una generica struttura A, avremo che le seguenti sono equivalenti:
I |= ¬∀x α
I ̸|= ∀x α
esiste I ′ =x I, I ′ ̸|= α
esiste I ′ =x I, I ′ |= ¬α
I |= ∃x ¬α.
Circa (7): se I |= ∀x , e’ ovvio che I |= α. Per il viceversa si applica la proposizione 8 e
da I |= α si ha, per ogni I ′ =x I, I ′ |= α. La relazione ≈ e’ (ovviamente) riflessiva, simmetrica e transitiva; essa `e anche compatibile con i connettivi e con i quantificatori:
Proposizione 12. Se α ≈ α′ , β ≈ β ′ allora
(1) α α′ ≈ β β ′ ;
(2) ¬α ≈ ¬α′ ;
(3) Qxα ≈ Qx(α′ ).
DIM. Il caso dei connettivi e’ simile alla situazione proposizionale e viene lasciato
al lettore. Vediamo il caso ∀ : siano A una struttura, I ∈ IN T (A); sia I |= ∀x α. Sia
I ′ =x I : si ha I ′ |= α, e dall’ ipotesi α ≈ α′ , otteniamo I ′ |= α′ . Quindi I |= ∀xα′ . Il
viceversa vale per simmetria Altre utili proprieta’ dell’ equivalenza logica:
Proposizione 13. Se α, β ∈ F ORM :
(1) ∀x(α ∧ β) ≈ ∀x α ∧ ∀x β;
(2) ∃x(α ∨ β) ≈ ∃x α ∨ ∃x β;
(3) Se x ∈
/ F V (β),
∀x(α ∨ β) ≈ ∀x α ∨ β;
(4) Se x ∈
/ F V (β),
∃x(α ∧ β) ≈ ∃x α ∧ β;
(5) Se x ∈
/ F V (β),
∀x(α → β) ≈ (∃x α) → β;
(6) Se x ∈
/ F V (β),
∃x(α → β) ≈ (∀x α) → β;
(7) Se x ∈
/ F V (β),
β → ∀x α ≈ ∀x(β → α);
/ F V (β),
(8) Se x ∈
β → ∃x α ≈ ∃x(β → α).
24
CAPITOLO 7
DIM. Vediamo alcune di tali equivalenze, lasciando le altre come esercizio. Sia data
una qualunque struttura A e sia I ∈ IN T (A).
(1).Sia I |= ∀x(α∧β); allora per ogni I ′ =x I, si ha I ′ |= α, I ′ |= β sicche’ I |= ∀x α, I |=
∀x β. Viceversa sia I |= ∀x α ∧ ∀x β; quale che sia I ′ =x I : avremo I ′ |= α, I ′ |= β, onde
I ′ |= α ∧ β; quindi I |= ∀x(α ∧ β).
(4). Sia I |= ∃(α ∧ β); allora per qualche I ′ =x I, I ′ |= α ∧ β; allora I ′ |= α e quindi
I |= ∃x α, ed inoltre I ′ |= β, onde (x ∈
/ F V (β)) anche I |= β. Quindi I |= ∃x α ∧ β.
Viceversa, sia I |= ∃x α ∧ β; cioe’ I |= ∃x α, I |= β. Allora per qualche I ′ =x I, I ′ |= α;
ma anche I ′ |= β e percio’ I ′ |= α ∧ β, e infine I |= ∃x(α ∧ β).
Si noti che 5,6,7,8 conseguono dalle precedenti 1-4 e dalle proposizioni precedenti; per
esempio (x ∈
/ F V (β)) :
(∀x α) → β ≈ (¬∀x α) ∨ β
≈ (∃x ¬α) ∨ β
≈ ∃x(¬α ∨ β)
≈ ∃x(α → β)
NOTE.
1.Si noti che in genere ∀x(α ∨ β) → ∀x α ∨ ∀xβ non e ’ una legge logica (ogni intero
e’ a pari o dispari, ma non sono tutti pari ne’ tutti dispari). Similmente non sempre vale
∃x α ∧ ∃x β → ∃x(α ∧ β) . In generale la condizione x ∈
/ F V (β) e’ essenziale in 3-8 nella
proposizione precedente. (Esercizio: trovare controesempi in ciascun caso se si lascia cadere
questa ipotesi)
2. Dalla propriet´a (6) si ricava in particolare:
(⋆)
|= ∃x(α → ∀yα[y/x])
infatti essa `e equivalente a (∀xα) → ∀yα[y/x] la quale `e chiaramente una verit´a logica ( prop.
9). La (⋆) ha un sapore paradossale: ”esiste un tizio tale che, se lui ha il cappello, allora
tutti lo hanno.” Il paradosso `e solo apparente, in quanto si sta dicendo che o qualcuno non
ha il cappello o ce l’hanno tutti, che `e una verit´a logica classica. La diﬃcolt´a sta, semmai,
nel fatto che non abbiamo idea di chi questo tizio possa essere. Questo indica come in una
logica “costruttiva”, in cui se si aﬀerma un’ esistenziale si deve essere in grado di indicare un
testimone preciso, la equivalenza (6 ) non `e ammissibile.
12.3. Ancora alcune proprieta’ tecniche che riguardano le sostituzioni; intanto a volte
intendiamo sostituire una formula al posto di una sottoformula in una formula. Un modo
di formalizzare questa nozione e’ quella di ipotizzare un segno di relazione zeroario “jolly”
$. Allora α[β/$] e’definito per induzione su α come segue:
– se α e’ atomica e ̸= $, α[β/$] = α; invece $[β/$] = β;
– (α α′ )[β/$] = α[β/$] α[β/$]; (¬α)[β/$] = ¬(α[β/$]), (Qxα)[β/$] = Qx(α[β/$]).
Diremo che β e’ libera per $ in α se nessuna variabile libera di β risulta vincolata in
α[β/$]. Il lettore puo’ fornire la corrispondente definizione per induzione, come pure la
sostituzione simultanea di diversi jolly con altrettante formule.
CAPITOLO 7
25
Cominciamo dalle sostituzioni successive:
Proposizione 14. Siano x, y variabili distinte,t, r, s termini e α, β, γ formule:
(1) Se x ∈
/ F V (r),
(t[s/x])[r/y] = (t[r/y])[s[r/y]/x];
(2) Se x ∈
/ F V (r), e s, r sono liberi per x, y in α :
(α[s/x])[r/y] = (α[s/y])[s[r/y]/x];
(3) Se β e’ libera per $ in α, e t e’ libero per x in α e in β :
(α[β/$])[t/x] = (α[t/x])[β[t/x]/$];
(4) Se α, β sono libere per $, $′ in γ, β e’ libera per $′ in in α, e $ non ha occorrenze
in β :
(γ[α/$])[β/$′ ] = (γ[β/$′ ])[α[β/$′ ]/$].
DIM. 1. Per induzione su t. La cosa e’ ovvia se t e’ una costante o una variabile
diversa da x, y. Se t e’ x, il lato sinistro e’ s[r/y]. Il lato destro e’ x[s[r/y]/x] = s[r/y].
Passo induttivo: pressoche’ ovvio.
2.Per induzione su α. Nel caso atomico si usa la 1. Per i passi induttivi: esercizio.
Lasciamo per esercizio al lettore anche 3,4.
.
Se ci si accontenta di avere validita’ logica (non identit´a sintattica), abbiamo:
Proposizione 15. (Teorema di sostituzione) Se t, r, s sono termini , α, β, γ formule:
.
.
(1) |= r = s → t[r/x] = t[s/x];
.
(2) |= r = s → (γ[r/x] ↔ γ[s/x]);
(3) Se α e β sono liberi per $ in γ : |= (α ↔ β) → (γ[α/$] ↔ γ[β/$]).
DIM. Ricordiamo la convenzione sulle sostituzioni di termini. Siano A una struttura
ed I ∈ IN T (A); e si assuma che rI = sI (tralasciamo di indicare A) e che I |= α ↔ β.
1.Si procede per induzione su t. Se t e’ una costante o una variabile diversa da x, la
cosa e’ ovvia; se t = x, la tesi coincide con l’ipotesi. Il banale passo induttivo e’ lasciato
per esercizio al lettore.
2. Si deve mostrare che I |= γ[r/x] sse I |= γ[s/x]. Si procede per induzione su γ.
[Esercizio.]
3. Per induzione su γ, si dimostra che I |= γ[α/$] sse I |= γ[β/$].
Se γ `e atomica e diversa da $, la tesi, cio`e I |= γ[α/$] sse I |= γ[β/$], `e banale; se γ `e
$, la tesi `e l’ ipotesi. Per i passi induttivi, su usi la proposizione 13.
13. Forme normali prenesse
Definiamo quando una formula `e in forma prenessa secondo la definizione induttiva:
(1) una formula aperta `e in forma prenessa;
(2) se α `e in forma prenessa, anche Qxα `e in forma prenessa
(3) niente altro· · · .
26
CAPITOLO 7
per Q un quantificatore e x una variabile.
Insomma le forme prenesse sono del tipo
α = Qxi1 Qx2 . . . Qxin β
con n ≥ 0, e β formula aperta (la matrice di α).
Proposizione 16. Per ogni formula α possiamo determinare una α′ in forma prenessa
con α ≈ α′ .
DIM. [Cenno.] In primo luogo, troviamo una α′′ che abbia la propriet´a di separazione delle variabili (corollario della proposizione 10) ed equivalente ad α. Applicando
la proposizione 14 possiamo poi esportare tutti i quantificatori all’ esterno della formula. [Esercizio: descrivere un algoritmo che prende una formula α e restituisce una
logicamente equivalente ad α ed in forma prenessa.] Si noti che di forme prenesse per α
equivalenti ad α ce ne sono infinite.
Per esempio: trovare una forma prenessa equivalente a (A, B, C sono simboli predicativi ad uno e due posti):
((∃xA(x) → ∀yB(x, y)) → ¬∀xC(x, y)
per esempio, abbiamo la catena di equivalenze ≈:
((∃zA(z) → ∀wB(x, w)) → ¬∀uC(u, y)
((∃zA(z) → ∀wB(x, w)) → ∃u¬C(u, y)
∀a∀w(A(z) → B(x, w) → ∃u¬C(u, y)
∀a∀w∃u((A(z) → B(x, w)) → ¬C(u, y)).
Una formula che sia atomica oppure sia la negazione di una atomica, si dice un letterale (predicativo). Una formula aperta si dice in forma normale disgiuntiva se essa
`e una istanza atomica di una formula proposizionale in forma normale disgiuntiva: in
sostanza, `e una disgiunzione di congiunzioni di letterali predicativi. (Similmente, per le
f.n. congiuntive.)
Una formula aperta β `e ovviamente sempre un’ istanza atomica di (almeno) una
opportuna formula proposizionale γ mediante una funzione di istanziazione G : AT P 7→
AT F ORM. Se φ `e una formula proposizionale in forma normale (per fissare le idee, in
forma normale disgiuntiva) equivalente a γ, allora la formula G(φ) `e in forma normale
disgiuntiva, ma inoltre essa `e equivalente a β : infatti |=0 γ ↔ φ, onde (prop. 11)
G(β) ≈ G(φ).
Una formula `e in forma normale prenessa se `e in forma prenessa e la matrice `e in
forma normale (disgiuntiva). Da quanto sopra, e dalla prop.13, si ricava allora:
Proposizione 17. Per ogni formula α possiamo determinare una formula α′ equivalente
ad α ed in forma normale prenessa.
CAPITOLO 7
27
14. Forme di Skolem
L’idea di partenza ´e bene illustrata da un esempio. Supponiamo di avere una formula
(atomica) con tre variabili distinte R(x, y, z) di un dato linguaggio L e consideriamo la
formula (chiusa) prenessa:
α := ∀x∀y∃zR(x, y, z)
e vogliamo indagare sulla soddisfacibilit´a di α. Se essa ´e soddisfacibile, ci saranno
una struttura A, ed un’ interpretazione I tali che A, I |= α. Questo significa: per ogni
a, b ∈ A, esiste un c ∈ A, tali che la terna (a, b, c) appartiene alla realizzazione RA del
segno di relazione R in A. Se per ogni a, b ∈ A scegliamo uno di tali c, troviamo una
funzione g da A × A verso A, tale che
per ogni a ∈ A, per ogni b ∈ A, (a, b, g(a, b)) ∈ RA .
Questo suggerisce una procedura per ”eliminare” ∃ dall’ espression di α, a costo di
espandere il linguaggio L. Aggiungiamo alla segnatura di L un nuovo segno di funzione
a due posti f, ar(f ) = 2; ”nuovo” significa che non appartiene alla segnatura di L; e sia
L′ il nuovo linguaggio cos´ı ottenuto. Consisderamo allora la formula di L′ :
αSk := ∀x∀yR(x, y, f (x, y)).
Avremo
(z)
α ´e soddisfacibile se e solo se αSk ´e soddisfacibile.
Infatti: se α ´e soddisfacibile in A, I come sopra, trasformiamo A in una struttura
A+ per L′ , nel modo ovvio: stesso insieme base A; la segnatura di L si realizza come in
A; resta da realizzare il nuovo segno di funzione f, e naturalmente lo realizziamo nelle
´ allora ovvio che A+ , I |= αSk , con la medesima lettura I per
funzione g vista sopra. E
le variabvili in A.
Per il viceversa, se αSk ´e soddisfacibile, esister´a una struttura B del linguaggio L′ , tale
che con una qualche lettura I delle variabili in B,
B, I |= αSk ,
il che significa: per ogni a, b ∈ B, (a, b, fB (a, b)) ∈ RB . Ora trasformiamo B in una
struttura per L per ”dimenticanza”: B− ha o stesso insieme base B; e la segnatura di L
´ presto
si realizza esattamente come in B. Abbiamo dimenticato il segno aggiuntivof. E
visto che:
B− |= α.
Infatti (essendo una formula chiusa) basta trovare una lettura I che la soddisfi. Prendiamo la stessa I usata per αSk ; ´e pressoch´e ovvio che B− , I |= α : per ogni a, b ∈ B
esiste c = fB (a, b) tale che Iax by cz |= R(x, y, z).
Non cambia granch´e se al posto di R(x, y, z) ci fosse una qualunque formula aperta
con tre varabili libere distinte β(x, y, z). Una procedura del genere (detta di Skolemizzazione dal nome del logico svedese che la invent´o) si pu´o ripetere per una formula
chiusa qualunque, trasformata prima in forma prenessa, facendo tante estensioni del
28
CAPITOLO 7
linguaggio di partenza quante ne necessitano. Ecco una descrizione della procedura nel
caso generale.
INPUT: una formula chiusa α di un linguaggio L.
OUTPUT: una formula chiusa Y= αSk di un linguaggio L+ che estende L mediante
qualche (numero finito di) nuovi segni di operazioni, tale che:
(1) αSk sia una formula prenessa universale (nel prefisso compaiono al pi´
u solamente
∀),
(2) tale che valga (z).
1.– Data α: si trasforma in forma prenessa αp [[fin qui abbiamo addirittura equivalenza
logica; si ricordi che in questo passo tutti i quantificatori agiscono su variabili diverse, a
costo di cambiar nome alle variabili legate.]]
2.–Si analizza il prefisso della formula corrente, [[che al primo giro sar´a αp ]], e sia:
Q0 x0 Q1 x1 · · · Qn−1 xn−1
e sia β la formula aperta matrice della formula corrente sicch´e formula corrente
= Q0 x0 Q1 x1 · · · Qn−1 xn−1 β.
2.1. if n = 0 : allora la formula corrente ´e una formula chiusa ed aperta: ´e
atomica chiusa oppure una combinazione booleana di atomiche chiuse. then αSk :=
formula corrente [[i requisiti sono rispettati]] stop
2.2. else sar´a n > 0.
2.2.1. if tutti i Qj del prefisso sono ∀ then : αSk = formula corrente; stop
2.2.2 else sia Qi il primo segno di ∃ a partire da sinistra nel prefisso di formula corrente:
allarghiamo il linguaggio corrente aggiungendo un nuovo segno di funzione fi
ad i − 1 posti [[ sar´a come dire: un segno di costante se i = 0]]: si fa un updating della
formula corrente:
formula corrente:= Q0 · · · Qi−1 Qi+1 · · · Qn (β[xi /fi (x0 , . . . , xi−1 )])
[[abbiamo eliminato ∃xi , e sostituito in β (la matrice della formula corrente ) al
posto di xi il termine fi (x0 , . . . , xi−1 )]]
ed infine : ricomincia dal punto 2.
´ intuitivamente chiaro che in un numero finito di giri, si produce una formula αSk
E
come richiesto. Si noti che strutturalmente le successive sostituzioni cui β ´e sottoposta
durante la procedura non interferiscono l’una con l’ altra: ogni variabile sostituita,
viene sostituita con un termine che non contiene variabili con indice maggiore. La
dimostrazione precisa sarebbe un’ induzione sul numero di quantificatori esistenziali
della forma prenessa di α, sarebbe un immaginabile ”tour de force”, e non molto pi´
u
informativa dell’ esempio di z visto sopra; per cui la tralasciamo.
Un paio di esempi chiariscono l’ uso della procedura: trovare una forma di Skolem
αSk per
.
.
α = ∀y∃z(f (y) = g(z) ∧ (¬(∀y∃z(¬(g(y) = f (z)))))).
Come forma prenessa, ottemiamo (a meno di equivalenza logica):
CAPITOLO 7
29
.
.
∀y∃z∀u∃v(f (y) = g(z) ∧ g(u) = f (v)).
Aggiungiamo un segno di funzione unaria f1 ed un segno di funzione binaria f2 e
possiamo prendere:
.
.
∀y∀u(f (y) = g(f1 (y)) ∧ g(u) = f (f2 (y, u))
come forma di Skolem per α. Siccome la sua matrice ´e una congiunzione di identit´a,
essa ´e soddisfacibile (in una struttura con un sol elemento, ogni identit´a ´e soddisfatta);
quindi anche α ´e soddisfacibile.
Oppure: trovare una forma di Skolem αSk per
α = ∃x∀y∃z∀u∃vR(x, y, z, u, v),
con R formula aperta :
αSk = ∀y∀uR(c, y, f1 (y), u, f2 (y, u)),
con: C nuovo simbolo di costante, f1 nuovo segno di funzione unaria, f2 nuovo segno
di funzione binaria.
OSSERVAZIONI.
1. Sia α una formula chiusa di linguaggio L; sia αSk una sua forma di Skolem in linguaggio LSk ; come formule del linguaggio esteso, sarebbe possibile dimostrare (esercizio
!?) che
aSk |= α;
mentre in generale
α ̸|= αSk .
Per esempio, per ∃xR(x), con R atomica, una forma di Skolem sarebbe R(c) = R[c/x],
con c nuova costante in L′ . Supponiamo che in una struttura A con almeno due elementi,
si abbia che RA = {a} (sia un singoletto). Realizziamo la nuova costante su un elemento
b ∈ A, b ̸= a. Sia I un’interpretazione delle variabili che manda x as assumere il valore
b. Ciononostante, anche nel nuovo linguaggio, avremo I |= ∃xR(x) : basta prendere la
variante di I ′ =x I che manda x in a. Mentre, disperatamente, I ̸ modelsR(c).
2. Circa la validit´a come leggi logiche, sia α una formula chiusa di L. Ovviamente |= α
se e solo se ¬α ´e insoddisfacibile, se e solo se [a causa di z)], (¬α)Sk ´e insoddisfacibile nel
suo linguaggio esteso. ”A prima vista”, tuttavia controllare l ’insoddisfacibilit´a di una
formula (chiusa) universale –qual’´e una forma di Skolem – appare come alquanto faticoso:
nessuna struttura (del linguaggio esteso) e nessuna interpretazione debbono soddisfarla.
Sembra un lavoro non meno titanico di quello della verifica della |= α : si tratta di
analizzare la classe di tutte le possibili strutture . . . . Inoltre la Skolemizzata di ¬α ha una
scarsa aﬃnit´a intuitiva di significato con α. 2. Per una formula ϕ(x, y, . . . ) qualunque,
contenente variabili libere, la soddisfacibilit´a di ϕ equivale alla soddisfacibilit´a di ∃ϕ,
la sua chiusura esistenziale; si puo’ allora applicare la procedura di Skolemizzazione a
quest’ultima.
30
CAPITOLO 7
3. Per un insieme finito F = {φ1 , . . . , varphin } di formule , la sua soddisfacibilit´a equivale alla soddisfacibilit´a delle loro congiunzione, alla quale si pu´o applicare
l’osservazione precedente, per usare la forma di Skolem. NON possiamo invece invertire
i due passi: se prima troviamo per ciascuna ∃φi una forma di Skolem βi , la soddisfacibilit´a
dell’ insieme {β1 , . . . , βn } pu´o darsi non abbia alcuna relazione con la soddisfacibilit´a di
F.
4. Per un insieme infinito di formule (supponiamo pure siano tutte chiuse) Γ le forme
di Skolem sono, direttamente, di scarso aiuto per decidere sulla soddisfacibilit’ di Γ.
Anticipando sul capitolo 8, tuttavia, avremo il teorema di compattezza: ogni sottinsieme
finito F di Γ ´e soddisfacibile se e solo se Γ ´e soddisfacibile. Si puo’ allora usare per ofni
singolo F l’ osservazione precedente. Tuttavia, le strutture che rendono soddisfacibili
due distinti sottinsiemi finiti di Γ possono essere del tutto diverse tra loro.
5. L’ utilizzo principale delle forme di Skolem ´e nella cosidetta teoria di Herbrand
...[MANCA]
15. L’ eguaglianza
Il predicato di eguaglianza ha un trattamento speciale: il segno formale di eguaglianza
`e stato interpretato forzatamente come la relazione di identit`a in qualunque modello del
linguaggio.
Questo comporta che avremo una classe di verit`a logiche e di relazioni di conseguenza
logica che attengono all’ eguaglianza.
Infatti:
Proposizione 18. Le seguenti sono verit´a logiche, per t ∈ T ERM, α ∈ F ORM :
.
(1) x = x;
.
.
(2) (x = y) → (y = x);
.
.
.
(3) (x = y) ∧ (y = z) → (x = z);
.
.
.
.
(4) ((x1 = y1 ) ∧ (x2 = y2 ) ∧ . . . (xn = yn )) → (t[⃗x/⃗z] = (t[⃗y /⃗z]).
.
.
.
(5) ((x1 = y1 ) ∧ (x2 = y2 ) ∧ . . . (xn = yn )) → (α[⃗x/⃗z] ↔ α[⃗y /⃗z]).
.
La dimostrazione di (1),(2),(3) e’ banale , basata sul fatto che = `e interpretata come
identit´a in qualunque struttura; la (4) segue dalla prop. 15 (1), e la (5) segue dalla prop.
15 (2).
NOTA.
.
Abbiamo posto che = faccia sempre parte della segnatura di un liguaggio del primo
ordine. Questo non impedisce lo studio di linguaggi qualunque , anche senza eguaglianza
.
. Tuuti i risultati ottenuti che non riguardano specificamente = restano ovviamente
validi.
CAPITOLO 7
31
´ di un linguaggio
16. Cardinalita
La cardinalit´a del linguaggio L su una segnatura τ = (R, F, C) `e il numero cardinale
(≥ ℵ0 ) definito da:
Card(L) = max{ℵ0 , Card(R), Card(F), Card(C)}.
Vale a dire che essa `e la cardinalit´a infinita numerabile se il linguaggio ha solo un
numero finito o numerabile di segni di relazioni, funzioni e costanti. Altrimenti `e uguale
alla cardinalit´a dell’ insieme di tali segni.
Si noti che se un linguaggio ha cardinalit´a k allora l’insieme delle sue formule e l’
insieme delle formule chiuse hanno anch’essi cardinalit´a k. Infatti l’ alfabeto ha cardinalita’ k , e l’insieme di tutte le sequenze finite di segni dell’ alfabeto ha cardinalita’ κ.
Ma l’ insieme delle formule atomiche e’ gia’ di cardinalita’ almeno k :
.
– anche se R = F = C = ∅, Card(L) = ℵ0 , e abbiamo altrettante formule atomiche:Xi =
x + i, per i ∈ ω.;
– altrimenti, almeno uno tra R, F, C avr´a cardinalit´a k. In ciascun caso possiamo ot.
tenere almeno k formule atomiche: per esempio, se F ha cardinalita’ k, fi (x1 , · · · , xn ) =
f (x1 , · · · , xn ) ´e una formula atomica per ogni fi ∈ F , ar(fi ) = ni .
Circa l’ insieme dei termini di L, la sua cardinalita’ sara in generale almeno ℵ0 e non
superiore a Card(L).
17. ESERCIZI
.
(1) Nel linguaggio (oltre il segno di uguaglianza =) c’e’ un segno di funzione binaria
f . Nel dominio dei numeri naturali questo si interpreti come l’ operazione di
addizione. Scrivere una formula D(x, y) con x, y variabili libere che nello stesso
dominio sia soddisfatta se e solo se si assegna ad x il valore assegnato ad y piu’
1.
(2) Nel linguaggio ci sono due segni di funzione binaria f, g che nel dominio dei
numeri reali si interpretino come l’ operazione di addizione e di moltiplicazione.
Scrivere una formula D(x) con x variabile libera che nello stesso dominio sia
soddisfatta se e solo se si assegna ad x un valore maggiore od eguale a 1.
(3) Nel linguaggio ci sono: un segno di costante c un segno di funzione binaria f ed
un segno di predicato unario I. Nel dominio dei numeri reali questi si interpretino
come: lo zero 0, l’ operazione di moltiplicazione, e l’ insieme dei numeri interi.
Scrivere una formula D(x) con x variabile libera che nello stesso dominio sia
soddisfatta se e solo se si assegna ad x un numero irrazionale.
(4) Nel linguaggio ci sono solo: un segno di costante c e due segni di funzione binaria f, g. Nel dominio dei numeri reali questi si interpretino come: lo zero 0
e le operazioni di addizione e moltiplicazione. Scrivere una formula D(x) con x
variabile libera che nello stesso dominio sia soddisfatta se e solo se si assegna ad
x un numero negativo (minore di 0).
32
CAPITOLO 7
.
(5) Avendo (oltre il segno di uguaglianza =) solo: una costante c per il numero zero
ed un segno R(x, y) di relazione binaria, che nel dominio dei numeri interi si
interpreta come: ”x e’ minore di y”, scrivere una formula P (x) con una sola
variabile libera x che nello stesso dominio sia soddisfatta solo assegnando ad x il
valore 2.
(6) Nel linguaggio c’e un segno di relazione binaria R; sul dominio degli esseri umani,
si interpreti come aRb se e solo se a ’ figlio di b. Scrivere una formula φ(x)
soddisfatta da coloro che hanno esattamente un cugino ed una formula ψ(x)
soddisfatta esattamente da coloro che hanno esttamente due cugini.
(7) Nel linguaggio ci sono un segno di predicato binario R ed un segno di funzione
binaria f , che nel dominio Z dei numeri interi si interpretano come l’ usuale <
e l’operazione di moltiplicazione. Scrivere una formula P (x) con una variabile
libera, soddisfatta in Z se e solo se il valore assegnato a x e’ un numero pari.
.
(8) Nel linguaggio (oltre il segno di uguaglianza =) ci sono un segno di predicato
binario R ed un segno di funzione unaria f , che nel dominio dei numeri reali R si
interpretano come l’ usuale ≤ e l’operazione di elevamento al quadrato. Scrivere
una formula P (x) con una variabile libera, soddisfatta in R se e solo se il valore
assegnato a x e’ un numero strettamente minore di 0.
(9) Nel linguaggio ci sono segni di funzione f unario, g binario, una costante c ed
un segno di relazione binaria R. Sui reali R si interpretino come: una generica
funzione, la funzione distanza |a − b|, lo zero e la relazione ≤ . Scrivere una
formula senza variabili libere che esprima: ”il limite della funzione f (x) per
x → 0 e’ uguale a 0”.
(10) Nel liguaggio ci siano 2 simboli di operazione binaria +, ·, 2 segni di costante 0, 1
ed un simbolo di relazione binaria ≤. Scrivere gli assiomi che definiscono i campi
ordinati.
(11) Stesso linguaggio del numero (10): Scrivere una formula D(x, y) soddisfatta sula
campo reale R (con l´ınterpretazione solita dei simboli)se e solo se ad y si assegna
il valore assoluto del valore di x.
(12) Stesso linguaggio del numero (10): Scrivere una formula F (x) che sul dominio
degli interi Z (con l’ interpretazione usuale dei simboli) sia soddisfatta sse il
valore assegnato a x ´e il prodotto di due primi distinti e dispari.
(13) Stesso linguaggio del numero (10): Scrivere una formula G(x, y) che sul dominio
degli interi Z (con l’ interpretazione usuale dei simboli) sia soddisfatta sse i valori
assegnati ad x, y sono congruenti tra loro modulo 4.
(14) Stesso linguaggio del numero (10): Scrivere una formula H(x, y) che sul dominio
degli interi Z ( con l’ interpretazione usuale dei simboli) sia soddisfatta sse i
valori assegnati ad x ed y sono primi tra loro.
(15) Stesso linguaggio del numero (10): Scrivere una formula K(x) che sul dominio
dei razionali Q (con l’ interpretazione usuale
√
√dei simboli) sia soddisfatta sse il
valore assegnato ad x ´e compreso tra − 2 e 3.
(16) Stabilire se e’ vero o meno che (essendo f, g segni di funzioni unarie):
CAPITOLO 7
33
.
.
.
∀x(g(x) = f (g(x))), ∀z∃y(g(y) = f (z)) |= ∀x(f (x) = x).
.
.
(17) Stabilire se e’ vero o meno che |= ∀x(f (g(x)) = x) → ∀x(g(f (x)) = x) (essendo
f, g un segni di funzioni unarie).
(18) Stabilire se e’ vero o meno che (essendo f, g segni di funzioni unarie):
.
.
.
∀x(g(x) = f (g(x))), ∀z∃y(g(y) = z) |= ∀x(f (x) = x)
(19) Scrivere le seguenti formule in forma di Skolem e stabilire se siano soddisfacibili:
(∃x∀yR(y, x)) ∧ (¬∃xR(x, x)).
.
.
.
∀x(g(x) = f (g(x))) ∧ (∀z∃y(g(y) = z) → ∀x(f (x) = x))
.
.
∃y∀x(f (x, y) = x) → ∃x(f (x, x) = x)
.
.
∃x(f (x) = x) ∧ ¬∃y(f (f (y)) = y) (essendo f un segno di funzione unaria).
(¬∃x(P → Q)) ∧ ((∀xQ) → (∃xP )), (P,Q formule aperte)
¬(∃xP ∨ ((∀yQ → ∀xP ))) (P,Q formule aperte)

Download Report