A computer does not understand "a little bit more" or "almost true". Inside the machine everything is a 0 or a 1, a memory address is a whole number, a loop runs 7 times or 8 times but never 7.5 times, and an if condition is either true or false. The mathematics that describes such objects, things you can count one by one, is called Discrete Mathematics.
Discrete mathematics is the language in which computer science is written. Algorithms are analysed with counting and recurrences, databases are built on sets and relations, networks and maps are graphs, compilers use logic and automata, and cryptography lives on modular arithmetic and groups.
In this first chapter we see what "discrete" means, why the subject matters for programmers, university exams and GATE, which topics this tutorial covers, and the basic notation used in every later chapter. The real work starts in the next chapter, Propositional Logic.
What Does "Discrete" Mean?
A set of objects is discrete if its elements are separate and distinct, so that they can be listed (counted) one after another, with gaps between neighbouring values. Discrete Mathematics is the study of such structures: integers, logical statements, sets, relations, functions, graphs, finite structures and the ways of counting them.
The opposite is continuous mathematics (calculus, real analysis), where between any two values there are infinitely many others. Compare a staircase with a ramp: on a staircase you stand on step 3 or step 4; on a ramp you can stand anywhere.
Aspect | Discrete | Continuous |
|---|---|---|
Typical values | Integers, true/false, nodes of a network | Real numbers, time, distance |
Next value | After 4 comes 5; nothing in between | Between 4 and 5 lie 4.5, 4.51, 4.501, ... |
Main tools | Logic, counting, induction, recurrences, graphs | Limits, derivatives, integrals |
Typical question | "How many passwords of length 8 are possible?" | "How fast is the speed changing at t = 2 s?" |
Picture | Dots | A smooth curve |
Discrete (separate points) Continuous (no gaps)
• • • • • ________________________
1 2 3 4 5 1 2 3 4 5Note that "discrete" does not mean "finite". The integers ℤ are infinite but discrete: each integer has a clear next one. What matters is that the elements are separate and can be listed.
Why Computer Science Needs It
A digital computer is a finite, discrete machine: finitely many bits, each 0 or 1, changing in separate clock steps. So the mathematics that models it exactly is discrete. Here is where each topic of this tutorial shows up in practice:
Discrete topic | Where you meet it in CS |
|---|---|
Logic |
|
Proofs and induction | Proving an algorithm is correct, loop invariants, correctness of recursive functions |
Sets, relations, functions | Relational databases, hash functions, type systems, equivalence classes in testing |
Partial orders and lattices | Task scheduling (topological order), dependency resolution in build tools, data-flow analysis in compilers |
Counting (combinatorics) | Number of test cases, password strength, probability of hash collisions, analysing loops |
Recurrences and generating functions | Running time of recursive algorithms like merge sort and binary search |
Graph theory | Maps and GPS routes, social networks, computer networks, compiler register allocation (graph colouring), web page ranking |
Algebraic structures (groups, rings, fields) | Cryptography (RSA, elliptic curves), error-correcting codes, checksums |
Beyond individual topics, discrete mathematics trains one skill above all: precise reasoning. Writing a correct proof and writing a correct program are very similar activities. Each step must follow from the previous ones, every case must be handled, and one careless "obviously" can hide a bug.
Discrete Mathematics in Exams and Interviews
University exams. Almost every Indian B.Tech/BE (CSE, IT), BCA and MCA programme has a course called Discrete Mathematics or Discrete Structures, usually in the first or second year.
GATE CS. Discrete mathematics is part of the Engineering Mathematics section. Recent GATE CS syllabi list: propositional and first-order logic; sets, relations, functions, partial orders and lattices; monoids and groups; graphs (connectivity, matching, colouring); and combinatorics (counting, recurrence relations, generating functions). Probability appears in the same section. Always check the official syllabus for your exam year on the organising IIT's GATE website.
Placements. Aptitude rounds are full of counting, probability and logic puzzles, and coding interviews constantly use graphs, recurrences and bit tricks.
How This Tutorial Is Organised
The chapters build on each other in this order:
Logic: Propositional Logic; Logical Equivalences & Normal Forms; Predicate Logic & Quantifiers; Rules of Inference.
Proofs: Proof Techniques; Mathematical Induction.
Sets and mappings: Sets & Set Operations; Functions.
Relations and orders: Relations; Properties of Relations; Equivalence Relations & Partitions; Partial Orders & Hasse Diagrams; Lattices.
Combinatorics: Counting Principles; Permutations & Combinations; Pigeonhole Principle; Inclusion-Exclusion Principle; Recurrence Relations; Solving Linear Recurrences; Generating Functions; Discrete Probability.
Graph theory: Graph Theory Basics; Graph Representations & Isomorphism; Euler & Hamiltonian Paths; Planar Graphs; Graph Coloring; Trees & Spanning Trees.
Algebraic structures: Groups; Rings & Fields.
Logic comes first because every later chapter uses it: a statement about sets, a property of a relation or a theorem about graphs is a logical statement, and we prove it with the rules of logic.
A Taste of Discrete Problems
Here are four small problems. Each one previews a later chapter. Try to answer before reading the solution.
Problem 1: Binary Strings (Counting)
How many binary strings of length 8 are there?
Each of the 8 positions can be filled in 2 ways (0 or 1), independently of the others. So the total is 2 × 2 × ... × 2 (8 times) = 28 = 256. That is exactly why one byte can store 256 different values (0 to 255). This "multiply the choices" idea is the product rule of Counting Principles.
Problem 2: Handshakes (Combinations)
10 people meet, and each pair shakes hands exactly once. How many handshakes happen?
Each person shakes 9 hands, which suggests 10 × 9 = 90. But that counts the handshake between A and B twice (once from A's side, once from B's side). So the answer is 90 / 2 = 45. In the notation of Permutations & Combinations this is C(10, 2) = 45. In graph terms, it is the number of edges of the complete graph K10.
Problem 3: Socks in the Dark (Pigeonhole)
A drawer has red, blue and black socks. How many socks must you pull out in the dark to be sure of a matching pair?
With 3 colours, you could be unlucky and draw one of each colour in 3 draws. The 4th sock must match one of them. Answer: 4. This is the Pigeonhole Principle: 4 socks in 3 colour "boxes" force some box to hold 2.
Problem 4: A Logic Check
A teacher says: "If you score above 90, you get an A." Riya got an A. Did she score above 90?
Not necessarily. The rule says nothing about students who scored 90 or less; maybe Riya got an A through a project. Concluding "she scored above 90" is a classic reasoning error called affirming the consequent. You will learn to spot it in Propositional Logic and Rules of Inference.
Checking with a Program
Small discrete problems can always be checked by brute force: list every possibility and count. This is a habit worth building, and we use it throughout the tutorial to verify answers.
from itertools import product, combinations
# 1. All subsets of {a, b, c}
items = ['a', 'b', 'c']
subsets = [set(c) for r in range(len(items) + 1) for c in combinations(items, r)]
print("Subsets:", len(subsets))
# 2. Binary strings of length 3
strings = [''.join(bits) for bits in product('01', repeat=3)]
print("Strings:", strings)
# 3. Handshakes among 10 people (pairs)
print("Handshakes:", len(list(combinations(range(10), 2))))
# 4. Integer division and remainder
print("17 // 5 =", 17 // 5, " 17 % 5 =", 17 % 5)
print("-7 // 3 =", -7 // 3, " -7 % 3 =", -7 % 3)Output:
Subsets: 8
Strings: ['000', '001', '010', '011', '100', '101', '110', '111']
Handshakes: 45
17 // 5 = 3 17 % 5 = 2
-7 // 3 = -3 -7 % 3 = 2A set of 3 elements has 23 = 8 subsets, there are 23 = 8 binary strings of length 3, and the brute-force handshake count agrees with C(10, 2) = 45. We explain the last line in the notation section below.
Basic Notation Used in This Tutorial
The symbols below appear in every chapter. They are defined fully where they first matter, but you should be able to read them from now on.
Number Sets
Symbol | Meaning | Examples |
|---|---|---|
ℕ | Natural numbers | {0, 1, 2, 3, ...} in this tutorial (many books start at 1; always check) |
ℤ | Integers | {..., −2, −1, 0, 1, 2, ...} |
ℤ+ | Positive integers | {1, 2, 3, ...} |
ℚ | Rational numbers (fractions a/b with b ≠ 0) | 1/2, −3, 0.75 |
ℝ | Real numbers | √2, π, −1.5 |
Set and Logic Symbols
Symbol | Read as | Example |
|---|---|---|
x ∈ A | x is an element of A | 3 ∈ ℤ, and √2 ∉ ℚ |
A ⊆ B | A is a subset of B | ℕ ⊆ ℤ ⊆ ℚ ⊆ ℝ |
|A| | Cardinality (number of elements) of A | |{a, b, c}| = 3 |
∅ | Empty set | |∅| = 0 |
{x ∈ ℤ : x > 0} | The set of all integers x such that x > 0 | Set-builder notation |
¬, ∧, ∨, →, ↔ | not, and, or, implies, if and only if | Introduced in Propositional Logic |
∀, ∃ | for all, there exists | Introduced in Predicate Logic & Quantifiers |
Sums, Products, Floor and Ceiling
Summation: ∑i=1n ai = a1 + a2 + ... + an. For example ∑i=1100 i = 100 × 101 / 2 = 5050.
Product: ∏i=1n i = 1 × 2 × ... × n = n! (n factorial). By convention 0! = 1.
Floor ⌊x⌋ is the largest integer ≤ x; ceiling ⌈x⌉ is the smallest integer ≥ x. So ⌊3.7⌋ = 3, ⌈3.2⌉ = 4, ⌊−3.7⌋ = −4 (not −3!) and ⌈−3.2⌉ = −3.
Example of why they matter: to give 1000 items distinct binary codes you need ⌈log2 1000⌉ = 10 bits, because 29 = 512 < 1000 ≤ 1024 = 210.
Division and "mod"
Division theorem: for any integer a and positive integer d, there are unique integers q (quotient) and r (remainder) with a = d × q + r and 0 ≤ r < d. We write q = a div d = ⌊a/d⌋ and r = a mod d.
For a = 17, d = 5: 17 = 5 × 3 + 2, so q = 3, r = 2. For a = −7, d = 3: −7 = 3 × (−3) + 2, so q = −3 and r = 2, because the remainder must be between 0 and d − 1. Python's // and % follow this mathematical convention, which is why the program printed 2. In C, C++ and Java, integer division truncates toward zero, so -7 / 3 is −2 and -7 % 3 is −1. Remember this difference when you turn a mathematical formula into code.
Finite, Countable and Uncountable
Discrete mathematics deals with sets you can count, but "count" has a precise meaning:
A set is finite if it has n elements for some natural number n. Example: the 256 values of a byte.
A set is countably infinite if its elements can be listed in a sequence x1, x2, x3, ... that eventually reaches every element. Example: ℤ can be listed as 0, 1, −1, 2, −2, 3, −3, ... The set of all finite binary strings, and therefore the set of all programs, is also countable.
A set is uncountable if no such list exists. Cantor proved that ℝ (even the interval between 0 and 1) is uncountable.
"Finite or countably infinite" together are called countable, and these are the natural home of discrete mathematics. A striking consequence: there are only countably many programs, but uncountably many functions from ℕ to {0, 1}, so most functions cannot be computed by any program. You will see the full argument in the Theory of Computation tutorial.
How to Study This Subject
Learn definitions word for word. In discrete maths, a definition is a tool. Half of all proofs are "unpack the definition, then pack it back".
Work small examples by hand. Before proving something for all n, try n = 1, 2, 3. Before trusting a formula, test it on a tiny case.
Verify with code. A 10-line brute-force program, like the one above, catches most counting and logic mistakes.
Practise previous-year questions. GATE questions in this subject are precise and repeat their patterns, so practice pays off reliably.
Common Mistakes and Misconceptions
"Discrete means finite." No. ℕ and ℤ are infinite but discrete. Discrete means the elements are separate and can be listed.
"Discrete maths is only for theory people." Every database query, every network route and every running-time analysis uses it.
Forgetting the convention for ℕ. Some books include 0, some do not. When a question says "natural numbers", check which convention is used.
Floor of negative numbers. ⌊−3.7⌋ = −4, not −3. Floor always goes down the number line.
Assuming
%in C equals mathematical mod. For negative operands they differ: mathematically −7 mod 3 = 2, but in C-7 % 3is −1.Counting ordered pairs when the problem is unordered (the 90 versus 45 handshakes mistake). Always ask "does order matter?"
Interview and Exam Questions
What is discrete mathematics? Give two differences from continuous mathematics.
It is the study of mathematical structures whose elements are separate and countable, such as integers, logical statements, sets, relations and graphs. Unlike continuous mathematics, there are no values "between" neighbouring elements (after 4 comes 5), and the main tools are logic, counting, induction and recurrences instead of limits and derivatives.
Is the set of integers discrete? Is it finite?
It is discrete (each integer has a well-defined next integer, with nothing in between) but infinite. In fact it is countably infinite, since it can be listed as 0, 1, −1, 2, −2, ...
How many different values can be stored in 12 bits?
Each bit has 2 choices, so 212 = 4096 values (0 to 4095 if unsigned).
Compute ⌊−2.5⌋, ⌈−2.5⌉ and −11 mod 4.
⌊−2.5⌋ = −3, ⌈−2.5⌉ = −2. For −11 mod 4: −11 = 4 × (−3) + 1, so −11 mod 4 = 1.
In a round-robin tournament of 8 teams, every team plays every other team once. How many matches are played?
Each match is an unordered pair of teams: C(8, 2) = 8 × 7 / 2 = 28 matches.
Name three areas of computer science that use graph theory.
Any three of: shortest-path routing (GPS, network routing), social-network analysis, compiler register allocation (graph colouring), dependency resolution and scheduling (directed acyclic graphs), web search ranking (link graph).
Summary
Discrete mathematics studies separate, countable objects: integers, logical statements, sets, relations, functions, graphs and finite structures.
Discrete does not mean finite; it means countable with gaps (ℤ is infinite and discrete, ℝ is continuous).
Computers are discrete machines, so this subject underpins algorithms, databases, networks, compilers and cryptography.
The tutorial goes: logic → proofs → sets and functions → relations and orders → combinatorics → graph theory → algebraic structures.
Know the basic notation: ℕ, ℤ, ℚ, ℝ, ∈, ⊆, |A|, ∑, ∏, n!, ⌊x⌋, ⌈x⌉ and a mod d with 0 ≤ r < d.
Next, in Propositional Logic, we start with the simplest building block of all: statements that are either true or false.