Sostituzioni sulle variabili di un termine

Definizione: Siano $s$ e $t$ termini su $A$, e sia $x$ una variabile. Si indica con $s[t/x]$ il termine che si ottiene sostituendo $t$ al posto di (tutte le occorrenze di) $x$ in $s$.

Ad esempio, siano $s=f(x, y(x, c))$ e $t=f(c, c)$. Allora:

$$ s[t/x]=f(f(c, c), g(f(c, c), c)) $$

Differenza tra assegnamenti e sostituzioni

Non bisogna fare confusione tra assegnamenti e sostituzioni. Infatti:

• Gli assegnamenti servono a interpretare le variabili sul dominio di un modello. In particolare, un assegnamento $e:VAR\rarr D$ (su $\mathcal M=(D, I))$ fornisce un mapping da un termine in un elemento del dominio, producendo quindi un elemento che non è un elemento sintattico del linguaggio (ma è invece, appunto, un elemento del dominio del modello)
• Una sostituzione trasforma un termine (che è un elemento sintattico del linguaggio in un altro termine (anch’esso un elemento sintattico del linguaggio).

Osservazione

In generale, il termine generato da una sostituzione è meno generico di quello di partenza.

Ad esempio, dato il modello $\mathcal M=(\natnums , I)$, dove

$$ I(f):\natnums \rarr \natnums \ \ \ \widetilde \forall n\in \natnums \ \ I(f)(n)=1 \\ I(g):\natnums \rarr \natnums \ \ \ \widetilde \forall n\in \natnums \ \ I(g)(n)=n \\

$$

si considerino i termini

• $g(x)$
• $g(f(y))$, ottenuto dal precedente mediante la sostituzione $g(x)[f(y)/x]$

In fase di valutazione, scegliendo un arbitrario assegnamento:

• in $g(x)$ l’argomento di $y$ può variare su tutti i possibili elementi del dominio (che, per $\cal M$, sono i numeri natural)
• in $g(f(y))$, l’argomento di $g$ varia solo sugli elementi dell’immagine della funzione $I(f)$, cioè su tutti i possibili valori ottenuti applicando la funzione $I(f)$ ai valori del dominio (nell’esempio, solo sul valore 1).

Sostituzione sulle formule

Lo scopo di una sostituzione su una formula è istanziare una data variabile a un caso più particolare (un termine). Comunque, il significato della formula non deve essere stravolto: in particolare, bisogna fare attenzione al caso in cui il termine sostituito contiene delle variabili che sono quantificate all’interno della formula.