Disjunction and Exclusive Or

TL;DR

Disjunction (OR) is true if at least one statement is true, including when both are true. Exclusive Or (XOR) is true only if exactly one statement is true, but not if both are true or both are false. Understanding the difference is crucial for precise logical statements and conditional programming.

1. The Mental Model

Think of "OR" like ordering food: if you can have pizza OR pasta, you'd be happy with pizza, happy with pasta, and even happier if somehow you got both. "XOR" is like choosing a single elective: you can take History OR Science, but you can't take both.

2. The Core Material

In discrete mathematics, we often combine statements using logical operators. Disjunction and Exclusive Or are two key operators, and while they sound similar, they have distinct meanings and applications.

Disjunction (OR)

Disjunction, denoted by the symbol $\lor$ (read as "or"), is a logical operation that returns true if at least one of the statements it connects is true. This means if statement A is true, or statement B is true, or both A and B are true, the disjunction A $\lor$ B is true. The only time A $\lor$ B is false is when both A and B are false.

Think of it as the "inclusive OR."

Here's its truth table:

Example: "Today is Tuesday OR it is raining."
- If it's Tuesday and raining: True
- If it's Tuesday but not raining: True
- If it's not Tuesday but it is raining: True
- If it's not Tuesday and not raining: False

Exclusive Or (XOR)

Exclusive Or, denoted by $\oplus$ (or sometimes XOR), is a logical operation that returns true if exactly one of the statements it connects is true. Unlike disjunction, if both statements are true, the XOR operation returns false. It also returns false if both statements are false.

Think of it as the "either/or, but not both" OR.

Here's its truth table:

Example: "You will choose coffee XOR tea."
- If you choose coffee and tea: False (you can't have both in this context)
- If you choose coffee but not tea: True
- If you choose tea but not coffee: True
- If you choose neither: False

Comparing OR and XOR

The main difference lies in the "both true" scenario. OR allows both to be true for the overall statement to be true, while XOR specifically excludes it.

Here's a visual way to compare them:

graph LR
    A["Statement A is True?"] --> B{ "Statement B is True?" }
    B -- Yes --> C{ "Both True" }
    B -- No --> D{ "A True, B False" }

    C --> OR_TRUE["OR Result: TRUE"]
    C --> XOR_FALSE["XOR Result: FALSE"]

    D --> OR_TRUE_2["OR Result: TRUE"]
    D --> XOR_TRUE["XOR Result: TRUE"]

    E["Statement A is False?"] --> F{ "Statement B is True?" }
    F -- Yes --> G{ "A False, B True" }
    F -- No --> H{ "Both False" }

    G --> OR_TRUE_3["OR Result: TRUE"]
    G --> XOR_TRUE_2["XOR Result: TRUE"]

    H --> OR_FALSE["OR Result: FALSE"]
    H --> XOR_FALSE_2["XOR Result: FALSE"]

    subgraph Outcomes for OR
        OR_TRUE
        OR_TRUE_2
        OR_TRUE_3
        OR_FALSE
    end

    subgraph Outcomes for XOR
        XOR_FALSE
        XOR_TRUE
        XOR_TRUE_2
        XOR_FALSE_2
    end

In Programming

Many programming languages use || for logical OR and often ^ or a specific keyword like xor for XOR.

Python Example:

# Disjunction (OR)
print(True or True)   # Output: True
print(True or False)  # Output: True
print(False or True)  # Output: True
print(False or False) # Output: False

# Exclusive Or (XOR) - Python doesn't have a direct 'xor' keyword for booleans.
# You can implement it as (A and not B) or (not A and B) or using bitwise XOR ^
a = True
b = True
print((a and not b) or (not a and b)) # Output: False

a = True
b = False
print((a and not b) or (not a and b)) # Output: True

a = False
b = True
print((a and not b) or (not a and b)) # Output: True

a = False
b = False
print((a and not b) or (not a and b)) # Output: False

3. Worked Example

Let's say we have two statements:
$P$: "The light switch is ON."
$Q$: "The room is bright."

We want to evaluate $P \lor Q$ and $P \oplus Q$ under different scenarios.

Scenario 1: The light switch is ON, and the room is bright.
- $P$ is True, $Q$ is True.
- $P \lor Q$: True $\lor$ True = True (The light switch is ON or the room is bright, which is true because both are true.)
- $P \oplus Q$: True $\oplus$ True = False (The light switch is ON exclusive or the room is bright is false because both are true.)

Scenario 2: The light switch is ON, but the bulb is broken, so the room is not bright.
- $P$ is True, $Q$ is False.
- $P \lor Q$: True $\lor$ False = True (The light switch is ON or the room is bright, which is true because the switch is ON.)
- $P \oplus Q$: True $\oplus$ False = True (The light switch is ON exclusive or the room is bright is true because exactly one is true.)

Scenario 3: The light switch is OFF, but there's sunlight, so the room is bright.
- $P$ is False, $Q$ is True.
- $P \lor Q$: False $\lor$ True = True (The light switch is ON or the room is bright, which is true because the room is bright.)
- $P \oplus Q$: False $\oplus$ True = True (The light switch is ON exclusive or the room is bright is true because exactly one is true.)

Scenario 4: The light switch is OFF, and there's no sunlight, so the room is not bright.
- $P$ is False, $Q$ is False.
- $P \lor Q$: False $\lor$ False = False (The light switch is ON or the room is bright, which is false because neither is true.)
- $P \oplus Q$: False $\oplus$ False = False (The light switch is ON exclusive or the room is bright is false because neither is true.)

4. Key Takeaways

• Disjunction ($\lor$, OR) is true if one or both statements are true.
• Exclusive Or ($\oplus$, XOR) is true only if exactly one statement is true.
• The "both true" case is the key difference: OR is true, XOR is false.
• Truth tables are your best friend for understanding and verifying logical operations.
• In programming, be aware of how your chosen language implements OR and XOR, especially for booleans.

Common mistakes to avoid:
- Confusing "or" in natural language with logical disjunction; natural language "or" can sometimes imply exclusivity.
- Assuming XOR is just a "stronger" version of OR; it's a distinct operation.
- Incorrectly evaluating the "both true" case when solving problems involving these operators.
- Forgetting that when both statements are false, both OR and XOR result in false.

5. Now Try It

Consider two statements:
$A$: "The number is even."
$B$: "The number is greater than 10."

For the numbers 4, 12, 7, and 15, determine the truth value of $A \lor B$ and $A \oplus B$. Write down your reasoning for each of the eight results. What makes each result true or false for each operator?