CSE211 Homework 1 Solved

Problem 1: Conditional Statements                                                                                                           
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                                                                                       
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                                                                                                                  
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.

(a)    There is a student at the university who can speak English and who knows Python. (Solution)

(b)   There is a student at the university who can speak English but who doesn’t know Python.

(Solution)
(c)    Every student at the university either can speak English or knows Python. (Solution)

(d)   No student at the university can speak English or knows Python.

(Solution)

(e)    If there is a student at the university who can speak English and know Python, then she/he is happy.

(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 2x1 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/