STUPIDSID
1 (a)
Define symmetric difference of two sets. Also prove by using Venn diagram for any three sets A, B, C (AΔB)ΔC=AΔ(BΔC)
6 M
1 (b)
i) Write the dual statement for the set theoretic results,
\( u: \ U=(A \cap B)\cup (A\cap \overline B)\cup (\overline A \cap B) \cup (\overline A \cap \overline B) \)
ii) Using the laws of set theory simplify: \(\overline {\overline{(A\cup B)\cap C}\cup \overline B} \)
\( u: \ U=(A \cap B)\cup (A\cap \overline B)\cup (\overline A \cap B) \cup (\overline A \cap \overline B) \)
ii) Using the laws of set theory simplify: \(\overline {\overline{(A\cup B)\cap C}\cup \overline B} \)
3 M
1 (c)
A student visits an arcade each day after school and plays one game of either Laser man, Millipede or space conquerors. In how many ways can he play one game each day so that he plays each of the three types at least once during a given school week? (Monday through Friday).
6 M
1 (d)
An integer is selected at random from 3 through 17 inclusive. If A is the event that a number divisible by 3 is chosen and B is the event that the chosen number exceeds 10. Determine Pr(A), Pr(B), Pr(A∩B), Pr(A∪B).
5 M
2 (a)
Prove the following logical equivalence without using truth table. \( \Big [ \neg p \wedge \big (\neg q \wedge r \big ) \Big ]\vee \big(q\wedge r\big) \vee \big(p\wedge r\big) \Leftrightarrow r. \)
6 M
2 (b)
Define Tautology. Examine whether the compound proposition \( \Big [ \big ( p\vee q \big ) \to r \Big] \leftrightarrow \Big[ \neg r \to \neg \big ( p \vee q \big) \Big] \) is a tautology.
7 M
2 (c)
Establish the validity of the argument:
\[ \ p \to q \\ \ q\to (r\wedge s) \\ \ \neg r \vee (\neg t \wedge u) \\ \ p\wedge t \\ \overline {\ \therefore u \ \ \ \ \ \ \ \ \ \ \ \ \ } \]
\[ \ p \to q \\ \ q\to (r\wedge s) \\ \ \neg r \vee (\neg t \wedge u) \\ \ p\wedge t \\ \overline {\ \therefore u \ \ \ \ \ \ \ \ \ \ \ \ \ } \]
7 M
3 (a)
Write down the converse, inverse and contra positive of, \[ \forall x \big [ x^2 + 4x-21 > 0 \big ] \to \big [(x>3)\vee (x<-7) \big ] \]
3 M
3 (b)
Let p(x): x2-7x+10=0, q(x): x2-2x-3=0, r(x):x<0. Determine the truth or falsity of the statement for which the universe contains only the integers 2 and 5. If a statement is false, provide a counter example. \[ i) \ \forall x[p(x) \to \neg r (x)] \\
ii) \ \forall x [q(x)\to r (x)] \\
iii) \ \exists x[q(x) \to r(x)] \\
iv) \ \exists x [ p(x) \to r (x)] \]
5 M
3 (c)
Determine the truth value of each of the following quantified statements for the set of all non-zero integers: \[ i) \exists x, \exists y [xy = 1] \\
ii) \forall x, \exists y [xy = 1] \\
iii) \exists x, \exists y [(2x+y=5) \wedge (x-3y=-8)] \\
iv) \exists x, \exists y [(3x - y = 17) \wedge (2x + 4y = 3)] \\
v) \exists x, \forall y [xy = 1] \]
5 M
3 (d)
Establish the validity of the following argument, \[ \ \forall x, \ [ p(x) \vee q (x)] \\
\ \exists x, \ [ \neg p(x)] \\
\ \forall x, \ [ \neg q(x) \wedge r(x)] \\
\ \forall x, \ [s(x) \to \neg r (x)] \\
\overline { \ \ \ \ \therefore \exists x \neg s(x) \ \ \ \ \ \ \ \ \ \ \ \ } \]
7 M
4 (a)
Define the well-ordering principle. By using mathematical induction prove that, \[ \dfrac {1}{2.5} + \dfrac {1}{5.8}+ \dfrac {1}{7.11} + \cdots + \dfrac {1}{(3n-1) (3n-2)} = \dfrac {n}{6n+4} \]
7 M
4 (b)
if F0, F1, F2.... are Fibonacci numbers, prove that \( \sum^n_{i=0} F^2_1 = F_n \times F_{n+1}. \)
7 M
4 (c)
The Ackermann's numbers Am,n are defined recursively for m, n∈N as follows:
A0, n=n+1 for n ≥ 0
Am, 0 = Am-1, 1 for m>0
Am, n = Am-1, p Where P=Am, n-1 for m, n>0. Prove that A1, n = n+2 for all n∈N.
A0, n=n+1 for n ≥ 0
Am, 0 = Am-1, 1 for m>0
Am, n = Am-1, p Where P=Am, n-1 for m, n>0. Prove that A1, n = n+2 for all n∈N.
6 M
5 (a)
Define equivalence relation and equivalence class with one example.
6 M
5 (b)
Let A={1, 2, 3, 4, 6}, R be a relation on A defined by aRb if and only if 'a' is a multiple of 'b'. Represent the relation R as a matrix and draw its digraph.
6 M
5 (c)
Let A={1, 2, 3, 4, 5}, A relation R on A×A by (x1, y1) R(x2, y2) if and only if x1+y1=x2+y2. Determine the partition of A×A induced by R.
4 M
5 (d)
Consider the Hasse diagram of a POSET (A,R) given below:
If B={c, d, e}, find (if they exist)
i) all upper bounds of B
ii) all lower bounds of B
iii) the least upper bound of B
iv) the greatest lower bound of B.
If B={c, d, e}, find (if they exist)
i) all upper bounds of B
ii) all lower bounds of B
iii) the least upper bound of B
iv) the greatest lower bound of B.
4 M
6 (a)
Let f: R→R be define by \( f(x)= \left\{\begin{matrix}
3x-5 & \text {for }x>0 \\ -3x+1
& \text {for } x \le 0
\end{matrix}\right. \text{ find }f^1 (3), \ f^{-1} \big ( [-5, 5]\big ) \text{ and } f^{-1} \big ( [ -6, 5] \big ) \)
5 M
6 (b)
If f is a real valued function defined by f(x)=x2+1 ∀x∈R. Find the images of the following: (i) A1 ={2, 3} (ii) A2={-2, 0, 3}
(iii) A3= {0, 1}
(iv) A4={-6, 3}.
(iii) A3= {0, 1}
(iv) A4={-6, 3}.
5 M
6 (c)
State the pigeon hole principle. Prove that in any set of 29 persons at least five persons must have been born on the same day of the week.
4 M
6 (d)
What is Invertible function? For the invertible functions f:A→B and g:B→C, prove that (g∘f)-1 = f-1 ∘ g-1.
6 M
7 (a)
Define subgroup of a group. Prove that H is a subgroup of a group G if and only if for all a, b∈H, ab-1 ∈H.
6 M
7 (b)
For a group G, prove that the function f: G→G defined by f(a)=a-1 is an isomorphism if and only if G is abelian.
4 M
7 (c)
State and prove Lagrange's theorem.
5 M
7 (d)
A binary symmetric channel has probability P=0.05 incorrect transmission. If the word C=01101101 is transmitted, what is the probability that, i) a double error occurs
ii) a triple errors occurs no two of them consecutive?
ii) a triple errors occurs no two of them consecutive?
5 M
8 (a)
Find all integers K and m for which (z,⊕,⊙) is a ring under the binary operations x⊕y=x+y-k, x⊙y=x+y-mxy.
5 M
8 (b)
What is an integral domain? Prove that every field is an integral domain.
5 M
8 (c)
Let C be a group code in Zn2. If r∈Zn2 is a received word and r is decoded as the code word. C*, then prove that d(C*, r) ≤ d (C, r) for all c∈C.
4 M
8 (d)
Prove that in Zn [a] is a unit if and only if ged (a,n)=1 and find all the units in Z12.
6 M
More question papers from Discrete Mathematical Structures