Mathematics-I Notes
Subject Overview
Mathematics-I gives B.Sc IT students the discrete-math foundation for computer science — set theory and relations, the algebra of logic and mathematical induction, graph theory, and recursion/
Subject at a glance
4
Units
34
Topics
6
Credits
4
Infographics
Unit-wise Syllabus
4 units — open any unit for detailed topic-wise notes, diagrams and important exam questions
- Elements and methods of describing a set
- types of sets
- set operations (union, intersection, difference)
- Venn diagrams
- associative/distributive/De Morgan's laws
- duality
- partitioning of a set
- relation definitions and types
- graphs of relations
- domain/range/inverse/composite relations
- matrix representation of a relation
De Morgan's laws
(A ∪ B)' = A' ∩ B' and (A ∩ B)' = A' ∪ B'
Distributive law
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Cardinality
n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
Power set
A set with n elements has 2^n subsets
Study guide
Set theory and relations provide the language of data and logic. You study sets and their types, operations, Venn diagrams, the laws of set algebra including De Morgan's laws and duality, partitions, relations and their types, graphs of relations, domain, range, inverse and composite relations and matrix representation. Draw a Venn diagram for each law to see why it holds.
- Propositions and logic operations
- truth tables
- arguments and validity
- propositions generated by a set
- equivalence and implication laws of logic
- mathematical systems
- quantifiers
- principle of mathematical induction
p ∧ q (AND)
F
F
p ∨ q (OR)
T
F
p → q (implies)
F
T
p ↔ q (iff)
F
T
Study guide
You study propositions, logical operations, truth tables, arguments and validity, equivalence and implication laws, quantifiers and the principle of mathematical induction. Practise writing an induction proof in three clear steps: base case, assumption and inductive step.
- Simple and multi-graphs
- directed and undirected graphs
- Eulerian and Hamiltonian graphs
- graph connectivity
- graph traversals
- graph optimization
- graph coloring
- trees and spanning trees
Visits every
Edge exactly once
Vertex exactly once
Circuit exists if
Connected and all degrees even
No simple rule (NP-complete)
Path exists if
Exactly 0 or 2 odd-degree vertices
Hard to test
Example
Königsberg bridges
Travelling salesman
Study guide
Graph theory models networks. You study simple and multigraphs, directed and undirected graphs, Eulerian and Hamiltonian graphs, connectivity, traversals, optimisation, graph colouring, trees and spanning trees. Draw each graph type and test whether an Euler path exists.
- Recursion and its applications
- recurrence relations and common recurrence relations
- binomial theorem of positive index
- general term
- middle terms
- particular terms
- terms from the end
Expansion
(x + a)^n = Σ nCr x^(n−r) a^r
General term
T(r+1) = nCr x^(n−r) a^r
Number of terms
n + 1
Middle term (n even)
T(n/2 + 1)
Middle terms (n odd)
T((n+1)/2) and T((n+3)/2)
Study guide
You study recursion and recurrence relations, then the binomial theorem for positive index: general term, middle terms, particular terms and terms from the end. Practise finding specific terms of an expansion with the general term formula.
Why Mathematics-I Matters
Discrete mathematics is the language of computer science: sets underpin databases, logic underpins programming, graphs underpin networks and algorithms, and recursion underpins data structures. Strong fundamentals here make algorithm and AI papers easier.
How to Prepare for Mathematics-I
- Draw a diagram or truth table for every set and logic problem.
- Practise induction proofs and binomial term problems regularly.
- Connect each topic to a computing use, such as graphs to networks.
Mathematics-I: Frequently Asked Questions
Why is discrete mathematics important for IT?
It underpins data structures, algorithms, databases, networks and cryptography, which all rely on sets, logic, graphs and recurrence.
What is mathematical induction?
It is a proof technique that shows a statement is true for a first case and then proves that if it is true for one case it is true for the next.