CS 4804 Homework #4

Date Assigned: October 3, 2003
Date Due: October 13, 2003, in class, before class starts
  1. (10 points) Problem 8.6 (h) of your textbook. Use only the following vocabulary:
    • Man(x): true when x is a man.
    • Barber(x): true when x is a barber.
    • Shaves(x,y): true when x shaves y.

  2. (10 points) For each of the following formulas, either prove that it is valid or give a counterexample to its validity. Here, "\E" denotes "there exists" and "\A" denotes "for all", P and Q are predicates).
    • {[(\Ex) P(x)] => Q(A)} => {(\Ax)[P(x) => Q(A)]}
    • {[(\Ax) P(x)] => Q(A)} => {(\Ex)[P(x) => Q(A)]}

  3. (20 points) Given the following facts:
    • If pushable objects are blue, then nonpushable ones are green.
    • All objects are either blue or green but not both.
    • If there is a nonpushable object, then all pushable ones are blue.
    • Object O1 is pushable.
    • Object O2 is not pushable.
    Express them in a suitably defined vocabulary of predicates (which you must state), and use resolution refutation to prove that there is a green object.

  4. (20 points) Problem 9.4 of your textbook (all parts).

  5. (40 points) Given the following facts:
    • Professors fall into three mutually exclusive categories: assistant professors, associate professors, and full professors.
    • An assistant professor can be evaluated by both associate and full professors. An associate professor can be evaluated by only full professors.
    • Dr. Knowitall is an associate professor. Dr. Shiny is an assistant professor. Dr. Gray and Dr. White are full professors. These, together with Dr. Strangelove, make up the entire department.
    • There exists exactly three two people who can evaluate Dr. Strangelove.
    State these facts (and any more that you need) in predicate logic (in a suitably defined vocabulary, which you must state), and use resolution-refutation to answer the question "What rank does Dr. Strangelove hold?" For full credit, clearly state the vocabulary, describe how the given facts are encoded, convert them to clauses, and prove a contradiction. Also state which of the following resolution strategies would suffice for this domain:
    • Input resolution
    • Unit resolution
    • Linear resolution
    • Set-of-support resolution with negated goal as the initial set of support

    Which one does your proof use?

Return Home