A través de la uso del álgebra de Boole demuestre que el operador XOR es a la vez conmutativo y asociativo.
Sé que puedo demostrarlo utilizando una tabla de verdad. ¿Pero usando álgebra booleana? ¿Cómo lo muestro? No tengo ni idea. ¿Alguna ayuda por favor?
Utilizo ⋅ para denotar AND y + para indicar OR. a⊕b viene dado por a⋅ˉb+b⋅ˉa . ¿Ves por qué? ¿Ves por qué es conmutativo?
Para la asociatividad, se quiere demostrar que (a⊕b)⊕c=a⊕(b⊕c) . El lado izquierdo se expande como
(a⊕b)⋅ˉc+¯(a⊕b)⋅c (a⋅ˉb+b⋅ˉa)⋅ˉc+¯(a⋅ˉb+b⋅ˉa)⋅c
Utiliza las reglas del álgebra booleana (leyes de Demorgan, leyes de distribución, etc.) para ampliarlo. Luego haz lo mismo para el otro lado y demuestra que las expansiones son iguales.
Una forma intuitiva de entender por qué XOR es asociativo es la siguiente:
Primero hay que reconocer que XOR es conmutativo, es decir, a⊕b=b⊕a . Esto se puede hacer utilizando una tabla de verdad o como en la respuesta de Robert Mastragostino.
Entonces, piense en el operador XOR como un operador de "volteo condicional", es decir, piense en a⊕b como diciendo si a es 1, toma volteado b como salida, mientras que si a es 0, toma b como salida. Debido a la propiedad conmutativa, a⊕b es completamente equivalente a b⊕a que dice que b voltea condicionalmente a .
Consideremos ahora a⊕(b⊕c) . Esto quiere decir que b voltea condicionalmente c cuyo resultado se invierte condicionalmente por a . Debido a la naturaleza de la operación de volteo, en última instancia c se invierte condicionalmente tanto por b y a y no importa en qué orden se realicen estas dos operaciones. Debido a esto, se ve que a⊕(b⊕c) es equivalente a b⊕(a⊕c) .
Por último, utilizando la conmutatividad, se puede escribir a⊕(b⊕c)=(b⊕c)⊕a que acaba de demostrarse que es equivalente a b⊕(a⊕c) que a su vez equivale a b⊕(c⊕a) por conmutatividad.
Por lo tanto, (b⊕c)⊕a=b⊕(c⊕a) lo que demuestra la asociatividad.
Una forma intuitiva de convencerse de que ⊕ es asociativa es la siguiente. (Nota: en realidad no lo estamos demostrando con álgebra rígida - pero creo que es un argumento muy intuitivo y muestra otra manera agradable de ver ⊕ .)
Primero echemos un vistazo de nuevo a la tabla de verdad: xyx⊕y000011101110 Conmutatividad: A partir de la tabla de verdad, podemos convencernos fácilmente de que podemos conmutar los argumentos. Ya que en cualquier caso, conmutarlos nos dará el mismo resultado.
Asociatividad: Además, vemos en la tabla de verdad que podemos reescribir x⊕y como predicado y adición: x⊕y⟺odd(x+y) Ahora bien, utilizando esta forma de reescribir el ⊕ podemos ver fácilmente que ⊕ es asociativo. x⊕(y⊕z)⟺odd(x+odd(y+z))⟺odd(x+y+z)⟺odd(odd(x+y)+z)⟺(x⊕y)⊕z
Supongo que se le da una definición de ⊕ en términos de ∨ y ∧ como a⊕b=(a∧¬b)∨(¬a∧b) ou a⊕b=(a∨b)∧¬(a∧b) . Tienes que demostrar a⊕b=b⊕a y a⊕(b⊕c)=(a⊕b)⊕c utilizando las normas para ∨ y ∧ . Por ejemplo, puede utilizar la conmutatividad y asociatividad de ∨ y ∧ las leyes distributivas o leyes de De Morgan (véase aquí para una lista completa de dichas leyes). La conmutatividad es sencilla, la asociatividad es un cálculo fácil pero bastante largo. Un procedimiento estándar sería poner ambos lados de a⊕(b⊕c)=(a⊕b)⊕c en forma normal conjuntiva o disyuntiva y luego comparar.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
3 votos
¿Qué tiene esto que ver con la demostración automática de teoremas?
2 votos
Respuesta intuitiva: Para un solo bit, XOR es lo mismo que la suma módulo 2, que como es bien sabido es conmutativa y asociativa. Para números de varios bits, cada posición de bit se trata por separado, por lo que el resultado es el mismo.