Math 2.0

Mathematical logic and foundations Definition

Satisfiability

Builds on Propositional logicWell-formed formulaStructure

Definition

  1. A formula φ\varphi of propositional logic is satisfiable if some truth assignment to its variables gives φ\varphi the value true.
  2. Let σ\sigma be a signature and φ\varphi a first-order formula over σ\sigma. Then φ\varphi is satisfiable if there are a σ\sigma-structure MM and an assignment ss of elements of MM to the variables with M⊨φ[s]M \models \varphi[s].
  3. A set Γ\Gamma of formulas is satisfiable if one interpretation makes all formulas of Γ\Gamma true at once.

A formula or set that is not satisfiable is unsatisfiable.

Remarks

The formula (p∨q)∧¬p(p \lor q) \land \neg p is satisfiable: the assignment p=𝖥p = \mathsf{F}, q=𝖳q = \mathsf{T} makes both conjuncts true. The set {p,  p→q,  ¬q}\set{p, \; p \to q, \; \neg q} is unsatisfiable: if pp and p→qp \to q are true then qq is true, so ¬q\neg q is false. Each of its three formulas is satisfiable on its own, so clause 3 is stronger than satisfiability of each member. A formula φ\varphi is valid, for example a tautology, exactly when ¬φ\neg \varphi is unsatisfiable.

Reading path

To understand this page from the ground up, read these 10 pages in order. The foundations come first.

Show the path as a graph
Proposition, concept, no evidence levelPropositionconceptStructure, concept, no evidence levelStructureconceptWell-formed formula, concept, no evidence levelWell-formed formulaconceptConjunction, definition, no evidence levelConjunctiondefinitionDisjunction, definition, no evidence levelDisjunctiondefinitionImplication, definition, no evidence levelImplicationdefinitionNegation, definition, no evidence levelNegationdefinitionBiconditional, definition, no evidence levelBiconditionaldefinitionPropositional logic, concept, no evidence levelPropositional logicconceptSatisfiability, definition, no evidence levelSatisfiabilitydefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Proposition concept
  2. Structure concept
  3. Well-formed formula concept
  4. Conjunction definition
  5. Disjunction definition
  6. Implication definition
  7. Negation definition
  8. Biconditional definition
  9. Propositional logic concept
  10. Satisfiability definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Satisfiability
About this page
TagK3WXSG7WBX
URIm2://K3WXSG7WBX
Kinddefinition
WritingW0 stub
MSC03B05, 03B10
DefinesSatisfiability
UsesPropositional logic, Well-formed formula, Structure
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.