¿La propiedad asociativa de XOR es demostrable o axiomática?

Question

He estado tratando de demostrar (para mi propio entretenimiento) que XOR es asociativo.

Sin embargo, al haber reducido $(p \oplus q ) \oplus r = p \oplus (q \oplus r)$ a la forma canónica, de modo que las únicas operaciones lógicas son OR, AND; termino teniendo algo que no puedo reducir sin recurrir a las propiedades asociativas y distributivas de AND y OR.

Parece bastante redundante demostrar que un operador lógico tiene una determinada propiedad pero depender de otro para hacerlo.

Mi pregunta es: ¿Es la propiedad asociativa de XOR demostrable algebraicamente - o es axiomática? ¿Cuenta la tabla de verdad como una prueba?

EDIT: Esta es la tabla que se me ocurrió.

Answer 1

La tabla de verdad es suficiente, ya que las tablas de verdad proporcionan una teoría de modelos completa para la lógica proposicional clásica. Esto se puede demostrar demostrando que cualquier fórmula es equivalente a su forma normal disyuntiva y luego observar que las tablas de verdad son esencialmente una representación condensada de este DNF.

XOR se define a menudo utilizando su tabla de verdad.

Answer 2

Tenga en cuenta que ambos $(p\oplus q)\oplus r$ y $p\oplus (q\oplus r)$ son verdaderos si y sólo si Número impar de $p,q,r$ son verdaderos.

Del mismo modo, puede considerar establece en lugar de afirmaciones lógicas, entonces AND corresponde a la intersección y OR a la unión, NOT al complemento, y utilizando $$p\oplus q = (p \land \lnot q ) \lor (q\land \lnot p) $$ obtenemos $$ A\oplus B = (A\setminus B) \cup (B\setminus A) $$ este es el diferencia simétrica de conjuntos, y $x\in A_1\oplus..\oplus A_n$ si $x$ es un elemento de exactamente un número impar de $A_i$ 's.

Answer 3

Si quieres un formal prueba según la definición de prueba utilizada en la lógica moderna, entonces se necesita algún conjunto de axiomas o reglas de inferencia a partir de los cuales se pueda escribir una prueba.

Informalmente, la tabla de verdad indica la asociatividad de XOR, o equivalentemente que {[(p⊕q)⊕r]=[p⊕(q⊕r)]} califica como una tautología, donde "=" indica la operación de equivalencia lógica. Por el metateorema de completitud (toda tautología es un teorema) de cualquier sistema de lógica proposicional clásica que probablemente encuentres, se deduce que {[(p⊕q)⊕r]=[p⊕(q⊕r)]} es un teorema. Por lo tanto, la tabla de verdad sí se califica como una prueba informal de que existe un teorema en el sistema formal.

Dependiendo del contexto, a casi nadie le interesa escribir o ver una prueba formal... aunque tu ordenador podría "considerarte" loco si crees que puedes darle una prueba informal y que signifique algo.