# UW-Madison MATH 240 - Exam 1 (12 pages)

Previewing pages*1, 2, 3, 4*of 12 page document

**View the full content.**## Exam 1

Previewing pages
*1, 2, 3, 4*
of
actual document.

**View the full content.**View Full Document

## Exam 1

0 0 57 views

Problems/Exams

- Pages:
- 12
- School:
- University of Wisconsin, Madison
- Course:
- Math 240 - Introduction to Discrete Mathematics

**Unformatted text preview: **

Exam 1 A Miller Spring 2002 Math 240 1 Show all work Circle your answer No notes no books no calculator no cell phones no pagers no electronic devices at all Solutions will be posted shortly after the exam www math wisc edu miller m240 Name Problem Points Score 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 5 9 5 10 8 11 8 12 8 13 8 14 8 15 8 Total 100 Exam 1 A Miller Spring 2002 Math 240 1 6 pts Show that p q and q p are logically equivalent 2 6 pts Construct a truth table for the following propositional sentence p q p r 2 Exam 1 A Miller Spring 2002 Math 240 3 3 6 pts Find a statement which is logically equivalent to x P x y Q y but in which the negation sign appears if at all only in front of the predicate symbols 4 6 pts Let A 1 2 and B 1 3 5 Find A B Exam 1 A Miller Spring 2002 5 6 pts Let A 1 3 4 B 2 4 and C 3 4 5 6 Find a A b B C c A B C 6 6 pts Let f R R be defined by f x bxc Let S 2 5 Find f 1 S Math 240 4 Exam 1 A Miller Spring 2002 Math 240 5 7 6 pts Compute the following double sum 2 X 3 X i j i 1 j 1 8 5 pts How large a problem can be solved in 10 seconds or less using an algorithm that when input n requires f n n2 bit operations where each bit operation is carried out in 10 9 seconds Exam 1 A Miller Spring 2002 Math 240 6 9 5 pts The value of the Euler function at the positive integer n is defined to be the number of positive integers less than or equal to n that are relatively prime to n Find 12 10 8 pts What is smallest positive integer k such that the function f n n log n 1 2 is O nk Exam 1 A Miller Spring 2002 Math 240 11 8 pts Show that 2n 2n 1 for all integers n 3 12 8 pts Let fn be the nth element of the Fibonacci sequence Prove that f1 f3 f5 f2n 1 f2n for every positive integer n 7 Exam 1 A Miller Spring 2002 13 8 pts Find a 2 2 matrix A so that 1 2 1 0 A 0 1 3 2 Hint Solve a system of linear equations Math 240 8 Exam 1 A Miller Spring 2002 Math 240 14 8 pts Let n ak ak 1 a2 a1 a0 2 be any positive integer written in binary Let E be the set of even k such that ak 1 and let O be the set of odd

View Full Document