XOR and Equivalence

Two additional logical connectives - exclusive or (true when inputs differ) and equivalence (true when inputs match).

21 topics • ~1889 words

Two sensors monitor the same valve. If they disagree—one says open, the other says closed—something is wrong. The XOR light triggers: mismatch detected.

XOR completes the truth table pattern: AND has 1/4 true outputs, OR has 3/4, and XOR has exactly 2/4—half. It is the "difference detector," true when inputs disagree.

The XOR Operation

The XOR operation (also called exclusive or) combines two truth values.

It returns true when the inputs are different - exactly one is true and the other is false. When both inputs are the same (both true or both false), XOR returns false.

Think of it as a "difference detector": the result is true when the inputs disagree.

XOR Notation

XOR has several notations in logic and programming:

  • $\oplus$ (circled plus) - the standard mathematical symbol
  • XOR - written out explicitly
  • ^ - common in programming languages (C, Java, Python)

The circled plus $\oplus$ reminds us that XOR is like addition modulo 2:

0$\oplus$0=0, 0$\oplus$1=1, 1$\oplus$0=1, 1$\oplus$1=0 (where 1+1 "wraps around" to 0).

Evaluating XOR

To evaluate XOR, remember the rule: XOR returns true when the inputs are different (one true, one false). When both inputs are the same, XOR returns false.

Evaluating XOR with Variables

When variables are assigned truth values, we can evaluate XOR expressions by substituting the values and applying the XOR rule: return true if the inputs differ, false if they're the same.

XOR Truth Table

The truth table for XOR shows all possible input combinations:

P Q P $\oplus$ Q
T T F
T F T
F T T
F F F

Notice the pattern: XOR is true exactly when the inputs differ.

The middle two rows (where P $\neq$ Q) produce true; the first and last rows (where P = Q) produce false.

The Equivalence Operation

Safety interlock: the system only proceeds when both sensors agree. Open-open or closed-closed—either works. But if they disagree, the equivalence check fails and the system halts.

The equivalence operation (also called biconditional) combines two truth values.

It returns true when both inputs have the same value - either both true or both false. When the inputs differ, equivalence returns false.

Think of it as a "sameness detector": the result is true when the inputs agree.

Equivalence is the logical opposite of XOR.

Equivalence Notation

Equivalence has several notations:

  • $\leftrightarrow$ (double arrow) - the standard mathematical symbol for biconditional
  • $\equiv$ (triple bar) - sometimes used, especially for logical equivalence
  • XNOR - in digital logic, emphasizing it's the negation of XOR
  • ⊙ (circled dot) - occasionally used in circuit design

The double arrow $\leftrightarrow$ suggests "goes both ways" - P implies Q and Q implies P.

Evaluating Equivalence

To evaluate equivalence, remember the rule: equivalence returns true when the inputs are the same (both true or both false). When the inputs differ, equivalence returns false.

Evaluating Equivalence with Variables

When variables are assigned truth values, we can evaluate equivalence expressions by substituting the values and applying the rule: return true if the inputs are the same, false if they differ.

Equivalence Truth Table

The truth table for equivalence shows all possible input combinations:

P Q P $\leftrightarrow$ Q
T T T
T F F
F T F
F F T

Notice the pattern: equivalence is true exactly when the inputs match.

The first and last rows (where P = Q) produce true; the middle two rows (where P $\neq$ Q) produce false. This is the exact opposite of XOR!

XOR and Equivalence Relationship

Mismatch alarm vs. agreement signal—opposite indicators on the same panel. When the mismatch light is on (XOR), the agreement light is off (not equivalent). They can never both be lit. That is the relationship.

XOR and equivalence are logical complements (opposites):

  • XOR is true when inputs differ
  • Equivalence is true when inputs match

This means: P $\leftrightarrow$ Q = $\neg$(P $\oplus$ Q) and P $\oplus$ Q = $\neg$(P $\leftrightarrow$ Q)

In digital logic, equivalence is often called XNOR (NOT-XOR) for this reason.

Wherever XOR gives True, equivalence gives False, and vice versa.

English to Logic (XOR)

"Either the main pump runs or the backup runs, but not both." The interlock prevents simultaneous operation—exactly one must be active. That is XOR in the system specs.

In English, XOR (exclusive or) is expressed when we mean "one or the other, but not both":

  • "Either X or Y, but not both"
  • "X or Y, but not both"
  • "Exactly one of X or Y"
  • "X or else Y" (sometimes implies exclusivity)

Be careful: plain "or" in English is often ambiguous - it might mean inclusive OR (at least one) or exclusive OR (exactly one). Context matters!

English to Logic (Equivalence)

In English, equivalence (biconditional) is expressed when we mean two things always have the same truth value:

  • "X if and only if Y" (often abbreviated "X iff Y")
  • "X exactly when Y"
  • "X is equivalent to Y"
  • "X just in case Y"
  • "X when and only when Y"

"If and only if" is the classic phrase - it means "if X then Y" AND "if Y then X".

XOR as Difference Detector

Two pressure gauges on the same line. If they read different values, something is wrong—a blockage, a leak, a sensor fault. XOR is the mismatch indicator: it triggers when the readings disagree.

XOR detects differences.

Think of XOR as answering: "Are these two things different?"

A B A $\oplus$ B Meaning
F F F Same (both false)
F T T Different!
T F T Different!
T T F Same (both true)

XOR is true exactly when the inputs disagree.

XOR in Cryptography

XOR has a magical property that makes it perfect for encryption:

XOR is its own inverse!

If you XOR something twice with the same key, you get back the original:

  • message $\oplus$ key = encrypted
  • encrypted $\oplus$ key = message

This is the basis of the one-time pad, a theoretically unbreakable cipher!

XOR Chains

XOR can chain across multiple operands:

A $\oplus$ B $\oplus$ C is evaluated left to right: (A $\oplus$ B) $\oplus$ C

Useful property: The result is true when an odd number of inputs are true.

T count Result
0 (FFF) F
1 (TFF, FTF, FFT) T
2 (TTF, TFT, FTT) F
3 (TTT) T

Building Blocks Synthesis

The control room has it all now: compound expression panels, gate schematics, and mismatch detectors. Different tools for different jobs—but they all describe the same underlying logic.

You've now learned the building blocks of Boolean logic:

  • Compound expressions: Combining NOT, AND, OR with precedence rules
  • Logic gates: Hardware implementation of Boolean operations
  • XOR/Equivalence: Advanced operations for difference/sameness detection

Building Blocks Challenge

Sensor A disagrees with Sensor B (XOR). Sensor A agrees with Sensor C (equivalence). What does that tell you about B and C? You trace the logic through the system.

This challenge combines everything from Building Blocks:

  • Precedence rules (NOT > AND > OR/XOR)
  • Gate-to-expression translation
  • XOR and equivalence properties
  • Multi-step evaluation

Practical Uses of XOR

XOR's practical applications stem from two key properties:

  1. Self-inverse: A $\oplus$ B $\oplus$ B = A (XOR twice with the same value cancels out)
  2. Information-preserving: Given A $\oplus$ B and either A or B, you can recover the other

Common applications:

  • Toggling bits: XOR with T flips a value; XOR with F leaves it unchanged
  • Comparing values: A $\oplus$ B = F means A and B are equal
  • RAID parity: XOR of all disks lets you rebuild any one failed disk
  • Swap trick: Swap two values without a temporary variable using three XORs

XOR for Parity Checking

A parity bit is an extra bit added to a message so that the total number of T values is always even (even parity) or always odd (odd parity).

Computing parity with XOR:

P = A $\oplus$ B $\oplus$ C $\oplus$ ... (XOR all data bits together)

The result P is T when an odd number of inputs are T, and F when an even number are T. This is even parity: append P so the total is always even.

Detecting errors: On receipt, XOR all bits including P. If the result is F, no error. If T, a single bit was flipped somewhere.

Limitation: Parity detects odd numbers of bit flips (1, 3, 5...) but misses even numbers (2, 4, 6...) because two flips cancel each other out.

XOR as Inequality Detector

XOR is a difference detector:

  • A $\oplus$ B = T means A and B are different
  • A $\oplus$ B = F means A and B are equal

Applications:

  • Equality check: XOR two values; F means they match
  • Change detection: XOR old state with new state; T bits show what changed
  • Bitwise diff: XOR two multi-bit values; the result has T in every position where they differ and F where they agree

Key insight: XOR answers "are these different?" while equivalence (XNOR) answers "are these the same?" They are complementary views of the same comparison.

Ready to test your understanding?

Bitwit uses spaced repetition to help you truly master concepts like this—not just read about them. Each card generates with different values, so you can't just memorize answers.

Practice XOR and Equivalence →