CS 343 Artificial Intelligence
Homework 2: Logic and Deduction


Due: March 1, 2007
  1. Represent the following in first-order logic (adapted from Russell & Norvig (first edition), Exercise 7.2 - you don't need to look it up). Make sure to use a reasonable set of primitive predicates that capture the basic concepts, not ones like FAILED-BOTH, BEST-SCORE, or VEGETARIAN.
    1. Only one student failed both History and Biology.
    2. The best score in History was better than the best score in Biology.
    3. There is a woman who likes all men who don't eat meat.
    4. Politicians can fool some of the people all of the time, and all of the people some of the time, but they can't fool all of the people all of the time.

  2. Consider the following definite Horn-clause KB:
    Notation: A: for all, E: exists, &: and, =>: implication, <=>: biconditional, ~: not

    Axy Guilty(x) & Associated(x,y) -> Guilty(y)
    Associated(Adam,Betty), Associated(Carl,David), Associated(Eddie,Adam), Associated(Eddie,David), Guilty(Eddie)

    Assume we perform forward-chaining on this KB and show the specific instantiations of all rules triggered and conclusions added in their exact order. Assume rules and facts are matched in the exact order given above and that new added facts are immediately added to the end of the list. Make sure you include all rule firings by considering all possible combinations of ways in which facts can match rule antecedents.

  3. Consider the following Horn clauses in first-order logic. 
    AxAy [Candidate(x, Governator) & Candidate(y, Governator) & x!=y => Debate(x,y)]
AwAz [OutGuns(w,z) & Debate(w,z) => WinDebate(w)]
ApAqAsAt [CatchPhraseRepertoire(p,s) & CatchPhraseRepertoire(q,t) & s > t => OutGuns(p,q)]

Candidate(Arnold, Governator)
Candidate(T1000, Governator)
CatchPhraseRepertoire(Arnold, 57)
CatchPhraseReportoire(T1000, 0)
    Assume backward-chaining rule-based inference is used to try to answer the query: WinDebate(u). Show the trace of the search conducted and the subgoals generated like that shown on page 16 of the lecture notes on "Inference in First Order Logic" and show the final answer retrieved. Assume that the predicates "!=" (not equal) and ">" (numerically greater than), are evaluated procedurally (i.e. handled externally by normal program functions that return the correct truth value).

  4. Given the following representation of "There is a barber in town who shaves all and only men in town who do not shave themselves" (if all barbers are men)

    Ex (Barber(x) & In(x,Town) & Ay [(Man(y) & In(y,Town) & ~Shave(y,y)) <=> Shave(x,y)])
    Ax (Barber(x) => Man(x))

    Show this statement is contradictory (usatisfiable) using resolution.