La barre de Sheffer

Ce qu'on a le droit d'utiliser. La définition de $\mid$ ; celle de l'implication, $P\Rightarrow Q$ étant par définition $(\neg P)\vee Q$ ; la double négation ; et les lois de De Morgan : $\neg (P\wedge Q)⟺(\neg P)\vee (\neg Q)$ et $\neg (P\vee Q)⟺(\neg P)\wedge (\neg Q)$. On écrit $=$ entre deux assertions qui ont la même table de vérité.

La stratégie : remonter la chaîne des connecteurs. La négation d'abord, puis la conjonction, qui n'est que la négation de la barre, puis la disjonction, qu'on atteint par De Morgan, enfin l'implication. Chaque étape ne se sert que de ce qui vient d'être établi.

1) La négation. L'assertion $P\wedge P$ a la même valeur de vérité que $P$ : elle est vraie exactement quand $P$ l'est. Donc $$P\mid P=\neg (P\wedge P)=\neg P.$$

2) La conjonction. Par définition $P\mid Q=\neg (P\wedge Q)$, donc, par double négation, $P\wedge Q=\neg (P\mid Q)$. Il suffit alors d'appliquer le 1) à l'assertion $P\mid Q$ tout entière : $$P\wedge Q=(P\mid Q)\mid (P\mid Q).$$

Le point délicat est ici. On applique la formule $\neg X=X\mid X$ non pas à une lettre, mais à l'assertion composée $X=P\mid Q$ : c'est légitime parce que le 1) vaut pour une assertion quelconque. C'est exactement le pas que l'on manque quand on cherche à écrire $\neg (P\mid Q)$ « directement ».

3) La disjonction. C'est ici que De Morgan travaille. Par double négation, $P\vee Q=\neg (\neg (P\vee Q))$, et par De Morgan $\neg (P\vee Q)=(\neg P)\wedge (\neg Q)$ ; donc $P\vee Q=\neg ((\neg P)\wedge (\neg Q))$, c'est-à-dire $P\vee Q=(\neg P)\mid (\neg Q)$. Il ne reste qu'à remplacer chaque négation par le 1) : $$P\vee Q=(P\mid P)\mid (Q\mid Q).$$

Vérification, cas par cas. La barre de deux assertions n'est fausse que si les deux sont vraies. Or $P\mid P$ et $Q\mid Q$ sont toutes deux vraies exactement quand $P$ et $Q$ sont toutes deux fausses : le membre de droite est donc faux dans ce seul cas, et vrai dans les trois autres — c'est la table de $P\vee Q$.

4) L'implication. Le cours définit $P\Rightarrow Q$ comme $(\neg P)\vee Q$. Par double négation puis De Morgan, $(\neg P)\vee Q=\neg (P\wedge (\neg Q))$, c'est-à-dire $P\mid (\neg Q)$ ; et $\neg Q=Q\mid Q$ par le 1). Donc $$P\Rightarrow Q=P\mid (Q\mid Q).$$ Contrôle. L'implication n'est fausse que lorsque $P$ est vraie et $Q$ fausse ; alors $Q\mid Q$ est vraie, et la barre de deux assertions vraies est fausse. Dans les trois autres cas, $P$ ou $Q\mid Q$ est fausse, et la barre est vraie — comme l'implication.

Conclusion. Toute assertion composée s'écrit avec $\neg$, $\wedge$ et $\vee$ : sa table de vérité se décrit en reliant par des « ou » les lignes où elle est vraie, chacune décrite par des « et ». Comme ces trois connecteurs s'écrivent avec la seule barre, un unique connecteur engendre toute la logique propositionnelle.

Ce que l'exercice installe. Les lois de De Morgan sont l'outil de calcul qui fait passer d'un connecteur à l'autre ; on les retrouvera à chaque négation d'une assertion quantifiée, donc dans toutes les définitions de l'analyse, à commencer par celle d'une limite. (Cette barre est celle de Sheffer, 1913 ; l'électronique numérique l'appelle porte NON-ET, et c'est pour cette raison qu'un processeur entier peut être fabriqué avec un seul type de porte logique.)