Exam 1 Math 205 Fall 1998 - University of Michigan



Exam 1 Math/ECE 276 Fall 2015

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) Are the expressions (p(q)(q'(r) and (q(p)r logically equivalent? Show why or why not.

2. (10 points) Let B(x) be the predicate “x is a boy,” G(x) the predicate “x is a girl,” and L(x,y) the predicate “x loves y” where the universe of discourse is the set of 6th grade students at Maple Elementary School. Use quantifiers and B, G, and L to express the following statement.

If some boy loves a girl, then there is some girl that loves that boy.

3. (14 points) Consider the proposition (x (y ( ( y ( ( ( x ( )

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

ii. 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 E(x), D(x), P(x) and T(x) be the following predicates.

E(x) = x was an ECE major

D(x) = x took Discrete Mathematics

P(x) = x has an iPad

T(x) = x has used iTunes

Write the following argument using E(x), D(x), P(x), T(x) and the logical operators. Suppose the universe is students who went to UMD.

If if all ECE majors took Discrete Mathematics

and if all non ECE majors have an iPad

and everyone who has an iPad has used iTunes

then if John didn't take Discrete Mathematics then John has used iTunes

5. (13 points) Use the rules of inference and equivalences on the formula sheet to show that ((p+q)(r)(r(s)s( ( q( is a valid argument.

6. (13 points) Is it true that (A – B) ( C = (A ( C) – (B – C) for any three sets A, B and C? If so, show why. If not, give a specific example of three sets A, B and C for which it is not true. Here – denotes the difference operation on sets, e.g. A – B is the set of all objects that are in A but not in B.

7. Consider the sum = (1 mod 2) + (2 mod 2) + (3 mod 2) + ( + (n mod 2).

a. (4 points) Find a nice closed form formula for the sum if n is even.

b. (4 points) Find a nice closed form formula for the sum if n is odd.

c. (4 points) Combine your answers to a. and b. into a single nice closed sum formula for the sum that holds in both the cases where n is even or n is odd. You may want to use ( (, ( ( or mod in the combined formula.

8. (13 points) Consider the following algorithm.

for k = 1 to n

│ for j = 2k to k2 + 2

└ └ 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. Let LHS = (p(q)(q'(r) and RHS = (q(p)r

p |q |r |p(q |q' |q'(r |LHS |q(p |RHS | |0 |0 |0 |1 |1 |0 |0 |1 |0 | |0 |0 |1 |1 |1 |1 |1 |1 |1 | |0 |1 |0 |1 |0 |1 |1 |0 |0 | |0 |1 |1 |1 |0 |0 |0 |0 |0 | |1 |0 |0 |0 |1 |0 |0 |1 |0 | |1 |0 |1 |0 |1 |1 |0 |1 |1 | |1 |1 |0 |1 |0 |1 |1 |1 |0 | |1 |1 |1 |1 |0 |0 |0 |1 |1 | |The LHS column is not the same as the RHS column, so (p(q)(q'(r) and (q(p)r are not equivalent.

2. (x[{B(x) (y(G(y)L(x,y))} ( (y(G(y)L(y,x)) ]

3. i. There exists a number whose ceiling is less than or equal to the floor of every number. ii. This is false because suppose x were such a number. Then we could choose y = ( x ( - 1 and then ( y ( = y = ( x ( - 1 which is less than ( x (, not greater than or equal to ( x ( as desired.

4. {[(x(E(x)(D(x))] ( [(x(E(x)((P(x))] ( [(x(P(x)(T(x))]} ( (D(John)((T(John))

5. Step Reason

1. r(s Premise

2. s( Premise

3. r( Modus Tollens using 1 and 2 (4 pts)

4. (p+q)(r Premise

5. p+q Modus Tollens using 3 and 4 (4 pts)

6. p(q' DeMorgan using 5 (4 pts)

7. q' Simplification (1 pts)

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 = R4 + R5 where + indicates union. (2 pts) So (A - B) ( C = R1 + R3 + R4 + R5 + R7. (2 pts) On the other hand A ( C = R1 + R3 + R4 + R5 + R6 + R7 (2 pts) and B - C = R2 + R6. (2 pts) So (A ( C) – (B – C) = R1 + R3 + R4 + R5 + R7. (2 pts) This is the same as (A - B) ( C. So they are the same for any A, B, C. (3 pts)

6. a. (1 mod 2) + (2 mod 2) + (3 mod 2) + ( + (n mod 2)

= 1 + 0 + 1 + 0 + ( + 1 + 0 =

b. (1 mod 2) + (2 mod 2) + (3 mod 2) + ( + (n mod 2)

= 1 + 0 + 1 + 0 + ( + 1 + 0 +1 =

c. ( (

8. First consider the inner loop. j runs from 2k to k2 + 2. There are k2 + 2 - 2k + 1 = k2 - 2k + 3 values of j in this range. Each time the inner loop is done with a given value of k the statement x = x + 1 is done Tk = k2 - 2k + 3 times. (6 pts) Now consider the outer loop. k runs 1 to n. We need to sum up Tk as k runs through these values. So Sn = = - 2 + = - 2 + 3n = ((n+1)(2n+1) – 3(n+1) + 18 = = . (7 pts)

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

R0

R1

R2

R3

R4

R5

R6

R7

A

B

C

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

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

Google Online Preview   Download