(2½ Hours) [Total Marks: 75]

N. B.: (1) All questions are compulsory.

(2) Make suitable assumptions wherever necessary and state the assumptions made.
(3) Answers to the same question must be written together.
(4) Numbers to the right indicate marks.
(5) Draw neat labeled diagrams wherever necessary.
(6) Use of Non-programmable calculators is allowed.

1. Attempt any three of the following: 15

a. 1) Use the set-roster notation to indicate the elements in each of the following sets.
i. S = {n ∈ Z| n = (−1)k , for some integer k}.
ii. T = {m ∈ Z |m = 1 + (−1)i , for some integer i}.
iii. U = {r ∈ Z| 2 ≤ r ≤ −2}
iv. V = {s ∈ Z| s > 2 or s < 3}
v. W = {t ∈ Z | 1 < t < −3}
vi. X = {u ∈ Z | u ≤ 4 or u ≥ 1}
2) Let A = {c, d, f, g}, B = { f, j }, and C = {d, g}.
Answer each of the following questions. Give reasons for your answers.
a. Is B ⊆ A?
b. Is C ⊆ A?
c. Is C ⊆ C?
d. Is C a proper subset of A?
Answer:1)
i. {1,−1}
ii. {0,2}
iii. ∅ (the set has no elements)
iv. Z (every integer is in the set)
v. {2}
vi. {1, 2, 3, 4}
2)
a) No, B is not a subset of A j ∈ B and j does not ∈ A
b) Yes, Both elements of C are in A.
c) Yes, Every set is a subset of itself.
d) Yes, C is a proper subset of A. Both elements of C are
in A, but A contains elements (namely c and f ) that are
not in C.

b. Write negations for each of the following statements.

(Assume that all variables represent fixed quantities or entities, as appropriate.)
i. If P is a square, then P is a rectangle.
ii. If today is New Year’s Eve, then tomorrow is January.
iii.If n is prime, then n is odd or n is 2.
iv. If x is nonnegative, then x is positive or x is 0.
v. If n is divisible by 6, then n is divisible by 2 and n is divisible by 3.
Answer:
i) P is a square and P is not a rectangle.
ii) Today is New year Eve and tomorrow is not January.
iii) n is prime and both n is not odd and n is not 2.
 Or: n is prime and n is neither odd nor 2.
iv) X is non negative and both x is not positive and x is not zero.
v) N is divisible by 6 and both n is not divisible by 2 and not divisible by 3.

c. Determine whether the statements in (a) and (b) are logically equivalent.
1) Assume x is a particular real number.
a. x < 2 or it is not the case that 1 < x < 3. b. x ≤ 1 or either x < 2 or x ≥ 3.
2) (p ∨ q) ∨ (p ∧ r ) and (p ∨ q) ∧ r

Answer:
1. Let p be ‘x < 2’, q be ‘1 < x’, and r be ‘x < 3’. Then the sentences in (a) and
(b) are symbolized as p ∨ ∼(q ∧ r ) and ∼q ∨ (p ∨ ∼r ), respectively.
p q r ∼q ∼r q ∧ r ∼(q ∧ r) p ∨ ∼r p ∨ ∼(q ∧ r) ∼q ∨ ( p ∨ ∼r)
T T T F F T F T T T
T T F F T F T T T T
T F T T F F T T T T
T F F T T F T T T T
F T T F F T F F F F
F T F F T F T T T T
F F T T F F T F T T
F F F T T F T T T T
↑ ↑
The statement forms p ∨ ∼(q ∧ r ) and ∼q ∨ (p ∨ ∼r ) always have the same truth
values, so they are logically equivalent.
2. P q r p v q p ^ r (pvq)V (p^r) (pvq)^r
T T T T T T T
T T F T F T F
T F T T T T T
T F F T F T F
F T T T F T T
F T F T F T F
F F T F F F F
F F F F F F F
The statements (p ∨ q) ∨ (p ∧ r ) and (p ∨ q) ∧ r do not have the same truth
values, so they are logically not equivalent.

d. Let A = {a, b, c}, B = {b, c, d}, and C = {b, c, e}.

1. Find A ∪ (B ∩ C), (A ∪ B) ∩ C, and (A ∪ B) ∩ (A ∪ C). Which of these sets are
equal?
2. Find (A − B) − C and A − (B − C). Are these sets equal?
Answer:
1. A ∪ (B ∩ C) = {a, b, c}, (A ∪ B) ∩ C = {b, c}, and (A ∪ B) ∩ (A ∪ C) = {a,
b, c, d} ∩ {a, b, c, e} = {a, b, c}.
Hence A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
2. (A-B)-C = (A-B) ∩ Cc A- (B-C) = A - (B ∩ Cc)
= (A ∩B ) ∩ C
c c
= A ∩ (B ∩ Cc)c
= A ∩ (Bc ∩ Cc) = A ∩ (Bc U C)
= A ∩ (B U C) c
= (A ∩ Bc) U (A ∩ C)
= A – (B U C) = (A – B) U (A – Cc)
These sets are not equal.
e. Use an element argument to prove each statement
1. For all sets A, B, and C, (A − B) ∪ (C − B) = (A ∪ C) − B.
2. For all sets A, B, and C, (A − B) ∩ (C − B) = (A ∩ C) − B.
Answer:
1. LHS. (A − B) ∪ (C − B) = (A ∩ Bc) U (C ∩ Bc) By Set difference property
= (A U C ) ∩ Bc By Distributive Law
= (A U C) – B By Set difference property Proved.
1. LHS. (A − B) ∩ (C − B) = (A ∩ Bc) ∩ (C ∩ Bc) By Set difference property.
= (A ∩ C ) ∩ Bc By Associative Law
= (A ∩ C) – B By Set Difference property Proved.
2.
f. 1. Write a negation for each of the following statements. Indicate which is true, the
statement or its negation. Justify your answers.
a. ∀ sets S, ∃ a set T such that S ∩ T = ∅.
b. ∃ a set S such that ∀ sets T, S ∪ T = ∅.
2. Verify whether the given statement is True or False
For all sets A, B, and C, A ∩ (B − C) = (A ∩ B) − (A ∩ C).
Answer:
1. a. Statement: ∀ sets S, ∃ a set T such that S ∩ T = ∅.
Negation: ∃ a set S such that ∀ sets T, S ∩ T ≠ ∅.
The statement is true. Given any set S, take T = Sc.
Then S ∩ T = S ∩ Sc = ∅ by the complement law for ∩. Alternatively, T
could be taken to be ∅.
b. Statement: ∃ a set S such that ∀ sets T, S ∪ T = ∅.
Negation: ∀ set S such that ∃ a set T, S U T ≠ ∅.
The statement is False. As union of any two sets is never a null set.

2. (A ∩ B) − (A ∩ C) = (A ∩ B) ∩ (A ∩ C)c By Set Difference Property

= (A ∩ B) ∩ (Ac U Cc) By De Morgan’s Law
= (A ∩ B ∩ Ac) U (A ∩ B ∩ Cc) By Distributive Law
= (A ∩ Ac ∩ B) U (A ∩ B ∩ Cc) By Commutative Law
= ( ∅ ∩ B) U (A ∩ B ∩ Cc)
= ∅ U (A ∩ B ∩ Cc)
= (A ∩ B) ∩ Cc By Associative Law
= (A ∩ (B ∩ C ))
c
By associative Law
= A ∩ (B − C) By Set Difference Property
L.H.S
The given statement is true.

2. Attempt any three of the following: 15

a. A menagerie consists of seven brown dogs, two black dogs, six gray cats, ten black cats,
five blue birds, six yellow birds, and one black bird. Determine which of the following
statements are true and which are false.
a. There is an animal in the menagerie that is red.
b. Every animal in the menagerie is a bird or a mammal.
c. Every animal in the menagerie is brown or gray or black.
d. There is an animal in the menagerie that is neither a cat nor a dog.
e. No animal in the menagerie is blue.
f. There are in the menagerie a dog, a cat, and a bird that all have the same color.
Answer:
A. False
 B. True
C. False
D. True
E. False
F. True
b. Let D be the set of all students at your school, and let M(s) be “s is a math major,” let C(s)
be “s is a computer science student,” and let E(s) be “s is an engineering student.”
Express each of the following statements using quantifiers, variables, and the predicates
M(s),C(s), and E(s).
a. There is an engineering student who is a math major.
b. Every computer science student is an engineering student.
c. No computer science students are engineering students.
d. Some computer science students are also math majors.
e. Some computer science students are engineering students and some are not.
Answer:
a. ∃ s E(s) -> M(s)
b. ∀ s, C(s) -> E(s)
c. ∀ s ~C(s) -> E(s)
d. ∃ s, C(s) -> M(s)
e. ∃ s,t (C(s) -> E(s)) ^ (C(t) -> ~E(t))

c. Prove that √5 is irrational.

Answer:
Proof by contradiction: Suppose not. That is, suppose √5 is rational. By definition of
rational,

√5 = a/b for some integers a and b with b ≠ 0. Without loss of generality,

assume that a and b have no common factor. (If not, divide both a and b by their greatest
common factor to obtain integers a$ and b$ with the property that a’ and b’ have no
common factor and

√5 = a’/b’ . Then redefine

a = a’ and b = b’.) Squaring both sides of

√5 = a/b

gives 5 = a2/b2 , and multiplying both sides by b2 gives

5b2 = a2 -----(1).

Thus a2 is divisible by 5, and so, by part (b), a is also divisible by 5. By definition of

divisibility, then, a = 5k

for some integer k, and so a2 = 25k2 (2)

Substituting equation (2) into equation (1) gives 5b2 = 25k2 , and dividing both sides by 5
yields b2 = 5k2.
 Hence b2 is divisible by 5, and so, by part (b), b is also divisible by 5. Consequently, both
a and b are divisible by 5, which contradicts the assumption that a and b have no common
factor. Thus the supposition is false, and so √5 is irrational.

d. Prove that for all integers n, if n > 2 then there is a prime number p such that n < p < n!.
Answer:
Proof by Induction or Proof by Contradiction
e. Prove that for all integers n, if n2 is odd then n is odd.
Answer:
a. Proof by contradiction: Suppose not. That is, suppose there is an integer n such that n2
is odd and n is even.

Show that this supposition leads logically to a contradiction.

b. Proof by contraposition: Suppose n is any integer such that n is not odd. Show that n2 is
not odd.

f. Prove that every prime number except 2 and 3 has the form 6q + 1 or 6q + 5 for some
integer q.
Answer:
Use the quotient-remainder theorem to say that n

must have one of the forms 6q, 6q + 1, 6q + 2, 6q + 3,6q + 4, or 6q + 5 for some integer q.

Now discard 6q,6q+2,6q+3 and 6q+4 as they are not prime numbers
Proof by Induction

3. Attempt any three of the following: 15

a. Prove that n3 − n is divisible by 6, for each integer n ≥ 0.
Answer:
Prove it by Mathematical Induction
b. Prove that n3 − 7n + 3 is divisible by 3, for each integer n ≥ 0.
Answer:
Prove it by Mathematical Induction
c. Find the first four terms of each of the recursively defined sequence
Sk = Sk-1 + 2Sk−2, for all integers k ≥ 2 S0 = 1, S1 = 1

Answer : s0 = 1, s1 = 1, s2 = s1 + 2s0 = 1 + 2·1 = 3,

s3 = s2 + 2s1 = 3 + 2·1 = 5

d. Indicate whether the statements in parts (i)–(iv) are true or false. Justify your answers.
i. If two elements in the domain of a function are equal, then their images in the co-
domain are equal.
ii. If two elements in the co-domain of a function are equal, then their preimages in the
domain are also equal.
iii. A function can have the same output for more than one input.
iv. A function can have the same input for more than one output.
Answer:
 i. True. The definition of function says that for any input there is one and only one output,
so if two inputs are equal, their outputs must also be equal.

Ii. False

iii. True. The definition of function does not prohibit this occurrence.

Iv. False. Then it will not be a function.

e. Prove or give counter examples for the following

i) If f : X → Y and g: Y → Z are functions and g ◦ f is one-to-one, must g be one-
to-one?
ii) If f : X → Y and g: Y → Z are functions and g ◦ f is onto, must f be onto?
Answer:
I) No. Counterexample: Define f and g by the arrow diagrams below.

Then g ◦ f is one-to-one but g is not one-to-one. (So it is false that both f and g are one-to-
one by De Morgan’s law)

ii) Yes. Suppose f : X → Y and g: Y → Z are functions and g ◦ f is onto. Given z ∈ Z,

there is an element x in X such that (g ◦ f )(x) = z. (Why?) Let y = f (x). Then g(y) = z.

f. Prove or give counter examples for the following

1. Define g: Z → Z by the rule g(n) = 4n − 5, for all integers n.
(i) Is g one-to-one?
(ii) Is g onto?
2. Define G: R → R by the rule G(x) = 4x − 5 for all real numbers x. Is G onto?
Answer:
1. (i) g is one-to-one (ii) g is not onto

2. G is onto. Proof: Suppose y is any element of R.

[We must show that there is an element x in R such that G(x) = y. What would x be if
it exists? Scratch work shows that x would have to equal (y + 5)/4. The proof must

then show that x has the necessary properties.]

Let x = (y + 5)/4. Then (1) x ∈ R, and (2) G(x) = G((y + 5)/4) = 4[(y + 5)/4] − 5 = (y
+ 5) − 5 = y [as was to be shown].

4. Attempt any three of the following: 15

a. i) Let R = {(0, 1), (0, 2), (1, 1), (1, 3), (2, 2), (3, 0)}. Find R$, the transitive
closure of R.
ii) Let S = {(0, 0), (0, 3), (1, 0), (1, 2), (2, 0), (3, 2)}. Find St , the transitive
closure of S.
iii) Let T = {(0, 2), (1, 0), (2, 3), (3, 1)}. Find T t , the transitive closure of T .
Answer:
i) Rt = R ∪ {(0, 0), (0, 3), (1, 0), (3, 1), (3, 2), (3, 3),(0, 2), (1, 2)}
= {(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 2), (3, 0), (3, 1), (3,
2),(3, 3)}
ii) St = S U {(0,2), (1,3), (2,2),(3,0)}
 = {(0,0),(0,2), (0,3), (1,0), (1,2), ( 1,3), (2,0), (2,2), (3,0), (3,2)}
iii) Tt = T U {(0,0),(0,1),(1,2),(2,0),(2,1),(2,2),(3,0),(3,2)}
={(0,0),(0,1),(0,2),(1,0),(1,2),(2,0),(2,1),(2,2),(2,3),(3,0),(3,1),(3,2)}

b. The relation R is an equivalence relation on the set A. Find the distinct equivalence
classes of R.
i) A = {0, 1, 2, 3, 4}
R = {(0, 0), (0, 4), (1, 1), (1, 3), (2, 2), (3, 1), (3, 3),(4, 0), (4, 4)}
ii) A = {a, b, c, d}
R = {(a, a), (b, b), (b, d), (c, c), (d, b), (d, d)}
iii) A = {1, 2, 3, 4, . . . , 20}. R is defined on A as follows:
For all x, y ∈ A, x R y ⇔ 4 | (x − y).
Answer:
i) {0, 4}, {1, 3}, {2}
ii) {a}, {b,d}, {c}
iii) {1, 5, 9, 13, 17},{2, 6, 10, 14, 18},{3, 7, 11, 15, 19},{4, 8, 12, 16, 20}

c. Verify the following statements.

a. 128 ≡ 2 (mod 7) and 61 ≡ 5 (mod 7)
b. (128 + 61) ≡ (2 + 5) (mod 7)
c. (128 − 61) ≡ (2 − 5) (mod 7)
d. (128·61) ≡ (2·5) (mod 7)
e. 1282 ≡ 22 (mod 7)
Answer:
i. 128 ≡ 2 (mod 7) because 128 − 2 = 126 = 7· 18, and 61 ≡ 5 (mod 7) because 61 − 5
= 56 = 7·8
ii. 128 + 61 ≡ (2 + 5) (mod 7) because 128 + 61 = 189, 2 + 5 = 7, and 189 − 7 = 182 =
7·26
iii. 128 − 61 ≡ (2 − 5) (mod 7) because 128 − 61 = 67, 2 − 5 = −3, and 67 − (−3) = 70
= 7·10
iv. 128·61 ≡ (2·5) (mod 7) because 128·61 = 7808, 2·5 = 10, and 7808 − (10) = 7798
= 7·1114
v. 1282 ≡ 22(mod 7) because 1282 = 16384, 22 = 4, and 16384 − 4 = 16380 = 7·2340.

d. Define the following

i) Trail ii) Path iii) Circuit iv) Walk v) tree
Definitions
e. i) Draw all non isomorphic graphs with six vertices, all having degree 2.
ii) Draw four non isomorphic graphs with six vertices, two of degree 4 and four of
degree 3.
Answer:
Refer section10.4 problem 18 and 19 from Susanna

f. Draw a graph with the given specifications or explain why no such graph exists.
i) Tree, nine vertices, nine edges
ii) Graph, connected, nine vertices, nine edges
iii) Graph, circuit-free, nine vertices, six edges
iv) Tree, six vertices, total degree 14
v) Graph, circuit-free, seven vertices, four edges
Answer:
 i) Any tree with nine vertices has eight edges, not nine. Thus there is no tree with nine
vertices and nine edges.
ii) Refer figure of section 10.5 problem 9 from susanna
iii) Refer figure of section 10.5 problem 10 from susanna
iv) There is no tree with six vertices and a total degree of 14. Any tree with six
vertices has five edges and hence (by Theorem) a total degree of 10, not 14.
v) No such graph exists. By Theorem a connected graph with six vertices and five
edges is a tree. Hence such a graph cannot have a nontrivial circuit.

5. Attempt any three of the following: 15

a. How many positive three-digit integers are multiples of 6? What is the probability that
a randomly chosen positive three-digit integer is a multiple of 6? What is the
probability that a randomly chosen positive three-digit integer is a multiple of 7?
Answer:
i) The above diagram shows that there are as many positive three-digit integers that
are multiples of 6 as there are integers from 16 to 166 inclusive. By Theorem of
inclusion exclusion there are 166 − 17 + 1, or 150, such integers.

ii) There are 999 − 100 + 1 = 900 positive three-digit integers in all, and by part (i),
150 of these are multiples of 6. So the probability that a randomly chosen positive
three-digit integer is a multiple of 6 is 150/900= 1/6 = 16.667 %.

iii) There are 900 positive three digit integers out of which 142 – 15 + 1 = 128 such
integers which are multiple of 7, hence the probability that a randomly chosen positive
three-digit integer is a multiple of 7 is 128/900= 32/225 = 14.222 %.

b. The instructor of a discrete mathematics class gave two tests. Twenty-five percent of the
students received an A on the first test and 15% of the students received A’s on both tests.
What percent of the students who received A’s on the first test also received A’s on the
second test?
Answer:
60% of the students who received A’s on the first test also received A’s on second test.

c. An urn contains four balls numbered 2, 2, 5, and 6. If a person selects a set of two
balls at random, what is the expected value of the sum of the numbers on the balls?
Answer:
Let 21 and 22 denote the two balls with the number 2, and let 5 and 6 denote the other
two balls. There are 4 subsets of 2 balls that can be chosen from the urn. The
following table shows the sums of the numbers on the balls in each set and the
corresponding probabilities:
Subset Sum s Probability that the sum = s
{21, 22} 4 1/6
{21, 5}, {22, 5} 7 2/6
{21, 6} {22, 6} 8 2/6
{5, 6} 11 1/6
So the expected value is 4· 1/6 + 7· 2/6 + 8· 2/6 + 11· 1/6 = 7.5.

d. i) Given a set of 52 distinct integers, show that there must be 2 whose sum or difference is
divisible by 100.
 ii) Show that if 101 integers are chosen from 1 to 200 inclusive, there must be 2 with the
property that one is divisible by the other.
Answer:
i) Let X be the set consisting of the given 52 positive integers, and let Y be the set
containing the following elements: {00}, {50}, {01, 99}, {02, 98}, {03, 97}, . . . , {48,
52}, {49, 51}. Define a function F from X to Y by the rule F(x) = the set containing the
last two digits of x. Use the pigeonhole principle to argue that F is not one-to-one, and
show how the desired conclusion follows.

ii) Represent each of the 101 integers xi as ai2ki where ai is odd and ki ≥ 0. Now 1 ≤ xi ≤
200, and so 1 ≤ ai ≤ 199 for all i . There are only 100 odd integers from 1 to 199 inclusive.

e. a. How many distinguishable ways can the letters of the word HULLABALOO be
arranged in order?
b. How many distinguishable orderings of the letters of HULLABALOO begin with U and
end with L?
c. How many distinguishable orderings of the letters of HULLABALOO contain the two
letters HU next to each other in order?
Answer:
10!/(3!.2!.2!) = 151200
8! /(2!.2!.2!) = 5040
9!/(3!.2!.2!) = 15120

f. A pool of 10 semifinalists for a job consists of 7 men and 3 women. Because all are
considered equally qualified, the names of two of the semifinalists are drawn, one after the
other, at random, to become finalists for the job.
a. What is the probability that both finalists are women?
b. What is the probability that both finalists are men?
c. What is the probability that one finalist is a woman and the other is a man?
Answer:
I) Let W1 be the event that a woman is chosen on the first draw,
W2 be the event that a woman is chosen on the second draw,
M1 be the event that a man is chosen on the first draw,
M2 be the event that a man is chosen on the second draw.
Then P(W1) = 3/10 and P(W2 |W1) = 2/9, and thus
P(W1 ∩ W2) = P(W2 |W1)P(W1) = 2/9· 3/10 = 1/15 = 6 2/3%.

ii) Let W1 be the event that a woman is chosen on the first draw,
W2 be the event that a woman is chosen on the second draw,
M1 be the event that a man is chosen on the first draw,
M2 be the event that a man is chosen on the second draw.
Then P(M1) = 7/10 and P(M2 |M1) = 6/9, and thus
P(M1 ∩ M2) = P(M2 |M1)P(M1) = 6/9· 7/10 = 7/30 = 2 1/3%.

iii) The answer is 7/15 = 46 2/3 %.

_____________________________