JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II DISCRETE STRUCTURES Previous Question Paper (April/May - 2023 - R18)
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
What is substitution instance of a formula? Explain with an example.
Answer
A substitution instance of a formula is a new formula obtained by replacing every occurrence of one or more propositional variables in the original formula with other formulas. Each occurrence of a specific variable must be replaced by the same formula throughout the expression.
For example, consider the formula
Write about Rule P, T and CP with one example for each.
Answer
These rules are fundamental principles used in propositional logic to derive conclusions from premises.
- Rule P (Premise Rule): Any premise can be introduced at any step of a derivation.
Example: Given P as a premise, we can write P in our proof sequence. - Rule T (Implication Rule): A formula S can be introduced in a derivation if S is logically equivalent to a formula already derived or if S follows from previous formulas by the rules of inference.
Example: If we have P and P → Q, we can introduce Q using Modus Ponens. - Rule CP (Conditional Proof): If a conclusion of the form P → Q is to be proved, one can assume P as an additional premise and derive Q. Once Q is reached, the implication P → Q is established.
Example: To prove P → (Q → R), assume P, then assume Q, derive R, and conclude P → (Q → R) by CP.
Define Cardinality of Set. Give example.
Answer
Sign in to view the complete answer paper.
Represent the relation A = {(1, 1), (1, 3), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (4, 1)} on the set {1, 2, 3, 4} using graph? Use this digraph to determine whether R is reflexive, symmetric, and transitive?
Answer
Sign in to view the complete answer paper.
What is Structural Induction and well-ordering?
Answer
Sign in to view the complete answer paper.
Use Mathematical induction to prove n(n2 +5) is an integer multiple of 6?
Answer
Sign in to view the complete answer paper.
Where is the need of Inclusion –Exclusion? Give one application?
Answer
Sign in to view the complete answer paper.
How many 6-digit numbers without repetition of digits are there such that the digits are all nonzero and 1 and 2 do not appear consecutively in either order?
Answer
Sign in to view the complete answer paper.
What is unilaterally connected in a digraph? Give one example.
Answer
Sign in to view the complete answer paper.
Write about various Graph representations.
Answer
Sign in to view the complete answer paper.
Part B
Show that ￢(P∨(￢P∧Q)) and ￢P∧￢Q are logically equivalent by developing a series of logical equivalences.
Answer
Sign in to view the complete answer paper.
Translate the statement “Everyone has exactly one best friend.” Into a logical expression using nested quantifiers with and without a domain consisting of all people, and logical connectives.
Answer
Sign in to view the complete answer paper.
Write about Quantifiers. Explain nested quantifiers with suitable examples.
Answer
Sign in to view the complete answer paper.
Prove the given Tautological Implication ((P→Q)∧(Q→R))⇒(P→R).
Answer
Sign in to view the complete answer paper.
Prove that A - (A - B) = A ∩ B. And Draw Venn diagram of both formulas.
Answer
Sign in to view the complete answer paper.
Define Partial Ordering relation. Draw the Hasse diagram for the partial ordering {(A, B)| A⊆B} on the Power set P(S) where S= {a, b, c, d}?
Answer
Sign in to view the complete answer paper.
Define One-One function. Give one example.
Answer
Sign in to view the complete answer paper.
Define Equivalence Relation. Prove that the Relation R ≤ in the set of Natural Numbers N is an Equivalence Relation. Compute N/R.
Answer
Sign in to view the complete answer paper.
Show that the set N of Natural numbers is a Semigroup under the operation x * y= max {x , y}. Is it a Monoid?
Answer
Sign in to view the complete answer paper.
What are abelian groups? Explain.
Answer
Sign in to view the complete answer paper.
Write a Recursive Algorithm for finding the Factorial of a given number.
Answer
Sign in to view the complete answer paper.
Define Lattice. Write its properties.
Answer
Sign in to view the complete answer paper.
How many different bit strings are there of length 7?
Answer
Sign in to view the complete answer paper.
Solve the recurrence relation an2 – 2an-12=0 for n>=1, where a0 =2?
Answer
Sign in to view the complete answer paper.
How many 9-letter Palindromes are possible using the English alphabet?
Answer
Sign in to view the complete answer paper.
Solve the Recurrence Relation an - 9an-1 + 26an-2 - 24an-3 = 0 for n≥3 using Generating Functions?
Answer
Sign in to view the complete answer paper.
Show that if G is a polyhedral graph, then there is a region of degree <=5.
Answer
Sign in to view the complete answer paper.
State Euler's theorem. Prove it.
Answer
Sign in to view the complete answer paper.
Prove that Every simple planar graph is 5-colorable.
Answer
Sign in to view the complete answer paper.
Draw a corresponding binary tree for the expression [((7 - 5)*2) ÷ 2] + (6×(9 ÷ 3)).
Answer
Sign in to view the complete answer paper.