COURSE: M.TECH BRANCH: CSE
YEAR & SEM: II REGULATION: R18
UNITI
1. Expailn in detail about logical connectives with examples
2. a) Defined well formed formula .Explain about tautology and contraduction with examples.
b) Determind whether the conclusion “C” follows logically from the premises H_{1}^H_{2.}
H_{1}:7p,H_{2}:p↔Q,C:7(p^Q).
3.(a) show that ((PvQ)^7(7P^(7Qv7R)))v(7P^7Q)v(7P^7R) is a tautology.
(b)Write the P.D.N.F and P.C.N.F for using following formulas without using truth table Pv(QR).
4.Using inference theory for statement calculus ,show the following implications.
(a).(PvQ) and (PR) and (QS)SvR
(b). show that R →S can be derived from P→(Q→S),(7RvP) and Q.
5. show that SvR is a tautologically implied by ((PvQ)^(P→R)^(Q→S)).
6. show that from (a) (x)(F(x)^S(x)→(y)(M(y)→W(y)).
(b)(y)(M(y)^7W(y)) then conclusion (x)(F(x)→7S(x)) follows .
7.Show That (x) (P(x)vQ(x))⇒(x)P(x)v(x)Q(x).
8. show that R^(PvQ) is a valid conclusion form the premises PvQ,Q→R,PM and
UNIITII

Define the following with examples .Set,proper subset ,empty set,power set, compliment.

a)Show that for any two sets A and B if. A(A.
b)Show that AB =(A (B).

Find how many integers b/w 1 and 60 that are not divisible by ‘2’ nor by ‘3’ nor by ‘5’. Also determine the no.of integers divisible ‘5’ not by ‘2’ not by ‘3’.

Define a Equivalence Relation . If R be a relation in the set of integers ‘Z’ defind by
R={(x,y)/x ,y ,(xy) is divisibie by 6}.Then provr that ‘R’ is an Equivalence Relation .
5.a) Define group ,semi group, sub group and abelian group.
b) Define group and an abelian group.Prove that the set Z of all integers with the binary operation ∗,Define as a∗b=a+b+1 a,bZ Is an abelian group.
6.a) The necessary and sufficient condition for a non empty subset H of a group (G,∗) to be a subgroup Is a a∗b^{1}H.
b).Prove that A non empty subset H of a group G is a subgroup of G Iff
I) aH,bH a∗bH 2)aHa^{I}H, where a^{I} is the inverse of a in G.
7. a)Let (L,≤) be a lattice in which ∗ and ⊕ denote the meet and join respectively for any a,bL.Prove That a≤b =a ⇔ a⊕b=b.
b) Define Boolean algebra.In any Boolean algebra prove that a=b iff ab^{l }⊕ a^{l}b =0.
8. a)Prove that every chain is a distributive lattice .
b)Show that in a complemented distributive lattice if a≤b ⇔ a∗b^{l }⇔ a^{l}⊕b=1⇔ b^{l}≤ a^{l}.
UNITIII
1.How many ways can the digits 0,1,2,3,4,5,6,7,8,9 be arranged so that
a) 0&1 adjacent and in the order of 01 b) 0&1 adjacent c) 0&1 are not adjacent.
2.Suppose there are 5 boys and 3 girls
a) In howmany ways can they sit in a row.
b) How many sitting arrangements are there with no two girls sitting together.
c) How many arrangements when all the girls never together.
d) How many ways all the girls sit together and all the boys sit together.
e) In how many than can they sit in a row if the boys are to sit together and the girls do not sit together.
3.A man has 7 relatives ,4 of them are ladies and 3 gentlemen,has wife has 7 relatives and 3 of them are ladies and 4 gentlemen . In howmany ways can they invite a dinner party of 3 ladies and 3 gentlemen so that there are 3 of wife relatives?
4. state and prove Binomial theorem and Multionmial theorem
5.Find the coefficient of a) x^{2} y^{4} in (x+y)^{6} b) x^{3}y^{2}z^{2 } in (x+y+z)^{9}
6.Explain Principle of inclusion & Exclusion give an example ?
7. Compute a) 20 b) Find n if (n+1)12x(n1) c)Convent the product 6.7.8.9.10 into factorial.
8. a) Compute the no.of the committees of three members each that can be formed from the committee of 25 members.
b)In how many was a committee of 5 members can be selected from 6 men and 5 women consisting of 3 men and 2 women ?
9.Find the no.of unordered samples of size five (repitation allowed) from the set .
a)No further restrictions b) ‘a’ occur atleast twice. C) ‘a’ occur exactly twice.
10. Find the no.of arrangement of the letters in the word a)”ACCOUNTANT “ b) “COMMERCE “
c) “PROGRAMMING” d) “MATHEMATICS”
UNITIV
1. Find a closed form for the generating function for each of the following sequence a)0,0,1,1,1…….
b) 1,1,0,1,1,1,1,1,…. C) 1,0,1,0,1,0,1,0,1,…. D) 3,3,3,3,3,3,…..
2. A person invest Rs 10,000/ @12% intrest compound annually. how much will be there of the end of 15years
3.Solve the recurrence relation of the Fibonacci sequence of number f_{n}=f_{n1}+f_{n2} n with the initial condition f_{0}=0,f_{1}=1
4.Solve f_{n}=f_{n1}+f_{n2},n2 with initial condition f_{0}=f_{1}=1 using fibonaci sequence
5. Solve the following RR by using iteration method
1). a_{n }=a_{n1}+f(n),n1 2). a_{n}=a_{n1}+3^{n }if n1 at a_{0}=1
6Solve a_{n+3}5a_{n+1}+6a_{n}=2 with initial condition a_{0}=1 and a_{1}=1
7.Solve the followingy_{n+2}y_{n+1}2y_{n}=n^{2}
8.Solve by using generating function a_{n}9a_{n1}+20a_{n2}=0 with initial condition a_{0}=3,a_{1}=10
9. By using generating function a_{n+2}2a_{n+1}+a_{n}=2^{n} with initial condition a_{0}=2,a_{1}=1
10.Suppose there are n guests of a dinner Party.each person shakes hands with everybody else exactly once,deduce the recurrence relation for the number of handshakes that occurs and solve the by iterative method.
UNITV
1.a) 1.What is a graph? Explain in detail.
b).Define the following with an example . a) Sub graph b) Spaning subgraph c) Null graph.
2.a)Let G be undirected graph with E=e edges and v=n vertices then show that V_{i})=2E.
b)Show that the sum of in degree of all nodes of a simple diagraph is equal to the sum of out degrees of all its nodes and that this sum is equal to the number of edges.
3 .a)In any graph G prove that the total number of vertices of odd degree is even.
b)Define isomorphism of two graphs. Give an example.
4.a) Define the following a)Walk b)Closed walk c) Open walk
b)Prove that the maximum no. Of edges in a simple graph with small n nodes in n_{c2 }(or) (or) .
5.a) What are Eulerian graph and Hamiltonian graph ?Explain briefly with an example
b) explain with Fleury’s Algorithm with any suitable example .
6. Explain about the Chinese postman problem ?
7.Explain about the Traveling sales man problem.
8.What do you mean by graph traversal ?Explain the different graph traversal with an Example .
1). a_{n }=a_{n1}+f(n),n1 2). a_{n}=a_{n1}+3^{n }if n1 at a_{0}=1
6Solve a_{n+3}5a_{n+1}+6a_{n}=2 with initial condition a_{0}=1 and a_{1}=1
7.Solve the followingy_{n+2}y_{n+1}2y_{n}=n^{2}
8.Solve by using generating function a_{n}9a_{n1}+20a_{n2}=0 with initial condition a_{0}=3,a_{1}=10
9. By using generating function a_{n+2}2a_{n+1}+a_{n}=2^{n} with initial condition a_{0}=2,a_{1}=1
10.Suppose there are n guests of a dinner Party.each person shakes hands with everybody else exactly once,deduce the recurrence relation for the num
6. Explain about the Chinese postman problem ?
7.Explain about the Traveling sales man problem.
8.What do you mean by graph traversal ?Explain the different graph traversal with an Example .