Logical Equivalence in FOL

Mathematical Logic · Axiom Academy

LESSON Logical Equivalence in FOL Explore logical equivalence in first-order logic: transformations, quantifier laws, and the careful dance of substitution and variable renaming. 1. What Is Logical Equivalence? Formally: φ ≡ ψ means that for every structure M and every assignment s, we have M, s ⊨ φ if and only if M, s ⊨ ψ. 2. Swapping Quantifiers of the Same Type Universal quantifiers commute with each other, and existential quantifiers commute with each other. Order doesn't matter when quantifiers are the same type: 3. Negating Quantifiers: De Morgan's Laws for FOL When we negate a quantified statement, the quantifier flips and the negation moves inside. These are the fundamental laws for pushing negations through quantifiers: "Not everything satisfies φ" means "Something doesn't satisfy φ" "Nothing satisfies φ" means "Everything doesn't satisfy φ" 4. Quantifier Distribution Over Connectives Quantifiers interact with logical connectives in specific ways. Some distributions work in both directions, while others work only one way: "For all x, both φ and ψ" is the same as "For all x, φ and for all x, ψ" "There exists x such that φ or ψ" is the same as "There exists x with φ or there exists x with ψ" Bound variables are just placeholders. We can rename them to any fresh variable that doesn't cause collisions, and the formula's meaning stays the same: 6. Substitution and Its Pitfalls

This is the written version of the interactive lesson above. See the full Mathematical Logic course.