Le misure di complessità come lh e ht, sono utili per fare dimostrazioni per induzione sull’insieme dei termini Per esempio, per

verificare che ogni termine gode di una proprietàP si verifica che la proprietà P vale per i termini di complessità minima (caso base) e che se P vale per tutti i termini di complessità inferiore alla complessità di t, allora anche t gode della proprietà P.

La scrittura t(x₁, . . . , xn) indica che le variabili che compaiono in t sono

tra le x1, . . . , xn. (Non chiediamo che tutte le xioccorrano in t.) In algebra, se

f (X) denota un polinomio nella variabile X, allora f (Y ) denota il polinomio f dove X è stata sostituita da Y . Analogamente, se x occorre in t(x), il

termine ottenuto sostituendo s al posto di x viene indicato con t[s/x] o, se la variabile x è chiara dal contesto, semplicemente con t(s). Un termine si dice chiuso se non contiene variabili, cioè se è stato costruito a partire dai simboli di costante e dai simboli di funzione. (Ovviamente se il linguaggio non contiene costanti, allora non ci sono termini chiusi.)

Formule. Una formula atomica è un’espressione della forma P (t1, . . . , tn)

oppure della forma

t1 = t2

dove t1, t2, . . . , tnsono termini e P è un simbolo di predicato n-ario. L’insieme

delle formule è definito induttivamente dalle clausole: • una formula atomica è una formula,

• se ϕ è una formula, allora anche (¬ϕ) è una formula,

• se ϕ e ψ sono formule, allora anche (ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ ⇒ ψ) e (ϕ ⇔ ψ) sono formule,

• se ϕ è una formula e x è una variabile, allora anche ∃xϕ e ∀xϕ sono formule.

Useremo le lettere greche ϕ, ψ, e χ, variamente decorate, per le formule.6 Una formula della forma (¬ϕ) è detta negazione; analogamente, una formula della forma (ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ ⇒ ψ), (ϕ ⇔ ψ), ∃xϕ e ∀xϕ è detta,

6Per le formule useremo talvolta anche le prime lettere dell’alfabeto in A, B, C, . . . in carattere tondo, come del resto abbiamo già fatto implicitamente nella Sezione 2.A.

rispettivamente, congiunzione, disgiunzione, implicazione, bi-implicazione, formula esistenziale e formula universale.

Convenzioni. (i) Per evitare l’eccessivo proliferare di parentesi, le soppri- meremo quando ciò non comporti ambiguità. Per esempio scriveremo ϕ∧ ψ, ϕ ∨ ψ, ϕ ⇒ ψ e ϕ ⇔ ψ invece di (ϕ ∧ ψ), (ϕ ∨ ψ), . . . ; ma se vogliamo prendere la negazione di una di queste formule reintrodurremo le parentesi. Seguiremo la convenzione che ∧ e ∨ legano più fortemente di ⇒ e ⇔, e che ¬ lega più fortemente di tutti gli altri connettivi. Quindi

ϕ∧ ψ ⇒ χ, ¬ϕ ∨ ψ sono abbreviazioni per

((ϕ ∧ ψ) ⇒ χ) , ((¬ϕ) ∨ ψ) .

In analogia con quanto detto per i termini, se  è un connettivo binario (cioè diverso da ¬) scriveremo ϕ₁ · · ·  ϕ_n al posto di ϕ₁ (ϕ₂ (· · ·  ϕ_n) . . . ).

(ii) Se P è un simbolo di relazione binario spesso useremo la notazione infissa t₁ P t2 al posto della notazione prefissa P (t1, t2). In particolare,

scriveremo s < t invece di <(s, t). (iii) t₁ 6= t₂ è un’abbreviazione di ¬(t₁= t₂).

Le sottoformule di ϕ sono ϕ e le formule usate per costruire ϕ. Una sottoformula di ϕ che sia diversa da ϕ si dice sottoformula propria. In altre parole:

• se ϕ è atomica, allora non ha sottoformule proprie,

• se ϕ è ¬ψ, allora le sue sottoformule proprie sono ψ e le sottoformule proprie di ψ,

• se ϕ è ψ  χ dove  è un connettivo binario, allora le sue sottoformule proprie sono: ψ, χ, le sottoformule proprie di ψ e le sottoformule proprie di χ,

• se ϕ è ∃xψ o ∀xψ, allora le sottoformule proprie di ϕ sono ψ e tutte le sottoformule proprie di ψ.

Per esempio, le sottoformule proprie della formula

sono ∃x∀y (P (x, y) ⇒ Q(x)), ∀zR(z) ∨ S(z) e tutte le sottoformule proprie di queste due. Quindi la lista completa delle sottoformule proprie di (3.2) è:

∃x∀y(P (x, y) ⇒ Q(x)) ∀zR(z) ∨ S(z) ∀y(P (x, y) ⇒ Q(x)) ∀zR(z)

P (x, y) ⇒ Q(x) R(z)

P (x, y) S(z)

Q(x)

Come per i termini, anche le formule possono essere descritte mediante alberi: l’albero sintattico della formula (3.2) è

∃x∀y (P (x, y) ⇒ Q(x)) ⇒ ∀zR(z) ∨ S(z) ∃x∀y(P (x, y) ⇒ Q(x)) ∀y (P (x, y) ⇒ Q(x)) P (x, y) ⇒ Q(x) P (x, y) Q(x) ∀zR(z) ∨ S(z) ∀zR(z) R(z) S(z) o più semplicemente ⇒ ∃x ∀y ⇒ P (x, y) Q(x) ∨ ∀z R(z) S(z)

I nodi dell’albero sintattico di ϕ sono le sottoformule di ϕ. Anche in questo caso abbiamo due nozioni di complessità : la lunghezza e l’altezza, definite in modo del tutto simile a quanto detto per i termini a pagina 22.

3.B. Ancora sulla formalizzazione. Nelle pagine precedenti abbiamo visto alcuni esempi di espressioni formalizzabili in un dato linguaggio L, ma ci capiterà spesso di imbatterci in frasi che non sono formalizzabili in

L, anche se magari lo sono in un linguaggio più ricco. In matematica si fa

sono delle formule secondo la nostra definizione ufficiale, quindi dovremo imparare a distinguere le formule ufficiali da quelle che potremmo chiamare pseudo-formule. Queste ultime sono semplicemente delle abbreviazioni stenografiche/simboliche di frasi matematiche espresse in un linguaggio natu- rale. Per esempio le espressioni contenenti prodotti non sono formalizzabili usando solo l’addizione. L’espressione x · y non può essere resa con

x + · · · + x

| {z }

y

quando x, y sono numeri naturali: l’espressione qui sopra non è un termine, dato che la sua lunghezza non è un intero fissato, ma dipende da y. (Natu- ralmente, un’espressione del tipo x · 3 può essere scritta come x + (x + x), che è un termine.) Per esempio, nell’Esercizio 2.8 parte (vii) a pagina 16, non possiamo eliminare il simbolo per l’esponenziale rimpiazzandolo con

xy = x · · · x

| {z }

y

perché il membro di destra non è un termine. Come vedremo nella Sezione 6.B, l’esponenziale può essere scritto usando solo addizione e moltiplicazione, ma questo è un risultato per nulla banale.

In generale le espressioni contenenti delle ellissi possono presentare problemi per la formalizzazione. Per esempio il

Problema di Waring. Per ogni k > 1 c’è un n tale per cui ogni naturale

è somma di n numeri che sono delle potenze di esponente k.

viene formalizzato così:

(3.3) ∀k > 1∃n∀x∃y1, . . . , yn



x = y₁k+ · · · + yk_n.

La scrittura qui sopra, benché perfettamente accettabile nell’uso quotidiano è una pseudo-formula, dato che il numero di quantificatori all’inizio dell’espres- sione non è fissato una volta per tutte. Ciò non significa che ci sia qualcosa di errato o sconveniente in quanto scritto in (3.3) — semplicemente non è una formula secondo la nostra definizione ufficiale. Non significa neppure che il problema di Waring non sia formalizzabile mediante una formula del prim’ordine — si veda l’Esercizio 6.51.

In alcuni casi può non essere evidente come formalizzare un enunciato in un dato linguaggio.

Esempio 3.3. La congettura abc asserisce che per ogni ε > 0 c’è una costante κε tale che se a, b, c sono coprimi fra loro e c = a + b, allora

c ≤ κεd(1+ε), dove d è il prodotto dei fattori primi distinti di a, b e c.

A prima vista la formalizzazione di questo enunciato nel linguaggio dell’aritmetica sembra improponibile, per via di numeri reali ε presente

nell’esponenziale d(1+ε). Tuttavia il reale ε può essere preso arbitrariamente piccolo, quindi della forma 1/n, mentre κε deve essere sufficientemente

grande, per cui la disuguaglianza c ≤ κ_εd(1+ε) diventa cn≤ mdn+1_{. Quindi}

la congettura abc è formalizzabile così:

∀n ∃m ∀a, b, c, d n > 0∧ d è il prodotto dei fattori primi distinti di a, b e c ∧ a, b, c sono coprimi ∧ c = a + b ⇒ cn≤ mdn+1

,

dove d è il prodotto dei fattori primi distinti di a, b e c può essere resa co- me

∀pPr(p) ⇒ p2_{- d ∧ (p | d ⇔ p | a ∨ p | b ∨ p | c)} e a, b, c sono coprimi può essere resa come

¬∃p [Pr(p) ∧ ((p | a ∧ p | b) ∨ (p | a ∧ p | c) ∨ (p | b ∧ p | c))] .

Naturalmente, possiamo sostituire i simboli 0, <, | e Pr con le loro definizioni in termini di somma e prodotto, e per quanto detto poco sopra, un discorso analogo si potrebbe applicare all’esponenziale.

3.C. Strutture e validità. Le formule sono strumenti particolarmente utili per studiare le strutture algebriche o le strutture d’ordine, e sono usate in maniera più o meno esplicita nella matematica. In algebra si parte da una famiglia di strutture algebriche e selezionando le proprietà rilevanti della struttura si definiscono le nuove strutture algebriche. Naturalmente, per parlare delle proprietà della struttura abbiamo bisogno di un linguaggio opportuno — per esempio, per definire la nozione di semigruppo partiamo da un insieme non vuoto S dotato di un’operazione binaria ∗ e richiediamo che valga le proprietà associativa

(3.4) ∀x, y, z ∈ S ((x ∗ y) ∗ z = x ∗ (y ∗ z)) Esempi di semigruppi sono:

• i numeri naturali N con l’operazione di addizione +,

• l’insieme Mn,n(R) delle matrici n × n su un anello R con l’operazione di

prodotto matriciale,

• l’insieme F delle funzioni da un insieme X in sé stesso con l’operazione di composizione ◦,

e così via. L’espressione (3.4) è una pseudo-formula, dato che abbiamo seguito l’usanza solita di indicare che gli oggetti su cui si quantifica appartengono ad un dato insieme, allontanandoci dalla definizione ufficiale di formula. In logica si preferisce partire da un linguaggio (che in questo caso contiene soltanto il simbolo di operazione binaria ∗) e dire che la formula

è vera nelle strutture (N, +), (Mn,n(R), ·), (F, ◦), . . . . In altre parole: il

simbolo di operazione ∗ viene interpretato di volta in volta come un’operazione diversa, a seconda della struttura specifica.

Il nostro obbiettivo è:

trovare una procedura per verificare quando una formula ϕ è vera in una struttura.

Innanzitutto osserviamo che alcune formule risultano vere in ogni struttura, indipendentemente dal significato che attribuiamo ai simboli del linguaggio — formule di questo tipo si dicono valide. All’estremo opposto abbiamo le formule insoddisfacibili cioè che risultano sempre false in ogni struttura, indipendentemente dal significato dei simboli. Per esempio, se P e f sono simboli di predicato e di funzione n-ari, allora le formule

(3.6) x = x x = y ⇒ y = x x = y ∧ y = z ⇒ x = z x1 = y1∧ · · · ∧ xn= yn⇒ (P (x1, . . . , xn) ⇔ P (y1, . . . , yn)) x1 = y1∧ · · · ∧ xn= yn⇒ f (x1, . . . , xn) = f (y1, . . . , yn)

sono valide, visto che abbiamo stabilito che il simbolo = denota sempre l’usuale relazione di uguaglianza. Invece la formula

∀x, y (x · y = y · x)

è soddisfacibile (vale a dire: non insoddisfacibile) ma non valida, dato che è vera o falsa a seconda che il simbolo · denoti un’operazione commutativa o meno, ad esempio, la moltiplicazione di numeri reali piuttosto che il prodotto di matrici. Analogamente

∀x, y (x < y ⇒ ∃z (x < z ∧ z < y))

è un’affermazione vera nei razionali o nei reali, ma falsa negli interi, quindi è una formula soddisfacibile, ma non valida. Se vogliamo istituire una procedura per verificare se una formula è vera in una struttura, dobbiamo cominciare ad esaminare le formule più semplici, vale a dire le formule atomiche. Tuttavia già il caso delle formule atomiche è problematico. Per esempio, per verificare se la formula x < y è vera in un insieme ordinato (A, <) è necessario attribuire un valore alle variabili x e y. Viceversa, ci sono formule contenenti variabili libere che sono vere o false in una struttura, indipendentemente dal valore attribuito alle variabili. Per esempio, la formula ¬(x < y) ∨ (x < y) è vera in ogni struttura (in cui abbia senso interpretare il simbolo <) indipendentemente dal valore attribuito alle variabili. Infatti, in generale, ogni formula della forma ϕ ⇒ ϕ ovvero ¬ϕ ∨ ϕ è valida,

indipendentemente da ciò che ϕ asserisce. Per i medesimi motivi, anche ϕ∧ ψ ⇒ ϕ è valida.

3.C.1. Tautologie. Dagli esempi qui sopra si vede come certe formule sono valide in virtù dei connettivi. Per studiare questo tipo di validità bisogna analizzare come una formula è costruita a partire da formule atomiche, esisten- ziali e universali. Diremo che una formula ϕ è combinazione booleana7 di formule A₁, . . . , An se ϕ è ottenuta da queste senza l’uso di quantificatori.

Se le A_i sono atomiche o esistenziali o universali (cioè non sono combinazioni booleane di loro sottoformule), allora diremo che A1, . . . , An sono le compo-

nenti primitive di ϕ. In altre parole, sono i nodi dell’albero sintattico di ϕ al di sopra dei quali non compaiono formule quantificate. Per esempio le sottoformule primitive della formula in (3.2) a pagina 23 sono

∃x∀y (P (x, y) ⇒ Q(x)) A ∀zR(z) B S(z) C

quindi la formula ∃x∀y (P (x, y) ⇒ Q(x)) ⇒ ∀zR(z) ∨ S(z) può essere scritta come A ⇒ B ∨ C.

Se fissiamo arbitrariamente dei valori di verità per le formule primitive, possiamo calcolare il valore di verità di una ϕ usando le proprietà dei connettivi. Più precisamente: una valutazione è una funzione

v : {ϕ | ϕ è atomica o esistenziale o universale} → {0, 1} ,

dove 0 rappresenta il falso e 1 rappresenta il vero. Ogni valutazione v può essere estesa ad una funzione (che verrà indicata ancora con v) dall’insieme di tutte le formule a valori in {0, 1}, ponendo

v(¬ϕ) = 1 − v(ϕ),

v(ϕ ∧ ψ) = min {v(ϕ), v(ψ)} = v(ϕ) · v(ψ) v(ϕ ∨ ψ) = max {v(ϕ), v(ψ)} ,

v(ϕ ⇒ ψ) = 1 − (v(ϕ) · (1 − v(ψ))) v(ϕ ⇔ ψ) = v(ϕ) + v(ψ) + 1 (mod 2).

Diremo che una formula è vera secondo v se e solo se v(ϕ) = 1, altrimenti diremo che è falsa secondo v. (Chiaramente la definizione di v qui sopra è imposta dal significato delle costanti logiche — Sezione 2.A.)

Una formula ϕ è

• una tautologia se v(ϕ) = 1 per ogni valutazione v,

• una contraddizione proposizionale se v(ϕ) = 0 per ogni valutazione

v.

Quindi una tautologia è una formula valida e una contraddizione propo- sizionale è una formula insoddisfacibile. Non tutte le formule valide sono tautologie — per esempio, si vedano le formule in (3.6) a pagina 27.

Siamo ora in grado di rendere rigorosi i discorsi fatti nella Sezione 2.A quando asserivamo che due espressioni costruite a partire da connettivi (per esempio A ⇒ B e ¬A ∨ B) erano equivalenti. Diremo che

• ϕ è tautologicamente equivalente a ψ se ψ ⇔ ϕ è una tautologia, • ϕ è conseguenza tautologica di ψ1, . . . , ψn se (ψ1∧ · · · ∧ ψn) ⇒ ϕ è

una tautologia.

Queste nozioni sono usate in matematica, spesso in modo implicito, quando invece di dimostrare un’affermazione del tipo ϕ ⇒ ψ si dimostra una formula tautologicamente equivalente ad essa, per esempio ¬ψ ⇒ ¬ϕ oppure ¬ϕ ∨ ψ.

Per verificare se una formula ϕ, che è combinazione booleana di sue sottoformule primitive A₁, . . . , An, è una tautologia o meno, si utilizza una

tabella nota come tavola di verità di ϕ. Si tratta di una tabella A1 A2 . . . An ϕ 0 0 . . . 0 i1 0 0 . . . 1 i2 .. . ... ... ... 1 1 . . . 1 i2n

con n + 1 colonne indicizzate da A₁, A₂, . . . , An e ϕ, e 2nrighe: nelle prime n

colonne scriviamo tutte le possibili valutazioni v di A₁, . . . , An e nell’ultima

colonna la valutazione di ϕ. Quindi ϕ è una tautologia se e solo se la colonna

n + 1-esima non contiene 0.

La tavola di verità della negazione è A ¬A

0 1

1 0

mentre quelle dei connettivi binari sono

A B A ∨ B A ∧ B A ⇒ B A ⇔ B

0 0 0 0 1 1

1 0 1 0 0 0

0 1 1 0 1 0

1 1 1 1 1 1

Osservazioni 3.4. (a) Mentre la nozione di equivalenza tra formule è stata