Does locking change the truth conditions of a clause?

The labels are search-control information. The underlying clause retains its logical meaning.

Is every sound resolution inference allowed under locking?

No. The purpose of the restriction is to permit only selected inferences according to the labeling discipline.

Is the simple lowest-index rule a complete theorem prover?

No. A full implementation also needs its specified inference rules, search process, unification behavior, and any required factoring or equality treatment.

AI Glossary / Graphs and symbolic AI / Advanced

Locking

Definition

In historical automated theorem proving, locking is a restriction on resolution that uses labels on literal occurrences to control which inferences are permitted. It reduces the number of possible resolution choices by imposing an order within clauses. This entry uses the theorem-proving meaning associated with Boyer's work, rather than the separate computing meaning of locking shared resources.

What it means

A resolution prover searches for consequences of logical clauses, often aiming to derive a contradiction after adding the negation of a conjecture. Without restrictions, many complementary literal pairs may be available for resolution, creating a large search space.

Locking adds control information to that search. The labels do not change what a clause means logically; they influence which derivations the procedure explores. This distinction matters: an inference can be logically sound but disallowed by a particular search discipline. Restricting search is useful only when the intended proof procedure retains the guarantees required for its task.

How it works

In a common instructional presentation of lock resolution, each input literal occurrence receives a distinct index. Binary resolution is permitted on the lowest-index literal in each participating clause. Literals that remain in a derived clause inherit their indices from their parents.

For first-order clauses, complementary literals must also satisfy the ordinary unification requirements. Full calculi need appropriately defined factoring and other supporting rules; the index restriction alone is not a complete implementation specification.

Numbering conventions and related variants should be read together with their formal definitions. In particular, equality reasoning introduces additional rules and restrictions. Do not assume that a rule from one presentation can be freely combined with every pruning or simplification technique used by another prover.

Three practical examples

1. An automated-reasoning course compares unrestricted resolution with a labeled version on a small clause set, making the reduction in immediately available inference choices visible.

2. A theorem-prover researcher studies how literal-selection restrictions affect generated clauses and proof discovery on documented benchmark problems.

3. A verification specialist examining an older prover's literature encounters locking as part of its proof-search design. Understanding the term helps interpret the algorithm's stated scope and correctness argument.

Think of it this way

Think of a file of tasks where each task contains a numbered list of items, and the workflow permits processing only the first eligible item. Finishing that item can expose a later one.

The analogy explains controlled eligibility, but logical clauses are disjunctions, not ordinary task lists. Resolution combines information from two clauses under a mathematical inference rule. The labels govern search; they do not mean that later statements are less true, less important, or temporarily absent from the clause's meaning.

Worked example

Use a propositional example with three clauses. Write C1 as P[1] or Q[2], C2 as not P[3], and C3 as not Q[4]. Bracketed numbers label literal occurrences; they are not part of the propositions.

Under the lowest-index convention, C1 initially allows resolution on P[1]. Its Q[2] occurrence is not yet eligible. Resolve C1 with C2 on P and not P. Both selected occurrences are lowest-index within their respective clauses. The result is the unit clause Q[2], retaining the original index.

Now Q[2] is the only literal in its clause, so it can resolve with C3's not Q[4]. The result is the empty clause, representing contradiction. The starting clauses cannot all be true: P or Q conflicts with both P and Q being false.

Unrestricted resolution could instead begin by resolving C1 with C3 on Q. Locking disallows that particular first move under these labels, while the displayed permitted route still finds the contradiction. This original hand trace does not establish completeness for arbitrary first-order inputs.

Illustrative case study

Fictional case: Elm Verification reviews a historical reasoning component whose documentation mentions locked resolution. An engineer first assumes the term concerns concurrent access to shared memory, then checks the proof-procedure description and discovers it refers to literal ordering.

The team reproduces a small labeled proof by hand and separates the component's inference rules from its search restrictions. Before relying on the component for a new requirement, they inspect its supported logic, proof output, and treatment of equality. This hypothetical case illustrates technical interpretation, not a claim that a particular product uses locking or achieves a verified performance gain.

Common misconceptions and mistakes

Do not confuse this meaning with mutexes, database locks, or file locks. Those coordinate access to resources; resolution locking controls permitted proof-search steps.

Do not renumber derived literals casually if the chosen calculus requires inherited indices. The labels participate in the search restriction, so changing them can change the procedure being executed.

Also distinguish soundness from completeness. An allowed resolution step can remain sound even when an added restriction makes a procedure miss proofs. Combining individually attractive heuristics requires checking the resulting calculus, rather than assuming their guarantees automatically combine.

Business use

This is a specialist term most useful when evaluating automated-reasoning methods or reading historical verification literature. A business stakeholder usually needs the consequences of a prover's design more than its literal-numbering details.

Ask what logic the tool supports, whether successful results include checkable proofs, and how timeouts or unsuccessful searches are reported. A failure to find a proof within a budget is not automatically a counterexample. For engineering teams modifying a prover, benchmark measurements should accompany an explicit review of the inference system and its assumptions.

Check your understanding

Why can Q[2] resolve in the second step of the worked example but not in the proposed alternative first step?

Answer: Initially P[1] has priority within C1. After resolving away P, Q[2] is alone in the derived clause and becomes eligible under the stated convention.

Related terms

Resolution
Literal
Clause
Unification
Factoring
Refutation
automated theorem proving
search strategy

Learn next

First practice ordinary propositional resolution, then annotate literal occurrences and compare permitted derivations. Study a complete published calculus before extending the exercise to first-order clauses or equality.

Sources

Geoff Sutcliffe, lock-resolution course presentation: https://www.cs.miami.edu/home/geoff/Courses/TPTPSYS/FirstOrder/SyntacticRefinements.shtml

Laurent Fribourg, historical locking and equality-related development: https://www.ijcai.org/Proceedings/83-2/Papers/073.pdf

Boyer's bibliography confirms the 1971 thesis: https://www.cs.utexas.edu/~boyer/publications.html

AIMA first-edition author index lists locking among theorem-proving terms, p.312: https://people.eecs.berkeley.edu/~russell/aima1e/defs.html

Historical resolution sense explicitly adopted; supplied glossary remains unavailable. The example uses Sutcliffe’s stated instructional convention.

Previous: Locative adverb Next: Locks with ordered sharing