Defining Satisfiability of a Sentence (Propositional and First-Order Logic)

In logic, satisfiability is a semantic property: it asks whether a given sentence can be made true under some allowed assignment of meanings/values. Formally, a sentence is satisfiable if there exists an interpretation/model in which the sentence evaluates to true. 2

keywordkeywordkeywordkeyword

This course section builds the definition carefully for both propositional logic (truth assignments/valuations) and first-order logic (structures/interpretations). 3

Core idea (semantic “exists”)

For any fixed logic, satisfaction depends on an interpretation. The “exists” quantifier is the key:

• Satisfiable: there exists an interpretation/model/valuation that makes the sentence true. 2
• Unsatisfiable: for every interpretation/model/valuation, the sentence is not true (i.e., always false). 2

This “exists interpretation” viewpoint is exactly how satisfiability is introduced in standard references on logic and model theory. 2

Satisfiability in Propositional Logic (truth assignments)

Definitions

Let $\\varphi$ be a propositional sentence built from propositional variables using logical connectives (e.g., $\\lnot, \\land, \\lor, \\Rightarrow$).

• A valuation (also called a truth assignment) is an assignment of $\\text{True/False}$ to each propositional variable.
• A sentence $\\varphi$ is satisfiable iff there exists at least one valuation $v$ such that $\\varphi$ evaluates to true under $v$. 2
• If no valuation makes $\\varphi$ true, it is unsatisfiable (a contradiction). 2

You can phrase it as:

• satisfiable: $\\exists v\\;\\big(\\varphi \\text{ is true under } v\\big)$
• unsatisfiable: $\\forall v\\;\\big(\\varphi \\text{ is false under } v\\big)$

These are the standard semantics used in treatments of SAT-style satisfiability. 2

Worked micro-example (intuitive)

Take $\\varphi := (p \\lor \\lnot p)$. This is true for every valuation, so it is satisfiable (and in fact valid). A contrasting example $\\varphi := (p \\land \\lnot p)$ is unsatisfiable because no valuation can make both $p$ and $\\lnot p$ true at once. These examples match the “exists valuation vs. none” semantics described in logic introductions. 2

Relationship to “SAT”

In computer science, the Boolean Satisfiability Problem (SAT) asks whether a formula has at least one assignment making it evaluate to true—i.e., exactly the satisfiability definition above.

keywordkeywordkeywordkeyword

Satisfiability in First-Order Logic (structures/interpretations)

Definitions (model-theoretic semantics)

In first-order logic (FOL), a “sentence” may contain:

• predicate symbols (relations)
• function symbols
• constant symbols
• quantifiers (e.g., $\\forall, \\exists$)
• variables (though “sentences” have no free variables)

A key notion is a structure (also called an interpretation/model). In model theory, satisfiability is defined relative to such structures. 2

A standard definition:

• A first-order sentence $\\varphi$ is satisfiable iff there exists a structure $A$ such that $A \\vDash \\varphi$ (meaning $\\varphi$ is true in $A$). 2

Equivalently, for a formula with free variables, satisfiability is sometimes phrased using an assignment of elements from the domain to those free variables; for sentences, no extra assignment is needed because free variables are absent. 2

Why “satisfiability” is semantic

The semantics are not just syntactic truth tables: meanings of predicate/function symbols depend on the structure. So satisfiability is inherently semantic—about whether some interpretation/model makes the sentence true. 2

keyword[keyword]{def="Model relation: $M \\vDash \\varphi$ means model satisfies sentence"}keywordkeyword

Satisfiable vs. valid (and why negation matters)

Satisfiability is often contrasted with validity:

• Valid: true under all interpretations/models. 2
• Satisfiable: true under at least one interpretation/model. 2

A common relationship:

• $\\varphi$ is valid exactly when $\\lnot\\varphi$ is not satisfiable. This is a standard observation in logic treatments of satisfiability/validity. 2

Another useful relationship in SAT/logic:

• Showing that $\\lnot\\varphi$ is unsatisfiable is equivalent to showing $\\varphi$ is valid. 2

keywordkeywordkeywordkeyword

Add-on: Satisfiability of a set of sentences (context)

Sometimes the target is not a single sentence but a set $\\Delta$ of sentences. The satisfiability definition generalizes:

• A set $\\Delta$ is satisfiable if there exists an interpretation/model that makes every sentence in $\\Delta$ true.
• In SAT-style settings, $\\Delta$ can be combined into one sentence (e.g., by conjunction), but the semantic core remains: “exists a model where all are true.” 2

This “exists a common model” perspective is also used in completeness/entailment connections (e.g., entailment relates to unsatisfiability of the premises plus the negation of the conclusion).