Logical Equivalence

Two logical expressions are Logically Equivalent if they have the exact same truth values in every possible scenario. In mathematics, we use the symbol $\equiv$ (or sometimes $\iff$) to denote this.

If $A \equiv B$, it means the column for $A$ and the column for $B$ in a truth table are identical.

1. Proving Equivalence: The Truth Table Method

Let's prove a fundamental equivalence: $p \implies q \equiv \neg p \lor q$. This is often called the Conditional Disjunction equivalence.

Conclusion: Since the third and fifth columns are identical, $p \implies q \equiv \neg p \lor q$.

2. De Morgan's Laws

These are perhaps the most famous equivalences in logic and computer science. They describe how to distribute a NOT ($\neg$) over an AND ($\land$) or an OR ($\lor$).

1. First Law: $\neg(p \land q) \equiv \neg p \lor \neg q$
2. Second Law: $\neg(p \lor q) \equiv \neg p \land \neg q$

3. Key Logical Identities

Just like $a \times (b + c) = ab + ac$ in algebra, logic has laws that allow us to simplify complex "circuitry."

• Double Negation: $\neg(\neg p) \equiv p$
• Idempotent Laws: $p \land p \equiv p$ and $p \lor p \equiv p$
• Distributive Laws: * $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$
  • $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$

4. Visualizing Equivalence with Gates

In digital logic, equivalence means two different circuit designs produce the exact same output for the same inputs.

subgraph Circuit_B["¬A ∨ ¬B"]
In3[A] --> NOT1((NOT))
In4[B] --> NOT2((NOT))
NOT1 --> OR((OR))
NOT2 --> OR
OR --> Out2[Result]
end`}

5. Verification in Python

We can write a script to check if two functions return the same Boolean result for all inputs.

def expression_1(p, q):
    return not (p and q)

def expression_2(p, q):
    return (not p) or (not q)

# Test all combinations
inputs = [(True, True), (True, False), (False, True), (False, False)]

for p, q in inputs:
    if expression_1(p, q) != expression_2(p, q):
        print("Equivalence Failed!")
        break
else:
    print("De Morgan's Law Verified: Expressions are Logically Equivalent.")

Next Step: Now that we can simplify expressions, we will explore Tautologies, Contradictions, and Contingencies to classify the nature of logical statements.