Looking For Something at vustudents.ning.com? Search Here
.... 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>>
[ + VU Study Groups Subject Code Wise ] [ + COMSATS Virtual Campus Study Groups Subject Code Wise ]
It is very necessary for all of us
Tags:
Share This With Friends......
Find Your Subject Study Group & Join.
+ Click Here To Join also Our facebook study Group.+ 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
Note: (This is Featured Discussion)
For Important Helping Material related to this subject (Solved MCQs, Short Notes, Solved past Papers, EBooks, 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 postconditions.
► 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(n1)
► n2 + n
► Cannot be determined
Question No: 30 ( Marks: 1 )  Please choose one
The number of kcombinations 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+k1,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+k1,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ÈB)ÈC 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 nonisomorphic tree with five vertices.
There are three nonisomorphic trees with five vertices as shown
(where every tree with five vertices has 51=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+501,7)
C(56,7)
56!/(567)!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.
► NOTgate (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(AB) =
► P(A) + P(B) + P(AB)
Come & Join Us at www.vustudents.ning.com
► P(A) + P(B) + P(AUB)
► P(A) + P(B)  P(AB)
► P(A) + P(B)  P(AB)
► 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
► AB
► 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(AB)  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(n1)
► ( 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(AB) = n(A) + n(B)  n(AB)
► n(AB)= 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 = ev
► f = e+v +2
► f = ev2
► f = ev+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 5permutations 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, y)ÎR 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,t)ÏR 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(n1)
► 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 _______________.
► 0≤r<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 77 =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!/(42)!
= (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 × (n1) = 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, y)ÎR 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.
► NOTgate (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
twodigit 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
► AB
► 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
► AB
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 kcombinations 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+k1,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 _______________.
► 0≤r<d
► 0<r<d
► 0≤d<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 stepbystep 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(BA)
P(BA)= 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?
Verticesedges+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 0≤r<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 4permutations 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 Onotation. 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 inclusionexclusion principle
Answer: InclusionExclusion 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 twopart 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 twopart 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
RR 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 circuitfree)
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 subset 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 preimage. 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 xcoordinates 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 codomain 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 ksample,kselection,
Come & Join Us at www.vustudents.ning.com
kpermutation and kcombination?
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 ksample )
2) The elements have only order, but no
repetition. ( It is called kpermutation )
3) The elements have only repetition, but no
order. ( It is called kselection )
4) The elements have no repetition and no
order. ( It is called kcombination )
Question: What is a combination?
Answer: A combination is an unordered 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(n1)!
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 antisymmetric.
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
contrapositive?
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 biconditional statement?
Answer: Click here.
Question: Explain the difference between ksample, kselection,
kcombination and kpermutation.
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 (codomain). 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 xfor 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.
(4X1, 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
+ Job's & Careers (Latest Jobs)
+ Admissions (Latest Admissons)
+ Scholarship (Latest Scholarships)
+ Internship (Latest Internships)
+ Other Universities/Colleges/Schools Help
::::::::::: More Categorizes :::::::::::
© 2019 Created by + M.Tariq Malik. Powered by
Promote Us  Report an Issue  Privacy Policy  Terms of Service
Looking For Something at vustudents.ning.com? Search Here
We are usergenerated contents site. All product, videos, pictures & others contents on vustudents.ning.com don't seem to be beneath our Copyrights & belong to their respected owners & freely available on public domains. We believe in Our Policy & do according to them. If Any content is offensive in your Copyrights then please email at m.tariqmalik@gmail.com or Contact us at contact Page with copyright detail & We will happy to remove it immediately.
Management: Admins ::: Moderators
Become a Team Member  Safety Guidelines for New  Site FAQ & Rules  Safety Matters  Online Safety  Rules For Blog Post