Description

Homework #1
Course Policy: Read all the instructions below carefully before you start working on the assignment, and before you make a submission.
• It is not a group homework. Do not share your answers to anyone in any circumstance. Any cheating means at least -100 for both sides.
• Do not take any information from Internet.
• No late homework will be accepted.
• For any questions about the homework, send an email to gizemsungu@gtu.edu.tr
• The homeworks (both latex and pdf files in a zip file) will be submitted into the course page of Moodle.
• The latex, pdf and zip files of the homeworks should be saved as ”Name Surname StudentId”.{tex, pdf, zip}.
• If the answers of the homeworks have only calculations without any formula or any explanation -when needed- will get zero.
• Writing the homeworks on Latex is strongly suggested. However, hand-written paper is still accepted IFF hand writing of the student is clear and understandable to read, and the paper is well-organized. Otherwise, the assistant cannot grade the student’s homework.
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:
1
(c) 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.
(a) (p ⊕¬ q)
(Solution)
(b) (p ⇐⇒ q) ⊕ ( ¬ p ⇐⇒ ¬ r)
(Solution)
(c) (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.”
(Solution)
(Solution)
(Solution)
(f) At least two students are happy.
(Solution)
(g) ¬∀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.
(a) {t : t is a root of x2 – 6x + 8 = 0}
(b) {y : y is a real number in the closed interval [2, 3]}
(c) {4, 2, 5, 4}
(d) {4, 5, 7, 2} – {5, 7}
(e) {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 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)