RGU Question Paper Mathematics Semester VI 2020: Discrete Mathematics

 

2 0 2 0

BA/BSc (VI Semester) Examination

MATHEMATICS

Paper : MATH–363 (New Course)

( Discrete Mathematics )

Full Marks : 80

Pass Marks : 35%

Time : Three Hours

Note : 1. Answer all questions.
2. The figures in the margin indicate full marks for the questions.

1. Answer the following questions (any five) : 2×5=10

(a) What do you understand by ‘relation’ on sets? Give an example of relation.

(b) Define lattice with an example.

(c) What is modular lattice? Show that every distributive lattice is modular.

(d) Write a short note on distributive lattice.

(e) Briefly describe a logic gate.

(f) Show that $a+b=a$, where $a$ and $b$ are Boolean variables.

(g) How do you distinguish between a propositional logic and a predicate logic?

(h) Define linearly ordered set with an example.

2. Answer the following questions (any four) : 5×4=20

(a) Define poset with an example.

(b) Let L be any lattice. Then show that $a\vee (b\vee c)=(a\vee b)\vee c$, for all $a,b,c\in L$.

(c) Briefly describe the representation of the graphs of relations. Draw the directed graph that represents the relation
$R=\left\{\right(1,1), (2,2),(1,2),(2,3),(3,2),(3,1),(3,3\left)\right\}$
on $X=\{1,2,3\}$.

(d) Write a short note on the principles of counting theory with examples.

(e) Out of 7 consonants and 4 vowels, how many words of 3 consonants and 2 vowels can be formed?

(f) Discuss Pigeonhole principle with a suitable example.

(g) Construct truth tables for the following :
(i) $p\vee \sim q\to p$
(ii) $[\sim (p\vee q)\vee r]\to \sim p$

(h) Use truth table to show that $p\to q=\sim p\vee q$. What are truth tables?

(i) Define the complemented lattice. Is the complement of any element
unique? Supportive example should be given.

3. Answer the following questions (any five) : 10×5=50

(a) (i) Show that in a lattice L, $a\wedge (b\wedge c)=(a\wedge b)\wedge c \forall a,b,c\in L$ 4

(ii) In any lattice, show that the statements
$a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$and $a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$
are equivalent for all $a,b,c\in L$. 3+3=6

(b) (i) Show that every chain is distributive lattice. 5
(ii) Prove that pentagonal lattice is not modular. 5

(c) (i) Show that in a distributive lattice (L, £), $(L,\le ), a\wedge b=a\wedge c$ and $a\vee b=a\vee c$ imply that $b=c$. 6
(ii) Write a short note on compound propositions. 4

(d) What is Boolean algebra? Let the operations $(+), (·)$ and $(\text{'})$ in $D_6=\{1,2,3,6\}$ be defined by
$a+b=lcm(a,b), a·b=gcd(a,b), a\text{'}=6/a$.
Show that $(D_6,+,·,\text{'},1,6)$ is a Boolean algebra. 10

(e) Prove that in a Boolean algebra B for all $a\in B$
(i) $a+a=a$
(ii) $a+1=1$
(iii) $a·a=a$
(iv) $a·0=0$
(v) $a+(a·b)=a$ 2+2+2+2+2=10

(f) (i) Show that there are $2^n$ minimal Boolean functions in $n$ variables. 5
(ii) Express $xy\text{'}+xz+x\text{'}y$ in disjunctive normal form and $x\wedge (y\vee z)$ in conjunctive normal
form. 5

(g) (i) State the principle of mathematical induction. Show that
$1^2+ 2^2+3^2+...+n^2=\frac{n(n+1)(2n+1)}{6}, n\ge 1$
by mathematical induction. 5
(ii) Simplify the Boolean functions
$f=a.\stackrel{-}{b}+a.b+b.c$
and
$g=\stackrel{-}{a}.b.c+a.\stackrel{-}{b}.c+a.b.\stackrel{-}{c}+a.b.c$ 5