1 (a)
If N is the set of positive integers and R is the set of real numbers, examine which of the following sets is empty:

i) {x|x∈N, 2x+7=3}

ii) {x|x∈R, x

iii) {x|x∈R, x

i) {x|x∈N, 2x+7=3}

ii) {x|x∈R, x

^{2}+4=6}iii) {x|x∈R, x

^{2}+3x+3=0}
4 M

1 (b)
Using Venn diagrams, investigate the truth of falsity of:

i) A Δ(B∩C)=(AΔB)∩(AΔC)

ii) A-(B∪C)=(A-B)∩(A-C) for any three sets A, B, C.

i) A Δ(B∩C)=(AΔB)∩(AΔC)

ii) A-(B∪C)=(A-B)∩(A-C) for any three sets A, B, C.

6 M

1 (c)
Simplify the following:

i) A∩(B-A)

ii) (A∩B)∪(A∩B)∪(A∩B∩C∩D).

i) A∩(B-A)

ii) (A∩B)∪(A∩B)∪(A∩B∩C∩D).

5 M

1 (d)
A fair coin is tossed five times. What is the probability that the number of heads always exceeds the number of tails as each outcome is observed.

5 M

2 (a)
Write the following in symbolic form and establish if the argument is valid: if A gets the supervisor's position and works hard, then he will get a raise. If the gets a raise, then he will by a new car. He has not bought a new car. Therefore A did not get the supervisor's position or he did not work hard.

5 M

2 (b)
Verify the following withot using thruth tables:

[ [(p o q)wedge( eg r vee s)wedge(pvee r) herefore eg q o s.] ]

[ [(p o q)wedge( eg r vee s)wedge(pvee r) herefore eg q o s.] ]

5 M

2 (c)
Define tautology. Show that [(p∨q)∧(p→r)∧(q→r)]→r is a tautology, by constructing a truth table.

5 M

2 (d)
Show that the following argument is invalid by giving a counter example:

[ [(pwedge eg q)wedge left { p o (q o r) ight }] o eg r ]

[ [(pwedge eg q)wedge left { p o (q o r) ight }] o eg r ]

5 M

3 (a)
Verify the following is valid:

[ forall x[p(x)vee q(x)]; exists x eg p(x) \ forall x [ eg g(x)vee r(x)] \ forall x [s(x) o eg r(x) ] herefore exists x eg s(x)) ]

[ forall x[p(x)vee q(x)]; exists x eg p(x) \ forall x [ eg g(x)vee r(x)] \ forall x [s(x) o eg r(x) ] herefore exists x eg s(x)) ]

5 M

3 (b)
Prove that for all real numbers x and y, if x+y>100, then x>50 or y>50

5 M

3 (c)
Determine if the argument is valid or not. All people concerned about the environment, recycle their plastic containers. B is not concerned about the environment. Therefore, B does not recycle his plastic containers.

5 M

3 (d)
Negative and simplify:

[ i) forall x[left (p(x)wedge eg q(x)] \ \ ii) exists x [p(x)vee q(x) ight) o r(x)] ]

[ i) forall x[left (p(x)wedge eg q(x)] \ \ ii) exists x [p(x)vee q(x) ight) o r(x)] ]

5 M

4 (a)
Define the following:

i) Well ordering principle

ii) Principle of mathematical induction.

i) Well ordering principle

ii) Principle of mathematical induction.

4 M

4 (b)
Establish the following by mathematical induction:

[ sum^{n}_{t=1}i(2^i)=2+(n-1)2^{n+1} ]

[ sum^{n}_{t=1}i(2^i)=2+(n-1)2^{n+1} ]

5 M

4 (c)
Find a unique solution for the recurrence relation:

4a

4a

_{n}-5a_{n-1}=0, n≥1, a_{0}=1
5 M

4 (d)
Let F

_{n}denote the n^{th}Fibonacci number: Prove that [ sum^{n}_{i=1}dfrac{F_{(i-1)}}{2^i}=1 - dfrac {F_{n+2}}{2^n} ]
6 M

5 (a)
Define Cartesian product of two sets. For non-empty set A, B, C prove that, A×(B∩C)=(A×B)∩(A×C).

4 M

5 (b)
For each of the following functions, determine whether it is 1-1;

i) f:Z→Z, f(x)=2x+1

ii) f:Z→Z, f(x)=x

i) f:Z→Z, f(x)=2x+1

ii) f:Z→Z, f(x)=x

^{3}-x
6 M

5 (c)
Let A=B=C=R, f:A→B, f(a)=2a+1; g; B→C, g(b)=b/2. compute gof and show that it is invertible.

5 M

5 (d)
Let ΔABC be an equilateral triangle of side 1. show that if we select 10 points in the interior, there must be at least two points whose distance apart is less than 1/3.

5 M

6 (a)
for each of the following relations, determine if the relation R is reflexive, symmetric, antisymmetric or transitive.

i) On the set of all line in the plane, l

ii) On Z, xRy if x-y is even.

i) On the set of all line in the plane, l

_{1}Rl_{2}if line l_{1}is perpendicular to live l_{2}ii) On Z, xRy if x-y is even.

5 M

6 (b)
For A={1,2,3,4,}, let R={(1,1), (1,2),(2,3),(3,3),(3,4)} be a relation on A. Draw the digraph of R

^{2}and find the matrix M(R^{2}).
5 M

6 (c)
Draw the Hasse diagram for all the positive integer division of 72.

5 M

6 (d)
Let A={1,2,3,4,5,6} × {1,2,3,4,5,6}. Define R on A by (x

_{1}, y_{1}) R(x_{2}, y_{2}) if x_{1}y_{1}. Verify that R is an equivalence relation on A.
5 M

7 (a)
For a group(G

_{1}'), prove that it is abelian if (a,b)^{2}=a^{2},b^{2}for all a, b∈G.
5 M

7 (b)
[ Let A=egin {pmatrix}0&1\-1&0 end{pmatrix} ] Verify that (A, A

^{2}, A^{3}, A^{4}) form an abelian group under matrix multiplication.
6 M

7 (c)
Define a cyclic group. Verify that (Z:,⋅) is cyclic. Find a generator of this group. Examine if it has any subgroups.

9 M

8 (a)
Determine whether (Z, ⊕,&otimes,) is a ring with the binary operations x⊕y=x+y-7, x⊗y=x+y-3xy for all x,y,∈Z.

6 M

8 (b)
The (5m, m) five times repetition code has encoding function E:Z

_{2}^{m}→Z_{2}^{5m}. Decoding with D:Z_{2}^{5m}→ Z_{2}^{m}is done by majority rule. With p=0.05, what is the probability for the transmission and correct decoding of the signal 110.
6 M

8 (c)
What is the minimum distance of a code consisting of the following code words:

001010, 011100, 010111, 011110, 101001? What kind of error can be detected?

001010, 011100, 010111, 011110, 101001? What kind of error can be detected?

3 M

8 (d)
The encoding function E: Z

_{2}^{2}→Z_{2}^{5}is given by the generator matrix [ G=egin{pmatrix}1 &0 &1 &1 &0 \0 &1 &0 &1 &1end{pmatrix} ] what is the error detection capacity of the code?
5 M

More question papers from Discrete Mathematical Structures