Is a pure symbol always true?

No. A negatively pure symbol is set to false to satisfy its negative occurrences.

Is the pure-symbol value forced?

Not generally. It is a satisfiability-preserving choice; other models may use the opposite value.

Can purity change during search?

Yes. Assignments can satisfy clauses and leave a residual formula in which a previously mixed symbol occurs in only one polarity.

AI Glossary / Graphs and symbolic AI / Intermediate

Pure symbol

Definition

A pure symbol is a propositional variable that appears with only one polarity in the relevant clauses of a satisfiability problem: always unnegated or always negated. Assigning it the value that makes those occurrences true can simplify a search for a satisfying assignment. The term is commonly encountered in the pure-symbol or pure-literal rule used with DPLL-style SAT solving.

What it means

In a formula written as an AND of OR-clauses, P and not P are opposite literals of the same symbol. If every relevant occurrence is P, the symbol is positively pure; if every occurrence is not P, it is negatively pure. If both occur, it is not pure.
The relevant clause set can change as a partial assignment satisfies clauses or makes literals false. A symbol that was mixed in the original formula may become pure in the remaining unsatisfied clauses. Purity is therefore a property of a formula or residual search state, not an intrinsic property of the symbol's name or intended meaning.

How it works

Inspect the unsatisfied clauses and identify a variable occurring in only one polarity. Set a positively pure symbol to true or a negatively pure symbol to false. Every clause containing that literal becomes satisfied, and no remaining occurrence of its opposite can be harmed. Continue simplifying or searching the residual formula.
This preserves the existence of a satisfying assignment: if the residual problem is satisfiable, a solution can be extended with the selected pure-symbol value. It does not necessarily preserve every original satisfying assignment. Pure-symbol elimination differs from unit propagation, where a clause with only one possible remaining literal forces that literal for any satisfying extension.

Three practical examples

A small SAT solver can simplify a configuration formula before branching on variables with both polarities.
A logic teaching tool can show how removing already satisfied clauses exposes newly pure symbols.
A symbolic planning encoding can use satisfiability preprocessing where preserving the existence of a plan is the required goal.

Think of it this way

Think of a checklist where every remaining mention of an optional feature asks for it to be enabled, and none asks for it to be disabled. Enabling it resolves those requests without conflicting with the remaining checklist. The analogy is limited because purity is a precise property of clause syntax; informal preferences or unstated requirements cannot justify the logical simplification.

Worked example

Consider the invented CNF formula (P or Q) and (P or not Q) and (not R or S). P occurs only positively, so setting P = true satisfies the first two clauses. Q occurs in both polarities initially, but it no longer matters once those clauses are satisfied.
In the third clause, R occurs only negatively and S only positively. Setting R = false makes not R true and satisfies that clause. One resulting complete model is P = true, Q = false, R = false, S = false. All three original clauses evaluate to true.
This example also exposes a limit. The original formula has satisfying models with R = true and S = true, but choosing R = false does not enumerate them. The pure-symbol step is suitable for finding whether a model exists, not automatically for counting all models.
For a second check, consider only P or Q. P is pure, so P = true is a safe satisfiability choice, yet P is not entailed: P = false, Q = true also satisfies the formula. A pure-symbol assignment need not be a logically forced conclusion.

Illustrative case study

Fictional case: Moss Configurator adds a pure-symbol simplification to a teaching SAT solver. The developers correctly find one valid configuration, then mistakenly report the chosen values as requirements that all valid configurations must satisfy.
A reviewer uses the single clause P or Q to demonstrate the mistake. The interface is revised to distinguish a convenient satisfying choice from a forced assignment. The fictional case illustrates how a correct decision procedure can be misinterpreted when its output is reused for a different question. No real performance improvement or production result is claimed.

Common misconceptions and mistakes

Do not treat purity as a vote based on frequency. Ten positive occurrences and one negative occurrence still make a symbol mixed. Do not include already satisfied clauses when determining purity for the standard residual-formula rule if doing so obscures newly available simplifications.
Conversely, never ignore an unsatisfied occurrence of the opposite polarity. Choosing a value without checking all relevant clauses can invalidate the reduction. A symbol absent from the residual formula can be assigned freely for satisfiability, but it need not be called pure under every convention. Finally, preserving satisfiability is weaker than preserving the complete model set or all logical consequences.

Business use

The practical value is a transparent simplification in systems that encode choices as Boolean constraints. It can reduce the number of branches needed to find a feasible configuration, though the benefit depends on the instance and implementation. It is one component, not a complete SAT-solving strategy.
For a prototype, verify returned assignments against the original formula. If the application asks which options are mandatory, perform a separate entailment or backbone analysis rather than interpreting the solver's chosen model as universal. If the task counts or samples configurations, check whether preprocessing preserves the needed information and how eliminated variables are reconstructed.

Check your understanding

Is P pure in (P or Q) and (not P or R), even if the first clause is repeated many times?

Answer: Not in the full unsatisfied formula. P appears both positively and negatively. Repeating one polarity does not remove the other. If a partial assignment already satisfies the second clause, P may become pure in the remaining clauses.

Related terms

Learn next

Learn unit propagation and SAT backbones next. Compare the formulas P and P or Q. Explain why the first forces P while the second merely permits setting a pure P to true. Then verify every satisfying assignment of the two-symbol formula by enumeration.

Unit propagation

Sources

AIMA Python project, logic implementation, DPLL and find_pure_symbol: https://aimacode.github.io/aima-python/_modules/aima/logic.html Stuart Russell and Peter Norvig, AIMA Chapter 7 propositional reasoning background: https://aima.cs.berkeley.edu/slides-pdf/chapter07.pdf

Previous: Pure strategy Next: PVLV