JNTU
JNTU MCA I MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE Previous Question Paper (March - 2023 - R15)
Note: i) Question paper consists of Part A, Part B. ii) Part A is compulsory, which carries 25 marks. In Part A, Answer all questions. iii) In Part B, Answer any one question from each unit. Each question carries 10 marks and may have a, b as sub questions.
Part A
List the various rules of inference in propositional logic.
Answer
The rules of inference in propositional logic are logical forms consisting of a set of premises and a conclusion. The primary rules include:
- Modus Ponens: p → q, p ⊢ q
- Modus Tollens: p → q, ¬q ⊢ ¬p
- Hypothetical Syllogism: p → q, q → r ⊢ p → r
- Disjunctive Syllogism: p ∨ q, ¬p ⊢ q
- Addition: p ⊢ p ∨ q
- Simplification: p ∧ q ⊢ p
- Conjunction: p, q ⊢ p ∧ q
- Resolution: p ∨ q, ¬p ∨ r ⊢ q ∨ r
Find the smallest relation containing the relation {(1,2), (1,4), (3,3), (4,1)} that is reflexive, symmetric and transitive.
Answer
Given the relation R = {(1,2), (1,4), (3,3), (4,1)} on set A = {1, 2, 3, 4}, we find the smallest equivalence relation (reflexive, symmetric, transitive closure):
- Reflexive: Add (1,1), (2,2), (3,3), (4,4).
- Symmetric: Add (2,1) since (1,2) exists, and (1,4) already has (4,1).
- Transitive: Since (1,2) and (2,1) exist, add (1,1) and (2,2). Since (4,1) and (1,2) exist, add (4,2). Since (2,1) and (1,4) exist, add (2,4).
The resulting equivalence relation is {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (1,4), (4,1), (2,4), (4,2)}.
Explain sum rule using an example.
Answer
Sign in to view the complete answer paper.
Write a generating function for 𝑎r when 𝑎r is the number of ways of selecting r balls from 3 red balls, 5 blue balls, 7 white balls.
Answer
Sign in to view the complete answer paper.
Define the following: complete graph, simple graph, multi graph, cycle graph, and path graph.
Answer
Sign in to view the complete answer paper.
Part B
Use the laws of logical equivalences to verify the following logical equivalence: (p ∧ (¬(¬p ∨ q))) ∨ (p ∧ q) ≡ p
Answer
Sign in to view the complete answer paper.
Show that s ⇒ (¬Q ∧ (P → Q)) → ¬P.
Answer
Sign in to view the complete answer paper.
Convert each of the following sentences to a sentence in predicate logic:
i) There are at least two mountains in England.
ii) There is exactly one coin in the box.
iii) The largest coin in the box is a quarter.
iv) No mountain is higher than itself.
v) All students get good grades if they study.
Answer
Sign in to view the complete answer paper.
Show that the premises “A student in this class has not read the book,” and “Everyone in this class passed the first exam” imply the conclusion “Someone who passed the first exam has not read the book.”
Answer
Sign in to view the complete answer paper.
What are the sets in the partition of the integers arising from congruence modulo 4?
Answer
Sign in to view the complete answer paper.
Determine whether the posets with the Hasse diagram shown below is a lattice or not.
Answer
Sign in to view the complete answer paper.
Find the inverse of the function f(x) = x³ + 1.
Answer
Sign in to view the complete answer paper.
Find f ∘ g and g ∘ f, where f(x) = x² + 1 and g(x) = x + 2, are functions from R to R.
Answer
Sign in to view the complete answer paper.
Find all the subgroups of S4 generated by the permutations:
Answer
Sign in to view the complete answer paper.
How many different number plates for cars can be made if each number plate contains two letters (A-Z) followed by five digits (0-9)?
Answer
Sign in to view the complete answer paper.
A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes socks out at random in the dark. How many socks must be taken out to be sure that he has at least two socks of the same color?
Answer
Sign in to view the complete answer paper.
How many bit strings contain exactly eight 0s and ten 1s if every 0 must be immediately followed by two 1s?
Answer
Sign in to view the complete answer paper.
What is the coefficients of x¹²y¹³ in the expansion of (2x - 3y)²⁵?
Answer
Sign in to view the complete answer paper.
State binomial theorem and find the expansion of (x + y)⁵.
Answer
Sign in to view the complete answer paper.
Calculate the coefficient of X¹⁵ in A(X) = (X² + X³ + X⁴ + X⁵)(X + X² + X³ + X⁴ + X⁵ + X⁶ + X⁷)(1 + X + ... + X¹⁵).
Answer
Sign in to view the complete answer paper.
Find a recurrence relation for the number of ways to make a pile of n chips using garnet, gold, red, white and blue chips such that no two gold chips are together.
Answer
Sign in to view the complete answer paper.
Solve the recurrence relation an = an-1 + n where a₀ = 2 using substitution.
Answer
Sign in to view the complete answer paper.
Determine whether following graphs are isomorphic or not and justify your answer:
Answer
Sign in to view the complete answer paper.
What do you mean by a subgraph and complement of a graph? Determine the complement of the following graph:
Answer
Sign in to view the complete answer paper.
Find a minimal spanning tree for the following graph:
Answer
Sign in to view the complete answer paper.
Draw all distinct binary trees with 4 vertices.
Answer
Sign in to view the complete answer paper.