Question Paper Code:: (10×2 20 Marks)

*62530* Reg. No.
Question Paper Code : X 62530

B.E./B.Tech. Degree Examinations, NOVEMBER/DECEMBERr
Fifth/Seventh Semester
Information Technology
ma1256/ma1301/070030014 – discrete mathematics
(Common to Computer Science and Engineering)
(Regulations 2004/2007)
(Also common to B.E. (Part-Time) Fourth Semester – Computer Science and
Engineering – Regulations 2005)
Time : Three Hours Maximum : 100 Marks
Answer all questions

Part – A (10×2=20 Marks)
1. Find the truth value of the statement, “2 > 3 or 3 is a positive interger”.
2. Define conjunctive normal form.
3. Negate and simplify : ∀x [p(x) → q (x)].
4. Give an example to show that (∃ x) (A(x) ∧ B(x)) need not be a conclusion from
(∃x) A(x) and (∃x) B(x).
5. Let x = {1, 2, 3, 4} and
R = {(x, y)/x, y ∈x and ( x – y) is an integral non zero multiple of 2}.
S = {(x, y)/ x, y ∈x and ( x – y) is an integral non-sero multiple of 3}. Find R∪S and
R∩s.
6. Let X = {2, 3, 6, 12, 24, 36} and the relation ≤ be such that x ≤ y if x divides y. Draw
the Hasse diagram of (x, ≤). Also pick out maximal, minimal, least and greatest
elements.
1
7. Given that f(x) = x3; g(x) = x 3 for X ∈R. Find fog ; gof.
X 62530 -2- *62530*
8. Determine whether the function
f : N → N, defined by
 1, j is even
f ( j) = 
0, j is odd, is on to or not ?
9. Show that the set of positive even integers with the usual addition is a semigroup
but not a monoid.
10. Define the minimum distance of a group code.
Part – B (5×16=80 Marks)
11. a) i) Construct the truth table for
(  p ∧ (  qr )) ∨ ((q ∧ r ) ∨ ( p ∧ r )) . (8)
ii) Prove the equivalence (p → r) ∧(q → r) ⇔ (p ∨ q) → r using derivation

method. (8)
(OR)
b) Obtain PCNF and PDNF of (  p → R ) ∧ (Q ↔ p) . (16)
12. a) i) Show that (x) (F(x) →~S(x)) follows from the premises.
(∃x) (F(x) ∧ S(x)) → (y) (M(y) → W(y)), (∃y) (M(y) ∧ ~ W(y)). (8)
ii) Show that ~ P (a, b) follows logically from (x)(y) (P(x, y) →W(x, y))
and ~ W(a, b). (8)

(OR)
b) i) Verify the validity of the following inference.

If one person is more successful than another then he has worked harder to
deserve success. John has not worked harder than Peter. Therefore John is
not more successful than Peter. (8)
ii) Verify the validity of the following argument.

Every living thing is a plant or an animal. John’s gold fish is alive and it is
not a plant. All animals have hearts. Therefore John’s gold fish has a heart. (8)
*62530* -3- X 62530
13. a) i) Prove that (A∩B) ∪[B ∩((C ∩ D) ∪ (C ∩ D ))] using laws of set theory. (8)
ii) Establish De Morgan’s laws in a Boolean Algebra. (8)
(OR)
b) i) Let R denote a relation on the set of ordered pairs of positive integers such that
(x, y) R(u, v) if and only if xv = yu. Show that R is an equivalence relation. (8)
ii) Let l, *,⊕ , be a complemented, distributed lattice. For a, b, c ∈ L show

that the following are equivalent. (8)
1) a ≤ b
2) a * b´ = 0
3) a′ ⊕ b = 1
4) b′ ≤ a′
14. a) i) Let X = {0, 1, 2,...). Then determine whether f : X → X defined by
1, x is odd
f ( x ) =  is one-one, on to and both. (5)
0, x is even
ii) Let f(x) = x + 2; g(x) = x – 2; h(x) = 3x for x ∈R, where R is the set of real
numbers. Find foh, hog, fohog and check whether (foh)og and fo(hog) are
equal. (6)
iii) Show that x * y = x – y is not a binary operation over the set of natural
numbers, but that it is a binary operation on the set of integers. Is it
commutative or associative ? (5)
(OR)
b) i) Prove that ψ a ∩ B ( x ) = ψ a ( x )xψ B ( x ), where x is the usual multiplication. (5)
ii) Determine the value of f(2, 4) of the function ‘f ’ defined by f(x, y) = x + y using
recursion formula with the initial value f(2, 0). (6)
1 2 3 4 5 6 7
iii) Is the permutation p =   even or odd ? (5)
 2 4 5 7 6 3 1
X 62530 -4- *62530*
15. a) i) If S = N × N, the set of ordered pairs of positive integers with the operation *
defined by (a, b) * (c, d) = (ad + bc, bd) and f : s(S,*) → (Q,+) is defined by
a
f (a, b) = show that f is a semigroup. (8)
b
ii) Show that the intersection of two normal subgroups of group G is also a
normal subgroup of G. (8)
(OR)
b) i) State and prove the Lagrange’s theroem. (8)
ii) Find the code words generated by the parity check matrix
1 1 0 1 0 0
h =  1 0 1 0 1 0 
0 1 1 0 0 1
. (8)
_______________

Question Paper Code:: (10×2 20 Marks)

Uploaded by

Copyright:

Available Formats

Question Paper Code:: (10×2 20 Marks)

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Question Paper Code:: (10×2 20 Marks)

Uploaded by

Copyright:

Available Formats

*62530* Reg. No.

Question Paper Code : X 62530

Time : Three Hours Maximum : 100 Marks

Answer all questions

1. Find the truth value of the statement, “2 > 3 or 3 is a positive interger”.

2. Define conjunctive normal form.

3. Negate and simplify : ∀x [p(x) → q (x)].

(∃x) A(x) and (∃x) B(x).

5. Let x = {1, 2, 3, 4} and

R = {(x, y)/x, y ∈x and ( x – y) is an integral non zero multiple of 2}.

8. Determine whether the function

10. Define the minimum distance of a group code.

Part – B (5×16=80 Marks)

11. a) i) Construct the truth table for

ii) Prove the equivalence (p → r) ∧(q → r) ⇔ (p ∨ q) → r using derivation

and ~ W(a, b). (8)

b) i) Verify the validity of the following inference.

ii) Verify the validity of the following argument.

ii) Establish De Morgan’s laws in a Boolean Algebra. (8)

ii) Let l, *,⊕ , be a complemented, distributed lattice. For a, b, c ∈ L show

14. a) i) Let X = {0, 1, 2,...). Then determine whether f : X → X defined by

b) i) Prove that ψ a ∩ B ( x ) = ψ a ( x )xψ B ( x ), where x is the usual multiplication. (5)

b) i) State and prove the Lagrange’s theroem. (8)

You might also like

62530 Reg. No.

and ~ W(a, b). (8)