Mathematical Foundations Of Computing Pdf
Code 9A05301
1
II B.Tech I semester (R09) Regular Examinations, November 2010 MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
(Computer Science & Systems Engineering, Information Technology, Computer Science & Engineering)
Time: 3 hours Max Marks: 70 Answer any FIVE questions All questions carry equal marks
1. (a) Explain about different types of statement connectives. (b) Show that
¬
P
∧
(
¬
Q
∧
R
))
∨
(Q
∧
R
)
∨
(P
∧
R
)
⇔
R
without constructing truth table. 2. (a) Show that
R
∧
(
P
∨
Q
) is a valid conclusion from the premises
P
∨
Q,Q
→
R,P
→
M
and
¬
M
. (b) Explain about free and bond variables for predicate calculus. 3. (a) Explain about the properties of a Binary relation in a set with suitable examples. (b) Define a lattice . Let(
L,
≤
) be lattice in which * and
⊕
denote the operations of meet and join respectively. For any
a,b
∈
L
, show that
a
≤
b
⇔
a
∗
b
=
a
⇔
a
⊕
b
=
b
. 4. (a) Define and give examples for semigroups and monaids. (b) Explain about the general properties of algebraic systems. 5. (a) How many 10 - digit binary numbers are there with exactly six 1's? (b) How many integral solutions are there to
x
1
+
x
2
+
x
3
+
x
4
+
x
5
= 20 where each
x
i
≥
2 ? (c) From a group of 10 professors how many ways can a committee of 5 members be formed so that atleast one of the professor A and professor B will be included? 6. Solve the recurrence relation
a
n
=
c.a
n
−
1
+
f
(
n
) for
n
≥
1 , where C is a constant, by substi- tution. 7. What is a spanning tree? Explain any two ways for finding out spanning tree of a given graph with examples. 8. Define isomorphism of graphs. Prove that the following graphs are isomorphic.
Code 9A05301
2
II B.Tech I semester (R09) Regular Examinations, November 2010 MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
(Computer Science & Systems Engineering, Information Technology, Computer Science & Engineering)
Time: 3 hours Max Marks: 70 Answer any FIVE questions All questions carry equal marks
1. (a) What is a principle disjunctive normal form? Obtain the principle disjunctive form of
P
→
((
P
→
Q
)
∧¬
(
¬
Q
∨¬
P
)) (b) Show that (((
P
∨¬
Q
)
→
R
↔
S
)
∨¬
(((
P
∨¬
Q
)
→
R
)
↔
S
) is a tautology. 2. (a) Explain the concept of tree and bound variables for predicate calculus. (b) Show that(
x
)(
P
(
x
)
→
Q
(
x
)))
∧
(
x
)(
Q
(
x
)
→
R
(
x
))
⇒
(
x
)(
P
(
x
)
→
R
(
x
)). 3. (a) What is an equivalence relation? Give an example. And prove that it is equivalence relation. (b) Define a partial order relation. Let A be a given finite set and P(A) its power set. Let
⊆
be the inclusion relation on the elements of P(A). Draw Hasse diagrams of
P
(
A
)
,
⊆
for (i) A =
{
a, b
}
(ii) A =
{
a, b, c, d
}
4. (a) Write about general properties of an algebraic system. (b) Explain about homomorphism of subgroups. 5. (a) How many ways can we get a sum of 4 or of 8 when two distinguishable dice are rolled? How many ways can we get an even sum? (b) State and prove the binomial theorem. 6. Solve
a
n
−
6
a
n
−
1
+ 12
a
n
−
2
−
8
a
n
−
3
= 0 by generating functions. 7. (a) Explain about different representations for graphs. (b) Explain about DFS and BFS methods. 8. (a) Explain about multigraphs and Euler circuits with examples. (b) What is a chromatic number? Find the Chromatic number for the following graph.
Code 9A05301
3
II B.Tech I semester (R09) Regular Examinations, November 2010 MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
(Computer Science & Systems Engineering, Information Technology, Computer Science & Engineering)
Time: 3 hours Max Marks: 70 Answer any FIVE questions All questions carry equal marks
1. (a) Explain different types of connectives for the statements with their truth tables. (b) Show that
P
→
(
Q
→
P
)
⇔ ¬
P
→
(
P
→
Q
) . 2. (a) Explain the concept of free and bound variables and rules of inference for predicate cal- culus. (b) Show that (
x
)(
P
(
x
)
→
Q
(
x
))
∧
(
x
)(
Q
(
x
)
→
R
(
x
))
⇒
(
x
)(
P
(
x
)
→
R
(
x
)) . 3. (a) What is a partial order relation? Let X =
{
2, 3, 6, 12, 24, 36
}
and the relation
≤
be such that
x
≤
y
if x divides y. Draw the Hasse diagram of
x,
≤
. (b) What is an equivalence relation? Give an example for equivalence relation and prove that it is an equivalence relation. 4. (a) Define a semigroup and monoid. Let S be a non empty set and P(s) be its power set. Prove that the algebras
P
(
s
)
,
∪
and
P
(
s
)
,
∩
are monoids. (b) Explain the concepts of homomorphism and isomorphism of groups with examples. 5. (a) What is pigeon hole principle? Explain any two of its applications. (b) How many two digits or three digits numbers can be formed by using the digits 1, 3, 4, 5, 6, 8 and 9 if no repetitions are allowed? (c) How many numbers can be formed using the digits 1, 3, 4, 5, 6, 8 and 9 if no repetitions are allowed? 6. Solve the recurrence relation
a
n
=
c.a
n
−
1
+
f
(
n
) , where C is a constant, by substitution method. Find a solution for Towers of Hanoi problem using recurrence relation. 7. Explain any two methods for finding out the spanning tree of a given graph with suitable examples. 8. Explain about multigraphs and Euler circuits.
Mathematical Foundations Of Computing Pdf
Source: https://id.scribd.com/document/44150721/9a05301-Mathematic-Foundations-of-Computer-Science
Posted by: andersonvearguat.blogspot.com
0 Response to "Mathematical Foundations Of Computing Pdf"
Post a Comment