COT3100/7094X Fall '99:
Exam 1 Sample Problems - Solutions

For some problems, we have also included, for your benefit, additional explanation which would not need to be included in your exam answers.

1. Plug in truth values, and simplify:

   (p r) (p r)	(F F) (F F)
   	F F
   	T

   So (in this case) the statement has truth value "true."

   Notes: If p=r=F, then pr=F, and pr=F. Since the antecedent and consequent are both false, the implication is by definition true. Another way to see this is that since the implication is equivalent to the disjunction ¬(pr) (p r), and one of the terms in that disjunction, namely ¬(p r), is true, the whole statement is true.

2. Converse:

   ``I will go to Disneyworld if the hurricane doesn't hit Florida.''

   Contrapositive:

   ``I won't go to Disneyworld if the hurricane hits Florida.''

   The contrapositive is logically equivalent.

   Notes: A statement of the form ``p only if r'' says that a minimum condition for p being true is that r is true. That is, p can possibly be true only in cases when r is true, and no others. So if p is true, this implies that r must be true. The statement is the same as ``p implies r.'' So, ignoring tense, the statement can be written as ``(I go to Disneyworld) implies (the hurricane doesn't hit Florida).'' That is, with p = ``I go to DW'' and r = ``The hurricane hits Fla.,'' the statement is (p ¬r). The converse means swapping the terms, (¬r p), which would mean, ``If the hurricane doesn't hit Florida, then this implies I will go to Disneyworld.'' The two clauses can be swapped with "if" moved to the middle, so this is just "I will go to DW if the hurricane doesn't hit Florida," our first answer. The contrapositive, which means swapping and negating the terms, (r ¬p), would be ``If the hurricane hits, then this implies I will not go to Disneyworld." As a general rule, it is only the contrapositive that is logically equivalent to the original statement. ``p only if r'' does not imply ``p if r.''

3. (a)

   (1)	(2)	(3)	(4)	(5)	(6)
   p	r	p r	¬p	r ¬p	¬(r ¬p)
   --	--	-----	---	-------	----------
   F	F	F	T	T	F
   F	T	F	T	T	F
   T	F	F	F	T	F
   T	T	T	F	F	T

   Columns 3 and 6 (corresponding to the two given statements) are identical, therefore the given statements are equivalent.

   (b)

   p r	¬(¬p ¬ r)	- DeMorgan's law
   	¬(¬r ¬p)	- Commutative law for disjunction
   	¬(r ¬p)	- Definition of ``'': ab ¬a b

   Therefore,

   p r ¬(r ¬p)

4. Yes, an associative law does hold. Proof via truth table:

   p	r	s	p r	r s	((p r) s)	(p (r s))
   --	--	--	-----	-----	---------	---------
   F	F	F	T	T	F	F
   F	F	T	T	F	T	T
   F	T	F	F	F	T	T
   F	T	T	F	T	F	F
   T	F	F	F	T	T	T
   T	F	T	F	F	F	F
   T	T	F	T	F	F	F
   T	T	T	T	T	T	T

   The last two columns are equivalent, therefore, the associative law holds for .

5. x Q(x) is FALSE because, for example, Q(x) is not true for x=0. (x²+1 = 1, whereas x - 2 = -2).

   x Q(x) is also FALSE, because the equation Q(x) has no real-valued roots.

   Note: Show how you got the second answer by sketching the function graphs, or by expressing x using the quadratic formula, and checking the square-root term.

6. m n P(n,m) is TRUE because if we let m=0, then all non-negative integers n are greater than or equal to m.

   m n (P(n,m) P(m,n)) is also TRUE, because for any value of m, just let n=m, and then P(n, m) and P(m, n) are both true.

7. (a) {2, 3}
   (b) {2}
   (c) {0, 1, 2, 3, 4, 6, 8, 10}
   (d) {0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11}
   (e) {0, 4, 6, 8, 10}
   (f) B - {0, 1, 3, 4} = {2, 6, 8, 10}

8. (A - C) is the set of all elements of A that are not in C, and (B - C) is all elements of B that are not in C. So the union of these two is all elements from either A or B, that are not in C. This is just what the first statement is saying.

9. You could answer this using a pure logical derivation:

   A - (B C)	= { x | (x A) ¬(x (B C)) }
   	= { x | (x A) ¬((x B) (x C)) }
   	= { x | (x A) (¬(x B) ¬(x C)) }
   	= { x | ((x A) ¬(x B)) ((x A) ¬(x C)) }
   	= { x | x (A - B) x (A - C) }
   	= (A - B) (A - C)

   or, a clear answer in English is also acceptable:

   The elements of A - (B C) are, by definition, in A, but not in both B and C. Therefore they are in A, and either not in B, or not in C. Therefore they are either in A but not B, or A but not C. So they are in the union of (A - B) and (A - C). (And all also conversely.)

10. Yes, f is one-to-one, because 3n-2 is strictly increasing, therefore, any horizontal line across its graph intersects it at only one point, so there is always only one x such that f(x)=y. This is what it means for f to be one-to-one. Further, f can be a function to the reals because the range of f when the domain is the integers is a subset of the reals, so the reals could be a co-domain of f.

    No, f over the domain of the integers has a range which does not cover all integers. All values of f(n) are odd, so no even integer is covered by f. Therefore, f with a domain of the integers is not onto the integers.

11. In this case, it happens that f^-1 = f.

    Note: This happened to be a special case in which f was its own inverse. Another function of this sort is f(x) = 1/x, over a domain and codomain of {x | x 0}.

    If, on the other hand, f had not happened to be its own inverse, then you would have had to write out all the values of f^-1, as was done for f in the problem statement.

12. One-to-one: No, because, for example, f(0) = f(1) = 0.
    Onto: Yes, because for any y , there is an x in the domain, namely 3y, such that f(x) = y.

13. We saw in the homework that the set of rationals is countable. All reals are either rational or irrational, so if the set of irrationals was countable, then we could list all the reals by simply enumerating the rationals and irrationals in parallel, and alternating back and forth between the two lists. However, we saw in the book and in lecture that there is no way to list all the reals (even with an infinite list), so our conjecture that the set of irrationals was countable must be false.

14. 5			(j=3)		(j=4)		(j=5)
    	8	=	8	+	8	+	8	=	24
    j=3

    3			(j=-1)		(j=0)		(j=1)		(j=2)		(j=3)
    	-j+2	=	[-(-1)+2]	+	(-0+2)	+	(-1+2)	+	(-2+2)	+	(-3+2)
    j=-1		=	3	+	2	+	1	+	0	+	(-1)
    		=	5

15. 300
    	4 = 300 4 = 1200.
    j=1

    This next one is a little tricky:

    50			/	25		\		/	25		\
    	(-1)j	=	|		(-1)2k	|	+	|		(-1)2k-1	|
    j=1			\	k=1		/		\	k=1		/
    			/	25		\		/	25		\
    		=	|		1k	|	+	|		1k/(-1)	|
    			\	k=1		/		\	k=1		/
    			/	25		\		/	25		\
    		=	|		1	|	+	|		-1	|
    			\	k=1		/		\	k=1		/
    		=			25		+			-25
    		=	0

    Note: What we are doing here is splitting the summation into the terms with even values of j, which we represent as 2k, and the terms with odd values of k, which we represent as 2k - 1, with an appropriate range of indexes for k so that all the original values of j are covered. For all the even values of j, the -1 raised to the power of j is just 1, and similarly all the odd terms are -1. There are the same number (25) of both, so they all cancel out.

16. 2n2 - 3n + 7	< 2n2 + 7	(when n>0)
    	< 2n2 + 7n2	(when n>1)
    	= 9 n2

    so, 2n² - 3n + 7 < 9 n² when n>1.

    So, there exist constants k=1 and c=9, such that n>k: 2n² - 3n + 7 < c n².

    Thus, 3n² + 8n + 7 is O(n²).

17. n			n
    	(j2 + 1)	<	(n2 + 1)	(when n > 1)
    j=1			j=1
    		=	n (n2 + 1)
    		=	n3 + n
    		<	n3 + n3	(when n>1)
    		=	2n3

    so, for k=1, c=2,

    n

    (j2 + 1) < c n3.

    j=1

    Another acceptable answer (Since the question did not ask for c and k):

    Since j is no greater than n, each term (j² + 1) in the summation is O(n²), since the high-order sub-term of the term is no greater than n². There are n of these O(n²) terms in the summation, so the maximum order of the entire summation is the product of O(n) and O(n²), or O(n³).

18. x^1/2 O(x). (Let k=1, c=1.)

    log(3 x4)	= log(x4) + log 3
    	= 4 log x + log 3
    	O(log x).

    So, x^1/2 log(3 x⁴) is O(x log x).

    log(2^x) = x log 2 O(x).

    f(x) is the sum of an O(x log x) function and an O(x) function, so f is O(x log x).