Description
Problem 1: Conditional Statements (5+5+5=15 points)
State the converse, contrapositive, and inverse of each of these conditional statements.
- If it snows tonight, then I will stay at home.
(Solution) Converse:
Contrapositive:
Inverse:
- I go to the beach whenever it is a sunny summer day.
(Solution) Converse:
Contrapositive:
Inverse:
1
- If I stay up late, then I sleep until noon.
(Solution) Converse:
Contrapositive:
Inverse:
Problem 2: Truth Tables For Logic Operators (5+5+5=15 points)
Construct a truth table for each of the following compound propositions.
- (p ⊕¬ q)
(Solution)
- (p ⇐⇒ q) ⊕ ( ¬ p ⇐⇒ ¬ r)
(Solution)
- (p ⊕ q) ⇒ (p ⊕¬ q)
(Solution)
Problem 3: Predicates and Quantifiers (21 points)
There are three predicate logic statements which represent English sentences as follows.
- P(x): ”x can speak English.”
- Q(x): ”x knows Python.”
- H(x): ”x is happy.”
Express each of the following sentences in terms of P(x), Q(x), H(x), quantifiers, and logical connectives or vice versa. The domain for quantifiers consists of all students at the university.
- There is a student at the university who can speak English and who knows Python. (Solution)
- There is a student at the university who can speak English but who doesn’t know Python.
(Solution)
- Every student at the university either can speak English or knows Python. (Solution)
- No student at the university can speak English or knows Python.
(Solution)
- If there is a student at the university who can speak English and know Python, then she/he is happy.
(Solution)
- At least two students are happy.
(Solution)
- ¬∀x(Q(x) ∧P(x))
(Solution)
Problem 4: Mathematical Induction (21 points)
Prove that 3 + 3 . 5 + 3 . 5 whenever n is a nonnegative integer.
(Solution)
Problem 5: Mathematical Induction (20 points)
Prove that n2 – 1 is divisible by 8 whenever n is an odd positive integer.
(Solution)
Problem 6: Sets (8 points)
Which of the following sets are equal? Show your work step by step.
- {t : t is a root of x2 – 6x + 8 = 0}
- {y : y is a real number in the closed interval [2, 3]}
- {4, 2, 5, 4}
- {4, 5, 7, 2} – {5, 7}
- {q: q is either the number of sides of a rectangle or the number of digits in any integer between 11 and 99}
(Solution)
Problem Bonus: Logic in Algorithms (20 points)
Let p and q be the statements as follows.
- p: It is sunny.
- q: The flowers are blooming.
Figure 1: Combinational Circuit
In Figure 1, the two statements are used as input. The circuit has 3 gates as AND, OR and NOT operators. It has also a 2×1 multiplexer[1] which provides to select one of the two options. (a) Write the sentence that ”result” output has.
(Solution)
(b) Convert Figure 1 to an algorithm which you can write in any programming language that you prefer (including pseudocode).
(Solution)
[1] https://www.geeksforgeeks.org/multiplexers-in-digital-logic/
