Discrete Mathematics Answers

If p→q is false can you find the truth value of ~ (p ∧ q) →q? Explain your answer

6. (i) Show that postage of 24 cents or more can be achieved by using only 5-cent and 7-cent stamps.
(ii) c1 = 0 and cn = cn/2 + n2 for all n > 1.
(a) Compute c2,c3,c4 and c5. (b) Prove that cn < 4n2 for all n ≥ 1.

5. (i) Prove that 12 + 32 + 52 + ... + (2n + 1)2 = (n+1) 3 (2n + 1)(2n + 3), whenever n is a nonnegative integer.
(ii) Prove that 3 + 3.5 + 3.52 + ... + 3.5n = 3(5n+1 - 1) / 4, whenever n is a nonnegative integer.

Let P(n) be the statement that 12 + 22 + ... + n2 = n 6(n + 1)(2n + 1) for positive integer n.
(a) What is the statement P(1) ?
(b) Show that P(1) is true, completing the basis step of the proof.
(c) What is the inductive hypothesis?
(d) What do you need to prove in the inductive step?
(e) Complete the inductive step, identifying where you use the inductive hypothesis.
(f) Explain why these steps show that this formula is true whenever n is a positive integer?

Show that these statements about the integer x are equivalent.
(i) 3x + 2 is even. (ii) x + 5 is odd. (iii) x2 is even.

2. (i) Prove that if n is a positive integer, then n is even if and only if 7n + 4 is even.
(ii) Prove that if n is a positive integer, then n is odd if and only if 5n + 6 is odd.
(iii) Prove that m2 = n2 if and only if m = n or m = -n.
(iv) Prove or disprove that if m and n are integers such that mn = 1, then either m = 1 or else m = -1 and n = -1.

1. (i) Prove that if m and n are integers and mn is even, then m is even or n is even.
(ii) Show that if n is an integer and n3 + 5 is odd, then n is even using
(a) a proof by contraposition
(b) a proof by contradiction
(iii) Prove that if n is an integer and 3n + 2 is even, then n is even using
(a) a proof by contraposition
(b) a proof by contradiction
(iv)ProvethepropositionP(0),whereP(n)istheproposition”ifnisapositiveintegergreater than 1, then n2 > n.” What kind of proof did you use?
(v) Prove the proposition P(1), where P(n) is the proposition ” If n is a positive integer, then n2 ≥ n.” What kind of proof did you use?

2. Justify whether the given operations on relevant sets are binary operations or not.
i. Multiplication and Division on set of Natural numbers
ii. Subtraction and Addition on Set of Natural numbers
iii. Exponential operation: on Set of Natural numbers and set of Integers

Construct a proof for the five color theorem for every planar graph.

2. Obtain the product of sums canonical form of the following formula
i)(P^Q^R)V (¬P^Q^R)V(¬P^¬Q^¬R)