Coen231h1 - Homework 1 PDF

Preview

Summary

Homework 1...

Description

Concordia University COEN231: Introduction to Discrete Mathematics Winter 2020-2021 Homework 1 Due date: February 03

1. a) Show in two different ways that the following compound propositions are logically equivalent: ¬p Ú (r ® ¬q) and ¬p Ú ¬r Ú ¬q b) Determine whether (p ® ¬q) Ù (p ® ¬r) and p ® ¬ (q Ù r) are logically equivalent or not. c) Determine whether this compound proposition is a Tautology or not: ((p Ú q) Ù ¬p) ® q d) Determine whether this compound proposition is a Tautology or not: (p ∧ q) ∨ (¬p ∨ (p ∧ ¬q)) e) Determine whether these two compound propositions are logically equivalent: (¬q Ù (p ® q))® ¬p and (q Ù (p ® ¬q)) ® ¬p 2. a) Give the converse, contrapositive, and the inverse of the following statement: “I will drive to work today unless it does not rain.” b) Negate the above statement. c) Find the inverse of the statement: “Knowing the rules and being not over confident is necessary for winning the game” d) Find the negation of: “I will go skiing tomorrow if it snows today.” 3. Are these two statements equivalent? Justify your answer. “If n is divisible by 15 then n is divisible by 3 and by 5.” “If n is not divisible by 15 then n is not divisible by 3 or not divisible by 5.” 4. Determine whether each of these compound propositions is satisfiable: - (p Ú q Ú ¬r) Ù(p Ú ¬q Ú ¬s) Ù(p Ú ¬r Ú ¬s) Ù(¬p Ú ¬q Ú ¬s) Ù(p Ú q Ú ¬s) - (¬p Ú ¬q Ú r) Ù(¬p Ú q Ú ¬s) Ù(p Ú ¬q Ú ¬s) Ù(¬p Ú ¬r Ú ¬s) Ù(p Ú q Ú ¬r) Ù(p Ú ¬r Ú ¬s) 5. Let p and q be the propositions p: The election is decided. q: The votes have been counted. Express each of these propositions as an English sentence: - ¬p - p®q - p ® ¬q - ¬p Ú (p Ù q) - ¬q ∨ (¬p∧ q)

6. Let P(x) and R(x) be two propositional functions. Determine whether the following are equivalent or not: $x (R(x) ® P(x)) and "x R(x) ® $x P(x) 7. Let P(x): “x3 > 3”, Q(x): “x2 = 9”, and R(x): “2x + 10 = 0” be three predicates on the domain of Z, the set of integers. Find the truth values of each statement below: - $x(P(2) Ú R(2)); - "x(R(x) ® P(x)); - $x(P(x) Ù Q(x)); - "x(P(x) ® ¬Q(x)); 8. Determine the truth value of each of the following statements if the domain of each variable consists of all real numbers: - $x (x2 = 2) - "x (x2 +1 ≥ 2) - "x (x2 +2 ≥ 1) 9. Let R(x) be the statement “Student x knows Russian" and C(x) be the statement “Student x knows C++". The domain is all students. Express the following statement using quantifiers: - Someone knows both Russian and C++. - Everyone knows either Russian or C++. - No one knows Russian but everyone knows C++. - Anyone who knows Russian knows C++. - Someone knows Russian if and only if someone else knows C++. 10. Let P(x,y) be a predicate where the universe of discourse of the variables is {1,2,3}. Suppose P(1,3), P(2,1), P(2,2), P(2,3), P(3,1), P(3,2) are true, and P(x,y) is false otherwise. What is the truth value of the following: - "x"y (x ¹ y ® ( P(x, y) Ú P(y, x) ) ) - "y$x (x £ y Ù P(x,y)) 11. Determine the truth value of each of the following statements if the domain of all variables consists of all real numbers: - "x $y (x2 = y) - $x "y (xy = 0) - "x (x ≠ 0 ® $y (xy = 1)) - "x $y (x + y = 1) 12. a) Express this statement using quantifiers: “Every student in this class has taken some course in every department in the school of mathematical sciences” b) Let T(x, y): “student x is taking course y." where the domains of x and y are all students and all courses, respectively. Express the following statement using quantifiers: - Some course is being taken by all students; - No course is being taken by all students;...