Barre de Sheffer. On pose P ∣ Q := ¬(P ∧ Q). Exprimer ¬ P, puis P ∧ Q…

1) La négation. Puisque $P\wedge P$ a la même table de vérité que $P$, on a directement : $$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 la loi de De Morgan travaille. On a $P\vee Q=\neg (\neg P\wedge \neg Q)$, c'est-à-dire $P\vee Q=(\neg P)\mid (\neg Q)$, et il ne reste qu'à remplacer chaque négation par le 1) : $$P\vee Q=(P\mid P)\mid (Q\mid Q)$$

Vérification par table de vérité (colonne de droite : $(P\mid P)\mid (Q\mid Q)$) :

$P$	$Q$	$P\mid P$	$Q\mid Q$	$(P\mid P)\mid (Q\mid Q)$	$P\vee Q$
V	V	F	F	V	V
V	F	F	V	V	V
F	V	V	F	V	V
F	F	V	V	F	F

Ce que l'exercice démontre. Les trois connecteurs $\neg$, $\wedge$, $\vee$ suffisent à écrire n'importe quelle assertion composée — c'est le contenu des tables de vérité. Comme chacun des trois s'écrit avec le seul $\mid$, un unique connecteur engendre toute la logique propositionnelle.

On peut d'ailleurs continuer : $P\Rightarrow Q$ vaut $\neg (P\wedge \neg Q)$, soit $$P\Rightarrow Q=P\mid (Q\mid Q)$$ (Cette barre est celle de Sheffer, 1913 ; l'électronique l'appelle porte NAND, et c'est pour la même raison qu'on peut fabriquer un processeur entier avec un seul type de porte.)