Barre de Sheffer

Diagramme de Venn de ${\displaystyle A\uparrow B}$.

En calcul de propositions, la barre de Sheffer, nommée d'après Henry M. Sheffer, notée « | » (voir barre verticale, à ne pas confondre avec « || » qui est souvent utilisé pour représenter la disjonction), « Dpq », ou « ↑ » (une flèche pointant vers le haut), désigne une opération logique qui est équivalente à la négation de la conjonction logique, exprimée « pas les deux à la fois » dans le langage ordinaire. Il est aussi appelé nand (« non et »), car il dit en effet qu'au moins l'un de ses opérandes est faux. En algèbre booléenne et en électronique numérique, il est connu sous le nom de l'opération NON-ET.

Comme son dual, l'opérateur NON-OU, NON-ET peut être utilisé par lui-même, sans aucun autre opérateur logique, pour constituer un système formel logique. Cette propriété rend la porte NON-ET cruciale pour l'électronique numérique moderne, y compris son utilisation dans la mémoire flash NAND et la conception d'un processeur d'ordinateur.

Définition

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

Histoire

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.

Introduction, élimination, et équivalences

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 }$

Articles connexes

• Liste des symboles logiques

• Domaine booléen
• Porte logique
• NAND gate
• NOR gate
• NOT gate
• Fonction OU
• Fonction NON-ET
• Fonction NON
• Calcul des propositions

Notes et références

1. Moses Schönfinkel, « Über die Bausteine der mathematischen Logik », Mathematische Annalen 92, (1924) p. 305-316. Traduit par Stefan Bauer-Mengelberg comme « On the building blocks of mathematical logic » in Jean van Heijenoort, 1967. A Source Book in Mathematical Logic, 1879-1931. Harvard Univ. Press: 355-66.

Notes

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sheffer stroke » (voir la liste des auteurs).

Références

• Bocheński, Józef Maria (1960), Précis of Mathematical Logic, translated from the French and German editions by Otto Bird, Dordrecht, South Holland: D. Reidel.
• Church, Alonzo, (1956) Introduction to Mathematical Logic, Vol. 1, Princeton: Princeton University Press.
• (en) Jean G. P. Nicod, « A Reduction in the Number of Primitive Propositions of Logic », Proceedings of the Cambridge Philosophical Society, vol. 19,‎ 1917, p. 32–41
• Charles Sanders Peirce, 1880, "A Boolian[sic] Algebra with One Constant", in Hartshorne, C. and Weiss, P., eds., (1931–35) Collected Papers of Charles Sanders Peirce, Vol. 4: 12–20, Cambridge: Harvard University Press.