Assignment 5 Solution

Questions




This will be a non-coding homework. Please upload a digital copy of your solution on Grade Scope. Submitted les should be in PDF. You may also submit a scanned PDF of a handwritten solution, but please ensure that the scanned le is clearly legible.




Consider the following sentences and decide for each whether it is valid, unsatis able, or neither:



Smoke ) Smoke



Smoke ) Fire



Smoke _ Fire _ :Fire



(Smoke ) Fire) ) (:Smoke ) :Fire)



(Smoke ) Fire) ) ((Smoke _ Heat) ) Fire)



((Smoke ^ Heat) ) Fire) , ((Smoke ) Fire) _ (Heat ) Fire))



Justify your answer using truth tables (worlds).




For each pair of atomic sentences, give the most general uni er if it exists:



P(A, B, B), P(x, y, z).



Q(y, G(A, B)), Q(G(x, x), y).



Older(Father(y), y), Older(Father(x), John).



Knows(Father(y),y), Knows(x,x).



Consider the following sentences:



John likes all kinds of food. Apples are food.




Chicken is food.




Anything anyone eats and isn’t killed by is food. If you are killed by something, you are not alive. Bill eats peanuts and is still alive. *




Sue eats everything Bill eats.




For rst-order syntax, feel free to use the following text le notation: | (for disjunction), & (for con-junction), - (for negation), = (for implication), <= (for equivalence), E (for existential quanti cation, e.g., E x, y, Loves(x, y)), and A (for universal quanti cation, e.g., A x, y, Loves(x, y)).




Translate these sentences into formulas in rst-order logic.



Convert the formulas of part (a) into CNF (also called clausal form).






1



Prove that John likes peanuts using resolution.



Use resolution to answer the question, \What food does Sue eat?"



Use resolution to answer the question, \What food does Sue eat?" if, instead of the axiom marked with an asterisk above, we had:



If you don’t eat, you die.




If you die, you are not alive. Bill is alive.




Consider the following:



If the unicorn is mythical, then it is immortal, but if it is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a mammal, then it is horned. The unicorn is magical if it is horned.




Represent the above information using a propositional logic knowledge base (set of sentences in propositional logic).



Convert the knowledge base into CNF



Can you use the knowledge base to prove that the unicorn is mythical? How about magical? Horned?



Justify your answers using resolution by providing corresponding resolution derivations. Make sure to clearly de ne all propositional symbols (variables) rst, then de ne your knowledge base, and nally give your derivations.




Prove each of the following assertions:



is valid if and only if T rue j= .



For any , F alse j= .



j= if and only if the sentence ( ) ) is valid.



j= if and only if the sentence ^ : is unsatis able.



Submission




Submit all solution les on Grade Scope.




Submit your solution in a le named hw5.pdf.




By submitting this homework, you agree to the following honor code.




You are encouraged to work on your own in this class. If you get stuck, you may discuss the problem with up to two other students, PROVIDED THAT YOU SUBMIT THEIR NAMES ALONG WITH YOUR ASSIGNMENT. ALL SOLUTIONS MUST BE WRITTEN UP INDE-PENDENTLY, HOWEVER. This means that you should never see another student’s solution before submitting your own. You may always discuss any problem with me or the TAs. YOU MAY NOT USE OLD SOLUTION SETS UNDER ANY CIRCUMSTANCES. Making your solu-tions available to other students, EVEN INADVERTENTLY (e.g., by keeping backups on github), is aiding academic fraud, and will be treated as a violation of this honor code.




You are expected to subscribe to the highest standards of academic honesty. This means that every idea that is not your own must be explicitly credited to its author. Failure to do this constitutes plagiarism. Plagiarism includes using ideas, code, data, text, or analyses from any other students or







2






individuals, or any sources other than the course notes, without crediting these sources by name. Any verbatim text that comes from another source must appear in quotes with the reference or citation immediately following. Academic dishonesty will not be tolerated in this class. Any student suspected of academic dishonesty will be reported to the Dean of Students. A typical penalty for a rst plagiarism o ense is suspension for one quarter. A second o ense usually results in dismissal from the University of California.









































































































































































3