Discrete Mathematics Answers

1. Which of the following statements are true and which are false? Give reasons for your

answer. (20)

i) ‘x

2 +y

2 −3 is not dividible by 4.’ is mathematical statement.

ii) The number of onto functions from {1,2,3,4,5,6} to {a,b, c,d} is 4!S

4

6

.

iii) The generating function associated with a sequence can never be a polynomial.

iv) K4,4 is non-planar.

v) Every bipartite graph with odd number of vertices is non-hamiltonian.

vi) an = an

2

+n,a1 = 0, where n is a power of 2, is a linear recurrence relation.

vii) The generating function of the sequence {1,2,3,4,...,n...} is (1−z)

−2

.

viii) If g(x) is the generating function for {an}n≥1, then (1−x)g(x) is the generating

function for the sequence {bn}n≥1 where bn = an −1,∀n.

ix) If a graph is isomorphic to its complement, then it has odd number of vertices.

x) Every 3-colourable graph is 4-colourable.

Suppose that Q(x) is “x+1=2x”, where x is a real number. Find the truth value of the following statement: 

a) Q(2) b) ∀𝑄(𝑥) c) ∃𝑄(𝑥) 

Prove the equivalence of the following in three different ways (truth table, simplification,

each is a logical consequence of the other): p → (q ∨ r) ≡ (p ∧ ~q) → r.

Let R be the relation on the set A = {1,2,3,4,5,6,7} defined by the rule (a,b) equivalent to R, if the integer (a-b) is divisible by 4,

List the elements of R and its inverse

1. Let p and q be the propositions

p : I bought a lottery ticket this week.

q : I won the million dollar jackpot.

Express each of these propositions as an English sentence.

a) ¬p 

b) p ∨ q 

c) p → q

d) p ∧ q 

e) p ↔ q 

f ) ¬p → ¬q

g) ¬p ∧ ¬q 

h) ¬p ∨ (p ∧ q)

determine the truth value of each of the following truth values

if 2+3=5 then 2x3=6

Show that -p → (q + r) and q→ (p V r) are logically equivalent.

Self - Assessment

A. List the members of the following sets

1. {x| x is real numbers and x2 = 1}

2. {x| x is an integer and -4 < x ≤ 3}

B. Use set builder notation to give description of each of these sets.

1. {a, e,i ,o, u}

2. {=2, -1, 0, 1, 2}

C. Let A= (a, b, c), B = (x, y) and C = (0, 1)

Find:

1. A U C

2. C x B

3. B – A

4. (A ∩ C) U B

D. Find these terms of the sequence (An}, where An = 2(3)n + 5

1. A0

2. A5

3. A3

4. 8th term

5. 2nd term

6. Sum of the sequence

E. Given the following set:

2. X = {-1, 0, 1, 2, 3, 4, 5} defined by the rule (x, y) ∈R if x ≤ y

F. List the elements of R

G. Find the domain of R

H. Find the range of R

I. Draw the digraph

J. Properties of the Relation

Show step by step:

find the inverse of {(-3,1) (2,4) (8,9)}

Let R be the relation on the set A = {1,2,3,4,5,6,7} defined by the rule (a,b) belongs to R, if the integer is divisible by 4,

List the elements of R and its inverse