DISCRETE MATHEMATICS NOTES
([Link]. Computer Science)
Unit: Discrete Mathematics
(Simple English – Around 10 Handwritten Pages)
PAGE 1 – INTRODUCTION TO DISCRETE
MATHEMATICS
Definition
Discrete Mathematics is the branch of mathematics that deals with countable, distinct, and
separate values instead of continuous values. It provides the mathematical foundation for
computer science.
Definition by Kenneth H. Rosen
"Discrete Mathematics is the study of mathematical structures that are fundamentally discrete
rather than continuous."
Need for Discrete Mathematics
Used in Computer Science.
Helps in algorithm design.
Supports database management.
Used in cryptography.
Helps in network design.
Used in artificial intelligence.
Supports software engineering.
Solves logical and computational problems.
Applications
Computer Programming
Data Structures
Artificial Intelligence
Database Systems
Network Security
Cryptography
Digital Circuits
Compiler Design
Robotics
Machine Learning
PAGE 2 – SET THEORY
Definition
A Set is a well-defined collection of distinct objects called elements.
Example
A = {1, 2, 3, 4, 5}
B = {2, 4, 6, 8}
Types of Sets
1. Empty Set (Null Set)
A set with no elements.
Example:
A={}
2. Singleton Set
A set containing only one element.
Example:
A = {5}
3. Finite Set
A set having a limited number of elements.
Example:
{10,20,30}
4. Infinite Set
A set having unlimited elements.
Example:
{1,2,3,4,...}
Operations on Sets
Union (A ∪ B)
Intersection (A ∩ B)
Difference (A − B)
Complement (A')
Cartesian Product (A × B)
PAGE 3 – RELATIONS
Definition
A Relation is a subset of the Cartesian product of two sets.
If A and B are sets, then
R⊆A×B
Example
A = {1,2}
B = {a,b}
R = {(1,a), (2,b)}
Types of Relations
Reflexive Relation
Every element is related to itself.
Example:
(1,1), (2,2), (3,3)
Symmetric Relation
If (a,b) belongs to R, then (b,a) also belongs to R.
Transitive Relation
If (a,b) and (b,c) belong to R, then (a,c) also belongs to R.
Equivalence Relation
A relation that is:
Reflexive
Symmetric
Transitive
PAGE 4 – FUNCTIONS
Definition
A Function is a special type of relation in which every element of one set is associated with
exactly one element of another set.
f:A→B
Example
A = {1,2,3}
B = {2,4,6}
f(1)=2
f(2)=4
f(3)=6
Types of Functions
One-to-One (Injective)
Each input has a unique output.
Onto (Surjective)
Every element in the codomain has at least one pre-image.
One-to-One Onto (Bijective)
Both one-to-one and onto.
Many-to-One
Many inputs map to one output.
Applications
Database mapping
Compiler design
Cryptography
Computer graphics
PAGE 5 – PROPOSITIONAL LOGIC
Definition
A Proposition is a declarative statement that is either True (T) or False (F).
Examples
2 + 3 = 5 (True)
7 < 4 (False)
Logical Connectives
AND (∧)
True only if both statements are true.
OR (∨)
True if at least one statement is true.
NOT (¬)
Reverses the truth value.
Implication (→)
"If P then Q."
Biconditional (↔)
True when both statements have the same truth value.
Truth Table
P∧ P∨
PQ ¬P
Q Q
T T T T F
T F F T F
F T F T T
F F F F T
PAGE 6 – PREDICATE LOGIC
Definition
Predicate Logic extends propositional logic by using variables and quantifiers.
Quantifiers
Universal Quantifier (∀)
Means "For all."
Example:
∀x (x > 0)
Existential Quantifier (∃)
Means "There exists."
Example:
∃x (x = 5)
Advantages
Expresses complex statements.
Used in Artificial Intelligence.
Used in databases.
Used in theorem proving.
Applications
Knowledge Representation
Logic Programming
Artificial Intelligence
Database Queries
PAGE 7 – GRAPH THEORY
Definition
A Graph is a mathematical structure consisting of Vertices (Nodes) and Edges (Links).
G = (V, E)
Where:
V = Set of Vertices
E = Set of Edges
Types of Graphs
Simple Graph
No loops or parallel edges.
Directed Graph (Digraph)
Edges have directions.
Undirected Graph
Edges have no directions.
Complete Graph
Every vertex is connected to every other vertex.
Connected Graph
Every vertex can be reached from every other vertex.
Applications
Social Networks
Computer Networks
GPS Navigation
Web Page Links
Routing Algorithms
PAGE 8 – TREES
Definition
A Tree is a connected graph with no cycles.
Characteristics
One root node.
Parent-child relationship.
No loops.
Connected structure.
Types of Trees
Binary Tree
Binary Search Tree (BST)
AVL Tree
B-Tree
Expression Tree
Applications
File Systems
Database Indexing
Compiler Design
Decision Trees
Artificial Intelligence
Advantages
Fast searching.
Easy insertion and deletion.
Efficient data organization.
PAGE 9 – COMBINATORICS
Definition
Combinatorics is the study of counting, arranging, and selecting objects.
Principle of Counting
If one task can be done in m ways and another in n ways, then both together can be done in:
m × n ways
Permutation
Arrangement where order matters.
Formula
nPr = n! / (n − r)!
Example:
Arrange 3 students from 5 students.
5P3 = 60
Combination
Selection where order does not matter.
Formula
nCr = n! / r!(n − r)!
Example:
Choose 3 students from 5 students.
5C3 = 10
Applications
Password generation
Scheduling
Probability
Cryptography
PAGE 10 – BOOLEAN ALGEBRA,
APPLICATIONS, AND CONCLUSION
Boolean Algebra
Boolean Algebra deals with logical values True (1) and False (0).
Basic Operations
AND
OR
NOT
Boolean Laws
Identity Law
Complement Law
Commutative Law
Associative Law
Distributive Law
De Morgan's Laws
Applications of Boolean Algebra
Digital Circuits
Logic Gates
Computer Architecture
Switching Circuits
Microprocessors
Real-Life Applications of Discrete Mathematics
Computer Programming
Database Management Systems
Cryptography
Artificial Intelligence
Machine Learning
Data Mining
Computer Networks
Software Engineering
Cyber Security
Robotics
E-Commerce
Search Engines
Advantages of Discrete Mathematics
Improves logical thinking.
Helps solve computational problems.
Supports efficient algorithm design.
Essential for modern computer science.
Provides a foundation for advanced technologies.
Conclusion
Discrete Mathematics is one of the most important subjects in Computer Science. It provides
the mathematical foundation for programming, algorithms, databases, cryptography, networking,
artificial intelligence, and software engineering. Concepts such as sets, relations, functions,
logic, graph theory, trees, combinatorics, and Boolean algebra help solve complex
computational problems efficiently. Because of its wide range of applications in modern
technology, Discrete Mathematics is an essential subject for every computer science student and
professional.
These notes are written in simple English and are suitable for [Link]. Computer Science
examinations, covering approximately 10 handwritten pages.