Discrete Mathematics and Its Applications PDF

Discrete Mathematics and Its Applications Section 2 Ch1: The Foundations: Logic and Proofs 1/48 Section 1.2 solution 2/48 Section 1.2 solution 2/48 Section 1.2 43. Construct a combinatorial circuit using inverters, OR gates, and...

Discrete Mathematics and Its Applications Section 2 Ch1: The Foundations: Logic and Proofs 1/48 Section 1.2 solution 2/48 Section 1.2 solution 2/48 Section 1.2 43. Construct a combinatorial circuit using inverters, OR gates, and AND gates that produces the output ((￢p ∨￢r)∧￢q) ∨ (￢p ∧ (q ∨ r)) from input bits p,q, and r. solution 2/48 Section 1.2 Question 42 (ass) 42- Construct a combinatorial circuit using inverters, OR gates, and AND gates that produces the output (p ∧ ¬r) ∨ (¬q ∧ r) from input bits p, q, and r. 2/48 Section 1.3 Tautology Contradiction Contingency Logically equivalent 2/48 Section 1.3 9. Show that each of these conditional statements is a tautology by using truth tables. a) (p ∧ q) → p b) p → (p ∨ q) Solution 2/48 Section 1.3 c) ￢p → (p → q) d) (p ∧ q) → (p → q) Solution 2/48 Section 1.3 e) ￢(p → q) → p f ) ￢(p → q)→￢q (ass) 2/48 Propositional Equivalences Some important equivalences. Equivalence Name Equivalence Name pT  p Identity laws (p  q)  r  p  (q  r ) Associative pF  p laws (p  q)  r  p  (q  r) pT  T Domination laws pF F p  (q  r)  (p  q)  ( p  r) Distributive laws pp  p p  (q  r)  (p  q)  ( p  r) pp  p (p  q)  p  q De Morgan’s (p)  p Double negation (p  q)  p  q laws law pq  qp Commutative laws p  p  T pq  qp p  p  F (p → q)  (p  q) 29/52 Section 1.3 11. Show that each conditional statement is a tautology without using truth tables. a) (p ∧ q) → p Solution (p ∧ q) → p Note: (p → q) ≡ ￢p ∨ q ￢(p ∧ q) ∨ p (￢ p ∨ ￢ q) ∨ p ￢p∨￢q∨p (￢ p ∨ p )∨ ￢ q T ∨￢q≡T 2/48 Section 1.3 b) p → (p ∨ q) Solution p → (p ∨ q) ￢ p ∨ (p∨ q) ￢p∨p∨q (￢ p ∨ p )∨ q T ∨q≡T 2/48 Section 1.3 c) ￢p → (p → q) d) (p ∧ q) → (p → q) (ass) e) ￢(p → q) → p f ) ￢(p → q)→￢q (ass) 2/48 Section 1.3 23. Show that (p → r) ∧ (q → r) and (p ∨ q) → r are logically equivalent. Solution (p → r) ∧ (q → r) Note: (p → q) ≡ ￢p ∨ q (￢p ∨ r ) ∧ (￢q ∨ r ) (￢p ∧ ￢q ) ∨ r ￢(p ∨ q ) ∨ r (p ∨ q) → r ## 2/48 Section 1.3 29. Show that (p → q) ∧ (q → r) → (p → r) is a tautology. Solution (￢ q ∨ ￢ p ) ∨ (q ∨ r) (p → q) ∧ (q → r)→ (p → r) [(p → q) ∧ (q → r) ]→ (p → r) ￢q∨￢p∨q∨r ￢[(p → q) ∧ (q → r)] ∨ (p → r) (￢ q ∨ q ) ∨ (￢ p ∨ r) ￢[(￢ p ∨ q) ∧ (￢ q ∨ r)] ∨ (￢ p ∨ r) T ∨ (￢ p ∨ r) =T ## [￢(￢ p ∨ q) ∨ ￢(￢ q ∨ r)] ∨ (￢ p ∨ r) [ (p ∧ ￢ q) ∨ (q ∧ ￢ r)] ∨ (￢ p ∨ r) (p ∧ ￢ q) ∨ (q ∧ ￢ r) ∨ ￢ p ∨ r (p ∧ ￢ q) ∨ ￢ p ∨ (q ∧ ￢ r) ∨ r (p ∨ ￢ p) ∧ (￢ q ∨ ￢ p ) ∨ (q ∨ r) ∧ (￢ r ∨ r) T ∧ (￢ q ∨ ￢ p ) ∨ (q ∨ r) ∧T 2/48 Section 1.4 Quantifiers 1. Let P(x) denote the statement “x ≤ 4.” What are these truth values? P(0) P(4) P(6) Solution 2/48 Section 1.4 5. Let P(x) be the statement “x spends more than five hours every weekday in class,” where the domain for x consists of all students. Express each of these quantifications in English. a) ∃xP(x) b) ∀xP(x) c) ∃x ￢P(x) d) ∀x ￢P(x) Solution a) There is a student who spends more than five hours every weekday in class. b) Every student spends more than five hours every weekday in class. c) There is a student who does not spend more than five hours every weekday in class. d) No student spends more than five hours every weekday in class. (Or, equivalently, every student spends less than or equal to five hours every weekday in class.) 2/48 Section 1.4 9. Let P(x) be the statement “x can speak Russian” and let Q(x) be the statement “x knows the computer language C++.” Express each of these sentences in terms of P(x), Q(x), quantifiers, and logical connectives. The domain for quantifiers consists of all students at your school. a) There is a student at your school who can speak Russian and who knows C++. b) There is a student at your school who can speak Russian but who doesn’t know C++. c) Every student at your school either can speak Russian or knows C++. d) No student at your school can speak Russian or knows C++. Solution 2/48 Section 1.4 11. Let P(x) be the statement “𝑥 = 𝑥 2.” If the domain consists of the integers, what are these truth values? a) P(0) b) P(1) c) P(2) d) P(−1) e) ∃xP(x) f) ∀xP(x) Solution a) T, since 0 = 02 b) T, since 1 = 12 c) F, since 2 != 22 d) F, since -1 != −12 e) T (let x = 1) f) F (let x = 2 ) 2/48 Section 1.4 13. Determine the truth value of each of these statements if the domain consists of all integers. a) ∀n(n + 1 > n) b) ∃n(2n = 3n) c) ∃n(n = −n) d) ∀n(3n ≤ 4n) Solution a) Since adding 1 to a number makes it larger, this is true. b) Since 2 · 0 = 3 · 0, this is true. c) This statement is true, since 0 = -0. d) This is true for the nonnegative integers but not for the negative integers. For example, 3(-2) ~= 4(-2).Therefore the universally quantified statement is false. 2/48 Thank you