1 (a)
For any three set A,B,C, prove that A∩(B∪C)=(A∩B)∪(A∩C).

6 M

1 (b)
Among the integers from 1 to 200, find the number of integers that are:

i) not divisible by 5

ii) divisible by 2 or 5 or 9

iii) not divisible by 2 or 5 or 9

i) not divisible by 5

ii) divisible by 2 or 5 or 9

iii) not divisible by 2 or 5 or 9

7 M

1 (c)
A problem is given to four students A,B,C,D whose chances of solving it are 1/2, 1/3, 1/4, 1/5 respectively. Find the probability that the problem is solved.

7 M

2 (a)
Define a tautology and contradiction. Prove that, for any propositions p,q,r, the compound proposition [(p→q) ∧ (q→r)] → (p→r) is a tautology.

6 M

2 (b)
Define the dual of logical statement. Verify the principle of duality for the following logical equivalence: [¬ (p∧q)→ ¬ p∨(¬ p∨q)]⇔ ( ¬ p∨q)

7 M

2 (c)
Define converse, inverse and contra-positive of a conditional with truth table. Write down the contra-positive of [p→(q→r)] with:

i) only one occurrence of the connective →

ii) no occurrence of the connective →

i) only one occurrence of the connective →

ii) no occurrence of the connective →

7 M

3 (a)
Negate and simplify each of the following:

i) ∃x, [p(x)∨q(x)]

ii) ∀x, [p(x)∧ ¬ q(x)]

iii) ∀x, [p(x)→q(x)]

i) ∃x, [p(x)∨q(x)]

ii) ∀x, [p(x)∧ ¬ q(x)]

iii) ∀x, [p(x)→q(x)]

6 M

3 (b)
Establish the validity of the following argument:

[ egin {align*} &forall x, [p(x)vee q(x)] \ &forall x, [ left { eg p(x)wedge q(x) ight } o r(x)] \ hline& herefore forall x, [ eg r(x) o p(x)] end{align*} ]

[ egin {align*} &forall x, [p(x)vee q(x)] \ &forall x, [ left { eg p(x)wedge q(x) ight } o r(x)] \ hline& herefore forall x, [ eg r(x) o p(x)] end{align*} ]

6 M

3 (c)
Prove that every even integer n with 2≤n≤26 can be written as a sum of atmost three perfect squares.

7 M

4 (a)
Let a

_{0}=1, a_{1}=2, a_{2}=3 and a_{n}=a_{n-1}+a_{n-2}+a_{n-3}for n≥3. Prove that a_{n}=≤3^{n}for all positive integrs n.
6 M

4 (b)
Find an explicit definition of the sequence defined by a

_{1}=7, a_{n}=2a_{n-1}+1 for n≥2.
7 M

4 (c)
The Lucas number are defined recursively by L

_{0}=2, L_{1}=1 and L_{n}=L_{n-1}+L_{-2}for n≥2. Evaluate L_{2}to L_{10}.
7 M

5 (a)
Suppose A, B, C⊆Z X Y with A={(x,y)|y=5x-1}; B={(x,y)|y=6x}; C={(x,y)|3x-y=-7}. Find: [ i) Acap B \ ii) B cap C \ iii) overline{overline{A}cup overline{C}}\ iv) overline{B}cup overline{C} ]

6 M

5 (b)
Define stirling number of second kind. Find the number of ways of distributing four distinct objects among three identical containers with some containers possibly empty.

7 M

5 (c)
If f:A→B, g:B→C, and h:C→D are three functions then prove that (h⋅g)⋅f=h⋅(g⋅f)

7 M

6 (a)
Let A={1,2,3,4}, B={w,x,y,z} and C={5,6,7}. Also let R

_{1}be a relation from A to B defined by R_{1}={(1,x), (2,x), (3,z)} and R_{2}and R_{3}be relation from B and C, defined by R_{2}={(w,5),(x,6)}, R_{3}={(w,5),(w,6)}. Find R_{1}⋅R_{3}.
6 M

6 (b)
Find the number of equivalence relation that can be defined on a finite set A with |A|=6

7 M

6 (c)
For A={a,b,c,d,e}, the Hasse diagam for the poset (A,R) is as shown below.

i) Determine the relation matrix for R.

ii) Construct the diagraph for R

i) Determine the relation matrix for R.

ii) Construct the diagraph for R

7 M

7 (a)
Define subgroup of a group. Let G he a group and let J={x ∈ G|xy=yx for all y ∈ G}. Prove that J is a subgroup of G.

6 M

7 (b)
State and prove Lagrange's theorem.

7 M

7 (c)
The word C=1010110 is sent through a binary symmetric channel. If p=0.02 is the probability of incorrect receipt of a signal, find the probability that C is received as r=1011111. Determine the error pattern.

7 M

8 (a)
The parity check matrix for an encoding function E: z

ii) Does this code correct all single errors in transmission?

_{2}^{3}→ z_{2}^{6}given by [ H=egin{bmatrix} 1&0 &1 &1 &0 &0 \1 &1 &0 &0 &1 &0 \1 &0 &1 &0 &0 &1 end{bmatrix} ] i) Determine the associated generator matrixii) Does this code correct all single errors in transmission?

6 M

8 (b)
Prove that the set z with binary operations ⊕ and ⊙ defined by x⊕y=x+y-1; x⊙y=x+y-xy is a cumulative ring.

7 M

8 (c)
Show that z

_{6}is no an integral domain.
7 M

More question papers from Discrete Mathematical Structures