Discrete Mathematics – Complete Exam-Oriented Notes (All Units Fully Expanded)

Discrete Mathematics is a logic-heavy subject. You do not pass it by memorizing definitions randomly. You pass it by understanding structures, properties, and how definitions connect. These notes are written exactly in the way examiners expect answers: precise definitions, correct terminology, formulas where needed, and logical flow.

Units Index

• Unit I – Set Theory, Relations, POSET & Lattices
• Unit II – Functions & Boolean Algebra (Including Karnaugh Maps)
• Unit III – Propositional & Predicate Logic
• Unit IV – Algebraic Structures (Groups, Rings, Fields)
• Unit V – Graph Theory
• Previous Year Solved Question
• Guess Question Paper

Unit I – Set Theory, Relations, POSET & Lattices

1. Set Theory

A set is a well-defined collection of distinct objects. “Well-defined” means there is no confusion about membership. If ambiguity exists, it is not a valid set.

Notation:

• a ∈ A → a belongs to A
• a ∉ A → a does not belong to A

Types of Sets

• Finite Set
• Infinite Set
• Empty Set (∅)
• Universal Set (U)
• Subset (A ⊆ B)

Operations on Sets

• Union: A ∪ B
• Intersection: A ∩ B
• Difference: A − B
• Complement: A'

Important Laws (Very Important for Exams)

• Commutative Law
• Associative Law
• Distributive Law
• Idempotent Law
• De Morgan’s Laws

De Morgan’s Laws:

(A ∪ B)’ = A’ ∩ B’
(A ∩ B)’ = A’ ∪ B’

2. Relations

A relation R from set A to set B is any subset of A × B.

Types of Relations

• Reflexive
• Symmetric
• Transitive
• Antisymmetric

Composite Relations

If R ⊆ A × B and S ⊆ B × C, then S ∘ R ⊆ A × C.

Equivalence Relation

A relation that is reflexive, symmetric, and transitive.

Recursive Relations

Defined using base conditions and recursive rules. These are used in defining reachability and paths.

3. POSET (Partially Ordered Set)

A POSET is a set A with a relation R that is:

• Reflexive
• Antisymmetric
• Transitive

Hasse Diagram

A simplified diagram representing ordering without showing reflexive and transitive edges.

4. Lattices

A lattice is a POSET in which every pair of elements has:

• Join (∨)
• Meet (∧)

Types of Lattices

• Bounded Lattice
• Complemented Lattice
• Distributive Lattice
• Modular Lattice
• Complete Lattice

Unit II – Functions & Boolean Algebra

1. Functions

A function f: A → B assigns exactly one element of B to each element of A.

Types of Functions

• Injective (One-One)
• Surjective (Onto)
• Bijective

Composition of Functions

(f ∘ g)(x) = f(g(x))

Growth of Functions

• O(1)
• O(log n)
• O(n)
• O(n²)

2. Boolean Algebra

Boolean algebra works on binary values 0 and 1.

Basic Operations

• AND (·)
• OR (+)
• NOT (’)

Boolean Laws

• Identity Law
• Null Law
• Idempotent Law
• Complement Law
• De Morgan’s Laws

3. Karnaugh Map (K-Map)

Karnaugh Map is a graphical technique for simplifying Boolean expressions.

Rules for K-Map

• Group in powers of 2
• Use largest possible groups
• Groups can wrap around

K-Maps are used for 2-variable, 3-variable, and 4-variable Boolean functions.

Unit III – Theory of Logic

Propositions

A proposition is a statement with a definite truth value.

Logical Connectives

• AND
• OR
• NOT
• IMPLIES
• IFF

Truth Tables

Truth tables show outcomes for all possible combinations.

Tautology and Contradiction

• Tautology: Always true
• Contradiction: Always false

Inference Theory

• Modus Ponens
• Modus Tollens

Predicate Logic

Uses quantifiers:

• ∀ (For all)
• ∃ (There exists)

Unit IV – Algebraic Structures

Groups

A group (G, *) satisfies:

• Closure
• Associativity
• Identity
• Inverse

Lagrange’s Theorem

Order of subgroup divides order of group.

Rings

A ring has two operations: addition and multiplication.

Fields

A field is a ring where every non-zero element has a multiplicative inverse.

Unit V – Graph Theory

Graphs

A graph G = (V, E) where V is vertices and E is edges.

Types of Graphs

• Simple Graph
• Multigraph
• Bipartite Graph
• Planar Graph

Euler Path & Circuit

Euler path uses every edge exactly once.

Hamiltonian Path

Hamiltonian path visits each vertex once.

Graph Coloring

Assigning minimum colors so adjacent vertices differ.

Solved Previous Year Question Paper (BT-308 / TU-907)

🔹 SECTION A – Very Short Answer (2 Marks Each)

Q1. Define lattice with example.

Answer:
A lattice is a partially ordered set (POSET) in which every pair of elements has a least upper bound (join) and a greatest lower bound (meet).

Example:
Set {1, 2, 4} under divisibility ( | ) is a lattice.

• Join of (2,4) = 4

• Meet of (2,4) = 2

✍️ Always write “join and meet” → full marks.

Q2. Prove that a + a = a.

Answer:
Using Idempotent Law of Boolean Algebra:

$$a+a=a$$

This law states that repeating the same variable with OR does not change the result.

✔ Hence proved.

✍️ Just name the law. No long proof needed.

Q3. Construct the truth table for (p ∨ q) ∨ ¬p.

Conclusion: Always TRUE → Tautology

Q4. Define coset with example.

Answer:
Let G be a group and H a subgroup of G.
A left coset of H in G is:

$$aH=\{ah\mid h\in H\}$$

Example:
G = {0,1,2,3}, H = {0,2} under addition mod 4
Cosets:

• 0 + H = {0,2}

• 1 + H = {1,3}

Q5. Define chromatic number with example.

Answer:
The chromatic number of a graph is the minimum number of colors required to color its vertices such that no two adjacent vertices have the same color.

Example:

• Triangle graph → Chromatic number = 3

🔹 SECTION B – Short Answer (9 Marks Each)

Q6. Write a note on classification of functions.

Answer:

Let f : A → B be a function.

1. Injective (One-One):
   If f(a₁) = f(a₂) ⇒ a₁ = a₂

2. Surjective (Onto):
   Every element of B has at least one pre-image in A.

3. Bijective:
   Both injective and surjective.

4. Many-One:
   Two or more elements of A map to same element of B.

5. Into Function:
   Some elements of B are not images of A.

✍️ Draw arrow diagrams if space allows.

Q7. Explain quantifiers with example.

Answer:

Quantifiers specify how many elements satisfy a predicate.

1. Universal Quantifier (∀):

   $$\forall xP(x)$$

   Means “P(x) is true for all x”.

   Example:
   ∀x (x² ≥ 0)

2. Existential Quantifier (∃):

   $$\exists xP(x)$$

   Means “There exists at least one x”.

   Example:
   ∃x (x² = 4)

Q8. Prove that the fourth roots of unity form an abelian group.

Answer:

Fourth roots of unity:

$$\{1,-1,i,-i\}$$

Operation: Multiplication

1. Closure: Product of any two roots is in the set

2. Associativity: Multiplication is associative

3. Identity: 1

4. Inverse:

   • inverse of i is −i

5. Commutative:
   a × b = b × a

✔ Hence forms an Abelian group.

🔹 SECTION C – Descriptive (14 Marks Each)

Q9. If R and S are equivalence relations, prove R ∩ S is also equivalence.

Proof:

Let R and S be equivalence relations on A.

1. Reflexive:
   Since R and S are reflexive, (a,a) ∈ R and S ⇒ (a,a) ∈ R ∩ S

2. Symmetric:
   If (a,b) ∈ R ∩ S ⇒ in both R and S
   ⇒ (b,a) ∈ R and S ⇒ (b,a) ∈ R ∩ S

3. Transitive:
   If (a,b), (b,c) ∈ R ∩ S
   ⇒ in R and S ⇒ (a,c) ∈ R ∩ S

✔ Hence R ∩ S is an equivalence relation.

Q10(a). Use K-map to minimize F(A,B,C)=Σ(1,9,11,13,15).

Convert to binary (ABC):

⚠️ Exam Tip: Treat as 4_toggle variable question (ABCD).

Final minimized SOP:

$$F=A+BC$$

✍️ Draw K-map, make groups of 1s, then write expression.

Q10(b). Prove

$$ab+bc+ca=(a+b)(b+c)(c+a)$$

Proof:

Expand RHS:

$$(a+b)(b+c)(c+a)$$

First:

(a+b)(b+c)=ab+ac+b2+bc(a+b)(b+c) = ab + ac + b² + bc(a+b)(b+c)=ab+ac+b2+bc

Since b² = b:

$$=ab+ac+b+bc$$

Multiply by (c+a) and simplify using Boolean laws.

Final result:

$$=ab+bc+ca$$

✔ Hence proved.

Q11. Show that s is valid conclusion from premises

Premises:

1. p → q

2. p → r

3. ¬r

4. (q ∧ r) → s

5. s ∨ p

Solution:

From (2) and (3):
p → r and ¬r ⇒ ¬p (Modus Tollens)

From (5): s ∨ p and ¬p ⇒ s

✔ Valid conclusion.

Q12. State and prove Lagrange’s Theorem.

Statement:
In a finite group G, the order of any subgroup H divides the order of G.

Proof:
Cosets of H partition G.
All cosets have equal number of elements as H.

$$|G|=|H|\times \text{number of cosets}$$

✔ Hence |H| divides |G|.

Q13(a). Write a note on graph coloring.

Graph coloring assigns colors to vertices such that no adjacent vertices share same color.

Applications:

• Scheduling

• Map coloring

• Register allocation

Chromatic number = minimum colors required.

Q13(b). Explain bipartite and planar graphs.

Bipartite Graph:
Vertices can be divided into two disjoint sets; edges only between sets.

Example: Complete bipartite graph K₃,₂

Planar Graph:
Graph drawable without edge crossing.

Example: Tree graphs, K₄ 

🔮 GUESS QUESTION PAPER – WITH COMPLETE SOLUTIONS

Time: 3 Hours
Maximum Marks: 70

🔹 SECTION–A (Very Short Answer)

Attempt all questions
5 × 2 = 10 marks

Q1. Define POSET with one example.

Q2. State De Morgan’s laws.

Q3. What is an injective function?

Q4. Define tautology.

Q5. What is a Hamiltonian path?

✅ SECTION–A SOLUTIONS

Ans 1. POSET

A Partially Ordered Set (POSET) is a set with a relation that is reflexive, antisymmetric, and transitive.

Example:
Set {1,2,4} under divisibility.

Ans 2. De Morgan’s Laws

(A+B)′=A′⋅B′(A + B)' = A' \cdot B'(A+B)′=A′⋅B′ (A⋅B)′=A′+B′(A \cdot B)' = A' + B'(A⋅B)′=A′+B′

Ans 3. Injective Function

A function f is injective if:

f(a1)=f(a2)⇒a1=a2f(a_1) = f(a_2) \Rightarrow a_1 = a_2f(a1​)=f(a2​)⇒a1​=a2​

Ans 4. Tautology

A proposition that is always true for all truth values.

Ans 5. Hamiltonian Path

A path that visits each vertex exactly once.

🔹 SECTION–B (Short Answer)

Attempt any TWO
2 × 9 = 18 marks

Q6. Explain types of relations with examples.

Q7. Explain Boolean algebra laws with examples.

Q8. Explain Euler path and Euler circuit.

✅ SECTION–B SOLUTIONS

Ans 6. Types of Relations

Let R be a relation on set A.

1. Reflexive: (a,a) ∈ R
   Example: ≤ relation

2. Symmetric: (a,b) ⇒ (b,a)
   Example: a = b

3. Transitive: (a,b) and (b,c) ⇒ (a,c)
   Example: ≥ relation

4. Equivalence Relation:
   Reflexive + Symmetric + Transitive

Ans 7. Boolean Algebra Laws

1. Identity Law:
   A + 0 = A, A · 1 = A

2. Null Law:
   A + 1 = 1, A · 0 = 0

3. Idempotent Law:
   A + A = A

4. Complement Law:
   A + A' = 1

5. De Morgan’s Law:
   (A + B)' = A' · B'

Ans 8. Euler Path & Circuit

Euler Path:
Uses every edge exactly once.

Euler Circuit:
Euler path that starts and ends at same vertex.

Condition:
• Euler Path → exactly 2 odd-degree vertices
• Euler Circuit → all vertices even degree

🔹 SECTION–C (Descriptive Answer)

Attempt any THREE
3 × 14 = 42 marks

Q9. Prove that every subgroup of a cyclic group is cyclic.

Q10.

(a) Minimize Boolean function using K-map:

$$F(A,B,C)=\Sigma (0,2,3,5,7)$$

(b) Prove:

$$(a+b)(a+c)=a+bc$$

Q11. Construct truth table and check validity:

Premises:
p → q
q → r
p
Conclusion: r

Q12. State and prove Lagrange’s theorem.

Q13.

(a) Explain graph coloring and chromatic number.
(b) Explain bipartite graphs with example.

✅ SECTION–C SOLUTIONS

Ans 9. Subgroup of cyclic group

Let G = ⟨a⟩ be a cyclic group.

Let H be a subgroup of G.

Let k be smallest positive integer such that aᵏ ∈ H.

Then:

H=⟨ak⟩H = \langle a^k \rangleH=⟨ak⟩

Hence H is cyclic.

✔ Proved.

Ans 10(a). K-map Minimization

Minterms:
0 → 000
2 → 010
3 → 011
5 → 101
7 → 111

After grouping 1s in K-map:

$$F=B+AC$$

Ans 10(b). Proof

LHS:

$$(a+b)(a+c)$$

Expand:

$$=a+ab+ac+bc$$

Using Boolean laws:

$$=a+bc$$

✔ Proved.

Ans 11. Validity using Truth Table

When premises are true, conclusion is true.

✔ Valid argument.

Ans 12. Lagrange’s Theorem

Statement:
Order of subgroup divides order of group.

Proof:
Cosets of H partition G.
All cosets have |H| elements.

$$|G|=|H|\times \text{number of cosets}$$

✔ Proved.

Ans 13(a). Graph Coloring

Graph coloring assigns colors to vertices so that adjacent vertices differ.

Chromatic number: Minimum colors required.

Applications:
• Scheduling
• Map coloring

Ans 13(b). Bipartite Graph

Vertices divided into two disjoint sets.

Edges only between sets.

Example: K₃,₂