Exclusivo o

Diagrama de Venn ${displaystyle scriptstyle Aoplus Boplus C}$

O exclusivo o disyunción exclusiva es una operación lógica que es verdadera si y solo si sus argumentos difieren (uno es verdadero, el otro es falso).

Es simbolizado por el operador de prefijo J y por los operadores de infijo XOR (, o) EOR, EXOR, ⊻, ⩒, ⩛, ⊕, ${displaystyle nleftrightarrow }$, y ≢. La negación de XOR es la lógica bicondicional, que produce verdad si y sólo si las dos entradas son las mismas.

Obtiene el nombre "exclusivo o" porque el significado de "o" es ambiguo cuando ambos operandos son verdaderos; el operador exclusivo o excluye ese caso. Esto a veces se considera como "uno o el otro pero no ambos". Esto podría escribirse como "A o B, pero no, A y B".

Dado que es asociativo, puede considerarse un operador n-ario que es verdadero si y solo si un número impar de argumentos es verdadero. Es decir, a XOR b XOR... puede tratarse como XOR(a,b,...).

Tabla de verdad

Argumentos a la izquierda combinados por XOR. Esta es una matriz binaria de Walsh (cf. código Hadamard).

La tabla de verdad de A XOR B muestra que da como resultado verdadero cada vez que las entradas difieren:

${displaystyle A}$	${displaystyle B}$	${displaystyle Aoplus B}$
Falso	Falso	Falso
Falso	Cierto.	Cierto.
Cierto.	Falso	Cierto.
Cierto.	Cierto.	Falso

Equivalencias, eliminación e introducción

La disyunción exclusiva significa esencialmente 'ya sea uno, pero no ambos ni ninguno'. En otras palabras, la declaración es verdadera si y sólo si uno es verdadero y el otro es falso. Por ejemplo, si dos caballos están corriendo, entonces uno de los dos ganará la carrera, pero no ambos. La disyunción exclusiva ${displaystyle pnleftrightarrow q}$, también denotado por ${displaystyle p}$ ? ${displaystyle q}$ o ${displaystyle operatorname {J} pq}$, se puede expresar en términos de la conjunción lógica ("lógica y", ${displaystyle wedge }$), la disyunción ("lógica o", ${displaystyle lor }$), y la negación (${displaystyle lnot }$) como sigue:

${displaystyle {begin{matrix}pnleftrightarrow q divide= got(plor q)land lnot (pland q)end{matrix}}}$

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

${displaystyle {begin{matrix}pnleftrightarrow q divide= got(pland lnot q)lor (lnot pland q)end{matrix}}}$

Esta representación de XOR se puede encontrar útil cuando se construye un circuito o red, porque sólo tiene uno ${displaystyle lnot }$ funcionamiento y pequeño número de ${displaystyle wedge }$ y ${displaystyle lor }$ operaciones. A continuación se presenta una prueba de esta identidad:

${fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}fnMicrosoft Sans Serif}fn)}cH3cH0fnMicrosoft Sans Ser)cH3cH3cH3cH0cH3pcH00cH0cH00cH0cH00cH0cH00cH00cH3cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00p]cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH0cH00cH00cH00cH003$

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

${displaystyle {begin{matrix}pnleftrightarrow q divide= gotlnot ((pland q)lor (lnot pland lnot q))end{matrix}}}$

o:

${displaystyle {begin{matrix}pnleftrightarrow q limit= limite(plor q)land (lnot plor 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 equivale 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}pnleftrightarrow q logro= discípulo(pland lnot q) limitadalor >(lnot pland q) {q}}+{overline {p}q[3pt] limite= limite(plor q) círculoland &(lnot plor lnot q) correspond=cl(p+q)({overline {p}+{ncipi)}[3pt] {p}p}p}pp}p} {m} {p}mcH00} {cH00}c]$

Negación

El espíritu de las leyes de De Morgan se puede aplicar, tenemos:

$${displaystyle lnot (pnleftrightarrow q)=lnot pnleftrightarrow q=pnleftrightarrow lnot q}$$

Relación con el álgebra moderna

Aunque los operadores ${displaystyle wedge }$ (conjunción) y ${displaystyle lor }$ (disyunción) son muy útiles en los sistemas lógicos, fallan una estructura más generalizable de la siguiente manera:

Los sistemas ${displaystyle ({T,F},wedge)}$ y ${displaystyle ({T,F},lor)}$ son monoides, pero tampoco un grupo. Desafortunadamente esto evita la combinación de estos dos sistemas en estructuras más grandes, como un anillo matemático.

Sin embargo, el sistema usando exclusiva o ${displaystyle ({T,F},oplus)}$ es un grupo abeliano. La combinación de operadores ${displaystyle wedge }$ y ${displaystyle oplus }$ sobre elementos ${displaystyle {T,F}}$ producir el campo conocido ${displaystyle F_{2}$. Este campo puede representar cualquier lógica obtenible con el sistema ${displaystyle (landlor)}$ y tiene el beneficio añadido del arsenal de herramientas de análisis algebraicos para campos.

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

${displaystyle {begin{Matrix}r=pland q {pmod2}[3pt]r=poplus q limiteleftrightarrow &r=p+q{pmod {2}\end{Matrix}$

El uso de esta base para describir un sistema booleano se denomina forma normal algebraica.

Exclusivo o en lenguaje natural

La disyunción a menudo se entiende exclusivamente en lenguajes naturales. En inglés, la palabra disyuntiva "or" a menudo se entiende exclusivamente, particularmente cuando se usa con la partícula "cualquiera". El siguiente ejemplo en inglés normalmente se entendería en una conversación como si implicara que Mary no es tanto cantante como poeta.

1. Mary es cantante o poeta.

Sin embargo, la disyunción también se puede entender de manera inclusiva, incluso en combinación con "cualquiera de los dos". Por ejemplo, el primer ejemplo a continuación muestra que "ya sea" se puede usar acertadamente en combinación con una declaración directa de que ambas disyuntivas son verdaderas. El segundo ejemplo muestra que la inferencia exclusiva se desvanece en contextos con 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.

2. María es cantante o poeta o ambos.

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 suelen ser cancelables y no surgen en contextos descendentes si su cálculo depende de la Máxima de Cantidad. Sin embargo, algunos investigadores han tratado la exclusividad como una vinculación semántica de buena fe y han propuesto lógicas no clásicas que la validarían.

Este comportamiento del inglés "or" también se encuentra en otros idiomas. Sin embargo, muchos idiomas tienen construcciones disyuntivas que son sólidamente exclusivas, como el francés soit... soit.

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 dado. Además de la abreviatura "XOR", también se puede ver cualquiera de los siguientes símbolos:

• +, un signo más, que tiene la ventaja de que todas las propiedades algebraicas ordinarias de anillos matemáticos y campos se pueden utilizar sin más ado; pero el signo más también se utiliza para la disyunción inclusiva en algunos sistemas de notación; note que la disyunción exclusiva corresponde al modulo adicional 2, que tiene la siguiente tabla de adición, claramente isomorfo a la anterior:

${displaystyle p}$	${displaystyle q}$	${displaystyle P+q}$
0	0	0
0	1	1
1	0	1
1	1	0

• ${displaystyle oplus }$, un signo más modificado; este símbolo también se utiliza en matemáticas para el suma directa de estructuras algebraicas
• J, como en Jpq
• Un símbolo de disyunción inclusivo (${displaystyle lor }$) que se modifica de alguna manera, como
  • ${displaystyle {compline {lor}}}$
  • ${displaystyle { dot {fnMie }$
• ^, el cuidado, utilizado en varios lenguajes de programación, como C, C++, C#, D, Java, Perl, Ruby, PHP y Python, denotando el operador XOR bitwise; no utilizado fuera de contextos de programación porque está demasiado fácilmente confundido con otros usos del cuidado como la exponenciación.
• , a veces escrito como
  • ■.
  • ..
• = 1, en la simbología IEC

Propiedades

Comunitario: sí

${displaystyle Aoplus B}$	${displaystyle Leftrightarrow$	${displaystyle Boplus A}$
	${displaystyle Leftrightarrow$

Associatividad: sí

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

Distribución:

La exclusiva o no distribuye sobre ninguna función binaria (ni siquiera ella misma), pero la conjunción lógica se distribuye sobre exclusiva o. ${displaystyle Cland (Aoplus B)=(Cland A)oplus (Cland B)}$ (Conjunción y exclusiva o forma las operaciones de multiplicación y adición de un campo GF(2), y como en cualquier campo obedecen la ley distributiva.)

Idempotencia: no

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

Monotonicity: no

${displaystyle Arightarrow B}$	${displaystyle nRightarrow }$			${displaystyle (Aoplus C)}$	${displaystyle rightarrow }$	${displaystyle (Boplus C)}$
	${displaystyle nRightarrow }$		${displaystyle Leftrightarrow$		${displaystyle rightarrow }$

Verdad-preservación: no

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

${displaystyle Aland B}$	${displaystyle nRightarrow }$	${displaystyle Aoplus B}$
	${displaystyle nRightarrow }$

Falsehood-preserving: yes

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

${displaystyle Aoplus B}$	${displaystyle "Rightarrow"$	${displaystyle Alor B}$
	${displaystyle "Rightarrow"$

espectro de Gales: (2,0,0,−2)

No linealidad: 0

La función es lineal.

Si usa valores binarios para verdadero (1) y falso (0), entonces exclusivo o funciona exactamente como módulo de adición 2.

Ciencias de la computación

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

Operación bit a bit

La adición de Nimber es exclusiva o exclusiva de enteros no negativos en representación binaria. Esta es también la adición vectorial ${displaystyle (mathbb {Z} {Z})} {4}}$.

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

• 1 XOR 1 = 0
• 1 XOR 0 = 1
• 0 XOR 1 = 1
• 0 XOR 0 = 0
• 11102 XOR 10012 = 01112 (esto es equivalente a la adición sin carga)

Como se ha señalado anteriormente, ya que la disyunción exclusiva es idéntica a la adición modulo 2, la disyunción exclusiva bitwise de dos n-bit strings es idéntico al vector estándar de adición en el espacio vectorial ${displaystyle (mathbb {Z} {Z})}$.

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

• Dice si dos partes son desiguales.
• Es un bit-flipper opcional (la entrada de decisión elige si invertir la entrada de datos).
• Dice si hay un número extraño de 1 bits (${displaystyle Aoplus Boplus Coplus Doplus E}$ es cierto si y sólo si un número extraño de las variables son verdaderas), que es igual al bit de paridad devuelto por una función de paridad.

En los 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 informáticas, es más eficiente almacenar un cero en un registro haciendo XOR-ing del registro consigo mismo (los bits XOR-ed consigo mismos siempre son cero) en lugar de cargar y almacenar el valor cero.

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

Exclusive-or se usa a veces como una función de mezcla simple en criptografía, por ejemplo, con sistemas de red de Feistel o bloc de notas de un solo uso.

Exclusive-or también se usa mucho en cifrados de bloque como AES (Rijndael) o Serpent y en la implementación de cifrado de bloque (CBC, CFB, OFB o CTR).

Del mismo modo, XOR se puede utilizar para generar grupos de entropía para generadores de números aleatorios de hardware. La operación XOR conserva 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.

XOR se usa en RAID 3–6 para crear información de paridad. Por ejemplo, RAID puede "hacer copias de seguridad" bytes 100111002 and 011011002 de dos (o más) discos duros haciendo XOR en los bytes recién mencionados, lo que da como resultado (111100002) y escribirlo en otra unidad. Con este método, si se pierde cualquiera de los tres discos duros, el byte perdido se puede volver a crear mediante la operación XOR de los bytes de las unidades restantes. Por ejemplo, si la unidad contiene 011011002 se pierde, 100111002 and 111100002 se puede aplicar XOR para recuperar el byte perdido.

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, eso significa que se produjo un desbordamiento. XORing esos dos bits dará un "1" si hay un desbordamiento.

XOR se puede usar para intercambiar dos variables numéricas en computadoras, usando el algoritmo de intercambio XOR; sin embargo, esto se considera más como una curiosidad y no se fomenta 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 por computadora, los métodos de dibujo basados en XOR se usan a menudo para administrar elementos tales como cuadros delimitadores y cursores en sistemas sin canales alfa o planos superpuestos.

Codificaciones

También se llama "no flecha izquierda derecha" (nleftrightarrow) en la marcación basada en LaTeX (${displaystyle nleftrightarrow }$). Aparte de los códigos ASCII, el operador está codificado en U+BB ⊻ XOR ()" Verbar ") y U+2295 ⊕ CIRCLED PLUS ()" CirclePlus; ", "), ambos en los operadores matemáticos bloque.