Anna University, Chennai, November/December 2010

B.E./B.Tech. DEGREE EXAMINATION, November/December 2010

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

Part - A
1. When do you say that two compound propositions are equivalent?
Answer:
Let A and B are the two compound propositions. 𝐴 ⇔ 𝐵 if 𝐴 ↔ 𝐵 is a tautology.

2. Prove that 𝒑, 𝒑 → 𝒒, 𝒒 → 𝒓 ⇒ 𝒓.
Solution:
1. 𝑝 Rule P
2. 𝑝→𝑞 Rule P
3. 𝑞→𝑟 Rule P
4. 𝑝→𝑟 Rule T,2,3, chain rule
5. 𝑟 Rule T,1,4, Modus phones

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. Find the recurrence relation satisfying the equation 𝒚𝒏 = 𝑨 𝟑 𝒏 + 𝑩 −𝟒 𝒏 .

Solution: 𝑦𝑛 = 𝐴 3 𝑛 + 𝐵 −4 𝑛 .
𝑦𝑛+1 = 𝐴 3 𝑛+1 + 𝐵 −4 𝑛 +1 = 3𝐴3𝑛 − 4𝐵 −4 𝑛
𝑦𝑛+2 = 𝐴 3 𝑛+2 + 𝐵 −4 𝑛+2 = 9𝐴3𝑛 + 16𝐵 −4 𝑛
𝑦𝑛+2 + 𝑦𝑛+1 − 12𝑦𝑛 = 0
5. Define strongly connected graph.
Answer:
A digraph is said to be strongly connected graph, if there is a path between every pair of vertices in the
digraph.

6. State the necessary and sufficient conditions for the existence of an Eulerian path in a connected
graph.
Answer:
A connected graph has an Euler path but not Euler circuit if and only if it has exactly two vertices of odd
degree.

7. State any two properties of a group.

Answer:
Identity element of a group is unique.
Inverse element of a group is unique.

8. Define a commutative ring.

Answer:

www.tranquileducation.weebly.com 1
 Anna University, Chennai, November/December 2010

A ring 𝑅, +,× is said to be a commutative ring if it satisfies the following condition

∀𝑎, 𝑏 ∈ 𝑅, 𝑎 × 𝑏 = 𝑏 × 𝑎

9. Define Boolean algebra.

Answer:
A complemented distributive lattice is called Boolean algebra.

10. Define sub-lattice.

Answer:
A lattice 𝑆, ≤ is called a sub-lattice of a lattice 𝐿, ≤ if 𝑆 ⊆ 𝐿 and 𝑆 is a lattice.

Part - B
11. a)i) Prove that the premises 𝒂 → 𝒃 → 𝒄 , 𝒅 → (𝒃 ∧∼ 𝒄) and (𝒂 ∧ 𝒅) are inconsistent.
Solution:
1. 𝑎 → 𝑏 → 𝑐 Rule P
2. 𝑑 → (𝑏 ∧∼ 𝑐) Rule P
3. (𝑎 ∧ 𝑑) Rule P
4. 𝑎 Rule T,3, 𝑝 ∧ 𝑞 ⇒ 𝑝
5. 𝑑 Rule T,3, 𝑝 ∧ 𝑞 ⇒ 𝑞
6. 𝑏→𝑐 Rule T,1,4, Modus phones
7. (𝑏 ∧∼ 𝑐) Rule T,2,5, Modus phones
8. ∼ (∼ 𝑏 ∨ 𝑐) Rule T,7, Demorgan’s law
9. ∼ 𝑏 → 𝑐 Rule T,8, ∼ 𝑎 ∨ 𝑏 ⇒ 𝑎 → 𝑏
10. 𝑏 → 𝑐 ∧∼ 𝑏 → 𝑐 Rule T,9, 𝑎, 𝑏 ⇒ 𝑎 ∧ 𝑏
11. 𝐹 Rule T,10, 𝑎 ∧∼ 𝑎 ⇒ 𝐹
∴ The premises 𝑎 → 𝑏 → 𝑐 , 𝑑 → (𝑏 ∧∼ 𝑐) and (𝑎 ∧ 𝑑) are inconsistent.

ii) Obtain the principal disjunctive normal form and principal conjunction form of the statement
𝑷∨ ∼𝑷→ 𝑸∨ ∼𝑸→𝑹
Solution:
Let 𝑆 ⇔ 𝑃 ∨ ∼ 𝑃 → 𝑄 ∨ ∼ 𝑄 → 𝑅
𝐴: ∼ 𝑃 → 𝑄 ∨ ∼ 𝑄 → 𝑅
𝐏 𝑸 𝑹 ∼𝑷 ∼𝑸 ∼𝑸→𝑹 𝑸∨ ∼𝑸→𝑹 𝑨 𝐒 𝑴𝒊𝒏𝒕𝒆𝒓𝒎 𝑴𝒂𝒙𝒕𝒆𝒓𝒎
T T T F F T T T T 𝑃∧𝑄∧𝑅
T F T F T T T T T 𝑃 ∧∼ 𝑄 ∧ 𝑅
F T T T F T T T T ∼𝑃∧𝑄∧𝑅
F F T T T T T T T ∼ 𝑃 ∧∼ 𝑄 ∧ 𝑅
T T F F F T T T T 𝑃 ∧ 𝑄 ∧∼ 𝑅
T F F F T F F T T 𝑃 ∧∼ 𝑄 ∧∼ 𝑅
F T F T F T T T T ∼ 𝑃 ∧ 𝑄 ∧∼ 𝑅
F F F T T F F F F P∨Q∨R
𝑆 ⇔ 𝑃 ∧ 𝑄 ∧ 𝑅 ∨ 𝑃 ∧∼ 𝑄 ∧ 𝑅 ∨ ∼ 𝑃 ∧ 𝑄 ∧ 𝑅 ∨ ∼ 𝑃 ∧∼ 𝑄 ∧ 𝑅 ∨ 𝑃 ∧ 𝑄 ∧∼ 𝑅
∨ 𝑃 ∧∼ 𝑄 ∧∼ 𝑅 ∨ ∼ 𝑃 ∧ 𝑄 ∧∼ 𝑅 is a PDNF
𝑆 ⇔ P ∨ Q ∨ R is a PCNF

www.tranquileducation.weebly.com 2
 Anna University, Chennai, November/December 2010

b) i) Prove that ∀𝒙 𝑷 𝒙 → 𝑸 𝒙 , ∀𝒙 𝑹 𝒙 →∼ 𝑸(𝒙) ⇒ ∀𝒙 𝑹 𝒙 →∼ 𝑷(𝒙)

Solution:
1. ∀𝑥 𝑃 𝑥 → 𝑄 𝑥 Rule P
2. ∀𝑥 𝑅 𝑥 →∼ 𝑄(𝑥) Rule P
3. 𝑃 𝑎 → 𝑄 𝑎 Rule T,1,US
4. 𝑅 𝑎 →∼ 𝑄(𝑎) Rule T,2,US
5. ∼ 𝑄 𝑎 →∼ 𝑝(𝑎) Rule T,3, 𝑝 → 𝑞 ⇒∼ 𝑞 →∼ 𝑝
6. 𝑅 𝑎 →∼ 𝑃(𝑎) Rule T,4,5, chain rule
7. ∀𝑥 𝑅 𝑥 →∼ 𝑃(𝑥) Rule T,6,UG

ii) Without using the truth table, prove that ∼ 𝑃 → 𝑄 → 𝑅 ≡ 𝑄 → 𝑃 ∨ 𝑅 .

Proof:
∼𝑃→ 𝑄→𝑅
⇔∼∼ 𝑃 ∨ 𝑄 → 𝑅 𝐼𝑚𝑝𝑙𝑖𝑐𝑎𝑡𝑖𝑜𝑛 𝑙𝑎𝑤
⇔𝑃∨ 𝑄→𝑅 𝑛𝑒𝑔𝑎𝑡𝑖𝑜𝑛 𝑙𝑎𝑤
⇔𝑃∨ ∼ 𝑄∨𝑅 𝐼𝑚𝑝𝑙𝑖𝑐𝑎𝑡𝑖𝑜𝑛 𝑙𝑎𝑤
⇔ 𝑃 ∨∼ 𝑄 ∨ 𝑅 𝐴𝑠𝑠𝑜𝑐𝑖𝑎𝑡𝑒 𝑙𝑎𝑤
⇔ ∼ 𝑄∨𝑃 ∨𝑅 𝐶𝑜𝑚𝑚𝑢𝑡𝑎𝑡𝑖𝑣𝑒 𝑙𝑎𝑤
⇔∼ 𝑄 ∨ 𝑃 ∨ 𝑅 𝐴𝑠𝑠𝑜𝑐𝑖𝑎𝑡𝑒 𝑙𝑎𝑤
⇔𝑄 → 𝑃∨𝑅 𝐼𝑚𝑝𝑙𝑖𝑐𝑎𝑡𝑖𝑜𝑛 𝑙𝑎𝑤

12.a) i) Prove, by mathematical induction, that for all 𝒏 ≥ 𝟏, 𝒏𝟑 + 𝟐𝒏 is a multiple of 3.

Solution:
𝐿𝑒𝑡 𝑃 𝑛 : 𝑛 ≥ 1, 𝑛3 + 2𝑛 is a multiple of 3. … (1)
3
𝑃 1 : 1 + 2 1 = 1 + 2 = 3 is a multiple of 3.
∴ 𝑃(1) is true.
Let us assume that 𝑃(𝑛) is true. Now we have to prove that 𝑃(𝑛 + 1) is true.
To prove:
𝑃 𝑛 + 1 : (𝑛 + 1)3 + 2(𝑛 + 1) is a multiple of 3
(𝑛 + 1) + 2 𝑛 + 1 = 𝑛 + 3𝑛 + 3𝑛2 + 1 + 2𝑛 + 2
3 3

= 𝑛3 + 2𝑛 + 3𝑛 + 3𝑛2 + 3
= 𝑛3 + 2𝑛 + 3 𝑛2 + 𝑛 + 1
3
From (1) 𝑛 + 2𝑛 is a multiple of 3
∴ (𝑛 + 1)3 + 2 𝑛 + 1 𝑖𝑠 𝑎 𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑒 𝑜𝑓 3

∴ 𝑃 𝑛 + 1 is true.
∴ By induction method,
𝑃 𝑛 : 𝑛 ≥ 1, 𝑛3 + 2𝑛 is a multiple of 3, is true for all positive integer n.

ii) Using the generating function, solve the difference equation

𝐲𝐧+𝟐 − 𝐲𝐧+𝟏 − 𝟔𝐲𝐧 = 𝟎, 𝐲𝟏 = 𝟏, 𝐲𝟎 = 𝟐
Solution:
∞

𝐿𝑒𝑡 𝐺 𝑥 = 𝑦𝑛 𝑥 𝑛 … (1) where 𝐺 𝑥 is the generating function for the sequence 𝑦𝑛 .

𝑛=0
Given 𝑦𝑛+2 − 𝑦𝑛+1 − 6𝑦𝑛 = 0
Multiplying by 𝑥𝑛 and summing from 0 to ∞, we have

www.tranquileducation.weebly.com 3
 Anna University, Chennai, November/December 2010
∞ ∞ ∞

𝑦𝑛+2 𝑥 𝑛 − 𝑦𝑛+1 𝑥 𝑛 − 6 𝑦𝑛 𝑥 𝑛 = 0
𝑛=0 𝑛=0 𝑛=0
∞ ∞ ∞
1 𝑛 +2
1 𝑛 +1
𝑦𝑛+2 𝑥 − 𝑦𝑛+1 𝑥 −6 𝑦𝑛 𝑥 𝑛 = 0
𝑥2 𝑥
𝑛=0 𝑛=0 𝑛 =0
1 1
2
𝐺 𝑥 − 𝑦1 𝑥 − 𝑦0 − 𝐺 𝑥 − 𝑦0 − 6𝐺 𝑥 = 0 [𝑓𝑟𝑜𝑚 1 ]
𝑥 𝑥
1 1 𝑦1 𝑦0 𝑦0
𝐺 𝑥 2
− −6 − − 2 + = 0
𝑥 𝑥 𝑥 𝑥 𝑥
1 1 1 2 2 6𝑥 2 − 𝑥 + 1 2 1
𝐺 𝑥 2
− − 6 − − 2
+ = 0 ⇒ 𝐺 𝑥 2
= 2−
𝑥 𝑥 𝑥 𝑥 𝑥 𝑥 𝑥 𝑥
2
1 − 𝑥 − 6𝑥 2−𝑥
𝐺 𝑥 2
= 2
𝑥 𝑥
2−𝑥 2−𝑥
𝐺 𝑥 = 2
=
1 − 𝑥 − 6𝑥 1 − 3𝑥 1 + 2𝑥
2−𝑥 𝐴 𝐵
= +
1 − 3𝑥 1 + 2𝑥 1 − 3𝑥 1 + 2𝑥
2 − 𝑥 = 𝐴 2𝑥 + 1 + 𝐵 1 − 3𝑥 … 2
1
Put 𝑥 = − 2
in (2)
1 3 5 5
2− − = 𝐵 1+ ⇒ 𝐵= ⇒𝐵=1
2 2 2 2
1
Put 𝑥 = 3 in (2)
1 2 5 5
2− = 𝐴 +1 ⇒ 𝐴 = ⇒𝐴 = 1
3 3 3 3
1 1 1 1
𝐺 𝑥 = + = +
1 − 3𝑥 1 + 2𝑥 1 − 3𝑥 1 − −2𝑥

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

b) i) How many positive integers 𝒏 can be formed using the digits 𝟑, 𝟒, 𝟒, 𝟓, 𝟓, 𝟔, 𝟕 if 𝒏 has to exceed
𝟓𝟎𝟎𝟎𝟎𝟎𝟎?
Solution:
The positive integer 𝑛 exceeds 5000000 if the first digit is either 5 or 6 or 7.
If the first digit is 5 then the remaining six digits are 3,4,4,5,6,7.
Then the number of positive integers formed by six digits is
6!
= 360 [𝑆𝑖𝑛𝑐𝑒 4 𝑎𝑝𝑝𝑒𝑎𝑟𝑠 𝑡𝑤𝑖𝑐𝑒]
2!
If the first digit is 6 then the remaining six digits are 3,4,4,5,5,7.
Then the number of positive integers formed by six digits is

www.tranquileducation.weebly.com 4
 Anna University, Chennai, November/December 2010

6!
= 180 [𝑆𝑖𝑛𝑐𝑒 4 & 5 𝑎𝑝𝑝𝑒𝑎𝑟𝑠 𝑡𝑤𝑖𝑐𝑒]
2! 2!
If the first digit is 7 then the remaining six digits are 3,4,4,5,6,5.
Then the number of positive integers formed by six digits is
6!
= 180 [𝑆𝑖𝑛𝑐𝑒 4 & 5 𝑎𝑝𝑝𝑒𝑎𝑟𝑠 𝑡𝑤𝑖𝑐𝑒]
2! 2!
∴ The number of positive integers 𝑛 can be formed using the digits 3,4,4,5,5,6,7 if 𝑛 has to exceed
5000000 is 360 + 180 + 180 = 720.

ii) Find the number of integers between 1 and 250 both inclusive that are divisible by any of the
integers 2,3,5,7.
Solution:
Let 𝐴, 𝐵, 𝐶 and 𝐷 represents the integer from 1 to 250 that are divisible by 2,3,5 and 7 respectively.
250 250 250 250
𝐴 = = 125, 𝐵 = = 83, 𝐶 = = 50, 𝐷 = = 35
2 3 5 7
250 250 250 250
𝐴∩𝐵 = = 41, 𝐴 ∩ 𝐶 = = 25, 𝐴 ∩ 𝐷 = = 17, 𝐵 ∩ 𝐶 = = 16
2×3 2×5 2×7 3×5
250 250 250
𝐵∩𝐷 = = 11, 𝐶 ∩ 𝐷 = = 7, 𝐴 ∩ 𝐵 ∩ 𝐶 = =8
3×7 5×7 2×3×5
250 250 250
𝐴∩𝐵∩𝐷 = = 5, 𝐴 ∩ 𝐶 ∩ 𝐷 = = 3, 𝐵 ∩ 𝐶 ∩ 𝐷 = =2
2×3×7 2×5×7 3×5×7
250
𝐴∩𝐵∩𝐶∩𝐷 = =1
2×3×5×7
∴The number of integers between 1 and 250 both inclusive that are divisible by any of the
integers 2,3,5,7 is
𝐴∪𝐵∪𝐶∪𝐷 = 𝐴 + 𝐵 + 𝐶 + 𝐷 − 𝐴∩𝐵 − 𝐴∩𝐶 − 𝐴∩𝐷 − 𝐵∩𝐶 − 𝐵∩𝐷
− 𝐶∩𝐷 + 𝐴∩𝐵∩𝐶 + 𝐴∩𝐵∩𝐷 + 𝐴∩𝐶∩𝐷 + 𝐵∩𝐶∩𝐷 − 𝐴∩𝐵∩𝐶∩𝐷
𝐴 ∪ 𝐵 ∪ 𝐶 ∪ 𝐷 = 125 + 83 + 50 + 35 − 41 − 25 − 17 − 16 − 11 − 7 + 8 + 5 + 3 + 2 − 1
𝐴 ∪ 𝐵 ∪ 𝐶 ∪ 𝐷 = 193

13. a) i) Draw the complete graph 𝑲𝟓 with vertices 𝑨, 𝑩, 𝑪, 𝑫 𝐚𝐧𝐝 𝑬 . Draw all complete sub graph of
𝑲𝟓 with 4 vertices.
Solution:
A complete graph with five vertices 𝐾5 is shown below
𝐵

𝐴 𝑐

𝐸 𝐷
Complete sub graph of 𝐾5 with 4 vertices are

www.tranquileducation.weebly.com 5
 Anna University, Chennai, November/December 2010

𝐵
𝐴 𝑐
𝑐

𝐸 𝐷
𝐸 𝐷 𝐵

𝐵 𝐴
𝑐
𝐴

𝐸 𝐴 𝑐

𝐸 𝐷

ii) If all the vertices of an undirected graph are each of degree 𝒌, show that the number of edges of
the graph is a multiple of 𝒌 .
Solution:
Let 𝐺(𝑉, 𝐸) be a graph with 𝑛 vertices and 𝑒 edges.
Let 𝑣1 , 𝑣2 , … , 𝑣𝑛 be the 𝑛 vertices.
Given that all the vertices of G are each of degree 𝑘.
deg 𝑣1 = deg 𝑣2 = deg 𝑣3 = ⋯ = deg 𝑣𝑘 = 𝑘
By handshaking theorem,
𝑛

deg 𝑣𝑖 = 2𝑒
𝑖=1
deg 𝑣1 + deg 𝑣2 + deg 𝑣3 + ⋯ + deg 𝑣𝑛 = 2𝑒
𝑘 + 𝑘 + 𝑘 + ⋯ 𝑛𝑡𝑖𝑚𝑒𝑠 = 2𝑒
𝑛𝑘 = 2𝑒
𝑛
𝑒=𝑘
2

www.tranquileducation.weebly.com 6
 Anna University, Chennai, November/December 2010

∴ The number of edges of the graph 𝐺 is a multiple of 𝑘 .

b) i) Draw the graph with 5 vertices, 𝑨, 𝑩, 𝑪, 𝑫, 𝑬 such that 𝒅𝒆𝒈(𝑨) = 𝟑 , 𝑩 is an odd vertex,
𝒅𝒆𝒈(𝑪) = 𝟐 and 𝑫and 𝑬 are adjacent.

𝐴 𝐵

𝐸
𝐶 𝐷

ii) The adjacency matrices of two pairs of graph as given below. Examine the isomorphism of G and H
𝟎 𝟎 𝟏 𝟎 𝟏 𝟏
by finding a permutation matrix. 𝐀𝐆 = 𝟎 𝟎 𝟏 , 𝐀𝐇 = 𝟏 𝟎 𝟎
𝟏 𝟏 𝟎 𝟏 𝟎 𝟎
Solution:
We know that two simple graphs 𝐺1 and 𝐺2 are isomorphic iff their adjacency matrices 𝐴1 and 𝐴2 are
related by
𝑃𝐴1 𝑃 𝑇 = 𝐴2
[A matrix whose rows are the rows of the unit matrix, but not necessarily in their natural order, is called
Permutation matrix.]
0 0 1 0 1 1
AG = 0 0 1 , AH = 1 0 0
1 1 0 1 0 0
0 0 1
𝑃= 0 1 0
1 0 0

0 0 1 0 0 1 0 0 1
𝑃𝐴𝐺 𝑃 𝑇 = 0 1 0 0 0 1 0 1 0
1 0 0 1 1 0 1 0 0
1 1 0 0 0 1 0 1 1
= 0 0 1 0 1 0 = 1 0 0 𝐴𝐻
0 0 1 1 0 0 1 0 0
𝑃𝐴𝐺 𝑃 𝑇 = 𝐴𝐻
∴ The two graphs 𝐺 and 𝐻 are isomorphic.

14.a) i) If 𝑮,∗ is an abelian group, show that 𝒂 ∗ 𝒃 𝟐 = 𝒂𝟐 ∗ 𝒃𝟐 .

Proof:
𝑎 ∗𝑏 2 = 𝑎∗𝑏 ∗ 𝑎∗𝑏
= 𝑎 ∗ 𝑏 ∗ 𝑎 ∗ 𝑏 𝐴𝑠𝑠𝑜𝑐𝑖𝑎𝑡𝑖𝑣𝑒 𝑙𝑎𝑤
= 𝑎 ∗ 𝑎 ∗ 𝑏 ∗ 𝑏 𝐶𝑜𝑚𝑚𝑢𝑡𝑎𝑡𝑖𝑣𝑒 𝑙𝑎𝑤
= 𝑎 ∗ 𝑎 ∗ 𝑏 ∗ 𝑏 𝐴𝑠𝑠𝑜𝑐𝑖𝑎𝑡𝑖𝑣𝑒 𝑙𝑎𝑤
𝑎 ∗ 𝑏 2 = 𝑎2 ∗ 𝑏2

ii) Show that (𝒁, +,×) is an integral domain where 𝒁 is the set of all integers.

www.tranquileducation.weebly.com 7
 Anna University, Chennai, November/December 2010

Proof:
Closure:
∀𝑎, 𝑏 ∈ 𝑍 ⇒ 𝑎 + 𝑏 ∈ 𝑍
∀𝑎, 𝑏 ∈ 𝑍 ⇒ 𝑎 × 𝑏 ∈ 𝑍
∴ 𝑍 is closed under + and ×.
Associative:
∀𝑎, 𝑏, 𝑐 ∈ 𝑍 ⇒ 𝑎 + 𝑏 + 𝑐 = 𝑎 + 𝑏 + 𝑐
∀𝑎, 𝑏 ∈ 𝑍 ⇒ 𝑎 × 𝑏 × 𝑐 = 𝑎 × 𝑏 × 𝑐
∴ 𝑍 is associative under + and ×.
Identity:
Let 𝑒 ∈ 𝑍 be the identity element.
∀𝑎 ∈ 𝑍, 𝑎 + 𝑒 = 𝑒 + 𝑎 = 𝑎 ⇒ 𝑎 + 𝑒 = 𝑎 ⇒ 𝑒 = 0
∴ 0 ∈ 𝑍 is the identity element with respect to the binary operation +.
∀𝑎 ∈ 𝑍, 𝑎 × 𝑒 = 𝑒 × 𝑎 = 𝑎 ⇒ 𝑎 × 𝑒 = 𝑎 ⇒ 𝑒 = 1
∴ 1 ∈ 𝑍 is the identity element with respect to the binary operation +.
Inverse:
Let 𝑏 ∈ 𝑍 be the inverse element of 𝑎 ∈ 𝑍.
𝑎 + 𝑏 = 𝑏 + 𝑎 = 0 ⇒ 𝑎 + 𝑏 = 0 ⇒ 𝑏 = −𝑎 ∈ 𝑍
−𝑎 ∈ 𝑍 is the inverse of 𝑎 ∈ 𝑍
∴ Every element has its inverse in 𝑍 under binary operation +.
Commutative:
∀𝑎, 𝑏 ∈ 𝑍, 𝑎 + 𝑏 = 𝑏 + 𝑎
∀𝑎, 𝑏 ∈ 𝑍, 𝑎 × 𝑏 = 𝑏 × 𝑎
∴ 𝑍 is Commutative under + and ×.
Distributive:
∀𝑎, 𝑏, 𝑐 ∈ 𝑍, 𝑎 × 𝑏 + 𝑐 = 𝑎 × 𝑏 + 𝑎 × 𝑐
∴ × is distributive over +.
∀𝑎, 𝑏 ∈ 𝑍, 𝑎 × 𝑏 = 0 ⇒ 𝑎 = 0 𝑜𝑟 𝑏 = 0
∴ 𝑍 has no zero divisors.
∴ (𝑍, +,×) is an integral domain.

b) i) State and Prove Lagrange’s theorem.

Statement:
The order of a subgroup of a finite group is a divisor of the order of the group.
Proof:
Let 𝑎𝐻 and 𝑏𝐻 be two left cosets of the subgroup {𝐻,∗} in the group {𝐺,∗}.
Let the two cosets 𝑎𝐻 and 𝑏𝐻 be not disjoint.
Then let 𝑐 be an element common to 𝑎𝐻 and 𝑏𝐻 i.e., 𝑐 ∈ 𝑎𝐻 ∩ 𝑏𝐻
∵ 𝑐 ∈ 𝑎𝐻, 𝑐 = 𝑎 ∗ 𝑕1 , 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑕1 ∈ 𝐻 … (1)
∵ 𝑐 ∈ 𝑏𝐻, 𝑐 = 𝑏 ∗ 𝑕2 , 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑕2 ∈ 𝐻 … (2)
From (1) and (2), we have
𝑎 ∗ 𝑕1 = 𝑏 ∗ 𝑕2
𝑎 = 𝑏 ∗ 𝑕2 ∗ 𝑕1−1 … (3)
Let 𝑥 be an element in 𝑎𝐻
𝑥 = 𝑎 ∗ 𝑕3 , 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑕3 ∈ 𝐻
= 𝑏 ∗ 𝑕2 ∗ 𝑕1−1 ∗ 𝑕3 , 𝑢𝑠𝑖𝑛𝑔 (3)
−1
Since H is a subgroup, 𝑕2 ∗ 𝑕1 ∗ 𝑕3 ∈ 𝐻
Hence, (3) means 𝑥 ∈ 𝑏𝐻

www.tranquileducation.weebly.com 8
 Anna University, Chennai, November/December 2010

Thus, any element in 𝑎𝐻 is also an element in 𝑏𝐻. ∴ 𝑎𝐻 ⊆ 𝑏𝐻

Similarly, we can prove that 𝑏𝐻 ⊆ 𝑎𝐻
Hence 𝑎𝐻 = 𝑏𝐻
Thus, if 𝑎𝐻 and 𝑏𝐻 are disjoint, they are identical.
The two cosets 𝑎𝐻 and 𝑏𝐻 are disjoint or identical. …(4)
Now every element 𝑎 ∈ 𝐺 belongs to one and only one left coset of 𝐻 in 𝐺,
For,
𝑎 = 𝑎𝑒 ∈ 𝑎𝐻, 𝑠𝑖𝑛𝑐𝑒 𝑒 ∈ 𝐻 ⇒ 𝑎 ∈ 𝑎𝐻
𝑎 ∉ 𝑏𝐻, since 𝑎𝐻 and 𝑏𝐻 are disjoint i.e., 𝑎 belongs to one and only left coset of
𝐻 in 𝐺 i.e., 𝑎𝐻 … (5)
From (4) and (5), we see that the set of left cosets of 𝐻 in 𝐺 form the partition of
𝐺. Now let the order of 𝐻 be 𝑚.
Let 𝐻 = 𝑕1 , 𝑕2 , … , 𝑕𝑚 , 𝑤𝑕𝑒𝑟𝑒 𝑕𝑖 ′𝑠 are distinct
Then 𝑎𝐻 = 𝑎𝑕1 , 𝑎𝑕2 , … , 𝑎𝑕𝑚
The elements of 𝑎𝐻 are also distinct, for, 𝑎𝑕𝑖 = 𝑎𝑕𝑗 ⇒ 𝑕𝑖 = 𝑕𝑗 , which is not
true.
Thus 𝐻 and 𝑎𝐻 have the same number of elements, namely 𝑚.
In fact every coset of 𝐻 in 𝐺 has exactly 𝑚 elements.
Now let the order of the group {𝐺,∗} be 𝑛, i.e., there are 𝑛 elements in 𝐺
Let the number of distinct left cosets of 𝐻 in 𝐺 be 𝑝.
∴ The total number of elements of all the left cosets = 𝑝𝑚 = the total number
of elements of 𝐺. i.e., 𝑛 = 𝑝𝑚
i.e., 𝑚, the order of 𝐻 is adivisor of 𝑛, the order of 𝐺.

ii) If (𝒁, +) and (𝑬, +) where 𝒁 is the set all integers and 𝑬 is the set all even integers, show
that the two semi groups (𝒁, +) and (𝑬, +) are isomorphic.
Proof:
Let 𝑓: 𝑍, + → (𝐸, +) be the mapping between the two semi groups (𝑍, +) and 𝐸, + defined by
𝑓 𝑥 = 2𝑥, ∀𝑥 ∈ 𝑍
𝑓 is one to one:
𝑓 𝑥 =𝑓 𝑦
⇒ 2𝑥 = 2𝑦
⇒𝑥=𝑦
∴ 𝑓is one to one.
𝑓 is onto:
𝑦
Let 𝑓 𝑥 = 𝑦 ⇒ 𝑦 = 2𝑥 ⇒ 𝑥 = 2 ∈ 𝑍 ∵ 𝑦 𝑖𝑠 𝑎𝑛 𝑒𝑣𝑒𝑛 𝑛𝑢𝑚𝑏𝑒𝑟
𝑥
∴ ∀𝑥 ∈ 𝐸 there is a preimage 2 ∈ 𝑍.
∴ 𝑓 is onto.
𝑓 is homomorphism:
∀𝑥, 𝑦 ∈ 𝑍, 𝑓 𝑥 + 𝑦 = 2 𝑥 + 𝑦 = 2𝑥 + 2𝑦 = 𝑓 𝑥 + 𝑓(𝑦)
𝑓 𝑥 + 𝑦 = 𝑓 𝑥 + 𝑓(𝑦)
∴ 𝑓is homomorphism.
∴ 𝑓is isomorphism.
∴The two semi groups (𝑍, +) and (𝐸, +) are isomorphic.

15. a) i) Show that (𝑵, ≤) is a partially ordered set where 𝑵 is set of all positive integers and ≤ is
defined by 𝒎 ≤ 𝒏 iff 𝒏 − 𝒎 is a non-negative integer.

www.tranquileducation.weebly.com 9
 Anna University, Chennai, November/December 2010

Proof:
Let R be the relation 𝑚 ≤ 𝑛 𝑖𝑓𝑓 𝑛 − 𝑚 is a non-negative integer.
𝑖) ∀𝑥 ∈ 𝑁, 𝑥 − 𝑥 = 0 𝑖𝑠 𝑎𝑙𝑠𝑜 𝑎 𝑛𝑜𝑛 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 ⇒ 𝑥, 𝑥 ∈ 𝑅
∴ 𝑅 is reflexive.
𝑖𝑖)∀𝑥, 𝑦 ∈ 𝑁,
𝑥, 𝑦 ∈ 𝑅 & 𝑦, 𝑥 ∈ 𝑅
⇒ 𝑥 − 𝑦 𝑖𝑠 𝑎 𝑛𝑜𝑛 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 & 𝑦 − 𝑥 𝑖𝑠 𝑎 𝑛𝑜𝑛 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒 𝑖𝑛𝑡𝑒𝑔𝑒𝑟
It is possible only if 𝑥 − 𝑦 = 0 ⇒ 𝑥 = 𝑦
𝑥, 𝑦 ∈ 𝑅 & 𝑦, 𝑥 ∈ 𝑅 ⇒ 𝑥 = 𝑦
∴ 𝑅 is Anti Symmetric.
𝑖𝑖𝑖)∀𝑥, 𝑦, 𝑧 ∈ 𝑁, 𝑥, 𝑦 ∈ 𝑅 𝑎𝑛𝑑 𝑦, 𝑧 ∈ 𝑅
𝑥−𝑧 = 𝑥−𝑦 + 𝑦−𝑧
Since sum of two non-negative integer is also a non-negative integer.
⇒ 𝑥 − 𝑧 𝑖𝑠 𝑎𝑙𝑠𝑜 𝑎 𝑛𝑜𝑛 − 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 ⇒ 𝑥, 𝑧 ∈ 𝑅
𝑥, 𝑦 ∈ 𝑅 𝑎𝑛𝑑 𝑦, 𝑧 ∈ 𝑅 ⇒ 𝑥, 𝑧 ∈ 𝑅
∴ 𝑅 is Transitive.
∴ (𝑵, ≤) is a partially ordered set.

ii) In a Boolean algebra, prove that 𝒂 ∧ 𝒃 ′ = 𝒂′ ∨ 𝒃′.

Solution: Let 𝑎, 𝑏 ∈ (𝐵,∧,⊕,′ , 0,1)
To prove 𝑎 ∧ 𝑏 ′ = 𝑎′ ∨ 𝑏′
𝑎 ∧ 𝑏 ∨ 𝑎′ ∨ 𝑏′ = 𝑎 ∨ 𝑎′ ∨ 𝑏′ ∧ 𝑏 ∨ 𝑎′ ∨ 𝑏′
= 𝑎 ∨ 𝑎 ′ ∨ 𝑏′ ∧ 𝑎′ ∨ 𝑏′ ∨ 𝑏
= 𝑎 ∨ 𝑎′ ∨ 𝑏′ ∧ 𝑎 ′ ∨ 𝑏′ ∨ 𝑏
= 1 ∨ 𝑏′ ∧ 𝑎′ ∨ 1 = 1 ∧ 1
𝑎 ∧ 𝑏 ∨ 𝑎′ ∨ 𝑏′ = 1 … (1)
𝑎 ∧ 𝑏 ∧ 𝑎′ ∨ 𝑏′ = 𝑎 ∧ 𝑏 ∧ 𝑎′ ∨ 𝑎 ∧ 𝑏 ∧ 𝑏′
= 𝑏 ∧ 𝑎 ∧ 𝑎′ ∨ 𝑎 ∧ 𝑏 ∧ 𝑏′
= 𝑏 ∧ 𝑎 ∧ 𝑎′ ∨ 𝑎 ∧ 𝑏 ∧ 𝑏′
= 𝑏∧0 ∨ 𝑎∧0 =0∨0
𝑎 ∧ 𝑏 ∧ 𝑎′ ∨ 𝑏′ = 0 … (2)
𝐹𝑟𝑜𝑚 1 𝑎𝑛𝑑 2 𝑤𝑒 𝑔𝑒𝑡,
𝑎 ∧ 𝑏 ′ = 𝑎′ ∨ 𝑏′

b) i) In a Lattice (𝑳, ≤) , prove that 𝒙 ∨ 𝒚 ∧ 𝒛 ≤ 𝒙 ∨ 𝒚 ∧ ( 𝒙 ∨ 𝒛 ).

Proof:
From the definition of LUB,
𝑥 ∨ 𝑦 ≥ 𝑥 & 𝑥 ∨ 𝑧 ≥ 𝑥 ⇒ 𝑥 ∨ 𝑦 ∧ 𝑥 ∨ 𝑧 ≥ 𝑥 … (1)
𝑦 ∧𝑧 ≤ 𝑦 ≤ 𝑥 ∨𝑦… 2
𝑦∧𝑧 ≤ 𝑧 ≤ 𝑥 ∨𝑧… 3
From (2) and (3), we get
𝑥 ∨ 𝑦 ∧ 𝑥 ∨ 𝑧 ≥ 𝑦 ∧ 𝑧… 4
From (1) and (4), we get
𝑥∨ 𝑦∧𝑧 ≤ 𝑥∨ 𝑦 ∧ 𝑥∨ 𝑧

ii) If 𝑺𝟒𝟐 is the set all divisors of 42 and 𝑫 is the relation “divisor of” on 𝑺𝟒𝟐 , prove that 𝑺𝟒𝟐 , 𝑫 is a

www.tranquileducation.weebly.com 10
 Anna University, Chennai, November/December 2010

complemented Lattice.
Solution:
𝑆42 = 1,2,3,6,7,14,21,42
The Hasse diagram for 𝑆42 , 𝐷 is

42

6 21
14

2 3 7

1
1 ∨ 42 = 42, 1 ∧ 42 = 1
2 ∨ 21 = 42, 2 ∧ 21 = 1
3 ∨ 14 = 42, 3 ∧ 14 = 1
7 ∨ 6 = 42, 7 ∧ 6 = 1
The complement of 1 is 42, The complement of 42 is 1, The complement of 2 is 21, The complement of
21 is 2, The complement of 3 is 14, The complement of 14 is 3, The complement of 7 is 6, The
complement of 6 is 7. Since all the elements in (𝑆24 , 𝐷) has a complement,
∴ (𝑆24 , 𝐷) is a complemented lattice.

www.tranquileducation.weebly.com 11