Chapter 12 — Discrete Mathematics: Exercise Solutions
| Board: Tamil Nadu State Board (Samacheer Kalvi) | Class: 12 | Subject: Maths |
|---|
How to Use This Page
This page provides complete exercise solutions for Chapter 12 — Discrete Mathematics from the Tamil Nadu State Board Class 12 Maths textbook. Follow these steps for effective preparation:
1. Read the Key Concepts Quick Recap to refresh formulas, definitions, and key results before attempting problems. 2. Attempt each problem on your own first — write the solution in your notebook before checking the answer here. 3. Compare your working with the step-by-step solutions provided. Pay close attention to intermediate steps, not just the final answer. 4. Redo any problem you got wrong after understanding where you went wrong. 5. Use the Common Mistakes to Avoid section to catch errors before the exam. 6. Review the Exam Checklist the night before your exam for a quick final revision.
For truth table problems: always write all rows and show every intermediate column. For proof problems: state each step clearly with the reason. For graph/relation problems: draw the diagram where possible.
Key Concepts Quick Recap
Logic and Propositions
A proposition is a declarative statement that is either true (T) or false (F), but not both.
| Symbol | Name | Meaning |
|---|---|---|
| p ∧ q | Conjunction | p AND q — true only when both are true |
| p ∨ q | Disjunction | p OR q — false only when both are false |
| ¬p | Negation | NOT p — opposite truth value |
| p → q | Conditional | If p then q — false only when p is true and q is false |
| p ↔ q | Biconditional | p if and only if q — true when both have the same truth value |
Key Logical Equivalences
Tautology, Contradiction, and Contingency
- Tautology: A statement that is always true regardless of truth values.
- Contradiction: A statement that is always false regardless of truth values.
- Contingency: A statement that is neither a tautology nor a contradiction.
Relations
- A relation R from set A to set B is a subset of A × B.
- Reflexive: (a, a) ∈ R for every a ∈ A.
- Symmetric: If (a, b) ∈ R, then (b, a) ∈ R.
- Transitive: If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.
- Equivalence relation: Reflexive + Symmetric + Transitive.
Binary Operations
A binary operation * on a set S is a function from S × S → S.
- Closure: a * b ∈ S for all a, b ∈ S.
- Associative: (a b) c = a (b c).
- Commutative: a b = b a.
- Identity element e: a e = e a = a for all a ∈ S.
- Inverse: For each a, there exists b such that a * b = e.
Graph Theory Basics
- A graph G = (V, E) where V is the set of vertices and E is the set of edges.
- Degree of a vertex: number of edges incident to it.
- Handshaking lemma: Sum of degrees = 2 × (number of edges).
- Complete graph K_n: every vertex connected to every other vertex; has n(n-1)/2 edges.
Choose the Best Answer
The column for p ∨ ¬p is always T → tautology.
Fill in the Blanks
1. The negation of "p and q" is equivalent to "not p ______ not q." Answer: or (¬p ∨ ¬q)
2. A statement that is always true is called a ________. Answer: tautology
3. The contrapositive of p → q is ________. Answer: ¬q → ¬p
4. If (a, b) ∈ R and (b, a) ∈ R for all (a, b) ∈ R, then R is ________. Answer: symmetric
5. The identity element for a * b = a + b on the set of real numbers is ________. Answer: 0
6. The identity element for a * b = a × b on the set of non-zero real numbers is ________. Answer: 1
7. The number of rows in a truth table with 3 propositions is ________. Answer: 8 (since 2³ = 8)
8. The converse of p → q is ________. Answer: q → p
9. A relation that is reflexive, symmetric, and transitive is called an ________ relation. Answer: equivalence
10. The sum of degrees of all vertices in a graph equals twice the number of ________. Answer: edges
True or False
1. The converse and contrapositive of an implication are logically equivalent. Answer: False — The contrapositive (¬q → ¬p) is equivalent to p → q, but the converse (q → p) is not equivalent to p → q.
2. p ∨ ¬p is a tautology. Answer: True — For any proposition p, either p is true or its negation is true.
3. A binary operation on a set S must always be commutative. Answer: False — Commutativity is not a requirement for a binary operation. For example, matrix multiplication is not commutative.
4. Every equivalence relation is also a partial order. Answer: False — An equivalence relation is symmetric, while a partial order is antisymmetric. These are different types of relations.
5. The negation of p → q is p ∧ ¬q. Answer: True — ¬(p → q) ≡ ¬(¬p ∨ q) ≡ p ∧ ¬q.
6. A relation R on a set A is reflexive if (a, a) ∈ R for every a ∈ A. Answer: True — This is the definition of reflexivity.
7. The inverse element under a * b = a + b on real numbers is the negative of the element. Answer: True — For a, the inverse is -a, since a + (-a) = 0 = e.
8. Every complete graph is a connected graph. Answer: True — In a complete graph, every vertex is connected to every other vertex, so it is always connected.
9. The biconditional p ↔ q is true when p and q have different truth values. Answer: False — The biconditional is true when p and q have the SAME truth value.
10. If a relation R is symmetric and transitive, it must be reflexive. Answer: False — Symmetry and transitivity do not guarantee reflexivity. For example, the empty relation on a non-empty set is symmetric and transitive but not reflexive.
Match the Following
| Column A | Column B |
|---|---|
| 1. Conjunction | a. p ↔ q |
| 2. Disjunction | b. ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| 3. Negation | c. Always true |
| 4. Conditional | d. p ∧ q |
| 5. Biconditional | e. ¬p |
| 6. Tautology | f. If p is true and q is false, then F |
| 7. Contradiction | g. Always false |
| 8. Contrapositive | h. p → q |
| 9. De Morgan's (OR) | i. ¬q → ¬p |
| 10. Implication truth | j. p ∨ q |
| 1 → d | 2 → j | 3 → e | 4 → h | 5 → a | 6 → c | 7 → g | 8 → i | 9 → b | 10 → f |
|---|
Answer Briefly
Q1: What is a proposition? Give two examples and two non-examples. A: A proposition is a declarative statement that is either true or false, but not both. Examples: "Chennai is the capital of Tamil Nadu" (true), "5 + 3 = 10" (false). Non-examples: "What time is it?" (question, not a statement), "x + 1 = 5" (open sentence — truth depends on x).
Q2: State and prove De Morgan's first law using truth tables. A: De Morgan's first law: ¬(p ∧ q) ≡ ¬p ∨ ¬q.
The columns for ¬(p ∧ q) and ¬p ∨ ¬q are identical → law verified.
Q3: What is the difference between the converse and the contrapositive of p → q? A: The converse of p → q is q → p — it swaps the hypothesis and conclusion. The contrapositive of p → q is ¬q → ¬p — it swaps AND negates both. The contrapositive is logically equivalent to the original implication, but the converse is not.
Q4: Define a binary operation. What properties must it satisfy for closure? A: A binary operation on a set S is a rule that assigns to every ordered pair (a, b) of elements in S exactly one element a b in S. For closure, the result a * b must belong to S for every a, b ∈ S. For example, subtraction is closed on integers (a − b is always an integer) but not on natural numbers (3 − 5 = −2 is not a natural number).
Q5: When is a relation called an equivalence relation? Give an example. A: A relation R on a set A is an equivalence relation if it is: 1. Reflexive: (a, a) ∈ R for every a ∈ A 2. Symmetric: If (a, b) ∈ R then (b, a) ∈ R 3. Transitive: If (a, b) ∈ R and (b, c) ∈ R then (a, c) ∈ R
Example: The relation "has the same remainder when divided by 3" on the set {1, 2, 3, 4, 5, 6, 7, 8, 9} is an equivalence relation. It is reflexive (every number has the same remainder as itself), symmetric (if a has the same remainder as b, then b has the same remainder as a), and transitive (if a and b have the same remainder, and b and c have the same remainder, then a and c have the same remainder).
Answer in Detail
Common Mistakes to Avoid
1. Wrong implication truth values: Remember, p → q is false ONLY when p is true and q is false. In all other cases, it is true. Students often get row 3 wrong (p = F, q = T gives T, not F).
2. Confusing converse and contrapositive: The converse of p → q is q → p (NOT equivalent). The contrapositive is ¬q → ¬p (equivalent). Do not use them interchangeably.
3. Missing rows in truth tables: For n propositions, you need 2ⁿ rows. Two variables → 4 rows. Three variables → 8 rows. Always list all combinations systematically (TT, TF, FT, FF for 2 variables).
4. Skipping intermediate columns: Never jump directly to the final column. Show each connective in its own column. Examiners award marks for intermediate steps.
5. Wrong De Morgan's law application: ¬(p ∧ q) = ¬p ∨ ¬q (OR, not AND). ¬(p ∨ q) = ¬p ∧ ¬q (AND, not OR). Students often reverse these.
6. Forgetting to verify closure for binary operations: Before checking other properties, verify closure first. If the operation is not closed, it is not even a valid binary operation on the set.
7. Confusing identity and inverse elements: The identity element e satisfies a e = a. The inverse of a satisfies a a⁻¹ = e. These are different. Do not mix them up.
8. Incomplete equivalence relation proofs: You must verify ALL THREE properties — reflexive, symmetric, and transitive. Skipping any one is an automatic loss of marks.
9. Not writing the final conclusion: After constructing a truth table, always write whether the statement is a tautology, contradiction, or contingency. After verifying properties, always state the final conclusion (e.g., "Therefore R is an equivalence relation").
10. Arithmetic errors in binary operation problems: When finding identity and inverse, solve the equation carefully. Common mistake: in a * b = a + b − 1, the identity is e = 1 (not e = 0). Double-check by substituting back.
Exam Checklist
Before submitting your exam paper, verify the following:
- [ ] Truth tables have all rows: 2ⁿ rows for n variables, with all combinations listed systematically.
- [ ] Intermediate columns are shown: Each logical connective gets its own column. No shortcuts.
- [ ] Final classification is written: After each truth table, state "tautology," "contradiction," or "contingency."
- [ ] Logical symbols are used consistently: Do not mix ∧ with "and" or ∨ with "or" in the same proof.
- [ ] De Morgan's laws are applied correctly: AND ↔ OR when negating compound statements.
- [ ] Implication truth values are correct: False only when p = T and q = F.
- [ ] Equivalence relation proofs cover all three properties: Reflexive, Symmetric, and Transitive — with a final conclusion.
- [ ] Binary operation identity is verified both ways: Check a e = a AND e a = a.
- [ ] Inverse is verified: Show that a a⁻¹ = e AND a⁻¹ a = e.
- [ ] Graph problems include the handshaking lemma check: Sum of degrees = 2 × number of edges.
- [ ] Equivalence classes are listed completely: No element is missed or repeated.
- [ ] Final answers are boxed or clearly highlighted: Make it easy for the examiner to find your answer.
- [ ] All steps in proofs are justified: Write the reason next to each step (e.g., "by De Morgan's law," "by definition of reflexive").