Math 215

Exam 1    Fall 2002

with some solutions and some hints

1)   Let X={1,2,3,4}, Y={a,b,c,d,e} and Z={!,#,%,*}.   Also, note the following operations:

f: X→Y such that 1→a

                              2→c

                              3→a

                              4→e

g:X→Z such that 1→!

                              2→#

                              3→%

                              4→*

h:Z→Y such that ! →a

                              #→b

                              %→e

                              *→d

Which of the operations are functions?

f,g,h

Which of the functions are one-to-one?

g, h

Which of the functions are onto?

g

Which of the functions are bijections?

g

Which of the functions are invertible?

G

2)      Let A={x: x is in the English alphabet}, B={a,e,i,o,u}, C={a,b,c,d,e} and Σ={1,2}.  Please list the elements in the following sets:

a)      C∩B

a,e

b)      B\C

I,o,u

c)      Σ x C

(1,a),(1,b),(1,c),(1,d),(1,e), (2,a),(2,b),(2,c),(2,d),(2,e)

d)      F={w in Σ* : length(w)=3}

111,112,121,122,211,212,221,222

e)      What is |A|?

26

3)   Show that if 3|n² then 3|n.  (Hint: Use contrapositive and cases.)

The contrapositive says if 3 does not divide n then 3 does not divide n².  Assume 3 does not divide n.  Then n=3k+1 or n=3k+2 for some integer k. 

Case 1: n=3k+1.  This implies n²=(3k+1)²=9k²+6k+1=3(3k²+2k)+1 which is not divisible by 3.

Case 2: n=3k+2.  This implies n²=(3k+2)²=9k²+12k+4=3(3k²+4k+1)+1 which is not divisible by 3.

Thus if 3 doesn’t divide n then 3 doesn’t divide n² so by contrapositive, if 3|n² then 3|n.

4)   Prove that √3 is an irrational number.

This is section 2.4 #2.  Imitate proof for √2 is an irrational number.

5)   a)         True or False: There are a finite number of prime numbers.  False

b)   Fill in the blank: The gcd(p,q) where p and q are relatively prime is_1____.

c)   The converse of the statement “If the dog is white, her name is Libby” is:

If her name is Libby then the dog is white.

d)   True or False: A prime number has two positive divisors. True

6)   Prove or disprove: If 4|n² then 4|n.

Disprove: 4 divides 2² but 4 does not divide 2

7)   If x and y are both even integers or both odd integers, then their sum is even.

Case 1: Let x and y both be even.  Then x=2j and y=2k for some j and k in the integers.  X+y=2j+2k=2(j+k) which is even.

Case 2: Let x and y both be odd.  Then x=2m+1 and y=2n+1 for some m and n in the integers.  They x+y=2m+1+2n+1=2m+2n+2=2(m+n+1) which is even.

8)   Prove or disprove: [(p→r)^(q→r)] is logically equivalent to [(pvq) →r].  Make sure you explain how what you’ve done provides support for your argument.

These statements are logically equivalent.  This can be shown by building the truth table for

[(p→r)^(q→r)]↔[(pvq) →r] gives all “trues” under ↔

9)   Write the following argument using logical connectives then determine whether or not the argument is valid.  Make sure you support your answer.

Janet will pass this course if and only if she works hard.  Either she’ll work hard or she won’t graduate.  But Janet will graduate; therefore she will pass this course.

H1: P↔W  H2: Wv –G   H3: G  C: P

Build truth table.  Highlight any lines where H1,H2 and H3 are true.  If C is also true, it’s a valid argument.