Test 2        Name __________________        Score __

1. Convert to CNF:
   • AB                    ØA Ú B
   • ABC                (ØA Ú B Ú C) Ù (ØB Ú A)  Ù (ØC Ú A)
      
2. Given: (P_2,1B_1,1)(B_1,1P_1,2P_2,1)(P_1,2B_1,1)B_1,1
   Prove by resolution:  P_1,2

   KB P_1,2

   (P2,1B1,1)(B1,1P1,2P2,1)(P1,2B1,1)B1,1 P1,2 Resolve B1,1P1,2 with B1,1 result is P1,2 Resolve P1,2 with P1,2 result is empty clause

3. Prove Z using forward chaining:
   1. RYX
   2. SXW
   3. RSX
   4. XWY
   5. YZ
   6. R
   7. S
       

   Facts	Rule
   R, S	RSX
   R,S,X	SXW
   R,S,X,W	XWY
   R,S,X,W,Y	YZ
   R,S,X,W,Y,Z

      

4. Prove Z using backward chaining:
   1. RYX
   2. SXW
   3. RSX
   4. XWY
   5. YZ
   6. R
   7. S
       

   Facts	Goal	Rule
   R,S	Z	YZ
   R,S	Y,Z	XWY
   R,S	X,W,Y,Z	RSX
   R,S,X	W,Y,Z	SXW
   R,S,X,W	Y,Z	XWY
   R,S,X,W,Y	Z	YZ
   R,S,X,W,Y,Z

5. For the KB of:
   • Horse(Prancer).
   • Horse(Thunder).
   • Horse(Comet).
   • Horse(Dasher).
   • Fast(Thunder).
   • Fast(Prancer).
   • Parent(Dasher,Comet).
   • Parent(Prancer,Comet).
   • Parent(Thunder,Dasher).
   • "x,y Horse(x) Ù Parent(y,x) Ù Fast(y) Þ Valuable(x)

   Prove using forward or backward chaining: Valuable(z); all valuable horses.

   Forward - Prove everything possible until Horse(x) Ù Parent(y,x) Ù Fast(y) is proven

   

   Backward

   Goal: Valuable(z)

   Subgoals: Horse(x), Parent(y,x), Fast(y)

   

    

6.     For the KB:
   • "x,y Horse(x) Ù Parent(y,x) Ù Fast(y) Þ Valuable(x)
   • "w Winner(w)  Þ Fast(w)
   • Winner(Prancer)
   • Winner(Dasher)
   • Horse(Prancer).
   • Horse(Thunder).
   • Horse(Comet).
   • Horse(Dasher).
   • Fast(Thunder).
   • Fast(Prancer).
   • Parent(Dasher,Comet).
   • Parent(Prancer,Comet).
   • Parent(Thunder,Dasher).

     Prove using resolution: Valuable(Comet)

     Add ØValuable(Comet)

     • ØValuable(Comet)
     • ØHorse(x) Ú ØParent(y,x) Ú ØFast(y) Ú Valuable(x)
     • ØWinner(w) Ú Fast(w)
     • • ØHorse(x) Ú ØParent(y,x) Ú ØFast(y) Ú Valuable(x)   {y/Prancer, x/Comet}
       •                      Parent(Prancer,Comet)
       • ØHorse(Comet) Ú ØFast(Prancer) Ú Valuable(Comet) 
       •                             Fast(Prancer)
       • ØHorse(Comet) Ú Valuable(Comet) 
       •   Horse(Comet)
       •   Valuable(Comet) 
       • ØValuable(Comet)
    
7.     Convert to CNF
   • "x [$y Animal(y) Ù Kills(x,y) Þ "z ØLoves(z,x)]
     •    "x [Ø$y Animal(y) Ù Kills(x,y) Ú "z ØLoves(z,x)]

          "x ["y ØAnimal(y) Ú ØKills(x,y) Ú "z ØLoves(z,x)]

          [ØAnimal(y) Ú ØKills(x,y)] Ú  ØLoves(z,x)

        

   • "x ["y Animal(y) Ù Kills(x,y)] Þ ["z ØLoves(z,x)]
        "x [Ø"y Animal(y) Ù Kills(x,y)] Ú ["z ØLoves(z,x)]
        "x [$y ØAnimal(y) Ú ØKills(x,y)] Ú ["z ØLoves(z,x)]
        "x [ØAnimal(F(x)) Ú ØKills(x,F(x))] Ú ["z ØLoves(z,x)]
        [ØAnimal(F(x)) Ú ØKills(x,F(x))] Ú ØLoves(z,x)

    

8.     Given the following, develop a total plan using backward planning:

   • Operators
     • On( b, x) - Block b is on top of block x.
     • Clear( x ) - Block x has no block on top of it.
     • Block( b ) - b is a block
   • Actions
     • Action( Move(b, x, y),    Move block b from x to y
           Precond: On(b, x) Ù Clear(b) Ù Clear(y) Ù Block(b)
                                     Ù (b≠x) Ù (b≠y) Ù (x≠y),
           Effect:    On(b, y) Ù Clear(x) Ù ØOn(b, x) Ù ØClear(y))
        

   • Initial( On(A, Table) Ù On(B, Table) Ù On(C, Table)
                                    Ù Block(A) Ù Block(B) Ù Block(C)
                                    Ù Clear(A) Ù Clear(B) Ù Clear(C)
   • Goal( On(A, B) Ù On(B, C) Ù On(C,Table) Ù Block(C))

   ---

   Action( Move(A, Table, B)
       Precond: On(A, Table) Ù Clear(A) Ù Clear(B) Ù Block(A)  {b/A, x/Table, y/B}
       Effect:    On(A,B) Ù Clear(Table)

   Goal :         On(B, C) Ù On(C,Table) Ù Block(C)
                                  Ù On(A, Table) Ù Clear(A) Ù Clear(B) Ù Block(A)                             

   ---

   Action( Move(B, Table, C)
       Precond: On(B, Table) Ù Clear(B) Ù Clear(C) Ù Block(B)    {b/B, x/Table, y/C}
       Effect:    On(B,C) Ù Clear(Table)
   Goal :         On(A, Table) Ù On(B, Table) Ù On(C,Table)
                                       Ù Block(A) Ù Block(B) Ù Block(C)
                                       Ù Clear(A) Ù Clear(B) Ù Clear(C)

   Initial( On(A, Table) Ù On(B, Table) Ù On(C, Table)
                                  Ù Block(A) Ù Block(B) Ù Block(C)
                                  Ù Clear(A) Ù Clear(B) Ù Clear(C)

    

9.     Given the following, develop a total plan using partial order planning:

   • Operators
     • On( b, x) - Block b is on top of block x.
     • Clear( x ) - Block x has no block on top of it.
     • Block( b ) - b is a block
   • Actions
     • Action( Move(b, x, y),    Move block b from x to y
           Precond: On(b, x) Ù Clear(b) Ù Clear(y) Ù Block(b)
                                     Ù (b≠x) Ù (b≠y) Ù (x≠y),
           Effect:    On(b, y) Ù Clear(x) Ù ØOn(b, x) Ù ØClear(y))

   • Graphical representation of Move(b,x,y)

     Action( Move(b, x, y),
         Preconditions: On(b, x) Ù Clear(b) Ù Clear(y)
         Effect:            On(b, y) Ù Clear(x) )

   • Operators:

     • finish
       • Preconditions: the overall goal
         
                  On(A,B) Ù On(B,C) Ù On(C, Table) Ù Clear(A)
          
       • Effect: Nothing
     • initial
       • Preconditions: True
       • Effects: All literals in initial state.

         On(A, Table) Ù On(B, Table) Ù On(C, A)
                            Ù Clear(B) Ù Clear(C) Ù Clear(Table)

   • Graphical representation of finish and initial operators in an unfinished plan.