Homework 1 (due 19/10/2004 16:00)

 

Notes:

·        No collaboration.

·        Your answers should be your own work.

·        Cheaters will directly get an F from this course.

·        Submit your homework before the PS. Late submissions will not be graded.

 

  1. Let p, q, and r be the propositions

 

p : You get an A on the final exam.

q : You do every exercise in this book.

r : You get an A in this class.

 

            Write the following propositions using p, q, and r and logical connectives.

    1. Getting an A on the final and doing every exercise in this book is sufficient for getting an A in this class.
    2. You will get an A in this class if and only if you either do every exercise in this book or you get an A on the final.

 

  1. State the converse and contrapositive of the following implication. (Definitions of converse and contrapositive : Pg. 7 of the textbook)

When I stay up late, it is necessary that I sleep until noon.

 

  1. Show that the following implication is a tautology without using truth tables.

[(p Ú q) Ů (p ® q) Ů (q ® r)] ® r

 

  1. Let I(x) be the statement “x has an Internet connection” and C(x, y) be the statement “x and y have chatted over the Internet,” where the universe of discourse for the variables x and y is the set of all students in your class. Use quantifiers to express each of the following statements:
    1.  Everyone in your class with an Internet connection has chatted over the Internet with at least one other student in your class.
    2. There are at least two students in your class who have not chatted with the same person in your class.

 

  1. Rewrite the following statement so that negations appear only within predicates.(no negation is outside a quantifier or an expression involving logical connectives.)

Ř$y ($x R(x,y) Ú "x S(x,y))

 

  1. Prove that the union of two countable sets is countable.