Does SAT require the input to be written in CNF?

The general problem concerns Boolean formulas; CNF is a common solver input form, often obtained through a suitable transformation.

Can a formula have several satisfying assignments?

Yes. A solver may return one without enumerating the others.

Is SAT the same as SMT?

No. Satisfiability modulo theories adds background theories such as arithmetic or arrays, rather than treating every expression as purely propositional.

AI Glossary / Graphs and symbolic AI / Intermediate

SAT

Definition

SAT is the Boolean satisfiability decision problem: given a propositional formula, determine whether some assignment of true or false values to its variables makes the entire formula true. A satisfying assignment is a witness that the answer is yes.

What it means

SAT provides a common language for combinations of yes-or-no requirements. A variable may represent whether a feature is enabled, a task occupies a time slot or a component is selected. Logical formulas express the allowed combinations.

A SAT solver searches for an assignment satisfying all encoded requirements or establishes that no such assignment exists. The result concerns the formula supplied to it. An incorrect or incomplete encoding can produce a mathematically correct answer to the wrong business question.

SAT asks whether a solution exists, not which solution is cheapest or how many solutions exist. Optimization variants such as MaxSAT and counting problems such as model counting ask different questions, even though they share some techniques.

How it works

Many solvers accept conjunctive normal form, or CNF: an AND of clauses, where each clause is an OR of literals. A literal is a variable or its negation. Every clause must be true, but each clause needs only one true literal.

A basic complete solver assigns variables, propagates forced consequences and backtracks when it reaches a conflict. Modern conflict-driven solvers can learn clauses from conflicts so that related unsuccessful choices are avoided later.

A satisfiable result can be checked by evaluating the formula under the returned assignment. An unsatisfiable result needs a complete argument rather than merely an unsuccessful search attempt; some solvers can emit proof information for independent checking.

General SAT is NP-complete, but that does not mean every instance is difficult. Structure and encoding strongly affect practical performance. A timeout is an unresolved computation, not evidence that the formula is unsatisfiable.

Three practical examples

1. Product configuration: Boolean variables represent optional components, while clauses encode compatibility and dependency rules. A satisfying assignment describes one allowed configuration.

2. Scheduling: A bounded schedule is encoded with variables for task-slot choices and clauses preventing conflicts. Additional constraints must ensure that every required task is actually assigned.

3. Software verification: An analysis encodes a bounded execution that would violate a property. A satisfying assignment can identify a candidate counterexample within that bound.

Think of it this way

Think of SAT as finding settings for a panel of yes-or-no switches so that every indicator requirement is satisfied. One requirement may allow either of two switches, while another forbids them both being on.

The analogy describes the logical search, not the correctness of the requirements. If an important condition was never connected to an indicator, the resulting switch setting can pass the model while failing the real task.

Worked example

Let A mean that an analytics feature is enabled, E that export is enabled and L that a logging feature is enabled. Require at least one of analytics or export: A OR E. Require logging whenever analytics is enabled: NOT A OR L. Finally, forbid logging in the selected configuration: NOT L.

The full formula is (A OR E) AND (NOT A OR L) AND NOT L. The last clause forces L to false. The second then forces A to false. The first consequently forces E to true.

Thus A=false, E=true, L=false satisfies all three clauses. If a new requirement A is added, the formula becomes unsatisfiable: A requires L, while NOT L forbids it.

This is a toy compatibility model. It demonstrates propagation and conflicting constraints, not a recommendation to disable logging in a real application.

Illustrative case study

In a fictional project, Maple Config uses SAT to check optional equipment bundles. The solver returns a valid assignment, but a reviewer notices that the encoding omitted the requirement to choose at least one power source.

The team adds the missing condition and creates small examples with known valid and invalid outcomes. It checks the decoded configurations against the original requirements, not only against the generated clauses.

The case illustrates that solver reliability and encoding correctness are separate responsibilities. A strong solver cannot infer a requirement that was never represented.

Common misconceptions and mistakes

SAT stands for one particular solver. It names a decision problem, with many solving algorithms and implementations.
Every clause requires all its literals to be true. An OR clause needs at least one true literal.
A timeout means unsatisfiable. It means the attempt did not finish with a conclusive result.
A satisfying assignment is necessarily optimal. SAT alone imposes no preference among satisfying assignments.
NP-complete means practical instances cannot be solved. Many structured instances are solved effectively, though worst-case difficulty remains.

Business use

SAT can support configuration, verification and planning when requirements can be encoded as Boolean constraints. Its value is a precise feasibility question with a checkable witness for a positive answer.

Review the mapping between domain decisions and variables, including how auxiliary variables are interpreted. Test constraints individually and in combinations that should conflict. Keep a clear distinction between no solution under the model and no practical solution in the wider world.

For important conclusions, document solver settings, limits and the form of evidence returned. A bounded verification result should state the bound. If costs or preferences matter, choose an appropriate optimization formulation rather than assuming the first feasible assignment is the best one.

Check your understanding

Why does adding A to the worked formula make it unsatisfiable?

Answer: A forces L through the dependency clause, but the formula also requires NOT L. No assignment can satisfy both requirements.

Related terms

Satisfiability
Clause
Conjunctive normal form
Boolean logic
DPLL
conflict-driven clause learning
MaxSAT
SMT

Learn next

Encode a small configuration with three Boolean choices, one dependency and one incompatibility. Find a satisfying assignment by hand, then add a requirement that creates a contradiction. Explain the conflict in the original domain language.

Sources

Russell and Norvig's logical-agent material covers propositional satisfiability, CNF and DPLL-style solving: https://aima.cs.berkeley.edu/slides-pdf/chapter07.pdf

The feature-configuration formula and Maple Config case are original teaching examples. They illustrate feasibility and encoding review, not a production configuration policy.

Previous: SARSA(lambda) Next: Satellite image time series

SAT