Are P and Q complementary if they have different names?

Not merely because they seem opposed. A complementary pair has the same underlying atom with opposite polarity.

Is P OR NOT P a contradiction?

No. In classical logic it is a tautology; P AND NOT P is contradictory.

Can first-order literals require substitution before resolution?

Yes. A valid substitution must make their underlying atoms match with opposite polarity.

AI Glossary / Graphs and symbolic AI / Beginner

Complementary literals

Definition

Complementary literals are a pair consisting of an atom and its negation, such as P and NOT P. In classical logic, they always have opposite truth values under the same interpretation. Recognizing such pairs is fundamental to contradiction checking, clause reasoning, and the resolution inference rule used in automated theorem proving.

What it means

A literal is either an atom or a negated atom. For example, approved(order7) is a positive literal, and NOT approved(order7) is its negative counterpart. Their underlying atom must be the same for them to be complementary.

Two statements that merely sound opposed in ordinary language are not automatically complementary literals. The predicates cheap(item) and expensive(item) are different atoms unless the formal model supplies a relationship between them.

Context also matters. Approved yesterday and not approved today may describe different time-indexed atoms rather than a contradiction. The formal representation must preserve the entity, time, and other arguments before a reasoner can identify a genuine complementary pair.

How it works

In propositional logic, identify the atom and its polarity. P and NOT P form a complementary pair; P and NOT Q do not when P and Q are different propositional atoms.

Their use depends on the surrounding connective. P AND NOT P is unsatisfiable in classical logic because both cannot be true together. P OR NOT P is a tautology because at least one is true under every classical truth assignment.

Resolution operates on clauses, which are disjunctions of literals. From P OR Q and NOT P OR R, it derives Q OR R by resolving on the complementary pair involving P. This inference is justified by considering the two possible truth values of P, not by a general rule that opposite-looking text can be deleted anywhere.

In first-order resolution, a substitution may be needed to make underlying atoms match. Opposite polarity alone is insufficient: predicates, arguments, and variable substitutions must satisfy the formal matching conditions.

Three practical examples

1. A theorem prover uses complementary literals in clauses to derive a resolvent and work toward a proof by contradiction.

2. A rule-model reviewer checks whether the same precisely defined condition has been asserted both positively and negatively for one entity and time.

3. A logic tutor contrasts a contradictory conjunction with a tautological disjunction, showing why the same two literals behave differently in different formulas.

Think of it this way

Think of a single yes-or-no switch described as both on and not on at the same moment. These descriptions oppose one another only if they refer to the same switch and the same meaning of on.

The analogy is limited to classical two-valued reasoning. Missing information about the switch is not the same as an explicit statement that it is off.

Worked example

Let P mean that order7 has passed a particular check, Q mean that it requires manual review, and R mean that it can proceed to the next stage. Suppose the knowledge base contains P OR Q and NOT P OR R.

If P is true, the second clause requires R to be true. If P is false, the first clause requires Q to be true. In either case, Q OR R must hold. Resolution therefore derives that disjunction by using P and NOT P as the complementary pair.

The two original clauses do not require both P and NOT P to be true. Their occurrence inside different disjunctions does not itself make the knowledge base inconsistent.

If separate unit clauses P and NOT P were asserted, resolving them would produce the empty clause, representing contradiction. This difference shows why identifying the surrounding clause structure is as important as spotting the pair.

Illustrative case study

Fictional case: Alder Workflow tests a rule-based order assistant. Its reviewer sees approved(order7, Monday) and NOT approved(order7, Tuesday) and initially flags a logical inconsistency.

The modeling team explains that the time arguments make these different atoms. It then finds a genuine problem: both approved(order9, Tuesday) and its exact negation were imported as unconditional facts from conflicting records.

The team traces those records to their sources and resolves the data issue before relying on the model's conclusions. The fictional case demonstrates that formal contradiction detection needs accurate symbol matching, while correcting the underlying evidence remains a separate task.

Common misconceptions and mistakes

Opposite polarity does not make literals complementary if their underlying atoms differ. Check every relevant argument, not just the predicate name.

A complementary pair inside a disjunction does not create a contradiction. P OR NOT P is classically valid; P AND NOT P is the contradictory form.

Do not remove several complementary pairs at once as if resolution were unrestricted cancellation. Each inference must follow the applicable rule, or a satisfiable set of clauses can be transformed incorrectly.

Finally, absence of a positive fact is not automatically an explicit negative literal. Whether a system treats missing facts as false depends on its semantics and cannot be inferred from this definition alone.

Business use

Businesses building symbolic rules benefit from clear treatment of negation, identity, and context. Define whether a negative record means a verified negative condition, an unknown status, or a failed check; these meanings are not interchangeable.

During validation, test exact complementary facts, similar but distinct predicates, time-specific statements, and disjunctive clauses. Preserve source information so that a detected contradiction can be investigated. Logical structure can reveal incompatibility, but it does not independently decide which source record reflects reality.

Check your understanding

Does approved(order7) form a complementary pair with NOT approved(order8)?

Answer: No. The object arguments differ. They are different atoms, so opposite polarity alone does not make them complementary.

Related terms

Learn next

Write four pairs of literals, including exact complements and pairs differing in an argument. Then derive one resolvent from two clauses and verify it by checking both truth values of the resolved atom. Keep conjunction and disjunction separate throughout.

Atom

Sources

Primary source consulted: Russell and Norvig, Logical Agents teaching slides, resolution and classical propositional semantics, https://aima.cs.berkeley.edu/slides-pdf/chapter07.pdf . The order-check clauses and fictional data-review case are original examples. Scope is ordinary classical literal complementation.

Previous: Complement Of An Event Next: Complementation Rule