.... How to Find Your Subject Study Group & Join ....   .... Find Your Subject Study Group & Join ....  

We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

Study Groups By Subject code Wise (Click Below on your university link & Join Your Subject Group)

[ + VU Study Groups Subject Code Wise ]  [ + COMSATS Virtual Campus Study Groups Subject Code Wise ]

Looking For Something at vustudents.ning.com? Search Here

It is very necessary for all of us

Share This With Friends......


How to Find Your Subject Study Group & Join.

Find Your Subject Study Group & Join.

+ Click Here To Join also Our facebook study Group.


This Content Originally Published by a member of VU Students.

+ Prohibited Content On Site + Report a violation + Report an Issue

+ Safety Guidelines for New + Site FAQ & Rules + Safety Matters

+ Important for All Members Take a Look + Online Safety


Views: 761

See Your Saved Posts Timeline

Attachments:

Replies to This Discussion

Note: (This is Featured Discussion)

For Important Helping Material related to this subject (Solved MCQs, Short Notes, Solved past Papers, E-Books, FAQ,Short Questions Answers & more). You must view all the featured Discussion in this subject group.

For how you can view all the Featured discussions click on the Back to Subject Name Discussions link below the title of this Discussion & then under featured Discussion corner click on the view all link.

FINALTERM EXAMINATION

Spring 2009

MTH202- Discrete Mathematics (Session - 2)

Time: 120 min

Marks: 80

Question No: 1 ( Marks: 1 ) - Please choose one

The negation of “Today is Friday” is

► Today is Saturday

Today is not Friday

► Today is Thursday

Question No: 2 ( Marks: 1 ) - Please choose one

An arrangement of rows and columns that specifies the truth

Come & Join Us at www.vustudents.ning.com

value of a compound proposition for all possible truth values of its

constituent propositions is called

Truth Table

► Venn diagram

► False Table

► None of these

Question No: 3 ( Marks: 1 ) - Please choose one

The converse of the conditional statement p R q is

q Rp

► ~q R~p

► ~p R~q

► None of these

Question No: 4 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

Contrapositive of given statement “If it is raining, I will take

an umbrella” is

I will not take an umbrella if it is not raining.

► I will take an umbrella if it is raining.

► It is not raining or I will take an umbrella.

► None of these.

Question No: 5 ( Marks: 1 ) - Please choose one

Let A= {1, 2, 3, 4} and R = {(1, 1), (2, 2), (3, 3),(4,4)} then

► R is symmetric.

► R is anti symmetric.

► R is transitive.

R is reflexive.

All given options are true

Question No: 6 ( Marks: 1 ) - Please choose one

A binary relation R is called Partial order relation if

► It is Reflexive and transitive

► It is symmetric and transitive

► It is reflexive, symmetric and transitive

It is reflexive, antisymmetric and transitive

Question No: 7 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

How many functions are there from a set with three

elements to a set with two elements?

► 6

8

► 12

Question No: 8 ( Marks: 1 ) - Please choose one

1,10,102 ,103 ,104 ,105 ,106 ,107 ,................ is

Arithmetic series

► Geometric series

► Arithmetic sequence

► Geometric sequence

Question No: 9 ( Marks: 1 ) - Please choose one

éêxùú for x = -2.01 is

► -2.01

► -3

-2

► -1.99

Question No: 10 ( Marks: 1 ) - Please choose one

If A and B are two disjoint (mutually exclusive)

events then

P(AUB) =

Come & Join Us at www.vustudents.ning.com

► P(A) + P(B) + P(ACB)

► P(A) + P(B) + P(AUB)

► P(A) + P(B) - P(ACB)

► P(A) + P(B) - P(ACB)

P(A) + P(B)

Question No: 11 ( Marks: 1 ) - Please choose one

If a die is thrown then the probability that the dots on the top

are prime numbers or odd numbers is

► 1

► 1

3

2

3

Question No: 12 ( Marks: 1 ) - Please choose one

If P(AÇB) ¹ P(A)P(B) then the events A and B are called

► Independent

► Dependent page 270

► Exhaustive

Question No: 13 ( Marks: 1 ) - Please choose one

A rule that assigns a numerical value to each outcome in a

sample space is called

► One to one function

► Conditional probability

Random variable

Come & Join Us at www.vustudents.ning.com

Question No: 14 ( Marks: 1 ) - Please choose one

The expectation of x is equal to

► Sum of all terms

► Sum of all terms divided by number of terms

► åxf (x)

Question No: 15 ( Marks: 1 ) - Please choose one

The degree sequence {a, b, c, d, e} of the given graph is

► 2, 2, 3, 1, 1

2, 3, 1, 0,1

► 0, 1, 2, 2, 0

2, 3,1,2,0 page305

Question No: 16 ( Marks: 1 ) - Please choose one

Which of the following graph is not possible?

► Graph with four vertices of degrees 1, 2, 3 and 4.

Graph with four vertices of degrees 1, 2, 3 and 5.

► Graph with three vertices of degrees 1, 2 and 3.

► Graph with three vertices of degrees 1, 2 and 5.

Question No: 17 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

The graph given below

► Has Euler circuit

► Has Hamiltonian circuit

Does not have Hamiltonian circuit

Question No: 18 ( Marks: 1 ) - Please choose one

Let n and d be integers and d 1 0. Then n is divisible by d or d

divides n

If and only if

n= k.d for some integer k

► n=d

► n.d=1

► none of these

Question No: 19 ( Marks: 1 ) - Please choose one

The contradiction proof of a statement paq involves

Considering p and then try to reach q

► Considering ~q and then try to reach ~p

Come & Join Us at www.vustudents.ning.com

► Considering p and ~q and try to reach contradiction

► None of these

Question No: 20 ( Marks: 1 ) - Please choose one

An integer n is prime if, and only if, n > 1 and for all positive

integers r and s, if

n = r·s, then

r = 1 or s = 1.

► r = 1 or s = 0.

► r = 2 or s = 3.

► None of these

Question No: 21 ( Marks: 1 ) - Please choose one

The method of loop invariants is used to prove correctness of

a loop with respect to certain pre and post-conditions.

True

► False

► None of these

Question No: 22 ( Marks: 1 ) - Please choose one

The greatest common divisor of 27 and 72 is

Come & Join Us at www.vustudents.ning.com

► 27

9

► 1

► None of these

Question No: 23 ( Marks: 1 ) - Please choose one

If a tree has 8 vertices then it has

► 6 edges

7 edges

► 9 edges

Question No: 24 ( Marks: 1 ) - Please choose one

Complete graph is planar if

n = 4

► n>4

n £ 4

Question No: 25 ( Marks: 1 ) - Please choose one

The given graph is

Come & Join Us at www.vustudents.ning.com

Simple graph

► Complete graph

► Bipartite graph

► Both (i) and (ii)

► Both (i) and (iii)

Question No: 26 ( Marks: 1 ) - Please choose one

The value of 0! Is

► 0

1 pg160

► Cannot be determined

Question No: 27 ( Marks: 1 ) - Please choose one

Two matrices are said to confirmable for multiplication if

► Both have same order

Number of columns of 1st matrix is equal to number

of rows in 2nd matrix

► Number of rows of 1st matrix is equal to number of

columns in 2nd matrix

Question No: 28 ( Marks: 1 ) - Please choose one

The value of (-2)! Is

►0

1

Cannot be determined

Question No: 29 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

The value of ( )

( 1)!

1 !

n

n

+

- is

► 0

► n(n-1)

n2 + n

► Cannot be determined

Question No: 30 ( Marks: 1 ) - Please choose one

The number of k-combinations that can be chosen from a set of n

elements can be written as

nCk pg223

► kCn

► nPk

► kPk

Question No: 31 ( Marks: 1 ) - Please choose one

If the order does not matter and repetition is allowed then

total number of ways for selecting k sample from n. is

► nk

C(n+k-1,k) page 228

P(n,k)

► C(n,k)

Question No: 32 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

If the order matters and repetition is not allowed then total

number of ways for selecting k sample from n. is

► nk

► C(n+k-1,k)

P(n,k) page 228

► C(n,k)

Question No: 33 ( Marks: 1 ) - Please choose one

To find the number of unordered partitions, we have to count the

ordered partitions and then divide it by suitable number to erase

the order in partitions

True pg231

► False

► None of these

Question No: 34 ( Marks: 1 ) - Please choose one

A tree diagram is a useful tool to list all the logical

possibilities of a sequence of events where each event can

occur in a finite number of ways.

True

► False

Come & Join Us at www.vustudents.ning.com

Question No: 35 ( Marks: 1 ) - Please choose one

If A and B are finite (overlapping) sets, then which of the

following must be true

► n(AEB) = n(A) + n(B)

► n(AEB) = n(A) + n(B) - n(ACB)

► n(AEB)= o

► None of these

Question No: 36 ( Marks: 1 ) - Please choose one

What is the output state of an OR gate if the inputs are 0 and 1?

► 0

1

► 2

► 3

Question No: 37 ( Marks: 1 ) - Please choose one

In the given Venn diagram shaded area represents:

Come & Join Us at www.vustudents.ning.com

► (A C B) E C

► (A E Bc) E C

(AC Bc) E Cc page 53

► (A C B) C Cc

Question No: 38 ( Marks: 1 ) - Please choose one

Let A,B,C be the subsets of a universal set U.

Then (AÈBC is equal to:

► AÇ(BÈC)

► AÈ(BÇC)

►Æ

AÈ(BÈC)

Question No: 39 ( Marks: 1 ) - Please choose one

n ! >2n for all integers n 34.

► True

False

Question No: 40 ( Marks: 1 ) - Please choose one

+,-,´,¸ are

► Geometric expressions

Arithmetic expressions

► Harmonic expressions

Question No: 41 ( Marks: 2 )

Find a non-isomorphic tree with five vertices.

There are three non-isomorphic trees with five vertices as shown

(where every tree with five vertices has 5-1=4 edges).

Come & Join Us at www.vustudents.ning.com

Question No: 42 ( Marks: 2 )

Define a predicate.

A predicate is a sentence that contains a finite number of

variables and becomes a statement when specific values are

substituted for the variables.

The domain of a predicate variable is the set of all values that

may be substituted in place of the variable.

Let the declarative statement:

“x is greater than 3”.

We denote this declarative statement by P(x) where

x is the variable,

P is the predicate “is greater than 3”.

The declarative statement P(x) is said to be the value of the

propositional function P at x.

Come & Join Us at www.vustudents.ning.com

Question No: 43 ( Marks: 2 )

Write the following in the factorial form:

(n +2)(n+1) n

( 2)( 1) !

!

n n n

n

+ +

Question No: 44 ( Marks: 3 )

Determine the probability of the given event

“An odd number appears in the toss of a fair die”

Sample space will be..S={1,2.3,4,5,6}…there are 3 odd numbers so,

For odd numbers, probability will be

3

6…Ans

Question No: 45 ( Marks: 3 )

Determine whether the following graph has Hamiltonian circuit.

This graph is not a Hamiltonian circuit, because it does not

satisfy all conditions of it.

Come & Join Us at www.vustudents.ning.com

E.g. it has unequal number of vertices and edges. And its path

cannot be formed without repeating vertices.

Question No: 46 ( Marks: 3 )

Prove that If the sum of any two integers is even, then so is their

difference.

Theorem: ∀ integers m and n, if m + n is even, then so is m - n.

Proof:

Suppose m and n are integers so that m + n is even. By definition

of even, m + n = 2k for some integer k. Subtracting n from both

sides gives m = 2k - n. Thus,

m - n = (2k - n) -

n

by

substitution

= 2k - 2n

combining

common

terms

= 2(k - n)

by

factoring

out a 2

But (k - n) is an integer because it is a difference of integers.

Hence, (m - n) equals 2 times an integer, and so by definition of

even number, (m - n) is even.

This completes the proof.

Come & Join Us at www.vustudents.ning.com

Question No: 47 ( Marks: 5 )

Show that if seven colors are used to paint 50 heavy bikes, at

least 8 heavy bikes will be the same color.

N=50

K=7

C(7+50-1,7)

C(56,7)

56!/(56-7)!7!

56!/49!.7!

Question No: 48 ( Marks: 5 )

Determine whether the given graph has a Hamilton circuit? If it

does, find such a circuit, if it does not , given an argument to

show why no such circuit exists.

(a)

Come & Join Us at www.vustudents.ning.com

This graph does not have Hamiltonian circuit, because it does not

satisfy the conditions. Circuit may not be completed without

repeating edges. It has also unequal values of edges and vertices.

(b)

This graph is a Hamiltonian circuit ..Its path is a b c d e a

Question No: 49 ( Marks: 5 )

Find the GCD of 11425 , 450 using Division Algorithm.

LCM = 205650

11425 = 450x25 + 175

450 = 175x2 + 100

175 = 100x1 + 75

100 = 75x1 + 25

75 = 25x3 + 0

Linear combination= 25 = 127x450 + -5x11425

GCD= 25…Ans

Come & Join Us at www.vustudents.ning.com

Question No: 50 ( Marks: 10 )

Write the adjacency matrix of the given graph also find

transpose and product of adjacency matrix and its transpose

(if not possible then give reason)

Adjacency matrix= 0 1 0 0 0

1 0 0 0 0

0 0 0 1 1

0 0 1 0 1

0 0 1 1 0

Transpose = 0 1 0 0 0

1 0 0 0 0

0 0 0 1 1

0 0 1 0 1

0 0 1 1 0

Its transpose is not possible…it’s same. Because there is no loop.

It is not directed graph.

FINALTERM EXAMINATION

Fall 2009

MTH202- Discrete Mathematics

Time: 120 min

Marks: 80

Question No: 1 ( Marks: 1 ) - Please choose one

Let A = {a, b, c} and

R = {(a, c), (b, b), (c, a)} be a relation on A. Is R

Transitive

Come & Join Us at www.vustudents.ning.com

Reflexive

Symmetric

Transitive and Reflexive

Question No: 2 ( Marks: 1 ) - Please choose one

Symmetric and antisymmetric are

Negative of each other

Both are same

Not negative of each other

Question No: 3 ( Marks: 1 ) - Please choose one

The statement p « q º q « p

describes

Commutative Law: page 27

► Implication Laws:

► Exportation Law:

Come & Join Us at www.vustudents.ning.com

► Equivalence:

Question No: 4 ( Marks: 1 ) - Please choose one

The relation as a set of ordered pairs as shown in figure is

{(a,b),(b,a),(b,d),(c,d)}

{(a,b),(b,a),(a,c),(b,a),(c,c),(c,d)}

{(a,b), (a,c), (b,a),(b,d), (c,c),(c,d)}

{(a,b), (a,c), (b,a),(b,d),(c,d)}

Question No: 5 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

The statement p ®q º (p Ù ~q) ®c

Describes

► Commutative Law:

► Implication Laws:

► Exportation Law:

Reductio ad absurdum page 27

Question No: 6 ( Marks: 1 ) - Please choose one

A circuit with one input and one output signal is called.

NOT-gate (or inverter)

OR- gate

AND- gate

None of these

Question No: 7 (Marks: 1) - Please choose one

If f(x) =2x+1, g(x)=x2 -1 then fg(x) =

Come & Join Us at www.vustudents.ning.com

x2 -1

2x2 -1

2x3 -1

Question No: 8 (Marks: 1) - Please choose one

Let g be the functions defined by

g(x)= 3x+2 then gog(x) =

► 9x2 + 4

6x+4

► 9x+8

Question No: 9 ( Marks: 1 ) - Please choose one

How many integers from 1 through 1000 are neither multiple of 3

nor multiple of 5?

333

467

533

497

Question No: 10 (Marks: 1) - Please choose one

Come & Join Us at www.vustudents.ning.com

What is the smallest integer N such that 9

6

éN ù = êê úú

46

29

49

Question No: 11 ( Marks: 1 ) - Please choose one

What is the probability of getting a number greater than 4 when

a die is thrown?

1

2

3

2

1

3

Question No: 12 ( Marks: 1 ) - Please choose one

If A and B are two disjoint (mutually exclusive)

events then

P(AB) =

P(A) + P(B) + P(AB)

Come & Join Us at www.vustudents.ning.com

P(A) + P(B) + P(AUB)

P(A) + P(B) - P(AB)

P(A) + P(B) - P(AB)

P(A) + P(B)

Question No: 13 ( Marks: 1 ) - Please choose one

If a die is thrown then the probability that the dots on the

top are prime numbers or odd numbers is

1

1

3

2

3

Question No: 14 ( Marks: 1 ) - Please choose one

The probability of getting 2 heads in two successive tosses of a

balanced coin is

Come & Join Us at www.vustudents.ning.com

1

4

By hackerzZz

1

2

2

3

Question No: 15 ( Marks: 1 ) - Please choose one

The probability of getting a 5 when a die is thrown?

1

6

5

6

1

3

Question No: 16 ( Marks: 1 ) - Please choose one

If a coin is tossed then what is the probability that the

number is 5

Come & Join Us at www.vustudents.ning.com

1

2

0

1

Question No: 17 ( Marks: 1 ) - Please choose one

If A and B are two sets then the set of all elements that belong

to both A and B, is

A U B

A  B

A--B

None of these

Question No: 18 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

What is the expectation of the number of heads when three

fair coins are tossed?

1

1.34

2

1.5 page 275

misuse

Question No: 19 ( Marks: 1 ) - Please choose one

If A, B and C are any three events, then

P(AÈBÈC) = is equal to

P(A) + P(B) + P(C)

P(A) + P(B) + P(C) - P(AÇB) - P (A ÇC) - P(B ÇC) + P(A ÇB ÇC)

pg262

P(A) + P(B) + P(C) - P(AB) - P (A C) - P(B C)

P(A) + P(B) + P(C) + P(A B C)

Question No: 20 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

A rule that assigns a numerical value to each outcome in a

sample space is called

One to one function

Conditional probability

Random variable

Question No: 21 ( Marks: 1 ) - Please choose one

The power set of a set A is the set of all subsets of A,

denoted P(A).

False

True

Question No: 22 ( Marks: 1 ) - Please choose one

A walk that starts and ends at the same vertex is called

Simple walk

Circuit

► Closed walk

Question No: 23 ( Marks: 1 ) - Please choose one

If a graph has any vertex of degree 3 then

Come & Join Us at www.vustudents.ning.com

It must have Euler circuit

It must have Hamiltonian circuit

► It does not have Euler circuit (becz 3 is odd)

Question No: 24 ( Marks: 1 ) - Please choose one

The square root of every prime number is irrational

True

False

Depends on the prime number given

Question No: 25 ( Marks: 1 ) - Please choose one

A predicate is a sentence that contains a finite number of

variables and becomes a statement when specific values are

substituted for the variables

True pg200

False

Come & Join Us at www.vustudents.ning.com

None of these

Question No: 26 ( Marks: 1 ) - Please choose one

If r is a positive integer then gcd(r,0)=

r

► 0

1

None of these

Question No: 27 ( Marks: 1 ) - Please choose one

Combinatorics is the mathematics of counting and arranging

objects

► True

False

Cannot be determined

Question No: 28 ( Marks: 1 ) - Please choose one

A circuit that consist of a single vertex is called

► Trivial

Come & Join Us at www.vustudents.ning.com

Tree

Empty

Question No: 29 ( Marks: 1 ) - Please choose one

In the planar graph, the graph crossing number is

0 page 312

1

2

3

Question No: 30 ( Marks: 1 ) - Please choose one

How many ways are there to select five players from a 10

member tennis team to make a trip to a match to another

school?

C(10,5)

C(5,10)

P(10,5)

Come & Join Us at www.vustudents.ning.com

None of these

Question No: 31 ( Marks: 1 ) - Please choose one

The value of 0! Is

0

► 1

Cannot be determined

Question No: 32 ( Marks: 1 ) - Please choose one

If the transpose of any square matrix and that matrix are same

then matrix is called

Additive Inverse

Hermition Matrix

Symmetric Matrix

Question No: 33 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

The value of ( )

( 1)!

1 !

n

n

-

+ is

0

► n(n-1)

► ( 2 )

1

n + n

Cannot be determined

Question No: 34 ( Marks: 1 ) - Please choose one

If A and B are two disjoint sets then which of the following must

be true

n(AB) = n(A) + n(B)

► n(AB) = n(A) + n(B) - n(AB)

n(AB)= o

None of these

Question No: 35 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

Any two spanning trees for a graph

Does not contain same number of edges

Have the same degree of corresponding edges

contain same number of edges

May or may not contain same number of edges

Question No: 36 ( Marks: 1 ) - Please choose one

When P(k) and P(k+1) are true for any positive integer k, then P(n)

is not true for all +ve Integers.

True

False by ali

Question No: 37 ( Marks: 1 ) - Please choose one

n2 > n+3 for all integers n 3.

True

False

Come & Join Us at www.vustudents.ning.com

Question No: 38 ( Marks: 1 ) - Please choose one

Quotient –Remainder Theorem states that for any positive

integer d, there exist unique integer q and r such that

_______________ and 0≤r<d.

n=d.q+ r

n=d.r+ q

n=q.r+ d

None of these

Question No: 39 ( Marks: 1 ) - Please choose one

Euler formula for graphs is

f = e-v

f = e+v +2

f = e-v-2

f = e-v+2

Question No: 40 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

The degrees of {a, b, c, d, e} in the given graph is

2, 2, 3, 1, 1

2, 3, 1, 0, 1

0, 1, 2, 2, 0

2, 3,1,2,0

Question No: 41 ( Marks: 2 )

Let

1 3 7

5 2 9

A é ù

= ê ú

ë û

then find At

Question No: 42 ( Marks: 2 )

Write the contra positive of the following statements:

1. For all integers n, if n2 is odd then n is odd.

2. If m and n are odd integers, then m+n is even integer.

Come & Join Us at www.vustudents.ning.com

Question No: 43 ( Marks: 2 )

How many distinguishable ways can the letter of the word

HULLABALOO be arranged.

Question No: 44 ( Marks: 3 )

Find the variance 2 of the distribution given in the following

table.

xi 1 3 4 5

f(xi) 0.4 0.1 0.2 0.3

Ans:

3

Question No: 45 ( Marks: 3 )

Prove that every integer is a rational number.

Question No: 46 ( Marks: 3 )

a. Evaluate P(5,2)

b. How many 5-permutations are there of a set of five

objects?

Question No: 47 ( Marks: 5 )

Come & Join Us at www.vustudents.ning.com

Is it possible to have a simple graph with four vertices of degree

1, 1, 3, and 3.If no then give reason?(Justify your answer)

Question No: 48 ( Marks: 5 )

Find the GCD of 500008, 78 using Division Algorithm.

Question No: 49 ( Marks: 5 )

Find the M number of ways that ten chocolates can be divided

among three children if the youngest child is to receive four

chocolates and each of the others three chocolates.

Question No: 50 ( Marks: 10 )

In the graph below, determine whether the following walks are

paths, simple paths, closed walks, circuits,

simple circuits, or are just walk?

Come & Join Us at www.vustudents.ning.com

i) v0 e1 v1 e10 v5 e9 v2 e2 v1

ii) v4 e7 v2 e9 v5 e10 v1 e3 v2 e9 v5

iii) v2

iv) v5 v2 v3 v4 v4v5

v) v2 v3 v4 v5 v2v4 v3 v2

FINALTERM EXAMINATION

Spring 2010

MTH202- Discrete Mathematics (Session - 1)

Time: 90 min

Marks: 60

Come & Join Us at www.vustudents.ning.com

Question No: 1 ( Marks: 1 ) - Please choose one

Whether the relation R on the set of all integers is reflexive,

symmetric, antisymmetric, or transitive, where (x, yR if and only

if xy ³1

► Antisymmetric

► Transitive

Symmetric

► Both Symmetric and transitive

Question No: 2 ( Marks: 1 ) - Please choose one

For a binary relation R defined on a set A , if for all

t Î A,(t,tR then R is

Antisymmetric

► Symmetric

► Irreflexive

Question No: 3 ( Marks: 1 ) - Please choose one

If ( AÈB ) = A, then ( AÇB ) = B

► True

False

► Cannot be determined

Question No: 4 ( Marks: 1 ) - Please choose one

Let

0 1 2

2

0

1, 2 3

j

j

a a and a

then a

=

= = - =

å =

►-6

Come & Join Us at www.vustudents.ning.com

2

►8

Question No: 5 ( Marks: 1 ) - Please choose one

The part of definition which can be expressed in terms of smaller

versions of itself is called

► Base

► Restriction

Recursion

► Conclusion

Question No: 6 ( Marks: 1 ) - Please choose one

What is the smallest integer N such that 9

6

éN ù = êê úú

► 46

► 29

49

Question No: 7 ( Marks: 1 ) - Please choose one

In probability distribution random variable f satisfies the

conditions

1

( ) 0 ( ) 1

n

i i

i

f x and f x

=

£ å ¹

1

( ) 0 ( ) 1

n

i i

i

f x and f x

=

³ å =

1

( ) 0 ( ) 1

n

i i

i

f x and f x

=

³ å ¹

1

( ) 0 ( ) 1

n

i i

i

f x and f x

=

p å =

Come & Join Us at www.vustudents.ning.com

Question No: 8 ( Marks: 1 ) - Please choose one

What is the probability that a hand of five cards contains

four cards of one kind?

► 0.0018

► 1

2

0.0024

Question No: 9 ( Marks: 1 ) - Please choose one

A rule that assigns a numerical value to each outcome in a

sample space is called

► One to one function

► Conditional probability

Random variable

Question No: 10 ( Marks: 1 ) - Please choose one

A walk that starts and ends at the same vertex is called

► Simple walk

► Circuit

Closed walk

Question No: 11 ( Marks: 1 ) - Please choose one

The Hamiltonian circuit for the following graph is

Come & Join Us at www.vustudents.ning.com

► abcdefgh

► abefgha

abcdefgha

Question No: 12 ( Marks: 1 ) - Please choose one

Distributive law of union over intersection for three sets

► A E (B E C) = (A E B) E C

► A C (B C C) = (A C B) C C

A E (B C C) = (A E B) C (A E B)

► None of these

Question No: 13 ( Marks: 1 ) - Please choose one

The indirect proof of a statement paq involves

►Considering ~q and then try to reach ~p

►Considering p and ~q and try to reach contradiction

*Both 2 and 3 above

Come & Join Us at www.vustudents.ning.com

►Considering p and then try to reach q

Question No: 14 ( Marks: 1 ) - Please choose one

The square root of every prime number is irrational

True

► False

► Depends on the prime number given

Question No: 15 ( Marks: 1 ) - Please choose one

If a and b are any positive integers with b≠0 and q and r are non

negative integers such that a= b.q+r then

gcd(a,b)=gcd(b,r)

► gcd(a,r)=gcd(b,r)

► gcd(a,q)=gcd(q,r)

Question No: 16 ( Marks: 1 ) - Please choose one

The greatest common divisor of 27 and 72 is

► 27

9

► 1

Come & Join Us at www.vustudents.ning.com

► None of these

Question No: 17 ( Marks: 1 ) - Please choose one

In how many ways can a set of five letters be selected from the

English Alphabets?

C(26,5)

► C(5,26)

► C(12,3)

► None of these

Question No: 18 ( Marks: 1 ) - Please choose one

A vertex of degree greater than 1 in a tree is called a

Branch vertex

► Terminal vertex

► Ancestor

Question No: 19 ( Marks: 1 ) - Please choose one

For the given pair of graphs whether it is

Come & Join Us at www.vustudents.ning.com

► Isomorphic

Not isomorphic

Question No: 20 ( Marks: 1 ) - Please choose one

The value of (-2)! Is

► 0

► 1

Cannot be determined

Question No: 21 ( Marks: 1 ) - Please choose one

In the following graph

Come & Join Us at www.vustudents.ning.com

How many simple paths are there from 1 v to 4 v

► 2

3

► 4

Question No: 22 ( Marks: 1 ) - Please choose one

The value of ( )

( 1)!

1 !

n

n

+

- is

► 0

n(n-1)

n2 + n

► Cannot be determined

Question No: 23 ( Marks: 1 ) - Please choose one

If A and B are finite (overlapping) sets, then which of the

following must be true

► n(AEB) = n(A) + n(B)

n(AEB) = n(A) + n(B) - n(ACB) page238

Come & Join Us at www.vustudents.ning.com

► n(AEB)= o

► None of these

Question No: 24 ( Marks: 1 ) - Please choose one

Any two spanning trees for a graph

► Does not contain same number of edges

► Have the same degree of corresponding edges

► contain same number of edges

► May or may not contain same number of edges

Question No: 25 ( Marks: 1 ) - Please choose one

When 3k is even, then 3k+3k+3k is an odd.

► True

False

Question No: 26 ( Marks: 1 ) - Please choose one

Quotient –Remainder Theorem states that for any positive

integer d, there exist unique integer q and r such that n=d.q+ r

and _______________.

0r<d

► 0<r<d

► 0≤d<r

► None of these

Question No: 27 ( Marks: 1 ) - Please choose one

The value of éêxùú for x = -3.01 is

-3.01

► -3

► -2

Come & Join Us at www.vustudents.ning.com

► -1.99

Question No: 28 ( Marks: 1 ) - Please choose one

If p= A Pentium 4 computer,

q= attached with ups.

Then "no Pentium 4 computer is attached with ups" is denoted

by

► ~ (pUq)

► ~ pUq

► ~ pUq

None of these

Question No: 29 ( Marks: 1 ) - Please choose one

An integer n is prime if and only if n > 1 and for all positive

integers r and s, if

n = r·s, then

►r = 1 or s = 2.

►r = 1 or s = 0.

►r = 2 or s = 3.

►None of these

Question No: 30 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

If P(AÇB) ¹ P(A)P(B) then the events A and B are called

►Independent

Dependent

►Exhaustive

Question No: 31 ( Marks: 2 )

Let A and B be the events. Rewrite the following event using set

notation

“Only A occurs”

Question No: 32 ( Marks: 2 )

Suppose that a connected planar simple graph has 15 edges. If a

plane drawing of this graph has 7 faces, how many vertices does

this graph have?

Answer:

Given,

Edges = e =15

Faces = f = 7

Vertices = v =?

According toEuler Formula, we know that,

f= e – v +2

Putting values, we get

7 = 15 – v + 2

7 = 17 – v

Simplifying

v =1 7-7 =10

Come & Join Us at www.vustudents.ning.com

Question No: 33 ( Marks: 2 )

How many ordered selections of two elements can be made from

the set {0,1,2,3}?

Answer

The order selection of two elements from 4 is as

P(4,2) = 4!/(4-2)!

= (4.3.2.1)/2!

= 12

Question No: 34 ( Marks: 3 )

Consider the following events for a family with children:

A={children of both sexes}, B={at most one boy}.Show that A and

B are dependent events if a family has only two children.

Question No: 35 ( Marks: 3 )

Determine the chromatic number of the given graph by

inspection.

Question No: 36 ( Marks: 3 )

Come & Join Us at www.vustudents.ning.com

A cafeteria offers a choice of two soups, five sandwiches, three

desserts and three drinks. How many different lunches, each

consisting of a soup, a sandwiche, a dessert and a drink are

possible?

Question No: 37 ( Marks: 5 )

A box contains 15 items, 4 of which are defective and 11 are good.

Two items are selected. What is probability that the first is good

and the second defective?

Answer

Question No: 38 ( Marks: 5 )

Draw a binary tree with height 3 and having seven terminal

vertices.

Answer: page324

Given height=h=3

Any binary tree with height 3 has almost 23=8 terminal vertices.

But here terminal vertices are 7 and Internal vertices=k=6 so

binary trees exist:

Question No: 39 ( Marks: 5 )

Find n if

P(n,2) = 72

(a) P(n,2) = 72

SOLUTION:

(a) Given P(n,2) = 72

Þ n × (n-1) = 72 (by using the definition of permutation)

Þ n2 -n = 72

Þ n2 - n - 72 = 0

Þ n = 9, -8

FINALTERM EXAMINATION

Fall 2009

MTH202- Discrete Mathematics

Time: 120 min

Marks: 80

Question No: 1 ( Marks: 1 ) - Please choose one

The negation of “Today is Friday” is

Today is Saturday

Today is not Friday

Come & Join Us at www.vustudents.ning.com

Today is Thursday

Question No: 2 ( Marks: 1 ) - Please choose one

In method of proof by contradiction, we suppose the

statement to be proved is false.

True

False

Question No: 3 ( Marks: 1 ) - Please choose one

Whether the relation R on the set of all integers is reflexive,

symmetric, antisymmetric, or transitive, where (x, yR if and

only if xy ³1

Antisymmetric

Transitive

Symmetric

Come & Join Us at www.vustudents.ning.com

Both Symmetric and transitive

Question No: 4 ( Marks: 1 ) - Please choose one

The inverse of given relation R = {(1,1),(1,2),(1,4),(3,4),

(4,1)} is

{(1,1),(2,1),(4,1),(2,3)}

{(1,1),(1,2),(4,1),( 4,3),(1,4)}

{(1,1),(2,1),(4,1),(4,3),(1,4)}

Question No: 5 ( Marks: 1 ) - Please choose one

A circuit with one input and one output signal is called.

NOT-gate (or inverter)

OR- gate

AND- gate

None of these

Question No: 6 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

A sequence in which common difference of two consecutive

terms is same is called

geometric mean

harmonic sequence

geometric sequence

arithmetic progression page147

Question No: 7 ( Marks: 1 ) - Please choose one

If the sequence { } 2.( 3) 5 n n

n a = - + then the term ! a is

-1

0

1

2

Question No: 8 ( Marks: 1 ) - Please choose one

How many integers from 1 through 100 must you pick in order

to be sure of getting one that is divisible by 5?

Come & Join Us at www.vustudents.ning.com

21

► 41

► 81

► 56

Question No: 9 ( Marks: 1 ) - Please choose one

What is the probability that a randomly chosen positive

two-digit number is a multiple of 6?

0.5213

0.167 pg252

0.123

Question No: 10 ( Marks: 1 ) – Please choose one

If a pair of dice is thrown then the probability of getting a

total of 5 or 11 is

Come & Join Us at www.vustudents.ning.com

1

18

1

9

1

6

pg256

Question No: 11 ( Marks: 1 ) - Please choose one

If a die is rolled then what is the probability that the

number is greater than 4

1

3

3

4

1

2

Question No: 12 ( Marks: 1 ) - Please choose one

If a coin is tossed then what is the probability that the

number is 5

Come & Join Us at www.vustudents.ning.com

1

2

0

1

Question No: 13 ( Marks: 1 ) - Please choose one

If A and B are two sets then The set of all elements that

belong to both A and B , is

A B

A U B

A--B

None of these

Question No: 14 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

If A and B are two sets then The set of all elements that

belong to A but not B , is

► A  B

► A  B

► None of these

► A-B

Question No: 15 ( Marks: 1 ) - Please choose one

If A, B and C are any three events, then

P(ABC) is equal to

P(A) + P(B) + P(C)

P(A) + P(B) + P(C)- P(AB) - P (A C) - P(B C) + P(A B

C)

P(A) + P(B) + P(C) - P(AB) - P (A C) - P(B C)

P(A) + P(B) + P(C) + P(A B C)

Question No: 16 ( Marks: 1 ) - Please choose one

If a graph has any vertex of degree 3 then

Come & Join Us at www.vustudents.ning.com

It must have Euler circuit

It must have Hamiltonian circuit

It does not have Euler circuit

Question No: 17 ( Marks: 1 ) - Please choose one

The contradiction proof of a statement pq involves

Considering p and then try to reach q

► Considering ~q and then try to reach ~p

► Considering p and ~q and try to reach contradiction

► None of these

Question No: 18 ( Marks: 1 ) - Please choose one

How many ways are there to select a first prize winner a

second prize winner, and a third prize winner from 100

different people who have entered in a contest.

► None of these

P(100,3)

Come & Join Us at www.vustudents.ning.com

► P(100,97)

► P(97,3)

Question No: 19 ( Marks: 1 ) - Please choose one

A vertex of degree 1 in a tree is called a

Terminal vertex

Internal vertex

Question No: 20 ( Marks: 1 ) - Please choose one

Suppose that a connected planar simple graph has 30 edges.

If a plane drawing of this graph has 20 faces, how many

vertices does the graph have?

12

13

Come & Join Us at www.vustudents.ning.com

14

Question No: 21 ( Marks: 1 ) - Please choose one

How many different ways can three of the letters of the

word BYTES be chosen if the first letter must be B ?

P(4,2)

P(2,4)

C(4,2)

None of these

Question No: 22 ( Marks: 1 ) - Please choose one

For the given pair of graphs whether it is

Come & Join Us at www.vustudents.ning.com

Isomorphic

Not isomorphic

Question No: 23 ( Marks: 1 ) - Please choose one

On the set of graphs the graph isomorphism is

Isomorphic Invariant

Come & Join Us at www.vustudents.ning.com

Equivalence relation pg304

Reflexive relation

Question No: 24 ( Marks: 1 ) - Please choose one

A matrix in which number of rows and columns are equal is

called

Rectangular Matrix

Square Matrix

Scalar Matrix

Question No: 25 ( Marks: 1 ) - Please choose one

If the transpose of any square matrix and that matrix are

same then matrix is called

Additive Inverse

Hermition Matrix

Symmetric Matrix

Come & Join Us at www.vustudents.ning.com

Question No: 26 ( Marks: 1 ) - Please choose one

The number of k-combinations that can be chosen from a set

of n elements can be written as

nCk pg223

kCn

nPk

kPk

Question No: 27 ( Marks: 1 ) - Please choose one

The value of C (n, 0) =

1

0

n

None of these

Come & Join Us at www.vustudents.ning.com

Question No: 28 ( Marks: 1 ) - Please choose one

If the order does not matter and repetition is not allowed

then total number of ways for selecting k sample from n. is

P(n,k)

C(n,k) pg228

nk

► C(n+k-1,k)

Question No: 29 ( Marks: 1 ) - Please choose one

If A and B are two disjoint sets then which of the following

must be true

n(AB) = n(A) + n(B)

n(AB) = n(A) + n(B) - n(AB)

Come & Join Us at www.vustudents.ning.com

n(AB)= o

None of these

Question No: 30 ( Marks: 1 ) - Please choose one

Among 200 people, 150 either swim or jog or both. If 85

swim and 60 swim and jog, how many jog?

125 pg239

225

85

25

Question No: 31 ( Marks: 1 ) - Please choose one

If two sets are disjoint, then PQ is

Come & Join Us at www.vustudents.ning.com

P

Q

PQ

Question No: 32 ( Marks: 1 ) - Please choose one

Every connected tree

does not have spanning tree

may or may not have spanning tree

has a spanning tree

Question No: 33 ( Marks: 1 ) - Please choose one

When P(k) and P(k+1) are true for any positive integer k,

then P(n) is not true for all +ve Integers.

True

False

Come & Join Us at www.vustudents.ning.com

Question No: 34 ( Marks: 1 ) - Please choose one

When 3k is even, then 3k+3k+3k is an odd.

True

False

Question No: 35 ( Marks: 1 ) - Please choose one

5n -1 is divisible by 4 for all positive integer values of n.

True

False

Question No: 36 ( Marks: 1 ) - Please choose one

Quotient –Remainder Theorem states that for any positive

integer d, there exist unique integer q and r such that n=d.q+

r and _______________.

0r<d

0<r<d

0d<r

Come & Join Us at www.vustudents.ning.com

None of these

Question No: 37 ( Marks: 1 ) - Please choose one

The given graph is

Simple graph

Complete graph

Bipartite graph

Both (i) and (ii)

Both (i) and (iii)

Question No: 38 ( Marks: 1 ) - Please choose one

Come & Join Us at www.vustudents.ning.com

An integer n is even if and only if n = 2k for some integer k.

True

False

Depends on the value of k

Question No: 39 ( Marks: 1 ) - Please choose one

The word "algorithm" refers to a step-by-step method for

performing some action.

True

False

Come & Join Us at www.vustudents.ning.com

None of these

Question No: 40 ( Marks: 1 ) - Please choose one

The adjacency matrix for the given graph is

0 1 1 0 0

1 0 0 1 0

1 0 0 1 1

0 0 1 0 1

1 0 0 1 0

é ù

ê ú

ê ú

ê ú

ê ú

ê ú

êë úû

0 1 1 0 1

1 0 0 0 0

1 0 0 1 1

0 0 1 0 1

1 0 1 1 0

é ù

ê ú

ê ú

ê ú

ê ú

ê ú

êë úû

Come & Join Us at www.vustudents.ning.com

0 1 0 0 1

1 0 0 0 0

1 0 0 1 0

0 0 1 0 1

0 0 1 1 0

é ù

ê ú

ê ú

ê ú

ê ú

ê ú

êë úû

None of these

Question No: 41 ( Marks: 2 )

Let A and B be events with

( ) 1 , ( ) 1 and ( ) 1

2 3 4

P A = P B = P AÇB =

Find

P(B | A)

Ans =

P(A B) = P(A) P(B|A)

P(B|A)= P(A B)/ P(A)

= 0.5

Question No: 42 ( Marks: 2 )

Come & Join Us at www.vustudents.ning.com

Suppose that a connected planar simple graph has 15 edges.

If a plane drawing of this graph has 7 faces, how many

vertices does this graph have?

Vertices-edges+faces=2

V - 15 +7=2

V -8 = 2

V =10

Question No: 43 ( Marks: 2 )

Find integers q and r so that a=bq+r , with 0r<b.

a=45 , b=6.

Question No: 44 ( Marks: 3 )

Draw a graph with six vertices, five edges that is not a tree.

Asn:

Here is the graph with six vertices, five edges that is not a

tree

Come & Join Us at www.vustudents.ning.com

Question No: 45 ( Marks: 3 )

Prove that every integer is a rational number.

Ans:

Every integer is a rational number, since each integer n can

be written in the form n/1. For example 5 = 5/1 and thus 5

is a rational number. However, numbers like 1/2,

45454737/2424242, and -3/7 are also rational; since they

are fractions whose numerator and denominator are integers.

Question No: 46 ( Marks: 3 )

b. Evaluate P(5,2)

c. How many 4-permutations are there of a set of seven

objects?

Question No: 47 ( Marks: 5 )

Find the GCD of 500008, 78 using Division Algorithm.

Come & Join Us at www.vustudents.ning.com

Question No: 48 ( Marks: 5 )

There are 25 people who work in an office together. Four

of these people are selected to attend four different

conferences. The first person selected will go to a

conference in New York, the second will go to Chicago, the

third to San Franciso, and the fourth to Miami. How many

such selections are possible?

Ans= 12650

Question No: 49 ( Marks: 5 )

Consider the following graph

(a) How many simple paths are there from 1 v to 4 v ====1

Come & Join Us at www.vustudents.ning.com

(b) How many paths are there from 1 v to 4 v ?

===========3

(c) How many walks are there from 1 v to 4 v ?==========3

Question No: 50 ( Marks: 10 )

In the graph below, determine whether the following walks

are paths, simple paths, closed walks, circuits,

simple circuits, or are just walk?

vi) v0 e1 v1 e10 v5 e9 v2 e2 v1== paths

vii)v4 e7 v2 e9 v5 e10 v1 e3 v2 e9 v5========, circuits

viii) v2========== closed walks

ix) v5 v2 v3 v4 v4v5=========== closed walks

x) v2 v3 v4 v5 v2v4 v3 v2========= paths

Subjective types short answer:

&

Important definitions:

Question: What does it mean by the preservation of edge end

point function in the definition of isomorphism of

graphs?

Answer: Since you know that we are looking for two functions

(Suppose one function is “f” and other function is “g”)

which preserve the edge end point function and this

preservation means that if we have vi as an end point

of the edge ej then f(vi) must be an end point of the

edge g(ej) and also the converse that is if f(vi) be an

end point of the edge g(ej) then we must have vi as an

end point of the edge ej. Note that vi and ej are the

vertex and edge of one graph respectively where as f

(vi) and g (ej) are the vertex and edge in the other

graph respectively.

Question: Is there any method of identifying that the given

graphs are isomorphic or not?(With out finding out

two functions).

Answer: Unfortunately there is no such method which will

Come & Join Us at www.vustudents.ning.com

identify whether the given graphs are isomorphic or

not. In order to find out whether the two given graphs

are isomorphic first we have to find out all the

bijective mappings from the set vertices of one graph

to the set of vertices of the other graph then find out

all the bijective functions from the set of edges of

one graph to the set of edges of the other graph. Then

see which mappings preserve the edge end point

function as defined in the definition of Isomorphism

of graphs. But it is easy to identify that the two

graphs are not isomorphic. First of all note that if

there is any Isomorphic Invariant not satisfied by

both the graphs, then we will say that the graphs are

not Isomorphic. Note that if all the isomorphic

Invariants are satisfied by two graphs then we can’t

conclude that the graphs are isomorphic. In order to

prove that the graphs are isomorphic we have to find

out two functions which satisfied the condition as

defined in the definition of Isomorphism of graphs.

Question: What are Complementary Graphs?

Answer: Complementary Graph of a simple graph(G) is denoted

by the (G bar ) and has as many vertices as G but two

vertices are adjacent in complementary Graph by an

edge if and only if these two vertices are not adjacent

in G .

Question: What is the application of isomorphism in real word?

Answer: There are many applications of the graph theory in

computer Science as well as in the Practical life; some

of them are given below. (1) Now you also go through

the puzzles like that we have to go through these

points without lifting the pencil and without repeating

our path. These puzzles can be solved by the Euler and

Come & Join Us at www.vustudents.ning.com

Hamiltonian circuits. (2) Graph theory as well as Trees

has applications in “DATA STRUCTURE" in which you

will use trees, especially binary trees in manipulating

the data in your programs. Also there is a common

application of the trees is "FAMILY TREE”. In which

we represent a family using the trees. (3) Another

example of the directed Graph is "The World Wide

Web ". The files are the vertices. A link from one file

to another is a directed edge (or arc). These are the

few examples.

Question: Are Isomorphic graphs are reflexive, symmetric and

transitive?

Answer: We always talk about " RELXIVITY"" SYMMETRIC"

and TRANSIVITY of a relation. We never say that a

graph is reflexive, symmetric or transitive. But also

remember that we draw the graph of a relation which

is reflexive and symmetric and the property of

reflexivity and symmetric is evident from the graphs,

we can’t draw the graph of a relation such that

transitive property of the relation is evident. Now

consider the set of all graphs say it G, this being a

set ,so we can define a relation from the set G to

itself. So we define the relation of Isomorphism on

the set G x G.( By the definition of isomorphism) Our

claim is that this relation is an " Equivalence Relation"

which means that the relation of Isomorphism’s of two

graphs is "REFLEXIVE" "SYMMETRIC" and

"TRANSITIVE". Now if you want to draw the graph of

this relation, then the vertices of this graph are the

graphs from the set G.

Question: Why we can't use the same color in connected portions

of planar graph?

Come & Join Us at www.vustudents.ning.com

Answer: We define the coloring of graph in such a manner that

we can’t assign the same color to the adjacent vertices

because if we give the same colors to the adjacent

vertices then they are indistinguishable. Also note that

we can give the same color to the adjacent vertices but

such a coloring is called improper coloring and the way

which we define the coloring is known as the proper

coloring. We are interested in proper coloring that’s

why all the books consider the proper coloring

Question: What is meant by isomorphic invariant?

Answer: A property "P" of a graph is known as Isomorphic

invariant. if the same property is found in all the

graphs which are isomorphic to it. And all these

properties are called isomorphic invariant (Also it clear

from the words Isomorphic Invariant that the

properties which remain invariant if the two graphs

are isomorphic to each other).

Question: What is an infinite Face?

Answer: When you draw a Planar Graph on a plane it divides the

plane into different regions, these regions are known

as the faces and the face which is not bounded by the

edges of the graph is known as the Infinite face. In

other words the region which is unbounded is known as

Infinite Face.

Question: What is "Bipartite Graph”?

Answer: A graph is said to be Bipartite if it’s set of vertices

can be divided into two disjoint sets such that no two

vertices of the same set are adjacent by some edge of

the graph. It means that the edges of one set will be

adjacent with the vertices of the other set.

Question: What is chromatic number?

Answer: While coloring a graph you can color a vertex which is

Come & Join Us at www.vustudents.ning.com

not adjacent with the vertices you already colored by

choosing a new color for it or by the same color which

you have used for the vertices which are not adjacent

with this vertex. It means that while coloring a graph

you may have different number of colors used for this

purpose. But the least number of colors which are

being used during the coloring of Graphs is known as

the Chromatic number.

Question: What is the role of Discrete mathematics in our

prectical life. what advantages will we get by

learning it.

Answer: In many areas people have to faces many mathematical

problems which can,t be solved in computer so discrete

mathematics provide the facility to overcome these

problems. Discrete math also covers the wide range of

topics, starting with the foundations of Logic, Sets

and Functions. It moves onto integer mathematics and

matrices, number theory, mathematical reasoning,

probability graphs, tree data structures and Boolean

algebra.So that is why we need discrete math.

Question: What is the De Morgan's law .

Answer: De Morgan law states " Negation of the conjunction of

two statements is logiacally equivalent to the

disjunction of their negation and Negation of the

disjunction of two statements is logically equivalent to

the conjucnction of their negation". i.e. ~(p^q) = ~p v

~q and ~(p v q)= ~p ^ ~q For example: " The bus was

late and jim is waiting "(this is an example of

conjuction of two statements) Now apply neaggation on

this statement you will get through De Morgan's law "

The bus was not late or jim is not waiting" (this is the

disjunction of negation of two statements). Now see

Come & Join Us at www.vustudents.ning.com

both statement are logically equivalent.Thats what De

Morgan want to say

Question: What is Tauology?

Answer: A tautology is a statement form that is always true

regardless of the truth values of the statement

variables. i.e. If you want to prove that (p v q) is

tautology ,you have to show that all values of

statement (p v q) are true regardless of the values of

p and q.If all the values of the satement (p v q) is not

true then this statement is not tautology.

Question: What is binary relations and reflexive,symmetric

and transitive.

Answer: Dear student! First of all ,I will tell you about the

basic meaning of relation i.e It is a logical or natural

association between two or more things; relevance of

one to another; the relation between smoking and

heart disease. The connection of people by blood or

marriage. A person connected to another by blood or

marriage; a relative. Or the way in which one person or

thing is connected with another: the relation of parent

to child. Now we turn to its mathematically definition,

let A and B be any two sets. Then their cartesian

product (or the product set) means a new set "A x B "

which contains all the ordered pairs of the form (a,b)

where a is in set A and b is in set B. Then if we take

any subset say 'R' of "A x B" ,then 'R' is called the

binary relation. Note All the subsets of the Cartesian

product of two sets A and B are called the binary

relations or simply a relation,and denoted by R. And

note it that one raltion is also be the same as "A x B".

Example: Let A={1,2,3} B={a,b} be any two sets. Then

their Cartesian product means "A x B"={ (1,a),(1,b),

Come & Join Us at www.vustudents.ning.com

(2,a),(2,b),(3,a),(3,b) } Then take any set which

contains in "A x B" and denote it by 'R'. Let we take

R={(2,b),(3,a),(3,b)} form "A x B". Clearly R is a subset

of "A x B" so 'R' is called the binary relation. A

reflexive relation defined on a set say ‘A’ means “all

the ordered pairs in which 1st element is mapped or

related to itself.” For example take a relation say R1=

{(1,1), (1,2), (1,3), (2,2) ,(2,1), (3,1) (3,3)} from “A x B”

defined on the set A={1,2,3}. Clearly R1 is reflexive

because 1,2 and 3 are related to itself. A relation say

R on a set A is symmetric if whenever aRb then

bRa,that is ,if whenever (a,b) belongs to R then (b,a)

belongs to R for all a,b belongs to A. For example given

a relation which is R1={(1,1), (1,2), (1,3), (2,2) ,(2,1),

(3,1) (3,3)} as defined on a set A={1,2,3} And a relation

say R1 is symmetric if for every (a, b) belongs to R ,(b,

a) also belongs to R. Here as (a, b)=(1,1) belongs to R

then (b, a)=(1,1)also belongs to R. as (a,b)=(1,2) belongs

to R then (b,a)=(2,1)also belongs to R. as (a,b)=(1,3)

belongs to R then (b,a)=(3,1)also belongs to R.etc So

clearly the above relation R is symmetric. And read the

definition of transitive relation from the handouts and

the book. You can easily understand it.

Question: What is the matrix relation .

Answer: Suppose that A and B are finite sets.Then we take a

relation say R from A to B. From a rectangular array

whose rows are labeled by the elements of A and

whose columns are labeled by the elements of B. Put a

1 or 0 in each position of the array according as a

belongs to A is or is not related to b belongs to B. This

array is called the matrix of the relation. There are

matrix relations of reflexive and symmetric relations.

Come & Join Us at www.vustudents.ning.com

In reflexive relation, all the diagonal elements of

relation should be equal to 1. For example if R = {(1,1),

(1,3), (2,2), (3,2), (3,3)} defined on A = {1,2,3}. Then

clearly R is reflexive. Simply in making matrix relation

In the above example,as the defined set is A={1,2,3} so

there are total three elements. Now we take 1, 2 and 3

horizontally and vertically.i.e we make a matrix from

the relation R ,in the matrix you have now 3 columns

and 3 rows. Now start to make the matrix ,as you have

first order pair (1, 1) it means that 1 maps on itself and

you write 1 in 1st row and in first column. 2nd order

pair is (1, 3) it means that arrow goes from 1 to 3.Then

you have to write 1 in 1st row and in 3rd column. (2, 2)

means that arrow goes from 2 and ends itself. Here

you have to write 1 in 2nd row and in 2nd column. (3,2)

means arrow goes from 3 and ends at 2. Here you have

to write 1 in 3rd row and in 2nd column. (3, 3) means

that 3 maps on itself and you write 1 in 3rd row and in

3rd column. And where there is space empty or unfilled

,you have to write 0 there.

Question: what is binary relation.

Answer: Let A and B be any two sets. Then their cartesian

product(or the product set) means a new set "A x B "

which contains all the ordered pairs of the form (a,b)

where a is in set A and b is in set B. Let we take any

subset say 'R' of "A x B" ,then 'R' is called the binary

relation. Note it that 'R' also be the same as "A x B".

For example: Let A={1,2,3} B={a,b} be any two sets.

Then their cartesian product means "A x B"={ (1,a),

(1,b),(2,a),(2,b),(3,a),(3,b) } Then take any set which

contains in "A x B" and denote it by 'R'. Let R={(2,b),

(3,a),(3,b)} Clearly R is a subset of "A x B" so 'R' is

Come & Join Us at www.vustudents.ning.com

called the binary relation.

Question: Role of ''Discrete Mathematics'' in our prectical life.

what advantages will we get by learning it.

Answer: Discrete mathematics concerns processes that consist

of a sequence of individual steps. This distinguishes it

from calculus, which studies continuously changing

processes. While the ideas of calculus were

fundamental to the science and technology of the

industrial revolution, the ideas of discrete

mathematics underline the science and technology

specific to the computer age. Logic and proof: An

important goal of discrete mathematics is to develop

students’ ability to think abstractly. This requires that

students learn to use logically valid forms of argument,

to avoid common logical errors, to understand what it

means to reason from definition, and to know how to

use both direct and indirect argument to derive new

results from those already known to be true. Induction

and Recursion: An exciting development of recent

years has been increased appreciation for the power

and beauty of “recursive thinking”: using the

assumption that a given problem has been solved for

smaller cases, to solve it for a given case. Such

thinking often leads to recurrence relations, which can

be “solved” by various techniques, and to verifications

of solutions by mathematical induction. Combinatorics:

Combinatorics is the mathematics of counting and

arranging objects. Skill in using combinatorial

techniques is needed in almost every discipline where

mathematics is applied, from economics to biology, to

computer science, to chemistry, to business

management. Algorithms and their analysis: The word

Come & Join Us at www.vustudents.ning.com

algorithm was largely unknown three decades ago. Yet

now it is one of the first words encountered in the

study of computer science. To solve a problem on a

computer, it is necessary to find an algorithm or stepby-

step sequence of instructions for the computer to

follow. Designing an algorithm requires an

understanding of the mathematics underlying the

problem to be solved. Determining whether or not an

algorithm is correct requires a sophisticated use of

mathematical induction. Calculating the amount of time

or memory space the algorithm will need requires

knowledge of combinatorics, recurrence relations

functions, and O-notation. Discrete Structures:

Discrete mathematical structures are made of finite

or count ably infinite collections of objects that

satisfy certain properties. Those are sets, bolean of

algebras, functions, finite start automata, relations,

graphs and trees. The concept of isomorphism is used

to describe the state of affairs when two distinct

structures are the same intheir essentials and diffr

only in the labeling of the underlying objects.

Applications and modeling: Mathematics topic are best

understood when they are seen ina variety of contexts

and used to solve problems in a broad range of applied

situations. One of the profound lessons of

mathematics is that the same mathematical model can

be used to solve problems in situations that appear

superficially to be totally dissimilar. So in the end i

want to say that discrete mathematics has many uses

not only in computer science but also in the other

fields too.

Question: what is the basic difference b/w sequences and series

Come & Join Us at www.vustudents.ning.com

Answer: A sequence is just a list of elements .In sequnce we

write the terms of sequence as a list (seperated by

comma's). e.g 2,3,4,5,6,7,8,9,... ( in this we have terms

2,3,4,5,6,7,8,9 and so on).we write these in form of list

seperated by comma's. And the sum of the terms of a

sequence forms a series. e.g we have sequence

1,2,3,4,5,6,7 Now the series is sum of terms of

sequence as 1+2+3+4+5+6+7.

Question: what is the purpose of permutations?

Answer: Permutation is an arrangement of objects in a order

where repitition is not allowed. We need arrangments

of objects in real life and also in mathematical

problems.We need to know in how many ways we can

arrange certain objects. There are four types of

arrangments we have in which one is permutation.

Question: what is inclusion-exclusion principle

Answer: Inclusion-Exclusion principle contain two rules which

are If A and B are disjoint finite sets, then n(AEB) =

n(A) + n(B) And if A and B are finite sets, then n(AEB)

= n(A) + n(B) - n(ACB) For example If there are 15

girls students and 25 boys students in a class then how

many students are in total. Now see if we take A ={ 15

girl students} and B={ 25 boys students} Here A and B

are two disjoints sets then we can apply first rule

n(AEB) = n(A) + n(B) =15 + 25 =40 So in total there are

40 students in class. Take another Example for second

rule. How many integers from 1 through 1000 are

multiples of 3 or multiples of 5. Let A and B denotes

the set of integers from 1 through 1000 that are

multiples of 3 and 5 respectivly. n(A)= 333 n(B)=200

But these two sets are not disjoint because in A and B

we have those elements which are multiple of both 3

Come & Join Us at www.vustudents.ning.com

and 5. so n(ACB) =66 n(AEB) = n(A) + n(B) - n(ACB)

=333 + 200 - 66 = 467

Question: How to use conditional probobility

Answer: Dear student In Conditional probability we put some

condition on an event to be occur. e.g. A pair of dice is

tossed. Find the probability that one of the dice is 2 if

the sum is 6. If we have to find the probability that

one of the dice is 2, then it is the case of simple

probability. Here we put a condition that sum is six.

Now A = { 2 appears in atleast one die} E = {sum is 6 }

Here E = { (1,5), (2, 4), (3, 3), (4, 2), (5, 1) } Here two

order pairs ( 2, 4 ) and ( 4, 2) satisfies the A. (i.e.

belongs to A) Now A (intersection) B= { (2,4), (4,2)}

Now by formula P(A/E) = P(A (intersection) E)/ P(E) =

2/5

Question: In which condition we use combination and in which

condition permutation.

Answer: This depends on the statement of question. If in the

statement of question you finds out that repetition of

objects are not allowed and order matters then we use

Permutation. e.g. Find the number of ways that a party

of seven persons can arrange themselves in a row of

seven chairs. See in this question repetition is no

allowed because whenever a person is chosen for a

particular seat r then he cannot be chosen again and

also order matters in the arrangements of chairs so we

use permutation here. If in the question repetition of

samples are not allowed and order does not matters

then we use combination. A student is to answer eight

out of ten questions on an exam. Find the number m of

ways that the student can choose the eight questions

See in this question repetition is not allowed that is

Come & Join Us at www.vustudents.ning.com

when you choose one question then you cannot choose

it again and also order does not matters(i.e either he

solved Q1 first or Q2 first) so you use combination in

this question.

Question: What is the differnce between edge and vertex

Answer: Vertices are nodes or points and edges are lines/arcs

which are used to connect the vertices. e.g If you are

making the graph to find the shortest path or for nay

purpose of cites and roads between them which

contain Lahore, Islamabad, Faisalabad , Karachi, and

Multan. Then cities Lahore, Islamabad, Faisalabad ,

Karachi, and Multan are vertices and roads between

them are edges.

Question: What is the differnce between yes and allowed in

graphs.

Answer: Allowed mean that specific property can be occurs in

that case but yes mean that specific property always

occurs in that case. e.g. In Walk you may start and end

at same point and may not be (allowed). But in Closed

Walk you have to start and end at same point (yes).

Question: what is the meanging of induction? and also

Mathematical Induction?

Answer: Basic meaning of induction is: a)The act or an instance

of inducting. b) A ceremony or formal act by which a

person is inducted, as into office or military service.

In Mathematics. A two-part method of proving a

theorem involving a positive integral variable. First the

theorem is verified for the smallest admissible value

of the integer. Then it is proven that if the theorem is

true for any value of the integer, it is true for the

next greater value. The final proof contains the two

parts. As you have studied. It also means that

Come & Join Us at www.vustudents.ning.com

presentation of material, such as facts or evidence, in

support of an argument or a proposition. Whether in

Physics Induction means the creation of a voltage or

current in a material by means of electric or magnetic

fields, as in the secondary winding of a transformer

when exposed to the changing magnetic field caused by

an alternating current in the primary winding. In

Biochemistry,it means that the process of initiating or

increasing the production of an enzyme or other

protein at the level of genetic transcription. In

embryology,it means that the change in form or shape

caused by the action of one tissue of an embryo on

adjacent tissues or parts, as by the diffusion of

hormones or chemicals.

Question: How to use conditional probobility

Answer: Dear student In Conditional probability we put some

condition on an event to be occur. e.g. A pair of dice is

tossed. Find the probability that one of the dice is 2 if

the sum is 6. If we have to find the probability that

one of the dice is 2, then it is the case of simple

probability. Here we put a condition that sum is six.

Now A = { 2 appears in atleast one die} E = {sum is 6 }

Here E = { (1,5), (2, 4), (3, 3), (4, 2), (5, 1) } Here two

order pairs ( 2, 4 ) and ( 4, 2) satisfies the A. (i.e.

belongs to A) Now A (intersection) B= { (2,4), (4,2)}

Now by formula P(A/E) = P(A (intersection) E)/ P(E) =

2/5

Question: In which condition we use combination and in which

condition permutation.

Answer: This depends on the statement of question. If in the

statement of question you finds out that repetition of

objects are not allowed and order matters then we use

Come & Join Us at www.vustudents.ning.com

Permutation. e.g. Find the number of ways that a party

of seven persons can arrange themselves in a row of

seven chairs. See in this question repetition is no

allowed because whenever a person is chosen for a

particular seat r then he cannot be chosen again and

also order matters in the arrangements of chairs so we

use permutation here. If in the question repetition of

samples are not allowed and order does not matters

then we use combination. A student is to answer eight

out of ten questions on an exam. Find the number m of

ways that the student can choose the eight questions

See in this question repetition is not allowed that is

when you choose one question then you cannot choose

it again and also order does not matters(i.e either he

solved Q1 first or Q2 first) so you use combination in

this question.

Question: What is the differnce between edge and vertex

Answer: Vertices are nodes or points and edges are lines/arcs

which are used to connect the vertices. e.g If you are

making the graph to find the shortest path or for nay

purpose of cites and roads between them which

contain Lahore, Islamabad, Faisalabad , Karachi, and

Multan. Then cities Lahore, Islamabad, Faisalabad ,

Karachi, and Multan are vertices and roads between

them are edges.

Question: What is the differnce between yes and allowed in

graphs.

Answer: Allowed mean that specific property can be occurs in

that case but yes mean that specific property always

occurs in that case. e.g. In Walk you may start and end

at same point and may not be (allowed). But in Closed

Walk you have to start and end at same point (yes).

Question: what is the meanging of induction? and also

Come & Join Us at www.vustudents.ning.com

Answer: Basic meaning of induction is: a)The act or an instance

of inducting. b) A ceremony or formal act by which a

person is inducted, as into office or military service.

In Mathematics. A two-part method of proving a

theorem involving a positive integral variable. First the

theorem is verified for the smallest admissible value

of the integer. Then it is proven that if the theorem is

true for any value of the integer, it is true for the

next greater value. The final proof contains the two

parts. As you have studied. It also means that

presentation of material, such as facts or evidence, in

support of an argument or a proposition. Whether in

Physics Induction means the creation of a voltage or

current in a material by means of electric or magnetic

fields, as in the secondary winding of a transformer

when exposed to the changing magnetic field caused by

an alternating current in the primary winding. In

Biochemistry,it means that the process of initiating or

increasing the production of an enzyme or other

protein at the level of genetic transcription. In

embryology,it means that the change in form or shape

caused by the action of one tissue of an embryo on

adjacent tissues or parts, as by the diffusion of

hormones or chemicals.

Question: What is "Hypothetical Syllogism".

Answer: Hypothetical syllogism is a law that if the argument is

of the form p --> q q---> r Therefore p---> r Then it'll

always be a tautology. i.e. if the p implies q and q

implies r is true then its conclusion p implies r is always

true.

Question: A set is define a well define collection of distinct

objects so why an empty set is called a set although it

Come & Join Us at www.vustudents.ning.com

has no element?

Answer: Some time we have collection of zero objects and we

call them empty sets. e.g. Set of natural numbers

greater than 5 and less than 5. A = { x belongs to N /

5< x < 5 } Now see this is a set which have collection of

elements which are greater than 5 and less than 5

( from natural number).

Question: What is improper subset.

Answer: Let A and B be sets. A is proper subset of B, if, and

only if, every element of A is in B but there is at least

on element if B that is not in A. Now A is improper

subset of B, if and only if, every element of A is in B

and there is no element in B which is not in A. e.g. A=

{ 1, 2 , 3, 4} B= { 2, 1, 4, 3} Now A is improper subset of

B. Because every element of A is in B and there is no

element in B which is not in A

Question: FAQ's in document Form

Answer: .

Question: How to check validity and unvalidity of argument

through diagram.

Answer: To check an argument is valid or not you can also use

Venn diagram. We identify some sets from the

premises . Then represent those sets in the form of

diagram. If diagram satisfies the conclusion then it is

a valid argument otherwise invalid. e.g. If we have

three premises S1: all my friends are musicians S2:

John is my friend. S3: None of my neighbor are

musicians. conclusion John is not my neighbor. Now we

have three sets Friends, Musicians, neighbors. Now you

see from premises 1 and 2 that friends are subset of

musicians .From premises 3 see that neighbor is an

individual set that is disjoint from set musicians. Now

Come & Join Us at www.vustudents.ning.com

represent then in form of Venn diagram. Musicians

neighbour Friends Now see that john lies in set friends

which is disjoint from set neighbors. So their

intersection is empty.Which shows that john is not his

neighbor. In that way you can check the validity of

arguments

Question: why we used venn digram?

Answer: Venn diagram is a pictorial representation of sets.

Venn diagram can sometime be used to determine

whether or not an argument is valid. Real life problems

can easily be illustrate through Venn diagram if you

first convert them into set form and then in Venn

diagram form. Venn diagram enables students to

organize similarities and differences visually or

graphically. A Venn diagram is an illustration of the

relationships between and among sets, groups of

objects that share something in common.

Question: what is composite relation .

Answer: Let A, B, and C be sets, and let R be relation from A to

B and let S be a relation from B to C. Now by

combining these two relations we can form a relation

from A to C. Now let a belongs to A, b belongs to B,

and c belongs to C. We can write relations R as a R b

and S as b S c. Now by combining R and S we write a (R

0 S) c . This is called composition of Relations holding

the condition that we must have a b belongs to B which

can be write as a R b and b S c (as stated above) . e.g.

Let A= {1,2,3,4}, B={a,b,c,d} , C ={x,y,z} and let

R={ {1,a), (2, d), (3, a), (3, b), (3, d) } and S={ (b, x), (b,

z), (c, y), (d, z)} Now apply that condition which is

stated above (that in the composition R O S only those

order pairs comes which have earlier an element is

Come & Join Us at www.vustudents.ning.com

common in them e.g. from R we have (3, b) and from S

we have ( b, x) .Now one relation relate 3 to b and

other relates b to x and our composite relation omits

that common and relates directly 3 to x.) I do not

understand your second question send it again. Now R

O S ={(2,z), (3,x), (3,z)}

Question: What are the conditions to confirm functions .

Answer: The first condition for a relation from set X to a set Y

to be a function is 1.For every element x in X, there is

an element y in Y such that (x, y) belongs to F. Which

means that every element in X should relate with

distinct element of Y. e.g if X={ 1,2,3} and Y={x, y} Now

if R={(1,x),(2,y),(1,y),(2,x)} Then R will not be a function

because 3 belongs to X but is does not relates with any

element of Y. so R={(1,x),(2,y),(3,y)} can be called a

function because every element of X is relates with

elements of Y. Second condition is : For all elements x

in X and y and z in Y, if (x, y) belongs to F and (x, z)

belongs to F, then y = z Which means that every

element in X only relates with distinct element of Y.

i.e. R={(1,x),(2,y),(2,x), (3,y)} cannot be called as

function because 2 relates with x and y also.

Question: When a function is onto.

Answer: First you have to know about the concept of function.

Function:It is a rule or a machine from a set X to a set

Y in which each element of set X maps into the unique

element of set Y. Onto Function: Means a function in

which every element of set Y is the image of at least

one element in set X. Or there should be no element

left in set Y which is the image of no element in set X.

If such case does not exist then the function is not

called onto. For example:Let we define a function f :

Come & Join Us at www.vustudents.ning.com

R----R such that f(x)=x^2 (where ^ shows the symbol

of power i.e. x raise to power 2). Clearly every element

in the second set is the image of atleast one element in

the first set. As for x=1 then f(x)=1^2=1 (1 is the

image of 1 under the rule f) for x=2 then f(x)=2^2=4

(4 is the image of 2 under the rule f) for x=0 then

f(x)=0^2=0 (0 is the image of 0 under the rule f) for

x=-1 then f(x)=(-1)^2=1 (1 is the image of -1 under the

rule f) So it is onto function.

Question: Is Pie an irrational number?

Answer: Pi π is an irrational number as its exact value has an

infinite decimal expansion: Its decimal expansion never

ends and does not repeat.

The numerical value of π truncated to 50 decimal

places is:

3.14159 26535 89793 23846 26433 83279

50288 41971 69399 37510

Question: Difference between sentence and statement.

Answer: A sentence is a statement if it have a truth value

otherwise this sentence is not a statement.By truth

value i mean if i write a sentence "Lahore is capital of

Punjab" Its truth value is "true".Because yes Lahore is

a capital of Punjab. So the above sentence is a

statement. Now if i write a sentence "How are you"

Then you cannot answer in yes or no.So this sentence

is not a statement. Every statement is a sentence but

converse is not true.

Question: What is the truth table?

Answer: Truth table is a table which describe the truth values

Come & Join Us at www.vustudents.ning.com

of a proposition. or we can say that Truth table display

the complete behaviour of a proposition. There fore

the purpose of truth table is to identify its truth

values. A statement or a proposition in Discrete math

can easily identify its truth value by the truth table.

Truth tables are especially valuable in the

determination of the truth values of propositions

constructed from simpler propositions. The main steps

while making a truth table are "first judge about the

statement that how much symbols(or variables) it

contain. If it has n symbols then total number of

combinations=2 raise to power n. These all the

combinations give the truth value of the statement

from where we can judge that either the truthness of

a statement or proposiotion is true or false. In all the

combinations you have to put values either "F" or "T"

against the variales.But note it that no row can be

repeated. For example "Ali is happy and healthy" we

denote "ali is happy" by p and "ali is healthy" by q so

the above statement contain two variables or symbols.

The total no of combinations are =2 raise to power

2(as n=2) =4 which tell us the truthness of a

statement.

Question: how empty set become a subset of every set.

Answer: If A & B are two sets, A is called a subset of B, if, and

only if, every element of A is also an element of B. Now

we prove that empty set is subset of any other set by

a contra positive statement( of above statement) i.e.

If there is any element in the the set A that is not in

the set B then A is not a subset of B. Now if A={} and

B={1,3,4,5} Then you cannot find an element which is in

A but not in B. So A is subset of B.

Question: What is rational and irrational numbers.

Come & Join Us at www.vustudents.ning.com

Answer: A number that can be expressed as a fraction p/q

where p and q are integers and q\not=0, is called a

rational number with numerator p and denominator q.

The numbers which cannot be expressed as rational

are called irrational number. Irrational numbers have

decimal expansions that neither terminate nor become

periodic where in rational numbers the decimal

expansion either terminate or become periodic after

some numbers.

Question: what is the difference between graphs and spanning

tree?

Answer: First of all, a graph is a "diagram that exhibits a

relationship, often functional, between two sets of

numbers as a set of points having coordinates

determined by the relationship. Also called plot". Or A

pictorial device, such as a pie chart or bar graph, used

to illustrate quantitative relationships. Also called

chart. And a tree is a connected graph that does not

contain any nontrivial circuit. (i.e., it is circuit-free)

Basically, a graph is a nonempty set of points called

vertices and a set of line segments joining pairs of

vertices called edges. Formally, a graph G consists of

two finite sets: (i) A set V=V(G) of vertices (or points

or nodes) (ii) A set E=E(G) of edges; where each edge

corresponds to a pair of vertices. Whereas, a spanning

tree for a graph G is a subgraph of G that contains

every vertex of G and is a tree. It is not neccesary for

a graph to always be a spanning tree. Graph becomes a

spanning tree if it satisfies all the properties of a

spanning tree.

Question: What is the probability ?

Answer: The definition of probability is : Let S be a finite

Come & Join Us at www.vustudents.ning.com

sample space such that all the outcomes are equally

likely to occur. The probability of an event E, which is

a subset of S, is P(E) = (the number of outcomes in E)/

(the number of total outcomes in S) P(E) = n (E) / n

( S ) This definition is due to ‘Laplace.’ Thus probability

is a concept which measures numerically the degree of

certainty or uncertainty of the occurrence of an event.

Explaination The basic steps of probability that u have

to remember are as under 1. First list out all possible

out comes. That is called the sample space S For

example when we roll a die the all possible outcomes

are the set S i.e. S = {1,2,3,4,5,6} 2. Secondly we have

to find out all that possible outcomes, in which the

probability is required . For example we are asked to

find the probability of even numbers. First we decide

any name of that event i.e E Now we check all the even

numbers in S which are E = {2,4,6} Remember Event is

always a sub-set of Sample space S. 3. Now we apply

the definition of probability P(E) = (the number of

outcomes in E)/ (the number of total outcomes in S)

P(E) = n (E) / n ( S ) So from above two steps we have n

(E) = 3 and n (S) = 6 then P(E) = 3 / 6 = 1/2 which is

probability of an even number.

Question: what is permutation?

Answer: Permutation comes from the word permute which

means " to change the order of." Basically permutation

means a "complete change." Or the act of altering a

given set of objects in a group. In Mathematics point

of view it means that a ordered arrangement of the

elements of a set (here the order of elements matters

but repetition of the elements is not allowed).

Question: What is a function.

Come & Join Us at www.vustudents.ning.com

Answer: A function say 'f' is a rule or machine from a set A to

the set B if for every element say a of A, there exist a

unique element say b of set such that b=f(a) Where b

is the image of a under f,and a is the pre-image. Note

it that set A is called the domain of f and Y is called

the codomain of f. As we know that function is a rule

or machine in which we put an input,and we get an

output.Like that a juicer machine.We take some

apples(here apples are input) and we apply a rule or a

function of juicer machine on it,then we get the output

in the form of juice.

Question: What is p implies q.

Answer: p--- >q means to "go from hypothesis to a conclusion"

where p is a hypothesis and q is a conclusion. And note

it that this statement is conditioned because the

"truth ness of statement p is conditioned on the truth

ness of statement q". Now the truth value of p--->q is

false only when p is true and q is false otherwise it will

always true. E.g. consider an implication "if you do your

work on Sunday ,I will give you ten rupees." Here p=you

do your work on Sunday (is the hypothesis) , q=I will

give you ten rupees ( the conclusion or promise). Now

the truth value of p---->q will false only when the

promise is braked. i.e. You do your work on Sunday but

you do not get ten rupees. In all other conditions the

promise is not braked.

Question: What is valid and invalid arguments.

Answer: As "an argument is a list of statements called premises

(or assumptions or hypotheses) which is followed by a

statement called the conclusion. " A valid argument is

one in which the premises entail(or imply) the

conclusion. 1)It cannot have true premises and a false

Come & Join Us at www.vustudents.ning.com

conclusion. 2)If its premises are true, its conclusion

must be true. 3)If its conclusion is false, it must have

at least one false premise. 4)All of the information in

the conclusion is also in the premises. And an invalid

agrument is one in which the premises do not entail(or

imply) the conclusion. It can have true premises and a

false conclusion. Even if its premises are true, it may

have a false conclusion. Even if its conclusion is false,

it may have true premises. There is information in the

conclusion that is not in the premises. To know them

better,try to solve more and more examples and

exercises.

Question: What is domain and co -domain.

Answer: Domain means "the set of all x-coordinates in a

relation". It is very simple,Let we take a function say f

from the set X to set Y. Then domain means a set

which contain all the elements of the set X. And co

domain means a set which contain all the elements of

the set Y. For example: Let we define a function "f"

from the set X={a,b,c,d} to Y={1,2,3,4}. such that

f(a)=1, f(b)=2, f(c)=3, f(d)=1 Here the domain set is

{a,b,c,d} And the co-domain set is {1,2,3,4} Where as

the image set is {1,2,3}.Because f(a)=1 as 1 is the image

of a under the rule 'f'. f(b)=2 as 2 is the image of b

under the rule 'f'. f(c)=3 as 3 is the image of c under

the rule 'f'. f(d)=1as 1 is the image of d under the rule

'f'. because "image set contains only those elements

which are the images of elements found in set X".

Note it that here f is one -one but not onto,because

there is one element '4' left which is the image of

nothing element under the rule 'f'.

Question: What is the difference between k-sample,k-selection,

Come & Join Us at www.vustudents.ning.com

k-permutation and k-combination?

Answer: Actually, these all terms are related to the basic

concept of choosing some elements from the given

collection.

For it, two things are important:

1) Order of elements .i.e. which one is first,

which one is second and so on.

2) Repetition of elements

So we can get 4 kinds of selections:

1) The elements have both order and

repetition. ( It is called k-sample )

2) The elements have only order, but no

repetition. ( It is called k-permutation )

3) The elements have only repetition, but no

order. ( It is called k-selection )

4) The elements have no repetition and no

order. ( It is called k-combination )

Question: What is a combination?

Answer: A combination is an un-ordered collection of unique

elements. Given S, the set of all possible unique

elements, a combination is a subset of the elements of

S. The order of the elements in a combination is not

important (two lists with the same elements in

different orders are considered to be the same

combination). Also, the elements cannot be repeated in

a combination (every element appears uniquely once

Question: why is 0! equal to 1?

Answer: Since n! = n(n-1)!

Come & Join Us at www.vustudents.ning.com

Put n =1 in it.

1! = 1x(1 – 1)!

1! =1x0!

1! = 0!

Since 1! = 1

So 1 = 0!

0! = 1.

Question: What is the basic idea if Mathematical Induction?

Answer: Mathematical Induction

Question: Define symmetric and anti-symmetric.

Answer: Click here.

Question: What is the main deffernce between Calculus and

Discrete Maths?

Answer: Discrete mathematics is the study of mathematics

which concerns to the study of discrete objects.

Discrete math build students approach to think

abstractly and how to handle mathematical models

problems in computer While Calculus is a mathematical

tool used to analyze changes in physical quantities. Or

"Calculus is sometimes described as the mathematics

of change." Also calculus played an important role in

industrial area as well discrete math in computer.

Discrete mathematics concerns processes that consist

Come & Join Us at www.vustudents.ning.com

of a sequence of individual steps. This distinguishes it

from calculus, which studies continuously changing

processes. the ideas of discrete mathematics

underline the science and technology specific to the

computer age. An important goal of discrete

mathematics is to develop students’ ability to think

abstractly.

Question: Explain Valid Arguments.

Answer: When some statement is said on the basis of a

set of other statements, meaning that this statement

is derived from that set of statements, this is called

an argument. The formal definition is “an argument is a

list of statements called “premises” (or assumptions or

hypotheses) which is followed by a statement called

the “conclusion.”

A valid argument is one in which the premises

imply the conclusion.

1) It cannot have true premises and a false

conclusion.

2) If its premises are true, its conclusion must

be true.

3) If its conclusion is false, it must have at least

one false premise.

4) All of the information in the conclusion is also

in the premises.

Question: What is the Difference between combinations and

permutations?

Answer: When we talk of permutations and combinations in

Come & Join Us at www.vustudents.ning.com

everyday talk we often use the two terms

interchangeably. In mathematics, however, the two

each have very specific meanings, and this distinction

often causes problems

In brief, the permutation of a number of objects is

the number of different ways they can be ordered; i.e.

which one is first, which one is second or third etc. For

example, you see, if we have two digits 1 and 2, then 12

and 21 are different in meaning. So their order has its

own importance in permutation.

On the other hand, in combination, the order is not

necessary. you can put any object at first place or

second etc. For example, Suppose you have to put some

pictures on the wall, and suppose you only have two

pictures: A and B.

You could hang them

or

We could summarise permutations and combinations

(very simplistically) as

Permutations - position important (although choice may

also be important)

Combinations - chosen important,

which may help you to remember

Question: What is the use of kruskal's algorithn in our daily life?

Come & Join Us at www.vustudents.ning.com

Answer: The Kruskal’s algorithm is usually used to find minimum

spanning tree i.e. the possible smallest tree that

contains all the vertices. The standard application is to

a problem like phone network design. Suppose, you have

a business with several offices; you want to lease

phone lines to connect them up with each other; and

the phone company charges different amounts of

money to connect different pairs of cities. You want a

set of lines that connects all your offices with a

minimum total cost. It should be a spanning tree, since

if a network isn't a tree you can always remove some

edges and save money. A less obvious application is

that the minimum spanning tree can be used to

approximately solve the traveling salesman problem. A

convenient formal way of defining this problem is to

find the shortest path that visits each point at least

once.

Question: What is irrational number?

Answer: Irrational number An irrational number can not be

expressed as a fraction. In decimal form, irrational

numbers do not repeat in a pattern or terminate. They

"go on forever" (infinity). Examples of irrational

numbers are: pi= 3.141592654...

Question: Define membership table and truth table.

Answer: Membership table: A table displaying the membership

of elements in sets. Set identities can also be proved

using membership tables. An element is in a set, a 1 is

used and an element is not in a set, a 0 is used. Truth

table: A table displaying the truth values of

propositions.

Question: Define function and example for finding domain and

range of a function.

Come & Join Us at www.vustudents.ning.com

Answer: Click here.

Question: Why do we use konigsberg bridges problem?

Answer: Click on it.

Question: Explain the intersection of two sets?

Answer: Click on it.

Question: What is absurdity With example?

Answer: Click here.

Question: What is sequence and series?

Answer: Sequence A sequence of numbers is a function defined

on the set of positive integer. The numbers in the

sequence are called terms. Another way, the sequence

is a set of quantities u1, u2, u3... stated in a definite

order and each term formed according to a fixed

pattern. U r =f(r) In example: 1,3,5,7,... 2,4,6,8,... 1 2 ,−

2 2 ,3 2 ,− 4 2 ,... Infinite sequence:- This kind of

sequence is unending sequence like all natural numbers:

1, 2, 3, ... Finite sequence:- This kind of sequence

contains only a finite number of terms. One of good

examples are the page numbers. Series:- The sum of a

finite or infinite sequence of expressions. 1+3+5+7+...

Question: Differntiate contigency and contradiction.

Answer: Click here.

Question: What is conditional statement, converse, inverse and

contra-positive?

Answer: Click here.

Question: What is Euclidean algorithm?

Answer: In number theory, the Euclidean algorithm (also called

Euclid's algorithm) is an algorithm to determine the

Come & Join Us at www.vustudents.ning.com

greatest common divisor (GCD) of two integers.

Its major significance is that it does not require

factoring the two integers, and it is also significant in

that it is one of the oldest algorithms known, dating

back to the ancient Greeks.

Question: what is the circle definition?

Answer: A circle is the locus of all points in a plane which are

equidistant from a fixed point. The fixed point is

called centre of that circle and the distance is called

radius of that circle

Question: What is bi-conditional statement?

Answer: Click here.

Question: Explain the difference between k-sample, k-selection,

k-combination and k-permutation.

Answer: Click here.

Question: What is meant by Discrete?

Answer:

A type of data is discrete if there are only a finite

number of values possible. Discrete data usually occurs

in a case where there are only a certain number of

values, or when we are counting something (using whole

numbers). For example, 5 students, 10 trees etc.

Question: Explain D'Morgan Law.

Answer: Click here.

Question: What are digital circuits?

Answer: Digital circuits are electric circuits based on a number

of discrete voltage levels.

In most cases there are two voltage levels: one near to

zero volts and one at a higher level depending on the

Come & Join Us at www.vustudents.ning.com

supply voltage in use. These two levels are often

represented as L and H.

Question: What is absurdity or contradiction?

Answer: A statement which is always false is called an

absurdity.

Question: What is contingency?

Answer: A statement which can be true or false depending upon

the truth values of the variables is called a

contingency.

Question: Is there any particular rule to solve Inductive Step in

the mathematical Induction?

Answer: In the Inductive Step, we suppose that the result is

also true for other integral values k. If the result is

true for n = k, then it must be true for other integer

value k +1 otherwise the statement cannot be true.

In proving the result for n = k +1, the procedure

changes, as it depends on the shape of the given

statement.

Following steps are main:

1) You should simply replace n by k+1 in the left

side of the statement.

2) Use the supposition of n = k in it.

3) Then you have to simplify it to get right side

of the statement. This is the step,

Come & Join Us at www.vustudents.ning.com

where students usually feel difficulty.

Here sometimes, you have to open the brackets,

or add or subtract some terms

or take some term common etc. This step of

simplification to get right side of the given

statement for n = n + 1 changes from question to

question.

Now check this step in the examples of the

Lessons 23 and 24.

Question: What is Inclusion Exclusion Principle?

Answer: Click on Inclusion Exclusion Principle.

Question: What is recusion?

Answer: Click here.

Question: Different notations of conditional implication.

Answer: If p than q. P implies q. If p , q. P only if q. P is

sufficient for q.

Question: What is cartesion product?

Answer: Cartesian product of sets:- Let A and B be sets. The

Cartesian product of A and B, denoted A x B (read “A

cross B”) is the set of all ordered pairs (a, b), where a

is in A and b is in B. For example: A = {1, 2, 3, 4, 5, 6} B

= {a} A x B = {(1,a), (2,a), (3,a), (4,a), (5,a)}

Question: Define fraction and decimal expansion.

Answer: Fraction:- A number expressed in the form a/b where

a is called the numerator and b is called the

denominator. Decimal expansion:- The decimal

expansion of a number is its representation in base 10

The number 3.22 3 is its integer part and 22 is its

decimal part The number on the left of decimal point is

Come & Join Us at www.vustudents.ning.com

integer part of the number and the number on the

right of the decimal point is decimal part of the

number.

Question: Explane venn diagram.

Answer: Venn diagram is a pictorial representation of sets.

Venn diagram can sometime be used to determine

whether or not an argument is valid. Real life problems

can easily be illustrate through Venn diagram if you

first convert them into set form and then in Venn

diagram form. Venn diagram enables students to

organize similarities and differences visually or

graphically. A Venn diagram is an illustration of the

relationships between and among sets, groups of

objects that share something in common

Question: Write the types of functions.

Answer: Types of function:- Following are the types of function

1. One to one function 2. Onto function 3. Into

function 4. Bijective function (one to one and onto

function) One to one function:- A function f : A to B is

said to be one to one if there is no repetition in the

second element of any two ordered pairs. Onto

function:- A function f : A to B is said to be onto if

Range of f is equal to set B (co-domain). Into

function:- A function f : A to B is said to be into

function of Range of f is the subset of set B (co

domain) Bijective function: Bijective function:- A

function is said to be Bijective if it is both one to one

and onto.

Question: Explain the pigeonhole principle.

Answer: Click here.

Question: What is conditional probability with example?.

Answer: Click here.

Come & Join Us at www.vustudents.ning.com

Question: Explain combinatorics.

Answer: Branch of mathematics concerned with the selection,

arrangement, and combination of objects chosen from

a finite set.

The number of possible bridge hands is a simple

example; more complex problems include scheduling

classes in classrooms at a large university and

designing a routing system for telephone signals. No

standard algebraic procedures apply to all

combinatorial problems; a separate logical analysis may

be required for each problem.

Question: How the tree diagram use in our real computer life?

Answer: Tree diagrams are used in data structure, compiler

construction, in making algorithms, operating system

etc.

Question: Write detail of cards.

Answer: Diamond Club Heart Spade A A A A 1 1 1 1 2 2 2 2 3 3

3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 10

10 10 10 J J J J Q Q Q Q K K K K Where 26 cards are

black & 26 are red. Also ‘A’ stands for ‘ace’ ‘J’ stands

for ‘jack’ ‘Q’ stands for ‘queen’ ‘K’ stands for ‘king’

Question: what is the purpose of permutations?

Answer: Definition:- Possible arrangements of a set of objects

in which the order of the arrangement makes a

difference. For example, determining all the different

ways five books can be arranged in order on a shelf. In

mathematics, especially in abstract algebra and

related areas, a permutation is a bijection, from a

finite set X onto itself. Purpose of permutation is to

Come & Join Us at www.vustudents.ning.com

establish significance without assumptions

FINALTERM EXAMINATION

MTH202- Discrete Mathematics

Time: 120 min

Marks: 80

1) If A and B are two disjoint (mutually exclusive) events

then

P(AUB) =

► P(A) + P(B) + P(ACB)

► P(A) + P(B) + P(AUB)

► P(A) + P(B) - P(ACB)

► P(A) + P(B) - P(ACB)

► P(A) + P(B)

Come & Join Us at www.vustudents.ning.com

2) If p=It is red,

q=It is hot

Then, It is not red but hot is denoted by ~ pU ~ q

► True

False

3) If ( AUB ) = A, then ( AnB ) = B

► True

False

► Cannot be determined

How many integers from 1 through 1000 are neither multiple

of 3 nor multiple of 5?

► 333

► 467

533

► 497

The value of xfor -2.01 is

► -3

► 1

-2

What is the expectation of the number of heads when three

fair coins are tossed?

► 1

► 1.34

► 2

1.5

Every relation is

Come & Join Us at www.vustudents.ning.com

function

► may or may not function

► bijective mapping

► Cartesian product set

The statement p . q o (p Rq)U(q Rp) describes

► Commutative Law

► Implication Laws

► Exportation Law

Equivalence

The square root of every prime number is irrational

True

► False

► Depends on the prime number given

A predicate is a sentence that contains a finite number of

variables and becomes a statement when specific values are

substituted for the variables

► True

► False

► None of these

If r is a positive integer then gcd(r,0)=

► r

► 0

► 1

► None of these

Associative law of union for three sets is

► A E (B E C) = (A E B) E C

► A C (B C C) = (A C B) C C

► A E (B C C) = (A E B) C (A E B)

Come & Join Us at www.vustudents.ning.com

► None of these

Values of X and Y, if the following order pairs are equal.

(4X-1, 4Y+5)= (3,5) will be

► (x,y) = (3,5)

► (x,y) = (1.5,2.5)

► (x,y) = (1,0)

► None of these

The expectation of x is equal to

► Sum of all terms

► Sum of all terms divided by number of terms

axf (x)

A line segment joining pair of vertices is called

► Loop

► Edge

► Node

The indirect proof of a statement pq involves

► Considering ~q and then try to reach ~p

► Considering p and ~q and try to reach contradiction

► Considering p and then try to reach q

Both 2 and 3 above

The greatest common divisor of 5 and 10 is

► 5

► 0

► 1

► None of these

Come & Join Us at www.vustudents.ning.com

Suppose that there are eight runners in a race first will get

gold medal the second will get siver and third will get bronze.

How many different ways are there to award these medals if

all possible outcomes of race can occur and there is no tie.

P(8,3)

► P(100,97)

► P(97,3)

► None of these

The value of 0! Is

► 0

1

► Cannot be determined

A sub graph of a graph G that contains every vertex of G and

is a tree is called

► Trivial tree

► empty tree

Spanning tree

In the planar graph, the graph crossing number is

0

► 1

► 2

► 3

A matrix in which number of rows and columns are equal is called

► Rectangular Matrix

Square Matrix pg296

► Scalar Matrix

Changing rows of matrix into columns is called

► Symmetric Matrix

Come & Join Us at www.vustudents.ning.com

Transpose of Matrix

► Adjoint of Matrix

If A and B are finite (overlapping) sets, then which of the

following must be true

n(AUB) = n(A) + n(B)

► n(AEB) = n(A) + n(B) - n(ACB)

► n(AEB)= o

► None of these

When 3k is even, then 3k+3k+3k is an odd.

► True

False

When 5k is even, then 5k+5k+5k is odd.

► True

False

The product of the positive integers from 1 to n is called

► Multiplication

n factorial

► Geometric sequence

The expectation m for the following table is

xi 1 3

f(xi) 0.4 0.1

► 0.5

► 3.4

► 0.3

► 0.7

If p= A Pentium 4 computer,

q= attached with ups.

The given graph is

Come & Join Us at www.vustudents.ning.com

► Simple graph

► Complete graph

► Bipartite graph

► Both (i) and (ii)

► Both (i) and (iii)

P(n) is called proposition or statement.

True

► False

An integer n is odd if and only if n = 2k + 1 for some integer k.

True

► False

► Depends on the value of k

RSS

Donation

A quality education changes lives & start with you.

Latest Activity

Forum Categorizes

Job's & Careers (Latest Jobs)

Admissions (Latest Admissons)

Scholarship (Latest Scholarships)

Internship (Latest Internships)

VU Subject Study Groups

Other Universities/Colleges/Schools Help

    ::::::::::: More Categorizes :::::::::::

Member of The Month

© 2018   Created by + M.TariK MaliC.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service