JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B. Tech II Year DISCRETE STRUCTURES Previous Question Paper (August/September - 2022 - R18)
Answer any five questions. All questions carry equal marks.
Main
Give a direct proof, an indirect proof, and proof by contradiction for, “If n is an odd integer, then (n + 9) is an even integer”.
Answer
Direct Proof: Assume n is an odd integer. By definition, n = 2k + 1 for some integer k. Then n + 9 = (2k + 1) + 9 = 2k + 10 = 2(k + 5). Since k + 5 is an integer, n + 9 is even.
Indirect Proof (Contrapositive): The contrapositive is: If n + 9 is odd, then n is even. Assume n + 9 is odd, so n + 9 = 2k + 1 for some integer k. Then n = 2k + 1 - 9 = 2k - 8 = 2(k - 4). Since k - 4 is an integer, n is even.
Proof by Contradiction: Assume n is odd and n + 9 is odd. If n = 2k + 1, then n + 9 = 2k + 10 = 2(k + 5), which is even. This contradicts the assumption that n + 9 is odd. Therefore, if n is odd, n + 9 must be even.
Show the following statement is a tautology:
Answer
To show that ¬P ∧ (¬P ∧ Q) → ¬Q is a tautology, we construct a truth table:
| P | Q | ¬P | ¬Q | (¬P ∧ Q) | ¬P ∧ (¬P ∧ Q) | ¬P ∧ (¬P ∧ Q) → ¬Q |
|---|---|---|---|---|---|---|
| T | T | F | F | F | F | T |
| T | F | F | T | F | F | T |
| F | T | T | F | T | T | F |
| F | F | T | T | F | F | T |
Wait, evaluating the expression ¬P ∧ (¬P ∧ Q) → ¬Q: The expression simplifies to (¬P ∧ Q) → ¬Q, which is equivalent to ¬(¬P ∧ Q) ∨ ¬Q = (P ∨ ¬Q) ∨ ¬Q = P ∨ ¬Q. This is not a tautology as it is false when P is false and Q is true. Re-evaluating the logic: The expression ¬P ∧ (¬P ∧ Q) simplifies to (¬P ∧ Q). Thus, the statement is (¬P ∧ Q) → ¬Q. This is equivalent to ¬(¬P ∧ Q) ∨ ¬Q = (P ∨ ¬Q) ∨ ¬Q = P ∨ ¬Q, which is only a tautology if the original expression was intended as (¬P ∧ (P ∨ Q)) → ¬Q or similar. Based on the provided formula, it is not a tautology.
Let X = {1, 2, 3, 4, 5, 6, 7} and R = {(x, y) | x - y is divisible by 3} in X. Show that R is an equivalence relation.
Answer
Sign in to view the complete answer paper.
Let the function f: N → N and g: Z → N be defined as f(x) = 3x + 2 and g(x) = x2 + 1. Specify the functions: i) f-1, ii) g-1, iii) f ∘ g, iv) g ∘ f. If they exist, give a valid argument if one/some of them do not exist.
Answer
Sign in to view the complete answer paper.
Check whether proposition ∼ A ↔ B ∧ C ∨ ∼ A → B is well-formed, providing step-by-step tracing of the algorithm.
Answer
Sign in to view the complete answer paper.
Explain the method of determining the complexity of a procedure by the step count approach. Illustrate with an example.
Answer
Sign in to view the complete answer paper.
Explain the principle of strong induction with example.
Answer
Sign in to view the complete answer paper.
Using induction principles prove that n3 + 2n is divisible by 3.
Answer
Sign in to view the complete answer paper.
Find the general solution for the recurrence relation T(n) - T(n - 1) = 4(n + n3), where n ≥ 1 and T(0) = 5.
Answer
Sign in to view the complete answer paper.
Find a general expression un using generating functions for un - 7un-1 + 16un-2 - 12un-3 = 0, n ≥ 3.
Answer
Sign in to view the complete answer paper.
How many solutions does x1 + x2 + x3 = 11 have, where x1, x2, and x3 are nonnegative integers with x1 ≤ 3, x2 ≤ 4, and x3 ≤ 6?
Answer
Sign in to view the complete answer paper.
How many bits of string of length 10 contain: i) Exactly four 1's, ii) At most four 1's, iii) At least four 1's, iv) An equal number of 0's and 1's.
Answer
Sign in to view the complete answer paper.
Define Graph. Given the adjacency matrix, i) Draw the Graph, ii) Determine if G is a tree, iii) Determine if G is an Eulerian graph, iv) Determine if G is a Hamiltonian graph.
Answer
Sign in to view the complete answer paper.
Define Planar Graph. Explain about the graph coloring with example.
Answer
Sign in to view the complete answer paper.
List and explain Tree Traversal techniques with an example.
Answer
Sign in to view the complete answer paper.
Show, step by step Kruskal's algorithm on the following connected weighted graph and also calculate sum of the weights of the minimal spanning tree.
Answer
Sign in to view the complete answer paper.