Accidente cerebrovascular de Sheffer

Operación lógica

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 ). ${\displaystyle \mid }$ ${\displaystyle \uparrow }$ ${\displaystyle {\overline {\wedge }}}$ ${\displaystyle Dpq}$

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 .

Definición

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.

Tabla de verdad

La tabla de verdad de es la siguiente. ${\displaystyle A\uparrow B}$

Equivalencias lógicas

El trazo de Sheffer de y es la negación de su conjunción. ${\displaystyle P}$ ${\displaystyle Q}$

Por las leyes de De Morgan , esto también es equivalente a la disyunción de las negaciones de y ${\displaystyle P}$ ${\displaystyle Q}$

Notaciones y nombres alternativos

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] ${\displaystyle {\overline {\curlywedge }}}$ ${\displaystyle {\overline {\curlywedge }}}$

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] ${\displaystyle \sim }$

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 , nombrándolo el trazo de Sheffer. ${\displaystyle \mid }$ ${\displaystyle \wedge }$ ${\displaystyle \mid }$

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

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

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] ${\displaystyle \uparrow }$ ${\displaystyle \downarrow }$

Historia

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  [pl] también describió los operadores NAND y NOR y demostró que las otras operaciones booleanas podían expresarse mediante ellos. ^[5]

Propiedades

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

Completitud funcional

El trazo de Sheffer, tomado por sí mismo, es un conjunto funcionalmente completo de conectivos. ^{[14] [15]} Esto se puede ver a partir del hecho de que 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). ^[16]

También se puede demostrar mostrando primero, con una tabla de verdad , que es funcionalmente veritativamente equivalente a . ^[17] Entonces, dado que es funcionalmente veritativamente equivalente a , ^[17] y es equivalente a , ^[17] el trazo de Sheffer es suficiente para definir el conjunto de conectivos , ^[17] que se muestra como funcionalmente veritativamente completo mediante el Teorema de la Forma Normal Disyuntiva . ^[17] ${\displaystyle \neg A}$ ${\displaystyle A\uparrow A}$ ${\displaystyle A\uparrow B}$ ${\displaystyle \neg (A\land B)}$ ${\displaystyle A\lor B}$ ${\displaystyle \neg (\neg A\land \neg B)}$ ${\displaystyle \{\land ,\lor ,\neg \}}$

Otras operaciones booleanas en términos del trazo de Sheffer

Expresados ​​​​en términos de NAND , los operadores habituales de la lógica proposicional son: ${\displaystyle \uparrow }$

Véase también

• Dominio booleano
• CMOS
• Puerta equivalente (GE)
• Gráfico lógico
• Axiomas mínimos para el álgebra de Boole
• Memoria flash NAND
• Lógica NAND
• Ley de Peirce
• Flecha de Peirce = NOR
• Único operador suficiente

Referencias

1. Howson, Colin (1997). Lógica con árboles: una introducción a la lógica simbólica . Londres; Nueva York: Routledge. p. 43. ISBN 978-0-415-13342-5.
2. Peirce, CS (1933) [1880]. "Un álgebra de Boolia con una constante". En Hartshorne, C.; Weiss, P. (eds.). Documentos recopilados de Charles Sanders Peirce, volumen IV Las matemáticas más simples . Massachusetts: Harvard University Press. págs. 13–18.
3. Peirce, CS (1933) [1902]. "Las matemáticas más simples". En Hartshorne, C.; Weiss, P. (eds.). Documentos recopilados de Charles Sanders Peirce, volumen IV Las matemáticas más simples . Massachusetts: Harvard University Press. págs. 189–262.
4. Zach, R. (18 de febrero de 2023). "Sheffer golpe antes que Sheffer: Edward Stamm" . Consultado el 2 de julio de 2023 .
5. Stamm, Edward Bronisław [en polaco] (1911). "Beitrag zur Algebra der Logik". Monatshefte für Mathematik und Physik (en alemán). 22 (1): 137-149. doi :10.1007/BF01742795. S2CID  119816758.
6. Hilbert, D.; Ackermann, W. (1928). Grundzügen der theoretischen Logik (en alemán) (1 ed.). Berlín: Verlag von Julius Springer. pag. 9.
7. Hilbert, D.; Ackermann, W. (1950). Luce, RE (ed.). Principios de lógica matemática . Traducido por Hammond, LM; Leckie, GG; Steinhardt, F. Nueva York: Chelsea Publishing Company. pág. 11.
8. Łukasiewicz, J. (1958) [1929]. Elementy logiki matematycznej (en polaco) (2 ed.). Varsovia: Państwowe Wydawnictwo Naukowe.
9. Quine, W. V (1981) [1940]. Lógica matemática (edición revisada). Cambridge, Londres, Nueva York, Nueva Rochelle, Melbourne y Sydney: Harvard University Press. pág. 45.
10. Sheffer, Henry Maurice (1913). "Un conjunto de cinco postulados independientes para álgebras de Boole, con aplicación a constantes lógicas". Transactions of the American Mathematical Society . 14 (4): 481–488. doi : 10.2307/1988701 . JSTOR  1988701.
11. Nicod, Jean George Pierre (1917). "Una reducción en el número de proposiciones primitivas de la lógica". Actas de la Sociedad Filosófica de Cambridge . 19 : 32–41.
12. Church, Alonzo (1956). Introducción a la lógica matemática . Vol. 1. Princeton University Press . pág. 134.
13. Rao, G. Shanker (2006). Fundamentos matemáticos de la informática. IK International Pvt Ltd. pág. 21. ISBN 978-81-88237-49-4.
14. Weisstein, Eric W. "Cálculo proposicional". mathworld.wolfram.com . Consultado el 22 de marzo de 2024 .
15. Franks, Curtis (2023), "Propositional Logic", en Zalta, Edward N.; Nodelman, Uri (eds.), The Stanford Encyclopedia of Philosophy (edición de otoño de 2023), Metaphysics Research Lab, Stanford University , consultado el 22 de marzo de 2024
16. Emil Leon Post (1941). Los sistemas iterativos de dos valores de la lógica matemática. Anales de estudios matemáticos. Vol. 5. Princeton: Princeton University Press. doi :10.1515/9781400882366. ISBN 9781400882366.
17. Howson, Colin (1997). Lógica con árboles: una introducción a la lógica simbólica . Londres; Nueva York: Routledge. pp. 41–43. ISBN 978-0-415-13342-5.

Lectura adicional

• 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 de Boolia con una constante". En Hartshorne, Charles ; Weiss, Paul (eds.). Documentos recopilados de Charles Sanders Peirce . Vol. 4. Cambridge: Harvard University Press . págs. 12–20.

Enlaces externos

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