AI Glossary / Graphs and symbolic AI / Advanced
Input resolution
Definition
Input resolution is a restricted resolution strategy in automated reasoning: at least one parent clause in every resolution step must belong to the original input clause set. The restriction reduces permitted combinations but is not complete for arbitrary clause sets.
What it means
Resolution derives a new clause by combining clauses containing complementary literals. For example, P OR Q and NOT P can yield Q. A derived clause is called a resolvent.
Input resolution adds a rule about the origin of the parents. One must be an original input; the other may be an input or a previously derived clause. It does not allow a step whose two parents are only derived clauses.
Here input resolution is a theorem-proving term. It does not mean the pixel dimensions of an image supplied to a model. The distinction matters because both phrases appear in AI literature but concern entirely different operations.
How it works
Express the reasoning problem as a set of clauses. In proof by refutation, this includes clauses representing the assumptions and the negation of the desired conclusion. Preserve which clauses belong to that initial set.
Select two eligible parents, resolve complementary literals and record the new resolvent and its provenance. For first-order clauses, suitable substitutions and variable handling are also needed. Continue searching for an empty clause, which represents a contradiction.
The input restriction is a search constraint, not a change in the meaning of logical consequence. Each correctly performed resolution step remains sound. However, some contradictions require combinations excluded by the strategy. Input resolution has useful completeness results for restricted classes, notably Horn refutation, but that should not be generalized to every first-order or propositional problem.
Three practical examples
- A theorem-proving course compares unrestricted resolution with input resolution on a small clause set.
- A logic-system researcher examines how restricting parent selection changes the available proof structures.
- A verification prototype records clause origins to check whether a claimed input-resolution proof actually obeys the restriction.
Think of it this way
Think of building an argument where each new step must cite at least one statement from the original brief. You may combine a previous conclusion with an original statement, but you cannot combine two later conclusions alone.
The analogy explains the provenance restriction. Logical resolution additionally has a precise inference rule; merely citing an original statement does not make an arbitrary argument valid.
Worked example
Seeing a refutation blocked by the input restriction
Take four input clauses: C1 = P OR Q, C2 = P OR NOT Q, C3 = NOT P OR Q, and C4 = NOT P OR NOT Q. Together they are unsatisfiable: each assignment to P and Q violates one of the four clauses.
Resolve C1 and C2 on Q to derive P. Resolve C3 and C4 on Q to derive NOT P. Both steps are allowed by input resolution because their parents are input clauses.
Unrestricted resolution can now combine P and NOT P to derive the empty clause. Input resolution forbids that final step, because both parents are derived and neither is an original input.
Could another input-resolution route reach the empty clause? In binary propositional resolution, that final result requires complementary unit clauses as parents. None of the original inputs is a unit clause, so no permitted final step can produce it. This demonstrates incompleteness for this non-Horn set.
Compare the Horn inputs P, NOT P OR Q, and NOT Q. Resolving P with the implication clause yields Q; resolving Q with the input NOT Q yields the empty clause. That refutation respects the input restriction throughout.
Illustrative case study
The fictional Maple Logic team adds a restricted resolution engine to a teaching demonstrator. The interface initially labels every search that fails to find a contradiction as consistent.
A reviewer supplies the four-clause example and observes that the restriction prevents the necessary final combination. The team changes the interface to distinguish a found refutation from a failure to find one under the selected strategy. It also displays parent origins so students can inspect why a step is allowed or forbidden.
Maple retains the Horn example as a contrasting successful case. The lesson is to match a reasoning claim to the method's completeness scope, not to interpret an unsuccessful search as a universal proof of consistency.
Common misconceptions and mistakes
- Input resolution means every parent must be an input. At least one parent must be; the other can be derived.
- It is the same as unit resolution. Unit resolution requires a unit parent, while input resolution restricts parent provenance.
- Soundness implies completeness. Sound steps can still omit proof paths needed for some consequences.
- An unresolved search proves satisfiability. That conclusion needs an appropriate complete procedure and a justified termination result.
Business use
The term is most relevant when evaluating symbolic reasoning methods rather than selecting a general business application. Its practical lesson is that a faster or simpler search restriction can change what the system is capable of proving.
When a tool claims a property has been established, ask whether it produced a checkable proof and what input class its completeness guarantee covers. For a negative result, distinguish resource exhaustion, strategy limitations and a genuine satisfiability result. Preserve clause provenance and proof traces so restrictions can be audited without relying only on the tool's final label.
People also ask
What is a Horn clause?
A clause with at most one positive literal. This restricted structure supports important reasoning procedures and completeness results.
Does input resolution permit the negated goal as an input?
Yes, when its clauses are part of the original clause set for the refutation problem.
Can a derived clause simply be renamed an input?
Doing so changes the designated input set and no longer demonstrates the original restricted proof claim.
Check your understanding
Why is the final P with NOT P step forbidden in the four-clause example?
Answer: Both unit clauses were derived. Neither belongs to the original input set, so the step violates the requirement that at least one parent be an input clause.
Related terms
Learn next
Draw the two worked proof trees and label every clause as input or derived. For each inference, check both the complementary literals and the parent-origin condition, then explain which final outcomes justify a contradiction claim.
More in Graphs and symbolic AI
- Information value theory - Information value theory evaluates information by how much it can improve a decision, taking account of uncertainty and the consequences of available actions.
- Inheritance - Inheritance in knowledge representation is the use of a category hierarchy to derive information about more specific categories or their members from...
- Initial state - An initial state is the state from which a modeled process, search problem or planning task begins.
- Inside-outside algorithm - The inside-outside algorithm is a dynamic-programming method for computing quantities over the possible parse trees of a context-free grammar.
- Instance-based learning - Instance-based learning predicts a new case by comparing it with stored examples.
- Intelligence - Intelligence is a broad term for capacities such as learning, reasoning, adapting and using information to achieve goals.
Sources
Bose and colleagues discuss the limitations of simple input resolution in their original Parthenon theorem-prover paper: https://www.cs.cmu.edu/~emc/papers/Papers%20In%20Refereed%20Journals/Parthenon_A%20Parallel%20Theorem%20Prover%20for%20Non-Horn%20Clauses.pdf
Hooker's original paper discusses input proofs and the Horn setting: https://pubsonline.informs.org/doi/abs/10.1287/ijoc.1.3.137
Relevant indexed Parthenon text and the Hooker abstract were reviewed. The small proofs are teaching illustrations; Maple Logic is fictional.
Previous: Input/Output Hidden Markov Model Next: Insertion Anomaly