Instances de tautologies et valuations des formules premières

(i) Par induction sur $\tau$ : l'ensemble des formules propositionnelles qui ont la propriété contient les lettres et il est stable par $\neg$ et $\to$, donc il les contient toutes, par la définition de Formules propositionnelles.

Pour une lettre $P$, $\tau[\theta] = \theta(P)$ est une formule et $\bar v(\theta(P)) = u(P) = \bar u(P)$. Le remplacement se faisant lettre par lettre, $(\neg\tau_1)[\theta] = \neg(\tau_1[\theta])$, qui est une formule, et $$\bar v\big(\neg(\tau_1[\theta])\big) = 1 - \bar u(\tau_1) = \bar u(\neg\tau_1).$$

De même $({\to}\, \tau_1\, \tau_2)[\theta] = {\to}\, \tau_1[\theta]\, \tau_2[\theta]$ est une formule, dont c'est l'unique décomposition ; elle prend la valeur $0$ sous $\bar v$ si et seulement si $\bar u(\tau_1) = 1$ et $\bar u(\tau_2) = 0$, c'est-à-dire si et seulement si $\bar u({\to}\, \tau_1\, \tau_2) = 0$.

(ii) Par récurrence sur la longueur : une formule première est un facteur d'elle-même, et les facteurs de $\varphi$ et de $\psi$ sont des facteurs de $\neg\varphi$ et de ${\to}\, \varphi\, \psi$. Le même raisonnement montre que, pour une formule propositionnelle $\tau$, $\bar u(\tau)$ ne dépend que des valeurs de $u$ sur les lettres qui figurent dans $\tau$.

(iii) Si $\varphi = \tau[\theta]$ avec $\tau$ tautologie, (i) donne $\bar v(\varphi) = \bar u(\tau) = 1$ pour toute valuation $v$.

Réciproquement, supposons $\bar v(\varphi) = 1$ pour toute $v$. On associe à toute formule $\chi$ une formule propositionnelle $\chi^\circ$, son squelette, par récurrence sur la longueur : $$\begin{aligned} \pi^\circ &= P_{\ulcorner \pi \urcorner}, \\ (\neg\chi)^\circ &= \neg\chi^\circ, \\ ({\to}\, \chi\, \chi')^\circ &= {\to}\, \chi^\circ\, \chi'^\circ, \end{aligned}$$ pour $\pi$ première, où $\ulcorner \pi \urcorner$ est le code de $\pi$ (Codage des mots) ; deux formules premières distinctes reçoivent des lettres distinctes.

Soit $\theta(P_c)$ la formule de code $c$ si $c$ code une formule première, et la formule ${=}\, x_0\, x_0$ sinon. Par récurrence sur la longueur, $\chi^\circ[\theta] = \chi$ pour toute formule $\chi$, et les lettres de $\chi^\circ$ sont des $P_c$ où $c$ code une formule première.

Montrons que $\varphi^\circ$ est une tautologie. Soit $u$ une valuation booléenne et $v$ la valuation des formules premières définie par $v(\pi) = u(P_{\ulcorner \pi \urcorner})$. Par (i), $1 = \bar v(\varphi) = \bar v(\varphi^\circ[\theta]) = \bar u'(\varphi^\circ)$, où $u'(P) = \bar v(\theta(P))$.

Pour $c$ code d'une formule première $\pi$, on a $u'(P_c) = v(\pi) = u(P_c)$ : $u$ et $u'$ coïncident sur les lettres de $\varphi^\circ$, et (ii) donne $\bar u(\varphi^\circ) = \bar u'(\varphi^\circ) = 1$. Ainsi $\varphi^\circ$ est une tautologie et $\varphi = \varphi^\circ[\theta]$ en est une instance.