Free MCS-211 Solved Assignment | January 2025, July 2025 | MCA_NEW, MCAOL | English & Hindi Medium | IGNOU

Question Paper: MCS-212 Discrete Mathematics

Prove by mathematical induction that $\sum _{i=1}^n\frac{1}{i(i+1)}=\frac{n}{n+1}$$\sum _{i=1}^n \frac{1}{i(i+1)}=\frac{n}{n+1}$sum_(i=1)^(n)(1)/(i(i+1))=(n)/(n+1)\sum_{i=1}^{n} \frac{1}{i(i+1)} = \frac{n}{n+1}$\sum _{i=1}^n\frac{1}{i(i+1)}=\frac{n}{n+1}$.

Answer:

🧮 Step 1: Base Case (n = 1)

🔁 Step 2: Inductive Hypothesis

🧠 Step 3: Inductive Step (Prove for $n=k+1$$n=k+1$n=k+1n = k+1$n=k+1$)

✅ Step 4: Conclusion

Verify whether $\sqrt{11}$$\sqrt{11}$sqrt11\sqrt{11}$\sqrt{11}$ is rational or irrational.

Answer:

Write the following statements in symbolic form:

• Some students cannot appear in exam.
• Everyone cannot sing.

Answer:

📝 Statements in Symbolic Form

• $S(x)$$S(x)$S(x)S(x)$S(x)$: $x$$x$xx$x$ is a student
• $E(x)$$E(x)$E(x)E(x)$E(x)$: $x$$x$xx$x$ can appear in the exam

• $P(x)$$P(x)$P(x)P(x)$P(x)$: $x$$x$xx$x$ is a person
• $S(x)$$S(x)$S(x)S(x)$S(x)$: $x$$x$xx$x$ can sing

Draw the logic circuit for the following Boolean Expression: $(xyz)+(x+y+z{)}^{\prime }+(x^{\prime }z{y}^{\prime })$$(xyz)+(x+y+z{)}^{\prime }+(x^{\prime }z{y}^{\prime })$(xyz)+(x+y+z)^(')+(x^(')zy^('))(xyz) + (x+y+z)' + (x'zy')$(xyz)+(x+y+z{)}^{\prime }+(x^{\prime }z{y}^{\prime })$.

Answer:

Explain whether the function $f(x)=x^2$$f(x)=x^2$f(x)=x^(2)f(x) = x^2$f(x)=x^2$ possesses an inverse function or not.

Answer:

• Example:
  $f(2)=4$$f(2)=4$f(2)=4f(2) = 4$f(2)=4$
  $f(-2)=4$$f(-2)=4$f(-2)=4f(-2) = 4$f(-2)=4$
  → Same output (4) from two different inputs (2 and -2).
• This violates the one-to-one condition.

Write the finite automata corresponding to the regular expression $(a+b{)}^{\ast }ab$$(a+b{)}^{\ast }ab$(a+b)^(**)ab(a + b)^*ab$(a+b{)}^{\ast }ab$.

Answer:

🧠 Finite Automata for Regular Expression: $(a+b{)}^{\ast }ab$$(a+b{)}^{\ast }ab$(a+b)^(**)ab(a + b)^*ab$(a+b{)}^{\ast }ab$

📌 Step 1: Understand the Regular Expression

• $(a+b{)}^{\ast }$$(a+b{)}^{\ast }$(a+b)^(**)(a + b)^*$(a+b{)}^{\ast }$: Any string of a's and b's (including empty string).
• ab: The string must end with "ab".

🔧 Step 2: Design the Finite Automata (FA)

🧩 States:

• q0: Initial state (no input or input not ending with "a" or "ab").
• q1: State after reading "a" (potential start of "ab").
• q2: Final state after reading "ab".

🧭 Transitions:

• From q0:
  • On a: go to q1 (possible start of "ab").
  • On b: stay at q0 (since "b" doesn't help form "ab").
• From q1:
  • On a: stay at q1 (new "a" may start a new "ab").
  • On b: go to q2 (complete "ab").
• From q2 (final state):
  • On a: go to q1 (new "a" may start a new "ab").
  • On b: go to q0 (as "b" breaks the sequence).

🗺️ State Transition Table:

📊 Diagram Representation:

        a           b
→ q0 ─────→ q1 ─────→ q2 (Final)
   │         │         │
   │ b       │ a       │ a
   ↓         ↓         ↓
   q0        q1        q1
   └───────────────────┘
          b

• Start State: q0
• Final State: q2

✅ Example Strings:

• "ab": q0 → q1 → q2 ✅
• "aab": q0 → q1 → q1 → q2 ✅
• "abb": q0 → q1 → q2 → q0 ❌ (ends at non-final state)
• "ba": q0 → q0 → q1 ❌ (ends at non-final state)

🧾 Summary:

If $L_1$$L_1$L_(1)L_1$L_1$ and $L_2$$L_2$L_(2)L_2$L_2$ are context-free languages, then prove that $L_1\cup L_2$$L_1\cup L_2$L_(1)uuL_(2)L_1 \cup L_2$L_1\cup L_2$ is a context-free language.

Answer:

🧠 Proof: Closure of CFLs under Union

📌 Step 1: Definition of Context-Free Languages (CFLs)

• $V$$V$VV$V$: Non-terminals
• $\mathrm{\Sigma }$$\mathrm{\Sigma }$Sigma\Sigma$\mathrm{\Sigma }$: Terminals
• $R$$R$RR$R$: Production rules
• $S$$S$SS$S$: Start symbol

📌 Step 2: Given

• $G_1=(V_1,{\mathrm{\Sigma }}_1,R_1,S_1)$$G_1=(V_1,{\mathrm{\Sigma }}_1,R_1,S_1)$G_(1)=(V_(1),Sigma_(1),R_(1),S_(1))G_1 = (V_1, \Sigma_1, R_1, S_1)$G_1=(V_1,{\mathrm{\Sigma }}_1,R_1,S_1)$ such that $L(G_1)=L_1$$L(G_1)=L_1$L(G_(1))=L_(1)L(G_1) = L_1$L(G_1)=L_1$
• $G_2=(V_2,{\mathrm{\Sigma }}_2,R_2,S_2)$$G_2=(V_2,{\mathrm{\Sigma }}_2,R_2,S_2)$G_(2)=(V_(2),Sigma_(2),R_(2),S_(2))G_2 = (V_2, \Sigma_2, R_2, S_2)$G_2=(V_2,{\mathrm{\Sigma }}_2,R_2,S_2)$ such that $L(G_2)=L_2$$L(G_2)=L_2$L(G_(2))=L_(2)L(G_2) = L_2$L(G_2)=L_2$

🛠️ Step 3: Construct a CFG for $L_1\cup L_2$$L_1\cup L_2$L_(1)uuL_(2)L_1 \cup L_2$L_1\cup L_2$

• $V=V_1\cup V_2\cup \{S\}$$V=V_1\cup V_2\cup \{S\}$V=V_(1)uuV_(2)uu{S}V = V_1 \cup V_2 \cup \{S\}$V=V_1\cup V_2\cup \{S\}$ (all non-terminals from $G_1$$G_1$G_(1)G_1$G_1$, $G_2$$G_2$G_(2)G_2$G_2$, plus a new start symbol $S$$S$SS$S$)
• $\mathrm{\Sigma }={\mathrm{\Sigma }}_1\cup {\mathrm{\Sigma }}_2$$\mathrm{\Sigma }={\mathrm{\Sigma }}_1\cup {\mathrm{\Sigma }}_2$Sigma=Sigma_(1)uuSigma_(2)\Sigma = \Sigma_1 \cup \Sigma_2$\mathrm{\Sigma }={\mathrm{\Sigma }}_1\cup {\mathrm{\Sigma }}_2$
• $R=R_1\cup R_2\cup \{S\to S_1\mid S_2\}$$R=R_1\cup R_2\cup \{S\to S_1\mid S_2\}$R=R_(1)uuR_(2)uu{S rarrS_(1)∣S_(2)}R = R_1 \cup R_2 \cup \{S \to S_1 \mid S_2\}$R=R_1\cup R_2\cup \{S\to S_1\mid S_2\}$ (all rules from $G_1$$G_1$G_(1)G_1$G_1$ and $G_2$$G_2$G_(2)G_2$G_2$, plus two new rules for $S$$S$SS$S$)

✅ Step 4: Prove $L(G)=L_1\cup L_2$$L(G)=L_1\cup L_2$L(G)=L_(1)uuL_(2)L(G) = L_1 \cup L_2$L(G)=L_1\cup L_2$

• Derivation in $G$$G$GG$G$:
  • Start with $S$$S$SS$S$.
  • Choose either $S\to S_1$$S\to S_1$S rarrS_(1)S \to S_1$S\to S_1$ or $S\to S_2$$S\to S_2$S rarrS_(2)S \to S_2$S\to S_2$.
  • If $S\to S_1$$S\to S_1$S rarrS_(1)S \to S_1$S\to S_1$, then derive a string using rules from $R_1$$R_1$R_(1)R_1$R_1$ ⇒ generates a string in $L_1$$L_1$L_(1)L_1$L_1$.
  • If $S\to S_2$$S\to S_2$S rarrS_(2)S \to S_2$S\to S_2$, then derive a string using rules from $R_2$$R_2$R_(2)R_2$R_2$ ⇒ generates a string in $L_2$$L_2$L_(2)L_2$L_2$.
• Every string in $L_1\cup L_2$$L_1\cup L_2$L_(1)uuL_(2)L_1 \cup L_2$L_1\cup L_2$:
  • If $w\in L_1$$w\in L_1$w inL_(1)w \in L_1$w\in L_1$, then $S_1{\Rightarrow }^{\ast }w$$S_1{\Rightarrow }^{\ast }w$S_(1)=>^(**)wS_1 \Rightarrow^* w$S_1{\Rightarrow }^{\ast }w$ in $G_1$$G_1$G_(1)G_1$G_1$, so $S\to S_1{\Rightarrow }^{\ast }w$$S\to S_1{\Rightarrow }^{\ast }w$S rarrS_(1)=>^(**)wS \to S_1 \Rightarrow^* w$S\to S_1{\Rightarrow }^{\ast }w$ in $G$$G$GG$G$.
  • Similarly, if $w\in L_2$$w\in L_2$w inL_(2)w \in L_2$w\in L_2$, then $S\to S_2{\Rightarrow }^{\ast }w$$S\to S_2{\Rightarrow }^{\ast }w$S rarrS_(2)=>^(**)wS \to S_2 \Rightarrow^* w$S\to S_2{\Rightarrow }^{\ast }w$ in $G$$G$GG$G$.

🧾 Step 5: Conclusion

Explain Decidable and Undecidable Problems. Give an example for each.

Answer:

📘 Decidable vs. Undecidable Problems

✅ Decidable Problems

• Halts on every input
• Correctly outputs "yes" or "no" for each input

• Given a CFG $G$$G$GG$G$ and string $w$$w$ww$w$, we can use the CYK algorithm to decide if $w\in L(G)$$w\in L(G)$w in L(G)w \in L(G)$w\in L(G)$.
• The algorithm always halts and returns a true/false answer.

❌ Undecidable Problems

• Halts on every input
• Correctly solves the problem for all cases

• Given a program $P$$P$PP$P$ and input $I$$I$II$I$, determine if $P$$P$PP$P$ halts on $I$$I$II$I$.
• Proven by Alan Turing to be undecidable: no general algorithm can solve this for all $(P,I)$$(P,I)$(P,I)(P, I)$(P,I)$.

🧠 Key Difference:

• Decidable: Algorithm exists and always gives an answer.
• Undecidable: No such algorithm exists; problem is "unsolvable" in general.

What is an equivalence relation? Explain the use of equivalence relation with the help of an example.

Answer:

1. ↺ Reflexivity: $a\sim a$$a\sim a$a∼aa \sim a$a\sim a$ (Every element is related to itself).
2. ↔️ Symmetry: If $a\sim b$$a\sim b$a∼ba \sim b$a\sim b$, then $b\sim a$$b\sim a$b∼ab \sim a$b\sim a$ (The relation is two-way).
3. ➡️ Transitivity: If $a\sim b$$a\sim b$a∼ba \sim b$a\sim b$ and $b\sim c$$b\sim c$b∼cb \sim c$b\sim c$, then $a\sim c$$a\sim c$a∼ca \sim c$a\sim c$ (Relations chain together).

• Let's define the relation: For integers $a$$a$aa$a$ and $b$$b$bb$b$, $a\sim b$$a\sim b$a∼ba \sim b$a\sim b$ if $a-b$$a-b$a-ba - b$a-b$ is divisible by 3.

• In our example, this relation partitions all integers into three distinct equivalence classes:
  • Class [0]: Integers with remainder 0 → $\{...,-6,-3,0,3,6,...\}$$\{...,-6,-3,0,3,6,...\}${...,-6,-3,0,3,6,...}\{..., -6, -3, 0, 3, 6, ...\}$\{...,-6,-3,0,3,6,...\}$
  • Class [1]: Integers with remainder 1 → $\{...,-5,-2,1,4,7,...\}$$\{...,-5,-2,1,4,7,...\}${...,-5,-2,1,4,7,...}\{..., -5, -2, 1, 4, 7, ...\}$\{...,-5,-2,1,4,7,...\}$
  • Class [2]: Integers with remainder 2 → $\{...,-4,-1,2,5,8,...\}$$\{...,-4,-1,2,5,8,...\}${...,-4,-1,2,5,8,...}\{..., -4, -1, 2, 5, 8, ...\}$\{...,-4,-1,2,5,8,...\}$

• 🔢 Mathematics: Defining rational numbers, constructing integers.

• **💻 Computer Science**: State minimization in automata, partitioning data.
  

• **🌐 Network Engineering**: Grouping objects into clusters based on a defining property.
  

There are three Companies, $C_1$$C_1$C_(1)C_1$C_1$, $C_2$$C_2$C_(2)C_2$C_2$, and $C_3$$C_3$C_(3)C_3$C_3$. The party $C_1$$C_1$C_(1)C_1$C_1$ has 4 members, $C_2$$C_2$C_(2)C_2$C_2$ has 5 members, and $C_3$$C_3$C_(3)C_3$C_3$ has 6 members in an assembly. Suppose we want to select two persons, both from the same Company, to become president and vice president. In how many ways can this be done?

Answer:

• $C_1$$C_1$C_(1)C_1$C_1$: 4 members
• $C_2$$C_2$C_(2)C_2$C_2$: 5 members
• $C_3$$C_3$C_(3)C_3$C_3$: 6 members

• For $C_1$$C_1$C_(1)C_1$C_1$ (4 members): $4\times 3=12$$4\times 3=12$4xx3=124 \times 3 = 12$4\times 3=12$ ways
• For $C_2$$C_2$C_(2)C_2$C_2$ (5 members): $5\times 4=20$$5\times 4=20$5xx4=205 \times 4 = 20$5\times 4=20$ ways
• For $C_3$$C_3$C_(3)C_3$C_3$ (6 members): $6\times 5=30$$6\times 5=30$6xx5=306 \times 5 = 30$6\times 5=30$ ways

How many words can be formed using the letters of DEPARTMENT using each letter at most once?

• If each letter must be used.
• If some or all the letters may be omitted.

Answer:

Part (1): Each letter must be used

Part (2): Some or all letters may be omitted

Final Answer

What is the probability that a number between 1 and 10,000 is divisible by neither 2, 3, 5, nor 7?

Answer:

🧮 Step 1: Count Numbers Divisible by 2, 3, 5, or 7

• $N=10,000$$N=10,000$N=10,000N = 10,000$N=10,000$
• Let $A_k$$A_k$A_(k)A_k$A_k$ be the set of numbers divisible by $k$$k$kk$k$.

• $|A_k|=\lfloor \frac{10000}{k}\rfloor$$|A_k|=⌊\frac{10000}{k}⌋$|A_(k)|=|__(10000 )/(k)__||A_k| = \left\lfloor \frac{10000}{k} \right\rfloor$|A_k|=\lfloor \frac{10000}{k}\rfloor$
• $|A_i\cap A_j|=\lfloor \frac{10000}{\text{lcm}(i,j)}\rfloor$$|A_i\cap A_j|=⌊\frac{10000}{\text{lcm}(i,j)}⌋$|A_(i)nnA_(j)|=|__(10000)/("lcm"(i,j))__||A_i \cap A_j| = \left\lfloor \frac{10000}{\text{lcm}(i,j)} \right\rfloor$|A_i\cap A_j|=\lfloor \frac{10000}{\text{lcm}(i,j)}\rfloor$
• Similarly for triple and quadruple intersections.

🔢 Step 2: Compute Individual Counts

Single Divisors:

• $|A_2|=\lfloor \frac{10000}{2}\rfloor =5000$$|A_2|=⌊\frac{10000}{2}⌋=5000$|A_(2)|=|__(10000)/(2)__|=5000|A_2| = \left\lfloor \frac{10000}{2} \right\rfloor = 5000$|A_2|=\lfloor \frac{10000}{2}\rfloor =5000$
• $|A_3|=\lfloor \frac{10000}{3}\rfloor =3333$$|A_3|=⌊\frac{10000}{3}⌋=3333$|A_(3)|=|__(10000)/(3)__|=3333|A_3| = \left\lfloor \frac{10000}{3} \right\rfloor = 3333$|A_3|=\lfloor \frac{10000}{3}\rfloor =3333$
• $|A_5|=\lfloor \frac{10000}{5}\rfloor =2000$$|A_5|=⌊\frac{10000}{5}⌋=2000$|A_(5)|=|__(10000)/(5)__|=2000|A_5| = \left\lfloor \frac{10000}{5} \right\rfloor = 2000$|A_5|=\lfloor \frac{10000}{5}\rfloor =2000$
• $|A_7|=\lfloor \frac{10000}{7}\rfloor =1428$$|A_7|=⌊\frac{10000}{7}⌋=1428$|A_(7)|=|__(10000)/(7)__|=1428|A_7| = \left\lfloor \frac{10000}{7} \right\rfloor = 1428$|A_7|=\lfloor \frac{10000}{7}\rfloor =1428$

Pairwise Intersections (lcm):

• $|A_2\cap A_3|=\lfloor \frac{10000}{6}\rfloor =1666$$|A_2\cap A_3|=⌊\frac{10000}{6}⌋=1666$|A_(2)nnA_(3)|=|__(10000)/(6)__|=1666|A_2 \cap A_3| = \left\lfloor \frac{10000}{6} \right\rfloor = 1666$|A_2\cap A_3|=\lfloor \frac{10000}{6}\rfloor =1666$
• $|A_2\cap A_5|=\lfloor \frac{10000}{10}\rfloor =1000$$|A_2\cap A_5|=⌊\frac{10000}{10}⌋=1000$|A_(2)nnA_(5)|=|__(10000)/(10)__|=1000|A_2 \cap A_5| = \left\lfloor \frac{10000}{10} \right\rfloor = 1000$|A_2\cap A_5|=\lfloor \frac{10000}{10}\rfloor =1000$
• $|A_2\cap A_7|=\lfloor \frac{10000}{14}\rfloor =714$$|A_2\cap A_7|=⌊\frac{10000}{14}⌋=714$|A_(2)nnA_(7)|=|__(10000)/(14)__|=714|A_2 \cap A_7| = \left\lfloor \frac{10000}{14} \right\rfloor = 714$|A_2\cap A_7|=\lfloor \frac{10000}{14}\rfloor =714$
• $|A_3\cap A_5|=\lfloor \frac{10000}{15}\rfloor =666$$|A_3\cap A_5|=⌊\frac{10000}{15}⌋=666$|A_(3)nnA_(5)|=|__(10000)/(15)__|=666|A_3 \cap A_5| = \left\lfloor \frac{10000}{15} \right\rfloor = 666$|A_3\cap A_5|=\lfloor \frac{10000}{15}\rfloor =666$
• $|A_3\cap A_7|=\lfloor \frac{10000}{21}\rfloor =476$$|A_3\cap A_7|=⌊\frac{10000}{21}⌋=476$|A_(3)nnA_(7)|=|__(10000)/(21)__|=476|A_3 \cap A_7| = \left\lfloor \frac{10000}{21} \right\rfloor = 476$|A_3\cap A_7|=\lfloor \frac{10000}{21}\rfloor =476$
• $|A_5\cap A_7|=\lfloor \frac{10000}{35}\rfloor =285$$|A_5\cap A_7|=⌊\frac{10000}{35}⌋=285$|A_(5)nnA_(7)|=|__(10000)/(35)__|=285|A_5 \cap A_7| = \left\lfloor \frac{10000}{35} \right\rfloor = 285$|A_5\cap A_7|=\lfloor \frac{10000}{35}\rfloor =285$