MUTHAYAMMAL ENGINEERING COLLEGE
(An Autonomous Institution)
(Approved by AICTE, New Delhi, Accredited by NAAC & Affiliated to Anna University)
Rasipuram - 637 408, Namakkal Dist., Tamil Nadu.
Department of Master of Computer Applications
Question Bank - Academic Year (2020-21)
Course Code & Course Name
:
19CAA01 & Mathematical Foundations of Computer
Science
Name of the Faculty
:
S.Ranjitha
Year/Sem/Branch
:
I/ I/ MCA
Unit-I : LOGIC AND PROOFS
Part-A (2 Marks)
Define Converse, Inverse and Contra positive of the statement?
Write the truth value of
FTT
Write the Symbolic representation “ If it rains today, then I buy an umbrella”.
Construct a truth table for the compound proposition
)()( pqqp
Construct the truth table for (a)
QP
(b)
QP
Prove that
QP
and
QP
are equivalent.
If P,Q and R are statement variable prove that
RQPQPP
Write Converse, Inverse and Contra positive of a statement of the form,
)()( xqxpx
Define a rule of Universal Specification.
Symbolize the expression “All the world loves a lover”.
Part-B (16 Marks)
1.(i)
Show that p∨(q∧r) and (p∨q)∧(p∨r) are logically equivalent.
(8)
(ii)
Without using the truth table, prove that ⅂p→(q→r) ≡ q→(p∨r).
(8)
2.(i)
Without using truth table show that
)()()))(()(( RPQPRQPQP
is a tautology.
(8)
(ii)
Prove that the following argument is valid : p→⅂q, r→q, r⇒⅂p.
(8)
3.(i).
Prove that the premises a→(b→c), d→(b∧⅂c) and (a∧d) are inconsistent.
(8)
Unit-II : COMBINATORICS
Part-A (2 Marks)
State the principle of Mathematical induction.
If seven colours are used to paint 50 bicycles, then show that atleast 8 bicycles will be
the same colour.
State the principle of strong induction.
How many students must be in a class to guarantee that atleast two students receive the
same score on the final exam, if exam is graded on a scale from 0 to 100 points
In how many ways permutation of the word “MISSISSIPPI” be arranged?
Define generating function.
Write the generating function for the sequence 20,21,22,,…2r
Solve S(k)-7S(k-1)+10S(k-2)=0
Write the recurrence relation for the Fibonacci sequence.
Find the recurrence relation satisfying the equation yn=A(3)n+B(-4)n
(ii).
Using indirect method of proof, derive p→⅂s from the premises p→(q∨r), q→⅂p, s→⅂r
and p.
(8)
4.(i)
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”.
(8)
(ii)
Prove that (∀x)(P(x)∨Q(x))⇒(∀x)P(x)∨(∃x)Q(x) using indirect method of proof.
(8)
5.(i)
Verify the validity of the following argument. Every living thing is a plant or an animal.
John’s gold fish is alive and it is not a plant. All animals have hearts. Therefore John’s
gold fish has a heart.
(8)
(ii)
Show that (∀x)(P(x)→Q(x)), (∃y)P(y) ⇒(∃x)Q(x).
(8)
Part-B (16 Marks)
1. (i).
show that = by using Mathematical induction method.
(8)
(ii)
show that > , n by using Mathematical induction method.
(8)
2(i)
Prove that the inequality n < 2n for all positive integer n by using Mathematical
induction method..
(8)
(ii)
How many positive integers n can be formed using the digits 3,4,4,5,5,6,7 if n has
to exceed 5000000?
(8)
3.(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 is
to develop a discrete mathematics course at a school if the committee is to consist
of three faculty members from the mathematics department and four from the
computer science department?.
(8)
(ii)
Find the number of distinct permutations that can be formed from all the letters of
each word (i) RADAR (ii) UNUSUAL
4.
There are 2500 students in a college, of these 1700 have taken a course in C, 1000
have taken acourse Pascal and 550 have taken a course in Networking. Further 750
have taken courses in bothC an Pascal. 400 have taken courses in both C and
Networking, and 275 have taken courses in bothPascal and Networking. If 200 of
these students have taken courses in C, Pascal and Networking.
(i)How many of these 2500 students have taken a course in any of these
three courses C, Pascal and Networking?
(ii)How many of these 2500 students have not taken a course in any of these
three courses C, Pascal and Networking?
16
5.(i).
Find the number of integers between 1 and 250 both inclusive that are any of the
integers 2,3,5,7.
(8)
(ii)
Solve the yn + 2 - 5yn+1+ 6 yn = 0, n ≥ 0 with y0 = 1 and y1= 1 by using generating
function.
(8)
Unit-III : GRAPHS
Part-A (2 Marks)
Define Graph.
Define strongly connected graphs.
Draw the graph represented by the given adjacency matrix
0101
1010
0101
1010
State the handshaking theorem.
How many edges are there in a graph with ten vertices each of degree six.
Let G be a graph with ten vertices. If four vertices has degree four and six vertices has
degree five, then find the number of edges of G.
Define complete graph and give an example (Or) Draw the complete graph K5.
Define Bipartite graph.
Give an example of Pseudo graph.
Give an example of an Euler graph.
Part-B (16 Marks)
1(i).
Prove that an undirected graph has an even number of vertices of odd degree.
(8)
(ii).
Show that a simple graph G with n vertices is connected if it has more than
2
21 nn
Edges
(8)
2(i).
Draw the complete graph K5 with vertices A, B , C , D, E . Draw all complete sub
graph of K 5 with 4 vertices.
(8)
(ii)
Draw the graph with 5 vertices A,B,C,D and E such that deg(A)=3, B is an odd
vertex, deg(C)=2 and D and E are adjacent.
(8)
3(i).
Examine whether the following pairs of graphs G1 and G2 given in figures are
isomorphic or not
(8)
Unit-IV : ALGEBRAIC STRUCTURES
Part-A (2 Marks)
Define semigroup and monoid.
Define semi group homomorphism.
Prove that the identity elements is unique in a group.
Define a commutative ring.
When is a group (G,*) called abelian?
Is G =
Rdcba
dc
ba ,,,
an abelian group with respect to multiplication?
Consider the group Z4= {[0],[1],[2],[3]} of integers modulor 4. Let H={[0],[2]} be a
subgroup of Z4 under +4. Find the left cosets of H.
If ‘a’ is a generator of a cyclic group G, then show that a-1 is also a generator of G
Define a Ring.
If a and b are any two elements of a group (G,*), If G is an Abelian group, show
G1 G2
(ii)
The adjacency matrices of two pairs of graph as given below. Examine the
isomorphism of G and H by finding a permutation matrix. AG = ,
AH =
(8)
4.(i)
Prove that the maximum number of edges in a simple disconnected graph G with n
vertices and k components is
(8)
(ii)
Prove that a given connected graph is Eulerian if and only if all the vertices of G are
of even degree.
(8)
5(i)
Show that the complete graph with n vertices Kn has a Hamiltonian circuit
whenever n≥3.
(8)
(ii)
Let G be a simple indirected graph with n vertices. Let u and v be two non adjacent
vertices in G such that deg(u) + deg(v) ≥ n in G . Show that G is Hamiltonian if and
only if G + uv is Hamiltonian
(8)
that (a*b)2=a2*b2
Unit-V : LATTICES AND BOOLEAN ALGEBRA
Part-A (2 Marks)
Define a Lattice.
Define Distributive lattice with example.
In a Lattice (L,≤) , prove that aν (aΛb)=a , for all a,bεL
Draw the Hasse diagram of
),,( X
where
X
is the set of positive divisors of 45 and the
relation
is such that
)(,:,( xdividesyAyAxyx
Draw the Hasse diagram of
20,10,5,4,2,1
20 D
Define partially ordered set.
Show that in a lattice if a≤b≤c, then and
(a*b)
Prove that
).().( baabaa
in a Boolean Algebra.
If ‘a’ and ‘b’ are two elements of a Boolean algebra prove that a + (a . b) = a.
Part-B (16 Marks)
1.(i)
If (G,*) is an abelian group, show that (a*b)2 =a2*b2
(ii)
State and prove Lagrange’s theorem.
2.(i)
Prove that every finite group of order n is isomorphic to a permutation group of order n.
(ii)
Prove that intersection of two normal subgroups of a group (G,*) is a normal subgroup
of a group (G,*)
3.(i)
Let f : G →G′ be a homomorphism of groups with Kernel K . Then prove that K is a
normal subgroup of G and G / K is isomorphic to the image of f.
(ii)
If * is the operation defined on S = Q x Q , the set of ordered pairs of rational numbers
and given by (a,b)*(x,y) = (ax, ay + b), show that (S, *) is a semi group. Is it
commutative? Also find the identity element of S.
4.(i).
Prove that the necessary and sufficient condition for a non empty subset H of a group
{G,*} to be a sub group is a,b∊ H⇒a*b-1∊H.
(ii)
Show that the Kernel of a homomorphism of a group into an another group
, is a subgroup of G.
5.(i)
Prove that the intersection of any two subgroups of a group G is again a subgroup of G.
(ii)
Prove that every cyclic group is an abelian group.
Show that in a Boolean algebra ab’+a’b=0 if a=b
Part-B (16 Marks)
1(i)
Show that (N, ≤) is a partially ordered set where N is set of all positive integers and ≤ is
defined by m ≤ n iff n-m is a non-negative integer.
(ii)
Let L be lattice, where a*b = glb(a,b) and a
b = lub(a,b) for all a,b . Then both
binary operations * and
defined as in L satisfies commutative law, associative law,
absorption law and idempotent law.
2.(i).
In a distributive Lattice {L, ∨, ∧} if an element a∊L a complement then it is unique.
(ii)
Show that every chain is a distributive lattice.
3.(i).
Prove that every distributive lattice is modular. Is the converse true?
(ii)
Show that the direct product of any two distributive lattices is a distributive lattice.
4.(i)
Draw the Hasse diagram for (1) P1 = {2,3,6,12,24} (2) P2 = {1,2,3,4,6,12} and ≤ is a
relation such x ≤ y if and only if x .
(ii)
Draw the Hasse diagram representing the partial ordering {(A,B):A⊆B} on the power
set P(S) where S ={a,b,c}. Find the maximal, minimal, greatest and least elements of
the poset
5.(i)
If S42 is the set all divisors of 42 and D is the relation “divisor of “ on S42, prove that
(S42,D}
is a complemented Lattice
(ii)
In any Boolean algebra show that a=b iff ab’+a’b=0.