Barre de Sheffer

L'opération NON-ET est une fonction logique sur deux valeurs logiques. Elle produit une valeur vrai, si — et seulement si — au moins une des propositions est fausse.

Table de vérité

La table de vérité de A NON-ET B (aussi noté A | B, Dpq, ou A ↑ B) est la suivante :

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\uparrow B}$
0	0	1
0	1	1
1	0	1
1	1	0

La barre est nommée d'après Henry M. Sheffer, qui en 1913 a publié un document dans les Transactions of the American Mathematical Society (Sheffer 1913) fournissant une axiomatisation des algèbres booléennes en utilisant cette barre, et a prouvé son équivalence. Moses Schönfinkel a étendu l'idée de Scheffer au calcul des prédicats dans sa tentative de minimiser le nombre de concepts de base en logique[1]. Russell et Whitehead ont utilisé la barre de Sheffer en 1927 lors de la deuxième édition des Principia Mathematica.

Charles Sanders Peirce (1880) avait découvert la complétude fonctionnelle de NON-ET ou NON-OU plus de 30 ans auparavant, mais il n'a jamais publié ses résultats.

La barre de Sheffer ${\displaystyle \uparrow }$ est la négation de la conjonction :

${\displaystyle P\uparrow Q}$	${\displaystyle \Leftrightarrow }$	${\displaystyle \neg (P\land Q)}$
	${\displaystyle \Leftrightarrow }$	${\displaystyle \neg }$

Exprimés en fonction de ${\displaystyle \uparrow }$, les opérateurs habituels de la logique propositionnelle sont :

${\displaystyle \neg P}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle P}$ ${\displaystyle \uparrow }$ ${\displaystyle P}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$		${\displaystyle P\rightarrow Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle ~P}$ ${\displaystyle \uparrow }$ ${\displaystyle (Q\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle ~P}$ ${\displaystyle \uparrow }$ ${\displaystyle (P\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$
${\displaystyle P\land Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle (P\uparrow Q)}$ ${\displaystyle \uparrow }$ ${\displaystyle (P\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$		${\displaystyle P\lor Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle (P\uparrow P)}$ ${\displaystyle \uparrow }$ ${\displaystyle (Q\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$

• Liste des symboles logiques