Can factoring apply to negative literals?

Yes, provided the selected literals have the same sign and their atoms unify. It is not limited to positive statements.

Is duplicate removal always factoring?

Removing already identical disjuncts is the simplest special case. First-order factoring can also require a nontrivial substitution.

Can the original clause always be replaced by its factor?

No. A factor is a logical consequence, but equivalence needs additional conditions. Provers distinguish inference from sound simplification policies.

AI Glossary / Graphs and symbolic AI / Advanced

Factoring

Definition

Factoring, in automated logical reasoning, is an inference rule that combines literals of the same sign within one clause when a substitution makes them identical. The substitution is applied throughout the clause, and duplicate copies are merged. It is used alongside resolution in first-order theorem proving and is distinct from numerical or matrix factorization.

What it means

A clause is a disjunction: a statement joined by logical “or.” A literal is an atomic statement or its negation. The clause might contain two positive statements that become the same after variables are consistently replaced. Factoring derives the corresponding clause containing one copy of that statement.

The operation is more than cosmetic duplicate removal when variables are involved. It first selects an instance of the original universally quantified clause. The resulting factor follows from the original, but need not express all of the original's information. This matters when deciding whether a prover should add the factor or replace its parent clause.

How it works

Select two literals in the same clause that have matching signs: both positive or both negative. Attempt to unify their atomic expressions by finding a consistent substitution for variables. A most general unifier avoids making unnecessary additional commitments.

Apply the substitution to every literal in the clause, including literals that were not selected. The chosen literals now coincide, so retain one copy. For example, a substitution affecting x must also change occurrences of x elsewhere in that clause; failing to do so can produce an invalid inference.

Factoring differs from binary resolution, which uses complementary literals from two parent clauses and removes the resolved pair. In first-order resolution systems, factoring helps provide refutation completeness under the appropriate inference rules and search assumptions. It does not by itself decide every first-order problem or guarantee that an implemented search will terminate.

Three practical examples

1. A theorem prover encounters two same-sign literals that can be unified within a generated clause. Factoring produces a shorter consequence that may participate in a later resolution step.

2. A formal verification exercise records a factor's parent clause and substitution in its proof trace. A proof checker can then verify the local inference without trusting the search heuristic that discovered it.

3. A logic teaching tool contrasts P(x) or P(a) with P(x) or not P(a). The first pair can support factoring with x replaced by a; the second has opposite signs and is not a factoring pair.

Think of it this way

Think of a form with two statements that become the same when a shared blank is filled in. Once the blank is consistently filled throughout the form, repeating the identical statement adds nothing to an “or” list. The analogy is limited: logical variables are universally quantified in clauses, and choosing an instance is not generally a reversible editing operation.

Worked example

Let the clause be P(x) or P(a) or Q(x), with x universally quantified and a a constant. Choose the two positive P literals. The substitution x := a makes them identical.

Applying that substitution to the whole clause gives P(a) or P(a) or Q(a). Merge the repeated P(a) to obtain the factor P(a) or Q(a). Notice that Q(x) also becomes Q(a). Retaining Q(x) while changing only the selected literals would not follow this inference rule.

Why is the result sound? If the original clause is true for every x, it is true for x = a. Repeated disjuncts can then be collapsed without changing that instance's truth. However, the factor only concerns a. It does not generally imply the original statement for every other object. Thus deriving this factor is valid, while discarding the parent as an equivalent replacement requires a separate justification. If the knowledge base also contains not P(a), resolution with the factor can derive Q(a).

Illustrative case study

Fictional case study: Elm Proof builds a small first-order reasoning demonstrator. Its developer merges similar-looking predicates but forgets to substitute variables in the rest of the clause. A reviewer checks a hand trace and identifies the mismatch before accepting the generated proof.

The team changes the proof record to include the chosen literals, complete substitution and resulting clause. It also distinguishes ordinary factoring from transformations allowed to replace a parent clause. The case illustrates proof-audit requirements; it claims no success on industrial verification problems or measured improvement in proof search.

Common misconceptions and mistakes

Factoring uses literals with the same sign, not a positive-negative pair. Merely sharing a predicate name is insufficient: their arguments must unify consistently. For example, incompatible constant symbols cannot simply be changed to force a match under ordinary syntactic unification.

Applying a substitution only to the selected literals is another mistake. All affected occurrences in the clause must change. Also, a shorter inferred clause is not automatically equivalent to its parent. Finally, this logical use of factoring should not be confused with splitting a probability distribution into factors or decomposing an integer into prime numbers.

Business use

Most business users encounter factoring indirectly through automated reasoning or verification tools. Its value is in supporting sound proof construction and helping the inference system explore useful consequences. A claimed proof should remain inspectable even if its search procedure is complex.

When evaluating a tool, ask whether it records checkable inference steps and how it handles substitutions, variable scope and clause simplification. Separate failure to find a proof within resource limits from a demonstrated counterexample. Factoring can be part of a trustworthy reasoning pipeline, but its presence alone does not establish that the entire pipeline or problem encoding is correct.

Check your understanding

What is wrong with turning P(x) or P(a) or Q(x) into P(a) or Q(x) using x := a?

Answer: The substitution was not applied to Q(x). The correct factor is P(a) or Q(a), with all occurrences of x consistently replaced.

Related terms

Clause
Literal
Unification
Resolution
Refutation
Most general unifier
substitution
theorem prover
soundness

Learn next

Practice unifying simple literals before factoring complete clauses. Then compare factoring with binary resolution and inspect a proof trace that records every substitution, including changes to literals outside the selected pair.

Binary resolution

Sources

Primary sources: Argonne National Laboratory, inference-rule account: https://www.mcs.anl.gov/research/projects/AR/inf_rules.html ; Geoff Sutcliffe, first-order resolution teaching material: https://www.cs.miami.edu/home/geoff/Courses/TPTPSYS/FirstOrder/Resolution.shtml . These support the logical-rule interpretation. The worked clause and fictional case are original teaching examples.

Previous: Factorial HMM Next: Factuality