MC0082 solved Assignment

Master of Computer Application (MCA) – Semester 5

MC0082 –Theory of Computer Science – 4 Credits

(Book ID: B0970)

Assignment Set – 1 (60 Marks)

________________________________________________________________________________

1. Define the concept of equivalence relation. Give at least two examples of equivalence

relation.

Ans.

Definition. A relation R on a set A is an equivalence relation if and

only if R is

1. reflexive,
2. symmetric, and
3. transitive.

The definition is motivated by observing that any process of “identification” must behave somewhat like the equality relation, and the equality relation satisfies the reflexive (x = x for all x), symmetric (x = y implies y = x), and transitive (x = y and y = z implies x = z) properties.

Example.

1. Let R be the relation on the set R real numbers defined by xRy iff x − y is an integer. Prove that R is an equivalence relation on R.

Proof.

I. Reflexive: Suppose x ∈ R. Then x − x = 0, which is an integer. Thus, xRx.

II. Symmetric: Suppose x, y ∈ R and xRy. Then x − y is an integer. Since

y − x = −(x − y), y − x is also an integer. Thus, yRx.

III. Suppose x, y ∈ R, xRy and yRz. Then x − y and y − z are integers. Thus,

the sum (x − y) + (y − z) = x − z is also an integer, and so xRz.

Thus, R is an equivalence relation on R. #

2. Let R be the relation on the set of real numbers R in Example

1. Prove that if xRx ' and yRy' , then (x + y)R(x' + y').

Proof. Suppose xRx ' and yRy '. In order to show that (x+y)R(x'+y'), we must show that (x + y) − (x ' + y') is an integer. Since

(x + y) − (x'+ y') = (x − x') + (y − y'),

and since each of x−x ' and y −y ' is an integer (by definition of R), (x−x') + (y −y ')

is an integer. Thus, (x + y)R(x ' + y').

2. Prove by the method of mathematical induction that

Ans.

Base Step:

Let n=0 then the sum of the left side is 0

Since there is nothing to add the expression on the right side is also 0

If n=1 then left side is 1

& right side =

Hence the result is true for n=1

Induction Hypothesis:

Assume that the result to be true for n=m then

Adding the (m+1)^th term i.e (m+1)³ to both side of the above equation

There for the result is true for n=m+1. Hence the mathematical induction, the given result is true for all positive integer n.

3. Prove that a graph G is connected if and only if it has a spanning tree.

Ans.

Proof: Let G be a connected graph. If G has no circuit, then G is a spanning

tree. If G has a circuit, then delete an edge from this circuit. If till leaves the

graph connected. If there are more circuits, repeat the operation till an edge

from the last circuit is deleted, leaving the graph connected, circuitless, and

contains all the vertices of G. Thus the subgraph obtained is a spanning tree

of G. Hence every connected graph has at least one spanning tree.

4. Prove that the relation “” is an equivalence relation

Ans.

Consider relation defined above is an equivalence relation on Z.

Let a € Z.

Reflexive: since m divides a-a=0, we have

Symmetric: Let

m divides a- b

m divides –(a-b)

m divides b-a

Transitivity: Let a, b, c Z such that , ,

m divides a-b, and n divides b-c

m divides (a-b)+(b-c)

m divides a-c

Hence the relation is a equivalence relation.

for any issue write me  @ rsravishri30@gmail.com