Must the initial support be the negated goal?

No. That is a common choice when the remaining assumptions are satisfiable, but other valid selections are possible.

Can two supported clauses be resolved together?

Yes. Requiring at least one supported parent allows both parents to be supported.

Does the strategy change what a sound resolution step means?

No. It controls which steps are attempted; the logical validity of the underlying inference remains a separate requirement.

AI Glossary / Graphs and symbolic AI / Advanced

Set of support

Definition

A set of support is a selected group of clauses used to guide resolution-based theorem proving. The strategy permits a resolution step only when at least one parent clause belongs to that group or descends from it, keeping the proof search connected to selected starting information.

What it means

Resolution proves a claim by seeking a contradiction from the assumptions together with the negation of the claim. Without guidance, a prover can generate many consequences of background rules that do not help answer the current question.

A set-of-support strategy limits which combinations are explored. The initial support often contains clauses from the negated goal, while the remaining clauses describe background knowledge. Newly generated supported consequences can participate in subsequent steps.

There is an essential qualification: the usual refutation-completeness guarantee requires the clauses outside the initial support to be jointly satisfiable, together with an appropriate complete calculus and fair search. Picking an arbitrary small subset and blocking everything else can lose proofs. “Support” here refers to proof-search organization, not statistical confidence or customer assistance.

How it works

The prover transforms formulas into a suitable clause representation. A clause is a disjunction of literals, such as “not Approved or Released.” It partitions the initial clauses into supported clauses and background clauses.

For binary resolution, a permitted inference combines complementary literals from two clauses when at least one parent is supported. The remaining literals form a resolvent, which inherits support. In first-order logic, unification and the calculus's other required operations must also be handled correctly.

The empty clause represents a contradiction. Reaching it establishes that the encoded assumptions and negated goal cannot all hold. A resource limit without a contradiction does not establish that the goal is false. Practical provers may organize clauses using queues with names such as sos and usable; those implementation lists should not be assumed to preserve exactly the same membership as the abstract initial-support partition throughout a run.

Three practical examples

A theorem-proving exercise starts with the negated target theorem as support to focus reasoning on that target.
A rule-verification prototype checks whether an encoded release condition follows from a consistent collection of workflow rules.
A researcher compares unrestricted resolution with a supported strategy, measuring generated clauses as well as completed proofs and runtime.

Think of it this way

Think of investigating a question by following evidence connected to that question, instead of deriving every fact available in an archive. Each new relevant inference creates another lead.

The analogy has limits. Logical support is defined through formal derivation, not a human judgment that a document looks relevant. Excluding unrelated-looking material is safe only under the strategy's stated logical conditions; intuition alone does not establish completeness.

Worked example

Following the negated goal to contradiction

Use an invented propositional example with background clauses P, not P or Q, and not Q or R. These are jointly satisfiable: assigning P, Q and R true satisfies all three. The goal is R, so place not R in the initial set of support.

Resolve not R with not Q or R to obtain not Q. This new clause is supported. Resolve not Q with not P or Q to obtain not P, also supported. Finally, resolve not P with P to obtain the empty clause. Every resolution step includes a supported parent, and the contradiction proves R from the background assumptions.

Why does consistency matter? Suppose instead that the background contains P and not P, while the support contains only an unrelated not R. The whole collection is inconsistent, but the restricted search has no supported resolution involving R that exposes the P contradiction. This deliberately unsuitable partition illustrates why the background-satisfiability condition cannot be omitted.

Illustrative case study

Fictional case study: Cedar Rule Lab tests a small collection of document-release rules. The team uses negated questions as the initial support, assuming that the background rule collection is consistent.

After merging two departments' rule sets, a separate check reveals contradictory background assumptions. A developer had interpreted an unsuccessful supported proof search as evidence that the questioned release condition did not follow. That conclusion was unwarranted, especially because the assumed consistency condition had failed.

Cedar separates background-consistency checks, theorem queries and timeout reporting. It retains proof traces for successful results and documents the supported-search configuration. The fictional lesson is that search guidance and logical guarantees must be reported together; a convenient strategy cannot compensate for contradictory or incorrectly encoded assumptions.

Common misconceptions and mistakes

Any small support set preserves completeness. The complement must satisfy the relevant consistency condition, and the inference/search procedure must meet its requirements.
The support never grows. Derived clauses with supported ancestry carry the reasoning forward.
A timeout means the theorem is false. It means the available search did not establish the requested result within its limits.
Set of support is the same as unit preference. Unit preference favors particular clause shapes; support restricts permitted ancestry in inference.

Business use

This concept matters primarily when interpreting automated-reasoning tools and their assurance claims. A business reviewing a symbolic verification result should know which assumptions were encoded, whether consistency was assessed and what the reported outcome actually establishes.

Ask for a proof or a clearly classified unsuccessful result, rather than treating every run as a yes/no answer. Strategy choices can affect efficiency substantially, but fewer generated clauses do not by themselves establish better performance across problems or stronger correctness guarantees.

Check your understanding

A prover excludes all background-to-background resolutions, but its background already contains P and not P. Can it cite the usual set-of-support completeness guarantee without qualification?

Answer: No. The required satisfiability condition for that background partition is violated. The search design or partition needs reconsideration.

Related terms

Learn next

Read resolution and refutation completeness. Reproduce the three-step P-to-R example, marking supported ancestry on every derived clause. Then remove one background implication and explain why the previous proof no longer works.

Sources

Prover9 official manual, glossary: https://www.cs.unm.edu/~mccune/prover9/manual/2009-11A/glossary.html. Maria Paola Bonacina, Set of Support, Demodulation, Paramodulation: A Historical Perspective, author manuscript: https://iris.univr.it/retrieve/c17f559c-ee16-44b7-8e84-5c49d14e4a67/JAR2022LWHistoricSurvey.pdf. Relevant strategy, consistency and implementation distinctions were reviewed. The propositional proof and business scenario are original illustrations.

Previous: Set-level Next: Set-oriented approach