B.TECH - Semester 3 discrete structures Question Paper 2020 (apr)
Practice authentic previous year university questions for better exam preparation.
Sample Questions
- Write the equivalent form of the propositional logic formula using $\neg$ and $v$ only $p \rightarrow(q \rightarrow r)$
- Prove that $p \vee \neg p$ is a tautology
- Define partially ordered set and equivalence relation with example
- If $A$ and $B$ are two sets, prove that $A \cup B=B \cup A$
- If $A$ and $B$ are two sets, prove that $A-B \neq B-A$.
- Given a set $A=\{1,2,3,4\}$ and a relation $R$ on $A$ is defined as $R=[(1,2),(2,3),(3,4),(4,1)\}$. Find the inverse of the relation $R$
- Define abelian group with example
- Define (a)Integral domain (b) Field
- What is a connected component of a graph. Draw a graph with 2 connected components
- Define a binary tree. Draw a complete binary tree with 7 vertices Answer any one full questions from each Module. Each question carries 20 marks.
- (a) Write the truth table for the statement by representing in propositional logic, " If a quadrilateral $A B C D$ is a square then all the sides of it are equal". Also write the converse, inverse and contra positive of the given statement with truth...
- (b) Show that
- (i) $p \rightarrow(q \vee r) \leftrightarrow(p \rightarrow q) v(p \rightarrow r)$ (ii) $\neg(p \rightarrow q) \leftrightarrow p \wedge \neg q$
- (a) Symbolize the following statement using predicate logic "All world loves a lover"
- (b) Verify the validity of the following argument." Every living thing is a planet or an animal. John's gold fish is alive and is not a planet. All animals have hearts. Therefore John's gold fish has a heart".
- (a) Give a relation which is both symmetric and antisymmetric on set $A=\{1,2,3,4\}$.
- (b) Let set $A=\{1,2,3,4\}$ and let $R$ be an equivalence relation on $A$ partitions $A$ into $\{1,2\},\{3\},\{4)$. Find the relation $R$.
- (c) Let set $A=\{1,2,3,4\}$, draw the graph representing the relation $R$ on $A$ defined by $R=(1,2),(1,1),(23)(3,2),(3,3),(4,3),(4,1)\}$.
- (d) Let set $A=\{1,2,3,4\}$ and $R$ is a relation on $A$ defined by $R=\{(1,1),(2,2),(1,2),(2,1)$. Find the properties of the relation. Is it an equivalence relation? OR
- (a) Let the sets $A$ and $B$ defined as $A=\{1,2)$ and $B=\{7,8,9\}$ and a relation $f$ is defined from $A$ to $B$ as $f=\{(1,7),(2,8),(1,9)\}$. Is $f$ a function? Justify your answer.
- (b) Let $N$ be the set of natural numbers and $f$ is a function from $N$ to $N$ defined by $f(x)=3 x+7$. Check whether the function is bijective.
- (c) Prove by mathematical induction $1+2+3+\ldots+n=n(n+1) / 2$.
- (a) Let G be the set of rational numbers excluding 1 and define *on $G$ as $a{ }^{*} b=a+b-a b$ for all $a, b \in c$. Show that ( $G,{ }^{*}$ ) is a group. Check whether it is an abelian group. 10
- (b) Prove that intersection of subgroups of a group $G$ is a subgroup of $G$. 10
- (a) State and prove Lagranges Theorem on subgroups 10
- (b) Define a ring with example 10
- Draw the Hasse diagram for the partial ordering "divides" on the set $D_{100}=\{1,2,4,5,10,20,25,50,100\}$. Check whether it is a lattice. Justify. If it is a lattice find its sub lattices.
- (a) Draw a complete graph with $2,3,4$, and 5 verices.
- (b) What are the various representation of graphs? Explain with examples