CS 343 Artificial Intelligence
Homework 2: Logic and Deduction

Due: Mar 5, 2009

ASCII Logic Notation:
A       for all 
E       exists
&       and
|       or
=>      implication
<=>     biconditional
~       not

All these type of parentheses are logically equivalent: "()","[]","{}".  
Capitalized arguments to predicates are constants; lowercase arguments are variables.
  1. Represent the following in first-order logic Make sure to use a reasonable set of primitive predicates that capture only the most basic concepts in the satements.
    1. Every Batman film with a different director also has a different actor playing Batman.
    2. Every university has a professor who started an Internet company that employs a student of the university who got stock options in the company.
    3. Any politician 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.
    4. Texas is the state with the second highest population.

  2. Consider the following definite Horn-clause KB for some family relationships.

    1) AxAyAz Parent(x,y) & Parent(x,z) & y!=z => Sibling(y,z)
    2) AxAyAwAz Parent(x,w) & Parent (y,z) & Sibling(x,y) => Cousin(w,z)
    Parent(Bob,Tom), Parent(Bob,Mary), Parent(Tom,Fred), Parent(Tom,Alice), Parent(Mary,John)

    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. Assume that the operator "!=" (not equal) is evaluated procedurally (i.e. handled externally by a special program that returns the correct truth value). 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 [Start(x,y) & Unpopular(y) => Unpopular(x)]
    AzAe [Unpopular(z) & Candidate(z,e) => Lose(z,e)]
    AsAuAw [Candidate(u,s) & Candidate(w,s) & w!=u & Lose(u,s) => Win(w,s)]
    Candidate(Barack, Election08)
    Candidate(George, Election08)
    Start(George, IraqWar)
    Assume backward-chaining rule-based inference is used to try to answer the query: Win(v,Election08). 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 operator "!=" (not equal) is evaluated procedurally (i.e. handled externally by a special program that returns the correct truth value).

  4. A popular children's riddle is "Brothers and sisters I have none, but that man's father is my father's son." Encode these facts in first-order logic and use resolution to prove that I am that man's father. Assume sibling is defined as:

    AfAxAy Father(f,x) & Father(f,y) & ~(x=y) => Sibling(x,y)

    and that "Brothers and sisters I have none" is is interpreted as "I have no siblings." Let F be the Skolem constant introduced to represent "that man's father" and M be the constant representing "me," and prove that F=M. You will also need to define a couple of simple extra axioms about the predicates Father and Son for use in the proof. See last year's solution for a sample of a compact way to show a resolution proof.