BE Computer Engineering (IOE, TU) Discrete Structure (IOE, CT 551) Question Paper 2078

(a) Define a relation $R$ on a set $A$. State the conditions for $R$ to be (i) reflexive, (ii) symmetric, (iii) anti-symmetric and (iv) transitive. Let $A = \{1, 2, 3, 4\}$ and $R = \{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}$. Determine whether $R$ is an equivalence relation, and if so, find the corresponding partition of $A$. (6)

(b) For arbitrary sets $A$, $B$ and $C$, prove the distributive law $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ using the definition of set membership. Verify the same result using a Venn diagram. (6)

(a) Without using truth tables, show that the compound proposition $(p \rightarrow q) \wedge (p \rightarrow r)$ is logically equivalent to $p \rightarrow (q \wedge r)$. State the laws of logic used at each step. (6)

(b) Define a tautology and a contradiction. Translate the following statement into a logical expression using quantifiers and hence write its negation in words: "Every student in the class has solved at least one problem." Use appropriate predicates and clearly state the universe of discourse. (6)

(a) Solve the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$ for $n \ge 2$, with the initial conditions $a_0 = 1$ and $a_1 = 0$, using the characteristic-equation method. (6)

(b) Find the particular and general solution of the non-homogeneous recurrence relation $a_n - 3a_{n-1} = 2^n$, $n \ge 1$, given $a_0 = 1$. (6)

(a) Define an Euler circuit and a Hamiltonian circuit in a graph. State and justify the necessary and sufficient condition for a connected graph to possess an Euler circuit. Determine, with reasoning, whether the complete graph $K_5$ has an Euler circuit. (6)

(b) Define the chromatic number of a graph. Find the chromatic number of the complete bipartite graph $K_{3,3}$ and justify your answer. (4)

Define injective, surjective and bijective functions. For the function $f: \mathbb{R} \rightarrow \mathbb{R}$ defined by $f(x) = 3x - 5$, prove that $f$ is a bijection and find its inverse function $f^{-1}$.

Using the principle of mathematical induction, prove that for every positive integer $n$:

(a) State the Pigeonhole Principle. Show that among any 13 people, at least two of them are born in the same month. (3)

(b) In how many ways can a committee of 3 men and 2 women be formed from a group of 7 men and 5 women? (3)

(a) Find the coefficient of $x^5 y^3$ in the expansion of $(2x - y)^8$ using the Binomial Theorem. (3)

(b) How many distinct arrangements can be made from the letters of the word "MISSISSIPPI"? (3)

Define a spanning tree and a minimum spanning tree of a weighted connected graph. Using Kruskal's algorithm, find a minimum spanning tree and its total weight for the graph with the following edge weights: $AB=4,\ AC=3,\ BC=2,\ BD=5,\ CD=6,\ CE=4,\ DE=1$. Show the order in which edges are selected.

State the basic postulates of Boolean algebra. Using Boolean algebra laws, simplify the expression $F = x'y'z + x'yz + xy'$ and draw the logic circuit for the simplified expression.

(a) Define the adjacency matrix of a graph. Write the adjacency matrix for a simple undirected graph $G$ with vertices $\{v_1, v_2, v_3, v_4\}$ and edges $\{v_1v_2, v_2v_3, v_3v_4, v_4v_1, v_1v_3\}$. (3)

(b) State the conditions under which two graphs are said to be isomorphic. (3)

Define a partially ordered set (poset). Draw the Hasse diagram for the poset $(D_{12}, \mid)$, where $D_{12}$ is the set of all positive divisors of 12 and $\mid$ denotes the "divides" relation.