Discrete math #3 - Questions and Answers

Question 1 Discrete Mathematics a) Write the proposition for the following English sentence: If Benjamin has cough, fever, and no smell, Benjamin is COVID19 positive. b) Write inverse, converse, and contrapositive of English sentence in (A). Let 𝑝 p and 𝑞 q be the propositions "The election is decided" and "The votes have been counted," respectively. Express each of these compound propositions as English sentences. c) Proof using laws of logic ( 𝑝 ∧ 𝑞 ) → 𝑝 (p∧q)→p is tautology. 𝑝 ∧ 𝑞 ↔ ¬ 𝑝 ∨ ¬ 𝑞 p∧q↔¬p∨¬q Answer Step 1 For part a) The objective here is to write the proposition for the given statement. (A) If Benjamin has cough, fever, and no smell, Benjamin is COVID19 positive. Step 2 Consider: 𝑃 P represents that Benjamin has cough, 𝑄 Q represents that Benjamin has fever, 𝑅 R represents that Benjamin has no smell, and 𝑆 S represents that Benjamin has COVID19. Then the given statement can be represented as a proposition as: ( 𝑃 ∧ 𝑄 ∧ 𝑅 ) → 𝑆 (P∧Q∧R)→S Step 3 (B) To write inverse, converse and contrapositive of the statement in part A. Step 4 Inverse: Note that inverse of a statement "if 𝑝 p, then 𝑞 q" is "if not 𝑝 p, then not 𝑞 q". Inverse of statement in 𝐴 A: ¬ ( 𝑃 ∧ 𝑄 ∧ 𝑅 ) → ¬ 𝑆 ¬(P∧Q∧R)→¬S That means the inverse of statement in 𝐴 A: "If Benjamin has no cough, no fever, and can smell, Benjamin is not COVID19 positive." Step 5 Converse: Note that converse of a statement "if 𝑝 p, then 𝑞 q" is "if 𝑞 q, then 𝑝 p". Converse of statement in 𝐴 A: 𝑆 → ( 𝑃 ∧ 𝑄 ∧ 𝑅 ) S→(P∧Q∧R) That means the converse of statement in 𝐴 A: "If Benjamin is COVID19 positive, Benjamin has cough, fever, and no smell." Step 6 Contrapositive: Contrapositive of statement "if 𝑝 p, then 𝑞 q" is "if not 𝑞 q, then not 𝑝 p". Contrapositive of statement in 𝐴 A: ¬ 𝑆 → ¬ ( 𝑃 ∧ 𝑄 ∧ 𝑅 ) ¬S→¬(P∧Q∧R) That means the contrapositive of statement in 𝐴 A: "If Benjamin is not COVID19 positive, Benjamin has no cough, fever, and can smell." Question 2 What is the remainder ( 𝑟 r) when − 43 −43 divided by 12? a) None of the Option b) − 5 −5 c) 5 5 d) 7 7 Consider the recursively defined function: 𝑓 ( 0 ) = 2 , 𝑓 ( 𝑛 ) = 2 𝑓 ( 𝑛 − 1 ) + 5 f(0)=2,f(n)=2f(n−1)+5 where 𝑛 n is an integer greater than 0 0. The function value at 𝑛 = 2 n=2, i.e., 𝑓 ( 2 ) = ? f(2)=? a) − 23 −23 b) 23 23 c) 7 7 d) − 7 −7 Answer Step 1 We can write: − 43 = 12 ( − 4 ) + 5 −43=12(−4)+5 So, the remainder is 5 5. Step 2 For the recursive function: 𝑓 ( 1 ) = 2 𝑓 ( 0 ) + 5 f(1)=2f(0)+5 = 2 ( 2 ) + 5 = 9 =2(2)+5=9 𝑓 ( 2 ) = 2 𝑓 ( 1 ) + 5 f(2)=2f(1)+5 = 2 ( 9 ) + 5 = 18 + 5 = 23 =2(9)+5=18+5=23 Answer: 𝑏 b. Question 3 Let 𝐴 2 A 2 ​ be the set of all multiples of 2 except for 2. Let 𝐴 3 A 3 ​ be the set of all multiples of 3 except for 3. And so on, so that 𝐴 𝑛 A n ​ is the set of all multiples of 𝑛 n except for 𝑛 n, for any 𝑛 ≥ 2 n≥2. Describe (in words) the set 𝐴 2 ∪ 𝐴 3 ∪ 𝐴 4 … A 2 ​ ∪A 3 ​ ∪A 4 ​ … Answer: Similarly, 𝐴 𝑛 A n ​ is defined such that it is the set of all multiples of 𝑛 n except for 𝑛 n. Now consider a composite number 𝑚 m. Then 𝑚 = 𝑎 𝑏 m=ab with ( 𝑎 , 𝑏 ) = 1 (a,b)=1. The number 𝑚 m belongs to the set 𝐴 𝑎 A a ​ and 𝐴 𝑏 A b ​ . Hence 𝑚 m belongs to the set 𝐴 2 ∪ 𝐴 3 ∪ 𝐴 4 … A 2 ​ ∪A 3 ​ ∪A 4 ​ …. On the other hand, consider a prime number 𝑝 p. It cannot be written as a multiple of any element other than 𝑝 p and 1. By definition of the set 𝐴 𝑝 A p ​ , 𝑝 p does not belong to 𝐴 𝑝 A p ​ . Thus, the set of all odd primes will constitute the set 𝐴 1 ∪ 𝐴 2 ∪ 𝐴 3 ∪ 𝐴 4 … A 1 ​ ∪A 2 ​ ∪A 3 ​ ∪A 4 ​ …. Question 4 A class with 𝑛 n kids lines up for recess. The order in which the kids line up is random with each ordering being likely. There are two kids in the class named Betty and Mary. What is the probability that Betty is first in line or Mary is last in line? Answer: Step 1 Define 𝑀 M and 𝐵 B such that Betty being first in line is the event 𝐵 B. The likelihood of event 𝐵 B: 𝑃 ( 𝐵 ) = Number of ways of line up when Betty is the first in line Total number of ways children line up = 1 × ( 𝑛 − 1 ) ! 𝑛 ! = 1 𝑛 P(B)= Total number of ways children line up Number of ways of line up when Betty is the first in line ​ = n! 1×(n−1)! ​ = n 1 ​ Step 2 Mary is last in the queue in the event 𝑀 M. Consequently, the likelihood of event 𝑀 M: 𝑃 ( 𝑀 ) = 1 𝑛 P(M)= n 1 ​ Step 3 Events 𝑀 M and 𝐵 B are apart from one another, hence: 𝑃 ( 𝑀 ∩ 𝐵 ) = 𝑃 ( 𝑀 ) ⋅ 𝑃 ( 𝐵 ) = 1 𝑛 ⋅ 1 𝑛 = 1 𝑛 2 P(M∩B)=P(M)⋅P(B)= n 1 ​ ⋅ n 1 ​ = n 2 1 ​ Step 4 Consequently, based on the definition provided in the query, the likelihood: 𝑃 ( 𝑀 ∪ 𝐵 ) = 𝑃 ( 𝑀 ) + 𝑃 ( 𝐵 ) + 𝑃 ( 𝑀 ∩ 𝐵 ) = 1 𝑛 + 1 𝑛 − 1 𝑛 2 = 2 𝑛 − 1 𝑛 2 P(M∪B)=P(M)+P(B)+P(M∩B)= n 1 ​ + n 1 ​ − n 2 1 ​ = n 2 2n−1