Exercise 7        Name __________________        Score __/12

  1. Consider a knowledge base KB containing just two sentences, P(a) and P(b). Does KB entail "x P(x)? Explain your answer in terms of models. Recall that KB may be true for a subset of the model's domain.

    KB does not entail "x P(x). To show must have model where P(a) and P(b) but "x P(x) is false. Consider a model with three domain elements, a, b, c where P(a) and P(b) holds but P(c) does not.
     

  2. Represent the following sentences in FOL using the following vocabulary:
    1. Takes(x,c,s): student x takes course c in semester s;
    2. Passes(x,c,s): student x passes course c in semester s;
    3. Score(x,c,s): the score obtained by student x in course c in semester s;
    4. x>y; x is greater than y;
    5. F and G; specific French and Greek courses;
    6. Buys(x,y,z): x buys y from z;
    7. Sells(x,y,z): x sells y to z;
    8. Shaves(x,y): person x shaves person y;
    9. Born(x,c): persons x is born in country c;
    10. Parent(x,y): x is a parent of y;
    11. Citizen(x,c): x is a citizen of country c;
    12. Resident(x,c,): x is a resident of country c;
    13. Fools(x,y,t): person x fools person y at time t;
    14. Student(x), Person(x), Man(x), Expensive(x), Agent(x), Insured(x), Smart(x), Politician(x): predicates satisified by members of the corresponding categories.

     

    1. Some students took French in spring 2004.   
          $x Student(x) Ù Takes(x,F,Spring2004)
    2. Every student who takes French passes it.
          "s,x Student(x) Ù Takes(x,F,s) Þ Passes(x,F,s)
    3. Only one student took Greek in spring 2004.
          $x Student(x) Ù Takes(x,G,Spring2004) Ù "y y≠x Þ ØTakes(y,G,Spring2004)
    4. The best score in Greek is always higher than the best score in French.
          "s $x "y Score(x,G,s) > Score(y,F,s)
    5. Every person who buys a policy is smart.
          "x Person(x) Ù [ $y, z Policy(y) Ù Buys(x,y,z)] Þ Smart(x)
    6. No person buys an expensive policy.
          "x, y, z Person(x) Ù  Policy(y) Ù Expensive(y) Þ ØBuys(x,y,z)
    7. There is an agent who sells policies only to people who are not insured.
          $x Agent(x) Ù "y, z Sells(x,y,z) Ù Policy(y) Þ (Person(z) Ù ØInsured(z))   
    8. There is a barber who shaves all men in town who do not shave themselves.
          $x Barber(x) Ù "y ØShaves(y,y) Ù Man(y) Þ Shaves(x,y)
    9. A person born in the US, each of whose parents is a US citizen or a US resident, is a US citizen by birth.
          "x Person(x) Ù Born(x,US) Ù "y Parent(x,y) Þ Citizen(y,US) Ú Resident(y,US) Þ Citizen(x, US)
    10. A person born outside the US, one of whose parents is a US citizen by birth, is a US citizen.
          "x Person(x) Ù ØBorn(x,US) Ù ($y Parent(x,y) Ù Citizen(y,US)) Þ Citizen(x, US)
    11. Politicians can fool some of the people all the time and they can fool all of the people some of the time but they can't fool all the people all the time.
          "x Politician(x) Þ ($y"t  Person(y) Þ Fools(x,y,t)) Ù
                                    ($t"y  Person(y) Þ Fools(x,y,t))  Ù
                                 Ø ("t"y  Person(y) Þ Fools(x,y,t))
  3. Give FOL for:
    1. The wumpus is not at a pit.

      "s At(s,wumpus) Þ ØAt(s, pit)
       
    2. There is only one wumpus.

      $s1 At(s1, wumpus)  Ù "s2 Ø(s1=s2) Þ ØAt(s2,wumpus)
       
    3. The rule that a wumpus in at a square implies that at adjacent squares there is a stench:
      • "s At(s, wumpus) Þ  $r At(r, stench) Ù Adjacent(r,s)

      Give the rule that a stench implies that at adjacent squares there is a wumpus.
       

      • "s At(s, stench) Þ  $r At(r, wumpus) Ù Adjacent(r,s)
  4.      
    1. What combination of inputs would cause the output of A1 to be 1?
      $i1, i2 Signal(In(1,C1))=i1   Signal(In(2,C1))=i2   Signal(Out(1,A1))=1

          {i1/1, i2/1}
       

    2. What combination of inputs would cause the output of A2 to be 1?
      $i1, i2, i3 Signal(In(1,C1))=i1 Signal(In(2,C1))=i2 Signal(In(3,C1))=i3   Signal(Out(1,A2))=1
         
          {i1/1, i2/0, i3/1} {i1/0, i2/1, i3/1}