Resolution is a powerful and commonly used method for automated theorem proving in propositional logic. It serves as the basis for many advanced techniques in artificial intelligence and computer-aided verification. This article delves into the resolution algorithm, explaining its inner workings, essential concepts, and providing illustrative examples.

Introduction to Propositional Logic

Propositional logic is a branch of logic dealing with formulae composed of propositions and logical connectives. A proposition is a statement that can be either true or false, but not both. The logical connectives typically used are:

• AND ($\land$)
• OR ($\lor$)
• NOT ($\neg$)
• IMPLIES ($\rightarrow$)
• IF AND ONLY IF ($\leftrightarrow$)

The primary goal in propositional logic is to determine the logical validity of certain propositions. Given a set of propositions (premises), one must ascertain whether a particular conclusion follows.

The Resolution Rule

The resolution rule in propositional logic is a single inference rule used to derive conclusions from known implications. The rule applies to disjunctions of literals, and it can be stated as follows: from two clauses $(A \lor C)$ and $(\neg A \lor D)$, one can infer the clause $(C \lor D)$.

This rule exploits the law of excluded middle, assuming $A$ is either true or false. If $A$ is true, then the second clause is satisfied by $D$. Conversely, if $A$ is false, then the first clause is satisfied by $C$.

Preconditions for Resolution

1. Conjunctive Normal Form (CNF): The resolution rule requires the formulae to be in Conjunctive Normal Form, where each formula is a conjunction of disjunctions of literals. For instance, $(A \lor B) \land (\neg B \lor C) \land (\neg A \lor \neg C)$ is an example of a CNF expression.
2. Pair of Clauses: The resolution operates on two clauses that contain complementary literals. These literals are negations of each other, such as $A$ and $\neg A$.

The Resolution Process

1. Convert to CNF: Begin by converting all the given propositions to CNF. This involves the application of logical equivalences such as De Morgan's laws and distribution of disjunctions over conjunctions.
2. Apply Resolution Rule: For each pair of clauses containing complementary literals, apply the resolution rule to derive a new clause. This step involves removing the complementary literals and combining the remaining literals.
3. Iterate: Repeat the resolution step with the newly formed clauses along with existing clauses.
4. Check for Contradiction: If you derive an empty clause, represented by $\bot$, a contradiction is found, and the original set of formulae is unsatisfiable—indicating that the negation of the conclusion is false, proving the conclusion.
5. Termination: If no new clauses can be generated without deriving an empty clause, and if the conclusion cannot be proven directly, the process terminates, suggesting that the conclusion does not logically follow.

Example: Resolution in Action

Consider the following set of premises and conclusion:

• Premises: $P \lor Q$, $\neg P \lor R$, $\neg Q \lor \neg R$.
• Conclusion: $R$.

Step-by-Step Resolution

1. Convert to CNF: The premises are already in CNF.
2. Identify Pairs and Resolve:
   • From $(P \lor Q)$ and $(\neg P \lor R)$, resolve on $P$:

$$(Q \lor R)$$

• From $(Q \lor R)$ and $(\neg Q \lor \neg R)$, resolve on $Q$:

$$(R \lor \neg R)$$

• From $(R \lor \neg R)$ logically simplify to $\top$ (a tautology), but continue for resolution purposes.

1. Check for Empty Clause: There is no direct derivation of the empty clause in this example without additional information or different clauses that lead to $\bot$. Conversely, reaching $\top$ implies consistency without contradiction in this context.

Understanding Completeness and Soundness

The resolution method is both complete and sound:

• Soundness: If the resolution method derives a conclusion, it is guaranteed to be logically valid.
• Completeness: If a conclusion is valid, the resolution method will be able to derive it given enough resources.

Summary Table

Conclusion

Resolution is an essential algorithm in automated reasoning for propositional logic. By converting formulae to CNF and applying the resolution rule, one can methodically derive conclusions or establish the inconsistency of a set of propositions. Understanding resolution's intricacies equips one with a fundamental tool for tackling logical propositions in fields such as computer science, mathematics, and philosophy.