Exclusivo o

Este artículo necesita citas adicionales para su verificación . Por favor, ayude a mejorar este artículo añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «Exclusivo o» – noticias  · periódicos  · libros  · académico  · JSTOR ( mayo de 2013 ) ( Aprenda cómo y cuándo eliminar este mensaje )

Exclusivo o

O-X
Tabla de verdad	${\estilo de visualización (0110)}$
Puerta lógica
Formas normales
Disyuntivo	${\displaystyle {\overline {x}}\cdot y+x\cdot {\overline {y}}}$
Conjuntivo	${\displaystyle ({\overline {x}}+{\overline {y}})\cdot (x+y)}$
Polinomio de Zhegalkin	${\displaystyle x\omás y}$
Las celosías del poste
0-conservación	Sí
1-conservación	No
Monótono	No
Afín	Sí
Auto-dual	No
en a mi

Conectivas lógicas
NO ${\displaystyle \neg A}$,${\estilo de visualización -A}$,${\displaystyle {\overline {A}}}$,${\displaystyle \sim A}$ Y ${\estilo de visualización A\y B}$,${\displaystyle A\cdot B}$, ${\displaystyle AB}$, ${\displaystyle A\&B}$, ${\displaystyle A\&\&B}$ NAND ${\displaystyle A{\overline {\land }}B}$, ${\displaystyle A\uparrow B}$, ${\displaystyle A\mid B}$, ${\displaystyle {\overline {A\cdot B}}}$ OR ${\displaystyle A\lor B}$, ${\displaystyle A+B}$, ${\displaystyle A\mid B}$, ${\displaystyle A\parallel B}$ NOR ${\displaystyle A{\overline {\lor }}B}$, ${\displaystyle A\downarrow B}$, ${\displaystyle {\overline {A+B}}}$ XNOR ${\displaystyle A\ {\text{XNOR}}\ B}$ └ equivalent ${\displaystyle A\equiv B}$, ${\displaystyle A\Leftrightarrow B}$, ${\displaystyle A\leftrightharpoons B}$ XOR ${\displaystyle A{\underline {\lor }}B}$, ${\displaystyle A\oplus B}$ └nonequivalent ${\displaystyle A\not \equiv B}$, ${\displaystyle A\not \Leftrightarrow B}$, ${\displaystyle A\nleftrightarrow B}$ implies ${\displaystyle A\Rightarrow B}$, ${\displaystyle A\supset B}$, ${\displaystyle A\rightarrow B}$ converse ${\displaystyle A\Leftarrow B}$, ${\displaystyle A\subset B}$, ${\displaystyle A\leftarrow B}$
Related concepts
Propositional calculus Predicate logic Boolean algebra Truth table Truth function Boolean function Functional completeness Scope (logic)
Applications
Digital logic Programming languages Mathematical logic Philosophy of logic
Category
v t e

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 .${\displaystyle J}$ ${\displaystyle {\dot {\vee }}}$${\displaystyle {\overline {\vee }}}$${\displaystyle {\underline {\vee }}}$${\displaystyle \oplus }$${\displaystyle \nleftrightarrow }$${\displaystyle \not \equiv }$

La tabla de verdad de muestra que el resultado es verdadero siempre que las entradas difieran:${\displaystyle A\oplus B}$

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\oplus B}$
F	F	F
F	yo	yo
yo	F	yo
yo	yo	F

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:${\displaystyle p\nleftrightarrow q}$${\displaystyle p\operatorname {?} q}$${\displaystyle Jpq}$${\displaystyle \wedge }$${\displaystyle \lor }$${\displaystyle \lnot }$

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\lor q)\land \lnot (p\land q)\end{matrix}}}$

La disyunción exclusiva también se puede expresar de la siguiente manera:${\displaystyle p\nleftrightarrow q}$

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\land \lnot q)\lor (\lnot p\land q)\end{matrix}}}$

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:${\displaystyle \lnot }$${\displaystyle \land }$${\displaystyle \lor }$

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\land \lnot q)&\lor &(\lnot p\land q)\\[3pt]&=&((p\land \lnot q)\lor \lnot p)&\land &((p\land \lnot q)\lor q)\\[3pt]&=&((p\lor \lnot p)\land (\lnot q\lor \lnot p))&\land &((p\lor q)\land (\lnot q\lor q))\\[3pt]&=&(\lnot p\lor \lnot q)&\land &(p\lor q)\\[3pt]&=&\lnot (p\land q)&\land &(p\lor q)\end{matrix}}}$

A veces es útil escribir de la siguiente manera:${\displaystyle p\nleftrightarrow q}$

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&\lnot ((p\land q)\lor (\lnot p\land \lnot q))\end{matrix}}}$

o:

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\lor q)\land (\lnot p\lor \lnot q)\end{matrix}}}$

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:

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\land \lnot q)&\lor &(\lnot p\land q)&=&p{\overline {q}}+{\overline {p}}q\\[3pt]&=&(p\lor q)&\land &(\lnot p\lor \lnot q)&=&(p+q)({\overline {p}}+{\overline {q}})\\[3pt]&=&(p\lor q)&\land &\lnot (p\land q)&=&(p+q)({\overline {pq}})\end{matrix}}}$

Aplicando el espíritu de las leyes de De Morgan , obtenemos:$${\displaystyle \lnot (p\nleftrightarrow q)\Leftrightarrow \lnot p\nleftrightarrow q\Leftrightarrow p\nleftrightarrow \lnot q.}$$

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:${\displaystyle \wedge }$${\displaystyle \lor }$

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 .${\displaystyle (\{T,F\},\wedge )}$${\displaystyle (\{T,F\},\lor )}$

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.${\displaystyle (\{T,F\},\oplus )}$ ${\displaystyle \wedge }$${\displaystyle \oplus }$${\displaystyle \{T,F\}}$${\displaystyle \mathbb {F} _{2}}$${\displaystyle (\land ,\lor )}$

Más específicamente, si uno asocia con 0 y con 1, puede interpretar la operación lógica "AND" como multiplicación en y la operación "XOR" como suma en :${\displaystyle F}$${\displaystyle T}$${\displaystyle \mathbb {F} _{2}}$${\displaystyle \mathbb {F} _{2}}$

${\displaystyle {\begin{matrix}r=p\land q&\Leftrightarrow &r=p\cdot q{\pmod {2}}\\[3pt]r=p\oplus q&\Leftrightarrow &r=p+q{\pmod {2}}\\\end{matrix}}}$

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]${\displaystyle \mathbb {F} _{2}}$

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]

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:

• ${\displaystyle +}$fue utilizado por George Boole en 1847. ^[6] Aunque Boole lo utilizó 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 la disyunción inclusiva (para la cual se usa casi fijamente hoy en día) y la disyunción exclusiva, y también puede provocar confusiones con sus otros usos, algunos libros de texto clásicos y modernos aún mantienen tal uso. ^{[7] [8]}${\displaystyle +}$${\displaystyle x,y}$${\displaystyle x+y}$${\displaystyle +}$${\displaystyle \vee }$
• ${\displaystyle {\overline {\vee }}}$fue utilizado por Christine Ladd-Franklin en 1883. ^[9] Estrictamente hablando, Ladd solía expresar " no es " o "No es ", es decir, se utiliza como exclusiones, mientras que implícitamente tiene el significado de disyunción exclusiva ya que el artículo se titula como "Sobre el álgebra de la lógica".${\displaystyle A\operatorname {\overline {\vee }} B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle {\overline {\vee }}}$${\displaystyle {\overline {\vee }}}$
• ${\displaystyle \not =}$, que denota la negación de la 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 Charles Sanders Peirce , Hugh MacColl , Giuseppe Peano , etc., no utilizaron como no equivalencia literalmente, posiblemente porque podría definirse a partir de la negación y la equivalencia fácilmente.${\displaystyle =}$${\displaystyle \not =}$
• ${\displaystyle \circ }$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 utiliza como disyunción inclusiva.${\displaystyle a\circ b=a-b\,\cup \,b-a}$${\displaystyle \circ }$${\displaystyle \cup }$${\displaystyle \cup }$
• ${\displaystyle \vee \vee }$fue utilizado por Izrail Solomonovich Gradshtein (Израиль Соломонович Градштейн) en 1936. ^{[12] : 76}
• ${\displaystyle \oplus }$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 que está escrito después de 1685; y 1890 es el momento 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 como disyunción inclusiva (suma lógica) también, y en 1933 lo utilizó como disyunción inclusiva. ^[16]${\displaystyle +}$
• ${\displaystyle \not \equiv }$, que también denota la negación de la equivalencia , fue utilizado por Alonzo Church en 1944. ^[17]
• ${\displaystyle J}$(como operador de prefijo , ) fue utilizado por Józef Maria Bocheński en 1949. ^{[2] : 16} Alguien ^[18] puede confundirse pensando que es Jan Łukasiewicz quien es el primero en utilizar para la 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 para la disyunción exclusiva apareció por primera vez. El uso de Bocheński de como disyunción exclusiva no tiene relación con el "alternatywa rozłączna" polaco de "o exclusivo" y es un accidente para el que véase la tabla en la página 16 del libro en 1949.${\displaystyle J\phi \psi }$${\displaystyle J}$${\displaystyle J}$${\displaystyle J}$
• ^, el símbolo de intercalación , se ha utilizado en varios lenguajes de programación para denotar el operador exclusivo o bit a bit , comenzando con C ^[20] y también incluyendo C++ , C# , D , Java , Perl , Ruby , PHP y Python .
• La diferencia simétrica de dos conjuntos y , que puede interpretarse como su o exclusivo de cada elemento, se ha denotado de diversas formas como , , o . ^[21]${\displaystyle S}$${\displaystyle T}$${\displaystyle S\ominus T}$${\displaystyle S\mathop {\triangledown } T}$${\displaystyle S\mathop {\vartriangle } T}$

Conmutatividad : sí

${\displaystyle A\oplus B}$	${\displaystyle \Leftrightarrow }$	${\displaystyle B\oplus A}$
	${\displaystyle \Leftrightarrow }$

Asociatividad : si

${\displaystyle ~A}$	${\displaystyle ~~~\oplus ~~~}$	${\displaystyle (B\oplus C)}$	${\displaystyle \Leftrightarrow }$			${\displaystyle (A\oplus B)}$	${\displaystyle ~~~\oplus ~~~}$	${\displaystyle ~C}$
	${\displaystyle ~~~\oplus ~~~}$		${\displaystyle \Leftrightarrow }$		${\displaystyle \Leftrightarrow }$		${\displaystyle ~~~\oplus ~~~}$

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.)${\displaystyle C\land (A\oplus B)=(C\land A)\oplus (C\land B)}$

Idempotencia : no

${\displaystyle ~A~}$	${\displaystyle ~\oplus ~}$	${\displaystyle ~A~}$	${\displaystyle \Leftrightarrow }$	${\displaystyle ~0~}$	${\displaystyle \nLeftrightarrow }$	${\displaystyle ~A~}$
	${\displaystyle ~\oplus ~}$		${\displaystyle \Leftrightarrow }$		${\displaystyle \nLeftrightarrow }$

Monotonía : no

${\displaystyle A\rightarrow B}$	${\displaystyle \nRightarrow }$			${\displaystyle (A\oplus C)}$	${\displaystyle \rightarrow }$	${\displaystyle (B\oplus C)}$
	${\displaystyle \nRightarrow }$		${\displaystyle \Leftrightarrow }$		${\displaystyle \rightarrow }$

Preservación de la verdad: no

Cuando todas las entradas son verdaderas, la salida no es verdadera.

${\displaystyle A\land B}$	${\displaystyle \nRightarrow }$	${\displaystyle A\oplus B}$
	${\displaystyle \nRightarrow }$

Preservación de la falsedad: sí

Cuando todas las entradas son falsas, la salida es falsa.

${\displaystyle A\oplus B}$	${\displaystyle \Rightarrow }$	${\displaystyle A\lor B}$
	${\displaystyle \Rightarrow }$

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.

${\displaystyle ~A\oplus B~}$	${\displaystyle ~\oplus ~}$	${\displaystyle ~B~}$	${\displaystyle \Leftrightarrow }$	${\displaystyle ~A~}$
	${\displaystyle ~\oplus ~}$		${\displaystyle \Leftrightarrow }$

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

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

• 1 XOR 1 = 0
• 1 XOR 0 = 1
• 0 XOR 1 = 1
• 0 XOR 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 .${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$

En informática, la disyunción exclusiva tiene varios usos:

• Indica si dos bits son desiguales.
• Es un inversor de bits controlable (la entrada de control elige si invertir o no la entrada de datos).
• Indica si hay un número impar de bits 1 ( es verdadero si y solo si un número impar de variables es verdadero), que es igual al bit de paridad devuelto por una función de paridad .${\displaystyle A\oplus B\oplus C\oplus D\oplus E}$

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.

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+22BB ⊻ XOR ( ⊻ ) y U+2295 ⊕ CIRCLED PLUS ( ⊕, ⊕ ), ambos en operadores matemáticos de bloque .${\displaystyle \nleftrightarrow }$

Wikimedia Commons tiene medios relacionados con Disyunción exclusiva .

Busque exclusivo o  o XOR en Wikcionario, el diccionario libre.

• Todo sobre XOR
• Demostraciones de propiedades XOR y aplicaciones de XOR, CS103: Fundamentos matemáticos de la informática, Universidad de Stanford