How should I prepare Discrete Mathematics?

Samacheer Kalvi 12th Maths Chapter 12 Exercise Solutions

Exercise Solutions Available

Step-by-step answers for all textbook questions in this chapter

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

De Morgan's Laws:
  ¬(p ∧ q) ≡ ¬p ∨ ¬q
  ¬(p ∨ q) ≡ ¬p ∧ ¬q

Contrapositive:
  p → q ≡ ¬q → ¬p

Double Negation:
  ¬(¬p) ≡ p

Distributive:
  p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
  p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

Implication:
  p → q ≡ ¬p ∨ q

Biconditional:
  p ↔ q ≡ (p → q) ∧ (q → p)

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

1. The negation of p → q is equivalent to:

Answer

(a) ¬p → ¬q
(b) p ∧ ¬q ✓
(c) ¬p ∨ q
(d) ¬q → ¬p

Answer(b) p ∧ ¬q

Proof:
  ¬(p → q) ≡ ¬(¬p ∨ q)      [since p → q ≡ ¬p ∨ q]
            ≡ p ∧ ¬q          [by De Morgan's law]

2. Which of the following is a tautology?

Answer

(a) p ∧ ¬p
(b) p ∨ ¬p ✓
(c) p ∧ q
(d) p → q

Answer(b) p ∨ ¬p

  p | ¬p | p ∨ ¬p
  T |  F  |   T
  F |  T  |   T

The column for p ∨ ¬p is always T → tautology.

3. The contrapositive of p → q is:

Answer

(a) q → p
(b) ¬p → ¬q
(c) ¬q → ¬p ✓
(d) q → ¬p

Answer(c) ¬q → ¬p — The contrapositive reverses and negates both parts.

4. An identity element e for * on a set S satisfies:

Answer

(a) a * e = a for some a ∈ S
(b) a e = e a = a for all a ∈ S ✓
(c) a * e = e for all a ∈ S
(d) a * a = e for all a ∈ S

Answer(b) — The identity must work for every element, and from both sides.

5. If R is a relation on a set A, then R is an equivalence relation if R is:

Answer

(a) Reflexive and Symmetric only
(b) Reflexive and Transitive only
(c) Reflexive, Symmetric, and Transitive ✓
(d) Symmetric and Transitive only

Answer(c) — All three properties are required for an equivalence relation.

6. The number of edges in a complete graph K_5 is:

Answer

(a) 5
(b) 10 ✓
(c) 20
(d) 25

Answer(b) 10

Number of edges in K_n = n(n-1)/2
For n = 5: 5(4)/2 = 10

7. De Morgan's law states that ¬(p ∧ q) is equivalent to:

Answer

(a) ¬p ∧ ¬q
(b) ¬p ∨ ¬q ✓
(c) p ∨ ¬q
(d) ¬p ∨ q

Answer(b) ¬p ∨ ¬q — The negation of AND becomes OR of the negations.

8. In a graph, the sum of degrees of all vertices equals:

Answer

(a) Number of edges
(b) 2 × number of edges ✓
(c) Number of vertices
(d) Number of vertices + number of edges

Answer(b) 2 × number of edges — This is the Handshaking Lemma.

9. The operation a * b = a + b - ab is:

Answer

(a) Not closed on real numbers
(b) Closed and commutative ✓
(c) Not commutative
(d) Not associative

Answer(b) Closed and commutative

Closure: a + b - ab is a real number for all real a, b. ✓
Commutative: a * b = a + b - ab = b + a - ba = b * a ✓

10. A statement that is always false is called:

Answer

(a) Tautology
(b) Contingency
(c) Contradiction ✓
(d) Converse

Answer(c) Contradiction — A statement that is false for every possible truth value assignment.

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

Answer

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.

 p | q | p∧q | ¬(p∧q) | ¬p | ¬q | ¬p∨¬q
 T | T |  T  |   F    |  F |  F |   F
 T | F |  F  |   T    |  F |  T |   T
 F | T |  F  |   T    |  T |  F |   T
 F | F |  F  |   T    |  T |  T |   T

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.

Example: p → q = "If it rains, the ground is wet."
Converse:     "If the ground is wet, it rains."        (NOT equivalent)
Contrapositive: "If the ground is not wet, it does not rain." (EQUIVALENT)

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).

Q6: State and explain the handshaking lemma.

Answer

A: The handshaking lemma states that the sum of the degrees of all vertices in a graph equals twice the number of edges. In formula: Σ deg(v) = 2	E	.

Why: Each edge connects two vertices, so it contributes 1 to the degree
of each of its endpoints. Thus, every edge is counted twice in the
sum of degrees.

Example: A graph with 3 vertices of degrees 2, 3, and 1:
Sum = 2 + 3 + 1 = 6
Number of edges = 6/2 = 3

Answer in Detail

Q1: Construct the truth table for (p → q) ∧ (q → r) → (p → r). Is it a tautology? Prove your answer.

Answer

A: This statement expresses the transitive property of implication. We construct the truth table step by step.

 p | q | r | p→q | q→r | (p→q)∧(q→r) | p→r | (p→q)∧(q→r)→(p→r)
 T | T | T |  T  |  T  |      T        |  T  |         T
 T | T | F |  T  |  F  |      F        |  F  |         T
 T | F | T |  F  |  T  |      F        |  T  |         T
 T | F | F |  F  |  T  |      F        |  F  |         T
 F | T | T |  T  |  T  |      T        |  T  |         T
 F | T | F |  T  |  F  |      F        |  T  |         T
 F | F | T |  T  |  T  |      T        |  T  |         T
 F | F | F |  T  |  T  |      T        |  T  |         T

The final column is all T's, so (p → q) ∧ (q → r) → (p → r) is a tautology. This is known as the hypothetical syllogism — if p implies q and q implies r, then p implies r.

Q2: Show that p → q is logically equivalent to its contrapositive ¬q → ¬p using truth tables. Also show that the converse q → p is NOT equivalent.

Answer

Part 1: p → q ≡ ¬q → ¬p

 p | q | ¬p | ¬q | p→q | ¬q→¬p
 T | T |  F |  F |  T  |   T
 T | F |  F |  T |  F  |   F
 F | T |  T |  F |  T  |   T
 F | F |  T |  T |  T  |   T

The columns for p → q and ¬q → ¬p are identical → they are logically equivalent.

Part 2: q → p is NOT equivalent to p → q

 p | q | p→q | q→p
 T | T |  T  |  T
 T | F |  F  |  T    ← Different!
 F | T |  T  |  F    ← Different!
 F | F |  T  |  T

Row 2 and Row 3 show different values → q → p is NOT equivalent to p → q.

This is a critical distinction. The contrapositive preserves meaning, but the converse does not.

Q3: Verify the two De Morgan's laws using truth tables.

Answer

Law 1: ¬(p ∧ q) ≡ ¬p ∨ ¬q

 p | q | p∧q | ¬(p∧q) | ¬p | ¬q | ¬p∨¬q
 T | T |  T  |   F    |  F |  F |   F
 T | F |  F  |   T    |  F |  T |   T
 F | T |  F  |   T    |  T |  F |   T
 F | F |  F  |   T    |  T |  T |   T

Columns ¬(p ∧ q) and ¬p ∨ ¬q match → Law 1 verified.

Law 2: ¬(p ∨ q) ≡ ¬p ∧ ¬q

 p | q | p∨q | ¬(p∨q) | ¬p | ¬q | ¬p∧¬q
 T | T |  T  |   F    |  F |  F |   F
 T | F |  T  |   F    |  F |  T |   F
 F | T |  T  |   F    |  T |  F |   F
 F | F |  F  |   T    |  T |  T |   T

Columns ¬(p ∨ q) and ¬p ∧ ¬q match → Law 2 verified.

Q4: On the set S = {1, 2, 3, 4, 5, 6}, define R by a R b if (a − b) is divisible by 3. Show that R is an equivalence relation. Find its equivalence classes.

Answer

Step 1: Reflexive For any a ∈ S, a − a = 0, and 0 is divisible by 3. So (a, a) ∈ R. R is reflexive. ✓

Step 2: Symmetric If (a, b) ∈ R, then (a − b) is divisible by 3. Then (b − a) = −(a − b) is also divisible by 3. So (b, a) ∈ R. R is symmetric. ✓

Step 3: Transitive If (a, b) ∈ R and (b, c) ∈ R, then (a − b) and (b − c) are divisible by 3. Then (a − c) = (a − b) + (b − c) is also divisible by 3. So (a, c) ∈ R. R is transitive. ✓

Since R is reflexive, symmetric, and transitive, R is an equivalence relation.

Equivalence classes:

[1] = {a : (a - 1) divisible by 3} = {1, 4}    (remainder 1 when divided by 3)
[2] = {a : (a - 2) divisible by 3} = {2, 5}    (remainder 2 when divided by 3)
[3] = {a : (a - 3) divisible by 3} = {3, 6}    (remainder 0 when divided by 3)

The equivalence classes partition S into three subsets: {1, 4}, {2, 5}, {3, 6}.

Q5: For the binary operation a * b = a + b − 1 on the set of integers, verify closure, find the identity element, and find the inverse of an element a.

Answer

Closure: For any integers a and b, a + b − 1 is an integer (since sum of integers minus 1 is an integer). The operation is closed on integers. ✓

Identity element: We need e such that a * e = a for all a.

a * e = a + e - 1 = a
Therefore: e - 1 = 0
Therefore: e = 1

Verify: a 1 = a + 1 − 1 = a ✓ and 1 a = 1 + a − 1 = a ✓

The identity element is 1.

Inverse element: For each a, we need a⁻¹ such that a * a⁻¹ = e = 1.

a * a⁻¹ = a + a⁻¹ - 1 = 1
Therefore: a⁻¹ = 1 - a + 1 = 2 - a

Verify: a * (2 − a) = a + (2 − a) − 1 = 1 ✓

The inverse of a is 2 − a.

Commutativity (bonus): a b = a + b − 1 = b + a − 1 = b a. The operation is commutative. ✓

Associativity (bonus):

(a * b) * c = (a + b - 1) * c = (a + b - 1) + c - 1 = a + b + c - 2
a * (b * c) = a * (b + c - 1) = a + (b + c - 1) - 1 = a + b + c - 2

Both are equal → the operation is associative. ✓

Therefore, (ℤ, *) forms an abelian group.

Q6: Draw the complete graph K₄ and find the degree of each vertex, the total number of edges, and verify the handshaking lemma.

Answer

Complete graph K₄ has 4 vertices, each connected to every other vertex.

Each vertex has degree 3 (connected to the other 3 vertices).

Number of edges:

|E| = n(n-1)/2 = 4(3)/2 = 6

The edges are: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4).

Verification of handshaking lemma:

Sum of degrees = deg(1) + deg(2) + deg(3) + deg(4)
              =    3    +    3    +    3    +    3
              =    12

2 × |E| = 2 × 6 = 12

Sum of degrees = 2 × |E| ✓

The handshaking lemma is verified.

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").

Frequently Asked Questions

Practise truth tables, logical connectives, graph basics, and step-by-step verification problems. Presentation matters in this chapter.