Logical Equivalence

Why do 'If you don't study, you won't get a job' and 'Study or you won't get a job' say the same thing? Logical equivalence explains when different words express one idea.

• **Code refactoring:** `!(a && b)` = `!a || !b` - De Morgan's laws simplify conditions
• **Mathematical proofs:** The contrapositive lets you prove a theorem 'from the other end'
• **Legal logic:** Equivalent formulations of a law must be applied consistently

Logical Equivalence

**Logical equivalence** is when two formulas have identical truth tables. They always give the same result for the same variable values. Denoted: P ≡ Q or P ⟺ Q.

**Key idea:** Equivalent formulas are different ways of saying the same thing. They can be substituted for each other in any context without changing the meaning.

**Don't confuse with implication!** P → Q asks 'is it true right now?' and depends on the values. P ≡ Q asks 'do they always match?' and is independent of specific values.

Contrapositive

**The contrapositive** is the transformation of the implication P → Q into ¬Q → ¬P. These two formulas are logically equivalent! The contrapositive says the same thing, but 'from the other end'.

**Why this matters:** Sometimes the contrapositive is easier to prove. Instead of 'If P, then Q', we prove 'If not-Q, then not-P' - and that is equivalent.

**Don't confuse with the converse and inverse!** This is a common mistake. The converse (Q → P) and the inverse (¬P → ¬Q) are NOT equivalent to the original implication.

Biconditional

**The biconditional** P ↔ Q (read 'P if and only if Q') is true when P and Q have the same truth value - both true or both false.

**Biconditional equivalence:** P ↔ Q ≡ (P → Q) ∧ (Q → P). This is a 'two-way' implication - it works in both directions.

**In mathematics**, 'if and only if' is used for definitions. 'A triangle is isosceles ↔ two of its angles are equal' - this is not just a consequence, but a definition of equivalent concepts.

Equivalent Forms

**Laws of equivalence** are a set of identities that allow transforming formulas without changing their truth value. This is the 'algebra of logic'.

**Why this is useful:** Transformations allow simplifying a formula, converting it to a required form (e.g., for programming), or proving the equivalence of two expressions.

**Example transformation:** Let's transform ¬(P → Q) - 'it is not the case that if P then Q'.

**Application in programming:** De Morgan's laws are often used for refactoring conditions. `!(a && b)` becomes `!a || !b`, which is sometimes easier to read.

Key Takeaways

• **Logical equivalence (≡):** formulas with identical truth tables, interchangeable everywhere
• **Contrapositive:** P → Q ≡ ¬Q → ¬P. The converse and inverse are NOT equivalent!
• **Biconditional (↔):** 'if and only if' = two-way connection, used in definitions
• **De Morgan's laws:** ¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q - negation flips the connective

Related Topics

Equivalence connects formal logic with practice:

• Truth Tables — Equivalence is verified by comparing truth tables
• Normal Forms — Equivalent transformations convert a formula to a standard form

Вопросы для размышления

• Why is the contrapositive intuitively clear, while the converse of an implication is a common mistake?
• In what situations is a biconditional (↔) used in everyday speech, even though we just say 'if'?
• How do De Morgan's laws help when writing conditions in programming?

Связанные уроки

• comp-22-ssa
• ml-01