Key Concepts in Computer Science -Assignment 5

1) [4 marks] Use rules of inference to show that the hypotheses
a) Randy works hard
b) If Randy works hard then he is a dull boy
c) If Randy is a dull boy, then he will not get the job
implies the conclusion “Randy will not get the job.”
Let w be the proposition “Randy works hard,” let d be the proposition “Randy is a dull boy,” and let j be the proposition “Randy will get the job.” We are given premises w, w  d, and d ¬ j. We want to conclude ¬ j.
Step Reason
1. w Hypothesis
2. w  d Hypothesis
3. d Modus ponens using (2) and (3)
4. d ¬ j Hypothesis
5. ¬ j Modus ponens using (3) and (4)
2) [12 marks] For each of these sets of premises, what relevant conclusion or conclusions can be drawn? Explain the rules of inference used to obtain each conclusion from the premises.
a) “If I eat spicy foods, then I have strange dreams.”
“I have strange dreams if there is thunder while I sleep.”
“I did not have strange dreams.”
 Using modus tollens we conclude two things-that I did not eat spicy food and that it did not thunder. Therefore, by the conjunction rule of inference, we conclude “I did not eat spicy food and it did not thunder.”
b) “I am either clever or lucky.”
“I am not lucky.”
“If I am lucky, then I will win the lottery.”
 By disjunctive syllogism from the first two hypotheses we conclude that I am clever. The third hypothesis gives us no useful information.
c) “Every Computer Science major has a personal computer.”
“Ralph does not have a personal computer.”
“Ann has a personal computer.”
 We can apply universal instantiation to the conditional statement and conclude that if Ralph (respectively, Ann) is a CS major, then he (she) has a PC. Now modus tollens tells us that Ralph is not a CS major. There are no conclusions to be drawn about Ann.
d) “All rodents gnaw their food.”
“Mice are rodents.”
“Rabbits do not gnaw their food.”
“Bats are not rodents.”
 The given conditional statement is “For all x, if x is a rodent, then x gnaws its food.” We can form the universal instantiation of this with x being a mouse, a rabbit, and a bat. Then modus ponens allows us to conclude that mice gnaw their food; and modus tollens allows us to conclude that rabbits are not rodents. We can conclude nothing about bats.
3) [6 marks] Prove that if m and n are integers and m×n is even, then m is even or n is even.
We use indirect proof (contraposition).
Assume the negation of “m is even or n is even” which is “m is not even and n is not even” (this is ¬q). In other words, “m is odd and n is odd”.
Now, we have to show that ¬p (negation of “m×n is even”) is true. In other words, we want to show “m×n is odd”.
Assuming m is odd and n is odd (¬q), we write m as 2k + 1 and n as 2k’ + 1. Then, m×n = (2k + 1) × (2k’ + 1) = 4kk’ + 2k + 2k’ + 1 = 2(2kk’ + k + k’) + 1.
Assume k’’ = 2kk’ + k + k’.
k’’ is an integer. Therefore, m×n is equal to 2k’’ + 1 which is an odd number (¬p).
We started from ¬q and showed ¬p. And the proof is complete.
4) [6 marks] Show that xP(x)  xQ(x) and x(P(x)  Q(x)) are not logically equivalent. Justify your answer.
Hint: You can prove this by constructing a counterexample. Choose a domain, e.g., integers, and two properties P and Q that integers may or may not have. Then show there exists an integer that has one property and there exists an integer that has the other property, but there does not exist an integer that has both properties.
We can show that these are not logically equivalent by giving an example in which one is true and the other is false.
Let P(x) be the statement “x is odd” applied to positive integers. Similarly let Q(x) be ”x is even”.
Then since there exist odd numbers and there exist even numbers, the statement xP(x)  xQ(x) is true. On the other hand, no number is both odd and even, so x(P(x)  Q(x)) is false.
5) [6 marks] Use a direct proof to show that the product of two odd numbers is odd.
Assume m is odd and n is odd, we write m as 2k + 1 and n as 2k’ + 1.
Then, m×n = (2k + 1) × (2k’ + 1) = 4kk’ + 2k + 2k’ + 1 = 2(2kk’ + k + k’) + 1.
Assume k’’ = 2kk’ + k + k’.
k’’ is an integer. Therefore, m×n is equal to 2k’’ + 1 which is an odd number.
6) [6 marks] Use a proof by cases to show that min(a, min(b, c)) = min(min(a, b), c) whenever a, b, and c are integers.
There are 6 cases as follows:
1) a ≥ b ≥ c
2) a ≥ c ≥ b
3) b ≥ a ≥ c
4) b ≥ c ≥ a
5) c ≥ a ≥ b
6) c ≥ b ≥ a
For each of them, we have to show min(a, min(b, c)) = min(min(a, b), c).
We show it for the first case here:
a ≥ b ≥ c
min(a, min(b, c)) = min(a, c) [because min(b, c) = c] ⟹ min(a, c) = c ⟹ min(a, min(b, c)) = c
min(min(a, b), c) = min(b, c) [because min(a, b) = b] ⟹ min(b, c) = c ⟹ min(min(a, b), c) = c
Thus, we show that min(a, min(b, c)) = min(min(a, b), c) = c and the proof is complete for the first case.