# Various Problems in Discrete Mathematics

Prove Each Directly.

1. The product of any two even integers is even.

Prove by cases, where n is an arbitrary integer and Ixl denotes the absolute

value of x.

2. [-x]=[x] (*Brackets are the x's is the absolute value symbol)

Give a counterexample to disprove each statement, where P(x) denotes an

arbitrary predicate.

3. Every month has exactly 30 days.

Let a, b, and c be any real numbers. Then a < b if and only if there

is a positive real number x such that a + x - b. Use this fact to prove

each.

4. If a+c is less than b+c, then a is less than b

Determine if the given sets are equal.

5. {x, {y}}, {{x},y}

Let A = {a, e, f, g,i}, B = {b, d, e, g, h}, C = {d, e, f, h, i}, and U= {a,b,... ,k}.

Find each set.

6. (A U B)'

© BrainMass Inc. brainmass.com October 25, 2018, 6:27 am ad1c9bdddfhttps://brainmass.com/math/discrete-math/various-problems-discrete-mathematics-460247

#### Solution Preview

1. Every even integer is divisible by two. Thus the product of two even integers is divisible by 4 and hence is divisible by 2 and is thus even.

2. If x is negative, then -x is ...

#### Solution Summary

We solve six simple problems in discrete mathematics. The product of any two even integers being even is determined.

Discrete Math : Logic (40 MC Problems)

1. Identify the rule of inference used in the following:

If it rains today, the flood gates will open. The flood gates did not open

today. Therefore, it did not rain.

a. modus tollens

b. hypothetical syllogism

c. modus ponens

d. disjunctive syllogism

2. Identify the rule of inference used in the following:

If I work all night on this homework, then 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.

a. modus tollens

b. hypothetical syllogism

c. modus ponens

d. disjunctive syllogism

3. The following argument is valid:

q

p

p q

∴¬

¬

→

a. True

b. False

4. Analyze the following argument:

If n is a real number such that n > 1, then n2 > 1. Suppose that n2 > 1,

then n > 1.

a. It is valid.

b. It is not valid because it begs the question.

c. It is not valid because it affirms the hypothesis.

d. It is not valid because it affirms the conclusion.

5. Analyze the following argument:

If n is a real number such that n > 2, then n2 > 4. Suppose that n ≤ 2,

then n2 ≤ 4.

a. It is valid.

b. It is not valid because it begs the question.

c. It is not valid because it denies the hypothesis.

d. It is not valid because it affirms the conclusion.

6. The following argument is valid:

Lynn works part time or full time

If Lynn does not play on the team, then she does not work part time

If Lynn plays on the team, she is busy

Lynn does not work full time

Therefore Lynn is busy

a. True

b. False

7. The statement "I visited New Orleans last month" logically implies

"Someone visited New Orleans last month."

a. True

b. False

8. You wish to prove theorem of the form "if p then q". To use the method

of direct proof, what do you assume and what do you prove?

a. assume p, prove q .

b. assume ¬q, prove p .

c. assume ¬q, prove ¬p .

d. assume p ∧ ¬q, prove otherwise .

9. You wish to prove theorem of the form "if p then q". To use the method

of indirect proof, what do you assume and what do you prove?

a. assume p, prove q .

b. assume ¬q, prove p .

c. assume ¬q, prove ¬p .

d. assume p ∧ ¬q, prove otherwise.

10. You wish to prove theorem of the form "if p then q". To use the method

of contradiction, what do you assume and what do you prove?

a. assume p, prove q .

b. assume ¬q, prove p .

c. assume ¬q, prove ¬p .

d. assume p ∧ ¬q, prove otherwise .

11. The method of mathematical induction is used to prove propositions of

the form: ∃ n P(n) .

a. True

b. False

12. The step that proves P(1) is called the basis step.

a. True

b. False

13. Why is mathematical induction valid?

a. It formalizes symbolic logic.

b. It follows from the well-ordering property.

c. It uses concrete examples as a means of proof by cases.

d. It is widely accepted as valid.

14. 2 | (n2 + 3n) for all n ≥ 1. (Hint: Use mathematical induction.)

a. True

b. False

15. 2n + 3 ≤ 2n for all n ≥ 4. (Hint: Use mathematical induction.)

a. True

b. False

16. A recursive definition specifies the value of the function at zero and

then gives a rule for finding it value at a given integer from its values

at smaller integers.

a. True

b. False

17. What is a reasonable name for the following procedure?

procedure mystery (x, y : integers)

if x = 0 then y := 1

else y := x*mystery(x-1)

a. Fibonacci

b. Factorial

c. Max

d. Product

18. Recursive functions are well-defined as a consequence of mathematical

induction.

a. True

b. False

19. What is a reasonable name for the following procedure?

procedure mystery (x, y : non-negative integers)

if x = 0 then answer := y

else answer := mystery(y mod x, x)

return(answer)

a. Binary Search

b. Power

c. Search

d. GCD

20. One of the common uses of recursive definitions is to define wellformed

formulae in various systems.

a. True

b. False

21. Σ* is:

a. the power set of Σ.

b. the set of strings over the alphabet Σ.

c. limited to the letters of the English alphabet.

d. limited to the non-negative integers.

22. Assume you have constructed a proof that P(k) is true for

3 ≤ k ≤ n. The proof of P(3) is called the:

a. basis step.

b. inductive step.

c. recursive step.

d. None of the above.

23. Continuing the above example, the ______________ step shows that

P(3) �� P(4).

a. basis step.

b. inductive step.

c. recursive step.

d. None of the above.

24. n2 > 2n whenever n is an integer greater than 4.

a. True

b. False

25. A procedure that starts with the value of the function at 1 and then

successively applies the definition to find the value of the function at

successively larger integers is said to be:

a. recursive.

b. iterative.

c. factorial.

d. None of the above.

26. The proof of the correctness of a program is called:

a. verification.

b. induction.

c. inference.

d. validation.

27. If you split a program into a series of subprograms and show that each

subprogram is correct, then you have established the program is

correct by means of:

a. verification.

b. induction.

c. inference.

d. validation.

28. A program is said to be ______________ if it produces the correct output

for every possible input.

a. correct

b. complete

c. partially correct

d. None of the above.

29. If the correct answer is obtained when a program terminates, it is said

to be:

a. correct.

b. complete.

c. partially correct.

d. None of the above.

30. To show that a conditional statement S in a program is correct, it is

necessary to show that:

a. when the condition is true, S executes.

b. when the condition is false, S does not execute.

c. both A and B.

d. None of the above.

31. Analyze the following rule of inference:

This inference rule is best described as:

a. if...then

b. while

c. compositional

d. loop invariant

32. The notation p{S}q is called a Hoare triple.

a. True

b. False

33. The notation p{S}q indicates the program or subprogram S is partially

correct with respect to the initial assertion p and the final assertion q.

a. True

b. False

p condition S q

p condition S q

( ){ }

( ){ }

2

1

∧ ¬

∧

34. Analyze the following rule of inference:

This inference rule is best described as:

a. if...then

b. while

c. compositional

d. loop invariant

35. Given the initial assertion is true and the following rule of inference,

what is the truth value of final assertion y = 2?

if x < 0 then

y := -2|x|/x

else if x > 0 then

y := 2|x|/x

else if x=0 then

y := 2

a. True

b. False

36. A sequence is a discrete structure used to define a set.

a. True

b. False

37. What is the lower limit of the index of summation for Σ=

100

1

1

j j

?

a. 0

b. 1

c. 100

d. None of the above.

38. What is the value of Σ =

5

2

2

i i ?

a. 32

b. 54

c. 55

d. 65

q S r

p S q

{ }

{ }

2

1

39. A sequence of the form a, ar, ar2, ar3, ar4,...,ark is called a harmonic

progression.

a. True

b. False

40. To compute a double summation,

a. expand the outer summation, then compute the inner summation.

b. expand the inner summation, then compute the outer summation.

c. expand the summation indices, then compute the function.

d. None of the above.