Discrete Mathematics – MTH202
Semester: Fall 2025
Assignment No. 1 — Solved (Human-style)
Name: ______________________ Roll No: ______________________ Section: ______________________
Question 1 (Marks: 05)
Verify by using the laws of logic whether the following statement is a Tautology or not:
¬(¬q → p) → ¬q
Solution (step-by-step, human-readable):
1. Recall implication equivalence: (A → B) ≡ (¬A ∨ B).
So, (¬q → p) ≡ (¬(¬q) ∨ p) ≡ (q ∨ p).
2. Substitute into the main expression:
¬(¬q → p) → ¬q becomes ¬(q ∨ p) → ¬q.
3. Apply De Morgan: ¬(q ∨ p) ≡ (¬q ∧ ¬p). So we have (¬q ∧ ¬p) → ¬q.
4. Use implication equivalence again: (X → Y) ≡ (¬X ∨ Y).
So (¬q ∧ ¬p) → ¬q ≡ ¬(¬q ∧ ¬p) ∨ ¬q.
5. Apply De Morgan to the negation: ¬(¬q ∧ ¬p) ≡ (q ∨ p).
Hence expression becomes (q ∨ p) ∨ ¬q.
6. Re-associate: (q ∨ p) ∨ ¬q ≡ p ∨ (q ∨ ¬q).
But (q ∨ ¬q) is a tautology (always True), therefore p ∨ True = True.
Conclusion: The statement ¬(¬q → p) → ¬q is always True for all truth values of p and q.
Therefore it is a tautology.
Final Answer: □ The formula is a TAUTOLOGY.
Question 2 (Marks: 05)
Verify the validity of the following argument:
If a number is even, then it is divisible by 2.
∴ The number is not even.
The number is not divisible by 2.
Solution (human-style):
1. Translate into propositional form: Let E = 'number is even', D = 'number is divisible by 2'.
Premises: (1) E → D. (2) ¬D. Conclusion: ¬E.
2. Recognize the argument form:
E → D, ¬D ⊢ ¬E. This is exactly Modus Tollens (contrapositive argument):
From P → Q and ¬Q we infer ¬P. Modus Tollens is a valid rule of inference.
3. Check with a short truth reasoning: Whenever E → D is true and ¬D is true, ¬E must be
true.
Conclusion: The argument is LOGICALLY VALID by Modus Tollens.
Final Answer: □ The argument is valid.
Question 3 (Marks: 05)
Problem statement (concise):
In a college, 120 students have access to three software packages P, Q, R.
Given:
- 25 used none.
- 14 used only P.
- 22 used only Q.
- 11 used only R.
- A total of 18 students used both P and Q.
- 7 students used all three.
- Twice as many students used Q as used P.
Let x = |P| (total using P), y = |Q| (total using Q).
(i) Write a pair of simultaneous equations in x and y.
(ii) Solve for x and y.
Solution (human-style):
Step A — Break overlaps:
Given P∩Q total is 18 and P∩Q∩R is 7, so P∩Q only (i.e. P∩Q but not R) = 18 − 7 = 11.
Step B — Express |P| and |Q| in terms of disjoint regions:
|P| = (only P) + (P∩Q only) + (P∩R only) + (all three)
⇒ x = 14 + 11 + (P∩R only) + 7 ⇒ P∩R only = x − 32.
|Q| = (only Q) + (P∩Q only) + (Q∩R only) + (all three)
⇒ y = 22 + 11 + (Q∩R only) + 7 ⇒ Q∩R only = y − 40.
Step C — Total count of students who used at least one package:
Total students = 120, none used = 25, so at least one = 95.
Sum of all disjoint regions equals 95:
14 (only P) + 22 (only Q) + 11 (only R) + 11 (P∩Q only) + (P∩R only) + (Q∩R only) + 7 (all
three) = 95.
Replace P∩R only and Q∩R only using x and y:
14 + 22 + 11 + 11 + (x − 32) + (y − 40) + 7 = 95.
Simplify constants: (14+22+11+11+7) = 65 and (−32 −40) = −72, so left becomes x + y − 7.
Thus x + y − 7 = 95 ⇒ x + y = 102. (Equation 1)
Step D — Use twice-as-many condition: y = 2x. (Equation 2)
Therefore, the pair of simultaneous equations is:
(1) x + y = 102
(2) y = 2x
Solve: Substitute (2) into (1): x + 2x = 102 ⇒ 3x = 102 ⇒ x = 34.
Then y = 2x = 68.
Final Answer:
(i) Equations: x + y = 102, y = 2x.
(ii) x = 34, y = 68.
Question 4 (Marks: 05)
Verify by using a membership table that:
B − A = A^c ∩ B
Solution (human-style):
Explanation: B − A means elements that are in B and not in A. A^c ∩ B means elements that
are not in A and in B. These are the same idea; we verify by membership table below.
A B A^c B-A A^c ∩ B
0 0 1 0 0
0 1 1 1 1
1 0 0 0 0
1 1 0 0 0
Compare the last two columns of the table: they are identical for every row (0,1,0,0).
Conclusion: B − A = A^c ∩ B. Verified by membership table.
Prepared for: Discrete Mathematics – MTH202 (Assignment 1).
Note: Fill in your Name, Roll No and Section before submission.