Discrete Mathematics
Problem 1: Conditional Statements (5+5+5=15 points)
State the converse, contrapositive, and inverse of each of these conditional statements.
(a) If it snows tonight, then I will stay at home.
(Solution) Converse:
Contrapositive:
Inverse:
(b) I go to the beach whenever it is a sunny summer day.
(Solution) Converse:
Contrapositive:
Inverse:
(c) When I stay up late, it is necessary that I sleep until noon.
(Solution) Converse:
Contrapositive:
Inverse:
1
Problem 2: Truth Tables For Logic Operators (5+5+5=15 points)
Construct a truth table for each of the following compound propositions.
(a) (p ⊕¬ q)
(Solution)
(b) (p ⇐⇒ q) ⊕ ( ¬ p ⇐⇒ ¬ r)
(Solution)
(c) (p ⊕ q) ⇒ (p ⊕¬ q)
(Solution)
Problem 3: Logic in Algorithms
(10+10+10=30 points)
If x = 1 before the statement is reached, what is the value of x after each of these statements is encountered in a computer program? Why? Show your work step by step. (a) for i ⇐ 1 to 10 do if x + 2 = 3 then x := x + 1
end
(Solution)
(b) for i ⇐ 1 to 5 do if (x + 1 = 2) XOR (x + 2 = 3) then x := x + 1
end
(Solution)
(c) for i ⇐ 1 to 4 do if (2x + 3 = 5) AND (3x + 4 = 7) then x := x + 1
end
(Solution)
Problem 4: Proof by contradiction
(20 points)
Show that at least three of any 25 days chosen must fall in the same month of the year using a proof by contradiction. Explain your work step by step.
(Solution)
Problem 5: Proof by contraposition
(20 points)
Show that if n3 + 5 is odd, then n is even using a proof by contraposition. Explain your work step by step. Note: Assume that n is an integer. (Solution)
