JNTU B.Tech II MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE Previous Question Paper (April/May - 2023 - R16)

State De-Morgan’s law.

Prove that ¬(P ˅ Q) ≡ (¬P ˄ ¬Q) .

Draw the Venn diagrams for (A∩B) ∪ (C∩D) of the sets A, B, C, and D.

Draw the Hasse diagram for the Poset <{2,4,5,10,12,20,25}, / >.

Define conditional probability.

What are the applications of the principle of inclusion and exclusion?

Define the term generating functions.

Find the generating function for the sequence 1, 3, 5, 7, 9, ….

What is a planar graph?

Write down the properties of binary trees.

Show that P→S can be derived from the premises ┐P ∨ Q, ┐Q ∨ R, R → S, using rules of inference.

Determine whether or not the following arguments are valid: If a baby is hungry, then the baby cries. If the baby is not mad, then he does not cry. If a baby is mad, then he has a red face. Therefore, if a baby is hungry, then he has a red face.

Find the PDNF and PCNF by constructing the truth table: (P ˄ Q) ˅ (¬P ˄ R) ˅ (Q ˄ R)

Write a brief note on universal quantifiers.

Let Z be the set of integers and Let R be the relation called “congruence modulo 3” defined by R= {<x, y> / x ∈ Z ˄ y ∈ Z ˄ (x-y) is divisible by 3}. Determine the equivalence classes generated by the elements of Z.

Let f1(x) = x+ 4, f2(x) = x – 4, and f3(x) = 4x for x ϵ R, where R is the set of real numbers. Find f o g and g o f.

Let <S1, *1> and <S2, *2> be semi groups on the Cartesian product S1 x S2. Let the operation *3 be defined by (a, b) *3 (c, d) = (a*1 c, b *2 d) for all (a, b) , (c, d) S1 x S2. Prove that < S1 x S2, *3> is a semi group.

Let R ={ (b,c), (b,e), (c,e), (d,a), (c,b), (e,c)} be a relation on the set A ={ a,b,c,d,e}. Find the transitive closure of the relation R.

How many permutations can be made with letters of the word ENGINEERING?

There are 7 men and 3 women. Find the number of ways in which a committee of 6 persons can be formed if the committee is to have (i) exactly 4 men, and (ii) at least 2 women.

What is the probability that a positive integer selected at random from the set of positive integers not exceeding 100 is divisible by either 2 or 5?

State and explain Baye’s theorem with an example.

Solve the recurrence relation an – 7an-1 + 10an-2 = 0 where a0=10 and a1= 41.

Find a generating function for the recurrence relation cn = 3cn-1 – 2cn-2 for n≥2 given c1 = 5, c2 = 3.

Use generating functions to find the number of k-combinations of a set with n elements. Assume that the binomial theorem has already been established.

Find a generating function for the recurrence relation an+1–an = n^2 for n≥0 where a0=1.

What is a graph? Write about various ways of representing graphs.

How to determine whether two graphs are isomorphic or not? Explain briefly.