5.7. Example of Resolution Tree

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. 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.

To build a resolution tree with a set of 'n' clauses, we start by gathering all the clauses together at the root level of the tree. These clauses can be resolved in pairs. Each time we resolve a pair of clauses, we create a new clause (the resolvent) that represents the outcome of that resolution. This new clause is then added to the tree. We continue this process, resolving different pairs of clauses until there are no more pairs that can be resolved.

Think of a resolution tree like a family tree. At the top level, you have a set of family members (the clauses) gathered together. As you connect pairs of family members through their relationships (resolutions), new branches (resolvents) are formed, which lead to new family members. You keep branching out until there are no more relationships to explore.

Let me give you an example to show how exactly we compute the resolution of a set of clauses. Imagine you are given here compound propositions p → q, r → s, p and r. The first step will be that I will be converting this compound propositions into their corresponding clause form because as of now p → q is not in its clause form.

In this example, we start with several compound propositions like 'p → q', 'r → s', 'p', and 'r'. The first task is to convert these into their clause forms: '¬p ∨ q' for 'p → q' and '¬r ∨ s' for 'r → s'. Once we have converted them, we represent them as clauses C1, C2, C3, and C4. We then build the resolution tree by starting with these clauses and resolving pairs to find new clauses until we can no longer resolve.

Imagine you are baking a cake using several ingredients. Each ingredient represents a clause. Before baking, you combine the ingredients (convert them to clause form). You then mix (resolve) two ingredients at a time until you create a smooth batter (the resolution tree). Eventually, when all ingredients are properly mixed and there are no more to add, you are ready to bake your cake.

So now here is how I can build my resolution tree at the root I can pick, I can keep all the clauses that are there currently in my set S. And now I keep on picking clauses, pair of clauses, which I can resolve. So for instance, I can resolve these two clauses by cancelling p and ¬ p and the resolvent will be q which will be now added to the tree.

Once we have our clauses in the root of the tree, we identify pairs that can be resolved based on the resolution rule. For instance, if we have a clause with 'p' and another with '¬p', these can be resolved. The result of this resolution is a new clause, which we can express as 'q'. This new clause is then added to our resolution tree, and we continue looking for pairs to resolve.

Imagine you are organizing a party and inviting people. Each guest represents a clause. If two guests are related in a specific way (e.g., one is bringing snacks and the other drinks), you can combine their efforts into one plan (resolvent). Each successful combination gets noted down, and you keep doing this until no more guests can combine their efforts.

Imagine you are given a set of n clauses. The claim here is that the empty clause or the constant False will belong to the resolvent of this set of clauses if and only if this, the set of clauses in S is unsatisfiable.

The empty clause, or the constant False (ϕ), indicates that the set of clauses we are examining has no possible truth assignment that makes them all true at the same time. If we can derive this empty clause from our resolution tree, it confirms that the original set of clauses is unsatisfiable, meaning they contradict each other.

Think of a situation where you and your friends are trying to agree on a place to eat. If one friend wants Italian food while another insists on sushi, and no restaurant serves both simultaneously, you reach a dead end (empty clause). This shows that the set of desires (clauses) is contradictory and unsatisfiable.

In the proof by resolution refutation the goal is the following you are given an argument form and you have to verify whether this argument form is valid or invalid.

The resolution refutation process allows us to check if an argument is valid by converting the arguments into clause forms and then trying to derive a contradiction. To do this, we combine all the premises with the negation of the conclusion and attempt to find an empty clause. If we can arrive at a contradiction, it demonstrates that the original argument was valid.

Consider it like a detective investigating a case. The detective collects all clues (premises) and finds any contradictions (an empty clause) by checking if the suspects' alibis hold true. If a contradiction arises, it proves that the link made by the arguments (the suspicion) is valid, revealing the truth.

--