MFCS QUESTION BANK
UNIT-I
1. a) Draw the truth table for [(p V q) → r] ↔ [~r → ~(p V q)]
b) Show the following by constructing derivations (x) ( H(x)→ A(x) ) ⇒ (x)
((∃y) (H(y)Λ N(x, y)) → (∃y) (A(y)Λ N(x, y))
2. a) Show that the following premises are inconsistent. (i) If jack misses
many classes through illness, then he fails high school (ii) If jack fails high
school, then he is uneducated. (iii) If jack reads lot of books, then he is not
uneducated. (iv) Jack misses many classes through illness and lot of books.
b) Show that P→S tautologically implied by ¬P˅Q , ¬Q˅R , R→S by automatic
theorem proving.
3. a) Symbolize the following statements:
all men are good
no men are good
some men are good some men are not good
b) Explain in detail about the Logical Connectives with Examples?
❑❑
UNIT-III
1. a) State and prove fundamental theorem of arithmetic.
2. a) In how many ways can 5 boys and 5 girls be seated in a row such that the boys and girls are to sit
on alternate sets and a boy X and girl Y do not sit on adjacent seats i.e. next to each other?
b) How many 6-digit numbers without repetition of digits are there such that the digits are all nonzero
and 1 and 2 do not appear consecutively in either order?
3. Find the number of Permutations the word MAYAJALAM?
4. a) In how many ways can we choose 3 of the numbers from 1 to 100, so that their sum is divisible by
3?
(b) Compute the number of rows of 6 Americans, 7 Mexicans, and 10 Canadians in which an American
invariably stands between a Mexican and a Canadian and in which a Mexican and a Canadian never
stand side by side.
5. a) A book binder is to bind 10 different books in red, blue and brown cloth. In how many ways can he
do this if each color of cloth is to be used for at least one book?
b) Explain Multinominal theorem with an example.
6. Explain Euclidian algorithm to find The Greatest Common Divisor of two numbers with suitable
example?
7. How many different five digit numbers can be formed from the digits 0,1,2,3 and 4?
b) A new state flag is to be designed with 6 vertical stripes in yellow, white, blue and red. In how many
ways can this be done so that no two adjacent stripes have the same color?
8. Explain Eulers Theorem with an example.
b) Explain Fermat’s theorem with an example
UNIT-II
1. a) For R={(1,1),(1,2),(2,2),(2,1),(3,3),(3,4),(4,4)} draw a graph of R, matrix of R.
Examine whether R is a reflexive, symmetric and transitive.
b) Define the following with examples, each. i) Inverse function, ii) One-to-one function, iii) Onto
function iv) Recursive function
2. a) Show that in a lattice if a≤ b and c ≤ d then a * c ≤ b * d
b) Let A=(6,12,18,24,36,72), a ≤ b if and only if a divides b. Draw Hasse diagram for it and prove that it is
a lattice, but not a distributive lattice.
3. Give three examples for a Monoid?
4. a) If X = {2, 3, 6, 12, 24} and if ≤ be the partial order defined by x≤ y if x divides y. Determine the
number of edges in Hasse diagram of (x, ≤).
b) If R and S are reflexive, symmetric and transitive, show that R∩S is also reflexive, symmetric and
transitive.
5.a) What are the properties of a Group? Show that the set G = {1} forms a group with respect to
multiplication?
b) Prove that H = {0, 2, 4} forms a subgroup of (Z6, +).
6.a) Let A = {1, 2, 3, 4, 5}, R ={(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (3, 4), (4, 3), (4, 4), (5, 5)} and S = {(1, 1), (2,
2), (3, 3), (4, 4), (5, 4), (4, 5), (5, 5)}. Find the smallest-equivalence relation containing R and S and
compute the partition of A that it produces.
(b) Given S = {1, 2, 3, 4} and a relation R on S defined by R = {< 1, 2 >,< 4, 3 >,< 2, 2 >,< 2, 1 >,< 3, 1 >},
show that R is not transitive.
7. Given S = {1,2,3,....,10}and a relation R on S where R = {<x,y> / x+y =10}, what are the properties of the
relation R? Explain
b) Determine all the bijections from {1, 2, 3} onto {a, b, c, d}.
8. Show that intersection of any two subgroups of a group G is also a sub group of G.
9. Let L be lattice. Then prove that a˄b = a if and only if a˅b = b.
b) Define the dual of a statement in a lattice L. Why does the principle apply to L?
UNIT-IV
1. a) Solve the recurrence relation a n- 4 an−1+4 an−2= 3n +2n, n≥2 with a 0=a 1=1.
b) Evaluate the sum 12 +22 +32 +… ..+r 2using generating function
2. Write the general solution and particular solution of recurrence relation?
3. a) Solve the recurrence relation a n+ ¿ a n−1−8 an−2−12 a n−3= 0 for n≥3 with a 0=1 , a1=5 anda 2=1.
b)Given an = 4an-1-4an-2 +(n2 +1)2n . Find the solution of non-homogeneous relation , a0=0 and a1=1
4. Solve simultaneous recurrence relations: (a) a n=3 a n+2 bn−1
(b¿ b n=a n−1+2 bn−1
5. Solve an - 2an-1 - 3an-2 = 5n , n≥2, given a0 = - 2, a1 =
a n- 4 an−1+4 an−2= 3n +2n, n≥2 with a 0=a 1=1.
a n+ ¿ a n−1−8 an−2−12 a n−3= 0 for n≥3 with a 0=1 , a1=5 anda 2=1.
UNIT-V
1. a) Discuss the rules for constituting Hamiltonian path and Hamiltonian cycle.
b) Determine whether the following two graphs are isomorphic or not
2. a) Explain Kruskal’s algorithm with example.
b) Prove that a complete graph kn is planar iff n≤4
3. Explain adjacency matrix of the graph?
4. a) Explain Kruskal’s algorithm to find minimal spanning tree of the graph with suitable example?
b) Show that the complete graph K5 and complete bipartite graph K3, 3 are not planar?
5. Differentiate between Eulerian graph and Hamiltonian graph with an example each.
b) Describe an algorithm to decide whether a graph is bipartite or not
6. Explain an algorithm to find the minimal spanning tree with an example.
b) Define Eulerian Graph and prove that a non empty connected graph G is Eulerian if and only if its
vertices are all of even degree.
