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.

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	$A\oplus B$
outros símbolos	$\nleftrightarrow$, ${\overline {\vee }}$, ${\underline {\vee }}$, ⩛,
táboa de verdade	${\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 $A\oplus B\oplus C$

Simbolízase polos operadores infixos: XOR, ${\overline {\vee }}$, ${\underline {\vee }}$, ⩛, $\oplus$, $\nleftrightarrow$, e $\not \equiv$ e polo operador de prefixo $J$.

Definición

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

$A$	$B$	$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 $p\nleftrightarrow q$, tamén denotada como $p\operatorname {?} q$ ou $Jpq$, pódese expresar en termos da conxunción lóxica ("E lóxico", $\wedge$ ), a disxunción ("OU lóxico", $\lor$ ), e a negación ($\lnot$) do seguinte xeito:

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

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

${\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 $\lnot$ e un número pequeno de opracións $\land$ e $\lor$. A proba desta identidade dáse a continuación:

${\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 $p\nleftrightarrow q$ do seguinte xeito:

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

ou:

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

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

$\lnot (p\nleftrightarrow q)\Leftrightarrow \lnot p\nleftrightarrow q\Leftrightarrow p\nleftrightarrow \lnot q.$

Relación coa álxebra abstracta

Aínda que os operadores $\wedge$ ( conxunción ) e $\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 $(\{T,F\},\wedge )$ e $(\{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$(\{T,F\},\oplus )$ temos un grupo abeliano. A combinación de operadores $\wedge$ e $\oplus$ sobre elementos $\{T,F\}$ producen o coñecido corpo de dous elementos $\mathbb {F} _{2}$. Este corpo pode representar calquera lóxica obtida co sistema $(\land ,\lor )$ e ten a vantaxe adicional do arsenal de ferramentas de análise alxébrica para corpos.

Máis concretamente, se se asocia $F$ con 0 e $T$ con 1, pódese interpretar a operación lóxica "AND" como multiplicación en $\mathbb {F} _{2}$ e a operación "XOR" como suma en $\mathbb {F} _{2}$:

${\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 $\mathbb {F} _{2}$, usando esta base, chámase forma normal alxébrica da función.

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:

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

Propiedades

Conmutatividade: si

$A\oplus B$	$\Leftrightarrow$	$B\oplus A$
	$\Leftrightarrow$

Asociatividade: si

$~A$	$~~~\oplus ~~~$	$(B\oplus C)$	$\Leftrightarrow$			$(A\oplus B)$	$~~~\oplus ~~~$	$~C$
	$~~~\oplus ~~~$		$\Leftrightarrow$		$\Leftrightarrow$		$~~~\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. $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

$~A~$	$~\oplus ~$	$~A~$	$\Leftrightarrow$	$~0~$	$\nLeftrightarrow$	$~A~$
	$~\oplus ~$		$\Leftrightarrow$		$\nLeftrightarrow$

Monótona: non

$A\rightarrow B$	$\nRightarrow$			$(A\oplus C)$	$\rightarrow$	$(B\oplus C)$
	$\nRightarrow$		$\Leftrightarrow$		$\rightarrow$

Preserva a verdade: non

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

$A\land B$	$\nRightarrow$	$A\oplus B$
	$\nRightarrow$

Preserva a falsidade: si

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

$A\oplus B$	$\Rightarrow$	$A\lor B$
	$\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.

$~A\oplus B~$	$~\oplus ~$	$~B~$	$\Leftrightarrow$	$~A~$
	$~\oplus ~$		$\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 $(\mathbb {Z} /2\mathbb {Z} )^{n}$.

Véxase tamén

Outros artigos

• Condicional material
• Disxunción lóxica
• Valor lóxico
• Cálculo proposicional
• Porta XOR

Ligazóns externas

• All About XOR
• Proofs of XOR properties and applications of XOR, CS103: Mathematical Foundations of Computing, Stanford University