Exam 1 Math 205 Fall 1998 - University of Michigan



Exam 1 Math/ECE 276 Winter 2016

Name: ___________________ This is a closed book exam. You may use a calculator and the formulas handed out with the exam. Show all work and explain any reasoning which is not clear from the computations. (This is particularly important if I am to be able to give part credit.) Turn in this exam along with your answers. However, don't write your answers on the exam itself; leave them on the pages with your work. Also turn in the formulas; put them on the formula pile.

1. (13 points) Recall that a logical expression is a tautology if it is true for every value of its variables. Is ((p(q) ( (q(r)) ( (p(r) a tautology? Show why or why not.

2. (10 points) Let D(x,y) be the predicate “x has beat y in darts” and P(x,y) the predicate “x has beat y in pool” where the universe of discourse is the set of all ECE majors at UM-D. Use quantifiers and D and P to express the following statement.

Every person that has beat everybody in darts has also beat everybody in pool.

3. Consider the proposition (y (x ( y2 > x )

i. (6 points) Translate it into everyday English in a form that could be understood by a high school algebra class.

ii. (7 points) Tell whether it is true or false and explain the reason for your answer.

Assume the universe is the set of all real numbers.

4. (12 points) Let H(x), T(x) and E(x) be the following predicates.

H(x) = x is healthy to eat

T(x) = x tastes good

E(x) = you eat x

Write the following proposition using H(x), T(x), E(x) and the logical operators.

If every food that is healthy to eat doesn't taste good

and Tofu is healthy to eat

and you only eat what tastes good

then you do not eat Tofu

5. (13 points) Use the rules of inference on the formula sheet to show that [p'q(r(p)(r'(s)(s(t)](t is a valid argument.

6. (13 points) Suppose A, B and C are three sets with the property that (A ( B) ( C = (. Does this imply A ( B ( C? If so, prove it. If not, give a counterexample. Here ( denotes the symmetric difference operation on sets, i.e. A ( B is the set of all objects that are in A or B but not both. Answer this question by doing the following.

a. (7 points) Make a Venn diagram of (A ( B) ( C to determine which elements x are in (A ( B) ( C.

b. (3 points) What does the condition (A ( B) ( C = ( imply about various types of x.

c. (3 points) From parts a and b can you conclude A ( B ( C?

7. (13 points) Which real numbers x satisfy the condition ( x – ½ ( = 3? Here ( y ( is the floor of y.

8. (13 points) Consider the following algorithm.

for k = 3 to n2

│ for i = k+1 to 2k+3

│ │ x = x + 1

│ └───

└──────

Let Sn be the number of times the statement x = x + 1 is done for a given value of n. Find a formula for Sn. In the formula sums like 1 + 2 + 3 + ( + n should be replaced by their closed form equivalents.

Solutions

1.

|p |q |r |p(q |q(r |(p(q)((q(r) |p(r |(p(q)((q(r)((p(r) |

|0 |0 |0 |1 |1 |1 |1 |1 |

|0 |0 |1 |1 |0 |0 |0 |1 |

|0 |1 |0 |0 |0 |0 |1 |1 |

|0 |1 |1 |0 |1 |0 |0 |1 |

|1 |0 |0 |0 |1 |0 |0 |1 |

|1 |0 |1 |0 |0 |0 |1 |1 |

|1 |1 |0 |1 |0 |0 |0 |1 |

|1 |1 |1 |1 |1 |1 |1 |1 |

(p(q)((q(r)((p(r) is a tautology since it is true for every combination of values of the variables p, q and r.

2. (x ( ((y D(x,y) ) ( ((y P(x,y) ) (2 + 1.5 + 1.5 + 2 + 1.5 + 1.5 pts)

3. i. For every number there is another number less than the square of the first. ii. This is true because y2 - 1 is less than the square of y.

4. {[(x(H(x)(T(x)']H(Tofu)[(x(E(x)(T(x)]}(E(Tofu)' (2.5 + 2.5 + 2.5 + 2 + 2.5 pts)

5. Step Reason

1. p' Premise

2. r ( p Premise

3. r' Modus tollens using 1 and 2

4. r' ( s Premise

5. s Modus ponens using 3 and 4

6. s ( t Premise

7. t Modus ponens using 5 and 6

6. Here is a Venn diagram showing three sets A, B and C. The numbered regions represent all eight possible relationships a given x can bear to each of the sets. For example, the region 1 represents those x that are in C but not A or B. With this in mind, A(B = 2 + 3 + 4 + 5 where + indicates union. So (A(B)(C = 1 + 2 + 4 + 7. (7 pts) So the condition (A(B)(C = ( implies that all the regions 1, 2, 4 and 7 are empty. (3 pts) This implies A = 5 + 6. Each of these regions is in B(C, so A(B(C. (3 pts)

7. ( x – ½ ( = 3 ( 3 ( x – ½ < 4 (7 pts) ( 3.5 ( x < 4.5. (6 pts) So the numbers between 3.5 and 4.5, including 3.5, but excluding 4.5 satisfy the equation.

8. First consider the inner loop. i runs k+1, k+2, …, 2k+3. There are k+3 values of i in this range. Each time the inner loop is done with a give value of k the statement x = x + 1 is done Tk = k+3 times. (7 pts) Now consider the outer loop. k runs 3, 4, 5, …, n2. As k runs through these values Tk runs through the values (3+3), (4+3), (5+3), …, (n2 + 3), i.e. 6, 7, 8, …. , (n2 + 3). Sn is the sum of these numbers, i.e. Sn = 6 + 7 + 8 + … + (n2 + 3) (3 pts) = 1 + 2 + 3 + + … + (n2 + 3) – (1 + 2 + 3 + 4 + 5) = - 15 = - 15 = + - 9. (3 pts)

-----------------------

0

1

2

3

4

5

6

7

A

B

C

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download