Exclusivo o disyunción exclusiva , alternancia exclusiva , no equivalencia lógica o desigualdad lógica es un operador lógico cuya negación es el bicondicional lógico . Con dos entradas, XOR es verdadero si y sólo si las entradas difieren (una es verdadera y la otra es falsa). Con múltiples entradas, XOR es verdadero si y solo si el número de entradas verdaderas es impar . [1]
Obtiene el nombre de "o exclusivo" porque el significado de "o" es ambiguo cuando ambos operandos son verdaderos. XOR excluye ese caso. Algunas formas informales de describir XOR son "uno o el otro pero no ambos", "uno o el otro" y "A o B, pero no A y B".
Está simbolizado por el operador de prefijo [2] : 16 y por los operadores de infijo XOR ( / ˌ ɛ k s ˈ ɔː r / , / ˌ ɛ k s ˈ ɔː / , / ˈ k s ɔː r / o / ˈ k s ɔː / ), EOR , EXOR , , , , ⩛ , , , y .
Definición
Cada fila de esta matriz binaria de Walsh es la tabla de verdad del XOR variado de los argumentos que se muestran a la izquierda. Por ejemplo, la fila AB corresponde al diagrama de Venn de 2 círculos y la fila ABC al diagrama de Venn de 3 círculos que se muestra arriba. (Como en los diagramas de Venn, el blanco es falso y el rojo es verdadero).
La tabla de verdad de muestra que genera verdadero siempre que las entradas difieren:
Equivalencias, eliminación e introducción
La disyunción exclusiva significa esencialmente "uno, pero no ambos ni ninguno". En otras palabras, el enunciado es verdadero si y sólo si uno es verdadero y el otro es falso. Por ejemplo, si dos caballos compiten, uno de los dos ganará la carrera, pero no ambos. La disyunción exclusiva , también denotada por o , se puede expresar en términos de la conjunción lógica ("lógica y", ), la disyunción ("lógica o", ) y la negación ( ) de la siguiente manera:
La disyunción exclusiva también puede expresarse de la siguiente manera:
Esta representación de XOR puede resultar útil al construir un circuito o red, porque tiene una sola operación y un pequeño número de operaciones . Una prueba de esta identidad se proporciona a continuación:
A veces resulta útil escribir de la siguiente manera:
o:
Esta equivalencia se puede establecer aplicando las leyes de De Morgan dos veces a la cuarta línea de la prueba anterior.
En resumen, tenemos, en notación matemática y de ingeniería:
Negación del operador
Se puede aplicar el espíritu de las leyes de De Morgan, tenemos:
Relación con el álgebra moderna
Aunque los operadores ( conjunción ) y ( disyunción ) son muy útiles en sistemas lógicos, fallan en una estructura más generalizable de la siguiente manera:
Los sistemas y son monoides , pero ninguno es un grupo . Desafortunadamente, esto impide la combinación de estos dos sistemas en estructuras más grandes, como por ejemplo un anillo matemático .
Sin embargo, el sistema que utiliza or exclusivo es un grupo abeliano . La combinación de operadores y sobreelementos produce el conocido campo de dos elementos . Este campo puede representar cualquier lógica que se pueda obtener con el sistema y tiene el beneficio adicional del arsenal de herramientas de análisis algebraico para campos.
Más específicamente, si se asocia con 0 y con 1, se puede interpretar la operación lógica "Y" como una multiplicación y la operación "XOR" como una suma :
La disyunción suele entenderse exclusivamente en las lenguas naturales . En inglés, la palabra disyuntiva "or" a menudo se entiende exclusivamente, particularmente cuando se usa con la partícula "cualquiera". Normalmente, en una conversación, se entendería que el siguiente ejemplo en inglés implica que Mary no es cantante y poeta a la vez. [4] [5]
1. María es cantante o poeta.
Sin embargo, la disyunción también puede entenderse de manera inclusiva, incluso en combinación con "cualquiera". Por ejemplo, el primer ejemplo a continuación muestra que "cualquiera" puede usarse felizmente en combinación con una afirmación directa de que ambas disyunciones son verdaderas. El segundo ejemplo muestra que la inferencia excluyente se desvanece en contextos vinculantes descendentes . Si en este ejemplo la disyunción se entendiera como exclusiva, dejaría abierta la posibilidad de que algunas personas comieran tanto arroz como frijoles. [4]
Este comportamiento del inglés "or" también se encuentra en otros idiomas. Sin embargo, muchas lenguas tienen construcciones disyuntivas que son fuertemente exclusivas, como el francés soit... soit . [4]
Símbolos alternativos
El símbolo utilizado para la disyunción exclusiva varía de un campo de aplicación a otro, e incluso depende de las propiedades que se destacan en un contexto de discusión determinado. Además de la abreviatura "XOR", también podrá verse cualquiera de los siguientes símbolos:
fue utilizado por George Boole en 1847. [6] Aunque Boole lo usó principalmente en clases, también consideró el caso de que sean proposiciones en , y en ese momento es un conectivo. Además, Boole lo utilizó exclusivamente. Aunque tal uso no muestra la relación entre disyunción inclusiva (para la cual se usa casi fijamente hoy en día) y disyunción exclusiva, y también puede generar confusiones con sus otros usos, algunos libros de texto clásicos y modernos aún mantienen dicho uso. [7] [8]
fue utilizado por Christine Ladd-Franklin en 1883. [9] En sentido estricto, Ladd solía expresar " is-not " o "No is ", es decir, utilizados como exclusiones, aunque implícitamente tiene el significado de disyunción exclusiva ya que el artículo se titula como "Sobre el álgebra de la lógica".
, que denota la negación de equivalencia , fue utilizado por Ernst Schröder en 1890, [10] : 307 Aunque el uso de como equivalencia podría remontarse a George Boole en 1847, [6] durante los 40 años posteriores a Boole, sus seguidores, como como Charles Sanders Peirce , Hugh MacColl , Giuseppe Peano, etc., no lo usaron como no equivalencia literalmente, lo que posiblemente se deba a que podría definirse fácilmente a partir de la negación y la equivalencia.
Fue utilizado por Giuseppe Peano en 1894: " . El signo corresponde al latín aut ; el signo a vel ". [11] : 10 Nótese que la palabra latina "aut" significa "o exclusivo" y "vel" significa "o inclusivo", y que Peano la usa como disyunción inclusiva.
fue utilizado por Izrail Solomonovich Gradshtein (Израиль Соломонович Градштейн) en 1936. [12] : 76
fue utilizado por Claude Shannon en 1938. [13] Shannon tomó prestado el símbolo como disyunción exclusiva de Edward Vermilye Huntington en 1904. [14] Huntington tomó prestado el símbolo de Gottfried Wilhelm Leibniz en 1890 (la fecha original no se conoce con certeza, pero es casi seguro está escrito después de 1685; y 1890 es la época de publicación). [15] Mientras que tanto Huntington en 1904 como Leibniz en 1890 utilizaron el símbolo como una operación algebraica. Además, Huntington en 1904 utilizó el símbolo también como disyunción inclusiva (suma lógica), y en 1933 lo utilizó como disyunción inclusiva. [dieciséis]
(como operador de prefijo , ) fue utilizado por Józef Maria Bocheński en 1949. [2] : 16 Alguien [18] puede confundir que fue Jan Łukasiewicz quien fue el primero en utilizar para disyunción exclusiva (parece que el error se extiende ampliamente) , mientras que ni en 1929 [19] ni en otras obras Łukasiewicz hizo tal uso. De hecho, en 1949 Bocheński introdujo un sistema de notación polaca que nombra los 16 conectivos binarios de la lógica clásica, que es una extensión compatible de la notación de Łukasiewicz en 1929, y en la que apareció por primera vez para disyunción exclusiva. El uso que hace Bocheński de como disyunción exclusiva no tiene relación con el polaco "alternatywa rozłączna" de "exclusivo o" y es un accidente, para lo cual consulte la tabla en la página 16 del libro de 1949.
El or exclusivo no se distribuye sobre ninguna función binaria (ni siquiera sobre sí mismo), pero la conjunción lógica se distribuye sobre el or exclusivo . (Conjunción y exclusiva o forman las operaciones de multiplicación y suma de un campo GF(2) , y como en cualquier campo obedecen a la ley distributiva.)
Exclusiva o con una entrada especificada, en función de la otra entrada, es una función de involución o autoinversa; aplicarlo dos veces deja la entrada variable sin cambios.
Si usa valores binarios para verdadero (1) y falso (0), entonces exclusivo o funciona exactamente como la suma módulo 2.
La disyunción exclusiva se utiliza a menudo para operaciones bit a bit. Ejemplos:
1XO 1 = 0
1XO 0 = 1
0 XO 1 = 1
0 XO 0 = 0
1110 2 XOR 1001 2 = 0111 2 (esto es equivalente a la suma sin acarreo )
Como se señaló anteriormente, dado que la disyunción exclusiva es idéntica a la suma módulo 2, la disyunción exclusiva bit a bit de dos cadenas de n bits es idéntica al vector estándar de suma en el espacio vectorial .
En informática, la disyunción exclusiva tiene varios usos:
Indica si dos bits son desiguales.
Es un bit-flipper opcional (la entrada decisiva elige si se invierte la entrada de datos).
En circuitos lógicos, se puede hacer un sumador simple con una puerta XOR para sumar los números y una serie de puertas AND, OR y NOT para crear la salida de acarreo.
En algunas arquitecturas de computadora, es más eficiente almacenar un cero en un registro aplicando XOR al registro consigo mismo (los bits XOR consigo mismos siempre son cero) que cargar y almacenar el valor cero.
En criptografía , XOR se utiliza a veces como una función de mezcla autoinversa simple, como en los sistemas de red de un solo uso o Feistel . [ cita necesaria ] XOR también se usa mucho en cifrados de bloques como AES (Rijndael) o Serpent y en la implementación de cifrado de bloques (CBC, CFB, OFB o CTR).
De manera similar, XOR se puede utilizar para generar grupos de entropía para generadores de números aleatorios de hardware . La operación XOR preserva la aleatoriedad, lo que significa que un bit aleatorio sometido a XOR con un bit no aleatorio dará como resultado un bit aleatorio. Se pueden combinar múltiples fuentes de datos potencialmente aleatorios usando XOR, y se garantiza que la imprevisibilidad de la salida será al menos tan buena como la mejor fuente individual. [22]
XOR se utiliza en RAID 3–6 para crear información de paridad. Por ejemplo, RAID puede "hacer una copia de seguridad" de los bytes 10011100 2 y 01101100 2 de dos (o más) discos duros realizando una operación XOR de los bytes recién mencionados, lo que da como resultado ( 11110000 2 ) y escribiéndolo en otra unidad. Con este método, si se pierde cualquiera de los tres discos duros, el byte perdido se puede volver a crear aplicando XOR en bytes de los discos restantes. Por ejemplo, si se pierde la unidad que contiene 01101100 2 , se puede realizar una operación XOR a 10011100 2 y 11110000 2 para recuperar el byte perdido. [23]
XOR también se utiliza para detectar un desbordamiento en el resultado de una operación aritmética binaria con signo. Si el bit retenido más a la izquierda del resultado no es el mismo que el número infinito de dígitos a la izquierda, entonces eso significa que se produjo un desbordamiento. XORing esos dos bits dará un "1" si hay un desbordamiento.
XOR se puede utilizar para intercambiar dos variables numéricas en computadoras, utilizando el algoritmo de intercambio XOR ; sin embargo, esto se considera más bien una curiosidad y no se fomenta en la práctica.
También se le llama "flecha no izquierda-derecha" ( \nleftrightarrow) en rebajas basadas en LaTeX ( ). Aparte de los códigos ASCII, el operador está codificado en U+22BB ⊻ XOR ( ⊻ ) y U+2295 ⊕ CIRCLED PLUS ( ⊕, ⊕ ), ambos en operadores matemáticos en bloque .
^ ab Bocheński, JM (1949). Précis de logique mathématique (PDF) (en francés). Países Bajos: FG Kroonder, Bussum, Pays-Bas.Traducido como Bocheński, JM (1959). Un resumen de la lógica matemática . Traducido por Bird, O. Dordrecht, Holanda: D. Reidel Publishing Company. doi :10.1007/978-94-017-0592-9. ISBN 978-90-481-8329-6.
^ Joux, Antoine (2009). "9.2: Formas normales algebraicas de funciones booleanas". Criptoanálisis algorítmico . Prensa CRC. págs. 285–286. ISBN9781420070033.
^ abcd Aloni, María (2016). "Disyunción". En Zalta, Edward N. (ed.). La Enciclopedia de Filosofía de Stanford (edición de invierno de 2016). Laboratorio de Investigación en Metafísica, Universidad de Stanford . Consultado el 3 de septiembre de 2020 .
^ Jennings cita a numerosos autores que dicen que la palabra "o" tiene un sentido exclusivo. Véase el Capítulo 3, "El primer mito del 'O'": Jennings, RE (1994). La genealogía de la disyunción . Nueva York: Oxford University Press.
^ ab Boole, G. (1847). El análisis matemático de la lógica, como ensayo hacia el cálculo del razonamiento deductivo. Cambridge/Londres: Macmillan, Barclay y Macmillan/George Bell. pag. 17.
^ Enderton, H. (2001) [1972]. Una introducción matemática a la lógica (2 ed.). San Diego, Nueva York, Boston, Londres, Toronto, Sydney y Tokio: una empresa de ciencia y tecnología de Harcourt. pag. 51.
^ Rautenberg, W. (2010) [2006]. Una introducción concisa a la lógica matemática (3 ed.). Nueva York, Dordrecht, Heidelberg y Londres: Springer. pag. 3.
^ Ladd, Christine (1883). "Sobre el álgebra de la lógica". En Peirce, CS (ed.). Estudios de lógica realizados por miembros de la Universidad Johns Hopkins . Boston: Little, Brown & Company. págs. 17–71.
^ Schröder, E. (1890). Vorlesungen über die Algebra der Logik (Exakte Logik), Erster Band (en alemán). Leipzig: Druck und Verlag BG Teubner.Reimpreso por Thoemmes Press en 2000.
^ Peano, G. (1894). Notaciones de lógica matemática. Introducción al formulario de matemáticas . Turín: Fratelli Boccna. Reimpreso en Peano, G. (1958). Ópera Scelte, Volumen II. Roma: Edizioni Cremonese. págs. 123-176.
^ ГРАДШТЕЙН, И. С. (1959) [1936]. ПРЯМАЯ И ОБРАТНАЯ ТЕОРЕМЫ: ЭЛЕМЕНТЫ АЛГЕБРЫ ЛОГИКИ (en ruso) (3 ed.). МОСКВА: ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО ФИЗИКа-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУ РЫ.Traducido como Gradshtein, IS (1963). Teoremas directos y recíprocos: los elementos de la lógica simbólica . Traducido por Boddington, T. Oxford, Londres, Nueva York y París: Pergamon Press.
^ Shannon, CE (1938). "Un análisis simbólico de circuitos de conmutación y relés" (PDF) . Transacciones del Instituto Americano de Ingenieros Eléctricos . 57 (12): 713–723. doi :10.1109/T-AIEE.1938.5057767. hdl : 1721.1/11173 . S2CID 51638483.
^ Huntington, EV (1904). "Conjuntos de postulados independientes para el álgebra de la lógica". Transacciones de la Sociedad Matemática Estadounidense . 5 (3): 288–309. doi :10.1090/S0002-9947-1904-1500675-4.
^ Leibniz, GW (1890) [16??/17??]. Gerhardt, CI (ed.). Die philosophischen Schriften, Siebter Band (en alemán). Berlín: Weidmann. pag. 237 . Consultado el 7 de julio de 2023 .
^ Huntington, EV (1933). "Nuevos conjuntos de postulados independientes para el álgebra de la lógica, con especial referencia a los Principia Mathematica de Whitehead y Russell". Transacciones de la Sociedad Matemática Estadounidense . 35 (1): 274–304.
^ Iglesia, A. (1996) [1944]. Introducción a la Lógica Matemática . Nueva Jersey: Prensa de la Universidad de Princeton. pag. 37.
^ Davies, Robert B (28 de febrero de 2002). "Generadores de números aleatorios de hardware y OR exclusivos (XOR)" (PDF) . Consultado el 28 de agosto de 2013 .
^ Nobel, Rickard (26 de julio de 2011). "Cómo funciona realmente RAID 5" . Consultado el 23 de marzo de 2017 .
enlaces externos
Wikimedia Commons tiene medios relacionados con la disyunción exclusiva .
Busque exclusivo o o XOR en Wikcionario, el diccionario gratuito.
Todo sobre XOR
Pruebas de propiedades XOR y aplicaciones de XOR, CS103: Fundamentos matemáticos de la informática, Universidad de Stanford