Elementary Discrete Mathematics

Exam II Sample Test

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

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

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

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

(b) Determine whether f is onto N. ... Close 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 ... Close {(1,7), (2,10), (3, 10), (4, 7)}

(b) Find f -1. ... Close {(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. ... Close no

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

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

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

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

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

a) ... Close = 35

b) ... Close = 11

c) ... Close = 120

d) ... Close

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

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

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

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

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

b) {8, 27, 64, 125, 216 ...} ... Close 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. ... Close 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. ... Close 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.

... Close

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.

... Close

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.

... Close 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

... Close ∀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.

... Close

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.

... Close

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):

... Close 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
 
This site is powered by the TWiki collaboration platformCopyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback