stringtranslate.com

Exclusivo o

Diagrama de Venn de

La disyunción exclusiva , la disyunción exclusiva , la alternancia exclusiva , la no equivalencia lógica o la desigualdad lógica son operadores lógicos cuya negación es el bicondicional lógico . Con dos entradas, XOR es verdadero si y solo si las entradas difieren (una es verdadera, una es falsa). Con múltiples entradas, XOR es verdadero si y solo si el número de entradas verdaderas es impar . [1]

Recibe 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".

Se simboliza por el operador de prefijo [2] : 16  y por los operadores infijos 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 de la operación XOR variádica 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 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 el resultado es verdadero siempre que las entradas difieran:

Equivalencias, eliminación e introducción

La disyunción exclusiva significa esencialmente "cualquiera de los dos, pero no ambos ni ninguno". En otras palabras, la afirmación es verdadera si y solo si una es verdadera y la otra es falsa. Por ejemplo, si dos caballos están corriendo, entonces uno de los dos ganará la carrera, pero no ambos. La disyunción exclusiva , también denotada por o , puede expresarse en términos de la conjunción lógica ("y lógico", ), la disyunción ("o lógico", ) y la negación ( ) de la siguiente manera:

La disyunción exclusiva también se puede expresar de la siguiente manera:

Esta representación de XOR puede resultar útil al construir un circuito o una red, ya que tiene una sola operación y un pequeño número de operaciones y . A continuación se ofrece una prueba de esta identidad:

A veces es ú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.

El o exclusivo también equivale a la negación de un bicondicional lógico , por las reglas de implicación material (un condicional material es equivalente a la disyunción de la negación de su antecedente y su consecuencia) y equivalencia material .

En resumen, tenemos, en notación matemática y de ingeniería:

Negación del operador

Aplicando el espíritu de las leyes de De Morgan , obtenemos:

Relación con el álgebra moderna

Aunque los operadores ( conjunción ) y ( disyunción ) son muy útiles en los sistemas lógicos, carecen de una estructura más generalizable de la siguiente manera:

Los sistemas y son monoides , pero ninguno es un grupo . Lamentablemente, esto impide la combinación de estos dos sistemas en estructuras más grandes, como un anillo matemático .

Sin embargo, el sistema que utiliza o exclusivo es un grupo abeliano . La combinación de operadores y sobre elementos produce el conocido campo de dos elementos . Este campo puede representar cualquier lógica obtenible con el sistema y tiene el beneficio adicional del arsenal de herramientas de análisis algebraico para campos.

Más específicamente, si uno asocia con 0 y con 1, puede interpretar la operación lógica "AND" como multiplicación de y la operación "XOR" como suma de :

La descripción de una función booleana como un polinomio en , utilizando esta base, se denomina forma normal algebraica de la función . [3]

Exclusivo o en lenguaje natural

La disyunción suele entenderse exclusivamente en los lenguajes naturales . En inglés, la palabra disyuntiva "or" suele entenderse exclusivamente, en particular cuando se utiliza con la partícula "either". El ejemplo en inglés que se muestra a continuación normalmente se entendería en una conversación como una implicación de que Mary no es cantante y poeta. [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 "either". Por ejemplo, el primer ejemplo que se muestra a continuación muestra que "either" puede usarse felizmente en combinación con una afirmación rotunda de que ambas disyunciones son verdaderas. El segundo ejemplo muestra que la inferencia exclusiva desaparece en contextos de implicación descendente . Si la disyunción se entendiera como exclusiva en este ejemplo, dejaría abierta la posibilidad de que algunas personas comieran tanto arroz como frijoles. [4]

2. María es cantante o poeta o ambas cosas.
3. Nadie comió ni arroz ni frijoles.

Ejemplos como el anterior han motivado análisis de la inferencia de exclusividad como implicaturas conversacionales pragmáticas calculadas sobre la base de una semántica inclusiva . Las implicaturas son típicamente cancelables y no surgen en contextos de implicación descendente si su cálculo depende de la Máxima de Cantidad . Sin embargo, algunos investigadores han tratado la exclusividad como una implicación semántica genuina y han propuesto lógicas no clásicas que la validarían. [4]

Este comportamiento del verbo "or" en inglés también se encuentra en otros idiomas. Sin embargo, muchos idiomas tienen construcciones disyuntivas que son rotundamente excluyentes, 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 enfatizan en un contexto de discusión determinado. Además de la abreviatura "XOR", también se puede ver cualquiera de los siguientes símbolos:

Propiedades

Conmutatividad : sí
Asociatividad : sí
Distributividad :
La o exclusiva no distribuye sobre ninguna función binaria (ni siquiera sobre sí misma), pero la conjunción lógica distribuye sobre o exclusiva . (La conjunción y la o exclusiva forman las operaciones de multiplicación y adición de un cuerpo GF(2) , y como en todo cuerpo obedecen a la ley distributiva.)
Idempotencia : no
Monotonía : no
Preservación de la verdad: no
Cuando todas las entradas son verdaderas, la salida no es verdadera.
Preservación de la falsedad: sí
Cuando todas las entradas son falsas, la salida es falsa.
Espectro de Walsh : (2,0,0,−2)
No linealidad : 0
La función es lineal.
Involución:
Exclusiva o con una entrada especificada, en función de la otra entrada, es una función de involución o autoinversa; al aplicarla dos veces se deja la entrada variable sin cambios.

Si se utilizan valores binarios para verdadero (1) y falso (0), entonces el o exclusivo funciona exactamente como la suma módulo 2.

Ciencias de la Computación

Representación simbólica tradicional de una puerta lógica XOR

Operación bit a bit

La suma de números es la suma exclusiva de números enteros no negativos en representación binaria . También es la suma vectorial en .

La disyunción exclusiva se utiliza a menudo para operaciones bit a bit. Ejemplos:

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:

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 computadoras, es más eficiente almacenar un cero en un registro mediante la operación XOR del registro consigo mismo (los bits operados mediante la operación 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 simple y autoinversa, como en los sistemas de libreta de un solo uso o de red Feistel . [ cita requerida ] XOR también se utiliza mucho en cifrados de bloque como AES (Rijndael) o Serpent y en la implementación de cifrados de bloque (CBC, CFB, OFB o CTR).

En redes neuronales artificiales simples activadas por umbral , modelar la función XOR requiere una segunda capa porque XOR no es una función linealmente separable .

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 XOR con un bit no aleatorio dará como resultado un bit aleatorio. Se pueden combinar múltiples fuentes de datos potencialmente aleatorios utilizando XOR, y se garantiza que la imprevisibilidad del resultado sea al menos tan buena como la mejor fuente individual. [22]

En RAID 3-6 se utiliza XOR 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 mediante la operación XOR de los bytes mencionados, lo que da como resultado ( 11110000 2 ) y lo escribe en otro disco. Con este método, si se pierde alguno de los tres discos duros, el byte perdido se puede volver a crear mediante la operación XOR de bytes de los discos restantes. Por ejemplo, si se pierde el disco que contiene 01101100 2 , se puede realizar la operación XOR de 10011100 2 y 11110000 2 para recuperar el byte perdido. [23]

La operación 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, significa que se produjo un desbordamiento. La operación XOR de esos dos bits dará como resultado 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 como una curiosidad y no se recomienda en la práctica.

Las listas enlazadas XOR aprovechan las propiedades XOR para ahorrar espacio y representar estructuras de datos de listas doblemente enlazadas .

En gráficos de computadora , los métodos de dibujo basados ​​en XOR se utilizan a menudo para gestionar elementos como cuadros delimitadores y cursores en sistemas sin canales alfa o planos superpuestos.

Codificaciones

También se le llama "flecha no izquierda-derecha" ( \nleftrightarrow) en el markdown basado en LaTeX ( ). Aparte de los códigos ASCII, el operador está codificado en U+22BBXOR ( ) y U+2295CIRCLED PLUS ( ⊕, ⊕ ), ambos en operadores matemáticos de bloque .

Véase también

Notas

  1. ^ Germundsson, Roger; Weisstein, Eric. "XOR". MathWorld . Wolfram Research . Consultado el 17 de junio de 2015 .
  2. ^ 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 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.
  3. ^ Joux, Antoine (2009). "9.2: Formas normales algebraicas de funciones booleanas". Criptoanálisis algorítmico . CRC Press. pp. 285–286. ISBN 9781420070033.
  4. ^ abcd Aloni, Maria (2016). "Disyunción". En Zalta, Edward N. (ed.). The Stanford Encyclopedia of Philosophy (edición de invierno de 2016). Metaphysics Research Lab, Stanford University . Consultado el 3 de septiembre de 2020 .
  5. ^ Jennings cita a numerosos autores que afirman que la palabra "o" tiene un sentido exclusivo. Véase el capítulo 3, "El primer mito de 'o'": Jennings, RE (1994). The Genealogy of Disjunction . Nueva York: Oxford University Press.
  6. ^ ab Boole, G. (1847). El análisis matemático de la lógica, un ensayo para el cálculo del razonamiento deductivo. Cambridge/Londres: Macmillan, Barclay y Macmillan/George Bell. pág. 17.
  7. ^ Enderton, H. (2001) [1972]. Introducción matemática a la lógica (2.ª ed.). San Diego, Nueva York, Boston, Londres, Toronto, Sídney y Tokio: A Harcourt Science and Technology Company. pág. 51.
  8. ^ Rautenberg, W. (2010) [2006]. Una introducción concisa a la lógica matemática (3.ª ed.). Nueva York, Dordrecht, Heidelberg y Londres: Springer. pág. 3.
  9. ^ Ladd, Christine (1883). "Sobre el álgebra de la lógica". En Peirce, CS (ed.). Estudios de lógica por miembros de la Universidad Johns Hopkins . Boston: Little, Brown & Company. págs. 17–71.
  10. ^ 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.
  11. ^ 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.
  12. ^ ГРАДШТЕЙН, И. С. (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.
  13. ^ 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.
  14. ^ Huntington, EV (1904). "Conjuntos de postulados independientes para el álgebra de la lógica". Transactions of the American Mathematical Society . 5 (3): 288–309. doi :10.1090/S0002-9947-1904-1500675-4.
  15. ^ 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 .
  16. ^ 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". Transactions of the American Mathematical Society . 35 (1): 274–304.
  17. ^ Church, A. (1996) [1944]. Introducción a la lógica matemática . Nueva Jersey: Princeton University Press. pág. 37.
  18. ^ Craig, Edward (1998). Enciclopedia de filosofía de Routledge, volumen 8. Taylor & Francis . pág. 496. ISBN 978-0-41507310-3.
  19. ^ Łukasiewicz, enero (1929). Elementy logiki matematycznej [ Elementos de lógica matemática ] (en polaco) (1 ed.). Varsovia, Polonia: Państwowe Wydawnictwo Naukowe .
  20. ^ Kernighan, Brian W. ; Ritchie, Dennis M. (1978). "2.9: Operadores lógicos bit a bit". El lenguaje de programación C . Prentice-Hall. págs. 44–46.
  21. ^ Weisstein, Eric W. "Diferencia simétrica". MathWorld .
  22. ^ Davies, Robert B (28 de febrero de 2002). «Exclusive OR (XOR) and hardware random number generators» (PDF) . Consultado el 28 de agosto de 2013 .
  23. ^ Nobel, Rickard (26 de julio de 2011). «Cómo funciona RAID 5 en realidad» . Consultado el 23 de marzo de 2017 .

Enlaces externos