CPSC 5627E - ASSIGNMENT 1 DUE DATE: September 26, 2016 1 1. Necessary Conditions and Sufficient Conditions Definition of "Sufficient condition" Definition: A condition A is said to be sufficient for a condition B, if (and only if) the truth (/existence /occurrence) of A guarantees (or brings about) the truth (/existence /occurrence) of B. Definition of "Necessary condition" Definition: A condition A is said to be necessary for a condition B, if (and only if) the falsity (/nonexistence /non-occurrence) of A guarantees (or brings about) the falsity (/nonexistence /non-occurrence) of B. See also definitions of necessity expressed in terms of possible worlds (p.31 of Possible Worlds book). Then, for each of the following, say whether it is true or false. 1. x's being a square is a sufficient condition for x's being a rectangle. 2. x's being a mother is a necessary condition for x's being a female. 3. x's being greater than 15 is a sufficient condition for x's being less than 20. 4. x's being less than 20 is a necessary condition for x's being less than 12. 5. x's having two arms is a sufficient condition for x's being a human being. 6. x's having two arms is a necessary condition for x's being a human being. 7. x's wanting to do a is a sufficient condition for x's doing a. 8. x's wanting to do a is a necessary condition for x's doing a.CPSC 5627E - ASSIGNMENT 1 DUE DATE: September 26, 2016 2 2. Propositional Logic Construct a proof of validity to show that the conclusion follows from the set of premises using the rules of inference found at http://19.org/blog/19rules/. Marks will be awarded based on shortness of your proof. 1.) 1.) (PQ) ^ (RS) premise 2.) (QT) ^ (SU) premise 3.) (~PT) ^ (~QS) premise 4.) ~T premise ------------------------- .: ~R v ~Q 2.) 1.) (B v C)  (D v E) premise 2.) [(D v E) v F)]  (G v H) premise 3.) (G v H)  ~D premise 4.) E  ~G premise 5.) B premise ---------------------------------- .: H Number the steps of each proof and state the rule of inference and previous steps that you used to arrive at each step. An example of a proof of validity in the required format can be found at http://www.philosophypages.com/lg/e11a.htm. 3. Predicate (1st Order) Logic Validity in first-order logic, like in prepositional logic, requires truth in all possible worlds. Which of the following statements are valid? Explain your answers. (This is exercise 8.6 in the chapter on First Order Logic from "Artificial Intelligence" by Russell and Norvig.) a. (∃x x=x) ⇒ (∀ y ∃z y =z). b. ∀ x P(x) ∨ ￢P(x). c. ∀ x Smart (x) ∨ (x=x).CPSC 5627E - ASSIGNMENT 1 DUE DATE: September 26, 2016 3 4. Predicate (1st Order) Logic (continued) (a.) (i) Translate this sentence into first order predicate logic: "An elephant is happy if all its children can fly" Use these predicates: happy(x) is read as "x is happy" fly(x) is read as "x can fly" child(x,y) is read as "x is a child of y" elephant(x) is read as "x is an elephant" (ii) Translate this sentence into first order predicate logic: "The rainfall in every Latin American country is at least 17cm a year" Invent your own predicates for this sentence, and explain how they are to be read. (iii) Identify the predicate names and the predicate arities, the constants, the quantifiers, the variables and the connectives in your translated sentence for part (ii). (iv) Translate the following sentences into first-order logic, using a function to represent mother:  All dogs are mammals  Fido is a dog  Fido's mother is a mammal  All mammals have a mother who is a mammal (v) Retranslate the sentences of part (iv) into first-order logic without using functions. (vi) Write your answers to part (iv) as Horn clauses, if possible. Recommended Readings: http://ccg.doc.gold.ac.uk/teaching/artificial_intelligence/lecture6.html http://ccg.doc.gold.ac.uk/teaching/artificial_intelligence/lecture7.html