Discrete Math: Logic

Please see the attached file for the fully formatted problems.

Discrete Math True or False questions

1. Circle T if the corresponding statement is True or F if it is False.
T F The Fibonacci Sequence is {sn | sn = sn1 + sn2, with s0 = 1 and s1 = 1}.
T F The First (Weak) and Second (Strong) Principles of Mathematical Induction are
logically equivalent.
T F All recursively defined sequences of Integers take on successively larger values.
T F If lazy students fail CMSC203 and Paul passed CMSC203, then we can
conclude logically that Paul is not lazy.
T F Functions that are O(x2) grow faster than functions that are O(2x).
T F The product of a Rational and an Irrational is always Irrational.
T F The product of an Irrational and an Irrational is always Irrational.
T F For every recursive algorithm, there is an equivalent iterative algorithm.

2. Circle V for Valid or I for Invalid with respect to the following arguments:
V I All dogs run fast and Zeke runs slow, therefore Zeke is not a dog.
V I All dogs run fast and Zeke is a dog, therefore Zeke runs fast.
V I All dogs run fast and Zeke is not a dog, therefore Zeke runs fast.
V I All dogs run fast and Zeke runs fast, therefore Zeke is a dog.

3. Let {an} and {bn} be the sequences defined, for n > 0, by: an = n + 2n, bn = (1)n.
Find c0, c1, c2, and c3 when cn = (an)(bn).

4. Rank from 1 (least complex) to 10 (most complex) the complexity of algorithms
with the following orders:
Order n2    nlogn            n!          2n        1           n          nn         logn   10n         n10
Rank
Find the Big-Oh of the algorithm with complexity: (n5 + 1)(n + n2) + (5n2 + 3n 2)(n5).

5. Use the Euclidean Algorithm to find GCD(688,124).

6. Prove Theorem below using Mathematical Induction.

Theorem : Every integer greater than 1 is divisible by a prime.

7. Use the Methods of Valid Arguments to obtain the indicated conclusion.
Premises:
Paul does not forfeit his scholarship and Paul goes to class.
If Paul does not watch TV, then Paul gets good grades.
If Paul watches TV or Paul does not do his homework, then Paul does not go to class.
Paul does his homework or Paul forfeits his scholarship.
Conclusion:
Therefore, Paul gets good grades.

8. (20 points) Prove one of the two Theorems below by either Contradiction.
Theorem 1: If every integer has a prime factorization, then the set of primes is infinite.
Theorem 2: For all integers n and primes p, if p divides n, then p does not divide (n + 1).

Attached file(s):

1.doc  View File