Exclusivo o - Exclusive or

Exclusivo o
XOR
Diagrama de Venn de Exclusivo o
Mesa de la verdad
Puerta lógica XOR ANSI.svg
Formas normales
Disyuntivo
Conjuntivo
Polinomio de Zhegalkin
Celosías de correos
0-conservando
1-conservando no
Monótono no
Afín
Diagrama de Venn de

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

Se simbolizado por el operador de prefijo J y por la infijos operadores XOR ( / ˌ ɛ k s ɔr / o / z ɔr / ), EOR , EXOR , , , , , y . La negación de XOR es el bicondicional lógico , que da como resultado verdadero si y solo si las dos entradas son iguales.

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

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

Mesa de la verdad

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

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

Tabla de verdad XOR
Aporte Producción
A B
0 0 0
0 1 1
1 0 1
1 1 0
  • 0, falso
  • 1, cierto

Equivalencias, eliminación e introducción

La disyunción exclusiva significa esencialmente "uno, pero no ambos ni ninguno". En otras palabras, el enunciado es verdadero si y solo si uno es verdadero y el otro es falso. Por ejemplo, si dos caballos están compitiendo, entonces uno de los dos ganará la carrera, pero no ambos. La disyunción exclusiva , también denotada por ? o , se puede expresar en términos de la conjunción lógica ("lógica y", ), la disyunción ("lógica o", ) y la negación ( ) de la siguiente manera:

La disyunción exclusiva también se puede expresar de la siguiente manera:

Esta representación de XOR puede resultar útil cuando se construye un circuito o una red, porque tiene una sola operación y un pequeño número de operaciones y . Una prueba de esta identidad se da a continuación:

A veces es útil escribir de la siguiente manera:

o:

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 es también equivalente a la negación de un bicondicional lógico , por las reglas de implicación material (un 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:

Negación

Se puede aplicar el espíritu de las leyes de De Morgan, tenemos:

Relación con el álgebra moderna

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

Los sistemas y son monoides , pero ninguno es 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 de uso exclusivo o es un grupo abeliano . La combinación de operadores y sobre elementos produce el campo conocido . Este campo puede representar cualquier lógica obtenible con el sistema y tiene el beneficio adicional del arsenal de herramientas de análisis algebraico para campos.

Más específicamente, si se asocia con 0 y con 1, se puede interpretar la operación lógica "Y" como una multiplicación en y la operación "XOR" como una suma en :

El uso de esta base para describir un sistema booleano se conoce como 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 "o" a menudo se entiende exclusivamente, particularmente cuando se usa con la partícula "o". El siguiente ejemplo en inglés normalmente se entendería en una conversación como implicando que Mary no es cantante y poeta a la vez.

1. María es cantante o poeta.

Sin embargo, la disyunción también se puede entender de manera inclusiva, incluso en combinación con "o". Por ejemplo, el primer ejemplo a continuación muestra que "cualquiera" se puede usar felizmente en combinación con una declaración directa de que ambos disyuntos son verdaderos. El segundo ejemplo muestra que la inferencia exclusiva se desvanece en contextos de 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, 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 implicaciones son típicamente 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 vinculación semántica auténtica y han propuesto lógicas no clásicas que la validarían.

Este comportamiento del inglés "o" también se encuentra en otros idiomas. Sin embargo, muchos lenguajes 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 los anillos y campos matemáticos se pueden utilizar sin más preámbulos; pero el signo más también se usa para la disyunción inclusiva en algunos sistemas de notación; Nótese que la disyunción exclusiva corresponde a la suma módulo 2, que tiene la siguiente tabla de suma, claramente isomórfica a la anterior:
     
0 0 0
0 1 1
1 0 1
1 1 0
  • , un signo más modificado; este símbolo también se usa en matemáticas para la suma directa de estructuras algebraicas
  • J, como en J pq
  • Un símbolo de disyunción inclusivo ( ) que se modifica de alguna manera, como
  • ^, el signo de intercalación , utilizado en varios lenguajes de programación , como C , C ++ , C # , D , Java , Perl , Ruby , PHP y Python , que denota el operador XOR bit a bit ; no se usa fuera de los contextos de programación porque se confunde demasiado fácilmente con otros usos del signo de intercalación
  • X-or.svg, a veces escrito como
    • > <
    • > - <
  • = 1, en simbología IEC

Propiedades

Conmutatividad : sí
        
Venn0110.svg          Venn0110.svg
Asociatividad : sí
        
Venn 0101 0101.svg Venn 0011 1100.svg          Venn 0110 1001.svg          Venn 0110 0110.svg Venn 0000 1111.svg
Distributividad :
El exclusivo o no se distribuye sobre ninguna función binaria (ni siquiera él mismo), pero la conjunción lógica se distribuye sobre el exclusivo o . (Conjunción y exclusiva o forman las operaciones de multiplicación y suma de un campo GF (2) , y como en cualquier campo obedecen a la ley distributiva.)
Idempotencia : no
                 
Venn01.svg Venn01.svg          Venn00.svg          Venn01.svg
Monotonicidad : no
        
Venn 1011 1011.svg          Venn 1011 1101.svg          Venn 0101 1010.svg Venn 0011 1100.svg
Conservación de la verdad: no
Cuando todas las entradas son verdaderas, la salida no es verdadera.
        
Venn0001.svg          Venn0110.svg
Conservación de la falsedad: sí
Cuando todas las entradas son falsas, la salida es falsa.
        
Venn0110.svg          Venn0111.svg
Espectro de Walsh : (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 el 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 suma de números es la exclusiva o de enteros no negativos en representación binaria . Esta es también la suma de vectores en .

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
  • 1110 2 XOR 1001 2 = 0111 2 (esto es equivalente a la suma sin acarreo )

Como se señaló anteriormente, dado que la disyunción exclusiva es idéntica a la suma módulo 2, la disyunción exclusiva bit a bit de dos cadenas de n bits es idéntica al vector estándar de adición en el espacio vectorial .

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

  • Indica si dos bits son desiguales.
  • Es un volteador de bits opcional (la entrada de decisión elige si se invierte la entrada de datos).
  • Indica si hay un número impar de 1 bits ( es verdadero si un número impar de las variables es verdadero).

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 Y, O y NO para crear la salida de acarreo.

En algunas arquitecturas de computadora, es más eficiente almacenar un cero en un registro haciendo XOR-ing el registro consigo mismo (los bits XOR-ed con ellos mismos son siempre 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 separable linealmente .

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

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

De manera similar, XOR se puede usar 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 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 sea al menos tan buena como la mejor fuente individual.

XOR se utiliza en RAID 3–6 para crear información de paridad. Por ejemplo, RAID puede "hacer una copia de seguridad" de los bytes 10011100 2 y 01101100 2 de dos (o más) discos duros mediante XORing de los bytes recién mencionados, lo que da como resultado ( 11110000 2 ) y lo escribe en otro disco. Con este método, si se pierde cualquiera de los tres discos duros, el byte perdido se puede volver a crear mediante XORing de los bytes de los discos restantes. Por ejemplo, si la unidad que contiene 01101100 2 se pierde, 10011100 2 y 11110000 2 se pueden 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 puede usarse para intercambiar dos variables numéricas en computadoras, usando el algoritmo de intercambio XOR ; sin embargo, esto se considera más una curiosidad y no se fomenta en la práctica.

Las listas vinculadas de XOR aprovechan las propiedades de XOR para ahorrar espacio y representar estructuras de datos de listas doblemente vinculadas .

En gráficos por computadora , los métodos de dibujo basados ​​en XOR se utilizan a menudo para administrar elementos como cuadros delimitadores y cursores en sistemas sin canales alfa o planos superpuestos.

Codificaciones

También se denomina "flecha no izquierda-derecha" (\ nleftrightarrow) en la rebaja basada en Latex ( ). Aparte de los códigos ASCII, el operador está codificado en U + 22BBXOR (HTML  · ) y U + 2295CIRCLED PLUS (HTML  · ), ambos en operadores matemáticos de bloque . &#8891;  &veebar; &#8853;  &CirclePlus;, &oplus;

Ver también

Notas

  1. ^ Germundsson, Roger; Weisstein, Eric. "XOR" . MathWorld . Wolfram Research . Consultado el 17 de junio de 2015 .
  2. ^ Craig, Edward, ed. (1998), Enciclopedia de Filosofía de Routledge , 10 , Taylor & Francis, p. 496, ISBN 9780415073103
  3. ^ a b c d Aloni, Maria (2016), Zalta, Edward N. (ed.), "Disjunction" , The Stanford Encyclopedia of Philosophy (ed. de invierno de 2016), Metaphysics Research Lab, Stanford University , consultado el 9 de septiembre de 2020 03
  4. ^ Jennings cita a numerosos autores que dicen que la palabra "o" tiene un sentido exclusivo. Consulte el Capítulo 3, "El primer mito de 'O'":
    Jennings, RE (1994). La genealogía de la disyunción . Nueva York: Oxford University Press.
  5. ^ Davies, Robert B (28 de febrero de 2002). "O (XOR) exclusivo y generadores de números aleatorios por hardware" (PDF) . Consultado el 28 de agosto de 2013 .
  6. ^ Nobel, Rickard (26 de julio de 2011). "Cómo funciona realmente RAID 5" . Consultado el 23 de marzo de 2017 .

enlaces externos