En funciones booleanas y cálculo proposicional , el trazo de Sheffer denota una operación lógica que es equivalente a la negación de la operación de conjunción , expresada en lenguaje ordinario como "no ambas". También se denomina no conjunción , o negación alternativa [1] (ya que dice en efecto que al menos uno de sus operandos es falso), o NAND ("no y"). [1] En electrónica digital , corresponde a la compuerta NAND . Recibe su nombre en honor a Henry Maurice Sheffer y se escribe como o como o como o como en notación polaca de Łukasiewicz (pero no como ||, a menudo usado para representar disyunción ).
Su dual es el operador NOR (también conocido como flecha de Peirce , daga de Quine u operador de Webb ). Al igual que su dual, NAND puede usarse por sí mismo, sin ningún otro operador lógico, para constituir un sistema formal lógico (lo que hace que NAND sea funcionalmente completo ). Esta propiedad hace que la compuerta NAND sea crucial para la electrónica digital moderna , incluido su uso en el diseño de procesadores de computadoras .
La no conjunción es una operación lógica sobre dos valores lógicos . Produce un valor verdadero si —y sólo si— al menos una de las proposiciones es falsa.
La tabla de verdad de es la siguiente.
El trazo de Sheffer de y es la negación de su conjunción.
Por las leyes de De Morgan , esto también es equivalente a la disyunción de las negaciones de y
Peirce fue el primero en demostrar la completitud funcional de la no conjunción (representando esto como ) pero no publicó su resultado. [2] [3] El editor de Peirce agregó ) para la no disyunción [ cita requerida ] . [3]
En 1911, Stamm fue el primero en publicar una prueba de la completitud de la no conjunción, representándola con el gancho de Stamm [4] y la no disyunción en forma impresa por primera vez y mostró su completitud funcional. [5]
En 1913, Sheffer describió la no disyunción utilizando y demostró su completitud funcional. Sheffer también utilizó para la no disyunción. [ cita requerida ] Muchas personas, comenzando por Nicod en 1917, y seguidas por Whitehead, Russell y muchos otros, pensaron erróneamente que Sheffer había descrito la no conjunción utilizando , denominándolo el Trazo de Sheffer.
En 1928, Hilbert y Ackermann describieron la no conjunción con el operador . [6] [7]
En 1929, Łukasiewicz utilizó en para la no conjunción en su notación polaca . [8]
Una notación alternativa para la no conjunción es . No está claro quién introdujo por primera vez esta notación, aunque la correspondiente para la no disyunción fue utilizada por Quine en 1940. [9]
El trazo debe su nombre a Henry Maurice Sheffer , quien en 1913 publicó un artículo en las Transactions of the American Mathematical Society [10] proporcionando una axiomatización de las álgebras de Boole utilizando el trazo, y demostró su equivalencia con una formulación estándar de las mismas por Huntington empleando los operadores familiares de la lógica proposicional ( AND , OR , NOT ). Debido a la autodualidad de las álgebras de Boole, los axiomas de Sheffer son igualmente válidos para cualquiera de 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 ello. Fue Jean Nicod quien utilizó por primera vez el trazo como signo de no conjunción (NAND) en un artículo de 1917 y que desde entonces se ha convertido en una práctica actual. [11] [12] Russell y Whitehead utilizaron el trazo de Sheffer en la segunda edición de Principia Mathematica de 1927 y lo sugirieron como reemplazo de las operaciones "OR" y "NO" 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 (que significa "corte 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 otras operaciones booleanas podían expresarse mediante ellos. [5]
NAND no posee ninguna de las siguientes cinco propiedades, cada una de las cuales se requiere que esté ausente, y la ausencia de todas las cuales es suficiente para, al menos un miembro de un conjunto de operadores funcionalmente completos : preservación de la verdad, preservación de la falsedad, linealidad , monotonía y autodualidad . (Un operador preserva la verdad si su valor es verdad siempre que todos sus argumentos sean verdad, o preserva la falsedad si su valor es falsedad siempre que todos sus argumentos sean falsedad). [13] Por lo tanto, {NAND} es un conjunto funcionalmente completo.
Esto también se puede realizar de la siguiente manera: los tres elementos del conjunto funcionalmente completo {AND, OR, NOT} se pueden construir utilizando solo NAND. Por lo tanto, el conjunto {NAND} también debe ser funcionalmente completo.
Expresados en términos de NAND , los operadores habituales de la lógica proposicional son:
El trazo de Sheffer, tomado por sí mismo, es un conjunto funcionalmente completo de conectivos. [14] [15] Esto se puede demostrar mostrando primero, con una tabla de verdad , que es funcionalmente verídicamente equivalente a . [16] Entonces, dado que es funcionalmente verídicamente equivalente a , [16] y es equivalente a , [16] el trazo de Sheffer es suficiente para definir el conjunto de conectivos , [16] que se muestra como funcionalmente verídicamente completo por el Teorema de la Forma Normal Disyuntiva . [16]
