Q1-CS205M-21.pdf

August 26, 2021 Quiz #1 CS205M Answer the questions in blank sheets, in the order they appear in the question paper, and convert to pdf (merge all the sheets in one pdf ) and then upload. File name should be RollNo-Q1.pdf. For example,...

August 26, 2021 Quiz #1 CS205M Answer the questions in blank sheets, in the order they appear in the question paper, and convert to pdf (merge all the sheets in one pdf ) and then upload. File name should be RollNo-Q1.pdf. For example, if your roll no. is 200109009, then the file name should be 200109009-Q1.pdf. You should use at most three pages to answer the questions. Write your name and roll no. at the top of every page. There will be penalty for any kind of collaboration. No of Questions: 8 Maximum Marks: 40 Maximum Time: 40 Min. 1. 2Marks Which of the following are well-formed propositional formulas? a) ¬(p → (q ∧ p)) b) p → (q ∨ p¬r) c) (p ∧ q) ∨ (q → r) 2. 2Marks If p → q is false, what is the truth value of (¬p ∧ q) ↔ (p ∨ q) ? 3. 6Marks Amit, Bimal and Chandra are three students that took the CS205M exam. Let’s consider the following propositions. A = Amit passed the exam, B = Bimal passed the exam, C = Chandra passed the exam Formalize the following sentences. a) Only one among Amit, Bimal and Chandra passed the exam. b) Exactly two among Amit, Bimal and Chandra passed the exam. 4. 6Marks Give a formal proof of the following. (p ∧ (p → q) ∧ (s ∨ r) ∧ (r → ¬q)) → (s ∨ t) 5. 3Marks Let p(x, y) be a predicate and let the variables x and y vary over the set D = {0, 1}. Represent the proposition (p(0, 0)∨p(0, 1))∧(p(1, 0)∨p(1, 1)) by a quantified expression. 6. 3Marks Find free variables, if any, in each of the following wffs. a) ∀x(p(x) → ∃y¬q(f (x), y, f (y))) b) ∀x(∃y p(x, f (y)) → q(x, y)) c) ∀x∃y p(x, f (y)) → q(x, y) 7. 8Marks Write in English the meaning of each of the following wffs. [Note that bought(x, y) means x bought y] a) ∀x∃y bought(x, y) b) ∃x∀y bought(x, y) c) ∀x(bought(Amit, x) → bought(P riya, x)) d) ∀x bought(Amit, x) → ∀x bought(P riya, x) 8. 10Marks Transform the following informal argument into a formalized wff and then give a formal proof of the wff. [Use the predicates - D(x) : x is a dog, L(x) : x likes people, H(x) : x hates cats. Assume, a = Rover] Every dog either likes people or hates cats. Rover is a dog. Rover loves cats. Therefore, some dog likes people.