Proving XOR Commutativity: Sufficiency of Tautology

  • Thread starter gnome
  • Start date
In summary, in order to prove that XOR is commutative, it is sufficient to prove that ((X \wedge \neg Y) \vee (\neg X \wedge Y)) \supset ((Y \wedge \neg X) \vee (\neg Y \wedge X)) is a tautology, which essentially means that if (X xor Y) is true, then (Y xor X) is also true. This is not the same as saying that X xor Y is equal to Y xor X, as the latter is not always true. It is important to clarify this distinction to ensure full rigor in the proof.
  • #1
gnome
1,041
1
Given that XOR is defined by [itex]((X \wedge \neg Y) \vee (\neg X \wedge Y))[/itex], in order to prove that XOR is commutative is it sufficient to prove that
[itex]((X \wedge \neg Y) \vee (\neg X \wedge Y)) \supset ((Y \wedge \neg X) \vee (\neg Y \wedge X))[/itex]
is a tautology?
 
Physics news on Phys.org
  • #2
Think about what that says:

If (X xor Y), then (Y xor X).

Is that the same as X xor Y = Y xor X?

(no)

Now, in general you would leave the last step implicit, because it's fairly routine, but I imagine you're interested in full rigor.
 
  • #3
OK, I'd like to retract that ridiculous statement before I get banned. :smile: :smile: :smile:

Maybe I'd better get some sleep... :zzz:
 

FAQ: Proving XOR Commutativity: Sufficiency of Tautology

1. What is XOR commutativity?

XOR commutativity is a mathematical property that states that the order in which two values are XORed together does not affect the final result. In other words, if A and B are two values, then A XOR B will always be equal to B XOR A.

2. Why is proving XOR commutativity important?

Proving XOR commutativity is important because it allows for simplification of mathematical operations and can also be used in various computer algorithms and data structures.

3. What is the sufficiency of tautology in proving XOR commutativity?

The sufficiency of tautology means that the truth table of a logical expression is always true, regardless of the input values. In the context of proving XOR commutativity, showing that the expression A XOR B = B XOR A is a tautology is sufficient to prove the commutativity property.

4. How is XOR commutativity proven using tautology?

XOR commutativity can be proven using tautology by constructing a truth table for the logical expression A XOR B = B XOR A. If the truth table shows that the expression is always true, regardless of the input values, then XOR commutativity is proven.

5. Can XOR commutativity be proven using other methods besides tautology?

Yes, XOR commutativity can also be proven using other methods such as algebraic manipulation or logical equivalences. However, using tautology is often the simplest and most direct method for proving this property.

Similar threads

MHB What is the Tautology in the Given Logical Equivalence?
Replies
2
Views
1K
Help with proving Biconditional equivalence
Replies
6
Views
6K
Writing some ZF axioms with FOL symbols
Replies
2
Views
1K
MHB Intro to Logic (prove sequents)
Replies
1
Views
1K
MHB What is the Implication of a Formula in Propositional Calculus?
Replies
10
Views
2K
MHB Proving the Inequality: 0<A<B Implies 1/B<1/A
Replies
1
Views
1K
MHB Proving Properties of Lattices: How to Use DeMorgan's Laws
Replies
2
Views
1K
MHB T admits elimination of quantifiers
Replies
1
Views
1K
Union of sets and indexed sets question from Vellerman
Replies
4
Views
1K
MHB Counting Quantifiers: Exercise 2.20 Solutions
Replies
1
Views
3K

Hot Threads

Recent Insights

Back
Top