OR exclusivo

OR exclusivo, OU exclusivo, disxunción exclusiva, non equivalencia lóxica ou desigualdade lóxica é un operador lóxico cuxa negación é o bicondicional lóxico. Con dúas entradas, XOR é verdadeiro se e só se as entradas difiren (unha é verdadeira, outra é falsa). Con varias entradas, XOR é verdadeiro se e só se o número de entradas verdadeiras é impar.^[1]

OR exclusivo
XOR

Diagrama de Venn do OR exclusivo (en vermello a parte verdadeira)
Outros nomes	OU exclusivo disxunción exclusiva non equivalencia lóxica desigualdade lóxica
linguaxe natural	A ou B mais non ambos os dous
linguaxe formal	${\displaystyle A\oplus B}$
outros símbolos	${\displaystyle \nleftrightarrow }$, ${\displaystyle {\overline {\vee }}}$, ${\displaystyle {\underline {\vee }}}$, ⩛,
táboa de verdade	${\displaystyle {\begin{array}{c|c||c}A&B&A\oplus B\\\hline V&V&F\\V&F&V\\F&V&V\\F&F&F\\\end{array}}}$
porta lóxica

Diagrama de Venn ${\displaystyle A\oplus B\oplus C}$

Simbolízase polos operadores infixos: XOR, ${\displaystyle {\overline {\vee }}}$, ${\displaystyle {\underline {\vee }}}$, ⩛, ${\displaystyle \oplus }$, ${\displaystyle \nleftrightarrow }$, e ${\displaystyle \not \equiv }$ e polo operador de prefixo ${\displaystyle J}$^[2](p16).

Definición

A táboa de verdade de ${\displaystyle A\oplus B}$ mostra que ten resultado verdadeiro sempre que as entradas sexan diferentes:

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

Equivalencias, eliminación e introdución

A disxunción exclusiva significa esencialmente "un, pero non os dous nin ningún". Noutras palabras, a afirmación é verdadeira se e só se unha é verdadeira e a outra é falsa. Por exemplo, se dous cabalos corren, entón un dos dous gañará a carreira, mais non os dous. A disxunción exclusiva ${\displaystyle p\nleftrightarrow q}$, tamén denotada como ${\displaystyle p\operatorname {?} q}$ ou ${\displaystyle Jpq}$, pódese expresar en termos da conxunción lóxica ("E lóxico", ${\displaystyle \wedge }$ ), a disxunción ("OU lóxico", ${\displaystyle \lor }$ ), e a negación (${\displaystyle \lnot }$) do seguinte xeito:

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

A disxunción exclusiva ${\displaystyle p\nleftrightarrow q}$ tamén se pode expresar do seguinte xeito:

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

Esta representación de XOR pode resultar útil á hora de construír un circuíto ou rede, porque só ten unha operación ${\displaystyle \lnot }$ e un número pequeno de opracións ${\displaystyle \land }$ e ${\displaystyle \lor }$. A proba desta identidade dáse a continuación:

${\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}}}$

Ás veces é útil escribir ${\displaystyle p\nleftrightarrow q}$ do seguinte xeito:

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

ou:

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

Esta equivalencia pódese estabelecer aplicando as leis de De Morgan dúas veces á cuarta liña da proba anterior.

O OR exclusivo tamén é equivalente á negación dun bicondicional lóxico, polas regras de implicación material (un condicional material equivale á disxunción da negación do seu antecedente e do seu consecuente) e da equivalencia material.

En resumo, temos, en notación matemática e en enxeñarí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}}}$

Negación do operador

Ao aplicar o espírito das leis de De Morgan, obtemos:

${\displaystyle \lnot (p\nleftrightarrow q)\Leftrightarrow \lnot p\nleftrightarrow q\Leftrightarrow p\nleftrightarrow \lnot q.}$

Relación coa álxebra abstracta

Aínda que os operadores ${\displaystyle \wedge }$ ( conxunción ) e ${\displaystyle \lor }$ ( disxunción ) son moi útiles en sistemas lóxicos, non serven para unha estrutura máis xeneralizábel pola seguinte razón:

Os sistemas ${\displaystyle (\{T,F\},\wedge )}$ e ${\displaystyle (\{T,F\},\lor )}$ son monoides, mais non son un grupo. Desafortunadamente, isto impide a combinación destes dous sistemas en estruturas máis grandes, como un anel matemático.

No entanto, usando o sistema con OR exclusivo${\displaystyle (\{T,F\},\oplus )}$ temos un grupo abeliano. A combinación de operadores ${\displaystyle \wedge }$ e ${\displaystyle \oplus }$ sobre elementos ${\displaystyle \{T,F\}}$ producen o coñecido corpo de dous elementos ${\displaystyle \mathbb {F} _{2}}$. Este corpo pode representar calquera lóxica obtida co sistema ${\displaystyle (\land ,\lor )}$ e ten a vantaxe adicional do arsenal de ferramentas de análise alxébrica para corpos.

Máis concretamente, se se asocia ${\displaystyle F}$ con 0 e ${\displaystyle T}$ con 1, pódese interpretar a operación lóxica "AND" como multiplicación en ${\displaystyle \mathbb {F} _{2}}$ e a 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}}}$

A descrición dunha función booleana como polinomio en ${\displaystyle \mathbb {F} _{2}}$, usando esta base, chámase forma normal alxébrica da función.^[3]

OU exclusivo en linguaxe natural

A disxunción enténdese a miúdo exclusivamente nas linguas naturais. En galego, a palabra "ou" adoita entenderse exclusivamente, precisamente como é no caso do XOR. Por exemplo: "Temos partida o sábado ou o domingo", que se interpreta como que temos partida un deses dous días mais non os dous.

Símbolos alternativos

A maiores da abreviatura "XOR", tamén se pode ver calquera dos seguintes símbolos:

• ${\displaystyle +}$ foi usado por George Boole in 1847.^[4]
• ${\displaystyle {\overline {\vee }}}$ usouse por Christine Ladd-Franklin en 1883.^[5]
• ${\displaystyle \not =}$, denotando a negación da equivalencia, foi usado por Ernst Schröder en 1890,^[6](p307)
• ${\displaystyle \circ }$ foi usado por Giuseppe Peano in 1894.
• ${\displaystyle \oplus }$ foi usado por Claude Shannon en 1938.^[7]
• ${\displaystyle \not \equiv }$, denotanto tamén a negación da equivalencia, foi usado por Alonzo Church en 1944.^[8]
• ${\displaystyle J}$ (como un operador prefixo, ${\displaystyle J\phi \psi }$) usouse por Józef Maria Bocheński en 1949.^[2](p16)

Propiedades

Conmutatividade: si

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

Asociatividade: 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 ~~~}$

Distributividade

O OR exclusivo non ten a propiedade distributiva sobre ningunha función binaria (nin sequera en si mesma), mais a conxunción lóxica distribúese sobre o OR exclusivo. ${\displaystyle C\land (A\oplus B)=(C\land A)\oplus (C\land B)}$ (Conxunción e OR exclusiva forman as operacións de multiplicación e suma dun corpo GF(2), e como en calquera corpo obedecen á lei distributiva.

Idempotencia: non

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

Monótona: non

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

Preserva a verdade: non

Cando todas as entradas son verdadeiras a saída non é verdadeira.

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

Preserva a falsidade: si

Cando todas as entradas son falsas a saída é falsa.

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

Espectro de Walsh: (2,0,0,−2)}}

Linear: si. A función é linear.

Involución:

o OR exclusivo cunha entrada especificada en función da outra entrada, é unha involución ou función autoinversa; aplicando dúas veces deixa a entrada sen cambios.

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

Ao usar os valores binarios true (1) e false (0) entón o OR exclusivo funciona exactamente iguaol que a suma módulo 2. 

Informática

Representación simbólica tradicional dunha porta lóxica XOR

Operación bit a bit

A disxunción exclusiva úsase a miúdo para operacións bit a bit. Exemplos:

• 1 XOR 1 = 0
• 1 XOR 0 = 1
• 0 XOR 1 = 1
• 0 XOR 0 = 0
• 11102 XOR 10012 = 01112 (isto é equivalente á suma sen acarreo)

Como se indicou anteriormente, dado que a disxunción exclusiva é idéntica á suma módulo 2, a disxunción exclusiva bit a bit de dúas cadeas de n bits é idéntica ao vector estándar de suma no espazo vectorial ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$.