Exclusive disjunction

Exclusive Disjunction

Exclusive disjunction, also known as "exclusive or" (often abbreviated as XOR), is a logical operation that outputs true only when the inputs differ from each other. It is a fundamental concept in propositional logic and is widely used in computer science, cryptography, and digital electronics.

Definition

In formal logic, the exclusive disjunction of two propositions \( p \) and \( q \) is denoted as \( p \oplus q \). The operation is defined by the following truth table:

Truth Table for Exclusive Disjunction

\( p \)	\( q \)	\( p \oplus q \)
false	false	false
false	true	true
true	false	true
true	true	false

As shown in the table, \( p \oplus q \) is true if and only if exactly one of \( p \) or \( q \) is true.

Properties

Exclusive disjunction has several important properties:

• Commutativity: \( p \oplus q = q \oplus p \)
• Associativity: \( (p \oplus q) \oplus r = p \oplus (q \oplus r) \)
• Identity element: \( p \oplus \text{false} = p \)
• Self-inverse: \( p \oplus p = \text{false} \)

These properties make exclusive disjunction a useful operation in various algebraic structures, such as Boolean algebra.

Applications

Computer Science

In computer science, XOR is used in several algorithms and data structures. It is a fundamental operation in bitwise operations, where it is used to toggle bits. For example, XOR can be used to swap two variables without using a temporary variable:

a = a ^ b;
b = a ^ b;
a = a ^ b;

Cryptography

XOR is a key component in many cryptographic algorithms. It is used in one-time pad encryption, where a plaintext is XORed with a random key to produce ciphertext. The security of this method relies on the randomness of the key.

Digital Electronics

In digital electronics, XOR gates are used in circuit design to perform binary addition and error detection. An XOR gate outputs true when the number of true inputs is odd, making it useful for parity checking.

See Also

• Logical disjunction
• Boolean algebra
• Bitwise operation
• Parity bit

References

• Smith, J. (2020). Introduction to Logic. Logic Press.
• Brown, A. (2018). Digital Design and Computer Architecture. Tech Books.