Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm reviewing for a final exam on Monday, and I have a question I was unable to answer on a previous test. The professor's notes were horrendous, and I can't find anything better online. They all seem to talk way over my head.

For each of the following pairs of literals, determine whether or not they are unifiable. If they do, show the unifiers.

  1. P(a), Q(g(x))
  2. P(x), Q(g(a))

I have a feeling that it's insanely easy, as the prof (despite teaching horribly, gives easy enough questions) but I still have no idea what to do.

share|cite|improve this question
"The professor's notes were horrendous, and I can't find anything better online." I'm a dinosaur, but can't help thinking "Try your university library. Look at a book or two ...". – Peter Smith Dec 9 '12 at 12:06
@PeterSmith I've seen a couple of textbooks, and they don't seem to help me at all either. They explain things in a way that is far too technical for me to grasp. I need examples of how to apply the algorithm, not just the algorithm. – agent154 Dec 9 '12 at 19:52
up vote 3 down vote accepted

There is no unification in either case, since whatever you substitute for $x$ (and perhaps $a$; you didn't state which symbols are variables to be substituted), the first expression of the pair will have $P$ as its outermost symbol and the second one will have $Q$.

share|cite|improve this answer
why the downvote? – joriki Dec 9 '12 at 2:47
@sunflower: I guessed as much, but it would be considerably more helpful if you explained why you think it's wrong. – joriki Dec 9 '12 at 2:48
@sunflower: This is rather unconstructive -- you wrote two different answers, now you've deleted them both without ever replying to my comment under one of them; you've also removed what minimal explanation you'd given for your downvote on my answer, but apparently you haven't removed the downvote itself. I would appreciate a more interactive approach, and in particular an explanation of your downvote, all the more so since your deletion of your own answers seems to suggest that you now agree with my interpretation of the question. – joriki Dec 9 '12 at 3:01
So, if two predicates are different - in this case, P and Q, they cannot be unified? – agent154 Dec 9 '12 at 20:15
@agent154: Yes. In a now deleted answer, sunflower gave a unification algorithm which has an explicit rule to that effect: "The unification of two functors with different name or arity fails." From your comment under the question it seems you have access to textbooks with unification algorithms. If you take a look at one of them, I expect you'll find a similar rule, or you can at least infer from the rules as a whole that they can never unify two predicates with different name or arity. – joriki Dec 9 '12 at 20:45

Your Answer


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.