Anna University, Chennai, November/December 2012

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2012

Fifth Semester
Computer Science and Engineering
MA2265 – DISCRETE MATHEMATICS
(Regulation 2008)

Part - A
1. Define Tautology with an example.
Solution:
A Statement that is true for all possible values of its propositional variables is called a tautology.
(𝑃⋁𝑄) ↔ (𝑄⋁𝑃) is a tautology.

2. Define a rule of universal specification.

Answer:
From (𝑥) 𝐴(𝑥) one can conclude 𝐴(𝑦). If (𝑥) 𝐴(𝑥) is true for every element 𝑥 in the universe, then
𝐴(𝑦) is true.
𝑥 𝐴 𝑥 ⇒ 𝐴(𝑦)

3. State pigeonhole principle.

Solution:
If 𝑘 pigeons are assigned to 𝑛 pigeonholes and 𝑛 < 𝑘 then there is at least one pigeonhole containing
more than one pigeons.

4. Solve 𝒂𝒌 = 𝟑𝒂𝒌−𝟏 , 𝐟𝐨𝐫 𝒌 ≥ 𝟏, 𝐰𝐢𝐭𝐡 𝒂𝟎 = 𝟐.

Solution:
∞

𝐿𝑒𝑡 𝐺 𝑥 = 𝑎𝑘 𝑥 𝑘 = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ … 1
𝑘=0
where 𝐺 𝑥 is the generating function for the sequence 𝑎𝑛 .
Given 𝑎𝑘 = 3𝑎𝑘−1 ⇒ 3𝑎𝑘−1 − 𝑎𝑘 = 0
Multiplying by 𝑥𝑘 and summing from 1 to ∞, we have
∞ ∞
𝑘
3 𝑎𝑘−1 𝑥 − 𝑎𝑘 𝑥 𝑘 = 0
𝑘=1 𝑘=1
∞ ∞

3𝑥 𝑎𝑘−1 𝑥 𝑘 −1 − 𝑎𝑘 𝑥 𝑘 = 0
𝑘=1 𝑘=1
3𝑥 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ − 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ = 0
3𝑥𝐺 𝑥 − 𝐺 𝑥 − 𝑎0 = 0 [𝑓𝑟𝑜𝑚 1 ]
𝐺 𝑥 3𝑥 − 1 − 2 = 0
2 2
𝐺 𝑥 = =−
(3𝑥 − 1) 1 − 3𝑥

∞ ∞ ∞
𝑘 𝑘 𝑘
1
𝑎𝑘 𝑥 = −2 3 𝑥 ∵ = 𝑥𝑛
1−𝑥
𝑘=0 𝑘=0 𝑛=0
𝑎𝑘 = Coefficient of 𝑥 𝑘 in 𝐺(𝑥)

www.tranquileducation.weely.com 1
 Anna University, Chennai, November/December 2012

𝑎𝑘 = −2 3𝑛

5. Define a regular graph. Can a complete graph be a regular graph?

Ans: A graph is said to be regular if all the vertices are of same degree.
Yes a complete graph is always a regular graph.

6. State the handshaking theorem.

Solution:
If 𝐺 𝑉, 𝐸 is an undirected graph with e edges, then
deg 𝑣𝑖 = 2𝑒.
𝑖

7. Prove that the identity of a subgroup is the same as that of the group.
Solution:
Let 𝑒1 be the identity element of a group 𝐺 and 𝐻 be the subgroup of 𝐺.
Let us assume that 𝑒2 ≠ 𝑒1 be the identity element of 𝐻.
Since 𝐻 ⊆ 𝐺, 𝑒2 ∈ 𝐺 which is a contradiction since in a group, identity element is unique.
∴Our assumption is wrong.
∴ 𝑒1 = 𝑒2 .

8. State Lagrange’s theorem in 𝜹 group theory.

Solution:
An order of a subgroup 𝐻 of a group 𝐺 divides the order of the group 𝐺.

9. When is a lattice said to be bounded?

Solution:
A lattice having least and greatest element is called a bounded lattice.

10. When is a lattice said to be a Boolean Algebra?

Solution:
A complemented distributive lattice is called a Boolean Algebra.

Part - B
11. a)i) Show that 𝐏 ∨ 𝐐 ∧ 𝐑 and 𝐏 ∨ 𝐐 ∧ 𝐏 ∨ 𝐑 are logically equivalent.
Solution:
To prove: 𝑆: P ∨ Q ∧ R ↔ P ∨ Q ∧ P ∨ R is a tautology.
𝐏 𝑸 𝑹 𝐐∧𝐑 𝐏∨ 𝐐∧𝐑 𝐏∨𝐐 𝐏∨𝐑 𝐏∨𝐐 ∧ 𝐏∨𝐑 𝑺
T T T T T T T T T
T F T F T T T T T
F T T T T T T T T
F F T F F F T F T
T T F F T T T T T
T F F F T T T T T
F T F F F T F F T
F F F F F F F F T

www.tranquileducation.weely.com 2
 Anna University, Chennai, November/December 2012

Since all the values in last column are true. P ∨ Q ∧ R ↔ P∨Q ∧ P∨R is a tautology.
∴ P∨ Q∧R ⇔ P∨Q ∧ P∨R

ii) Show that the hypothesis, “It is not sunny this afternoon and it is colder than yesterday”, “we will
go swimming only if it is sunny”, “If we do not go swimming, then we will take a canoe trip” and “If we
take a canoe trip, then we will be home by sunset” lead to the conclusion “We will be home by
sunset”.
Solution:
Let 𝑆 represents it is sunny this afternoon.
Let 𝐶 represents it is colder than yesterday.
Let 𝑊 represents we will go swimming.
Let 𝑇𝑟 represents we will take a canoe trip.
Let 𝐻 represents we will be home by sunset.
The inference is ∼ 𝑆 ∧ 𝐶, 𝑊 → 𝑆, ∼ 𝑊 → 𝑇𝑟 , 𝑇𝑟 → 𝐻 ⇒ 𝐻
1. ∼ 𝑆 ∧ 𝐶 𝑅𝑢𝑙𝑒 𝑃
2. 𝑊 → 𝑆 𝑅𝑢𝑙𝑒 𝑃
3. ∼ 𝑊 → 𝑇𝑟 𝑅𝑢𝑙𝑒 𝑃
4. 𝑇𝑟 → 𝐻 𝑅𝑢𝑙𝑒 𝑃
5. ∼ 𝑆 𝑅𝑢𝑙𝑒 𝑇, 1, 𝑃 ∧ 𝑄 ⇒ 𝑃
6. ∼ 𝑊 𝑅𝑢𝑙𝑒 𝑇, 5,2, 𝑀𝑜𝑑𝑢𝑠 𝑡𝑜𝑙𝑙𝑒𝑛𝑠
7. 𝑇𝑟 𝑅𝑢𝑙𝑒 𝑇, 6,3, 𝑀𝑜𝑑𝑢𝑠 𝑝𝑕𝑜𝑛𝑒𝑠
8. 𝐻 𝑅𝑢𝑙𝑒 𝑇, 7,4, 𝑀𝑜𝑑𝑢𝑠 𝑝𝑕𝑜𝑛𝑒𝑠

b) i) Find the principal disjunctive normal form of the statement 𝒒 ∨ 𝒑 ∧ 𝒓 ∧∼ 𝒑 ∨ 𝒓 ∧ 𝒒 .

Solution:
Let S ⇔ 𝑞 ∨ 𝑝 ∧ 𝑟 ∧∼ 𝑝 ∨ 𝑟 ∧ 𝑞 .
⇔ 𝑞 ∨ 𝑝 ∧ 𝑟 ∧ ∼ 𝑝 ∨ 𝑟 ∨∼ 𝑞
⇔ 𝑞 ∨ 𝑝 ∧ 𝑟 ∧ ∼ 𝑝 ∧∼ 𝑟 ∨∼ 𝑞
⇔ 𝑞 ∨ 𝑝 ∧ 𝑞 ∨ 𝑟 ∧ ∼ 𝑝 ∨∼ 𝑞 ∧ ∼ 𝑟 ∨∼ 𝑞
⇔ 𝑞 ∨ 𝑝 ∨ 𝐹 ∧ 𝐹 ∨ 𝑞 ∨ 𝑟 ∧ ∼ 𝑝 ∨∼ 𝑞 ∨ 𝐹 ∧ 𝐹 ∨∼ 𝑟 ∨∼ 𝑞
⇔ 𝑞 ∨ 𝑝 ∨ 𝑟 ∧∼ 𝑟 ∧ 𝑝 ∧∼ 𝑝 ∨ 𝑞 ∨ 𝑟 ∧ ∼ 𝑝 ∨∼ 𝑞 ∨ 𝑟 ∧∼ 𝑟 ∧ 𝑝 ∧∼ 𝑝 ∨∼ 𝑟 ∨∼ 𝑞
⇔ 𝑞 ∨ 𝑝 ∨ 𝑟 ∧ 𝑞 ∨ 𝑝 ∨∼ 𝑟 ∧ 𝑝 ∨ 𝑞 ∨ 𝑟 ∧ ∼ 𝑝 ∨ 𝑞 ∨ 𝑟 ∧ ∼ 𝑝 ∨∼ 𝑞 ∨ 𝑟
∧ ∼ 𝑝 ∨∼ 𝑞 ∨∼ 𝑟 ∧ 𝑝 ∨∼ 𝑟 ∨∼ 𝑞 ∧ ∼ 𝑝 ∨∼ 𝑟 ∨∼ 𝑞
⇔ 𝑞 ∨ 𝑝 ∨∼ 𝑟 ∧ 𝑝 ∨ 𝑞 ∨ 𝑟 ∧ ∼ 𝑝 ∨ 𝑞 ∨ 𝑟 ∧ ∼ 𝑝 ∨∼ 𝑞 ∨ 𝑟
∧ ∼ 𝑝 ∨∼ 𝑞 ∨∼ 𝑟 ∧ 𝑝 ∨∼ 𝑟 ∨∼ 𝑞
⇔ 𝑝 ∨ 𝑞 ∨∼ 𝑟 ∧ 𝑝 ∨ 𝑞 ∨ 𝑟 ∧ ∼ 𝑝 ∨ 𝑞 ∨ 𝑟 ∧ ∼ 𝑝 ∨∼ 𝑞 ∨ 𝑟
∧ ∼ 𝑝 ∨∼ 𝑞 ∨∼ 𝑟 ∧ 𝑝 ∨∼ 𝑞 ∨∼ 𝑟 𝑤𝑕𝑖𝑐𝑕 𝑖𝑠 𝑎 𝑃𝐶𝑁𝐹
∼ 𝑆 ⇔ 𝑟𝑒𝑚𝑎𝑖𝑛𝑖𝑛𝑔 𝑚𝑎𝑥 𝑡𝑒𝑟𝑚𝑠 𝑖𝑛 𝑆
∼ 𝑆 ⇔ 𝑝 ∨∼ 𝑞 ∨ 𝑟 ∧ ∼ 𝑝 ∨ 𝑞 ∨∼ 𝑟
∼∼ 𝑆 ⇔∼ 𝑝 ∨∼ 𝑞 ∨ 𝑟 ∧ ∼ 𝑝 ∨ 𝑞 ∨∼ 𝑟
𝑆 ⇔ ∼ 𝑝 ∧ 𝑞 ∧∼ 𝑟 ∨ 𝑝 ∧∼ 𝑞 ∧ 𝑟 𝑤𝑕𝑖𝑐𝑕 𝑖𝑠 𝑃𝐷𝑁𝐹.
𝑆 ⇔∼ 𝑝 ∨∼ 𝑞 ∨ 𝑟 ∨∼ ∼ 𝑝 ∨ 𝑞 ∨∼ 𝑟

ii) By indirect method prove that (𝒙) (𝑷(𝒙) → 𝑸(𝒙)), (∃𝒙)𝑷(𝒙) ⇒ (∃𝒙)𝑸(𝒙)

www.tranquileducation.weely.com 3
 Anna University, Chennai, November/December 2012

Solution:
Let us assume that ¬(∃𝑥)𝑄(𝑥) as additional premise
1. ¬(∃𝑥)𝑄(𝑥) 𝐴𝑑𝑑𝑖𝑡𝑖𝑜𝑛𝑎𝑙 𝑝𝑟𝑒𝑚𝑖𝑠𝑒
2. 𝑥 ¬𝑄 𝑥 𝑅𝑢𝑙𝑒 𝑇, 1, 𝐷𝑒 𝑀𝑜𝑟𝑔𝑎𝑛′𝑠 𝑙𝑎𝑤
3. ¬𝑄 𝑎 𝑅𝑢𝑙𝑒 𝑇, 2, 𝑈𝑆
4. (∃𝑥)𝑃(𝑥) 𝑅𝑢𝑙𝑒 𝑃
5. 𝑃 𝑎 𝑅𝑢𝑙𝑒 𝑇, 4, 𝐸𝑆
6. 𝑃 𝑎 ⋀¬𝑄 𝑎 𝑅𝑢𝑙𝑒 𝑇, 5,3 𝑎𝑛𝑑 𝑐𝑜𝑛𝑗𝑢𝑐𝑡𝑖𝑜𝑛
7. ¬ ¬𝑃 𝑎 ⋁𝑄 𝑎 𝑅𝑢𝑙𝑒 𝑇, 6, 𝐷𝑒 𝑀𝑜𝑟𝑔𝑎𝑛′𝑠 𝑙𝑎𝑤
8. ¬ 𝑃 𝑎 → 𝑄 𝑎 𝑅𝑢𝑙𝑒 𝑇, 7, 𝐸𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑐𝑒
9. 𝑥 𝑃 𝑥 → 𝑄 𝑥 𝑅𝑢𝑙𝑒 𝑃
10. 𝑃 𝑎 → 𝑄 𝑎 𝑅𝑢𝑙𝑒 𝑇, 9, 𝑈𝑆
11. ¬ 𝑃 𝑎 → 𝑄 𝑎 ⋀ 𝑃 𝑎 → 𝑄 𝑎 𝑅𝑢𝑙𝑒 𝑇, 8,10 𝑎𝑛𝑑 𝑐𝑜𝑛𝑗𝑢𝑐𝑡𝑖𝑜𝑛
12. 𝐹 𝑅𝑢𝑙𝑒 𝑇, 11 𝑎𝑛𝑑 𝑛𝑒𝑔𝑎𝑡𝑖𝑜𝑛 𝑙𝑎𝑤

12.a)i) Use mathematical induction to prove the inequality 𝒏 < 𝟐𝒏 for all positive integer 𝒏.
Proof:
𝐿𝑒𝑡 𝑃 𝑛 : 𝑛 < 2𝑛 … (1)
1
𝑃 1 :1<2
⇒1<2
∴ 𝑃(1) is true.
Let us assume that 𝑃(𝑛) is true. Now we have to prove that 𝑃(𝑛 + 1) is true.
To prove:
𝑃 𝑛 + 1 : 𝑛 + 1 < 2𝑛 +1
𝑛 < 2𝑛 (𝑓𝑟𝑜𝑚 1 )
𝑛 + 1 < 2𝑛 + 1
𝑛 + 1 < 2𝑛 + 2𝑛 ∵ 1 < 2𝑛
𝑛
𝑛 + 1 < 2.2
𝑛 + 1 < 2𝑛 +1
∴ 𝑃 𝑛 + 1 is true.
∴ By induction method,
𝑃 𝑛 : 𝑛 < 2𝑛 𝑖𝑠 𝑡𝑟𝑢𝑒 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝑖𝑛𝑡𝑒𝑔𝑒𝑟𝑠.

ii) What is the maximum number of students required in a discrete mathematics class to be sure that
at least six will receive the same grade if there are five possible grades 𝑨, 𝑩, 𝑪, 𝑫 and 𝑭.
Solution:
By Pigeonhole principle, If there are 𝑛 holes and 𝑘 pigeons 𝑛 ≤ 𝑘 then there is at least one hole contains
𝑘−1
at least 𝑛 + 1 pigeons.
Here 𝑛 = 5
𝑘−1
+1=6
5
𝑘−1
= 5 ⇒ 𝑘 − 1 = 25 ⇒ 𝑘 = 26
5
The maximum number of students required in a discrete mathematics class is 26.

b)i) Suppose that there are 9 faculty members in the mathematics department and 11 in the computer
science department. How many ways are there to select a committee to develop a discrete

www.tranquileducation.weely.com 4
 Anna University, Chennai, November/December 2012

mathematics course at a school if the committee is to consist of three faculty member from
mathematics department and four from the computer science department?
Solution:
The number of ways to select 3 mathematics faculty members from 9 faculty members is
9𝐶3 ways.
The number of ways to select 4 computer Science faculty members from 11 faculty members is
11𝐶4 ways.
The number of ways to select a committee to develop a discrete mathematics course at a school if the
committee is to consist of three faculty member from mathematics department and four from the
computer science department is 9𝐶3 . 11𝐶4 ways.
9 × 8 × 7 11 × 10 × 9 × 8
9𝐶3 . 11𝐶4 = . = 27720
3! 4!

ii) Using method of generating function to solve the recurrence relation

𝒂𝒏 + 𝟑𝒂𝒏−𝟏 − 𝟒𝒂𝒏−𝟐 = 𝟎; 𝒏 ≥ 𝟐 , given that 𝒂𝟎 = 𝟑 and 𝒂𝟏 = −𝟐.
Solution:
∞

𝐿𝑒𝑡 𝐺 𝑥 = 𝑎𝑛 𝑥 𝑛 = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ … 1
𝑛=0
where 𝐺 𝑥 is the generating function for the sequence 𝑎𝑛 .
Given 𝑎𝑛 + 3𝑎𝑛−1 − 4𝑎𝑛−2 = 0
Multiplying by 𝑥𝑛 and summing from 2 to ∞, we have
∞ ∞ ∞
𝑛 𝑛
𝑎𝑛 𝑥 + 3 𝑎𝑛−1 𝑥 − 4 𝑎𝑛−2 𝑥 𝑛 = 0
𝑛=2 𝑛=2 𝑛=2
∞ ∞ ∞

𝑎𝑛 𝑥 𝑛 + 3𝑥 𝑎𝑛−1 𝑥 𝑛 −1 − 4𝑥 2 𝑎𝑛−2 𝑥 𝑛 −2 = 0
𝑛=2 𝑛 =2 𝑛 =2
𝑎2 𝑥 2 + 𝑎3 𝑥 3 + 𝑎4 𝑥 4 + ⋯ + 3𝑥 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ − 4𝑥 2 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ = 0
𝐺 𝑥 − 𝑎0 − 𝑎1 𝑥 + 3𝑥𝐺 𝑥 − 3𝑥𝑎0 − 4𝑥 2 𝐺 𝑥 = 0 [𝑓𝑟𝑜𝑚 1 ]
2
𝐺 𝑥 1 + 3𝑥 − 4𝑥 − 3 + 2𝑥 − 9𝑥 = 0
𝐺 𝑥 1 + 3𝑥 − 4𝑥 2 = 3 − 7𝑥
3 − 7𝑥 3 − 7𝑥
𝐺 𝑥 = 2
=
1 + 3𝑥 − 4𝑥 1 + 4𝑥 1 − 𝑥

3 − 7𝑥 𝐴 𝐵
= +
1 + 4𝑥 1 − 𝑥 1 + 4𝑥 1−𝑥
3 − 7𝑥 = 𝐴 1 − 𝑥 + 𝐵 1 + 4𝑥 … 2
1
Put 𝑥 = − 4
in (2)
1 1 5 7 19
3−7 − =𝐴 1+ ⇒ 𝐴=3+ ⇒𝐴=
4 4 4 4 5
Put 𝑥 = 1 in (2)
4
3 − 7 = 𝐵 1 + 4 ⇒ 5𝐵 = −4 ⇒ 𝐵 = −
5

www.tranquileducation.weely.com 5
 Anna University, Chennai, November/December 2012

19 4
𝐺 𝑥 = 5 − 5
1 + 4𝑥 1−𝑥

∞ ∞ ∞ ∞
19 4 1
𝑎𝑛 𝑥 𝑛 = −4 𝑛 𝑥 𝑛 − 𝑥𝑛 ∵ = 𝑥𝑛
5 5 1−𝑥
𝑛=0 𝑛=0 𝑛 =0 𝑛=0
𝑎𝑛 = Coefficient of 𝑥 𝑛 in 𝐺(𝑥)
19 4
𝑎𝑛 = −4 𝑛 −
5 5

13. a)i) How many paths of length four are there from 𝒂 to 𝒅 in the simple graph 𝑮 given below.
𝑎 𝑏

𝑐 𝑑
Solution: The adjacency matrix for the given graph is
𝑎 𝑏 𝑐 𝑑
𝑎 0 1 0 1
𝑏 1 0 1 0
𝐴=
𝑐 0 1 0 1
𝑑 1 0 1 0

𝑎 𝑏 𝑐 𝑑
𝑎 2 0 2 0
𝑏 0 2 0 2
𝐴2 =
𝑐 2 0 2 0
𝑑 0 2 0 2

𝑎 𝑏 𝑐 𝑑
𝑎 8 0 8 0
𝑏 0 8 0 8
𝐴4 =
𝑐 8 0 8 0
𝑑 0 8 0 8

Since the value in the 𝑎𝑡𝑕 row and 𝑑𝑡𝑕 column in 𝐴4 is 0.

∴ There is no path from 𝑎 to 𝑑 of length 4.

ii) Show that the complete graph with n vertices 𝑲𝒏 has a Hamiltonian circuit whenever 𝒏 ≥ 𝟑.
Proof:
In a complete graph 𝐾𝑛 , every vertex is adjacent to every other vertex in the graph.

www.tranquileducation.weely.com 6
 Anna University, Chennai, November/December 2012

Therefore a path can be formed starting from any vertex and traverse through all the vertices of 𝐾𝑛 and
reach the same vertex to form a circuit without traversing through any vertex more than once except
the terminal vertex. This circuit is called the Hamiltonian circuit.
∴ The complete graph with n vertices 𝐾𝑛 has a Hamiltonian circuit whenever 𝑛 ≥ 3.

b) i) Determine whether the graphs 𝑮 and 𝑯given below are isomorphic.

𝑎 𝑏 𝑝 𝑟
𝑞
𝑒
𝑓
𝑢

𝑑 𝑐 𝑡 𝑠
𝐺 𝐻
Solution:
The two graphs 𝐺and 𝐻 have same number of vertices and same number of edges.
deg 𝑎 = 2, deg 𝑏 = 3, deg 𝑐 = 2, deg 𝑑 = 3, deg 𝑒 = 2, deg 𝑓 = 2
deg 𝑝 = 2, deg 𝑞 = 2, deg 𝑟 = 3, deg 𝑠 = 2, deg 𝑡 = 3, deg 𝑢 = 2
Here in both the graphs two vertices are of degree three and remaining vertices are of degree two.
The mapping between two graphs are 𝑎 → 𝑢, 𝑏 → 𝑟, 𝑐 → 𝑠, 𝑑 → 𝑡, 𝑒 → 𝑝 and 𝑓 → 𝑞.
There is one to one correspondence between the adjacency of the vertices between the two graphs.
Therefore the two graphs are isomorphic.

ii) Prove that an undirected graph has an even number of vertices of odd degree.
Proof:
By Handshaking theorem, we know that
If the graph G has n vertices and e edges then
𝑛 𝑛

deg 𝑣𝑖 = 2𝑒 ⇒ deg 𝑣𝑖 = 𝑒𝑣𝑒𝑛 𝑛𝑢𝑚𝑏𝑒𝑟

𝑖=1 𝑖=1

deg 𝑣𝑖 + deg 𝑣𝑖 = 𝑒𝑣𝑒𝑛 𝑛𝑢𝑚𝑏𝑒𝑟

𝑜𝑑𝑑 𝑒𝑣𝑒𝑛

𝑤𝑕𝑒𝑟𝑒 deg 𝑣𝑖 𝑖𝑠 𝑠𝑢𝑚 𝑜𝑓 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠 𝑤𝑖𝑡𝑕 𝑜𝑑𝑑 𝑑𝑒𝑔𝑟𝑒𝑒

𝑜𝑑𝑑

deg 𝑣𝑖 𝑖𝑠 𝑠𝑢𝑚 𝑜𝑓 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠 𝑤𝑖𝑡𝑕 𝑒𝑣𝑒𝑛 𝑑𝑒𝑔𝑟𝑒𝑒

𝑒𝑣𝑒𝑛

deg 𝑣𝑖 + 𝑒𝑣𝑒𝑛 𝑛𝑢𝑚𝑏𝑒𝑟 = 𝑒𝑣𝑒𝑛 𝑛𝑢𝑚𝑏𝑒𝑟

𝑜𝑑𝑑
( Since sum of even numbers is an even number)
deg 𝑣𝑖 = 𝑒𝑣𝑒𝑛 𝑛𝑢𝑚𝑏𝑒𝑟
𝑜𝑑𝑑

www.tranquileducation.weely.com 7
 Anna University, Chennai, November/December 2012

Sum of even number of odd numbers is an even number.

∴ An undirected graph has an even number of vertices of odd degree.

14.a)i) If ∗ is the operation defined on 𝑺 = 𝑸 × 𝑸, the set of ordered pairs of rational numbers and
givenby 𝒂, 𝒃 ∗ 𝒙, 𝒚 = 𝒂𝒙, 𝒂𝒚 + 𝒃 ,show that 𝑺,∗ is a semi group. Is it commutative? Also find the
identity element of S.
Solution:
Closure: ∀ 𝑎, 𝑏 , 𝑥, 𝑦 ∈ 𝑆
𝑎, 𝑏 ∗ 𝑥, 𝑦 = 𝑎𝑥, 𝑎𝑦 + 𝑏 ∈ 𝑆 ∵ 𝑎𝑥 ∈ 𝑄 𝑎𝑛𝑑 𝑎𝑦 + 𝑏 ∈ 𝑄, ∀𝑎, 𝑏, 𝑥, 𝑦 ∈ 𝑄
⇒ 𝑎, 𝑏 ∗ 𝑥, 𝑦 ∈ 𝑆
∀ 𝑎, 𝑏 , 𝑥, 𝑦 ∈ 𝑆 ⇒ 𝑎, 𝑏 ∗ 𝑥, 𝑦 ∈ 𝑆
∴ 𝑆 is closed under ∗.
Associative: ∀ 𝑎, 𝑏 , 𝑥, 𝑦 , (𝑢, 𝑤) ∈ 𝑆
𝑎, 𝑏 ∗ 𝑥, 𝑦 ∗ 𝑢, 𝑣 = 𝑎, 𝑏 ∗ 𝑥𝑢, 𝑥𝑣 + 𝑦
= 𝑎𝑥𝑢, 𝑎 𝑥𝑣 + 𝑦 + 𝑏 = 𝑎𝑥𝑢, 𝑎𝑥𝑣 + 𝑎𝑦 + 𝑏 … (1)
𝑎, 𝑏 ∗ 𝑥, 𝑦 ∗ 𝑢, 𝑣 = 𝑎𝑥, 𝑎𝑦 + 𝑏 ∗ 𝑢, 𝑣
= 𝑎𝑥𝑢, 𝑎𝑥𝑣 + 𝑎𝑦 + 𝑏 … (2)
From (1) and (2), we get
𝑎, 𝑏 ∗ 𝑥, 𝑦 ∗ 𝑢, 𝑣 = 𝑎, 𝑏 ∗ 𝑥, 𝑦 ∗ 𝑢, 𝑣
∴ 𝑆 satisfies associative property under ∗.
Identity: Let 𝑒1 , 𝑒2 ∈ 𝑆 be the identity element.
Then 𝑎, 𝑏 ∗ 𝑒1 , 𝑒2 = 𝑒1 ∗ 𝑒2 ∗ 𝑎, 𝑏 = 𝑎, 𝑏 , ∀ 𝑎, 𝑏 ∈ 𝑆
𝑎, 𝑏 ∗ 𝑒1 , 𝑒2 = 𝑎, 𝑏
⇒ 𝑎𝑒1 , 𝑎𝑒2 + 𝑏 = 𝑎, 𝑏
⇒ 𝑎𝑒1 = 𝑎, 𝑎𝑒2 + 𝑏 = 𝑏
⇒ 𝑒1 = 1, 𝑎𝑒2 = 0
⇒ 𝑒1 = 1, 𝑒2 = 0
⇒ 1,0 =∈ 𝑆
∴ 1,0 ∈ 𝑆 is the identity element.
∴ 𝑆 is a semi group under ∗.
∀ 𝑎, 𝑏 , 𝑥, 𝑦 ∈ 𝑆, 𝑎, 𝑏 ∗ 𝑥, 𝑦 = 𝑎𝑥, 𝑎𝑦 + 𝑏 … 3
𝑥, 𝑦 ∗ 𝑎, 𝑏 = 𝑥𝑎, 𝑥𝑏 + 𝑦 … 4
From (3) and (4), we get
𝑎, 𝑏 ∗ 𝑥, 𝑦 ≠ 𝑥, 𝑦 ∗ 𝑎, 𝑏
∴ 𝑆 is not commutative under ∗.

ii) Prove that the necessary and sufficient condition for a non empty subset 𝑯 of a group 𝑮,∗ to be a
subgroup is 𝒂, 𝒃 ∈ 𝑯 ⇒ 𝒂 ∗ 𝒃−𝟏 ∈ 𝑯.
Proof:
Necessary condition:
Let us assume that 𝐻is a subgroup of 𝐺.
𝐻 itself is a group.

www.tranquileducation.weely.com 8
 Anna University, Chennai, November/December 2012

𝑎, 𝑏 ∈ 𝐻 ⇒ 𝑎 ∗ 𝑏 ∈ 𝐻 … 1 𝐶𝑙𝑜𝑠𝑢𝑟𝑒
𝑏 ∈ 𝐻 ⇒ 𝑏 −1 ∈ 𝐻 … (2) 𝐼𝑛𝑣𝑒𝑟𝑠𝑒 𝑝𝑟𝑜𝑝𝑒𝑟𝑡𝑦
𝑎, 𝑏 ∈ 𝐻 ⇒ 𝑎, 𝑏−1 ∈ 𝐻 ⇒ 𝑎 ∗ 𝑏−1 ∈ 𝐻 𝑓𝑟𝑜𝑚 1 𝑎𝑛𝑑 2
∴ 𝑎, 𝑏 ∈ 𝐻 ⇒ 𝑎 ∗ 𝑏−1 ∈ 𝐻.
Sufficient condition:
Let 𝑎, 𝑏 ∈ 𝐻 ⇒ 𝑎 ∗ 𝑏−1 ∈ 𝐻 and 𝐻 is a subset of 𝐺.
Closure property:
If 𝑏 ∈ 𝐻 ⇒ 𝑏 −1 ∈ 𝐻
𝑎, 𝑏 ∈ 𝐻 ⇒ 𝑎, 𝑏−1 ∈ 𝐻 ⇒ 𝑎 ∗ 𝑏−1 −1 ∈ 𝐻 ⇒ 𝑎 ∗ 𝑏 ∈ 𝐻
𝑎, 𝑏 ∈ 𝐻 ⇒ 𝑎 ∗ 𝑏 ∈ 𝐻
Hence 𝐻 is closed.
Associative property:
∵ 𝐻 is a subset of 𝐺. All the elements in 𝐻 are elements of 𝐺. Since 𝐺 is associative under ∗.
∴ 𝐻 is associative under ∗.
Identity property:
𝑎, 𝑎 ∈ 𝐻 ⇒ 𝑎 ∗ 𝑎−1 ∈ 𝐻 ⇒ 𝑒 ∈ 𝐻
∴ 𝑒 ∈ 𝐻 be the identity element.
Inverse property:
𝑒, 𝑎 ∈ 𝐻 ⇒ 𝑒 ∗ 𝑎−1 ∈ 𝐻 ⇒ 𝑎−1 ∈ 𝐻
−1
∴ 𝑎 ∈ 𝐻 be the inverse of 𝑎 ∈ 𝐻.
𝐻 itself is a group.
∴ 𝐻 is a subgroup of 𝐺.

b) i) Prove that the set 𝒁𝟒 = 𝟎 , 𝟏 , 𝟐 , [𝟑] is a commutative ring with respect to the binary
operation addition modulo and multiplication modulo +𝟒 ,×𝟒 .
Solution:
The Cayley table for 𝒁𝟒 , +𝟒 𝑎𝑛𝑑 𝒁𝟒 ,×𝟒 is given below
+𝟒 [0] [1] [2] [3] ×𝟒 [0] [1] [2] [3]
[0] [0] [1] [2] [3] [0] [0] [0] [0] [0]
[1] [1] [2] [3] [0] [1] [0] [1] [2] [3]
[2] [2] [3] [0] [1] [2] [0] [2] [0] [2]
[3] [3] [0] [1] [2] [3] [0] [3] [2] [1]
From the above Cayley table, we observe that
All the elements in the table is also an element in 𝑍4 under +4 .
∴ 𝑍4 is closed under binary operation +4 .
It is clear from the table that 𝑍4 is associative under +4 .
Here 0 ∈ 𝑍4 is the identity element.
The inverse of 0 , 1 , [2] and [3] are 0 , 3 , 2 and [1] respectively.
It is clear from the table that 𝑍4 is commutative under +4 .
All the elements in the table is also an element in 𝑍4 under ×4 .
∴ 𝑍4 is closed under binary operation ×4 .
It is clear from the table that 𝑍4 is associative under ×4 .

www.tranquileducation.weely.com 9
 Anna University, Chennai, November/December 2012

It is clear from the table that 𝑍4 is commutative under ×4 .

∴ 𝑍4 , +4 ,×4 is a commutative ring.

ii) If 𝒇: 𝑮 → 𝑮′ is a group homomorphism from 𝑮,∗ to 𝑮′ , 𝚫 then prove that for any 𝒂 ∈ 𝑮,
𝒇 𝒂−𝟏 = 𝒇 𝒂 −𝟏 .
Solution:
Since 𝑓 is a group homomorphism.
∀𝑎, 𝑏 ∈ 𝐺, 𝑓 𝑎∗𝑏 = 𝑓 𝑎 Δ𝑓 𝑏
−1
Since G is a group, 𝑎 ∈ 𝐺 ⇒ 𝑎 ∈ 𝐺.
𝑓 𝑎 Δ 𝑓(𝑎−1 ) = 𝑓(𝑎 ∗ 𝑎−1 )
𝑓 𝑎 Δ 𝑓(𝑎−1 ) = 𝑓(𝑒)
−1 ′
𝑓 𝑎 Δ𝑓 𝑎 =𝑒 𝑤𝑕𝑒𝑟𝑒 𝑒 ′ 𝑖𝑠 𝑡𝑕𝑒 𝑖𝑑𝑒𝑛𝑡𝑖𝑡𝑦 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑖𝑛 𝐺′
The inverse of 𝑓 𝑎 is 𝑓 𝑎−1 .
∴ 𝑓 𝑎 −1 = 𝑓(𝑎−1 )

15. a)i) Draw the Hasse diagram representing the partial ordering 𝑨, 𝑩 : 𝑨 ⊆ 𝑩 on the power set
𝑷(𝑺) Where 𝑺 = 𝒂, 𝒃, 𝒄 . Find the maximal, minimal, greatest and least elements of the Poset.
Solution:
{𝒂, 𝒃, 𝒄}

{𝒂, 𝒃} {𝒂, 𝒄} {𝒃, 𝒄}

{𝒂} {𝒃} {𝒄}

∅
The minimal element is 𝜙
The maximal element is 𝑎, 𝑏, 𝑐
The least element is 𝜙
The greatest element is 𝑎, 𝑏, 𝑐

ii) In a Boolean algebra, prove that 𝒂. 𝒂 + 𝒃 = 𝒂, for all 𝒂, 𝒃 ∈ 𝑮.

Solution:
We know from the definition of GLB and LUB
𝑎. 𝑏 ≤ 𝑎 … 1
𝑎+𝑏 ≥ 𝑎… 2
𝑎. 𝑎 + 𝑏 ≤ 𝑎 … 3 𝑓𝑟𝑜𝑚 1
𝑎. 𝑎 + 𝑏 = 𝑎. 𝑎 + 𝑎. 𝑏
𝑎. 𝑎 + 𝑏 = 𝑎 + 𝑎. 𝑏 ≥ 𝑎 𝑓𝑟𝑜𝑚 (2)

www.tranquileducation.weely.com 10
 Anna University, Chennai, November/December 2012

⇒ 𝑎. 𝑎 + 𝑏 ≥ 𝑎 … 4
From (3) and (4), we get
𝑎. 𝑎 + 𝑏 = 𝑎

b) i) In a distributive Lattice 𝑳,∨,∧ if an element 𝒂 ∈ 𝑳 has a complement then it is unique.

Solution:
Let 𝑏 and 𝑐 be the complement of 𝑎 ∈ 𝐿
𝑏 =𝑏∧1
𝑏 =𝑏∧ 𝑎∨𝑐 ∵𝑎∨𝑐 =1
𝑏 = 𝑏∧𝑎 ∨ 𝑏∧𝑐 𝐷𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑒 𝑙𝑎𝑤
𝑏 =0∨ 𝑏∧𝑐 ∵𝑎∧𝑏 =0
𝑏 = 𝑏 ∧ 𝑐 … (1) ∵ 𝑎 ∨ 0 = 𝑎
𝑐 =1∧𝑐
𝑐 = 𝑎∨𝑏 ∧𝑐 ∵𝑎∨𝑏 =1
𝑐 = 𝑎∧𝑐 ∨ 𝑏∧𝑐 𝐷𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑒 𝑙𝑎𝑤
𝑐 =0∨ 𝑏∧𝑐 ∵𝑎∧𝑐 =0
𝑐 = 𝑏 ∧ 𝑐 … (2) ∵ 𝑎 ∨ 0 = 𝑎
From (1) and (2), we get
𝑏=𝑐
∴ In a distributive Lattice 𝐿,∨,∧ if an element 𝑎 ∈ 𝐿 has a complement then it is unique.

ii) Simplify the Boolean expression 𝒂′ . 𝒃′ . 𝒄 + 𝒂. 𝒃′ . 𝒄 + 𝒂′ . 𝒃′ . 𝒄′ using Boolean algebra identities.

Solution:
𝑎′ . 𝑏′ . 𝑐 + 𝑎. 𝑏′ . 𝑐 + 𝑎′ . 𝑏′ . 𝑐 ′ = 𝑎 ′ + 𝑎 . 𝑏′ . 𝑐 + 𝑎′ . 𝑏′ . 𝑐 ′ 𝐷𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑒 𝑙𝑎𝑤
= 1. 𝑏′ . 𝑐 + 𝑎′ . 𝑏′ . 𝑐 ′ 𝑎′ + 𝑎 = 1
= 𝑏′ . 𝑐 + 𝑎′ . 𝑏′ . 𝑐 ′ 1. 𝑎 = 𝑎
′ ′ ′ ′
= 𝑏 .𝑐 + 𝑏 .𝑎 .𝑐 𝑎. 𝑏 = 𝑏. 𝑎
= 𝑏′ . 𝑐 + 𝑎′ . 𝑐 ′ 𝐷𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑒 𝑙𝑎𝑤
= 𝑏′ . 𝑐 + 𝑎′ . 𝑐 + 𝑐′ 𝐷𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑒 𝑙𝑎𝑤
= 𝑏′ . 𝑐 + 𝑎′ . 1 𝑎′ + 𝑎 = 1
= 𝑏′ . 𝑐 + 𝑎′ 1. 𝑎 = 𝑎
= 𝑏′ . 𝑐 + 𝑏′ . 𝑎′ 𝐷𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑒 𝑙𝑎𝑤

www.tranquileducation.weely.com 11