5.9. Proof by Resolution Refutation

So to begin with, let us try to understand what exactly is the resolution rule. It is a very important inference rule and it is used extensively in this programming language called PROLOG. So recall I said that PROLOG is an important programming language, which is used in AI applications. So what exactly is this resolution rule? So it says the following, imagine you are given two clauses. So C₁ is the clause and C₂ is another clause. And the important property here is that I have a literal L which is present in positive form in C₁ and negative form in C₂. So you can imagine that C₁ is a huge clause consisting of one or more literals, one of the literals is L. So just to recall a literal is propositional variable or the constants True or False. So what I am saying here is that we have two clauses C₁ and C₂. In C₁, we have some literal L and the same literal is available in a negation form in C₂. The remaining portion of C₁, I am denoting it as C₁' and the remaining portion of C₂, I am denoting it as C₂'. So you have 2 such clauses and what this resolution rule says is the following. It says that, if it is given that the clause C₁ and C₂ are true, then based on the truth of these 2 clauses we can conclude, conclusion C₁' ∨ C₂'. So in some sense you can imagine that resolution rule is something equivalent to cancellation rule.

The resolution rule is a significant inference method utilized in logic, particularly in programming and artificial intelligence. It allows us to derive a conclusion from two clauses that contain contradictory literals. The rule states that if we have a literal L in one clause (C₁) and its negation (¬L) in another clause (C₂), we can ignore these literals and focus on the remaining parts of the clauses (C₁' and C₂'). The conclusion derived from this process is C₁' ∨ C₂', which signifies that at least one of the remaining components must be true if the original clauses are valid. This principle is akin to 'cancellation' where we cancel out terms that oppose each other. This is important for constructing logical arguments and proofs, especially in determining truth values in propositional logic.

Imagine you have two friends who are arguing about the time of a meeting. One says, "If it is 5 PM, I will attend the meeting," and another says, "If it is not 5 PM, I will attend the meeting too." Here, the time being 5 PM and not being 5 PM contradict each other. According to the resolution rule, if at least one of them is valid (both can't be true), you can conclude that regardless of whether it is 5 PM or not, either of your friends will attend the meeting. This is similar to resolving two conflicting perspectives to find a common conclusion.

In argument form the resolution rule can be stated as follows. So this is the argument form of resolution inference rule. It says that if you are given the clauses C₁ and C₂ where, C₁ is C₁' ∨ L and C₂ is C₂' ∨ ¬ L. Then based on these two premises, you can conclude the conclusion C₁' ∨ C₂'. I stress that to apply the resolution rule you need C₁ and C₂ to be clauses. That means C₁ and C₂ have to be compound propositions which are available in the form of clause. It should not be available in a different form.

The argument form of the resolution rule clarifies how to apply this rule in logical arguments. It specifies that if we have two clauses C₁ and C₂ defined as C₁ = C₁' ∨ L and C₂ = C₂' ∨ ¬L, we can safely infer the combined clause C₁' ∨ C₂' as a legitimate conclusion. The essential requirement is that both C₁ and C₂ need to be structured as clauses, meaning they must be in a format where they can be interpreted as compound propositions. This structure supports the logical derivation and ensures that the resolution process can be applied correctly, leading to valid conclusions.

Consider a situation where a chef is discussing two recipes. Recipe A states "If I include eggs in this dish, it will be delicious" (C₁), while Recipe B states, "If I do not include eggs, this dish will also be delicious" (C₂). Both statements present possibilities concerning the inclusion of eggs. If we can agree on the affirmation (C₁) and negation (C₂), we can then say, regardless of whether eggs are used or not, the dish will turn out delicious. This scenario illustrates how resolving the two conflicting ideas leads to a comprehensive culinary conclusion.

So now we want to prove that indeed the resolution is the, indeed resolution in principle that we are stating here is a valid argument form. So what we have to prove is we want to prove this statement that indeed this implication is a tautology. So for that we assume that a left hand side of this implication namely the conjunction of C₁ and C₂ is true. Why we are assuming it to be true because remember we want to show that this implication is a tautology and this implication is true for all other cases. Remember the truth table of implication of false → false is true, false → true is true and in the same way true → true is true. So for these three cases by default this implication is always a true statement we have to consider the fourth case when your left hand side of this implication is true and we have to show in that case the right-hand side of the implication is also true.

To establish the validity of the resolution rule as a logical argument form, we need to demonstrate that it leads to a tautology. This involves assuming that the conjunction of the two clauses C₁ and C₂ is true. By exploring all truth table scenarios, we can ascertain that the implication holds true for various conditions. The pivotal aspect is to check the scenario where both clauses are true. If C₁ and C₂ are indeed true, the resolution must also maintain truth, confirming that our derived disjunction (C₁' ∨ C₂') is also a valid outcome. Thus, proving the resolution method is reliable and logical.

Consider a team making a decision where every member contributes to the final outcome. If all team members are in agreement (C₁ and C₂), the team reaches a consensus conclusion (C₁' ∨ C₂'). If it can be shown that with team agreement, the final decision must be agreeable as well, we confirm the process is valid. Just like confirming a decision is valid based on everyone's approval, affirming the tautological nature of the resolution process confirms it as a reliable logical strategy.

So we have seen already how to find or how to resolve a pair of clauses, now next we want to see how exactly we resolve a set of clauses where we may have more than two clauses. So imagine you are given a set of n clauses and I would be interested to resolve the clauses in this set, which is often called as a resolvent of the set of clauses. So the idea remains the same that means we will keep on finding two clauses from this collection and keep on resolving them and we stop till we cannot proceed further. So basically we build what we call as a resolution tree and in the resolution tree we can keep the n clauses that are given in my set S at the root level, that means by default we can imagine that the clauses C₁, C₂,..., Cₙ each of them belongs to the resolvent of my set of clauses S because I can always conclude C₁, I can always conclude C₂ and I can always conclude Cₙ from my set of clauses in S.

When resolving a collection of more than two clauses, we employ a systematic approach often visualized as a resolution tree. At the start, we have all clauses placed at the root of this tree. The process involves selecting pairs of clauses to resolve iteratively. Each resolved pair generates a new clause that also gets added to the resolution tree. This continues until no further resolutions are possible. This method supports the examination of complex relationships among the clauses while facilitating the simplification into a coherent resolution or conclusion.

Think of a project team handling multiple tasks. Each task represents a clause. By first addressing each pair of tasks and combining them into a coherent sub-task (the resolvent), the team continuously refines its project until it reaches a final cohesive plan. Drawing from multiple elements and resolving overlaps allows you to simplify complexity into actionable steps. Just as the project team eliminates inefficiencies through resolution, in logical terms, we derive clarity and conclusions by resolving clauses effectively.

--