1.
a) Can a relation R in a set A be both symmetric and anti symmetric? Justify your answer.
b) Write the negation of the following by changing the quantifiers:
“Every complete bipartite graph is not planar.”
c) Prove absorption law in a Boolean algebra.
d) How many ways can one right and one left shoe be selected from 10 pairs of shoes without obtaining a pair?
e) What is the largest possible number of vertices in a graph with 35 edges and all vertices of degree at least 3?
f) Find a grammar to generate the set
{0m1n | m and n are non negative integers}
g) Let (A,*) be an algebraic system, where * is a binary operation such that for any a and b in A
a*b = a
Show that this operation is associative.
(7×4)
2.
a) Suppose R is an arbitrary transitive and reflexive relation on a set A. Prove that the relation E defined by “x E y iff x R y and y R x” is an equivalence relation.
b) Prove or disprove the validity of the following argument:
i) Every living thing is a plant or animal.
ii) Ram’s dog is alive and is not a plant.
iii) All animals have heart.
iv) Hence Ram’s dog has a heart.
(9+9)
3.
a) Prove that if R is a partial ordering relation on a set S, then for n ³ 2,there can not be a sequence s1, s2, s3,….sn of distinct elements of S such that s1 R s2 R s3…RsnRs1.
b) Minimize following switching function
Sm(0, 2, 8, 12, 13 ).
c) Consider the group (Z4, 
): the integer modulo 4 group with respect to the operation : addition modulo 4. Does H={[0], [2]} form a subgroup of Z4. If yes, is it a normal subgroup? Justify.
(6+6+6)
4.
a) Solve the following:
an = 2 a n-1 +1
where
a0 =0
a1= 1
a2 = 3.
b) Find a generating function to count the number of integral solutions of
e1 + e2+ e3 = 10 if for each i, 0 £ ei
(9+9)
5.
a) Show that complement of a regular set is a regular set.
b) Write a grammar/ regular expression for the language on the alphabet{0,1} having all the strings with different first and last symbols.
c) Find a deterministic finite state machine that recognizes the set:
L={0i10j | i ≥ 1, j ≥ 1}
(6+6+6)
6.
a) Apply Dijkstra’s algorithm to determine a shortest path between a and z in the following graph:
b 3 e
2 2 5 1
a 1 z
c
4 2 7 3
d 4 f
The numbers associated with the edges are distances between vertices.
b) Obtain the principal conjunctive normal form and principal disjunctive normal form of the formula S given by
(ØP® R )L (Q« P)
c) State Pigeon hole principle. Show that in a sequence of n2+1 distinct integers, there is either an increasing subsequence of length(n+1) or decreasing subsequence of length.
(6+6+6)
