JNTU
JNTU B.Tech II MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE Previous Question Paper (August/September - 2022 - R15)
Answer any five questions. All questions carry equal marks.
Main
Show that (p → r) ∧ (q → r) and (p ∨ q) → r are logically equivalent.
Answer
To show that (p → r) ∧ (q → r) is logically equivalent to (p ∨ q) → r, we use the logical equivalence p → q ≡ ¬p ∨ q:
Applying the distributive law:
By De Morgan's Law, (¬p ∧ ¬q) ≡ ¬(p ∨ q), therefore:
Using the implication rule again, this is equivalent to:
Thus, the two expressions are logically equivalent.
Show that (∃x)(P(x) ∧ Q(x)) ⇒ (∃x)P(x) ∧ (∃x)Q(x). Is the converse true?
Answer
To show (∃x)(P(x) ∧ Q(x)) ⇒ (∃x)P(x) ∧ (∃x)Q(x), assume the antecedent is true. There exists some element 'a' in the domain such that P(a) ∧ Q(a) is true. This implies P(a) is true and Q(a) is true. Since P(a) is true, there exists an x such that P(x) is true (∃xP(x)). Similarly, since Q(a) is true, there exists an x such that Q(x) is true (∃xQ(x)). Therefore, (∃x)P(x) ∧ (∃x)Q(x) must be true.
The converse, (∃x)P(x) ∧ (∃x)Q(x) ⇒ (∃x)(P(x) ∧ Q(x)), is not true. Consider a domain of integers where P(x) is 'x is even' and Q(x) is 'x is odd'. Then (∃x)P(x) is true (e.g., x=2) and (∃x)Q(x) is true (e.g., x=1). However, there is no integer x that is both even and odd, so (∃x)(P(x) ∧ Q(x)) is false.
Obtain the PDNF and PCNF of the following formula:
Answer
Sign in to view the complete answer paper.
Define the dual of a statement in a lattice L. Why does the principle apply to L?
Answer
Sign in to view the complete answer paper.
A function f:(Z × Z) → Z is defined as f(x,y) = 4x + 5y. Prove that f is onto, but not one-to-one.
Answer
Sign in to view the complete answer paper.
Given S = {1, 2, 3, ...., 10} and a relation R on S where R = { / x + y = 10}, what are the properties of the relation R? Explain.
Answer
Sign in to view the complete answer paper.
Define Semi-groups and Monoids. Give examples and properties of each.
Answer
Sign in to view the complete answer paper.
State and prove multinomial theorem. Determine the coefficient of x3y3z2 in the expansion of (2x – 3y + 5z)8.
Answer
Sign in to view the complete answer paper.
How many ways are there to seat 10 boys and 10 girls around a circular table, if boys and girls seat alternatively.
Answer
Sign in to view the complete answer paper.
There are 35 students and 04 teachers. In how many ways every student shakes hand with other students and all the teachers?
Answer
Sign in to view the complete answer paper.
Prove that in a group of six people at least three must be mutual friends or at least three must be mutual strangers.
Answer
Sign in to view the complete answer paper.
Solve the following recurrence relations: an - 5an-1 + 8an-2 - 4an-3 = n2n
Answer
Sign in to view the complete answer paper.
Solve the recurrence relation by using substitution method: an = an-1 + 1/(n(n+1)), a0 = 1
Answer
Sign in to view the complete answer paper.
Show that the complete graph K5 and complete bipartite graph K3,3 are not planar.
Answer
Sign in to view the complete answer paper.
Show that the following graphs are isomorphic.
Answer
Sign in to view the complete answer paper.