Title | Solutions to Assignment 1 |
---|---|
Author | Junya Mo |
Course | Discrete Mathematics |
Institution | University of Queensland |
Pages | 2 |
File Size | 47.6 KB |
File Type | |
Total Downloads | 191 |
Total Views | 404 |
MATH1061 Solutions to Assignment 1 Semester 2, 2016 This Assignment was marked out of 30. You can check you mark at courses.smp.uq.edu/marks. 1. (3 marks) For an “or” statement to be false, we require both parts of the statement to be false, so p → q is false and ∼ p ∧ q is false. The only way for p...
MATH1061
Solutions to Assignment 1
Semester 2, 2016
This Assignment was marked out of 30. You can check you mark at http://courses.smp.uq.edu.au/marks. 1. (3 marks) For an “or” statement to be false, we require both parts of the statement to be false, so p → q is false and ∼ p ∧ q is false. The only way for p → q to be false is if p is true and q is false. In this case ∼ p ∧ q is indeed also false. Therefore, we can conclude that p is true and q is false. 2. (5 marks) (Note that you are not required to list the names of the laws but they are included here for your reference. Other answers are possible, and it is ok to combine some steps into one, like a combination of associative and commutative laws. ) ((∼ p ∨ q) ∧ (q ∨ r)) ∧ (p ∧ ∼ q) ≡ ≡ ≡ ≡ ≡ ≡ ≡ ≡ ≡ ≡
(∼ p ∨ q) ∧ ((q ∨ r) ∧ (p ∧ ∼ q)) (∼ p ∨ q) ∧ ((p ∧ ∼ q) ∧ (q ∨ r)) ((∼ p ∨ q) ∧ p)∧ ∼ q ∧ (q ∨ r) ((∼ p ∧ p) ∨ (q ∧ p))∧ ∼ q ∧ (q ∨ r) (c ∨ (q ∧ p))∧ ∼ q ∧ (q ∨ r) (q ∧ p)∧ ∼ q ∧ (q ∨ r) (p ∧ q)∧ ∼ q ∧ (q ∨ r) p ∧ (q∧ ∼ q) ∧ (q ∨ r) p ∧ c ∧ (q ∨ r) c
Associative law Commutative law Associative law Distributive law Negation law Identity law Commutative law Associative law Negative law Universal bound law
3. (a) (2 marks) Premise 1 Premise 2 Premise 3 Conclusion
(f ∧ q ∧ e) → p f q∨e p
(b) (5 marks) Suppose that this argument is invalid, so the conclusion is false and each of the premises is true. Since the conclusion is false we have p false. Since premise 2 is true, we have f true. Since premise 1 is true and we already know that p is false, we have that f ∧ q ∧ e is false, so at least one of q or e is false. Since premise 3 is true, we require that at least one of q or e is true. We can achieve all of this by letting p be false, f be true, q be true and e be false (or let q be false and e be true). Thus the argument is invalid. 4. (3 marks) Award marks for anything that is a valid argument form. 5. (a) (1.5 marks) ∃x ∈ Z+ such that x < 4. (b) (1.5 marks) ∀x ∈ R, x2 ≥ 0. (c) (1.5 marks) ∀m ∈ Z, if m is even, then m − 2 is even. (d) (1.5 marks) ∀x ∈ Zodd , ∃y ∈ Zeven such that x divides y .
6. (a) (3 marks) Original: ∀ a ∈ Z, ∃ b ∈ Z such that ab ≤ 1. Negation: ∃a ∈ Z such that ∀b ∈ Z, ab > 1. The original is true. For any a ∈ Z, choose b to be −a. Then ab = −a2 which is less than 1. (b) (3 marks) Original: ∃ x ∈ R such that ∀ y ∈ Z+ , x < y. Negation: ∀x ∈ R, ∃y ∈ Z+ such that x ≥ y . The original is true. Choose x = 0, then for every y ∈ Z+ we have x < y....