B.TECH - Semester 3 discrete structures Question Paper 2020 (feb)
Practice authentic previous year university questions for better exam preparation.
Sample Questions
- If the truth values of $p$ and $q$ are $T$ and those of $\gamma$ and $s$ are $F$, find the truth value of $(p \vee(q \rightarrow(r \wedge \neg p)) \mid \leftrightarrow(q \vee \neg s)$.
- Define tautology and contradiction. Give examples of each.
- Write an equivalent formula for $p \wedge(q \rightarrow \gamma) \vee(\gamma \leftrightarrow p)$ which does not contain the biconditional.
- Draw the logic network of $(a+b) \cdot(\bar{a}+\bar{b})$
- Show that $(x)(H(x) \rightarrow M(x)) \wedge H(s) \Rightarrow M(s)$.
- Define partition and covering of a set. Give examples.
- State Peano's axions.
- Define $f: I \rightarrow I$ by $f(j)=\frac{j / 2}{2}$ if $j$ is even if $j$ is odd check whether $f$ is a bijection.
- Define a group code. Show that the minimum weight of the non zero code words in a group code is equal to its minimum distance.
- If $v$ is a mode in a graph $G$, then define the in degree and out degree of $v$. PART - B Answer any one full questions from each Module.
- (a) Show that the following premises are inconsistent
- (i) If Jack misses many classes, then he fails high school. (ii) If Jack fails high school, then he is uneducated. (iii) If Jack reads a lot of books, then he is not uneducated. (iv) Jack misses many classes and reads a lot of books.
- (b) Show that $(x)(p(x) \vee q(x)) \Rightarrow(x) p(x) \vee(\exists x) q(x)$.
- (a) Prove that $(\exists x)(p(x) \wedge q(x)) \Rightarrow(\exists x) p(x) \wedge(\exists x) q(x)$. Does the converse hold.
- (b) Show that
- (i) $((p \vee \neg p) \rightarrow q) \rightarrow((p \vee \neg q) \rightarrow r) \Rightarrow q \rightarrow r$ (ii) $\square(p \leftrightarrow q) \Leftrightarrow(p \wedge \square q) \vee(\square p \wedge q)$.
- (a) Show by induction that $B \cup\left(\bigcap_{i=1}^{u} A_{i}\right)=\bigcap_{i=1}^{u}\left(B \cup A_{i}\right)$, where $A_{1}, A_{2} \ldots A_{u}, B$ are nonempty sets.
- (b) Define countable and uncountable sets. Show that an infinite subset of an uncountable set is uncountable.
- (a) Give the definitions of a bijection and inverse of a function. If $f: R \rightarrow R$ is defined by $f(x)=2 x^{3}-1$, then find $f^{-1}$.
- (b) Define equivalence relation on a set $A$. On $Z$ define $R=\{(a=b): a \equiv b(\bmod 2\}$. Show that $R$ is an equivalence relation on $A .10$
- (a) Define monoid and homomorphism between monoids. IF $f: S_{1} \rightarrow S_{2}$ is a homomorphism between two monoids $S_{1}$ and $S_{2}$ with identifies $e_{1}$ and $e_{2}$, then show that $f\left(e_{1}\right)=e_{2}$.
- (b) Let $G$ be a group. Show by mathematical induction that if $a b=b a$, then $(a b)^{u}=a^{u} b^{u}$ for $n \in N$.
- (a) If ( $L, \leq$ ) is a lattice then show that
- (i) $a \oplus(b * c) \leq(a \oplus b) *(a \oplus c)$ (ii) $a *(b \oplus c) \geq(a * b) \oplus(a * c)$.
- (b) Let $f: G \rightarrow H$ be a group homomorphism. Show that Kernel of $f$ is a normal subgroup of $G$.