Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I have been reading on converting first order logic sentences to conjunctive normal form, and then performing resolution.

One of the steps of converting to CNF, is to Standardize variables: rename all variables so that each quantifier has its own unique variable name.

Most general Unifier is the least specialized unification of two clauses.

Question 1: I have been searching to find an example that shows what are the potential problems if I don't standardize variables, but all the online resources I found only explain the "How" and not the "Why". Could you provide me with an example of a potential problem?

Question 2: The same problem as the first question. What if we don't use MGU, and use a more specialized unifier? What are the potential problems? Could you provide me with an example?

My sincere thanks. Felipe

share|improve this question

1 Answer 1

up vote 0 down vote accepted
  1. See this answer - it's an example of a contradictory set of clauses where we cannot derive a contradiction without renaming variables. Note that it's not sufficient to only rename variables after the conversion to CNF, we have to rename variables to be distinct before every application of the resolution rule. You can view it as follows: A variable appearing in two distinct clauses has different meaning in each of them as they're implicitly universally quantified. If we don't rename the variable in one of the clauses, we make a false assumption that the variable means the same in both clauses.

  2. By using MGU, we derive the most general clause in a resolution step. If we use any unifier that is more specialized than their MGU, the resulting clause is weaker. This means, that we didn't infer all the knowledge we could, and we can miss a derivation of an empty clause even if it exists. For example: \begin{array}{c} P(x,y) \lor Q(y) \\ \lnot Q(d) \\ \lnot P(c,d) \end{array} If we make a resolvent from the first two clauses using MGU which sends $y\to d$, we get $P(x,d)$ and we can proceed with the third clause. If we take a weaker unifier, like one that also sends $x\to d$, we get $P(d,d)$ and we're not able to make a resolvent with the third clause. This means the method is no longer complete.

share|improve this answer
    
Thanks for the reply –  FELIPE N. Feb 3 '13 at 15:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.