Bengal Engineering and Science University 2007 B.E Computer Science and Engineering Discrete Structures - Question Paper
The ques. paper is with the attachment.
Ex/BESUS/ CS-401/07 B.E. (CST) Part-II 4th Semester Examination, 2007 Discrete Structures (CS-401)
Time : 3 hours Full Marks : 70
Use separate answerscript for each half.
Answer SIX questions, taking THREE from each half.
Two marks are reserved for neatness in each half.
FIRST HALF
1. a) Given the implication P Q, then ~Q - ~P is the contrapositive of the
implication and Q > P is the converse of the implication. The only remaining variation in the inverse of the implication, defined as ~P -> ~Q.
i) To which of the other three (implication, contrapositive, converse) is the inverse equivalent?
ii) To which of the other three (implication, inverse, converse) is the contrapositive equivalent?
Prove your answers to (i) and (ii).
b) Write down the converse of the following statement about integers :
If x and y are odd then x-y is even.
Is the statement that you wrote down true or false? Prove your answer.
c) Write down the contrapositives of the following
i) If the product of two integers is not divisible by n, then neither integer is divisible by n.
ii) If x1 is odd, then x is odd.
Prove your answers to (i) and (ii). [4+3+4)
c) Consider the following statements :
A1 : If the maid stole the jewelry, the gardener wasnt guilty.
A2 : Either the maid stole the jewelry or she milked the cows.
A3 : If the maid milked the cows, then the gardener get his cream.
G : Therefore, if the gardener was guilty, then he got his cream.
i) Express these statements in propositional calculus.
ii) Demonstrate that the conclusion G is valid. |3+3+5]
3. a) Define Prenex Normal Form.
Write%an algorithm to convert a FOPL wff into PNF.
b) For the following interpretation (D = {a, b})
~P(a,a) P (a, b) P (b, a) P (b, b)
6. i) Prove that vertex connectivity of any planar graph is at most five.
ii) State and prove Eulers formula. [5+61
7. i) Define stability number p (G) and chromatic number K (G) of a graph G. Prove
that (5 (G) > } where n is number of vertices in a graph.
K((j)
ii) Define cutset, fundamental cutset, cutspace. Prove that every cutset must contain at least one branch of every spanning tree of G. [5+6]
8. a) Prove that a connected graph with n vertices and n- 1 edges is a tree.
b) Define a binary tree. Obtain number of vertices at height h in a complete binary tree of n vertices.
c) Define tree graph of a graph. Prove that diameter of a tree graph is at most n-1. [3+4+4]
a) Define :
i) well formed formula in PL.
ii) valid and invalid wff.
iii) model and countermodel.
b) For each of the following formulas, determine whether it is valid, invalid, inconsistent, consistent or some combination of these.
i) (Pa(Q>P))-P
ii) (Pv~Q)a(~PvQ)
|
Attachment: |
| Earning: Approval pending. |
