JNTU
JNTU B.Tech II DISCRETE MATHEMATICS Previous Question Paper (March - 2022 - R18)
Answer any five questions. All questions carry equal marks.
Main
Obtain the PDNF and PCNF of the following statement formula: (¬P ∨ ¬Q) → (P ↔ Q).
Answer
To find the Principal Disjunctive Normal Form (PDNF) and Principal Conjunctive Normal Form (PCNF) of the statement formula (¬P ∨ ¬Q) → (P ↔ Q), we first simplify the expression using logical equivalences.
Let the formula be A = (¬P ∨ ¬Q) → (P ↔ Q). Using the implication law (X → Y ≡ ¬X ∨ Y), we get:
Applying De Morgan's Law to the first part and the biconditional definition to the second:
Expanding the second part using the distributive law:
PDNF: The minterms present are (P ∧ Q) and (¬P ∧ ¬Q). Thus, the PDNF is:
PCNF: The PCNF is the product of maxterms not present in the PDNF. The missing combinations are (P ∧ ¬Q) and (¬P ∧ Q). Converting these to maxterms (P ∨ ¬Q) and (¬P ∨ Q), the PCNF is:
Show that (∃x) (P(x) ∧ Q(x)) ⇒ (∃x) (P(x) ∧ ∃x Q(x)).
Answer
To show that (∃x)(P(x) ∧ Q(x)) ⇒ (∃x)P(x) ∧ (∃x)Q(x), we assume the antecedent is true. If (∃x)(P(x) ∧ Q(x)) is true, there exists at least one element, say 'a', in the domain such that P(a) ∧ Q(a) is true.
From the definition of conjunction, this implies P(a) is true and Q(a) is true. Since P(a) is true, by the rule of existential generalization, (∃x)P(x) must be true. Similarly, since Q(a) is true, (∃x)Q(x) must be true.
Since both (∃x)P(x) and (∃x)Q(x) are true, their conjunction (∃x)P(x) ∧ (∃x)Q(x) is true. Thus, the implication holds.
Symbolize the following argument and check for its validity: All men are giants. Not all birds can fly. Some babies are illogical. There is a student who likes maths, but not history.
Answer
Sign in to view the complete answer paper.
Use a Venn diagram to illustrate the relationships A ⊂ B and A ⊂ C.
Answer
Sign in to view the complete answer paper.
Prove that the relation “congruence modulo m” given by R={<x,y> / x-y is divisible by m} over the set of positive integers is an equivalence relation.
Answer
Sign in to view the complete answer paper.
Give the definition and examples of reflexive, symmetric, anti-symmetric and transitive relations.
Answer
Sign in to view the complete answer paper.
What is meant by Poset? Draw the Hasse diagram for the Poset <{2,4,5,10,12,20,25},|> and compute LUB and GLB.
Answer
Sign in to view the complete answer paper.
Conjecture a formula for the sum of the first n positive odd integers. Then prove your conjecture using mathematical induction.
Answer
Sign in to view the complete answer paper.
Express the linear search algorithm as a recursive procedure and explain.
Answer
Sign in to view the complete answer paper.
Prove that 2 divides n2+n whenever n is a positive integer, using mathematical induction.
Answer
Sign in to view the complete answer paper.
Give a recursive algorithm to compute the factorial of a number and explain.
Answer
Sign in to view the complete answer paper.
Solve the recurrence relation an - 7an-1 + 10an-2 = 0 where a0=10 and a1= 41.
Answer
Sign in to view the complete answer paper.
Find the degree sequence of K4 graph.
Answer
Sign in to view the complete answer paper.
What are the various ways of representing graphs? Explain them briefly with relevant examples.
Answer
Sign in to view the complete answer paper.