Logical Equivalence: Different Statements Same Meaning

"Not both" equals "at least one not."

¬(P ∧ Q) ≡ ¬P ∨ ¬Q

Different symbols. Identical truth tables. Logically equivalent expressions.

This is one of the most powerful ideas in logic. If two expressions are equivalent, you can substitute one for the other anywhere without changing truth values. Complex expressions can be simplified. Proofs can be restructured. Arguments can be rewritten in clearer forms.

De Morgan's Laws say "not both" is the same as "at least one not" — and "not either" is the same as "both not." Once you see this equivalence, you can translate freely between the forms.

What Equivalence Means

Two expressions are logically equivalent (≡) if they have the same truth value in every possible world.

P → Q ≡ ¬P ∨ Q

Check it:

Same columns. Equivalent expressions.

"If P then Q" means the same as "not P or Q." The conditional is really just a disjunction in disguise.

De Morgan's Laws

The most useful equivalences in logic:

De Morgan's First Law: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q "Not both" = "at least one not"

De Morgan's Second Law: ¬(P ∨ Q) ≡ ¬P ∧ ¬Q "Not either" = "both not"

Negation distributes over connectives but flips ∧ to ∨ and vice versa.

Examples:

• "It's not the case that it's raining and cold" = "It's not raining or it's not cold"
• "It's not the case that it's raining or cold" = "It's not raining and it's not cold"

Double Negation

¬¬P ≡ P

Negating twice returns you to the original.

"It's not the case that it's not raining" = "It's raining"

This seems trivial but it's essential for proof techniques like proof by contradiction.

Conditional Equivalences

The conditional has several equivalent forms:

P → Q ≡ ¬P ∨ Q (material conditional) P → Q ≡ ¬Q → ¬P (contrapositive) P → Q ≡ ¬(P ∧ ¬Q) (negated conjunction)

The contrapositive is crucial: "If P then Q" is equivalent to "If not Q then not P."

"If it's raining, the ground is wet" ≡ "If the ground is not wet, it's not raining"

Both statements make exactly the same claim about the world.

Biconditional Equivalence

P ↔ Q ≡ (P → Q) ∧ (Q → P)

"P if and only if Q" means "P implies Q and Q implies P."

Also: P ↔ Q ≡ (P ∧ Q) ∨ (¬P ∧ ¬Q)

"P iff Q" means "both true or both false."

Commutativity and Associativity

Commutativity: order doesn't matter. P ∧ Q ≡ Q ∧ P P ∨ Q ≡ Q ∨ P P ↔ Q ≡ Q ↔ P

Associativity: grouping doesn't matter. (P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R) (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)

Note: the conditional is neither commutative nor associative. P → Q ≢ Q → P (P → Q) → R ≢ P → (Q → R)

Distributivity

And distributes over Or: P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)

Or distributes over And: P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)

These are like the distributive property in algebra, but logic has distribution in both directions (unlike arithmetic, where multiplication distributes over addition but not vice versa).

Absorption Laws

P ∧ (P ∨ Q) ≡ P P ∨ (P ∧ Q) ≡ P

The second term gets "absorbed." If P is already true, knowing P ∨ Q adds nothing. If P is already false, P ∧ Q is already false.

Negation of Conditionals

¬(P → Q) ≡ P ∧ ¬Q

The negation of "if P then Q" is "P and not Q."

What does it take for "if it rains, the ground gets wet" to be false? It must rain AND the ground must stay dry.

Just having dry ground isn't enough. Just having rain isn't enough. You need both the condition to hold AND the consequence to fail.

The Master Table

Why This Matters

Equivalences let you transform expressions.

Complex expression? Simplify it using equivalences. Proof stuck? Rewrite using contrapositive. Circuit design? Find an equivalent form with fewer gates.

The equivalences are the algebraic rules of logic. Just as algebra lets you manipulate equations, logical equivalences let you manipulate expressions — and the truth is preserved through every transformation.

Part 5 of the Logic series.

Previous: Truth Tables: Computing Logical Values Next: Tautologies and Contradictions: Always True and Never True