Discrete Structures Notes

explain every topic theory and example in detail

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 1/23
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 2/23
 Discrete Structures – Complete Notes with Theory and Examples

Unit 1: Set Theory, Relations and Functions

1. Set Theory

Definition of Set
A set is a well-defined collection of objects.

Examples:

A = {1,2,3,4}

V = {a,e,i,o,u}

The objects inside a set are called elements or members.

If an element belongs to a set:

2∈A

If an element does not belong:

5∉A

Types of Sets
1. Empty Set (Null Set)

A set with no elements.

Example:

A = {}
Number of students with age below 1 year in college.

2. Singleton Set

A set having only one element.

Example:

A = {5}

3. Finite Set

A set having limited elements.

Example:
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 3/23
 Example:

A = {1,2,3,4}

4. Infinite Set

A set having unlimited elements.

Example:

Natural numbers N = {1,2,3,...}

5. Equal Sets

Two sets having exactly same elements.

Example:

A = {1,2,3}
B = {3,2,1}

Then A = B

6. Subset

A ⊆ B if every element of A is also in B.

Example:

A = {1,2}
B = {1,2,3,4}

Then A ⊆ B

7. Proper Subset

A ⊂ B means A is subset of B and A ≠ B.

2. Operations on Sets

Union
The union contains all elements from both sets.
A ∪ B = {x : x ∈ A or x ∈ B}

Example:

A = {1,2,3}

B = {3,4,5}

A ∪ B = {1,2,3,4,5}

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 4/23
 Intersection
Contains common elements.
A ∩ B = {x : x ∈ A and x ∈ B}

Example:

A = {1,2,3}
B = {2,3,4}

A ∩ B = {2,3}

Difference
Elements of A not in B.

A − B = {x : x ∈ A and x ∉ B}
Example:

A = {1,2,3,4}
B = {2,4}

A − B = {1,3}

Complement
Elements not in A.

A' = U − A
Example:

U = {1,2,3,4,5}
A = {1,3}

A' = {2,4,5}

3. Laws of Set Theory

Commutative Laws
A∪B=B∪AA∩B=B∩A

Associative Laws
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 5/23
 Associative Laws
(A ∪ B) ∪ C = A ∪ (B ∪ C) (A ∩ B) ∩ C = A ∩ (B ∩ C)

Distributive Laws
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

De Morgan’s Laws
(A ∪ B)' = A' ∩ B' (A ∩ B)' = A' ∪ B'
Example: If

U = {1,2,3,4,5,6}
A = {1,2,3}

B = {3,4}

Then: (A ∪ B)' = {5,6}

Also: A' = {4,5,6} B' = {1,2,5,6}

A' ∩ B' = {5,6}

Hence proved.

4. Cartesian Product

The Cartesian product of A and B is:

A × B = {(a,b) : a ∈ A and b ∈ B}
Example:

A = {1,2}

B = {a,b}

A × B = {(1,a),(1,b),(2,a),(2,b)}
Number of elements:

n(A × B) = n(A) × n(B)

5. Venn Diagrams

Venn diagrams visually represent sets.

Uses:

Union

I t ti
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 6/23
 Intersection
Complement

Difference

Example: If

A = students who play cricket

B = students who play football

Then intersection region represents students who play both games.

6. Relations

Definition
A relation from A to B is a subset of A × B.

Example:

A = {1,2}
B = {a,b}

Relation: R = {(1,a),(2,b)}

7. Types of Relations

Reflexive Relation
Every element is related to itself.
(a,a) ∈ R

Example: R = {(1,1),(2,2),(3,3)}

Symmetric Relation
If (a,b) ∈ R then (b,a) ∈ R

Example: R = {(1,2),(2,1)}

Antisymmetric Relation
If (a,b) and (b,a) belong to R then a = b.

Example: ≤ relation.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 7/23
 Transitive Relation
If (a,b) and (b,c) belong to R then (a,c) belongs to R.
Example: If (1,2), (2,3) Then (1,3)

8. Equivalence Relation

A relation which is:

Reflexive
Symmetric

Transitive

Example: Relation “same remainder when divided by 2”.

9. Partial Ordering Relation

A relation that is:

Reflexive

Antisymmetric
Transitive

Example: Subset relation ⊆

10. Functions

A function maps every element of A to exactly one element of B.

f:A→B

Example: f(x) = x²
If A = {1,2,3} Then:

1→1

2→4

3→9

11. Types of Functions

One-One Function (Injective)

Different inputs have different outputs.
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 8/23
 Example: f(x)=2x

Onto Function (Surjective)

Every element of codomain has preimage.

Example: f(x)=x³

Bijective Function
Both one-one and onto.

Example: f(x)=x+1

Many-One Function
Different inputs may have same output.
Example: f(x)=x²

Because:

2² = 4

(-2)² = 4

12. Inverse Function

If f is bijective, inverse exists.

f⁻¹(y)=x
Example: If: f(x)=2x+1

Then: y=2x+1 x=(y−1)/2

So: f⁻¹(x)=(x−1)/2

13. Countable and Uncountable Sets

Countable Set
Elements can be listed.

Examples:

Natural numbers

Integers
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 9/23
 Uncountable Set
Cannot be listed completely.

Example: Real numbers.

14. Recursive Functions

Function defined using previous values.

Example: Factorial:
f(n)=n·f(n−1)

with f(1)=1

Example: 4! = 4×3×2×1 = 24

Unit 2: Lattice and Combinatorics

1. Lattice

A lattice is a partially ordered set in which every pair of elements has:

Greatest Lower Bound (GLB)

Least Upper Bound (LUB)

Meet and Join

Meet (∧)

Greatest lower bound.

Join (∨)

Least upper bound.

Example: For divisibility:

Meet = GCD

Join = LCM

2. Properties of Lattices

Idempotent Law
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 10/23
 A∨A=AA∧A=A

Commutative Law
A∨B=B∨A

Associative Law
(A ∨ B) ∨ C = A ∨ (B ∨ C)

Absorption Law
A ∨ (A ∧ B)=A

3. Bounded Lattice

Has greatest and least elements.

Greatest element = 1 Least element = 0

4. Complemented Lattice

Each element has complement.

Example: Boolean algebra.

5. Hasse Diagram

Graphical representation of partially ordered sets.

Used to avoid drawing reflexive and transitive edges.

Example: Divisors of 12: 1,2,3,4,6,12

6. Ordered Set

A set with order relation.

Example: (N, ≤)

7. Well Ordered Set

Every non-empty subset has smallest element.

Example: Natural numbers.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 11/23
 8. Isomorphic Ordered Sets

Two ordered sets having same structure.

9. Combinatorics

Study of counting.

10. Fundamental Counting Principle

If one operation can occur in m ways and another in n ways:

Total ways = m × n
Example: 3 shirts and 2 pants.
Total combinations = 3×2 = 6

11. Permutation

Arrangement of objects.

Formula:
genui{"math_block_widget_always_prefetch_v2":{"content":"^nP_r=\frac{n!}{(n-r)!}"}}

Example: Arrange 3 letters from ABCD.

4P3 = 24

12. Combination

Selection of objects.
Formula:

genui{"math_block_widget_always_prefetch_v2":{"content":"^nC_r=\frac{n!}{r!(n-r)!}"}}
Example: Choose 2 students from 4.
4C2 = 6

13. Binomial Theorem

Expansion:

genui{"math_block_widget_always_prefetch_v2":{"content":"
(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k"}}
Example: (a+b)² = a²+2ab+b²

14. Recurrence Relation

D fi i l
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 12/23
 Defines sequence recursively.
Example:
an = an−1 + 2

with a1=1
Sequence: 1,3,5,7...

15. Linear Recurrence Relation

Example:
an = 2an−1 + 3

16. Generating Function

Used to solve recurrence relations.

Example: Sequence: 1,1,1,1...
Generating function:

1/(1−x)

17. Pigeonhole Principle

If more pigeons than holes: At least one hole contains more than one pigeon.
Example: 13 people in a room. At least two have same birth month.

Unit 3: Logic and Algebraic Structures

1. Propositional Logic

A proposition is a statement which is either true or false.

Examples:

“2+2=4” → True
“Delhi is in USA” → False

2. Logical Connectives

Negation
¬P

AND
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 13/23
 AND
P∧Q

OR
P∨Q

Implication
P→Q

Biconditional
P↔Q

3. Truth Tables

Example:

P Q P∧Q
T T T

T F F
F T F
F F F

4. Tautology

Always true.

Example: P ∨ ¬P

5. Contradiction

Always false.
Example: P ∧ ¬P

6. Logical Equivalence

Two statements with same truth values.

Example: P→Q ≡ ¬P∨Q

7. Predicate Logic

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 14/23
 Uses variables.
Example: P(x): x>5

8. Quantifiers

Universal Quantifier
∀x P(x)
Means P(x) true for all x.

Existential Quantifier
∃x P(x)
Means there exists at least one x.

9. Normal Forms

Conjunctive Normal Form (CNF)

AND of OR terms.

Disjunctive Normal Form (DNF)

OR of AND terms.

10. Finite State Machine

Machine with finite states.

Components:

States
Input

Output
Transition

Example: Traffic light system.

11. Algebraic Structures

Set with operation.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 15/23
 Examples:

Group

Ring
Field

12. Semigroup

Closure + Associativity.

13. Monoid

Semigroup + Identity element.

Example: (N,+)
Identity = 0

14. Group

Conditions:

Closure

Associativity
Identity
Inverse

Example: (Z,+)

15. Abelian Group

Commutative group.
Example: (a+b)=(b+a)

16. Cyclic Group

Generated by single element.

Example: Z6={0,1,2,3,4,5}

17. Cosets

If H subgroup of G:
Left coset: aH={ah:h∈H}

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 16/23
 18. Homomorphism

Structure preserving mapping.

f(a*b)=f(a)*f(b)

19. Isomorphism

Bijective homomorphism.
Two groups structurally same.

20. Rings

Set with addition and multiplication.

Example: Integers.

21. Fields

Ring where division possible except by zero.

Example: Real numbers.

Unit 4: Graph Theory

1. Graph

A graph consists of:

Vertices

Edges

Notation: G=(V,E)

2. Types of Graphs

Simple Graph
No loops or parallel edges.

Multigraph
Multiple edges allowed.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 17/23
 Weighted Graph
Edges have weights.

3. Directed Graph

Edges have directions.

Example: A→B

4. Planar Graph

Can be drawn without crossing edges.

Example: Square graph.

5. Euler Graph

Contains Euler circuit.

Condition: All vertices have even degree.

6. Hamiltonian Graph

Contains Hamiltonian cycle visiting each vertex once.

7. Euler Path and Circuit

Euler Path
Uses every edge once.

Euler Circuit
Starts and ends at same vertex.

8. Hamiltonian Path and Circuit

Hamiltonian Path
Visits every vertex once.

Hamiltonian Circuit
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 18/23
 Returns to starting point.

9. Trees

Connected graph without cycles.

Properties:

n vertices have n−1 edges.

10. Spanning Tree

Subgraph connecting all vertices.

11. Minimum Spanning Tree

Tree with minimum total weight.

Algorithms:

Kruskal’s Algorithm
Prim’s Algorithm

12. Shortest Path

Find minimum distance.

Algorithm: Dijkstra’s Algorithm.

13. Warshall’s Algorithm

Used to find transitive closure.

14. Breadth First Search (BFS)

Visits level by level.

Uses Queue.

Applications:

Shortest path

Networking

15. Depth First Search (DFS)

Explores deeply first.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 19/23
 Uses Stack.
Applications:

Maze solving
Cycle detection

16. Tree Traversals

Preorder
Root → Left → Right

Inorder
Left → Root → Right

Postorder
Left → Right → Root

17. Graph Coloring

Assign colors so adjacent vertices have different colors.

18. Chromatic Number

Minimum colors required.

Example: Triangle graph needs 3 colors.

19. Five Color Theorem

Any planar graph can be colored using at most 5 colors.

20. Graph Isomorphism

Two graphs structurally same.

Same:

Vertices
Edges

Degree sequence
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 20/23
 21. Graph Homomorphism

Mapping preserving adjacency.

If u and v connected in G, then f(u),f(v) connected in H.

Important Exam Tips

Frequently Asked Topics

Unit 1

Set identities

Equivalence relation
Types of functions
Inverse function

Unit 2

Permutation and Combination numericals

Recurrence relations
Pigeonhole principle
Hasse diagrams

Unit 3

Truth tables

CNF and DNF

Groups and subgroups
Homomorphism

Unit 4

BFS and DFS

Euler and Hamiltonian graphs

Minimum spanning tree
Graph coloring

Important Formulas

Permutation
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 21/23
 genui{"math_block_widget_always_prefetch_v2":{"content":"^nP_r=\frac{n!}{(n-r)!}"}}

Combination
genui{"math_block_widget_always_prefetch_v2":{"content":"^nC_r=\frac{n!}{r!(n-r)!}"}}

Binomial Expansion
genui{"math_block_widget_always_prefetch_v2":{"content":"
(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k"}}

Tree Property
genui{"math_block_widget_always_prefetch_v2":{"content":"e=v-1"}}
Where:

e = edges
v = vertices

Conclusion

Discrete Structures forms the mathematical foundation of computer science. It is important in:

Algorithms
Databases
Networking
Artificial Intelligence

Compiler Design
Cryptography
Data Structures

Mastering these topics improves logical thinking and problem-s

I’ve created detailed Discrete Structures notes covering all the topics from your syllabus with:

Theory explanations
Definitions
Properties
Important formulas
Worked examples

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 22/23
 Exam-focused concepts

The notes include:

Set Theory
Relations & Functions
Lattices
Combinatorics

Logic
Algebraic Structures
Graph Theory
BFS/DFS
Trees
Graph Coloring

Permutations & Combinations

Groups, Rings, Fields
And more.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 23/23