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

Instructions

All the questions are compulsory.

Draw diagrams wherever required.

Answers to each question must begin from new page.

1

Answer the following.

14

1 (A)

Atempt any three

09

1

Let the relation R be defined on the set A = { 1,2,3,4,} as follows:
R={ (1,1),(1,2),(2,3),(3,2),(2,2),(3,3),(4,4)}
Determine whwther R is
(i) reflexive
(ii) symmetric
(iii) transitive

2

Explain the following giving suitable example.
(i) Graph of a relation
(ii) Equivalence relation
(iii) Ternary relation

3

Answer the following questions concerning the partially ordered set <{ 3,5,9,15,19,24,40} D>
(1) Find maximal elements
(2) Find upper bounds of {5,9}, if any.
(3)Find GLB of (15,40}

4

Draw the Hasse diagram of . Is it distributive? Which elements have complements?

(B)

Attempt two:

5

1

Show that every cain is a distributive lattice.

2

Let be a lattice, prove that for any a,b,c E L the distributive inequality a+(b*c)<=(a+b)*(a+c).

3

Give an example of a complemented, non-distributive lattice. Justify your claim.

2

Answer the following:

(A)

Attempt any three.

9

1

Define a Boolean algebra. Prove in a Boolean algebra, (a*b)' = a'+b'

2

Find the sum of product from of Boolean expression
A(x₁,x₂,x₃) = (x₁+x₂) * x₃

3

Give three other representations of tree expressed by
(V₀(V₁(V₂)(V₃(V₄)))(V₅(V₆)(V₇(V₈)(V₉)))(V₁₀(V₁₁(V₁₂))))

4

Determine atoms of {S₁₁₀,D}, Express every non-zero element of {S₁₁₀,D} as join of atoms.

(B)

Attemt any two .

5

1

Prove the given identity for a Boolean algebra
(a+b) (a'+c) = ac + a'b = ac + a'b + bc.

2

In a boolean algebra prove that a = b <=> ab' + a'b = 0

3

List all the minterms in 3 variables, a,b,c.

3

Answer the following.

14

(A)

Solve the following (any three).

12

1

Solve the following system of equations using Gauss Elimination Method.

    x + y + z = 6

    x - y + 2z = 5

    3x + y + z = 8

2

Define rank of matrix, Find the Rank of the given matrix:

3

Solve the folowing system of equations using Matrix Inverse Method :

    x + 2y - 3z = 1

    2x - y + z = 4

    3x + y - 2z = 5

4

Solve the following system of equations using Crammer's rule:

    2x + 3y - z = 5

    3x - 2y + z = 10

    x - 5y + 3z = 0

(B)

Give an example of 3 X 3 matrix (any two):

2

1

Diagonal Matrix

2

Symmetric Matrix

3

Upper Triangular Matrix

4

Answer the following.

14

(A)

Attempts the following parts (any three).

9

1

Which of the following sentences are statements, give the specification

   (i) Dr. Rajendra Prasad was the first President of India.

   (ii) Jawaharlal Nehru wrote the "Freedom of India".

   (iii) 11 + 1 = 111

   (iv) God bless you!

   (v) 10 is not a prime number

   (vi) How wonderful!

2

Using the following premises:
P : Sehwag made fastest hundred
Q : Indian won the one-day match against New Zealand.
Write the following statements in symbolic form:

   (i) Sehwag made fastest hundread and India won the match.

   (ii) Sehwag neither made hundread nor India won the match.

   (iii) If Sehwag made hundread then and only then India won the match, or Sehwag did not make hundread.

3

Find out conditional tautology using follwing premises:
P1 : H -> M
P2 : S -> H
Q : S -> M

4

Define the rules of inference.

(B)

Attempt the following (any two).

5

1

Explain the basic schema of WFF (well formed formulae)

2

Without using truth table show that
( ~ P ( ~ Q R ) ) v ( Q R ) v ( P R ) <=> R

3

Obtain the disjunctive normal form of ( ~p -> r ) ( p <=> q )

5

Answer the following.

14

(A)

Attempt any three:

12

(i)

Give an absstract definition of graph. When are two simple siagraphs said to be isomorphic? Give an example of simple digraphs each having five nodes and eight edges which are isomorphic.

(ii)

Explain reachability and node base of a graph. Find node base of the graph given in Figure-1.

(iii)

Given the adjacency matrix of the graph as

Determine whether the graph is connected.

(iv)

Define following :

 (1) Forest

 (2) Binary tree

 (3) Complete Binary tree

 (4) Subgraph

(B)

Distinguish between the following:

2

1

Graph and tree

2

Rppt and Leaf