Discrete mathematics(dm) question papers and important questions in Mca. pune university
a) Show lhal the following formulae are equivalent.
(A -» B) A (C —»B) <=> (A v Q —» B
b) Let P : It rains
Q : The atmospheric humidity increases. Write the following statements in symbolic form :
i) Atmospheric humidity increases only if it rains.
ii) Sufficient condition for it to rain is that atmospheric humidity increases.
iii) Necessary condition for it to rain is that atmospheric humidity increases.
iv) Whenever atmospheric humidity increases it rains.
c) Determine whether the operation * defined on the following sets is the binary
operation or not. 6
i) A = I where a * b = a + b.
ii) A = I where a * b = max (a, b)
d) GivenA= { 1,2,3,4,5 ) and B = { 1,3, 5). Let R be the relation from A -> B
defined by "x is greater than y" .
e) Show that the sum of degrees of all vertices in a graph is twice the number ofedges.
a) Construct Truth fables for the following :
i) PVI(PAQ)
ii) (PvQ)vlR
iii) 1(PV1Q)
b) Rewrite the following propositions using the symbols 3 and V.
i) There are some successful students who are not clever.
ii) All cats like cream.
c) Obtain the Principal Conjunctive Normal Form (PCNF) for the following
>->(Q<->R).
d) Show that the given set of premises is inconsistent.
A —»(B —»C);D —>(B A |C) and A A D.
3. a) Let A be the set of positive factors of 36 and let < be the relation divides; i.e.,
< = {< x, y >' x, ye A and x divides y} . Show that < is totally ordered on A. Also draw the Hasse diagram.
b) Use Warshall's algorithm to find the transitive closure of the relation R = {<1,2>. <2, 3>, <3,4>,<2, l>} onA = {1.2, 3,4).
c) Let R = {<1, 2>, <3, 4>, <2, 2>) and S = f<4, 2>, <2, 5>, <3. 1>, <1. 3>|. Find S • Rand R • R • R.
d) Show that the set of integers is countable.
4. a) If A = {1.2, 3,4 J and B = (a, b, c, d}, determine if the following functions are
one to one, onto or both.
i) f= (<l,a>, <2, a>, <3. b>,<4, d>)
ii) g = (<1, c>, <2, b>, <3, a>, <4, a>|
iii) h - (<1, a>, <2, b>, <3, a>, <4, c>)
b) Let < G, *> and <H, A> be groups and g : G -» H be a homomorphism. Prove that kernel of g is a normal subgroup of G.
c) Let < I, +> be the group and Hj the set of all multiples of 3. Show that H3 is a subgroup of 1. Determine all the left cosets of H, in I, where 1 is the set of all integers.
a) Show that the Graphs G and H are isomorphic.
b) Count the number of vertices, number of edges and number of region of each of ihe following planar graphs :
c) Show thai the maximum number edges in a simple graph with n vertices is n(n-l)/2.
d) Draw the following graphs :
i) Two ternary trees with 9 leaves
ii) Two binary trees with 7 leaves
a) Show the following equivalence. P-*(OvR)»(P-*Q)v(P-»R)
b) If the universe of discourse is the set (a, b, c) eliminate the quantifiers in the following formulae.
i) (x) (P(x)VQ(x))
ii) (x) R (x) A(x) S(x).
c) Write down the composition tables for (z7 +7} and i^'i, x7) where
z;-z7:([o]}. ^
d) Let R be a transitive and reflexive relation on A. Let T be a relation on A such that (a,b)is in t if and only if both (a,b) and {b,a)are in R. Show that T is an equivalence relation on A. 5
e) Let N denote the set of all natural numbers. Show thai NxN is denumerable.
0 A connected planner graph has 9 vertices having degrees 2, 2, 2. 3, 3. 3, 4, 4
and 5. 4
i) How many edges are there ?
ii) How many faces are there ?
2. a) Construct truth tables for the following :
i) Pv (PAR)
ii) (P A lQ)vR
iii) ~~|(pA~~iQ)
b) Rewrite the following propositions using the symbols 3 and V-
i) All good students study hard.
ii) There is a triangle whose sum of angles # 180-
c) Obtain the Principal Disjunctive Normal Form ( PDNF) for the following :
~]pv("">->(QV(Q-»"!R)) rjn'Aunap* gfllwoHol -yiJ wort? (n
d) Show the validity of the conclusion G v H is valid from the premises
BAC.(BHC)^(HVG)
3. a) Let A be the set of positive factors of 72 and let < be the relation devides;
i.e., < = I <x, y>| x, y e A and x divides y ). Show that < is totally ordered on A. Also draw the Hasse diagram.
b) Use Warshall's algorithm to find the transitive closure of the relation
R = I (1.3). (1.1), (3.1), (1,2), (3,3), (4,4)] on A = {1, 2, 3, 4 ]
c) Let R = I < 1, 2>, <3, 4>, <2, 3> ( and S = (<4, 2>, <2, 5>, <3. 1>, <l, 3> ). Find S« (S.R) and (R*S) • R.
d) Let A = { 1,2,3} determine whether the relations R and S whose matrices MK and Ms are given are equivalence relations or not.
i) MR =I 0 0 0 I I 0 1 I
ii) MS =
I 0 I
0 1 0
1 0 0
4. a) If A = {1, 2, 3, 4( and B - {a, b. c, d), determine if the following functions are one to one. onto or both.
i) f = { <1, a>, <2, a>, < 3, b>, <4, d>|
ii) g = |< I, c>. < 2. b>, <3, a>, <4, a>]
iii) h = (<l. a>, <2, b>, <3, a>. <4, c>)
b) Show that if (H. *) is a sub group of (G, *), then a * H = H if and only if a eH.
c) Write the code words generated by H, where :
(\ 1 0 1 0 0\ H_ 0 1 10 10 ] 0 I 0 0 I
V /
What is the minimum weight of the non zero code word in above code words ?
How many errors are detected by this group code ? 7
5. a) Show that the graphs G and H are isomorphic : 6
c) Show that if G is a simple graph with n vertices and k components, then G
can have at most (n - k) (n - k +1) 12 edges. 6
d) Draw the following graphs : 4
i) Complete graphs with 4 and 5 vertices
ii) Simple graph with 2 and 4 vertices.
B/l 1/07/2,940
MT-11: DISCRETE MATHEMATICS (New: 2005 Pattern)
ime: 3 Hours
Max. Marks: 70
N.B.: Question No. 1 is compulsory and attempt any 2 questions out of remaining 4.
1. a) Show the following equivalence. P-»(QvR)<=> (P->Q)V(P-»R).
b) Let I7 be the set of integers modulo 7; i.e; I7 = {0, 1, 2, 3, 4, 5, 6}. Define f: I? -»I7 by f(x) = 2x (mod 7). Determine whether the function f is one-one and onto.
c) Let <G, * > be a group and a GG. Let f: G —» G be given by f(x) = a * x * a-1 for every x e G. Prove that f is an isomorphism of G onto G.
d) If the universe of discourse is the set ( a, b, c}, eliminate the quantifiers in the following formulas.
i) (x) (P (x) -> Q(x)) ii) (x) R(x) A (X) S(x). ' ^ ( a
e) Let A be the set of positive factors of 45, and let < be the relation divides;
i.e; < = ( <x, y> | x, y e A and x divides y). Show that < is a totally ordered
relation on A. Also draw the Hasse diagram.
0 Determine adjacency and incidence matrices of the following graph.
2. a) Let A = { 1, 2, 3). Let R, S be relations on A whose matrices are
[I 0 1 [1 0 o]
1 1 1 , Mc = 0 I 0
0 I Oj 9 1 0 1
Find MS0R. Is SOR reflexive ? Is it symmetric ?
b) Use Warshall's algorithm, to find the transitive closure of the relation R = ( (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)) on A = { 1, 2, 3,4).
c) Show that the set of all integers is a denumerable set.
d) Let A = {1, 2, 3, 4) and R = {(1, 1), (1,4), (2, 2), (3, 3), (4, 1), (4,4)}. Prove that R is an equivalence relation on A. Find the equivalence classes of elements of A.
3. a) Test the validity of the following argument.
If Tina marries Rahul, she will be in Pune. If Tina marries Ramcsh, she will be in Mumbai. If she is either in Pune or Mumbai, she will definitely be settled in life. She is not settled in life.Thus she did not marry Rahul or Ramesh.
b) Obtain disjunctive normal form of P A (P ->Q).
c) Show the following implication without constructing the truth table. P -*Q P —» (P A Q)
d) Prove that (3x) (P (x) A Q (X)) => (3x) P (x) A (3X) Q(X).
4. a) Determine all the binary operations on the set (0, 1). Give their composition
tables.
b) Show that the set N of natural numbers is a semigroup under the operation x * y = max {x, y}. Is it a monoid ?
c) Let H=
1 1 <> 1 0 0 o I 1 0
1
0
0 0
1
0 0
1
be a parity check matrix. Decode the following words relative to a maximum likehood decoding function associated with eH.
i) 011001
ii) 101011
iii) 111010
d) Let G be a group and aeG. Show that H = (an | n is an integer) is a
subgroup of G. 4
5. a) Attempt each of the following: 8
i) Define a complete graph. Draw a complete graph on 5 vertices (nodes).
ii) Define a complete bipartite graph. Draw a complete bipartite graph on
5 vertices.
iii) Define the complement of a simple graph.
c) Attempt each of the following:
i) Draw 2 rooted trees with 5 nodes.
ii) Draw 2 binary trees with 6 leaves.
iii) Draw two ternary trees with 11 leaves.
7(POQ)O(PVQ)A7(PAO)
b) Let X = { 2, 3, 6, 12, 24, 36) and the relation < be such that X ^ Y if X divides Y. Draw the hasse diagram of < X, < >.
c) R is the additive group of real numbers and R+ the multiplicative group of
positive real no's, the map f: R -> R* defined by f (x) = ex V x e R. Does f(x)
defines isomorphism ?
d) A connected planar graph has 9 vertices having degrees 2, 2, 2, 3, 3, 3, 4, 4 and 5. How many edges are there ? How many faces are there ?
e) Determine whether the conclusion C is valid in the following when H,, H2
are premises. 5
i) H, : PVQ H,: P -» R H3:Q-»R C:R
I ii) H, : P (Q -> R) : R C : P
0 Show that the maximum number of edges in a simple graph with n-vcrtices is "(n-1)
2 " 5
2. a) Obtain the principal disjunctive normal form of
(PAQ)V(7PAR)V(QAR) 5
b) Show the following equivalence without constructing truth table.
((PAQAA)->C)A(A->(PVQVC))«(AA(POQ))->C 5
c) Show that (3x)M(x) follows logically from the premises 5
1 (x)(H(x)-»M(x))&(3x)H(x)
d) Test the validity of the following arguments :
If I study, then I will not fail in mathematics. If I do not play basket ball, then
I will study. But I fail in mathematics. Therefore, I must have played Basket
ball.
[3180] - 104 -2
3. a) Let the compatibility relation on a set {x,,x2 x6( be given by the matrix.
X2 1
X3 1 1
X4 0 ■ 0 1
X5 0 0 1 1
X6 1 0 1 0 1
x. \ X3 X4 X5
Draw the graph and find the maximum compatibility blocks of the relation.
b) Let A = (a, b, c} and p(A) its power set. Let Q be the inclusion relation on
the elements p(A). Show that (p(A), c) is a partially ordered set. Draw the
hasse diagram of (p(A), c). Find the least and greatest members in p(A) if they exist.
c) Given A = {1, 2, 3, 4} and R = { <2, 2>, <2, 4>, <1, 3>, <3, 2>} Find transitive closure of R.
d) Let X = {1, 2, 3) and f, g and h be functions from X to X given by f = {<1, 2>, <2, 3>, <3, 1>} g = {<1, 2>, <2, 1>, <3, 3>} h= {<1, 1>, <2, 2>, <3, 1>}
find
0 fog, gof are they equal ii) fogoh and fohog.
4. a) Let <G, *> be a group and a e G. Let f:G -> G be given by f (x) = axa-1 for every x s G. Prove that f is an isomorphism of G onto G.
b) Find the left cosets of ([0], [3]) in the group <Z6, + 6>.
c) Consider the (2,6) encoding function e:
e (00) = 000000, e (10) = 101010, e (01) = 011110, e (11) = 111000
i) Find the minimum distance.
ii) How many errors will e detect ?
d) Let f: IxI—> I, where I is set of integers and f (x, y) = x*y
= x + y^xy
Show that the binary operation * is commutative and associative. Find the identity element and indicate inverse of each clement.
4 of degree 2. Draw two such graphs.
Determine whether the following graphs are isomorphic or not.
a) Determine the number of edges in a graph with 6 nodes, 2 of degree 4 and b)
Represent the following using a binary tree.
(3x-5z£ a(2b+-c2)
ii) (3.(l-x)) + (4 + (7-(y + z)).(7 + (x + y))).
What are the total numbers of nodes in a full binary tree with 20 leaves ?
1. a) Show that the truth value of the following formula is independent of their components.
((P->Q)A(Q->R))->(P-*R)
b) Let A be the set of positive factors of 45 and let< be the relation divides,
i.e. < = (<x.y>/x e A, y e A A (x divides y) ).
Show that < is a totally ordered relation on A. Also draw the Hassc diagram.
c) Let T be the set of all even integers. Show that the semigroups (z, +) and (T, +) an isomorphic.
d) Show that the maximum no. of edges in a simple graph with n vertices is
n(n-i)
2
e) Let z be the set of integers and let R be the relation called "congruence modulo 3" defined by
R = {<x, y>/x€ZAyezA(x-y)is divisible by 3} Determine the equivalence classes generated by the elements of z.
2. a)
Show that R A (P V Q) is a valid conclusion from the premises PvQ,Q->R,P->M&lM. •
Show that the conclusion C follows from the premises H,, Hr
i) H, : P->(Q~>R) H2 :R C:P
ii) Hl : R H2:Pv^P C:R
Show that the following set of premises are inconsistent
A->(B-^C),D->(BA"|C),AAD.
c) Obtain the PCNF of the following formula (P->(QAR))AnP-*(-»QA-*R))
d) "Every computer has a CD drive. Some computers have floppy drive. Therefore some computers have both CD and a floppy drive." Verify the above argument is valid or not.
. a) Find all upper bounds, lower bounds, least upper bounds, greatest lower bounds of B = { c, d, e } for the poset whose Ilasse diagram is
b) Use Warshall's algorithm to find the transitive closure of the relation R = ( < 1,2 > <2, 1 > <2, 3 > <3,4> } on A = { 1, 2, 3, 4 )
c) Show that the set N x N is dcnumcrable.
d) Let the compatibility relation on a set ( x,, x2, x, x6 ) be given by the
matrix.
*2 1
1 1
*4 0 0 1
0 0 1 1
*6 1 0 1 0 1
x. x2 x3 x4 x5
Draw the graph and find the maximal compatibility blocks of the relation.
a) Show lhal the following formulae are equivalent.
(A -» B) A (C —»B) <=> (A v Q —» B
b) Let P : It rains
Q : The atmospheric humidity increases. Write the following statements in symbolic form :
i) Atmospheric humidity increases only if it rains.
ii) Sufficient condition for it to rain is that atmospheric humidity increases.
iii) Necessary condition for it to rain is that atmospheric humidity increases.
iv) Whenever atmospheric humidity increases it rains.
c) Determine whether the operation * defined on the following sets is the binary
operation or not. 6
i) A = I where a * b = a + b.
ii) A = I where a * b = max (a, b)
d) GivenA= { 1,2,3,4,5 ) and B = { 1,3, 5). Let R be the relation from A -> B
defined by "x is greater than y" .
e) Show that the sum of degrees of all vertices in a graph is twice the number ofedges.
a) Construct Truth fables for the following :
i) PVI(PAQ)
ii) (PvQ)vlR
iii) 1(PV1Q)
b) Rewrite the following propositions using the symbols 3 and V.
i) There are some successful students who are not clever.
ii) All cats like cream.
c) Obtain the Principal Conjunctive Normal Form (PCNF) for the following
>->(Q<->R).
d) Show that the given set of premises is inconsistent.
A —»(B —»C);D —>(B A |C) and A A D.
3. a) Let A be the set of positive factors of 36 and let < be the relation divides; i.e.,
< = {< x, y >' x, ye A and x divides y} . Show that < is totally ordered on A. Also draw the Hasse diagram.
b) Use Warshall's algorithm to find the transitive closure of the relation R = {<1,2>. <2, 3>, <3,4>,<2, l>} onA = {1.2, 3,4).
c) Let R = {<1, 2>, <3, 4>, <2, 2>) and S = f<4, 2>, <2, 5>, <3. 1>, <1. 3>|. Find S • Rand R • R • R.
d) Show that the set of integers is countable.
4. a) If A = {1.2, 3,4 J and B = (a, b, c, d}, determine if the following functions are
one to one, onto or both.
i) f= (<l,a>, <2, a>, <3. b>,<4, d>)
ii) g = (<1, c>, <2, b>, <3, a>, <4, a>|
iii) h - (<1, a>, <2, b>, <3, a>, <4, c>)
b) Let < G, *> and <H, A> be groups and g : G -» H be a homomorphism. Prove that kernel of g is a normal subgroup of G.
c) Let < I, +> be the group and Hj the set of all multiples of 3. Show that H3 is a subgroup of 1. Determine all the left cosets of H, in I, where 1 is the set of all integers.
a) Show that the Graphs G and H are isomorphic.
b) Count the number of vertices, number of edges and number of region of each of ihe following planar graphs :
c) Show thai the maximum number edges in a simple graph with n vertices is n(n-l)/2.
d) Draw the following graphs :
i) Two ternary trees with 9 leaves
ii) Two binary trees with 7 leaves
a) Show the following equivalence. P-*(OvR)»(P-*Q)v(P-»R)
b) If the universe of discourse is the set (a, b, c) eliminate the quantifiers in the following formulae.
i) (x) (P(x)VQ(x))
ii) (x) R (x) A(x) S(x).
c) Write down the composition tables for (z7 +7} and i^'i, x7) where
z;-z7:([o]}. ^
d) Let R be a transitive and reflexive relation on A. Let T be a relation on A such that (a,b)is in t if and only if both (a,b) and {b,a)are in R. Show that T is an equivalence relation on A. 5
e) Let N denote the set of all natural numbers. Show thai NxN is denumerable.
0 A connected planner graph has 9 vertices having degrees 2, 2, 2. 3, 3. 3, 4, 4
and 5. 4
i) How many edges are there ?
ii) How many faces are there ?
2. a) Construct truth tables for the following :
i) Pv (PAR)
ii) (P A lQ)vR
iii) ~~|(pA~~iQ)
b) Rewrite the following propositions using the symbols 3 and V-
i) All good students study hard.
ii) There is a triangle whose sum of angles # 180-
c) Obtain the Principal Disjunctive Normal Form ( PDNF) for the following :
~]pv("">->(QV(Q-»"!R)) rjn'Aunap* gfllwoHol -yiJ wort? (n
d) Show the validity of the conclusion G v H is valid from the premises
BAC.(BHC)^(HVG)
3. a) Let A be the set of positive factors of 72 and let < be the relation devides;
i.e., < = I <x, y>| x, y e A and x divides y ). Show that < is totally ordered on A. Also draw the Hasse diagram.
b) Use Warshall's algorithm to find the transitive closure of the relation
R = I (1.3). (1.1), (3.1), (1,2), (3,3), (4,4)] on A = {1, 2, 3, 4 ]
c) Let R = I < 1, 2>, <3, 4>, <2, 3> ( and S = (<4, 2>, <2, 5>, <3. 1>, <l, 3> ). Find S« (S.R) and (R*S) • R.
d) Let A = { 1,2,3} determine whether the relations R and S whose matrices MK and Ms are given are equivalence relations or not.
i) MR =I 0 0 0 I I 0 1 I
ii) MS =
I 0 I
0 1 0
1 0 0
4. a) If A = {1, 2, 3, 4( and B - {a, b. c, d), determine if the following functions are one to one. onto or both.
i) f = { <1, a>, <2, a>, < 3, b>, <4, d>|
ii) g = |< I, c>. < 2. b>, <3, a>, <4, a>]
iii) h = (<l. a>, <2, b>, <3, a>. <4, c>)
b) Show that if (H. *) is a sub group of (G, *), then a * H = H if and only if a eH.
c) Write the code words generated by H, where :
(\ 1 0 1 0 0\ H_ 0 1 10 10 ] 0 I 0 0 I
V /
What is the minimum weight of the non zero code word in above code words ?
How many errors are detected by this group code ? 7
5. a) Show that the graphs G and H are isomorphic : 6
c) Show that if G is a simple graph with n vertices and k components, then G
can have at most (n - k) (n - k +1) 12 edges. 6
d) Draw the following graphs : 4
i) Complete graphs with 4 and 5 vertices
ii) Simple graph with 2 and 4 vertices.
B/l 1/07/2,940
MT-11: DISCRETE MATHEMATICS (New: 2005 Pattern)
ime: 3 Hours
Max. Marks: 70
N.B.: Question No. 1 is compulsory and attempt any 2 questions out of remaining 4.
1. a) Show the following equivalence. P-»(QvR)<=> (P->Q)V(P-»R).
b) Let I7 be the set of integers modulo 7; i.e; I7 = {0, 1, 2, 3, 4, 5, 6}. Define f: I? -»I7 by f(x) = 2x (mod 7). Determine whether the function f is one-one and onto.
c) Let <G, * > be a group and a GG. Let f: G —» G be given by f(x) = a * x * a-1 for every x e G. Prove that f is an isomorphism of G onto G.
d) If the universe of discourse is the set ( a, b, c}, eliminate the quantifiers in the following formulas.
i) (x) (P (x) -> Q(x)) ii) (x) R(x) A (X) S(x). ' ^ ( a
e) Let A be the set of positive factors of 45, and let < be the relation divides;
i.e; < = ( <x, y> | x, y e A and x divides y). Show that < is a totally ordered
relation on A. Also draw the Hasse diagram.
0 Determine adjacency and incidence matrices of the following graph.
2. a) Let A = { 1, 2, 3). Let R, S be relations on A whose matrices are
[I 0 1 [1 0 o]
1 1 1 , Mc = 0 I 0
0 I Oj 9 1 0 1
Find MS0R. Is SOR reflexive ? Is it symmetric ?
b) Use Warshall's algorithm, to find the transitive closure of the relation R = ( (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)) on A = { 1, 2, 3,4).
c) Show that the set of all integers is a denumerable set.
d) Let A = {1, 2, 3, 4) and R = {(1, 1), (1,4), (2, 2), (3, 3), (4, 1), (4,4)}. Prove that R is an equivalence relation on A. Find the equivalence classes of elements of A.
3. a) Test the validity of the following argument.
If Tina marries Rahul, she will be in Pune. If Tina marries Ramcsh, she will be in Mumbai. If she is either in Pune or Mumbai, she will definitely be settled in life. She is not settled in life.Thus she did not marry Rahul or Ramesh.
b) Obtain disjunctive normal form of P A (P ->Q).
c) Show the following implication without constructing the truth table. P -*Q P —» (P A Q)
d) Prove that (3x) (P (x) A Q (X)) => (3x) P (x) A (3X) Q(X).
4. a) Determine all the binary operations on the set (0, 1). Give their composition
tables.
b) Show that the set N of natural numbers is a semigroup under the operation x * y = max {x, y}. Is it a monoid ?
c) Let H=
1 1 <> 1 0 0 o I 1 0
1
0
0 0
1
0 0
1
be a parity check matrix. Decode the following words relative to a maximum likehood decoding function associated with eH.
i) 011001
ii) 101011
iii) 111010
d) Let G be a group and aeG. Show that H = (an | n is an integer) is a
subgroup of G. 4
5. a) Attempt each of the following: 8
i) Define a complete graph. Draw a complete graph on 5 vertices (nodes).
ii) Define a complete bipartite graph. Draw a complete bipartite graph on
5 vertices.
iii) Define the complement of a simple graph.
c) Attempt each of the following:
i) Draw 2 rooted trees with 5 nodes.
ii) Draw 2 binary trees with 6 leaves.
iii) Draw two ternary trees with 11 leaves.
7(POQ)O(PVQ)A7(PAO)
b) Let X = { 2, 3, 6, 12, 24, 36) and the relation < be such that X ^ Y if X divides Y. Draw the hasse diagram of < X, < >.
c) R is the additive group of real numbers and R+ the multiplicative group of
positive real no's, the map f: R -> R* defined by f (x) = ex V x e R. Does f(x)
defines isomorphism ?
d) A connected planar graph has 9 vertices having degrees 2, 2, 2, 3, 3, 3, 4, 4 and 5. How many edges are there ? How many faces are there ?
e) Determine whether the conclusion C is valid in the following when H,, H2
are premises. 5
i) H, : PVQ H,: P -» R H3:Q-»R C:R
I ii) H, : P (Q -> R) : R C : P
0 Show that the maximum number of edges in a simple graph with n-vcrtices is "(n-1)
2 " 5
2. a) Obtain the principal disjunctive normal form of
(PAQ)V(7PAR)V(QAR) 5
b) Show the following equivalence without constructing truth table.
((PAQAA)->C)A(A->(PVQVC))«(AA(POQ))->C 5
c) Show that (3x)M(x) follows logically from the premises 5
1 (x)(H(x)-»M(x))&(3x)H(x)
d) Test the validity of the following arguments :
If I study, then I will not fail in mathematics. If I do not play basket ball, then
I will study. But I fail in mathematics. Therefore, I must have played Basket
ball.
[3180] - 104 -2
3. a) Let the compatibility relation on a set {x,,x2 x6( be given by the matrix.
X2 1
X3 1 1
X4 0 ■ 0 1
X5 0 0 1 1
X6 1 0 1 0 1
x. \ X3 X4 X5
Draw the graph and find the maximum compatibility blocks of the relation.
b) Let A = (a, b, c} and p(A) its power set. Let Q be the inclusion relation on
the elements p(A). Show that (p(A), c) is a partially ordered set. Draw the
hasse diagram of (p(A), c). Find the least and greatest members in p(A) if they exist.
c) Given A = {1, 2, 3, 4} and R = { <2, 2>, <2, 4>, <1, 3>, <3, 2>} Find transitive closure of R.
d) Let X = {1, 2, 3) and f, g and h be functions from X to X given by f = {<1, 2>, <2, 3>, <3, 1>} g = {<1, 2>, <2, 1>, <3, 3>} h= {<1, 1>, <2, 2>, <3, 1>}
find
0 fog, gof are they equal ii) fogoh and fohog.
4. a) Let <G, *> be a group and a e G. Let f:G -> G be given by f (x) = axa-1 for every x s G. Prove that f is an isomorphism of G onto G.
b) Find the left cosets of ([0], [3]) in the group <Z6, + 6>.
c) Consider the (2,6) encoding function e:
e (00) = 000000, e (10) = 101010, e (01) = 011110, e (11) = 111000
i) Find the minimum distance.
ii) How many errors will e detect ?
d) Let f: IxI—> I, where I is set of integers and f (x, y) = x*y
= x + y^xy
Show that the binary operation * is commutative and associative. Find the identity element and indicate inverse of each clement.
4 of degree 2. Draw two such graphs.
Determine whether the following graphs are isomorphic or not.
a) Determine the number of edges in a graph with 6 nodes, 2 of degree 4 and b)
Represent the following using a binary tree.
(3x-5z£ a(2b+-c2)
ii) (3.(l-x)) + (4 + (7-(y + z)).(7 + (x + y))).
What are the total numbers of nodes in a full binary tree with 20 leaves ?
1. a) Show that the truth value of the following formula is independent of their components.
((P->Q)A(Q->R))->(P-*R)
b) Let A be the set of positive factors of 45 and let< be the relation divides,
i.e. < = (<x.y>/x e A, y e A A (x divides y) ).
Show that < is a totally ordered relation on A. Also draw the Hassc diagram.
c) Let T be the set of all even integers. Show that the semigroups (z, +) and (T, +) an isomorphic.
d) Show that the maximum no. of edges in a simple graph with n vertices is
n(n-i)
2
e) Let z be the set of integers and let R be the relation called "congruence modulo 3" defined by
R = {<x, y>/x€ZAyezA(x-y)is divisible by 3} Determine the equivalence classes generated by the elements of z.
2. a)
Show that R A (P V Q) is a valid conclusion from the premises PvQ,Q->R,P->M&lM. •
Show that the conclusion C follows from the premises H,, Hr
i) H, : P->(Q~>R) H2 :R C:P
ii) Hl : R H2:Pv^P C:R
Show that the following set of premises are inconsistent
A->(B-^C),D->(BA"|C),AAD.
c) Obtain the PCNF of the following formula (P->(QAR))AnP-*(-»QA-*R))
d) "Every computer has a CD drive. Some computers have floppy drive. Therefore some computers have both CD and a floppy drive." Verify the above argument is valid or not.
. a) Find all upper bounds, lower bounds, least upper bounds, greatest lower bounds of B = { c, d, e } for the poset whose Ilasse diagram is
b) Use Warshall's algorithm to find the transitive closure of the relation R = ( < 1,2 > <2, 1 > <2, 3 > <3,4> } on A = { 1, 2, 3, 4 )
c) Show that the set N x N is dcnumcrable.
d) Let the compatibility relation on a set ( x,, x2, x, x6 ) be given by the
matrix.
*2 1
1 1
*4 0 0 1
0 0 1 1
*6 1 0 1 0 1
x. x2 x3 x4 x5
Draw the graph and find the maximal compatibility blocks of the relation.
