Code: AC10
Subject: DISCRETE STRUCTURES
PART - I, VOL – I
TYPICAL QUESTIONS & ANSWERS
OBJECTIVE TYPE QUESTIONS
Each Question carries 2 marks.
Choose correct or the best alternative
in the following:
Q.1 Which of the following statement is the negation of the
statement,
“2 is
even and –3 is negative”?
(A) 2 is even and –3 is not negative.
(B) 2 is odd and –3 is not negative.
(C) 2 is even or –3 is not negative.
(D) 2 is odd or –3 is not negative.
Ans:D
Q.2 If
(where
A and B are general matrices) then
. (B)
A = B’.
(C) B = A. (D)
A’ = B.
Ans:C
Q.3 A
partial ordered relation is transitive, reflexive and
(A) antisymmetric. (B) bisymmetric.
(C) antireflexive. (D) asymmetric.
Ans:A
Q.4 Let N = {1, 2, 3, ….} be
ordered by divisibility, which of the following subset is totally ordered,
(A) 
. (B)
.
(C) 
. (D)
.
Ans:A
Q.5 If B is a Boolean Algebra,
then which of the following is true
(A)
B is a finite but not complemented lattice.
(B)
B is a finite, complemented and distributive
lattice.
(C)
B is a finite, distributive but not
complemented lattice.
(D) B is not distributive lattice.
Code: AC10
Subject: DISCRETE STRUCTURES
Ans:B
Q.6 In a finite
state machine, m = (Q,
)
transition function 
is a function which maps
(A)
. (B)
.
(C) 
. (D)
.
Ans:B
Q.7 If 
and 
, then 
is
(A)
. (B)
cos 3 x.
(C) 
. (D)
.
Ans:D
Q.8 
is logically
equivalent to
(A) 
(B)
(C) 
(D)
Ans:D
Q.9 Which of the following is not a well formed formula?
(A) 
(B) 
(C) 
(D) 
Ans:B
Q.10 The
number of distinguishable permutations of the letters in the word BANANA are,
(A) 60. (B) 36.
(C) 20. (D) 10.
Ans:A
Q.11 Let
the class of languages accepted by finite state machines be L1 and the class of
languages represented by regular expressions be L2 then,
(A) 
. (B)
.
(C) 
. (D)
L1 = L2.
Ans:D
Q.12 
is,
Code: AC10
Subject: DISCRETE STRUCTURES
(A) Satisfiable. (B)
Unsatisfiable.
(C) Tautology. (D) Invalid.
Ans:C
Q.13 The minimized expression
of 
is
(A) 
. (B) 
.
(C) 
. (D)
C.
Ans:C
Q.14 Consider
the finite state machine M = 
where F = 
is defined by the
following transition table. Let for any 
, let fw = 
. List the values of
the transition function, 
.
(A) 
.
(B)
(C) 
(D) 
Ans:B
Q.15 Which of the following
pair is not congruent modulo 7?
(A) 10, 24 (B)
25, 56
(C) -31, 11 (D) -64, -15
Ans:B
Q.16 For
a relation R on set A, let 
if 
and 0 otherwise, be the matrix of
relation R. If 
=
then R is,
(A) Symmetric (B)
Transitive
(C) Antisymmetric (D)
Reflexive
Ans:B
Code: AC10
Subject: DISCRETE STRUCTURES
Q.17 In an
examination there are 15 questions of type True or False. How many sequences
of answers are possible.
Ans:
Each question can be answered in 2 ways
(True or False). There are 15 questions, so they all can be answered in 215
different possible ways.
Q.18 Find
the generating function for the number of r-combinations of {3.a, 5.b, 2.c}
Ans:
Terms sequence is
given as r-combinations of {3.a, 5.b, 2.c}. This can be written as rC3.a,
rC5.b, rC2.c. Now generating
function for this finite sequence is given by
f(x)
= rC3.a + rC5.bx + rC2.cx2
Q.19 Define
a complete lattice and give one example.
Ans:
A
lattice (L, £) is said to be a complete lattice if, and only if every non-empty
subset S of L has a greatest lower bound and a least upper bound. Let A be set
of all real numbers in [1, 5] and £ is relation of ‘less than equal to’. Then,
lattice (A, £) is a complete lattice.
Q.20 For the given diagram
Fig. 1 compute
(i) 
(ii) 
Ans: (i) 
= u + v (ii) 
= y + z
Q.21 The
converse of a statement is: If a steel rod is stretched, then it has been
heated. Write the inverse of the statement.
Ans: The statement corresponding to the
given converse is “If a steel rod has not been heated then it is not stretched”.
Now the inverse of this statement is “If a steel rod is not stretched then it
has not been heated”.
Q.22 Is 
a tautology
or a fallacy?
Ans: Draw a truth table of the statement and it is found that it is a
fallacy.
Q.23 In how many ways 5
children out of a class of 20 line up for a picture.
Ans: It can be performed in 20P5 ways.
Code: AC10
Subject: DISCRETE STRUCTURES
Q.24 If P
and Q stands for the statement
P : It is hot
Q : It is humid,
then what does the following
mean?
Ans: The statement means “It is hot and it is not
humid”.
Q.25 In a survey
of 85 people it is found that 31 like to drink milk, 43 like coffee and 39
like tea. Also 13 like both milk and tea, 15 like milk and coffee, 20 like tea
and coffee and 12 like none
of the three drinks. Find the number
of people who like all the three drinks. Display the answer using a Venn
diagram.
Ans: Let
A, B and C is set of people who like to drink milk, take coffee and take tea
respectively. Thus |A| = 31, |B| = 43, |C| = 39, |AÇB| = 15, |AÇC| = 13, |BÇC| = 20, |AÈBÈC|
= 85 – 12 = 73. Therefore, |AÇBÇC| = 73 + (15 + 13 + 20) –
(31 + 43 + 39) = 8. The Venn diagram is shown below.
Q.26 Consider
the set A = {2, 7, 14, 28, 56, 84} and the relation a 
b if and only if a
divides b. Give the Hasse diagram for the poset (A, ).
Ans: The
relation is given by the set {(2,2), (2, 14), (2, 28), (2, 56), (2, 84), (7,
7), (7, 14), (7, 28), (7, 56), (7, 84), (14, 14), (14, 28), (14, 56), (14, 84),
(28, 28), (28, 56), (28, 84), (56, 56), (84, 84)}. The Hasse Diagram is shown
below:
Code: AC10
Subject: DISCRETE STRUCTURES
Q.27 How
many words can be formed out of the letters of the word ‘PECULIAR’ beginning
with P and ending with R?
(A) 100 (B) 120
(C) 720 (D)
150
Ans:C
Q.28 Represent the
following statement in predicate calculus: Everybody respects all the selfless
leaders.
Ans: For every X, if every Y that is a
person respects X, then X is a selfless leader. So in predicate calculus we may
write:
ҰX. ҰY(Person(Y)
→ respect(Y,X)) → selfless-leader(X)
Where person(Y): Y is a person
respect(Y,X): Y respects X
selfless-leader(X): X is a selfless leader.
Q.29 In which order does a
post order traversal visit the vertices of the following rooted tree?
Ans: The post order traversal is in order (Right, Left, Root). Thus the
traversal given tree is C E D B A.
Q.30 Consider
a grammar G = ({S, A, B}, {a, b}, P, S). Let L (G)= 
then if P be the set of
production rules and P includes S aB, give the remaining production rules.
Ans: One of the production rules can be: S®aB, B®bA, A®aB, B®b.
Q.31 Choose
4 cards at random from a standard 52 card deck. What is the probability that
four kings will be chosen?
Ans: There are four kings in a standard pack of 52 cards. The 4 kings
can be selected in 4C4 = 1 way. The total number of ways
in which 4 cards can be selected is 52C4. Thus the
probability of the asked situation in question is = 1 / 52C4.
Q.32 How many edges are there in an
undirected graph with two vertices of degree 7, four vertices of degree 5, and
the remaining four vertices of degree is 6?
Code: AC10
Subject: DISCRETE STRUCTURES
Ans: Total degree of the graph = 2 x 7 + 4 x 5 + 4 x 6 = 58. Thus number
of edges in the graph is 58 / 2 = 29.
Q.33 Identify the
flaw in the following argument that supposedly shows that n2 is even
when n is an even integer. Also name the reasoning:
Suppose that n2 is even. Then n2 =
2k for some integer k. Let n = 2l for some integer l. This shows that n is
even.
Ans: The flaw lies in the statement “Let n = 2l for some integer l. This
shows that n is even”. This is a loaded and biased reasoning. This can be
proved by method of contradiction.
Q.34 The description of the shaded region in the following figure using
the
operations on set is,
(A) 
(B) 
(C) 
(D) 
Ans:B
Q.35 A
matrix
has
an inverse if and only if,
(A) x, y, u and v are all
nonzeros. (B) xy - uv 
0
(C) xv - uy 0 (D)
all of the above.
`
Ans:C
Q.36 If
x and y are real numbers then max (x, y) + min (x, y) is equal to
(A) 2x (B)
2y
(C) (x+y)/2 (D) x+y
Ans:D
Q.37 The sum of the entries in
the fourth row of Pascal’s triangle is
(A) 8 (B)
4
(C) 10 (D) 16
Ans:A
Q.38 In the following graph
Code: AC10
Subject: DISCRETE STRUCTURES
the Euler path is
(A) abcdef (B) abcf
(C) fdceab (D) fdeabc
Ans:C
Q.39 Let
A = Z+, be the set of positive integers, and R be the
relation on A defined by a R b if and only if there exist a 
Z+ such that a = bk. Which one of the
following belongs to R?
(A) (8, 128) (B)
(16, 256)
(C) (11, 3) (D)
(169, 13)
Ans:D
Q.40 For the sequence defined
by the following recurrence relation
, the explicit formula for Tn
is
(A) 
(B)
(C) 
(D)
Ans:B
Q.41 Which
one of the following is not a regular expression?
(A) 
(B) 
(C) 
(D)
Ans:B
Q.42 Which of the following
statement is the negation of the statement “2 is even or –3 is negative”?
(A) 2 is even & -3 is negative (B) 2 is odd & -3 is not negative
(C) 2 is odd or –3 is not negative (D)
2 is even or –3 is not negative
Ans:B
Q.43 The statement ( pÙq) Þ
p is a
(A) Contingency. (B) Absurdity
(C) Tautology (D)
None of the above
Ans:C
Q.44 In how many ways can a
president and vice president be chosen from a set of 30 candidates?
(A) 820 (B)
850
(C) 880 (D)
870
Code: AC10
Subject: DISCRETE STRUCTURES
Ans:D
Q.45 The
relation { (1,2), (1,3), (3,1), (1,1), (3,3), (3,2), (1,4), (4,2), (3,4)} is
(A) Reflexive. (B) Transitive.
(C) Symmetric. (D)
Asymmetric.
Ans:B
Q.46 Let
L be a lattice. Then for every a and b in L which one of the following is
correct?
(A) 
(B) 
(C) 
(D) 
Ans:B
Q.47 The
expression 
is equivalent to
(A) 
(B)
a+c
(C) c (D)
1
Ans:B
Q.48 A
partial order relation is reflexive, antisymmetric and
(A) Transitive. (B) Symmetric.
(C) Bisymmetric. (D) Asymmetric.
Ans:A
Q.49 If
n is an integer and n2 is odd ,then n is:
(A) even. (B) odd.
(C) even
or odd. (D) prime.
Ans:B
Q.50 In
how many ways can 5 balls be chosen so that 2 are red and 3 are black
(A) 910. (B)
990.
(C) 980. (D)
970.
Ans:B
Q.51 A
tree with n vertices has _____ edges
(A) n (B) n+1
(C) n-2 (D) n-1
Ans:D
Q.52 In
propositional logic which one of the following is equivalent to p
q
Code: AC10
Subject: DISCRETE STRUCTURES
(A) 
(B)
(C) 
(D) 
Ans:C
Q.53 Which of the following statement is
true:
(A) Every
graph is not its own sub graph.
(B) The terminal vertex of a graph are of degree two.
(C) A tree with n vertices has n edges.
(D) A single vertex in graph G is a sub graph of G.
Ans:D
Q.54 Pigeonhole principle states
that AB and 
then:
(A) f is not onto (B) f is not
one-one
(C) f is neither one-one nor onto (D)
f may be one-one
Ans:B
Q.55 The
probability that top and bottom cards of a randomly shuffled deck are both aces
is:
(A) 
(B)
(C) 
(D)
Ans:C
Q.56 The
number of distinct relations on a set of 3 elements is:
(A) 8 (B)
9
(C) 18 (D) 512
Ans:D
Q.57 A self
complemented, distributive lattice is called
(A) Boolean Algebra (B) Modular
lattice
(C) Complete lattice (D)
Self dual lattice
Ans:A
Q.58 How
many 5-cards consists only of hearts?
(A) 1127 (B) 1287
(C) 1487 (D) 1687
Ans:B
Q.59 The
number of diagonals that can be drawn by joining the vertices of an octagon is:
Code: AC10
Subject: DISCRETE STRUCTURES
(A) 28 (B)
48
(C) 20 (D) 24
Ans:C
Q.60 A
graph in which all nodes are of equal degrees is known as:
(A) Multigraph (B) Regular graph
(C) Complete
lattice (D) non
regular graph
Ans:B
Q.61 Which
of the following set is null set?
(A) 
(B)
(C) 
(D) 
Ans:B
Q.62 Let
A be a finite set of size n. The number of elements in the power set of A x A
is:
(A) 
(B)
(C) 
(D) 
Ans:B
Q.63 Transitivity and irreflexive imply:
(A) Symmetric (B) Reflexive
(C) Irreflexive (D)
Asymmetric
Ans:D
Q.64 A binary Tree T has n leaf
nodes. The number of nodes of degree 2 in T is:
(A) log n (B) n
(C) n-1 (D)
n+1
Ans:A
Q.65 Push
down machine represents:
(A) Type
0 Grammar (B) Type 1 grammar
(C) Type-2 grammar (D) Type-3 grammar
Ans:C
Q.66 Let
* be a Boolean operation defined by
A * B = AB + 
, then A*A is:
Code: AC10
Subject: DISCRETE STRUCTURES
(A)
A (B) B
(C) 0 (D) 1
Ans:D
Q.67 In
how many ways can a party of 7 persons arrange themselves around a circular
table?
(A) 6! (B) 7!
(C) 5! (D)
7
Ans:A
Q.68 In how many ways
can a hungry student choose 3 toppings for his prize from a list of 10
delicious possibilities?
(A) 100 (B)
120
(C) 110 (D) 150
Ans:B
Q.69 A
debating team consists of 3 boys and 2 girls. Find the number of ways they can
sit in a row?
(A) 120 (B)
24
(C) 720 (D) 12
Ans:A
Q.70 Suppose
v is an isolated vertex in a graph, then the degree of v is:
(A) 0 (B)
1
(C) 2 (D) 3
Ans:A
Q.71 Let p be “He is
tall” and let q “He is handsome”. Then the statement “It is false that he is
short or handsome” is:
(A) 
(B)
(C) 
(D)
Ans:B
Q.72 The
Boolean expression 
is independent of the Boolean
variable:
(A) Y (B)
X
(C) Z (D) None of these
Ans:A
Q.73 Which
of the following regular expression over 
denotes the set of all
strings not containing 100 as sub string
Code: AC10
Subject: DISCRETE STRUCTURES
(A) 
. (B) 
.
(C) 
. (D)
.
Ans:D
Q.74 In
an undirected graph the number of nodes with odd degree must be
(A) Zero (B) Odd
(C) Prime (D) Even
Ans:D
Q.75 Find
the number of relations from A = {cat, dog, rat} to B = {male , female}
(A) 64 (B) 6
(C) 32 (D) 15
Ans:A
Q.76 Let
P(S) denotes the powerset of set S. Which of the following is always true?
(A) 
(B) 
(C) 
(D) 
Ans:D
Q.77 The number of functions from an m
element set to an n element set is:
(A) mn (B)
m + n
(C) nm (D)
m * n
Ans:A
Q.78 Which
of the following statement is true:
(A) Every graph is not its own subgraph
(B) The terminal vertex of a graph are of degree two.
(C) A tree with n vertices has n edges.
(D) A single vertex in graph G is a subgraph of G.
Ans:D
Q.79 Which
of the following proposition is a tautology?
(A) (p v q)®p (B)
p v (q®p)
(C) p v (p®q) (D) p®(p®q)
Ans:C
Q.80 What is the converse of the following assertion?
I stay only if
you go.
Code: AC10
Subject: DISCRETE STRUCTURES
(A) I stay if you go. (B) If you do not go then I do not stay
(C) If I stay then you go. (D) If you do not stay then you go.
Ans:B
Q.81 The
length of Hamiltonian Path in a connected graph of n vertices is
(A) n–1 (B)
n
(C) n+1 (D)
n/2
Ans:A
Q.82 A
graph with one vertex and no edges is:
(A) multigraph (B) digraph
(C) isolated graph (D) trivial graph
Ans:D
Q 83 If R
is a relation “Less Than” from A = {1,2,3,4} to B = {1,3,5} then RoR-1
is
(A) {(3,3), (3,4), (3,5)}
(B) {(3,1), (5,1),
(3,2), (5,2), (5,3), (5,4)}
(C) {(3,3), (3,5), (5,3), (5,5)}
(D) {(1,3), (1,5),
(2,3), (2,5), (3,5), (4,5)}
Ans:C
Q.84 How
many different words can be formed out of the letters of the word VARANASI?
(A) 64 (B)
120
(C) 40320 (D)
720
Ans:D
Q.85 Which
of the following statement is the negation of the statement “4 is even or -5 is
negative”?
(A) 4 is odd and -5 is not negative (B)
4 is even or -5 is not negative
(C) 4 is odd or -5 is not negative (D)
4 is even and -5 is not negative
Ans:A
Q.86 A complete graph of n
vertices should have __________ edges.
(A) n-1 (B)
n
(C) n(n-1)/2 (D)
n(n+1)/2
Ans:C
Q.87 Which one is the
contrapositive of
?
Code: AC10
Subject: DISCRETE STRUCTURES
(A) 
(B)
(C) 
(D)
None of these
Ans:B
Q.88 A relation that is
reflexive, anti-symmetric and transitive is a
(A) function (B)
equivalence relation
(C) partial order (D)
None of these
Ans:C
Q.89 A Euler graph is one in which
(A) Only two vertices are of odd degree
and rests are even
(B) Only two
vertices are of even degree and rests are odd
(C) All the vertices are of odd degree
(D) All the vertices
are of even degree
Ans:D
Q.90 What kind of strings is
rejected by the following automaton?
(A) All strings with two consecutive
zeros
(B) All strings with two consecutive
ones
(C) All strings with alternate 1 and 0
(D) None
Ans:B
Q.91 A spanning tree of a
graph is one that includes
(A) All the vertices of the graph
(B) All the edges of
the graph
(C) Only the vertices of odd degree
(D) Only the
vertices of even degree
Ans:A
Q.92 The Boolean
expression 
is
independent to
(A) A (B)
B
(C) Both A and B (D)
None
Code: AC10
Subject: DISCRETE STRUCTURES
Ans:B
Q.93 Seven
(distinct) car accidents occurred in a week. What is the probability that they
all occurred on the same day?
(A) 
(B)
(C) 
(D)
Ans:A
Code: AC10
Subject: DISCRETE
STRUCTURES
PART – II, VOL – I
DESCRIPTIVES
Q.1 Solve the
recurrence relation
. (5)
Ans: The given equation can be written
in the following form:
tn
- 2tn-1 = 0
Now successively replacing n by (n – 1) and then by (n – 2) and so
on we get a set of equations. The process is continued till terminating
condition. Add these equations in such a way that all intermediate terms get
cancelled. The given equation can be rearranged as
tn – 2tn–1 = 0
tn–1 – 2tn–2 = 0
tn–2 – 2tn–3 = 0
tn–3 – 2tn–4 = 0
.
t2 – 2t1 = 0
t1 – 2t0 = 0 [we stop here,
since t0 = 1 is given ]
Multiplying all the equations respectively by 20, 21,
…, 2n – 1 and then adding them together, we get tn
– 2nt0 = 0
or, tn = 2n
Q.2 Find the
general solution of
(9)
Ans: The general solution, also called homogeneous
solution, to the problem is given by homogeneous part of the given
recurrence equation. The homogeneous part of the given equation is
Code: AC10
Subject: DISCRETE STRUCTURES
The
characteristic equation of (2) is given as
The general solution is given by
Q.3 Find the
coefficient of 
in 
. (7)
Ans: The coefficient of x20 in
the expression (x3 + x4 + x5 + …)5
is equal to the coefficient of x5 in the expression (1 + x + x2+
x3 + x4 + x5 + …)5 because x15
is common to all the terms in (x3 + x4 + x5
+ …)5. Now expression (1 + x + x2+ x3 + x4
+ x5 + …)5 is equal to 
. The required coefficient is
Q.4 If 
find L(G). (7)
Ans: The language of the grammar can be
determined as below:
S ®0 S 1 [Apply rule S ®0 S 1]
®0n
S 1n [Apply
rule S ®0 S 1 n ³ 0 times ]
® 0n
1n [Apply rule S
® e]
The language
contains strings of the form 0n 1n where n ³ 0.
Q.5 By using
pigeonhole principle, show that if any five numbers from 1 to 8 are chosen,
then two of them will add upto 9. (5)
Code: AC10
Subject: DISCRETE STRUCTURES
Ans: Let us form four groups of two numbers from 1 to 8 such that sum the
numbers in a group is 9. The groups are: (1, 8), (2, 7), (3, 6) and (4,5).
Let us consider these four groups as pigeonholes (m). Thus m = 4.
Take the five numbers to be selected arbitrarily as pigeons i.e. n = 5. Take a
pigeon and put in the pigeonhole as per its value. After placing 4 pigeons, the
5th has to go in one of the pigeonhole. i.e by pigeonhole principle
has at least one group that will contain
. Thus two of the numbers, out of
the five selected, will add up to 9.
Q.6 Test
whether 101101, 11111 are accepted by a finite state machine M given as follows
: (9)
Where
Ans: The transition diagram for the given FSM is as below:
The given FSM
accepts any string in {0, 1} that contains even number of 0’s and even number
of 1’s. The string “101101” is accepted as it contains even number of 0’s and
even number of 1’s. However string “11111” is not acceptable as it contains odd
number of 1’s.
Q.7 Let
L be a distributive lattice. Show that if there exists an a with
(7)
Ans: In any distributive lattice L, for
any three elements a, x, y of L, we can write
Code: AC10
Subject: DISCRETE STRUCTURES
x = xÚ (a Ù x)
= (xÚ a) Ù (xÚx) [Distributive law]
= (aÚ x) Ù x [Commutative and Idempotent
law]
= (aÚ y) Ù x [Given that (aÚ x) = (aÚ y)]
= (a Ù y) Ú (y Ù x) [Distributive law]
= (a Ù y) Ú (y Ù x) [Given that (a Ù x) = (a Ù y)]
= (y Ù a) Ú (y Ù x) [Commutative law]
= y Ù (a Ú x) [Distributive law]
= y Ù (a Ú y) [Given that (aÚ x) = (aÚ y)]
= y
Q.8 Check
the validity of the following argument :-
“If the labour market
is perfect then the wages of all persons in a particular employment will be
equal. But it is always the case that wages for such persons are not equal
therefore the labour market is not perfect.” (7)
Ans: Let p: “Labour market is perfect”; q : “Wages of all persons in a
particular employment will be equal”. Then the given statement can be written
as
[(p®q) Ù ~q] ® ~p
Now, [(p®q) Ù ~q] ® ~p = [(~pÚq) Ù ~q] ® ~p
= [(~p Ù ~q) Ú (q Ù ~q)] ® ~p
= [(~p Ù ~q) Ú 0] ® ~p
= [~(p Ú q)] ® ~p
= ~[~(p Ú q)] Ú ~p
= (p Ú q) Ú ~p = (p Ú ~p) Ú q = 1 Ú q =1
A tautology. Hence the given statement is true.
Q.9 Let
find
(i) Prime implicants of E, (ii) Minimal sum
for E. (7)
Ans: K –map for given boolean
expression is given as:
Code: AC10
Subject: DISCRETE STRUCTURES
Prime
implicant is defined as the minimum term that
covers maximum number of min terms. In the K-map prime implicant y’t covers
four min terms. Similarly yz’ and xz are other prime implicants. The minimal
sum for E is [y’t + yz’ + xz].
Q.10 What
are the different types of quantifiers? Explain in brief.
Show that 
(7)
Ans: There are two quantifiers used in
predicate calculus: Universal and existential.
Universal Quantifier: The operator, represented by the symbol ∀, used in predicate
calculus to indicate that a predicate is true for all members of a specified set.
Some verbal
equivalents are "for each" or "for every".
Existential
Quantifier: The operator, represented by the symbol ∃, used in predicate
calculus to indicate that a predicate is true for at least one member of a
specified set.
Some verbal
equivalents are "there exists" or "there is".
Now, ($x) (P(x) Ù Q(x)) Þ For some (x = c)
(P(c) Ù
Q(c))
Þ P(c) Ù Q(c)
Þ $x P(x) Ù $x
Q(x)
Q.11
Which of the partially ordered sets in figures (i), (ii) and (iii) are
lattices? Justify your answer. (7)
Ans: Let (L, £) be a poset. If every
subset {x, y} containing any two elements of L, has a glb
(Infimum) and a lub (Supremum), then the poset (L, £) is called a lattice.
The poset in (i) is a
lattice because for every pair of elements in it, there a glb and
lub in the poset. Similarly poset in (ii) is also a lattice. Poset of (iii) is
also a lattice.
Code: AC10
Subject: DISCRETE STRUCTURES
Q.12 Consider the
following productions :
Then, for the string a a a b b a
b b b a, find the
(i)
the leftmost derivation.
(ii)
the rightmost derivation. (7)
Ans:
(i) In the left most derivation, the
left most nonterminal symbol is first replaced with some terminal symbols as
per the production rules. The nonterminal appearing at the right is taken next
and so on. Using the concept, the left most derivation for the string
aaabbabbba is given below:
S ®aB [Apply rule S ® aB]
®aaBB [Apply
rule B ® aBB]
®aaaBBB [Apply
rule B ® aBB]
®aaabBB [Apply
rule B ® b]
®aaabbB [Apply
rule B ® b]
®aaabbaBB [Apply
rule B ® aBB]
®aaabbabB [Apply
rule B ® b]
®aaabbabbS [Apply
rule B ® bS]
®aaabbabbbA [Apply
rule S ® bA]
®a a a b b a b b b a [Apply
rule A ® a]
(ii) In the right most derivation, the right most nonterminal symbol
is first replaced with some terminal symbols as per the production rules. The
nonterminal appearing at the left is taken next and so on. Using the concept,
the right most derivation for the string aaabbabbba is given below:
S ®aB [Apply rule S ® aB]
®aaBB [Apply
rule B ® aBB]
®aaBbS [Apply
rule B ® bS]
®aaBbbA [Apply
rule S ® bA]
®aaBbba [Apply
rule A ® a]
® aaaBBbba [Apply
rule B ® aBB]
® aaa B bbba [Apply
rule B ® b]
® aaa bS bbba [Apply
rule B ® bS]
® aaab bA bbba [Apply
rule S ® bA]
®a a a b b a b b b a [Apply
rule A ® a]
Code: AC10
Subject: DISCRETE STRUCTURES
Q.13 Determine the
properties of the relations given by the graphs shown in fig.(i) and (ii) and
also write the corresponding relation matrices. (7)
Ans8. (a) (i) The relation matrix for the relation is :
.
The relation is reflexive,
Symmetric and transitive. It is in fact antisymmetric as well.
The relation
matrix for the relation is :
.
The relation is reflexive,
Symmetric but not transitive.
Q.14 If f is a
homomorphism from a commutative semigroup (S, *) onto a semigroup 
, then show
that is
also commutative. (7)
Ans: The function f is said to be a homomorphism
of S into T if
f(a * b) = f(a) *’ f(b)
" a, b Î S
i.e. f preserves
the composition in S and T.
It is given that
(S, *) is commutative, so
a*b = b*a Þ f(a*b) = f(b*a) " a, b Î S
Code: AC10
Subject: DISCRETE STRUCTURES
Þ f(a) *’ f(b) =
f(b)*’ f(a)
Þ (T,*’) is also
commutative.
Q.15 Construct
K-maps and give the minimum DNF for the function whose truth table is shown
below : (9)
|
x
|
y
|
z
|
f(x, y, z)
|
|
0
|
0
|
0
|
1
|
|
0
|
0
|
1
|
1
|
|
0
|
1
|
0
|
0
|
|
0
|
1
|
1
|
0
|
|
1
|
0
|
0
|
1
|
|
1
|
0
|
1
|
0
|
|
1
|
1
|
0
|
1
|
|
1
|
1
|
1
|
0
|
Ans: The K-map for the given function (as per the truth table) is produced
below.
The three duets are: y’z’, x’y’ and xz’. The DNF (Disjunctive
normal form) is the Boolean expression for a Boolean function in which
function is expressed as disjoint of the min terms for which output of function
is 1. The minimum DNF is the sum of prime implicant. Thus the minimum DNF for
the given function is
y’z’+
x’y’ + xz’
Q.16 Define
tautology and contradiction. Show that “If the sky is cloudy then it will rain
and it will not rain”, is not a contradiction. (5)
Ans: If a compound proposition has two
atomic propositions as components, then the truth table for the compound
proposition contains four entries. These four entries may be all T, may be all
F, may be one T and three F and so on. There are in total 16 (24)
possibilities. The possibilities when all entries in the truth table is T,
implies that the compound proposition is always true. This is called tautology.
However when all the entries are F, it implies that the proposition
is never true. This situation is referred as contradiction.
Code: AC10
Subject: DISCRETE STRUCTURES
Let p: “Sky is
cloudy”; q : “It will rain”.
Then the given statement can be written as “(p®q) Ù ~q”. The truth table for the expression is as below:
|
p
|
q
|
p®q
|
(p®q) Ù ~q
|
|
0
|
0
|
1
|
1
|
|
0
|
1
|
1
|
0
|
|
1
|
0
|
0
|
0
|
|
1
|
1
|
1
|
0
|
Obviously, (p®q) Ù ~q is not a
contradiction.
Q.17 How many
words of 4 letters can be formed with the letters a, b, c, d, e, f, g and h,
when
(i)
e and f are not to be included and
(ii)
e and f are to be included. (7)
Ans: There are 8 letters: a, b, c, d, e, f, g and h. In order to form a
word of 4 letters, we have to find the number of ways in which 4 letters can be
selected from 8 letters. Here order is important, so permutation is used.
(i)
When e and f are not to be
included, the available letters are 6 only. Thus we can select 4 out of six to
form a word of length 4 in 6P4 ways = 
. Thus 360 words can be
formed.
(ii)
When e and f are to be included,
the available letters are all 8 letters. Thus we can select 4 out of 8 to form
a word of length 4 in 8P4 ways = 
. Thus 1680 words can be
formed.
Q.18 Explain
chomsky classification of languages with suitable examples. (7)
Ans: Any language is suitable for
communication provided the syntax and semantic of the language is known to the
participating sides. It is made possible by forcing a standard on the way to
make sentences from words of that language. This standard is forced through a
set of rules. This set of rules is called grammar of the
language. According to the Chomsky classification, a grammar G = (N, å, P, S) is said
to be of
Type 0: if there is no restriction on
the production rules i.e., in a®b, where a, bÎ (N È å)*. This type of
grammar is also called an unrestricted grammar and language is
called free language.
Code: AC10
Subject: DISCRETE STRUCTURES
Type 1: if in every production a®b of P, a, b Î (N È å)* and |a| £ |b|. Here |a| and |b| represent number of symbols in string a and b respectively.
This type of grammar is also called a context sensitive grammar
(or CSG) and language is called context sensitive.
Type 2: if in every production a®b of P, a Î N and b Î (N È å)*. Here a is a single non-terminal symbol. This type of grammar is also
called a context free grammar (or CFG) and language
is called context free.
Type 3: if in every production a®b of P, a Î N and b Î (N È å)*. Here a is a single non-terminal symbol and b may consist of at the most
one non-terminal symbol and one or more terminal symbols. The non-terminal
symbol appearing in b must be the extreme right symbol. This type of grammar is also
called a right linear grammar or regular grammar
(or RG) and the corresponding language is called regular
language.
Q.19 Find a generating function to count the number of
integral solutions to 
if for each I, 0 
. (7)
Ans: According to the given constraints
polynomial for variable e1 can be written as
1+ x + x2 + x3 + …. since
0 £
e1
Similarly
polynomial for variable e2 and e3 can be written as
1+ x + x2 + x3 + …. since
0 £
e2
1+ x + x2 + x3 + …. since
0 £
e3
respectively.
Thus the number of
integral solutions to the given equations under the constraints is equal to the
coefficient of x10 in the expression
(1+ x + x2
+ x3 + …. )( 1+ x + x2 + x3 + ….
)( 1+ x + x2 + x3 + …. )
Thus the
generating function f(x) = 
.
Q.20. Prove by elimination of cases : if X is a number such that
then X = 3 or X = 2.
(7)
Ans: Let a and b be two roots of the equation, then
a + b = 5 and a *
b = 6
Now, (a
– b)2 = (a + b)2 – 4a*b
= 25 – 24 = 1
Code: AC10
Subject: DISCRETE STRUCTURES
\ a – b = 1 or -1
Now using the method of elimination (adding) the two equation a + b
= 5 and a – b = 1, we get,
2a = 6, or a = 3.
Using this value in any of the equation, we get b = 2.
It is easy to
verify that, if a – b = -1 is taken then we get a = 2 and b = 3. Thus two root
of the given equations are X = 3 or X = 2.
Q.21 Consider the
following open propositions over the universe 
R(x) : s is a multiple
of 2
Find the truth values
of
(8)
Ans: The truth values for each element
of U under the given conditions of propositions is given in the following
table:
|
x
|
P(x)
|
Q(x)
|
R(x)
|
P(x)
Ù
R(x)
|
~Q(x)Ù P(x)
|
|
-4
|
0
|
0
|
1
|
0
|
0
|
|
-2
|
0
|
0
|
1
|
0
|
0
|
|
0
|
0
|
0
|
1
|
0
|
0
|
|
1
|
0
|
0
|
0
|
0
|
0
|
|
3
|
0
|
0
|
0
|
0
|
0
|
|
5
|
1
|
1
|
0
|
0
|
0
|
|
6
|
1
|
0
|
1
|
1
|
1
|
|
8
|
1
|
0
|
1
|
1
|
1
|
|
10
|
1
|
0
|
1
|
1
|
1
|
Q.22 Let 
then compute 
. (6)
Ans: It is given that nzr is defined as (n + 1) nPr-1. Then we can
write
(n+1)z(r – 1) = (n + 2) n+1Pr-2 = 
, and
7z4 = 8* 7P3 = 
Q.23 Translate
and prove the following in terms of propositional logic
A = B if and
only if A 
B
and B A (5)
Code: AC10
Subject: DISCRETE STRUCTURES
Ans: Let SUB(A, B) stands for “A is subset of B” and EQL(A, B) stands
for “A is equal to B”. Then the given statement can be written as
"A, B [SUB(A, B) Ù SUB(B, A)] Û EQL(A, B)
Q.24 Determine
the number of integral solutions of the equation
(9)
Ans: According to the given constraints polynomial for variable x1
can be written as
x2 + x3 + x4 + x5 + x6
since 2 £ x1 £ 6
Similarly
polynomial for variable x2, x3 and x4 can be
written as
x3 + x4 + x5 + x6 + x7
since 3 £ x2 £ 7
x5 + x6 + x7 + x8
since 5 £ x3 £ 8
x2 + x3 + x4 + x5 + x6
+ x7 + x8 + x9 since 2 £ x4 £ 9
respectively.
Thus the number of
integral solutions to the given equations under the constraints is equal to the
coefficient of x20 in the expression
(x2 + x3
+ x4 + x5 + x6)( x3 + x4
+ x5 + x6 + x7)( x5 + x6
+ x7 + x8)( x2 + x3 + x4
+ x5 + x6 + x7 + x8 + x9)
= x12
(x5 – 1)2 (x4 – 1)2(x4 +
1) (x – 1)–4
= x12
[1 – x4 – 2x5 – x8 + 2x9 + x10
+ x12 + 2x13 – x 14 – 2x 17– x 18+
x22] (1 – x)–4
In the coefficient of x20, the terms that can contribute
are from (1 – x4 – 2x5 – x8) only. All other
terms when multiplied with x20, yields higher degree terms.
Therefore coefficients of x20 in the entire expression are equal to
linear combinations of coefficients of x8, x4, x3
and 1 in (1 – x)–4 with respective constant coefficients 1, -1, -2,
-1. This is equal to
Therefore number
of integral solution is 89.
Q.25 Using BNF
notation construct a grammar G to generate the language over an alphabet 
with an equal
number of 0’s and 1’s for some integer 
(7)
Ans: The given language is
defined over the alphabet å = {1, 0}. A string in this language contains equal number of 0 and
1. Strings 0011, 0101, 1100, 1010, 1001 and 0110 are all valid strings of
length 4 in this language. Here, order of appearance of 0’s and 1’s is not
fixed. Let S be the start symbol. A string may start with either 0 or 1. So, we
should have productions S ®
Code: AC10
Subject: DISCRETE STRUCTURES
0S1, S ® 1S0, S ® 0A0 and S ® 1B1 to implement this. Next A and B should be replaced in such a
way that it maintains the count of 0’s and 1’s to be equal in a string. This is
achieved by the productions A ® 1S1 and B ® 0S0. The null string is also an acceptable string, as it
contains zero number of 0’s and 1’s. Thus S ® e should also be a
production. In addition to that a few Context sensitive production rules are to
be included.
These are: A ® 0AD0, 0D1 ® 011, 0D0 ® 00D, B® 1BC1, 1C0 ® 100, 1C1 ® 11C. Therefore, the required grammar G can be given by (N, å, P, S), where N
= {S, A, B}, å = (1, 0} and P = {S ® 0S1, S ® 1S0, S ® 0A0, S ® 1B1, A ® 1S1, B ® 0S0, A ® 0AD0, 0D1 ® 011, 0D0 ® 00D, B® 1BC1, 1C0 ® 100, 1C1 ® 11C, S ® e}.
Q.26 Construct the derivation trees for the strings 01001101 and
10110010 for the above grammar. (7)
Ans: The derivation tree for the given
string under the presented grammar is as below.
Q.27 Find the generating function to
represent the number of ways the sum 9 can be obtained when 2 distinguishable
fair dice are tossed and the first shows an even number and the second shows an
odd number. (5)
Ans: Let x1 and x2
be the variable representing the outcomes on the two dice the x1 has
values 2, 4, 6 and x2 has 1, 3, 5. Now polynomial for variable x1
and x2 can be written as (x2 + x4 + x6)
and (x + x3 + x5) respectively.
Thus the number of
ways sum 9 can be obtained is equal to the coefficient of x9 in the
expression (x2 + x4 + x6)(x + x3 +
x5). This is equal to 2.
Code: AC10
Subject: DISCRETE STRUCTURES
Q.28 Prove
that if 
are
elements of a lattice 
then
(9)
Ans:
Let us use b = L1 and a = L2. It is given that aÚb = b. Since aÚb
is an upper bound of a, a £ aÚb. This implies a £ b.
Next,
let a £ b. Since £ is a partial order relation, b £ b. Thus, a£b
and b£b together implies that b is an
upper bound of a and b. We know that aÚb
is least upper bound of a and b, so aÚb
£ b. Also b £ aÚb because aÚb is an upper bound of b. Therefore, aÚb £
b and b £ aÚb Û aÚb = b by the anti-symmetry property of
partial order relation £. Hence, it is
proved that aÚb = b if and only if a £ b.
Q.29 Let 
be a semigroup.
Consider a finite state machine M = (S, S F), where 
and fx (y) = x * y for
all x, y 
Consider
the relation R on S, x R y if and only if there is some z such that fz (x) = y.
Show that R is an equivalence relation.
(14)
Ans: Let M = (S, I, Á, s0, T) be a FSM where S is the set of states, I is set
of alphabets, Á is transition table, s0 is initial state and T is the
set of final states. Let TC = S – T. Then set S is decomposed into
two disjoint subsets T and TC. Set T contains all the terminal
(acceptance) states of the M and TC contains all the non-terminal
states of M. Let w Î I* be any string. For any state s Î S, fw(s)
belongs to either T or TC. Any two states: s and t are said to be
w-compatible if both fw(s) and fw(t) either
belongs to T or to TC for all wÎ I*.
Now we have to show that if R be a relation defined on S as sRt if
and only if both s and t are w-compatible the R is an equivalence relation.
Let
s be any state in S and w be any string in I*. Then fw(s) is either
in T or in TC. This implies that sRs " sÎ S. Hence R is
reflexive on S. Let s and t be any two states in S such that sRt. Therefore, by
definition of R both s and t w-compatible states. This implies that tRs. Thus,
R is symmetric also. Finally, let s, t and u be any three states in S such that
sRt and tRu. This implies that s t and u are w-compatible states i.e. s and u are
w-compatible. Hence sRu. Thus, R is a transitive relation. Since R is
reflexive, symmetric and transitive, it is an equivalence relation.
Q.30 Represent
each of the following statements into predicate calculus forms :
(i) Not all birds can fly.
(ii) If x is a man, then x is a giant.
(iii)
Some men are not giants.
(iv)
There is a student who likes mathematics but not
history. (9)
Ans:
(i) Let us assume
the following predicates
Code: AC10
Subject: DISCRETE STRUCTURES
bird(x):
“x is bird”
fly(x): “x can fly”.
Then given
statement can be written as: $x bird(x) Ù ~ fly(x)
(ii)
Let us assume the following predicates
man(x): “x is Man”
giant(x): “x is giant”.
Then
given statement can be written as: "x (man(x)® giant(x))
(iii) Using the
predicates defined in (ii), we can write
$x
man(x) Ù ~ giant(x)
(iv) Let us assume
the following predicates
student(x): “x is student.”
likes(x, y): “x likes y”. and ~likes(x, y) Þ “x does not like y”.
Then given
statement can be written as:
$x
[student(x) Ù likes(x, mathematics) Ù~ likes(x, history)]
Q.31 Let X be the
set of all programs of a given programming language. Let R the relation on X
be defined as
give the same output on all the
inputs for which they terminate.
Is R an equivalence relation? If
not which property fails? (5)
Ans: R is defined on the set X of all
programs of a given programming language. Now let us test whether R is an
equivalence relation or not
Reflexivity: Let P be any element of
X then obviously P gives same output on all the inputs for which P terminates
i.e. P R P. Thus R is reflexive.
Symmetry: Let P and Q are any two
elements in X such that P R Q. Then P and Q give same output on all the inputs
for which they terminate => Q R P =>R is symmetric.
Transitivity: Let P, Q and S are any
three elements in X such that P R Q and Q R S. It means P and Q gives the same
out for all the inputs for which they terminate. Similar is the case for Q and
S. It implies that there exists a set of common programs from which P, Q and S
give the same output on all the inputs for which they terminate i.e. P R S
=> R is transitive.
Therefore R is an
equivalence relation.
Q.32 Let 
and relation 
be partial
order of divisibility on A. Let 
and 
be the relation “less than or
equal to” on integers. Show that 
are isomorphic posets. (7)
Code: AC10
Subject: DISCRETE STRUCTURES
Ans: Any two posets (A, R1) and
(A’, R2) are said to isomorphic to each other if there exists a
function f: A ® A’ such that
·
f is one to one and
onto function; and
·
For any a, b Î A, a R1 b Û f(a) R2 f(b), i.e. images
preserve the order of pre-images.
Let f: A ® A’ is defined
as f(1) = 0, f(2) = 1, f(4) = 2, f(8) = 3, f(16) = 4.
It is obvious from the definition that f is one to one and
onto. Regarding preservation of order, it is preserved under the respective
partial order relation. It is shown in the following hasse diagram.
Q.33 Let 
be defined as 
, then either
prove or give counter example for the following,
(7)
Ans: Let R = {1, 2, 3, 4}; S = {1, 2, 3,
4, 5, 6} and T = {3, 6, 7}. Obviously R Í S. However RÑ T = {1, 2, 4,
6, 7}and S Ñ T = {1, 2, 4, 5, 7}. Clearly, (RÑ T) Ë (S Ñ T). Hence it is
disproved.
Q.34 Prove or
disprove the following equivalence,
(9)
Ans: RHS of the given expression ((p Ù ~q) Ú (q Ù ~p)) can be
written as
~(~((p Ù ~q) Ú (q Ù ~p))) = ~((~(p Ù ~q)) Ù (~(q Ù ~p)))
= ~((~p Ú q) Ù (~q Ú p))
= ~((p ® q) Ù (q ® p))
= ~(p « q)
Q.35 Solve the
following recurrence relation and indicate if it is a linear homogeneous
relation or not. If yes, give its degree and if not justify your answer. 
(5)
Ans: The given equation can be written
in the following form:
tn - tn-1 = n
Code: AC10
Subject: DISCRETE STRUCTURES
Now successively replacing n by (n – 1)
and then by (n – 2) and so on we get a set of equations. The process is
continued till terminating condition. Add these equations in such a way that
all intermediate terms get cancelled. The given equation can be rearranged as
tn – tn–1 = n
tn–1 – tn–2 = n – 1
tn–2 – tn–3 = n – 2.
tn–3 – tn–4 = n – 3
.
t2 – t1 = 2 [we stop here, since t1 = 4 is given ]
Adding all, we get tn – t1 = [n + (n – 1) + (n – 2) + ... + 2]
or, tn = [n + (n – 1) + (n – 2) + ... + 2 + 4]
or, tn = 
The given recurrence equation is linear and non homogeneous. It is
of degree 1.
Q.36 State the
relation between Regular Expression, Transition Diagram and Finite State
Machines. Using a simple example establish your claim. (6)
Ans: For every regular language, we can
find a FSM for this, because a FSM work as recognizer of a regular language.
Whether a language is regular can be determined by finding whether a FSM can be
drawn or not.
A machine contains finite number of states. To determine whether a
string is valid or not, the FSM begins scanning the string from start state and
moving along the transition diagram as per the current input symbol. The table
showing the movement from one state to other for input symbols of the alphabets
is called transition table.
Every machine has a unique transition table. Thus there is one to
one relationship between Regular language and FSM and then between FSM and
transition table.
Q.37 Identify the
type and the name of the grammar the following set of production rules belong
to. Also identify the language it can generate. (8)
Code: AC10
Subject: DISCRETE STRUCTURES
Ans: In the left hand side of the
production rules, only single non terminal symbol is use. This implies that the
grammar is either of Type 2 or Type 3. In the RHS of some production rules,
there are more than one non terminal. The null production can be removed by
combining it with the other productions. Thus, according to the Chomsky
hierarchy, the grammar is of type 2, and name of the grammar is Context Free
Grammar(CFG). The language of the grammar can be determined as below:
S1 ® S1S2
® S1S2S3
[Apply rule S2 ® S2S3]
® S1S2 0mS3
[Apply rule S3 ® 0S3 (m
³ 0)
times]
® S1S2 0m
[Apply rule S3 ® e]
® S1 01S2 0m
[Apply rule S2 ® 01S2 ]
® S1 (01)l (0m)k [Apply
rule S2 ® S2S3 and S2 ® 01S2 (k ³ 0,
l
³ 1)
times and then S2 ® 01 once ]
® 1n
[(01)l (0m)k ] t [Apply
rule S1 ® S1S2 , (t ³ 0) times,
S1®1S1 (n ³ 0) time and S2
® e once]
That the language
contains strings of the form 1n [(01)l (0m)k
] t where l ³ 1 and other values like n, m, k and t are ³ 0.
Q.38 For any positive integer n, let 
.
Let the relation “divides”
be written as 
iff a divides b or b = ac for some integer c. Draw the
Hasse diagram and determine whether 
is a lattice. (8)
Ans: Hasse diagram for the structure (I12, |) is given below.
Code: AC10
Subject: DISCRETE STRUCTURES
It
is obvious from the Hasse diagram that there are many pairs of element, e.g (7,
11), (8, 10) etc that do not have any join in the set. Hence (I12,
|) is not a lattice.
Q.39 Give the
formula and the Karnaugh map for the minimum DNF,
(Disjunctive Normal Form)
(6)
Ans: The K-map for the given DNF is shown below. The formula for the same
is
pq’
+ s’q’ + pr’s
Q.40 If the
product of two integers a and b is even then prove that either a is even or b
is even. (5)
Ans: It is given that product of a and b
is even so let a * b = 2n. Since 2 is a prime number and n is any integer (odd or
even), either a or b is a multiple of 2. This shows that either a is even or b
is even.
Q.41 Using proof
by contradiction, prove that “
is irrational”. Are irrational
numbers countable? (5)
Code: AC10
Subject: DISCRETE STRUCTURES
Ans:
If s were a
rational number, we can write
Where p is an integer and q is any positive integer. We can
further assure that the gcd(p, q) =1 by driving out common factor
between p and q, if any. Now using equation (2), in equation (1), we get
Conclusion: From equation (3), 2
must be a prime factor of p2. Since 2 itself is a
prime, 2 must be a factor of p itself. Therefore, 2*2 is a factor of
p2. This implies that 2*2 is a factor of 2*q2.
Þ 2 is a factor of q2
Þ 2 is a factor of q
Since,
2 is factor of both p and q gcd(p, q) = 2. This is
contrary to our assumption that gcd(p, q) = 1. Therefore, Ö2 is an
irrational number. The set of irrational numbers is uncountable.
Q.42 Use
quantifiers and predicates to express the fact that 
does not exist. (4)
Ans: Let P(x, a) : 
Then the given limit
can be written as
$a ØP(x, a).
Q.43 Minimize the
following Boolean expression using k-map method
(7)
Code: AC10
Subject: DISCRETE STRUCTURES
Ans:
The minimized
boolean expression C’D’ + A’C’ + AB
Q.44 Find a recurrence relation for
the number of ways to arrange flags on a flagpole n feet tall using 4 types of
flags: red flags 2 feet high, white, blue and yellow flags each 1 foot high. (7)
Ans: Let An be the number of
ways in which the given flags can be arranged on n feel tall flagpole. The red
color flag is of height 2 feet, and white, blue and yellow color flag is of
height 1 foot. Thus if n =1, flag can be arranged in 3 ways. If n = 2, the
flags can be arranged in either 3x3 ways using 3 flags of 1 foot long each or
in 1 way using 2 feet long red flag. Thus, flags on 2 feet long flagpole can be
arranged in 10 ways. This can be written in recursive form as:
An
= 3An – 1 ; An = 10An – 2 ; Adding them
together, we have
2An
– 3An – 1 – 10An – 2 = 0 and A1 = 3; A2
= 10.
Q.45 What is the
principle of inclusion and exclusion? Determine the number of integers between
1 and 250 that are divisible by any of the integers 2, 3, 5 and 7. (7)
Ans:
This principle is
based on the cardinality of finite sets. Let us begin with the given problem of
finding all integers between 1 and 250 that are divisible by any of the
integers 2, 3, 5 or 7. Let A, B, C and D be two sets defined as:
A
= {x | x is divisible by 2 and 1 £ x £ 250},
B
= {x | x is divisible by 3 and 1 £ x £ 250},
C
= {x | x is divisible by 5 and 1 £ x £ 250} and
D = {x | x is divisible by 7 and 1 £ x £ 250}
Similarly, A Ç B= {x | x is divisible by 2 and 3 and 1 £ x £ 250}
Code: AC10
Subject: DISCRETE STRUCTURES
.
.
C Ç D = {x | x is divisible by 5 and 7 and 1 £ x £ 250}
AÇBÇD = {x | x is divisible by 2, 3 and 7 and 1 £ x £ 250}
Here,
problem is to find the number of elements in AÈBÈCÈD. Also, there are numbers
that are divisible by two or three or all the four numbers taken together. A Ç B, A ÇC, A Ç D, B Ç C, …, C Ç D are not null
set. This implies that while counting the numbers, whenever common elements
have been included more than once, it has to be excluded. Therefore, we can
write
|
A È
B È
C È
D | = |A| + |B| + |C| + |D| – |AÇB| – |AÇC| – |AÇD| – |BÇC| – |BÇD| – |C Ç D| + |AÇBÇC| + |AÇBÇD| + |AÇCÇD| + |BÇCÇD| - |AÇBÇCÇD|
The
required result can be computed as below:
Code: AC10
Subject: DISCRETE STRUCTURES
Therefore,
| A È B È C È D | = 125 + 83
+50 + 35 – 41 – 25 – 17 – 16 – 11 – 7 +8 + 5 + 3 + 2 –1
= 311 – 118
= 193.
Q.46 Show that 
is tautologically
implied by 
. (7)
Ans: Let us find the truth table for [(PÚQ)Ù(P®R)Ù(Q®S)] ® (SÚR).
|
P
|
Q
|
R
|
S
|
(PÚQ)
|
(P®R)
|
(Q®S)
|
(SÚR)
|
[(PÚQ)Ù(P®R)Ù(Q®S)] ® (SÚR)
|
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
|
0
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
Code: AC10
Subject: DISCRETE STRUCTURES
Hence the
implication is a tautology.
Q.47 Identify the regular set
accepted by the Fig.2 finite state machine and construct the corresponding
state transition table.
(7)
Ans: The transition table for the given FSM is as below:
|
State
|
0
|
1
|
|
A
|
{A,
B}
|
{}
|
|
B
|
{B}
|
{C}
|
|
C
|
{B}
|
{D}
|
|
D
|
{E}
|
{A}
|
|
E
|
{D}
|
{C}
|
The language
(Regular set) accepted by the FSM is any string on the alphabets {0, 1} that
(a)
begins with ‘0’
(b)
contains substring ‘011’ followed by zero or
more 0’s, and
(c)
does not contain 3 consecutive 1’s.
Q.48 Construct
truth tables for the following:
(7)
Ans: The required truth table for (pÚq) Ù (Ør) « q is as below:
|
p
|
q
|
r
|
pÚq
|
(pÚq) Ù (Ør)
|
(pÚq) Ù (Ør) « q
|
|
0
|
0
|
0
|
0
|
0
|
1
|
|
0
|
0
|
1
|
0
|
0
|
1
|
|
0
|
1
|
0
|
1
|
1
|
1
|
|
0
|
1
|
1
|
1
|
0
|
0
|
|
1
|
0
|
0
|
1
|
1
|
0
|
|
1
|
0
|
1
|
1
|
0
|
1
|
|
1
|
1
|
0
|
1
|
1
|
1
|
|
1
|
1
|
1
|
1
|
0
|
0
|
Code: AC10
Subject: DISCRETE STRUCTURES
Q.49 Find
the coefficient of 
in 
(7)
Ans: Let the given expression is written as
f(x) = (1 + x +
x2 + x3 +¼+ xn)2 
= (1 – x)–2
The coefficient of x10 is equal to
Q.50 If 
is a complemented and
distributive lattice, then the complement 
of any element 
is unique. (7)
Ans:
Let I and 0 are the unit and zero elements of L
respectively. Let b and c be two complements of an element a Î L. Then from
the definition, we have
a
Ù b
= 0 = a Ù c and
a Ú b = I = a Ú c
We can write
b = b Ú 0 = b Ú (a Ù c )
=
(b Ú
a) Ù
(b Ú
c ) [since lattice is distributive ]
= I Ù (b Ú c )
= (b Ú c )
Similarly,
c = c Ú 0 = c Ú (a Ù b )
=
(c Ú
a) Ù
(c Ú
b) [since lattice is distributive ]
= I Ù (b Ú c) [since Ú is a commutative operation]
= (b Ú c)
The above two results show
that b = c.
Q.51 Consider the
following Hasse diagram Fig.3 and the set B= {3, 4, 6}. Find, if they exist,
(i)
all upper bounds
of B;
(ii)
all lower bounds of B;
(iii)
the least upper bound of B;
(iv)
the greatest lower bound of B; (7)
Code: AC10
Subject: DISCRETE STRUCTURES
Ans:
(i) The set of
upper bounds of subset B = {3, 4, 6} in the given lattice is {5}. It is only
element in the lattice that succeeds all the elements of B.
(ii) Set
containing lower bounds is {1, 2, 3}
(iii) The least
upper bound is 5, since it is the only upper bounds.
(iv) The greatest
lower bound is 3, because it is the element in lower bounds that succeeds all
the lower bounds.
Q.52 Solve the
recurrence relation 
. (7)
Ans:
The general solution, also called homogeneous solution, to
the problem is given by homogeneous part of the given recurrence equation. The
homogeneous part of the given equation is
The characteristic equation of (2) is given as
The homogeneous solution is given by
------------------------(2)
Now, particular solution is given by
Substituting the
value of Sk in the given equation, we get
Code: AC10
Subject: DISCRETE STRUCTURES
The complete,
also called total, solution is obtained by combining the homogeneous
and particular solutions. This is given as
Since no
initial condition is provided, it is not possible to find A and B,
Q.53 Prove that 
. (7)
Ans: In order to prove this let x be any element of A È B, then
x Î A È B Û x Î A or x Î B
Û (x Î A and x Ï B) or (x Î B and x Ï A) or (x Î A and x Î B)
Û (x Î A – B) or (x Î B – A) or (x Î A Ç B)
Û x Î (A – B) È (B – A) È (A Ç B)
This implies
that
A È B Í
(A – B) È (B – A) È (A Ç B) and
(A – B) È
(B – A) È (A
Ç B) Í A È B
Thus A È B = (A – B) È (B – A) È (A Ç B)
Q.54 There are 15
points in a plane, no three of which are in a straight line except 6 all of
which are in one straight line.
Code: AC10
Subject: DISCRETE STRUCTURES
(i) How many straight lines
can be formed by joining them?
(ii) How many triangles can be
formed by joining them? (7)
Ans: There are 15 points out of which 6 are collinear. A straight can
pass through any two points. Thus
(i) The number straight lines that can be formed is 15C2
– 6C2 +1 = 105 – 15 + 1 = 91. 15C2 is
the number of ways two points can be selected. If the two points are coming
from 6 collinear, then there can be only one straight line. Thus 6C2
is subtracted and 1 is added in the total.
(ii) The number Triangles that can be formed is 15C3
– 6C3 = 455 – 20 = 425. 15C3 is
the number of ways three points can be selected to form a triangle. If the
three points are coming from 6 collinear, then no triangle is formed. Thus 6C3
is subtracted from the total.
Q.55 Prove
the following Boolean expression:
(7)
Ans: In the given expression, LHS is equal to:
(xÚy)Ù(xÚ ~y)Ù(~x Ú z) = [xÙ(xÚ ~y)] Ú [yÙ(xÚ ~y)] Ù(~x Ú z)
= [xÙ(xÚ ~y)] Ú [yÙ(xÚ ~y)] Ù(~x Ú z)
= [(xÙx) Ú (xÙ~y)] Ú [(yÙx)Ú (yÙ~y)] Ù(~x Ú z)
= [x Ú (xÙ~y)] Ú [(yÙx)Ú 0] Ù(~x Ú z)
= [x Ú (yÙx)] Ù(~x Ú z) [x Ú (xÙ~y) =x]
= x Ù(~x Ú z) [x
Ú (xÙy) =x]
= [x Ù~x)] Ú (x Ù z) [x Ú (xÙ~y) =x]
= 0 Ú (x Ù z) = (x Ù z) = RHS
Q.56 Find how
many words can be formed out of the letters of the word DAUGHTER such that
(i)
The vowels are always together.
(ii)
The vowels occupy even places. (7)
Ans: In the word DAUGHTER, there are
three vowels: A, E and U. Number of letters in the word is 8.
(i)
When vowels are always together, the number
of ways these letters can be arranged (5 +1)! * 3!. The 5 consonants and one
group of vowels. Within each such arrangement, the three vowels can be arranged
in 3! Ways. The required answer is 4320.
(ii)
When vowel occupy even position, then the
three vowels can be placed at 4 even positions in 3*2*1 ways. The three even
positions can be selected in 4C3 ways. And now the 5
consonants can be arranged in 5! Ways. Therefore the required number is = 3! * 4C3
*5! = 2880
Code: AC10
Subject: DISCRETE STRUCTURES
Q.57 Let R be the
relation on the set of ordered pairs of positive integers such that 
if and only
if ad = bc. Determine whether R is an equivalence relation or a partial
ordering. (8)
Ans: R is defined on the set P of cross product of set of positive
integers Z+ as (a, b) R (c, d) iff a*d =b*c. Now let us test whether R is an
equivalence relation or not
Reflexivity: Let (x, x) be any element of P, then since a*a = a*a , we can say
the (a, a) R (a, a).Thus R is reflexive.
Symmetry: Let (a, b) and (c, d) are any two elements in P such that (a, b) R
(c, d). Then we have a*d = b*c => c*b = d*a => (c, d) R (a, b) => R is
symmetric.
Transitivity: Let (a, b), (c, d) and (e, f) are any
three pairs in P such that (a, b) R (c, d) and (c, d) R (e, f). Then we have
a*d = b*c and c*f = d*e => a/e = b/f => a*f = b*e => (a, b) R (e, f)
=> R is transitive.
Therefore R is an
equivalence relation.
Q.58 Prove that
the direct product of any two distributive lattice is a distributive. (6)
Ans:
Let (L1, £1) and (L2, £2) be two
distributive lattices then we have to prove that (L, £) is also a
distributive lattice, where L = L1 ´ L2 and £ is the product
partial order of (L1, £1) and (L2, £2). It will be
sufficient to show that L is lattice, because distributive properties shall be
inherited from the constituent lattices.
Since
(L1, £1) is a lattice, for any two elements
a1 and a2 of L1, a1Úa2 is
join and a1Ùa2 is meet of a1 and a2 and both
exist in L1. Similarly for any two elements b1 and b2
of L2, b1Úb2 is join and b1Ùb2 is meet of b1
and b2 and both exist in L2. Thus, (a1Úa2, b1Úb2)
and (a1Ùa2, b1Ùb2) Î L. Also (a1,
b1) and (a2, b2) Î L for any a1, a2
Î L1
and any b1, b2 Î L2.
Now
if we prove that
(a1,
b1) Ú (a2, b2) = (a1Úa2, b1Úb2)
and
(a1,
b1) Ù (a2, b2) = (a1Ùa2, b1Ùb2)
then
we can conclude that for any two ordered pairs (a1, b1)
and (a2, b2) Î L, its join and meet exist and thence (L, £) is a lattice.
We
know that (a1, b1) Ú (a2, b2)
= lub ({(a1, b1), (a2, b2)
}). Let it be (c1, c2). Then,
(a1,
b1) £ (c1, c2) and (a2, b2) £ (c1,
c2)
Þ a1£1c1, b1 £2 c2; a2 £1c1, b2 £2 c2
Þ a1£1c1, a2 £1c1; b1 £2 c2, b2 £2 c2
Þ a1Ú a2 £1c1; b1Ú b2 £2 c2
Code: AC10
Subject: DISCRETE STRUCTURES
Þ(a1Ú a2 ,
b1Ú b2) £ (c1, c2)
This
shows that (a1Ú a2 , b1Ú b2) is an upper
bound of {(a1, b1), (a2, b2)} and
if there is any other upper bound (c1, c2) then (a1Ú a2 ,
b1Ú b2) £ (c1, c2). Therefore, lub ({(a1,
b1), (a2, b2)}) = (a1Ú a2,
b1Ú b2) i.e.
(a1, b1) Ú (a2, b2) = (a1Úa2, b1Úb2)
Similarly, we can show for the
meet.
Q.59 Given n
pigeons to be distributed among k pigeonholes. What is a necessary and
sufficient condition on n and k that, in every distribution, at least two
pigeonholes must contain the same number of pigeons?
Prove
the proposition that in a room of 13 people, 2 or more people have their
birthday in the same month. (8)
Ans: The situation when all the k
pigeonholes may contain unique number of pigeons out of n pigeons, if n ³ (0 + 1 + 2 + 3
+…+ (k – 1)) = 
. Thus, as long as n (number of
pigeons)
is less than equal to , at least two of the k
pigeonholes shall contain equal number of pigeons.
Let 12 months are pigeonholes and 13
people present in the room are pigeons. Pick a man and make him seated in a
chair marked with month corresponding his birthday. Repeat the process until 12
people are seated. Now even in the best cases, if all the 12 people have
occupied 12 different chairs, the 13th person will have to share
with any one, i.e. there is at least 2 persons having birthday in the same
month.
Q.60 Define a grammar. Differentiate
between machine language and a regular language. Specify the Chowsky’s
classification of languages. (6)
Ans: Any language is suitable for communication provided the syntax and
semantic of the language is known to the participating sides. It is made
possible by forcing a standard on the way to make sentences from words of that
language. This standard is forced through a set of rules. This set of rules is
called grammar of the language. A grammar G = (N, å, P, S) is said
to be of
Type 0: if there is no restriction on
the production rules i.e., in a®b, where a, bÎ (N È å)*. This type of
grammar is also called an unrestricted grammar.
Type 1: if in every production a®b of P, a, b Î (N È å)* and |a| £ |b|. Here |a| and |b| represent number of symbols in string a and b respectively.
This type of grammar is also called a context sensitive grammar
(or CSG).
Code: AC10
Subject: DISCRETE STRUCTURES
Type 2: if in every production a®b of P, a Î N and b Î (N È å)*. Here a is a single non-terminal symbol. This type of grammar is also
called a context free grammar (or CFG).
Type 3: if in every production a®b of P, a Î N and b Î (N È å)*. Here a is a single non-terminal symbol and b may consist of at the most
one non-terminal symbol and one or more terminal symbols. The non-terminal
symbol appearing in b must be the extreme right symbol. This type of grammar is also
called a right linear grammar or regular grammar
(or RG).
For any language
a acceptor (a machine) can be drawn that could be DFA, NFA, PDA, NPDA, TM etc.
Language corresponding to that machine is called machine language. In
particular a language corresponding to Finite automata is called Regular
language.
Q.61 Determine the
closure property of the structure [
,(·)] with respect to the operations 
and (·). Illustrate using examples and give the identity element, if one exists
for all the binary operations. (9)
Ans: Let A and B are any two 5x5 Boolean
matrices. Boolean operations join (Ú), meet (Ù) and product [(·)] on set of 5x5
Boolean matrix M is defined as
A Ú B = [cij], where cij = max {aij, bij}
for 1 £ i £ 5, 1 £ j £ 5
A Ù B = [cij], where cij = min {aij, bij}
for 1 £ i £ 5, 1 £ j £ 5
A (·) B = [cij], where cij = 
for 1 £ i £ 5, 1 £ j £ 5
It is obvious that
for any two matrices A and B of M, (A Ú B), (A Ù B) and (A (·) B) are also in
M. Hence M closed under Ú, Ù and (·). The identity element for the operations Ú, Ù and (·) are
,
and 
respectively.
Q.62 Prove that
if x is a real number then
(5)
Code: AC10
Subject: DISCRETE STRUCTURES
Ans: Let x be any real number. It has two parts: integer and fraction.
Without loss of any generality, fraction part can always be made +ve. For
example, -1.3 can be written as –2 + 0.7. Let us write x = a + b, and [x] = a
(integer part only of the real x). The fraction part b needs to considered in
two cases:
0
< b < 0.5 and 0.5 £ b < 1.
Case 1: 0 < b
< 0.5; In this case [2x] = 2a, and [x] +[x + .5] = a + a = 2a
Case 2: 0.5 £ b < 1; In
this case [2x] = 2a + 1, and [x] +[x + .5] = a + (a + 1) = 2a +1
Hence [2x] = [x]
+ [x + .5]
Q.63 Let 
. For n a
positive integer and 
the 
Fibonacci number show that
(5)
Ans: The Fibonacci number is given as 1, 1, 2, 3, 5, 8, ... and so on
and defined as
fn
= fn – 1 + fn – 2
For A = 
, we have 
. Let us suppose that it
is true for n = k i.e. 
. Then we prove that it is true
for n = k + 1 as well and hence the result shall follow from mathematical
induction.
Therefore we
have the result, 
Q.64 Let the
universe of discourse be the set of integers. Then consider the following
predicates:
Code: AC10
Subject: DISCRETE STRUCTURES
Identify from the following
expressions ones which are not well formed formulas, if any and determine the truth
value of the well-formed-formulas:
(i) 
(ii) 
(iii) 
(iv) 
(v) 
(9)
Ans:
(i) It is wff and not true for every x. P(x)
is true for all x whereas Q(x) is true only for x = 2, 3 and not for all x.
(ii)
It is not a wff because argument of R is
predicate and not a variable as per the definition.
(iii)
It is true because square of an integer
is always ³ 0 and there are y (= 2, 3) such that Q (y) is true.
(iv) It is false. Because there exists x = 3 and y =5 (there are
infinite many such examples) such that P(3) is true but R(3, 5) is not true.
(v)
"y $x R(y, x) is always true because square of an integer is an integer
so we can always find an x for every y such that R(y, x) is satisfied. However
"zQ(z) is not true. Since two statements are connected with Ú, it is TRUE.
Q.65 What is the
minimum number of students required in a class to be sure that at least 6 will
receive the same grade if there are five possible grades A, B,C, D and F? (4)
Ans: Let us consider 5 pigeonholes
corresponding to five grades. Then, our problem is to find the number of
pigeons (students) so that when placed in holes, one of the holes must contain
at least 6 pigeons (students). In the theorem above, m = 5, then we have to
find n such that
Therefore, at least 26 students are required in the
class.
Q.66 Let n be a positive integer.
Then prove that 
(4)
Ans: 
Code: AC10
Subject: DISCRETE STRUCTURES
Q.67 Suppose
E is the event that a randomly generated bit string of length 4 begins with a 1
and F is the event that this bit string contains an even number of 1’s. Are E
and F independent if the 16 bit strings of length 4 are equally likely? (6)
Ans: Number of 4 bit strings that begins with 1 is 8, thus P(E) = .5
Number of 4-bit
string having even number of 1’s is also 8 [C(4, 0) + C(4, 2) + C(4, 4)].
Therefore P(F) = .5
Now Number of
4-bit string that begins with 1 and contains even number of 1’s is 4 [1 + C(3,
0)]. Thus P(EÇF) = .25.
Clearly P(EÇF) = P(E)*P(F).
Thus E and F are independent.
Q.68 Find
the sum-of-products expression for following function,
(6)
Ans: The sum of the product expression
for the given function f is DNF (disjunctive normal form) expression.
The truth table for f is as below.
|
x
|
y
|
z
|
F(x, y, z) = y + z’
|
|
0
|
0
|
0
|
1
|
|
0
|
0
|
1
|
0
|
|
0
|
1
|
0
|
1
|
|
0
|
1
|
1
|
1
|
|
1
|
0
|
0
|
1
|
|
1
|
0
|
1
|
0
|
|
1
|
1
|
0
|
1
|
|
1
|
1
|
1
|
1
|
The required sum
of product (min term) notation is
F(x,
y, z) = x’y’z’ + x’yz’ + x’yz + xy’z’ + xyz’ + xyz
Q.69 Using other identities of
Boolean algebra prove the absorption law,
x + xy = x
Construct
an identity by taking the duals of the above identity and prove it too. (8)
Ans: We have to prove that x + xy = x.
x + xy = x (y +
y’) + xy
Code: AC10
Subject: DISCRETE STRUCTURES
= xy + xy’ + xy
= (xy + xy) +
xy’
= xy + xy’
= x (y + y’) =
x.1 = x
The dual of the
given identity is x(x+ y) = x. Now
x(x + y) = xx + xy
= x + xy
= x [From
above theorem]
Q.70 Define
grammar. Differentiate a context-free grammar from a regular grammar.
(6)
Ans: Any language is suitable for communication provided the syntax and
semantic of the language is known to the participating sides. It is made
possible by forcing a standard on the way to make sentences from words of that
language. This standard is forced through a set of rules. This set of rules is
called grammar of the language.
A
grammar G = (N, å, P, S) is said to be of Context Free if in every production a®b of P, a Î N and b Î (N È å)*. Here a is a single non-terminal symbol.
On
the other hand, in a regular grammar, every production a®b of P, a Î N and b Î (N È å)*. Here a is a single
non-terminal symbol and b may consist of at the most one non-terminal symbol and one or more
terminal symbols. The non-terminal symbol appearing in b must be the extreme right
(or left) symbol. This type of grammar is also called a right linear grammar
or regular grammar.
Q.71 Let L be a language over {0, 1}
such that each string starts with a 0 and ends with a minimum of two subsequent
1’s. Construct,
(i)
the regular expression to specify L.
(ii)
a finite state automata M, such that M (L) = L.
(iii)
a regular grammar G, such that G(L) = L. (8)
Ans:
(i)
The regular expression for the language is 0+(0Ú1) *11.
(ii)
The finite automata M is as below:
Code: AC10
Subject: DISCRETE STRUCTURES
(iii) Now the
regular grammar G is:
S ® 0A,
A ® 0A |1B,
B ® 1 | 1C | 0A,
C ®1C| 0A |e
Q.72 Define an
ordered rooted tree. Cite any two applications of the tree structure, also
illustrate using an example each the purpose of the usage. (7)
Ans: A tree is a graph such that
it is connected, it has no loop or circuit of any length and number of edges in
it is one less than the number of vertices.
If the downward slop of an arc is taken as the direction of the arc
then the above graph can be treated as a directed graph. In degree of node + is
zero and of all other nodes is one. There are nodes like 3, 4, 5, 2 and 5 with
out degree zero and all other nodes have out degree > 0. A node with in
degree zero in a tree is called root of the tree. Every tree
has one and only one root and that is why a directed tree is also called a rooted
tree. The position of every labeled node is fixed, any change in the
position of node will change the meaning of the expression represented by the
tree. Such type of tree is called ordered tree.
A tree structure is used in evaluation of an arithmetic expression
(parsing technique) The other general application is search tree. The tree
presented is an example of expression tree. An example of binary search tree is
shown below.
Code: AC10
Subject: DISCRETE STRUCTURES
Q.73 Determine the values of the
following prefix and postfix expressions. (
is exponentiation.)
(i)
+, -, , 3, 2, , 2, 3, /, 6, –, 4, 2
(ii)
9, 3, /, 5, +, 7, 2, -, *
(7)
&n
is
