Exclusivo o

La disyunción exclusiva , la alternancia exclusiva , la no equivalencia lógica o la desigualdad lógica es un operador lógico cuya negación es la bicondicional lógica . Con dos entradas, la operación XOR es verdadera si y solo si las entradas son diferentes (una es verdadera y la otra falsa). Con múltiples entradas, la operación XOR es verdadera si y solo si el número de entradas verdaderas es impar . ^{[ 1 ]}

Se le denomina "o exclusivo" porque el significado de "o" es ambiguo cuando ambos operandos son verdaderos. La operación XOR excluye ese caso. Algunas formas informales de describir XOR son "uno u otro, pero no ambos", "uno u otro" y "A o B, pero no A y B".

Se simboliza mediante el operador de prefijo.${\displaystyle J}$^{[ 2 ] : 16}y por losoperadores infijosXOR( / ˌ ɛ k s ˈ ɔː r / o / ˈ k s ɔː r / ),EOR,EXOR,${\displaystyle {\dot {\vee }}}$,${\displaystyle {\overline {\vee }}}$,${\displaystyle {\underline {\vee }}}$, ⩛ ,${\displaystyle \oplus }$,${\displaystyle \nleftrightarrow }$,${\displaystyle \not \equiv }$y ^.

La tabla de verdad de${\displaystyle A\nleftrightarrow B}$muestra que la salida es verdadera siempre que las entradas sean diferentes:

La disyunción exclusiva significa esencialmente "una de las dos, pero no ambas ni ninguna". 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 compitiendo, entonces uno de los dos ganará la carrera, pero no ambos. La disyunción exclusiva${\displaystyle p\nleftrightarrow q}$, también denotado por${\displaystyle p\operatorname {?} q}$o${\displaystyle Jpq}$, puede expresarse en términos de la conjunción lógica ("y lógico",${\displaystyle \land }$), la disyunción ("o lógico",${\displaystyle \vee }$), y la negación (${\displaystyle \neg }$) de la siguiente manera:

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

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

${\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 red, porque tiene solo una operación lógica.${\displaystyle \lnot }$operación y un pequeño número de${\displaystyle \land }$y${\displaystyle \lor }$operaciones. A continuación se presenta una prueba de esta identidad:

${\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${\displaystyle p\nleftrightarrow q}$De la siguiente manera:

${\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 demostración anterior.

La disyunción exclusiva también es equivalente a la negación de una bicondicional lógica , según las reglas de implicación material (una 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 \neg (p\nleftrightarrow q)\equiv \neg p\nleftrightarrow q\equiv p\nleftrightarrow \neg q.}$$

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

Los sistemas${\displaystyle (\{T,F\},\wedge )}$y${\displaystyle (\{T,F\},\lor )}$son monoides , pero ninguno es un grupo . Esto, desafortunadamente, impide la combinación de estos dos sistemas en estructuras más grandes, como un anillo matemático .

Sin embargo, el sistema que utiliza de forma exclusiva o${\displaystyle (\{T,F\},\oplus )}$es un grupo abeliano . La combinación de operadores${\displaystyle \wedge }$y${\displaystyle \oplus }$sobre los elementos${\displaystyle \{T,F\}}$producir el conocido campo de dos elementos${\displaystyle \mathbb {F} _{2}}$Este campo puede representar cualquier lógica obtenible con el sistema.${\displaystyle (\land ,\lor )}$y tiene la ventaja añadida de contar con un amplio arsenal de herramientas de análisis algebraico 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 una multiplicación en${\displaystyle \mathbb {F} _{2}}$y la operación "XOR" como suma en${\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${\displaystyle \mathbb {F} _{2}}$, utilizando esta base, se denomina forma normal algebraica de la función . ^{[ 3 ]}

La disyunción se entiende a menudo exclusivamente en lenguas naturales . En inglés, la palabra disyuntiva "or" se entiende a menudo exclusivamente, sobre todo cuando se usa con la partícula "either". El ejemplo en inglés que aparece a continuación se entendería normalmente en una conversación como que Mary no es a la vez cantante y poeta. ^{[ 4 ] [ 5 ]}

1. María es cantante o poeta.

Sin embargo, la disyunción también puede entenderse de forma inclusiva, incluso en combinación con «cualquiera de las dos». Por ejemplo, el primer ejemplo a continuación muestra que «cualquiera de las dos» puede usarse convenientemente en combinación con una afirmación explícita 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, quedaría abierta la posibilidad de que algunas personas comieran tanto arroz como frijoles. ^{[ 4 ]}

2. Mary es cantante, poeta o ambas cosas.

3. Nadie comió ni arroz ni frijoles.

Ejemplos como los anteriores 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 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 "or" inglés también se encuentra en otros idiomas. Sin embargo, muchos idiomas tienen construcciones disyuntivas que son robustamente exclusivas, como el francés soit... soit . ^{[ 4 ]}

El símbolo utilizado para la disyunción exclusiva varía según el campo de aplicación 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 pueden encontrar los siguientes símbolos:

• ${\displaystyle +}$fue utilizado por George Boole en 1847. ^{[ 6 ]} Aunque Boole utilizó${\displaystyle +}$principalmente en clases, también consideró el caso de que${\displaystyle x,y}$son proposiciones en${\displaystyle x+y}$y en ese momento${\displaystyle +}$es un conector. Además, Boole lo usó exclusivamente. Aunque tal uso no muestra la relación entre la disyunción inclusiva (para la cual${\displaystyle \vee }$(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 ]}
• ${\displaystyle {\overline {\vee }}}$fue utilizado por Christine Ladd-Franklin en 1883. ^{[ 9 ]} Estrictamente hablando, Ladd utilizó${\displaystyle A\operatorname {\overline {\vee }} B}$para expresar "${\displaystyle A}$no es-no${\displaystyle B}$" o "No${\displaystyle A}$es${\displaystyle B}$", es decir, usado${\displaystyle {\overline {\vee }}}$como exclusiones, mientras que implícitamente${\displaystyle {\overline {\vee }}}$tiene el significado de disyunción exclusiva ya que el artículo se titula "Sobre el álgebra de la lógica".
• ${\displaystyle \not =}$, que denota la negación de equivalencia , fue utilizado por Ernst Schröder en 1890, ^{[ 10 ] : 307} Aunque el uso de${\displaystyle =}$como la 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 y otros, no utilizaron${\displaystyle \not =}$como no equivalencia literalmente, lo cual posiblemente se deba a que podría definirse fácilmente a partir de la negación y la equivalencia.
• ${\displaystyle \circ }$Fue utilizada por Giuseppe Peano en 1894:${\displaystyle a\circ b=a-b\,\cup \,b-a}$El letrero${\displaystyle \circ }$corresponde al latín aut ; el signo${\displaystyle \cup }$a vel ." ^{[ 11 ] : 10} Nótese que la palabra latina "aut" significa "o exclusivo" y "vel" significa "o inclusivo", y que Peano usa${\displaystyle \cup }$como disyunción inclusiva.
• ${\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 casi con seguridad fue escrito después de 1685; y 1890 es la fecha de publicación). ^{[ 15 ]} Mientras que tanto Huntington en 1904 como Leibniz en 1890 usaron el símbolo como una operación algebraica. Además, Huntington en 1904 también usó el símbolo como disyunción inclusiva (suma lógica), y en 1933 usó${\displaystyle +}$como disyunción inclusiva. ^{[ 16 ]}
• ${\displaystyle \not \equiv }$, que también denota la negación de equivalencia , fue utilizado por Alonzo Church en 1944. ^{[ 17 ]}
• ${\displaystyle J}$(como operador de prefijo ,${\displaystyle J\phi \psi }$) fue utilizado por Józef Maria Bocheński en 1949. ^{[ 2 ] : 16} Alguien ^{[ 18 ]} puede confundirse y pensar que fue Jan Łukasiewicz quien fue el primero en utilizar${\displaystyle J}$ for exclusive disjunction (it seems that the mistake spreads widely), while neither in 1929^[19] nor in other works did Łukasiewicz make such use. In fact, in 1949 Bocheński introduced a system of Polish notation that names all 16 binary connectives of classical logic which is a compatible extension of the notation of Łukasiewicz in 1929, and in which ${\displaystyle J}$ for exclusive disjunction appeared at the first time. Bocheński's usage of ${\displaystyle J}$ as exclusive disjunction has no relationship with the Polish "alternatywa rozłączna" of "exclusive or" and is an accident for which see the table on page 16 of the book in 1949.
• ^, the caret, has been used in several programming languages to denote the bitwise exclusive or operator, beginning with C^[20] and also including C++, C#, D, Java, Perl, Ruby, PHP, Python and Rust.
• The symmetric difference of two sets ${\displaystyle S}$ and ${\displaystyle T}$, which may be interpreted as their elementwise exclusive or, has variously been denoted as ${\displaystyle S\ominus T}$, ${\displaystyle S\mathop {\triangledown } T}$, or ${\displaystyle S\mathop {\vartriangle } T}$.^[21]

Commutativity: yes

Associativity: yes

Distributivity:

The exclusive or does not distribute over any binary function (not even itself), but logical conjunction distributes over exclusive or. ${\displaystyle C\land (A\oplus B)=(C\land A)\oplus (C\land B)}$ (Conjunction and exclusive or form the multiplication and addition operations of a fieldGF(2), and as in any field they obey the distributive law.)

Idempotency: no

Monotonicity: no

Truth-preserving: no

When all inputs are true, the output is not true.

Falsehood-preserving: yes

When all inputs are false, the output is false.

Walsh spectrum: (2,0,0,−2)

Non-linearity: 0

The function is linear.

Involution:

Exclusive or with one specified input, as a function of the other input, is an involution or self-inverse function; applying it twice leaves the variable input unchanged.

If using binary values for true (1) and false (0), then exclusive or works exactly like additionmodulo 2.

También se le llama "flecha no izquierda-derecha" ( \nleftrightarrow) en Markdown basado en LaTeX (${\displaystyle \nleftrightarrow }$). Aparte de los códigos ASCII, el operador está codificado en U+22BB ⊻ XOR ( & veebar; ) y U+2295 ⊕ CIRCLED PLUS ( & CirclePlus;, & oplus; ) , ambos en operadores matemáticos de bloque .

• Todo sobre XOR
• Demostraciones de las propiedades de la compuerta XOR y aplicaciones de la compuerta XOR, CS103: Fundamentos Matemáticos de la Computación, Universidad de Stanford.