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]
Simbolízase polos operadores infixos: XOR, , , ⩛, , , e e polo operador de prefixo [2]Modelo:Rp.
Definición
A táboa de verdade de mostra que ten resultado verdadeiro sempre que as entradas sexan diferentes: Modelo:2-ary truth table
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 , tamén denotada como ou , pódese expresar en termos da conxunción lóxica ("E lóxico", ), a disxunción ("OU lóxico", ), e a negación () do seguinte xeito:
A disxunción exclusiva tamén se pode expresar do seguinte xeito:
Esta representación de XOR pode resultar útil á hora de construír un circuíto ou rede, porque só ten unha operación e un número pequeno de opracións e . A proba desta identidade dáse a continuación:
Ás veces é útil escribir do seguinte xeito:
ou:
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:
Negación do operador
Ao aplicar o espírito das leis de De Morgan, obtemos:
Relación coa álxebra abstracta
Aínda que os operadores ( conxunción ) e ( disxunción ) son moi útiles en sistemas lóxicos, non serven para unha estrutura máis xeneralizábel pola seguinte razón:
Os sistemas e 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 temos un grupo abeliano. A combinación de operadores e sobre elementos producen o coñecido corpo de dous elementos . Este corpo pode representar calquera lóxica obtida co sistema e ten a vantaxe adicional do arsenal de ferramentas de análise alxébrica para corpos.
Máis concretamente, se se asocia con 0 e con 1, pódese interpretar a operación lóxica "AND" como multiplicación en e a operación "XOR" como suma en :
A descrición dunha función booleana como polinomio en , 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:
- foi usado por George Boole in 1847.[4]
- usouse por Christine Ladd-Franklin en 1883.[5]
- , denotando a negación da equivalencia, foi usado por Ernst Schröder en 1890,[6]Modelo:Rp
- foi usado por Giuseppe Peano in 1894.
- foi usado por Claude Shannon en 1938.[7]
- , denotanto tamén a negación da equivalencia, foi usado por Alonzo Church en 1944.[8]
- (como un operador prefixo, ) usouse por Józef Maria Bocheński en 1949.[2]Modelo:Rp
Propiedades
Conmutatividade: si
Asociatividade: si
- 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. (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
Monótona: non
Preserva a verdade: non
- Cando todas as entradas son verdadeiras a saída non é verdadeira.
- Modelo:Táboa aliñada
Preserva a falsidade: si
- Cando todas as entradas son falsas a saída é falsa.
- Modelo:Táboa aliñada
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.
- Modelo:Táboa aliñada
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
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 .
Notas
Véxase tamén
Bibliografía
Outros artigos
Ligazóns externas
- All About XOR
- Proofs of XOR properties and applications of XOR, CS103: Mathematical Foundations of Computing, Stanford University
- ↑ Modelo:Cita web
- ↑ 2,0 2,1 Modelo:Cita libro Translated as Modelo:Cite book
- ↑ Modelo:Cita libro
- ↑ Modelo:Cita libro
- ↑ Modelo:Cita enciclopedia
- ↑ Modelo:Cite book Reprinted by Thoemmes Press in 2000.
- ↑ Modelo:Cita revista
- ↑ Modelo:Cite book