Discrete Mathematics Answers

Let x and y be real numbers. Prove that, if 5x+y>11, then x>2 or y>1.

4. (2 points) Solve these recurrence relations together with the initial conditions given. Each is worth 1 point.

a) an = 6an-1 - 11an-3 +6an-3 for n > 3, a0 = 4, a1 = 6, a2 = 12

b) an = an–1 +9an-2 – 9an-3 for n > 3, a0 = 6, a1= 0, a2 = 30

Construct a truth table for each of these compound propositions. [6 marks]

a) p ⊕ p b) p ⊕￢p

c) p ⊕￢q d) ￢p ⊕￢q

e) (p ⊕ q) ∨ (p ⊕￢q) f ) (p ⊕ q) ∧ (p ⊕￢q)

Suppose that the domain of the predicateP(x) consists of −2, −1, 0, 1, and2. Write out each

of the following predicate logic formulas in propositional logic formulas using disjunctions, conjunctions,

negations, or their combinations.

use the Euclidean algorithm to express gcd(94, 159) as a linear combination of 94 and 159

Let P(x,y) denote the sentence x2 + 1≥ x + 1. What are the truth value of the following where the domain of x and y is the set of all integers?

a. ⱯxⱯyP(x,y)

b. ⱯxƎyP(x,y)

c. ƎxⱯyP(x,y) .

d. ƎxƎyP(x,y)

3. Which of the intervals (0, 5), (0, 5], [0, 5), [0, 51, (1,4], [2, 3], (2, 3) contains a) 0? b)1?c)2? d) 3? e)4? f)5?

Solve the linear congruence 34x ≡ 53(mod 89).

Suppose that a password for a computer system must have at least 6, but no more than 9 characters, where each character in the password is a lowercase English letter, or an uppercase English letter, or a digit, or one of the five special characters *, <, >, !, and #.

(a) How many different passwords are available for this computer system?

(b) How many of these passwords contain at least one occurrence of at least one of the five special characters?

(c) Using your answer to part (b), determine how long it takes a hacker to try every possible password, assuming that it takes one microsecond for a hacker to check each possible password.

Determine whether function f : Z × Z → Z is onto if (i) f(m,n)=2m−n

(ii) f(m,n)=m+n+1