La barre de Sheffer

Ce qu'on a le droit d'utiliser. La définition de $\mid$, 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)$. La stratégie est de tout ramener à des négations et des conjonctions, que la barre sait écrire.

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

2) La conjonction. Par définition $P\mid Q=\neg (P\wedge Q)$, donc $P\wedge Q=\neg (P\mid Q)$. Il suffit d'appliquer le 1) à l'assertion $P\mid Q$ : $$P\wedge Q=(P\mid Q)\mid (P\mid Q).$$

3) La disjonction. C'est ici que De Morgan travaille : $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, les quatre cas un par un. Si $P$ et $Q$ sont toutes deux vraies, $P\mid P$ et $Q\mid Q$ sont fausses ; la barre de deux assertions fausses est vraie, et l'on retrouve la valeur de $P\vee Q$. Si $P$ est vraie et $Q$ fausse, $P\mid P$ est fausse et $Q\mid Q$ est vraie ; leur barre est encore vraie, comme $P\vee Q$. Le cas symétrique donne vrai lui aussi. Enfin, si $P$ et $Q$ sont toutes deux fausses, $P\mid P$ et $Q\mid Q$ sont vraies, et la barre de deux assertions vraies est fausse : c'est bien la valeur de $P\vee Q$.

4) L'implication. Le cours définit $P\Rightarrow Q$ comme $(\neg P)\vee Q$. Or $(\neg P)\vee Q=\neg (P\wedge (\neg Q))=P\mid (\neg Q)$, et $\neg Q=Q\mid Q$. Donc $$P\Rightarrow Q=P\mid (Q\mid Q).$$

Conclusion. Toute assertion composée s'écrit avec $\neg$, $\wedge$, $\vee$ : c'est ce que disent les tables de vérité, puisqu'une table finie se décrit ligne par ligne par une disjonction de conjonctions. Comme chacun des trois s'écrit avec le seul $\mid$, un unique connecteur engendre toute la logique propositionnelle.

Ce que l'exercice installe. Les lois de De Morgan ne sont pas une curiosité : elles sont l'outil de calcul qui fait passer d'un connecteur à l'autre. On les retrouvera à chaque négation d'une assertion quantifiée. (Cette barre est celle de Sheffer, 1913 ; l'électronique l'appelle porte NAND, et c'est pour cette raison qu'un processeur entier peut être fabriqué avec un seul type de porte.)