ITCS 6150/8150 - HW2 - Solved

Logical Agents, Propositional Logic and First Order Logic
 

1.      [5 points] Consider the following propositional language:  A =“Andy comes to the party”,  

B =“Bob comes to the party”,  C =“Cody comes to the party”, 

D =“Daniel comes to the party”.  

                Formalize the following sentences:              

a)      “If Daniel comes to the party then Bob and Cody come too”  

b)      “Daniel comes to the party if and only if Cody comes and Andy doesn’t come”  

c)       “Cody comes to the party provided that Daniel doesn’t come, but, if Daniel comes, then Bob doesn’t come”  

d)      “A necessary condition for Andy coming to the party, is that, if Bob and Cody aren’t coming, then 

Daniel comes”  

e)       “Andy, Bob and Cody come to the party if and only if Daniel doesn’t come, but, if neither Andy nor Bob come, then Daniel comes only if Cody comes”  

2.      [3 + 3 = 6 points] Convert the following sentences into conjunctive normal form (CNF). a) (AÞB)ÞC 

b) (P Þ(QÞR)) Þ (P Þ (RÞQ)) 

 

3.      [5 points] Andy, Cody, and Smith find themselves trapped in a dark and cold old building. The reason for being there is to find some treasures. After some exploration they find three doors, the first one red, the second one blue, and the third one green. Behind one of the doors is a path to $10M. Behind the other two doors, however, is an Wumpus. Opening a door to the Wumpus means almost certain death. On each door there is a message:

Red door: “$10M is behind this door”

Blue door: “$10M is not behind this door”  

Green door: “$10M is not behind the blue door”         

 

Given the fact: at least one of the three above statements on the three doors is true and at least one of them is false, which door would lead to $10M? Solve by using propositional logic.  

 

Use the following notation:

r: “$10M is behind the red door” b: “$10M is behind the blue door”  g: “$10M is behind the green door” 

 

4.      [3 + 2 = 5 points] Alan, Brianna, Cody and Daniel love scuba diving and went to Martinique. They talked to a provider and planned accordingly. Unfortunately, they arrived at the seaside little late and by then only 2 suits were available (meaning only two can go for scuba diving).  

 

Moreover, they had the following constraints.

Alan will only go if Brianna goes too.  

Daniel will only go if Cody goes too.  

Also, suddenly, Brianna had found out that she did not complete ITCS 6150 homework, so she could not go.  

 

a)      Using appropriate literals, write the propositional logic formulas corresponding to this English text. [Hints. One big formula and some other propositional sentences]

b)      Can you tell who had scuba diving experience in Martinique using propositional logic.

 

 
 5. [7 points] Use Internet to study various first order sentences. Mention at least seven natural English sentences and corresponding first order sentences that you find interesting. The sentences must be non- trivial, outside textbook, lecture slides and class practices.

 

6.      [2 + 5 = 7 points]  

a.      Mention at least two problems, other than 8-queens problem, that you think we can solve them by hill-climbing search.  

b.      Later explain how hill-climbing and/or its variants can solve one of these problems (from your list). You must demonstrate the solution formally stating different components such as problem statements, goal, constraints, heuristic function required, actions etc. with examples.  

 

7.      [5 points] State the rules to translate a FOL sentence to Canonical Normal Form (CNF). Explain this with an example.