Complétude fonctionnelle

Fonctions de vérité

La leçon sur la sémantique de la logique propositionnelle a attribué à chaque formule, sous chaque valuation, une valeur de vérité, et a montré que cette valeur ne dépend que des valeurs des variables qui y apparaissent ; d’où toute formule à $n$ variables a une table de vérité de $2^{n}$ lignes. La question de cette leçon est la question inverse. Étant donné une table quelconque, c’est-à-dire une colonne de uns et de zéros écrite arbitrairement en face des $2^{n}$ lignes, existe-t-il une formule qui l’ait pour table ? Si c’est le cas pour toute table, le langage n’a pas de lacunes expressives : tout ce qui peut se dire sur la valeur de vérité de $n$ énoncés, en fonction des valeurs de ceux-ci, se dit avec une formule. Et comme dans ce cours toute formule composée est une négation conjointe, la réponse dira aussi si un seul connecteur suffit à tout dire.

Ce qu’on utilise des leçons précédentes

Une valuation est une fonction $v$ de l’ensemble des variables $\{v_1, v_2, \ldots\}$ dans $\{0, 1\}$, où $1$ est le vrai et $0$ le faux ; son prolongement à toutes les formules, qu’on écrit aussi $v$, est défini par récurrence : $v((\varphi \downarrow \psi)) = 1$ si et seulement si $v(\varphi) = 0$ et $v(\psi) = 0$. À partir des abréviations officielles, la même leçon a calculé, dans le théorème des valeurs des connecteurs dérivés, la valeur de chaque connecteur ; écrites avec des sommes et des produits, ce sont les suivantes, pour toute valuation $v$ et toutes formules $\varphi$ et $\psi$ :

En outre, $v((\varphi \leftrightarrow \psi)) = v(\varphi)\,v(\psi) + (1 - v(\varphi))\,(1 - v(\psi))$, qui vaut $1$ si et seulement si $v(\varphi) = v(\psi)$, et $v((\varphi \veebar \psi)) = v(\varphi) + v(\psi) - 2\,v(\varphi)\,v(\psi)$, qui vaut $1$ si et seulement si $v(\varphi) \neq v(\psi)$. Comme les valeurs sont $0$ ou $1$, le carré d’une valeur est la valeur elle-même, $v(\varphi)\,v(\varphi) = v(\varphi)$, et un produit de valeurs vaut $1$ si et seulement si chaque facteur vaut $1$ ; ces deux observations seront utilisées sans les répéter. On utilise aussi le lemme de coïncidence : si deux valuations coïncident sur les variables de $\varphi$, c’est-à-dire sur les variables qui sont des sous-formules de $\varphi$, elles donnent à $\varphi$ la même valeur. De la leçon sur la conséquence et l’équivalence sémantiques on reprend l’équivalence sémantique : $\varphi \eqsem \psi$ lorsque $v(\varphi) = v(\psi)$ pour toute valuation $v$. Enfin, la convention des lettres de la leçon sur la formalisation s’applique : $p$, $q$ et $r$ désignent les variables $v_1$, $v_2$ et $v_3$.

Les fonctions de vérité et leur nombre

Soit $n$ un entier naturel. Une ligne de $n$ valeurs est une suite $a = (a_1, \ldots, a_n)$ dans laquelle chaque $a_i$ est $0$ ou $1$ ; l’ensemble de toutes ces lignes se note $\{0, 1\}^{n}$. Une fonction de vérité à $n$ arguments est une fonction

qui attribue à chaque ligne une valeur de vérité. On la présente comme une table : les lignes s’écrivent dans l’ordre de la table, à partir de celle où toutes les valeurs sont $1$ (pour deux arguments, $1\,1$, $1\,0$, $0\,1$, $0\,0$), et en face de chaque ligne on écrit sa valeur. Une fonction de vérité est donc une table de vérité sans formule : la colonne de droite, sans rien d’écrit dans son en-tête.

Formules qui représentent des fonctions

Une formule et une fonction de vérité sont liées de la manière suivante. Si $\varphi$ est une formule dont les variables sont parmi $v_1, \ldots, v_n$, on dit que $\varphi$ représente la fonction de vérité $f$ à $n$ arguments lorsque, pour toute valuation $v$,

c’est-à-dire lorsque la table de $\varphi$, écrite avec les variables $v_1, \ldots, v_n$, est la table de $f$. La condition sur les variables n’est pas un détail : la formule $(p \wedge q)$ ne représente aucune fonction à un argument, parce que sa valeur ne dépend pas seulement de celle de $p$.

Il y a une infinité de formules à variables parmi $v_1, \ldots, v_n$ et seulement $2^{2^{n}}$ fonctions ; donc beaucoup de formules représentent la même fonction, et la proposition dit que ce sont exactement les formules équivalentes entre elles. Il reste à savoir si toute fonction est représentée par une formule, ou si certaines tables restent sans formule qui les ait.