CSE630 Homework 3: Propositional and Predicate Logic

Due: Thursday, Nov 1 at 04:00 a.m.
1 point late penalty for each minute late

For notational convenience, you can spell out 'ForAll' and 'Exists' if you're using a text editor that doesn't support the logic symbols. Also, you can use & for 'And'.

1. (15 points) Express the following statements in Propositional Logic:
   1. If P is false, then we know that Q is also false.
   2. Q and P are either both false or both true.
   3. Either P is true or Q is true.
   4. Both P and Q are true and M is false.
   5. John is tall and Peter has short hair. (define the proposition symbols you use).


2. (15 points) Derive the indicated statements using inference rules for propositional logic from the KB provided:
   KB:
   1. P -> (~Q & S)
   2. S -> (~Q & T)
   3. S & ~W
   4. R -> W
   5. P V R
   • derive: ~W & ~Q
   • derive: ~(Q & S)
   
   KB:
   1. ~P
   2. P -> (Q V R)
   3. T & ~Q
   4. T -> S
   • c. derive: S V R


3. (10 points) Rewrite the following statements in FOL, stating definitions for the predicates you use:
   1. Lori is a fast runner.
   2. Lions roar.
   3. There is at least one frog that lives in Buckeye Creek.


4. (5 points) Consider a KB containing just two sentences: P(a) and P(b). What would need to be true about the model for this KB to entail All x P(x)?


5. (21 points) 8.6 a,b,c,d,e,h,i from the textbook. Some of these are challenging, but do your best. Start by figuring out how many separate entities are being described, and what relationships obtain between them. You can use arithmetic operators such as greater-than or less-than as predicates.


6. (9 points) 8.8 from the book


7. (25 points) Using the following first-order logic predicates:
   
   • BREEZE(x,y) means that a breeze is sensed in square x,y
   • PIT(x,y) means that square x,y contains a pit
   • GLITTER(x,y) means that glitter is sensed in square x,y
   • GOLD(x,y) means that square x,y contains the gold
   • WUMPUS(x,y) means that square x,y contains the wumpus
   • STENCH(x,y) means that a stench is sensed in square x,y
   • ARCHER(x,y) means that the archer is in square x,y
   • hasArrow(ARCHER) means that the archer has his arrow (in other words, he hasn't shot the arrow yet).
   
   
   1. Create a KB that expresses all of the properties of entire wumpus world maze and the archer shown in Figure 7.2, and logical axioms that show the relationship between the maze properties (PIT(x,y), WUMPUS(x,y), GOLD(x,y)) and the perceptions they cause. (HINT: your KB should include at least 7 facts and 3 axioms.) You can use arithmetic operators + and - as predicates.
   2. Assume your archer has moved through the maze beginning from position (1,1) to all of the safe squares in the first 2 rows of the maze, and has inferred new KB statements expressing all the percepts and facts possible from these squares. Use these facts and the axioms you created in part (a) to prove ~PIT(2,3) using Resolution Proof by negation only (see figure 7.13 for an example) .

   Submission instructions:

   You will submit your work to be graded electronically. Submit your answers either as plain text or pdf. Please don't use any formatted text product, such as Microsoft Word, but do format your text for readability to the extent possible. Put the following header at the top of your file:

   Name
   CSE630 Assignment 3

   Put only the file or files that you want to submit in a directory on STDSUN called hw3, and use the submit command to send the files to the grader by the submission deadline. The syntax of the submit command is:

   > submit c630aa lab3 hw3

   You can learn about using the submit command by typing man submit at a unix command prompt. If you cannot get the submit command to work, you can email your files to the grader, but please don't use this option unless you're having trouble with submit.