National University of Computer and Emerging Sciences, Lahore Campus

Course: Discrete Structures Course Code: CS-1005

Program: BS (Software Engineering) Semester: Fall 2022
Duration: 180 Minutes Total Marks: 100
Paper Date: 15-June-22 Weight NA
Section: ALL Page(s): 21
Exam: Final Exam Roll No. Solution
• Use of calculator is allowed; however, sharing of calculator is strictly
Instruction/Notes: prohibited.
• Do NOT un-staple your exam, otherwise it might be cancelled.
• You may use rough sheets, but you must write your answers (and the
relevant working, where required) on the space provided in the answer
sheet. No credit would be given for the work done on the rough sheets.

Question 1 2 3 4 5 6 7 8 9 10 Total
Number
Total 10 10 10 10 10 10 10 10 10 10 100
Marks
Obtained
Marks

FAST School of Computing Page 1 of 21

Question 1: [2+1+2+2+3] Marks
What is the negation of each of these propositions?

The summer in Maine is hot and sunny.

The summer in Maine is either cold (or not hot) or cloudy (or not sunny).

You can get admission in University unless you have failed the entrance exam.
You passed the exam but can’t get admission in University.

Translate the given statement into propositional logic using the propositions provided.

You can upgrade your operating system only if you have a 32-bit processor running
at 1 GHz or faster, at least 1 GB RAM, and 16 GB free hard disk space, or a 64- bit
processor running at 2 GHz or faster, at least 2 GB RAM, and at least 32 GB free hard
disk space.

Express you answer in terms of

u: “You can upgrade your operating system,” b32: “You have a 32-bit
processor,” b64: “You have a 64-bit processor,” g1: “Your processor runs at 1
GHz or faster,” g2: “Your processor runs at 2 GHz or faster,” r1: “Your
processor has at least 1 GB RAM,” r2: “Your processor has at least 2 GB RAM,”
h16: “You have at least 16 GB free hard disk space,” and h32: “You have at
least 32 GB free hard disk space.”

𝑢𝑢 → (𝑏𝑏32 ∧ 𝑔𝑔1 ∧ 𝑟𝑟1 ∧ ℎ16) ∨ (𝑏𝑏64 ∧ 𝑔𝑔2 ∧ 𝑟𝑟2 ∧ ℎ32)

Express these system specifications using the propositions 𝒑𝒑 “The user enters a valid
password”, 𝒒𝒒 “Access is granted”, and 𝒓𝒓 “The user has paid the subscription fee” and
logical connectives (including negations).

“Access is granted whenever the user has paid the subscription fee and enters a
valid password.”

𝑝𝑝 ∧ 𝑟𝑟 → 𝑞𝑞

FAST School of Computing Page 2 of 21

 “If the user has not entered a valid password but has paid the subscription fee,
then access is granted.”

¬𝑝𝑝 ∧ 𝑟𝑟 → 𝑞𝑞

Write each of these statements in the form “if p, then q” in English.

It is necessary to walk 8 miles to get to the top of Long’s Peak.

If one gets to the top of Long’s Peak, then one has walked 8 miles.

Your guarantee is good only if you bought your CD player less than 90 days ago.

If your guarantee is good, then you bought your CD player less than 90 days ago.

Show that ￢𝒑𝒑 → (𝒒𝒒 → 𝒓𝒓) and 𝒒𝒒 → (𝒑𝒑 ∨ 𝒓𝒓) are logically equivalent by developing a
series of logical equivalences.

Note: You can establish the above equivalence using truth table to get 50% marks.

¬𝒑𝒑 → (𝒒𝒒 → 𝒓𝒓) ≡ �¬(¬𝑝𝑝) ∨ (𝑞𝑞 → 𝑟𝑟)� ≡ 𝑝𝑝 ∨ (¬𝑞𝑞 ∨ 𝑟𝑟) ≡ 𝒑𝒑 ∨ ¬𝒒𝒒 ∨ 𝒓𝒓 (1)

𝒒𝒒 → (𝒑𝒑 ∨ 𝒓𝒓) ≡ �¬𝑞𝑞 ∨ (𝑝𝑝 ∨ 𝑟𝑟)� ≡ ¬𝑞𝑞 ∨ 𝑝𝑝 ∨ 𝑟𝑟 ≡ 𝒑𝒑 ∨ ¬𝒒𝒒 ∨ 𝒓𝒓 (2)

From (1) and (2) above, the equivalence is established.

FAST School of Computing Page 3 of 21

Question 2: [2+3+1+2+2] Marks
Let 𝑪𝑪(𝒙𝒙) be the statement “𝑥𝑥 has a cat”, let 𝑫𝑫(𝒙𝒙) be the statement “𝑥𝑥 has a dog”, and let
𝑭𝑭(𝒙𝒙) be the statement “𝑥𝑥 has a ferret”. Express each of these statements in terms of
𝐶𝐶(𝑥𝑥), 𝐷𝐷(𝑥𝑥), 𝐹𝐹(𝑥𝑥), quantifiers, and logical connectives. Let the domain consist of all
students in your class.
No student in your class has a cat, a dog, and a ferret.
¬∃𝑥𝑥�𝐶𝐶(𝑥𝑥) ∧ 𝐷𝐷(𝑥𝑥) ∧ 𝐹𝐹(𝑥𝑥)� ≡ ∀𝑥𝑥�¬𝐶𝐶(𝑥𝑥) ∨ ¬𝐷𝐷(𝑥𝑥) ∨ ¬𝐹𝐹(𝑥𝑥)�

For each of the three animals, cats, dogs, and ferrets, there is a student in your class
who has this animal as a pet.
∃𝑥𝑥𝑥𝑥(𝑥𝑥) ∧ ∃𝑥𝑥𝑥𝑥(𝑥𝑥) ∧ ∃𝑥𝑥𝑥𝑥(𝑥𝑥)

Let 𝑷𝑷(𝒙𝒙) be the predicate “𝑥𝑥 is a predator,” 𝑸𝑸(𝒙𝒙) be the predicate “𝑥𝑥 is a prey,” and
𝑹𝑹(𝒙𝒙, 𝒚𝒚) be the predicate “𝑥𝑥 has killed 𝑦𝑦,” where the domain consists of all animals in a
jungle. Use quantifiers to express each of these statements.
Some predator has not killed any prey.
∃𝑥𝑥(𝑃𝑃(𝑥𝑥) ∧ ∀𝑦𝑦(𝑄𝑄(𝑦𝑦) → ¬𝑅𝑅(𝑥𝑥, 𝑦𝑦)))

There is a prey who has never been killed by a predator.

∃𝑦𝑦(𝑄𝑄(𝑦𝑦) ∧ ∀𝑥𝑥(𝑃𝑃(𝑥𝑥) → ¬𝑅𝑅(𝑥𝑥, 𝑦𝑦)))

Some predator has killed every prey.

∃𝑥𝑥(𝑃𝑃(𝑥𝑥) ∧ ∀𝑦𝑦(𝑄𝑄(𝑦𝑦) → 𝑅𝑅(𝑥𝑥, 𝑦𝑦)))
∀𝑦𝑦(𝑄𝑄(𝑦𝑦) → ∃𝑥𝑥(𝑃𝑃(𝑥𝑥) ∧ 𝑅𝑅(𝑥𝑥, 𝑦𝑦)))
Express the negation of the statement ∀𝑥𝑥∃𝑦𝑦(𝑥𝑥𝑥𝑥 = 1) so that no negation precedes a
quantifier.
¬(∀𝑥𝑥∃𝑦𝑦(𝑥𝑥𝑥𝑥 = 1)) ≡ ∃𝑥𝑥¬∃𝑦𝑦(𝑥𝑥𝑥𝑥 = 1) ≡ ∃𝑥𝑥∀𝑦𝑦¬(𝑥𝑥𝑥𝑥 = 1) ≡ ∃𝑥𝑥∀𝑦𝑦(𝑥𝑥𝑥𝑥 ≠ 1)

FAST School of Computing Page 4 of 21

Express each of these mathematical statements using predicates, quantifiers, logical
connectives, and mathematical operators (the domain consists of all real numbers).
Every positive real number has exactly two square roots.
∀𝑥𝑥(𝑥𝑥 > 0 → (∃𝑎𝑎∃𝑏𝑏(𝑎𝑎 ≠ 𝑏𝑏 ∧ ∀𝑐𝑐(𝑐𝑐 2 = 𝑥𝑥 ↔ 𝑐𝑐 = 𝑎𝑎 ∨ 𝑐𝑐 = 𝑏𝑏))))

A negative real number does not have a square root that is a real number.
∀𝑥𝑥(𝑥𝑥 < 0 → ¬∃𝑦𝑦(𝑦𝑦 2 = 𝑥𝑥))

Determine the truth value of each of these statements if the domain of each variable
consists of all real numbers.

∀𝑥𝑥∃𝑦𝑦(𝑥𝑥 2 = 𝑦𝑦) True / False

∀𝑥𝑥∃𝑦𝑦(𝑥𝑥 = 𝑦𝑦 2 ) True / False

FAST School of Computing Page 5 of 21

Question 3: [4+6] Marks
Use rules of inference to show that the hypotheses “If I do not work hard or if I am not
lucky, then I will perform poor and I will get bad grade,” “If I will get bad grade, then I will
get a warning,” and “I did not get warning” imply the conclusion “I worked hard.”

Use the following propositional variables in your argument:

𝒑𝒑: = I work hard, 𝒒𝒒: = I am lucky, 𝒓𝒓: = I will perform poor,
𝒔𝒔: = I will get bad grade, 𝒕𝒕: = I will get a warning

1 (¬𝑝𝑝 ∨ ¬𝑞𝑞) → (𝑟𝑟 ∧ 𝑠𝑠) Premise

2 (¬𝑝𝑝 ∨ ¬𝑞𝑞) → 𝑠𝑠 Simplification using (1)
3 𝑠𝑠 → 𝑡𝑡 Premise
4 ¬𝑡𝑡 Premise
5 ¬𝑠𝑠 Modus Tollens using (3) & (4)
6 ¬(¬𝑝𝑝 ∨ ¬𝑞𝑞) Modus Tollens using (2) & (5)
7 ¬¬𝑝𝑝 ∧ ¬¬𝑞𝑞 Application of De Morgan’s Law on (6)
8 𝑝𝑝 ∧ 𝑞𝑞 Application of Double negation Law on (7)
9 𝑝𝑝 Simplification using (8)

We can break down Step 2 further as following:

(¬𝑝𝑝 ∨ ¬𝑞𝑞) → (𝑟𝑟 ∧ 𝑠𝑠) ≡ �(¬𝑝𝑝 ∨ ¬𝑞𝑞) → 𝑟𝑟� ∧ �(¬𝑝𝑝 ∨ ¬𝑞𝑞) → 𝑠𝑠�
and then apply simplification on the R.H.S of the above equivalence resulting in
(¬𝑝𝑝 ∨ ¬𝑞𝑞) → 𝑠𝑠

FAST School of Computing Page 6 of 21

What rule of inference is used in each of these arguments?
Note: Just mention the rule; you are not required to show any working.

1. Kangaroos live in Australia and are marsupials. Therefore, kangaroos are marsupials.

Simplification

2. Linda is an excellent swimmer. If Linda is an excellent swimmer, then she can work
as a lifeguard. Therefore, Linda can work as a lifeguard.

Modus ponens

3. It is either hotter than 100 degrees today or the pollution is dangerous. It is less
than 100 degrees outside today. Therefore, the pollution is dangerous.
Disjunctive syllogism

4. A convertible car is fun to drive. Isaac’s car is convertible. Therefore, Isaac’s car is
fun to drive.

Universal Modus ponens

5. Quincy likes only action movies. Quincy likes the movie Eight Men Out. Therefore,
Eight Men Out is an action movie.

Universal Modus ponens

6. Everyone who eats granola every day is healthy. Linda is not healthy. Therefore,
Linda does not eat granola every day.

Universal Modus tollens

FAST School of Computing Page 7 of 21

Question 4: [4+4+2] Marks
Prove the distributive law 𝑨𝑨 ∩ (𝑩𝑩 ∪ 𝑪𝑪) = (𝑨𝑨 ∩ 𝑩𝑩) ∪ (𝑨𝑨 ∩ 𝑪𝑪) without using membership
table.
Note: You can prove the above mentioned Law using membership table to get 50% marks.

𝑨𝑨 ∩ (𝑩𝑩 ∪ 𝑪𝑪) = {𝑥𝑥|𝑥𝑥 ∈ 𝐴𝐴 ∧ (𝑥𝑥 ∈ 𝐵𝐵 ∪ 𝐶𝐶)}

= {𝑥𝑥|𝑥𝑥 ∈ 𝐴𝐴 ∧ (𝑥𝑥 ∈ 𝐵𝐵 ∨ 𝑥𝑥 ∈ 𝐶𝐶)}
= {𝑥𝑥|(𝑥𝑥 ∈ 𝐴𝐴 ∧ 𝑥𝑥 ∈ 𝐵𝐵) ∨ (𝑥𝑥 ∈ 𝐴𝐴 ∧ 𝑥𝑥 ∈ 𝐶𝐶)}
= {𝑥𝑥|𝑥𝑥 ∈ 𝐴𝐴 ∩ 𝐵𝐵 ∨ 𝑥𝑥 ∈ 𝐴𝐴 ∩ 𝐶𝐶}
= �𝑥𝑥�𝑥𝑥 ∈ �(𝐴𝐴 ∩ 𝐵𝐵) ∪ (𝐴𝐴 ∩ 𝐶𝐶)��
= (𝑨𝑨 ∩ 𝑩𝑩) ∪ (𝑨𝑨 ∩ 𝑪𝑪)
Note that besides the definitions of union, intersection, set membership, and set
builder notation, this proof uses the distributive law for conjunction over disjunction
for logical equivalences.

FAST School of Computing Page 8 of 21

Find 𝒇𝒇 ∘ 𝒈𝒈 and 𝒈𝒈 ∘ 𝒇𝒇 , where 𝒇𝒇(𝒙𝒙) = 𝒙𝒙𝟑𝟑 + 𝟏𝟏 and 𝒈𝒈(𝒙𝒙) = 𝒙𝒙𝟐𝟐 + 𝟐𝟐, are functions from R
to R.

(𝒇𝒇 ∘ 𝒈𝒈)(𝒙𝒙) = 𝑓𝑓�𝑔𝑔(𝑥𝑥)� = 𝑓𝑓(𝑥𝑥 2 + 2) = (𝑥𝑥 2 + 2)3 + 1 = 𝒙𝒙𝟔𝟔 + 𝟔𝟔𝒙𝒙𝟒𝟒 + 𝟏𝟏𝟏𝟏𝒙𝒙𝟐𝟐 + 𝟗𝟗

(𝒈𝒈 ∘ 𝒇𝒇)(𝒙𝒙) = 𝑔𝑔�𝑓𝑓(𝑥𝑥)� = 𝑔𝑔(𝑥𝑥 3 + 1) = (𝑥𝑥 3 + 1)2 + 2 = 𝒙𝒙𝟔𝟔 + 𝟐𝟐𝒙𝒙𝟑𝟑 + 𝟑𝟑

Determine whether the function 𝑓𝑓:z × z → z is bijective if 𝑓𝑓(𝑚𝑚, 𝑛𝑛) = 𝑚𝑚 + 𝑛𝑛.

It’s not; e.g. 7 has more than one pre-images, (5,2), (4,3) etc.

FAST School of Computing Page 9 of 21

Question 5: [3+2+(1+2)+2] Marks
List the first 5 terms of each of these sequences.
The sequence whose 𝑛𝑛th term is the sum of the first 𝑛𝑛 positive integers

𝑎𝑎1 = 1, 𝑎𝑎2 = 3, 𝑎𝑎3 = 6, 𝑎𝑎4 = 10, 𝑎𝑎5 = 15

The sequence whose 𝑛𝑛th term is 𝑛𝑛! − 2𝑛𝑛

𝑎𝑎1 = −1, 𝑎𝑎2 = −2, 𝑎𝑎3 = −2, 𝑎𝑎4 = 8, 𝑎𝑎5 = 88

The sequence whose 𝑛𝑛th term is the largest integer whose binary expansion has 𝑛𝑛
bits (Write your answer in decimal notation.)

𝑎𝑎1 = 1, 𝑎𝑎2 = 3, 𝑎𝑎3 = 7, 𝑎𝑎4 = 15, 𝑎𝑎5 = 31

Using an iterative approach, find the solution to the following recurrence relation and
initial condition:

𝑎𝑎𝑛𝑛 = 𝑛𝑛𝑎𝑎𝑛𝑛−1 , 𝑎𝑎0 = 5

𝑎𝑎1 = 1 ⋅ 5 = 5
𝑎𝑎2 = 2 ⋅ (1 ⋅ 5) = (2 ⋅ 1) ⋅ 5
𝑎𝑎3 = 3 ⋅ �(2 ⋅ 1) ⋅ 5� = (3 ⋅ 2 ⋅ 1) ⋅ 5
⋮
𝑎𝑎𝑛𝑛 = (𝑛𝑛 ⋅ 𝑛𝑛 − 1 ⋅ … ⋅ 1) ⋅ 5 = 𝑛𝑛! ⋅ 5 = 5(𝑛𝑛!)

FAST School of Computing Page 10 of 21

A person deposits $1000 in an account that yields 9% interest compounded annually.

Set up a recurrence relation for the amount in the account at the end of 𝑛𝑛 years.

𝑃𝑃𝑛𝑛 = 𝑃𝑃𝑛𝑛−1 + 0.09𝑃𝑃𝑛𝑛−1 = 1.09𝑃𝑃𝑛𝑛−1

Find an explicit formula for the amount in the account at the end of 𝑛𝑛 years.

𝑃𝑃0 = 1000
𝑃𝑃1 = (1.09)𝑃𝑃0
𝑃𝑃2 = (1.09)𝑃𝑃1 = (1.09)2 𝑃𝑃0
𝑃𝑃3 = (1.09)𝑃𝑃2 = (1.09)3 𝑃𝑃0
⋮
𝑃𝑃𝑛𝑛 = (1.09)𝑃𝑃𝑛𝑛−1 = (1.09)𝑛𝑛 𝑃𝑃0

What is the value of the following sum?

100 100

��5
𝑖𝑖=1 𝑗𝑗=𝑖𝑖

100 100 100 100 100

5 ⋅ 100 ⋅ 101
� � 5 = 5 � � 1 = 5 �(100 − 𝑖𝑖 + 1) = 5(100 + 99 + ⋯ + 1) =
2
𝑖𝑖=1 𝑗𝑗=𝑖𝑖 𝑖𝑖=1 𝑗𝑗=𝑖𝑖 𝑖𝑖=1

= 𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐

FAST School of Computing Page 11 of 21

Question 6: [5+5] Marks
Prove that if 𝑚𝑚 + 𝑛𝑛 and 𝑛𝑛 + 𝑝𝑝 are even integers, where 𝑚𝑚, 𝑛𝑛, and 𝑝𝑝 are integers, then
𝑚𝑚 + 𝑝𝑝 is even.

Suppose that m+n and n+p are even. Then m+n = 2s for some integer s and n+p = 2t for
some integer t. If we add these, we get m+p+2n = 2s +2t .

Subtracting 2n from both sides and factoring, we have m+p = 2s+2t − 2n = 2(s + t − n).
Because we have written m + p as 2 times an integer, we conclude that m + p is even.

FAST School of Computing Page 12 of 21

Prove that √3 is irrational by giving a proof by contradiction. You may use lemma 1 in your
proof where needed.
Lemma 1: If 𝑛𝑛2 is a multiple of 3 then 𝑛𝑛 is also a multiple of 3.

Letp be the proposition “√3 is irrational.” To start a proof by contradiction, we suppose

that ￢p is true. Note that ￢p is the statement “It is not the case that √3 is irrational,”
which says that √3 is rational. We will show that assuming that ￢p is true leads to a
contradiction.
If √3 is rational, there exist integers 𝑎𝑎 and 𝑏𝑏 with √3 = 𝑎𝑎/𝑏𝑏, where 𝑏𝑏 ≠ 0 and 𝑎𝑎 and 𝑏𝑏
have no common factors (so that the fraction 𝑎𝑎/𝑏𝑏 is in lowest terms.) Because √3 = 𝑎𝑎/𝑏𝑏,
when both sides of this equation are squared, it follows that
𝑎𝑎2
3 = 2 ⇒ 3𝑏𝑏 2 = 𝑎𝑎2
𝑏𝑏
2
Hence, 𝑎𝑎 is a multiple of 3. Using the Lemma 1, it follows that 𝑎𝑎 must also be a multiple
of 3. Now, if 𝑎𝑎 is a multiple of 3 then 𝑎𝑎 can be written as 3𝑐𝑐 (where 𝑐𝑐 is an integer). Thus
3𝑏𝑏 2 = 9𝑐𝑐 2
Dividing both sides of this equation by 3 gives
𝑏𝑏 2 = 3𝑐𝑐 2
Hence, 𝑏𝑏 2 is a multiple of 3. Once again, using the Lemma 1, it follows that 𝑏𝑏 must also be
a multiple of 3.
We have now shown that the assumption of ￢p leads to the equation √3 = 𝑎𝑎/𝑏𝑏, where
𝑎𝑎 and 𝑏𝑏 have no common factors, but both 𝑎𝑎 and 𝑏𝑏 are multiple of 3, that is, 3 divides both
𝑎𝑎 and 𝑏𝑏. Note that the statement that √3 = 𝑎𝑎/𝑏𝑏, where 𝑎𝑎 and 𝑏𝑏 have no common factors,
means, in particular, that 3 does not divide both 𝑎𝑎 and 𝑏𝑏. Because our assumption of ￢p
leads to the contradiction that 3 divides both 𝑎𝑎 and 𝑏𝑏 and 3 does not divide both 𝑎𝑎 and 𝑏𝑏,
￢p must be false. That is, the statement p, “√3 is irrational,” is true. We have proved that
√3 is irrational.

FAST School of Computing Page 13 of 21

Question 7: [5+5] Marks
An odd number of people stand in a yard at mutually distinct distances. At the same time
each person throws a pie at their nearest neighbor, hitting this person. Use mathematical
induction to show that there is at least one survivor, that is, at least one person who is not
hit by a pie.

FAST School of Computing Page 14 of 21

Use mathematical induction to prove that

12 + 32 + 52 +· · · +(2𝑛𝑛 + 1)2 = (𝑛𝑛 + 1)(2𝑛𝑛 + 1)(2𝑛𝑛 + 3)/3

whenever 𝑛𝑛 is a nonnegative integer.

Basis step:

𝑃𝑃(0) is true because

12 = 1 = (0 + 1)(2 ⋅ 0 + 1)(2 ⋅ 0 + 3)/3.

Inductive step:

Assume that 𝑃𝑃(𝑘𝑘) is true. Then

(𝑘𝑘 + 1)(2𝑘𝑘 + 1)(2𝑘𝑘 + 3)
12 + 32 + ⋯ + (2𝑘𝑘 + 1)2 + [2(𝑘𝑘 + 1) + 1]2 = + (2𝑘𝑘 + 3)2
3
(𝑘𝑘 + 1)(2𝑘𝑘 + 1)
= (2𝑘𝑘 + 3) � + (2𝑘𝑘 + 3)�
3
(2𝑘𝑘 + 3)(2𝑘𝑘 2 + 9𝑘𝑘 + 10)
=
3
(2𝑘𝑘 + 3)(2𝑘𝑘 + 5)(𝑘𝑘 + 2)
=
3
[(𝑘𝑘 + 1) + 1][2(𝑘𝑘 + 1) + 1][2(𝑘𝑘 + 1) + 3]
=
3

FAST School of Computing Page 15 of 21

Question 8: [3+4+3] Marks
Find the error in the “proof” of the following “theorem.”
“Theorem”: Let 𝑅𝑅 be a relation on a set 𝐴𝐴 that is symmetric and transitive. Then 𝑅𝑅 is
reflexive.
“Proof ”: Let 𝑎𝑎 ∈ 𝐴𝐴. Take an element 𝑏𝑏 ∈ 𝐴𝐴 such that (𝑎𝑎, 𝑏𝑏) ∈ 𝑅𝑅. Because 𝑅𝑅 is
symmetric, we also have (𝑏𝑏, 𝑎𝑎) ∈ 𝑅𝑅. Now using the transitive property, we can
conclude that (𝑎𝑎, 𝑎𝑎) ∈ 𝑅𝑅 because (𝑎𝑎, 𝑏𝑏) ∈ 𝑅𝑅 and (𝑏𝑏, 𝑎𝑎) ∈ 𝑅𝑅.

If no such 𝑏𝑏 ∈ 𝐴𝐴 exists such that (𝑎𝑎, 𝑏𝑏) ∈ 𝑅𝑅, then the proof would collapse.

Which of these relations on {0, 1, 2, 3} are equivalence relations? Determine the properties
of an equivalence relation that the others lack.
{(0, 0), (1, 1), (2, 2), (3, 3)}
Equivalence Relation

{(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}
Not Reflexive [(1,1) is missing]; Not Transitive [(0,2) and (2,3) are in the relation but
(0,3) is missing].
{(0, 0), (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}
Not Transitive [(1,3) and (3,2) are in the relation but (1,2) is missing; moreover, (2,3)
and (3,1) are in the relation but (2,1) is missing]
{(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}
Equivalence Relation

Let 𝑅𝑅 and 𝑆𝑆 be relations on a set 𝐴𝐴 represented by the matrices

FAST School of Computing Page 16 of 21
 0 1 0 0 1 0
𝑀𝑀𝑅𝑅 = �1 1 1� , 𝑀𝑀𝑆𝑆 = �0 1 1�
1 0 0 1 1 1

Find the matrix representing 𝑅𝑅 ∘ 𝑆𝑆

1 1 1
𝑀𝑀𝑅𝑅∘𝑆𝑆 = 𝑀𝑀𝑆𝑆 ⊙ 𝑀𝑀𝑅𝑅 = �1 1 1�
1 1 1

FAST School of Computing Page 17 of 21

Question 9: [2+3+1.5+1.5+1+1] Marks
A multiple-choice test contains 10 questions. There are four possible answers for each
question.

In how many ways can a student answer the questions on the test if the student
answers every question?

410
In how many ways can a student answer the questions on the test if the student can
leave answers blank?

510
How many bit strings of length seven either begin with two 0s or end with three 1s?

25 + 24 − 22 = 32 + 16 − 4 = 𝟒𝟒𝟒𝟒

What is the minimum number of students, each of whom comes from one of the 37 states,
who must be enrolled in a university to guarantee that there are at least 55 who come from
the same state?
𝑥𝑥
min �� � = 55� ⇒ 𝑥𝑥 = 𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏
𝑥𝑥 37

There are 38 different time periods during which classes at a university can be scheduled.
If there are 677 different classes, how many different rooms will be needed?

𝟏𝟏𝟏𝟏

FAST School of Computing Page 18 of 21

A group contains 𝑛𝑛 men and 𝑛𝑛 women. How many ways are there to arrange these people
in a row if the men and women alternate and the last person in the row is always a man?

(𝒏𝒏!)𝟐𝟐

What is the coefficient of 𝑥𝑥 12 𝑦𝑦 9 in the expansion of (3𝑥𝑥 2 − 2𝑦𝑦)15 ?

15
� � (3𝑥𝑥 2 )6 (−2𝑦𝑦)9 = 5005 ⋅ 729𝑥𝑥 12 (−512𝑦𝑦 9 ) = −𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝑥𝑥 12 𝑦𝑦 9
6

FAST School of Computing Page 19 of 21

Question 10: [1+2+1.5+1.5+4] Marks
Can a simple graph exist with 15 vertices each of degree five? Justify your answer with
proper reasoning.

Show that in a simple graph with at least two vertices there must be two vertices that have
the same degree.

For which values of 𝑛𝑛 are these graphs bipartite?

𝐾𝐾𝑛𝑛

𝐶𝐶𝑛𝑛

𝑊𝑊𝑛𝑛

FAST School of Computing Page 20 of 21

For the graph given below find the subgraph induced by the vertices a, b, c, and f .

Draw your graph here:

Determine whether the given pairs of graphs are isomorphic. Exhibit an isomorphism or
provide a rigorous argument that none exists.
Answer:

Answer:

FAST School of Computing Page 21 of 21