accidente cerebrovascular de Sheffer

En las funciones booleanas y el cálculo proposicional , el trazo de Sheffer denota una operación lógica equivalente a la negación de la operación de conjunción , expresada en lenguaje ordinario como "no ambos". También se le llama no conjunción , negación alternativa (ya que en efecto indica que al menos uno de sus operandos es falso) o NAND ("no y"). ^{[ 1 ]} En electrónica digital , corresponde a la puerta NAND . Recibe su nombre de Henry Maurice Sheffer y se escribe como${\displaystyle \mid }$o como${\displaystyle \uparrow }$o como${\displaystyle {\overline {\wedge }}}$o como${\displaystyle Dpq}$en notación polaca de Łukasiewicz (pero no como ||, que se usa a menudo para representar la disyunción ).

Su dual es el operador NOR (también conocido como flecha de Peirce , daga de Quine u operador Webb ). Al igual que su dual, la puerta NAND puede utilizarse por sí sola, sin ningún otro operador lógico, para constituir un sistema formal lógico (lo que la hace funcionalmente completa ). Esta propiedad convierte a la puerta NAND en un elemento crucial de la electrónica digital moderna , incluyendo su uso en el diseño de procesadores informáticos .

La no conjunción es una operación lógica sobre dos valores lógicos . Produce un valor verdadero si —y solo si— al menos una de las proposiciones es falsa.

Peirce fue el primero en demostrar la completitud funcional de la no conjunción (representando esto como${\displaystyle {\overline {\curlywedge }}}$) pero no publicó su resultado. ^{[ 2 ] [ 3 ]} El editor de Peirce añadió${\displaystyle {\overline {\curlywedge }}}$) para no disyunción. ^{[ 3 ]}

En 1911, Stammfue el primero en publicar una prueba de la completitud de la no conjunción, representando esto con${\displaystyle \sim }$(el gancho de Stamm ) ^{[ 4 ]} y la no disyunción en la impresión por primera vez y demostraron su completitud funcional. ^{[ 5 ]}

En 1913, Sheffer describió la no disyunción utilizando${\displaystyle \mid }$y demostró su completitud funcional. Sheffer también utilizó${\displaystyle \wedge }$para la no disyunción. ^{[ 4 ]} Muchas personas, comenzando con Nicod en 1917, y seguidas por Whitehead y Russell , pensaron erróneamente que Sheffer había descrito la no conjunción usando${\displaystyle \mid }$, denominando a este símbolo trazo de Sheffer.

En 1928, Hilbert y Ackermann describieron la no conjunción con el operador${\displaystyle /}$. ^{[ 6 ] [ 7 ]}

En 1929, Łukasiewicz utilizó${\displaystyle D}$en${\displaystyle Dpq}$para la no conjunción en su notación polaca . ^{[ 8 ]}

Una notación alternativa para la no conjunción es${\displaystyle \uparrow }$No está claro quién introdujo por primera vez esta notación, aunque la correspondiente${\displaystyle \downarrow }$Quine utilizó la no disyunción en 1940. ^{[ 9 ]}

El trazo recibe su nombre de Henry Maurice Sheffer , quien en 1913 publicó un artículo en las Transacciones de la Sociedad Matemática Americana ^{[ 10 ]} que proporcionaba una axiomatización de las álgebras booleanas utilizando el trazo, y demostró su equivalencia con una formulación estándar de la misma por Huntington empleando los operadores familiares de la lógica proposicional ( AND , OR , NOT ). Debido a la autodualidad de las álgebras booleanas, los axiomas de Sheffer son igualmente válidos para las operaciones NAND o NOR en lugar del trazo. Sheffer interpretó el trazo como un signo de no disyunción ( NOR ) en su artículo, mencionando la no conjunción solo en una nota al pie y sin un signo especial para ella. Fue Jean Nicod quien utilizó por primera vez el trazo como signo de no conjunción (NAND) en un artículo de 1917, lo que desde entonces se ha convertido en la práctica habitual. ^{[ 11 ] [ 12 ]} Russell y Whitehead utilizaron el trazo de Sheffer en la segunda edición de 1927 de Principia Mathematica y lo sugirieron como reemplazo de las operaciones "OR" y "NOT" de la primera edición.

Charles Sanders Peirce (1880) había descubierto la completitud funcional de NAND o NOR más de 30 años antes, utilizando el término ampheck (por 'cortar en ambos sentidos'), pero nunca publicó su hallazgo. Dos años antes que Sheffer, Edward Stamm también describió los operadores NAND y NOR y demostró que las demás operaciones booleanas podían expresarse mediante ellos. ^{[ 5 ]}

NAND es conmutativo pero no asociativo, lo que significa que${\displaystyle P\uparrow Q\leftrightarrow Q\uparrow P}$pero${\displaystyle (P\uparrow Q)\uparrow R\not \leftrightarrow P\uparrow (Q\uparrow R)}$. ^{[ 13 ]}

Expresado en términos de NAND${\displaystyle \uparrow }$Los operadores habituales de la lógica proposicional son:

• Bocheński, Józef María ; Menne, Albert Heinrich [en alemán] (1960). Resumen de lógica matemática . Traducido por Bird, Otto (  edición revisada). Dordrecht, Holanda Meridional, Países Bajos: D. Reidel .(NB. Editado y traducido de las ediciones francesa y alemana: Précis de logique mathématique )
• Peirce, Charles Sanders (1931–1935) [1880]. «Un álgebra booleana con una constante». En Hartshorne, Charles ; Weiss, Paul (eds.). Obras completas de Charles Sanders Peirce . Vol.  4. Cambridge: Harvard University Press . págs. 12–20 . 

• Artículo sobre el derrame cerebral de Sheffer en la Enciclopedia de Filosofía de Internet.
• http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
• Implementaciones de compuertas NAND de 2 y 4 entradas
• Demostraciones de algunos axiomas mediante la función Stroke de Yasuo Setô en Project Euclid.