Voir la source de Barre de Sheffer

[[Fichier:Venn1110.svg|vignette|[[Diagramme de Venn]] de <math>A \uparrow B</math>.]]
En [[Calcul des propositions|calcul de propositions]], la '''barre de Sheffer''', nommée d'après [[Henry Maurice Sheffer|Henry M. Sheffer]], notée « '''|''' » (voir [[barre verticale]], à ne pas confondre avec « || » qui est souvent utilisé pour représenter la [[Disjonction logique|disjonction]]), « '''D''pq''''' », ou « '''↑''' » (une flèche pointant vers le haut), désigne une [[Connecteur logique|opération logique]] qui est équivalente à la [[Négation logique|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 de Boole (logique)|algèbre booléenne]] et en [[électronique numérique]], il est connu sous le nom de l{{'}}'''opération NON-ET'''.

Comme son [[Dualité (mathématiques)|dual]], l'[[Fonction NON-OU|opérateur NON-OU]], NON-ET peut être utilisé par lui-même, sans aucun autre [[Connecteur logique|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|processeur d'ordinateur]].

== Définition ==
L'opération NON-ET est une [[fonction logique]] sur deux [[Valeur de vérité|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&nbsp;|&nbsp;B''', '''Dpq''', ou '''A&nbsp;↑&nbsp;B''') est la suivante :

{| class="wikitable"  style="margin: 0 0 1em 1em"
|- bgcolor="#ddeeff" align="center"
| <math>A</math> || <math>B</math> || <math>A \uparrow B</math>
|- bgcolor="#ddffdd" align="center"
|0 || 0 || 1
|- bgcolor="#ddffdd" align="center"
|0 || 1 || 1
|- bgcolor="#ddffdd" align="center"
|1 || 0 || 1
|- bgcolor="#ddffdd" align="center"
|1 || 1 || 0
|}

== Histoire ==
La barre est nommée d'après [[Henry Maurice Sheffer|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èbre de Boole (logique)|algèbres booléennes]] en utilisant cette barre, et a prouvé son [[Équivalence logique|é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<ref>Moses Schönfinkel, « {{Langue|de|Über die Bausteine der mathematischen Logik}} », ''{{Langue|de|Mathematische Annalen}}'' '''92''', (1924) {{p.}}305-316. Traduit par Stefan Bauer-Mengelberg comme « {{Langue|en|On the building blocks of mathematical logic}} » in [[Jean van Heijenoort]], 1967. ''{{Langue|en|A Source Book in Mathematical Logic, 1879-1931}}''. Harvard Univ. Press: 355-66.</ref>.
[[Bertrand Russell|Russell]] et [[Alfred North Whitehead|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 <math>\uparrow</math> est la négation de la conjonction :

{| style="text-align: center; border: 1px solid darkgray;"
|-
|<math>P \uparrow Q</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>\neg (P \land Q)</math>
|-
|[[File:Venn1110.svg|50px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>\neg</math> [[File:Venn0001.svg|50px]]
|}
Exprimés en fonction de <math>\uparrow</math>, les opérateurs habituels de la [[Calcul des propositions|logique propositionnelle]] sont :
{|
|-
|<!--- non --->
{| style="text-align: center; border: 1px solid darkgray;"
|-
|<math>\neg P</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>P</math>
|<math>\uparrow</math>
|<math>P</math>
|-
|[[File:Venn10.svg|36px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[File:Venn01.svg|36px]]
|<math>\uparrow</math>
|[[File:Venn01.svg|36px]]
|}<!--- end not--->

|&nbsp;&nbsp;&nbsp;
|<!--- flêche --->
{| style="text-align: center; border: 1px solid darkgray;"
|-
|<math>P \rightarrow Q</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>~P</math>
|<math>\uparrow</math>
|<math>(Q \uparrow Q)</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>~P</math>
|<math>\uparrow</math>
|<math>(P \uparrow Q)</math>
|-
|[[File:Venn1011.svg|50px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[File:Venn0101.svg|50px]]
|<math>\uparrow</math>
|[[File:Venn1100.svg|50px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[File:Venn0101.svg|50px]]
|<math>\uparrow</math>
|[[File:Venn1110.svg|50px]]
|}<!--- end arrow --->
|-
|&nbsp;
|-
|<!--- et --->
{| style="text-align: center; border: 1px solid darkgray;"
|-
|<math>P \land Q</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>(P \uparrow Q)</math>
|<math>\uparrow</math>
|<math>(P \uparrow Q)</math>
|-
|[[File:Venn0001.svg|50px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[File:Venn1110.svg|50px]]
|<math>\uparrow</math>
|[[File:Venn1110.svg|50px]]
|}<!--- end and --->
|&nbsp;&nbsp;&nbsp;
|<!--- ou --->
{| style="text-align: center; border: 1px solid darkgray;"
|-
|<math>P \lor Q</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>(P \uparrow P)</math>
|<math>\uparrow</math>
|<math>(Q \uparrow Q)</math>
|-
|[[File:Venn0111.svg|50px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[File:Venn1010.svg|50px]]
|<math>\uparrow</math>
|[[File:Venn1100.svg|50px]]
|}<!--- end or --->
|}

== Articles connexes ==
* [[Liste des symboles logiques]]
{{div col|2}}
* [[Domaine booléen]]
* [[Porte logique]]
* [[NAND gate]]
* [[NOR gate]]
* [[NOT gate]]
* [[Fonction OU]]
* [[Fonction NON-ET]]
* [[Fonction NON]]
* [[Calcul des propositions]]
{{div col end}}

== Notes et références ==
{{Références}}
=== Notes ===
{{Traduction/Référence|lang1=en|art1=Sheffer stroke}}

=== Références ===
* [[Józef Maria Bocheński|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]].
* [[Alonzo Church|Church, Alonzo]], (1956) ''{{Langue|en|Introduction to Mathematical Logic}}'', Vol. 1, [[Princeton, New Jersey|Princeton]]:  [[Princeton University Press]].
* {{article|langue=en| nom1 = Nicod | prénom1 = Jean G. P. | lien auteur = Jean Nicod | année = 1917 | titre = A Reduction in the Number of Primitive Propositions of Logic | url = | journal = Proceedings of the Cambridge Philosophical Society | volume = 19 | numéro = | pages = 32–41 }}
* [[Charles Sanders Peirce]], 1880, "A Boolian[sic] Algebra with One Constant", in [[Charles Hartshorne|Hartshorne, C.]] and [[Paul Weiss|Weiss, P.]], eds., (1931–35) ''Collected Papers of Charles Sanders Peirce, Vol. 4'': 12–20, [[Cambridge]]:  [[Harvard University Press]].

{{Palette Connecteurs logiques}}

{{Portail|logique}}

[[Catégorie:Connecteur logique]]
[[Catégorie:Symbole]]