Can a valid formula be satisfiable?

Yes, in an ordinary setting with permitted interpretations, it is true in all of them and therefore in at least one.

Can two satisfiable formulas conflict?

Yes. Their individual models may not overlap, making their conjunction unsatisfiable.

Is satisfiability only about Boolean formulas?

No. Boolean SAT is a prominent case, but satisfiability is defined for other logical languages and theories too.

AI Glossary / Graphs and symbolic AI / Beginner

Satisfiability

Definition

Satisfiability is the property of a logical formula or collection of constraints being true under at least one permitted interpretation. A satisfying interpretation is called a model; if no model exists, the formula is unsatisfiable.

What it means

The key phrase is at least one. Satisfiability asks whether the requirements could hold together, not whether they hold in every situation or in the actual world.

In propositional logic, an interpretation assigns true or false to each variable. In richer logics, it may also specify a domain of objects and meanings for predicates, functions or arithmetic expressions. The language and background theory determine which interpretations are permitted.

A valid formula is true in every permitted interpretation. A satisfiable formula needs only one. Some formulas are satisfiable but not valid, while a contradiction is unsatisfiable. Keeping these distinctions clear prevents a feasible possibility from being mistaken for a logical necessity.

How it works

Start with a precise formula or set of constraints and the relevant semantics. Search for a model that makes every required statement true at the same time.

For a small propositional formula, a truth table can enumerate all assignments. Larger cases use specialized reasoning procedures. In arithmetic or other theories, a solver must respect the theory's meaning rather than treating every expression as an unrelated Boolean label.

If a model is found, it witnesses satisfiability. If a complete reasoning procedure proves that no model exists, the constraints are unsatisfiable. An incomplete search or a solver response of unknown does not establish unsatisfiability.

Satisfiability also supports entailment checking. A knowledge base entails a conclusion exactly when adding the conclusion's negation makes the combined statements unsatisfiable, under the same classical semantics. The test asks whether a counterexample to the conclusion can coexist with the knowledge base.

Three practical examples

1. Rule consistency: A team checks whether several eligibility requirements can all hold for at least one hypothetical case. A positive result establishes compatibility, not that such a case has actually occurred.

2. Configuration feasibility: A set of component requirements is tested for a permitted assignment. Unsatisfiability indicates a conflict within the encoded requirements.

3. Reasoning systems: An assistant checks whether a proposed conclusion follows from formal facts by searching for a model where those facts hold and the conclusion is false.

Think of it this way

Think of a set of conditions for a possible room arrangement. Finding one arrangement that satisfies them proves compatibility; it does not prove that every arrangement works or that the room has already been arranged that way.

The analogy concerns logical possibility under a model. Physical feasibility, omitted requirements and factual accuracy still need separate treatment when translating a real situation into constraints.

Worked example

Let P mean a package is prepared and Q mean it is queued. Consider F = P OR Q. Three of the four Boolean assignments satisfy F: (true, true), (true, false) and (false, true). The assignment (false, false) does not.

Therefore F is satisfiable but not valid. By contrast, P OR NOT P is true under both values of P and is valid in classical propositional logic. P AND NOT P is false under both values and is unsatisfiable.

Now let the knowledge base contain P and P IMPLIES Q. To test whether it entails Q, add NOT Q. P forces Q through the implication, contradicting NOT Q. The combined set has no satisfying assignment, so the original knowledge base entails Q.

This is an inference about the encoded propositions. It does not independently establish that a real package was prepared.

Illustrative case study

In a fictional project, Cedar Rules checks a policy model and finds a satisfying assignment. A report then mistakenly states that the policy is satisfied by every current case.

The review separates three questions: whether the rules are mutually compatible, whether a specific recorded case satisfies them and whether a conclusion follows for all permitted cases. The team gives each question its own test and report label.

The case illustrates that a single satisfying model supports an existence claim. It cannot justify a universal statement or substitute for checking the facts of a particular record.

Common misconceptions and mistakes

Satisfiable means true in every interpretation. That is validity.
Satisfiable means true in reality. A model establishes compatibility with the formal constraints.
Individually satisfiable statements are always jointly satisfiable. P and NOT P each have a model, but their conjunction does not.
Failure to find a model proves there is none. The search must support that conclusion.
Satisfiability has identical computational difficulty in every logic. The representation and theory matter.

Business use

Satisfiability checking can reveal inconsistent requirements before they reach a workflow or product. It also helps explain why a configuration or case cannot meet all conditions simultaneously.

Preserve the connection between constraints and their originating requirements. If a solver reports inconsistency, a meaningful explanation should identify the conflicting business conditions, not only anonymous symbols. An unsatisfiable subset can help focus that review, though it need not be unique or smallest unless the method establishes that property.

Keep feasibility separate from desirability. A satisfying model may be expensive, impractical or incomplete relative to unmodeled objectives. If the task requires the best feasible outcome, additional optimization criteria are needed. If it requires a factual conclusion, validate the premises as well as the logical inference.

Check your understanding

Why is P OR Q satisfiable but not valid?

Answer: Some assignments make it true, but the assignment with both variables false makes it false. Existence of a true assignment is weaker than truth under every assignment.

Related terms

Model
Interpretation
Validity
Contradiction
SAT
Constraint satisfaction
logical entailment
satisfiability modulo theories

Learn next

Write two individually satisfiable constraints whose conjunction is impossible. Then write a satisfiable but non-valid formula and exhibit both a satisfying assignment and a falsifying assignment. Explain the different claims those examples establish.

Sources

Russell and Norvig explain models, satisfiability, validity and the connection between unsatisfiability and entailment: https://aima.cs.berkeley.edu/slides-pdf/chapter07.pdf

The package propositions and Cedar Rules case are original illustrations using classical propositional semantics. They are not claims about an actual package or policy.

Previous: Satellite image time series Next: Satisfiability threshold conjecture