Satisfaction and Validity

Mathematical Logic · Axiom Academy

LESSON Satisfaction and Validity Understanding semantic truth in first-order logic Mathematical Logic • Unit 4 - First-Order Logic In first-order logic, we distinguish between syntax (how formulas are written) and semantics (what formulas mean). Semantics concerns itself with truth in structures. A formula doesn't have a truth value in isolation. It becomes true or false only when interpreted in a structure with a specific variable assignment . An assignment maps each variable to an element of the domain: Satisfiability: Finding a Witnessing Structure A formula is satisfiable if there exists at least one structure that makes it true. We read this as: "There exists a structure and assignment such that satisfies under ." This is satisfiable! We can find a structure where it's true: Interpretation: means "less than" In this structure, the formula is TRUE because 3 < 5. Validity: Truth in All Structures A formula is valid (or a tautology ) if it's true in every possible structure. This is a much stronger condition than satisfiability. A formula is valid , written , if: We read as "models" or "semantically entails." This is valid! It's true in every structure: No matter what domain we choose No matter what value we assign to This is a logical law: either holds or it doesn't! This is NOT valid (though it is satisfiable): True when domain is and means "less than" False when domain has only one element Since it fails in at least one structure, it's not valid.

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