TWiki> Main Web>ElementaryDiscreteMath2011>EDMExamIISampleTest (2011-05-15, JimSkon)

### Exam II Sample Test

1. Give an example of a function f: Z → Z that is 1 - 1 and not onto Z. f( x) = 2x

2. Give an example of a function f: Z → Z that is onto Z but not 1 - 1. f( x) = ⌊x/2

3. Suppose f: N → N has the rule f( n) = 4n + 1.

(a) Determine whether f is 1-1. Yes

(b) Determine whether f is onto N. No

4. Suppose g: A → B and f: B → C where A = {1,2,3,4}, B = {a,b,c}, C =

{2,7,10}, and f and g are defined by g = {(1,b),(2,a),(3,a),(4,b)} and f = {(a,10),(b,7),(c,2)}.

(a) Find f ° g {(1,7), (2,10), (3, 10), (4, 7)}

(b) Find f -1. {(10,a),(7,b),(2,c)}

5. Determine whether f below is a function from the set of all bit strings to the set of integers I

(a) f(S) is the position of the 1 bit in the bit string S. no

(b) f(S) is the number of 0 bits in S yes

(c) f(S) is the largest integer i such that the ith bit of S is 0 yes

(d) f(S) = 1 when S is the empty string (the string with no bits) otherwise f(S) = 0. yes

6. Consider the function that maps MVNU students to their GPA (a real number).

• Is this a function? Yes
• What is the range? {x | 0 ≤ x ≤ 4}
• Is the function Surjective? No, not every real is mapped to.
• Is the function Injective? No, two students may have the same GPA
• Is the function Bijective? No
7. What is the value of the following sums?

a) = 35

b) = 11

c) = 120

d)  8. (6) Give the first five elements in the following sequences of {an} if

a) an = 4n - 1 3, 7, 11, 15, 19

b) bn = 3n3 - 3 2, 23, 80, 191, 374

9. (8) Give definitions for the following sets.

a) { 7, 11, 15, 19, 23 … } an = 4n + 3

b) {8, 27, 64, 125, 216 ...} an = ( n + 1)3

10. (8) What rule of inference is used in each of the following arguments:

a. If it snows today, the university will be closed. The university will not be closed today. Therefore, it did not snow today. Modus tollens

b. If I work all night on this homework, than I can answer all the exercises. If I answer all the exercises, I will understand the material. Therefore, if I work all night on this homework, then I will understand the material. Hypothetical Syllogism

11. (4) Prove the following. Show your work.

 Rainy days make gardens grow. Gardens don't grow if it is not hot. It always rains on a day that is not hot. Therefore, if it is not hot, then it is hot.

 R –Rainy days G – Garden Grow H – hot Assume Invalid: Let H=F, G=F, R=F. Invalid! R → G ¬H → ¬G R → ¬H ∴ ¬H → H.

12. (4) Determine whether the following argument is valid. Show your work.

 It is not rainy and it is not cold. If it is not July, then it is rainy or cold. If it is July or August, then it is rainy. Therefore, it is rainy.

 R - Rainy days ¬R ∧ ¬C Assume Invalid: Let R=F, C=F, J=T C - Cold ¬J → (R ∨ C) Can’t make line three true! Valid! J - July (J ∨ A) → R A - August ∴ R.

 1 ¬R ∧ ¬C) 2 ¬(R ∨ C) Demorgans and 1 3 ¬J → (R ∨ C) 4 J Modus Tollens 5 J ∨ A Addition 6 (J ∨ A) → R 7 ∴R Modus ponens

13. (6) Determine if an argument of the following form is valid.

p → r

q → r

q ∨ ¬ r

∴ ¬ p.

Prove invalid by showing you can make the premises true but the conclusion false: Assume p is true to make the conclusion false. Then r must be true to make p → r true. Then q must be true to make q ∨ ¬ r true. Then r must be true to make q → r true. Thus invalid argument since we found a assignment of the variables which made the premises true but the conclusion false.

14. (5) Prove whether the following argument is valid. The universe of discourse is MVNU students. Justify.

Everyone who owns a hound dog can sing the blues.

Everyone either owns a TV or owns a hound dog.

Everyone who has a TV has electricity.

Bill does not have electricity

Therefore Bill can sing the blues

∀x HD(x) → B(x)

∀x TV(x) ∨ HD(x)

∀x TV(x) → E(x)

¬E(Bill)

∴ B(Bill)

1. ¬E(Bill)

2.∀x TV(x) → E(x)

3.∀x ¬E(x) → ¬TV(x) Contrapositive of 2

4. ¬E(Bill) → ¬TV(Bill) UI of 3.

5. ¬TV(Bill) 1 & 4 and Modus Ponens

6.∀x TV(x) ∨ HD(x)

7.TV(Bill) ∨ HD(Bill) UI of 6

8.HD(Bill) Disjuctive syllogism with 5 and 7

9.∀x HD(x) → B(x)

10.HD(Bill) → B(Bill) UI of 9

11.B(Bill) 8 & 10 and Modus Ponens Q.E.D

15. Prove or disprove the following:

 All babies are illogical. Nobody is despised who can manage a crocodile. Illogical persons are despised. Therefore, Anyone who can manage a crocodile is not a baby.

 B → ¬L If it is a baby then it is not logical. M → ¬D If it can manage a crocodile then it is not despised. ¬L → D If it is not logical then it is despised. ∴ M → ¬B If it can manage a crocodile then it is not a baby.

 1 B → ¬L 2 M → ¬D 3 ¬L → D 4 D → ¬M 2 contrapositive 5 B → D 1, 4 hypothetical syllogism 6 B → ¬M 4,5 hypothetical syllogism 7 M → ¬B 6 contrapositive

16. Prove or disprove the following:

 No interesting poems are unpopular among people of real taste. No modern poetry is free from affectation. All your poems are on the subject of soap-bubbles. No affected poetry is popular among people of real taste. No ancient poem is on the subject of soap-bubbles. Therefore, Your poetry is not interesting.

 Statement Contrapositive I → P ¬P → ¬I M → A ¬A → ¬M Y → S ¬S → ¬Y A → ¬P P → ¬A ¬M → ¬S S → M Y → ¬I

 Y → M hypothetical syllogism M → A hypothetical syllogism A → ¬I hypothetical syllogism Y → A hypothetical syllogism Y → ¬I hypothetical syllogism

16. Prove (using induction): Basis: (You must assume the sum on the right starts from 0)

P(1): Inductive hypothesis: P(k) → P(k + 1):

Assume True for some P(k): Show True for some P(k+1): Proof:    Some Interesting logic problems.

-- JimSkon - 2011-04-28

Topic revision: r6 - 2011-05-15 - JimSkon

Copyright &Â© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback