How To Exam?

a knowledge trading engine...

Gujarat University 2008-2nd Year B.C.A Computer Application Mathematical Foundation of Computer Science - Question Paper

Sunday, 12 May 2013 08:55Web

Page 1 of 5

Sea! No.: 1 3 6 0

SBCA-03

March-2008

Mathematical Foundation of Computer Scicncc (203)

(New Course)

Time : 3 Hours! l^Max* ^{Marks : 70}

Instructions: (I) AH the questions arc compulsory.

(2) Figures to the right indicate full marks.

(3) Answer of cach question must start on new page.

(4) Assume suitable data wherever necessary.

I. (A) Do as directed (Any two): 0#

(1) Determine the truth value of cach of the following statement:

(i) 3 x 9 - 3 or 7 is positive integer.

(ii) 3 x 9 = 3 or 7 is not a positive integer.

(iii) 3 x 9 *= 27 and 7 is a positive integer.

(iv) If 3 x 9 = 27 then 7 is not a positive integer.

(2) Show that (p -* q) a (r -> q) <* (p v r) q.

(3) For the formula (1 p -> r) a (q p) in three variables p, q, and r, obtain the principal conjunctive normal form.

(B) Attempt the following (Any two): 06

(1) Show that the hypothesis *1 p a q, r -> p'\ 1 r -> s" and s -> f lead to the conclusion t.

(2) Explain the following using truth table :

<1) Conjunction

(2) Exclusive disjunction

(3) NAND

(3) Check whether the following premises are consistent or not:

p - q, q -> s, r -> 1 s, p a r.

SBCA-03 1 ^l>xt)-

c%D

Give ihc definition of the followmg^-: 04

2- (A)

(B)

(C)

(1) Complete graph

(2) Regular graph

(3) Converse of a digraph

(4) Null graph

Let D be the divides relation (x divides y if there exist an integer m such that y - xm) defined on set A - {5,7,11,13,23}. Find maximal and minimal elements of set A with rcspect to D relation. 02

Attempt any two : 08

(1) Define equivalence relation. Let N be a set of integers and let be the relation on N x N defined by (a, b) - (c, d) if a+d=b+c. Prove that - is an equivalence relation.

(2) (i) Draw the Hasse diagram of (P(S), c), where S - {a,b,c,d} and c be

the inclusion relation.

(ii) Let * be the binary operation on set of real numbers (R), defined as x*y = xy-x -y. Is commutative? Is V associative?

(3) Let X = {1,2,3,4,5,6} and let D be the relation on X defined by "x divides y written as x | y ( x | y if there exists an integer m such that y = xm). Answer the following:

(1) Show that the given relation is antisymmetric.

(2) Draw the graph of given relation.

(3) Determine the relation matrix.

Attempt any four : 12

3. (A)

(1) Let <L, *, ,0,1) be a complimented distributive latticc. Then prove that (a b) - a * b'.

(2) Let <L, <> be a Janice. Then prove that ifb<c=> i)a*b<a*c

ii)ab<ac

(3) Obtain sum of products canonical form of x, (x₂ * x₃) in three variables

*j i '*3'

(4) In a Boolean algebra (B, . \ 0. l> prove that a³boa*b' + a'b = 0.

(5) Show that the following Boolean expressions arc equivalent to each other.

(1) (jr y) * (*' z) * (y z)

(2) (x * z) (V + y) (y * z)

Define: 2

<B)

(1) Complimented latticc

(2) POSET

I

SBCA-03 2

Do as directed (any four);

1 2 3'

12

4. (A)

then find A + A^T and A - A^T. Also represent the

4-10 L -2 3 5 .

(1) If A *

matrix A as sura of symmetric and skcw-symmctric matrix.

(2) Solve following system of linear equation by Cramers rule, x + 2y + z = 8,2x + 3y + 4z = 20,4x + 3y + 2z 16.

(3) Use Gauss elimination method to solve x+y+z=6, x-y+z=2 and 2x+y-z= I.

(4) Define rank of a matrix and find it for

0 2 4 6

2 7 8 1 -3-113 LI 3 5 7 J

0 I I

1 2 0

. Use Gauss-Jordan reduction method to find inverse

(5) Let A =

L 3 -I 4 J of matrix A.

2-13 4 7?.

L I 4 5 J

02

is 2.

(B)

5- (A)

12

Attempt the following (any four):

(1) Define the following :

(I) Geodesic (2) Graph (3) Tree

(2) Define diameter of a graph and find it for the graph in Figure (i).

Find the value of X, if rank of A

SBCA-03 3 P.T.O.

(3) When a digraph is said to be strongly connccted and unilaterally connected ? Give an example of each. Also find strong components for the graph given in Figure (i).

(4) Give the definition of Isomorphic graphs. Consider the two graphs given in Figure (ii) and check whether they arc isomorphic or not.