NOR lógico

Operación binaria que es verdadera si y solo si ambos operandos son falsos

En lógica booleana , NOR lógico , ^[1] no disyunción o negación conjunta ^[1] es un operador veritativo-funcional que produce un resultado que es la negación de o lógico . Es decir, una oración de la forma ( p NOR q ) es verdadera precisamente cuando ni p ni q son verdaderas, es decir, cuando tanto p como q son falsas . Es lógicamente equivalente a y , donde el símbolo significa negación lógica , significa OR y significa AND . ${\displaystyle \neg (p\lor q)}$ ${\displaystyle \neg p\land \neg q}$ ${\displaystyle \neg }$ ${\displaystyle \lor }$ ${\displaystyle \land }$

La no disyunción se denota generalmente como o o (prefijo) o . ${\displaystyle \downarrow }$ ${\displaystyle {\overline {\vee }}}$ ${\displaystyle X}$ ${\displaystyle \operatorname {NOR} }$

Al igual que con su dual , el operador NAND (también conocido como trazo de Sheffer , simbolizado como , o ), NOR puede usarse por sí solo, sin ningún otro operador lógico, para constituir un sistema formal lógico (lo que hace que NOR sea funcionalmente completo ). ${\displaystyle \uparrow }$ ${\displaystyle \mid }$ ${\displaystyle /}$

La computadora utilizada en la nave espacial que llevó por primera vez humanos a la Luna , la Computadora de Guía Apolo , fue construida enteramente utilizando puertas NOR con tres entradas. ^[2]

Definición

La operación NOR es una operación lógica sobre dos valores lógicos , normalmente los valores de dos proposiciones , que produce un valor verdadero si y solo si ambos operandos son falsos. En otras palabras, produce un valor falso si y solo si al menos un operando es verdadero.

Tabla de verdad

La tabla de verdad de es la siguiente: ${\displaystyle A\downarrow B}$

Equivalencias lógicas

El NOR lógico es la negación de la disyunción: ${\displaystyle \downarrow }$

Notaciones y nombres alternativos

Peirce es el primero en demostrar la completitud funcional de la no disyunción, aunque no publica su resultado. ^{[3] [4]} Peirce utilizó para la no conjunción y para la no disyunción (de hecho, lo que Peirce mismo utilizó es y no lo introdujo mientras que los editores de Peirce hicieron un uso tan desambiguado). ^[4] Peirce llamó a la ${\displaystyle {\overline {\curlywedge }}}$ ${\displaystyle \curlywedge }$ ${\displaystyle \curlywedge }$ ${\displaystyle {\overline {\curlywedge }}}$ ${\displaystyle \curlywedge }$ampheck (del griego antiguo ἀμφήκης , amphēkēs , "cortante en ambos sentidos").^[4]

En 1911, Stamm  [pl] fue el primero en publicar una descripción tanto de la no conjunción (usando , el gancho de Stamm) como de la no disyunción (usando , la estrella de Stamm), y mostró su completitud funcional. ^{[5] [6]} Nótese que la mayoría de los usos en la notación lógica de usan this para la negación. ${\displaystyle \sim }$ ${\displaystyle *}$ ${\displaystyle \sim }$

En 1913, Sheffer describió la no disyunción y demostró su completitud funcional. Sheffer utilizó para la no conjunción y para la no disyunción. ${\displaystyle \mid }$ ${\displaystyle \wedge }$

En 1935, Webb describió la no disyunción para la lógica valuada y su uso para el operador. Por eso, algunas personas lo llaman operador de Webb ^[7] , operación de Webb ^[8] o función de Webb ^[9] . ${\displaystyle n}$ ${\displaystyle \mid }$

En 1940, Quine también describió la no disyunción y su uso para el operador. ^[10] Por eso algunas personas llaman al operador flecha de Peirce o daga de Quine . ${\displaystyle \downarrow }$

En 1944, Church también describió la no disyunción y el uso del operador. ^[11] ${\displaystyle {\overline {\vee }}}$

En 1954, Bocheński utilizó en para la no disyunción en notación polaca . ^[12] ${\displaystyle X}$ ${\displaystyle Xpq}$

Propiedades

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

Completitud funcional

El NOR lógico, tomado por sí mismo, es un conjunto funcionalmente completo de conectivos. ^[14] Esto se puede demostrar mostrando primero, con una tabla de verdad , que es veritativamente funcionalmente equivalente a . ^[15] Entonces, dado que es veritativamente funcionalmente equivalente a , ^[15] y es equivalente a , ^[15] el NOR lógico es suficiente para definir el conjunto de conectivos , ^[15] que se muestra como veritativamente funcionalmente completo por el Teorema de la Forma Normal Disyuntiva . ^[15] ${\displaystyle \neg A}$ ${\displaystyle A\downarrow A}$ ${\displaystyle A\downarrow B}$ ${\displaystyle \neg (A\lor B)}$ ${\displaystyle A\lor B}$ ${\displaystyle \neg (\neg A\land \neg B)}$ ${\displaystyle \{\land ,\lor ,\neg \}}$

Esto también se puede ver en el hecho de que NOR lógico no posee ninguna de las cinco cualidades (preservación de la verdad, preservación de lo falso, lineal , monótona , autodual) que deben estar ausentes en al menos un miembro de un conjunto de operadores funcionalmente completos .

Otras operaciones booleanas en términos del NOR lógico

NOR tiene la característica interesante de que todos los demás operadores lógicos pueden expresarse mediante operaciones NOR entrelazadas. El operador lógico NAND también tiene esta capacidad.

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

Véase también

• NOR bit a bit
• Álgebra de Boole
• Dominio booleano
• Función booleana
• Completitud funcional
• Puerta NOR
• Lógica proposicional
• Único operador suficiente
• Trazo de Sheffer como símbolo para la NAND lógica

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. Hall, Eldon C. (1996). Viaje a la Luna: La historia del ordenador de guía del Apolo . Reston, Virginia, EE. UU.: Instituto Americano de Aeronáutica y Astronáutica . pág. 196. ISBN. 1-56347-185-X.
3. 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.
4. 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.
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. Zach, R. (18 de febrero de 2023). "Sheffer golpe antes que Sheffer: Edward Stamm" . Consultado el 2 de julio de 2023 .
7. Webb, Donald Loomis (mayo de 1935). "Generación de cualquier lógica n-valuada mediante una operación binaria". Actas de la Academia Nacional de Ciencias . 21 (5). EE. UU.: Academia Nacional de Ciencias : 252–254. Bibcode :1935PNAS...21..252W. doi : 10.1073/pnas.21.5.252 . PMC 1076579 . PMID  16577665. 
8. Vasyukevich, Vadim O. (2011). "1.10 Propiedades de la venjunción (fórmulas básicas)". Escrito en Riga, Letonia. Operadores asincrónicos de lógica secuencial: venjunción y secuenciación: análisis y diseño de circuitos digitales . Apuntes de clase en ingeniería eléctrica (LNEE). Vol. 101 (1.ª ed.). Berlín/Heidelberg, Alemania: Springer-Verlag . pág. 20. doi :10.1007/978-3-642-21611-4. ISBN. 978-3-642-21610-7. ISSN  1876-1100. LCCN  2011929655. p. 20: Antecedentes históricos […] Operador lógico NOR llamado flecha de Peirce y también conocido como operación Webb.(xiii+1+123+7 páginas) (NB: La contraportada de este libro indica erróneamente el volumen 4, cuando en realidad es el volumen 101.)
9. Freimann, Michael; Renfro, Dave L.; Webb, Norman (2018-05-24) [2017-02-10]. "¿Quién es Donald L. Webb?". Historia de la ciencia y las matemáticas. Stack Exchange . Archivado desde el original el 2023-05-18 . Consultado el 2023-05-18 .
10. 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.
11. Church, A. (1996) [1944]. Introducción a la lógica matemática . Nueva Jersey: Princeton University Press. pág. 37.
12. Bochenski, JM (1954). Précis de logique mathématique (en francés). Países Bajos: FG Kroonder, Bussum, Pays-Bas. pag. 11.
13. Rao, G. Shanker (2006). Fundamentos matemáticos de la informática. IK International Pvt Ltd. pág. 22. ISBN 978-81-88237-49-4.
14. Smullyan, Raymond M. (1995). Lógica de primer orden . Nueva York: Dover. pp. 5, 11, 14. ISBN 978-0-486-68370-6.
15. 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.

Enlaces externos

• Medios relacionados con NOR lógico en Wikimedia Commons