Discrete mathematics for computing

Computer Applications (BCA) · Mathematics and business · free study notes for exams, placements and interviews

In short

Discrete mathematics is the study of countable, separated structures — sets, logic statements, relations, functions, counting arrangements, recurrences and algebraic systems — as opposed to the continuous quantities of calculus. It is the formal language of computing: databases rest on set theory and relations, circuits and conditions on Boolean logic, program correctness on induction, algorithm cost on recurrences and counting, and cryptography on modular arithmetic and groups. Indian universities examine it in BCA/MCA semester papers under UGC CBCS and the AICTE model curriculum, and GATE CS devotes roughly 8–12 marks a year to it. Placement tests at TCS, Infosys, Wipro, Cognizant, Accenture and Capgemini draw aptitude and reasoning questions directly from counting, probability basics and logic, while product-company interviews probe recursion, induction and combinatorial reasoning.

Explained

Sets, relations and functions

Set: an unordered collection of distinct objects. Notation: roster {1,2,3} or rule {x : x ∈ N, x < 4}. Cardinality |A| = number of elements.
Operations: union A∪B, intersection A∩B, difference A−B, symmetric difference A△B = (A−B)∪(B−A), complement A′ = U−A, Cartesian product A×B = {(a,b)}, |A×B| = |A||B|.
Power set P(A) = set of all subsets; |P(A)| = 2^|A|. A set with n elements has 2ⁿ subsets, 2ⁿ − 1 proper subsets (all except itself) and 2ⁿ − 2 proper non-empty ones.
Laws: commutative, associative, distributive, idempotent (A∪A=A), De Morgan's (A∪B)′ = A′∩B′ and (A∩B)′ = A′∪B′, absorption A∪(A∩B)=A.
Relation R from A to B: any subset of A×B. On a set of n elements there are 2^n² relations.
Properties of a relation on A: reflexive (aRa for all a), irreflexive, symmetric (aRb ⇒ bRa), antisymmetric (aRb and bRa ⇒ a=b), transitive (aRb and bRc ⇒ aRc).
Equivalence relation: reflexive + symmetric + transitive. It partitions the set into disjoint equivalence classes (e.g. "same remainder mod 3" splits Z into 3 classes).
Partial order (poset): reflexive + antisymmetric + transitive, e.g. (N, ≤) or (P(A), ⊆). Total order adds comparability of every pair. Drawn as a Hasse diagram (transitive and reflexive edges omitted, direction shown by height).
Closures: reflexive closure R∪Δ; symmetric closure R∪R⁻¹; transitive closure R⁺ computed by Warshall's algorithm in O(n³).
Function f: A→B: a relation where every a ∈ A has exactly one image. Injective (one-one), surjective (onto), bijective (both, hence invertible). Composition (g∘f)(x) = g(f(x)) is associative, not commutative.
Counting functions: total functions A→B = |B|^|A|; injections (m ≥ n) = m!/(m−n)! for |A|=n, |B|=m; bijections on n elements = n!.

Propositional and predicate logic

Proposition: a declarative statement that is definitely true or false. Connectives: ¬ (NOT), ∧ (AND), ∨ (OR), → (implication), ↔ (biconditional), ⊕ (XOR).
Implication p→q is false ONLY when p is true and q is false. Equivalent to ¬p∨q. Converse q→p, inverse ¬p→¬q, contrapositive ¬q→¬p — only the contrapositive is logically equivalent to the original.
Classification: tautology (always true), contradiction (always false), contingency/satisfiable (depends on values). A truth table for n variables has 2ⁿ rows.
Key equivalences: De Morgan's ¬(p∧q) ≡ ¬p∨¬q; distributive; exportation (p∧q)→r ≡ p→(q→r); negation of implication ¬(p→q) ≡ p∧¬q.
Normal forms: CNF = AND of OR-clauses; DNF = OR of AND-terms. Any formula can be converted to either; SAT (satisfiability of CNF) is the classic NP-complete problem.
Rules of inference: modus ponens (p, p→q ⊢ q), modus tollens (¬q, p→q ⊢ ¬p), hypothetical syllogism, disjunctive syllogism, simplification, conjunction, addition, resolution (p∨q, ¬p∨r ⊢ q∨r — the engine of Prolog and SAT solvers).
Fallacies: affirming the consequent (q, p→q ⊢ p) and denying the antecedent are invalid.
Predicate logic: a predicate P(x) becomes a proposition when quantified. Universal ∀x P(x), existential ∃x P(x).
Negating quantifiers: ¬∀x P(x) ≡ ∃x ¬P(x); ¬∃x P(x) ≡ ∀x ¬P(x). Order matters: ∀x∃y Loves(x,y) ("everyone loves someone") ≠ ∃y∀x Loves(x,y) ("someone is loved by everyone").
Proof methods: direct, contrapositive, contradiction (reductio ad absurdum), by cases, constructive and non-constructive existence, disproof by counterexample.

Counting, pigeonhole and recurrences

Rules: sum rule — mutually exclusive choices add; product rule — independent sequential choices multiply.
Permutation (order matters) ⁿPᵣ = n!/(n−r)!; combination (order irrelevant) ⁿCᵣ = n!/(r!(n−r)!). Circular permutations of n objects = (n−1)!.
With repetition: arrangements of n items from k types = kⁿ; permutations of n objects with repeats n!/(n₁!n₂!…); selections with repetition = ⁿ⁺ʳ⁻¹Cᵣ (the "stars and bars" result).
Binomial theorem: (x+y)ⁿ = Σ ⁿCᵏ xⁿ⁻ᵏyᵏ; Pascal's identity ⁿCᵣ = ⁿ⁻¹Cᵣ₋₁ + ⁿ⁻¹Cᵣ; Σ ⁿCᵏ = 2ⁿ.
Inclusion–exclusion: |A∪B| = |A|+|B|−|A∩B|; for three sets add back the triple intersection. Used for counting items satisfying "at least one" condition.
Pigeonhole principle: n items in m boxes with n > m force some box to hold ≥ 2. Generalised: some box holds at least ⌈n/m⌉ items. Proves hash collisions, duplicate birthdays, and lower bounds.
Recurrence relation: defines a term from earlier terms, e.g. Fibonacci Fₙ = Fₙ₋₁ + Fₙ₋₂, F₀=0, F₁=1; Hanoi Tₙ = 2Tₙ₋₁ + 1.
Solving linear homogeneous recurrences aₙ = c₁aₙ₋₁ + c₂aₙ₋₂: write the characteristic equation r² − c₁r − c₂ = 0; distinct roots give aₙ = A r₁ⁿ + B r₂ⁿ; a repeated root r gives aₙ = (A + Bn)rⁿ; fit A, B from initial conditions.
Non-homogeneous: general solution = homogeneous solution + a particular solution guessed to match the RHS form.
Master theorem (for divide-and-conquer T(n) = aT(n/b) + f(n)) gives algorithm complexity directly — merge sort T(n)=2T(n/2)+n → Θ(n log n).
Generating functions: encode a sequence as coefficients of a power series; useful for solving recurrences and counting partitions (usually introductory in BCA).
Mathematical induction: prove P(1) (base), assume P(k) (hypothesis), prove P(k+1) (step). Strong induction assumes P(1)…P(k). Used to verify loop invariants and recursive program correctness.

Boolean algebra and logic simplification

A Boolean algebra is a complemented distributive lattice on {0,1} with operations +( OR), ·(AND), ′(NOT).
Postulates: identity (A+0=A, A·1=A), null (A+1=1, A·0=0), idempotence, complement (A+A′=1, A·A′=0), involution (A′)′=A, De Morgan's, absorption A+AB=A, consensus AB+A′C+BC = AB+A′C.
Duality: swap AND↔OR and 0↔1 and every valid identity remains valid.
Canonical forms: SOP (sum of minterms, Σm) and POS (product of maxterms, ΠM). For n variables there are 2ⁿ minterms and 2^2ⁿ distinct Boolean functions.
Karnaugh map (K-map): cells arranged in Gray-code order so adjacent cells differ in one variable; group 1s in powers of 2 (1,2,4,8), use largest groups, allow overlaps, treat the map as wrapping edge-to-edge, and use don't-care (X) cells freely to enlarge groups. Practical to 4–5 variables; Quine–McCluskey is the tabular method for more.
Gates: AND, OR, NOT, NAND, NOR, XOR, XNOR. NAND and NOR are universal (functionally complete) — any circuit can be built from either alone.
Applications: combinational circuits (adders, multiplexers, decoders), SQL WHERE clauses, if-conditions, and bitmask programming.

Lattices, algebraic structures and number theory

Lattice: a poset in which every pair has a least upper bound (join, ∨) and greatest lower bound (meet, ∧). Bounded (has 0 and 1), distributive, complemented.
Algebraic structures on a set with one binary operation, in increasing strength:
1. Semigroup — closure + associativity.
2. Monoid — semigroup + identity element.
3. Group — monoid + inverse for every element.
4. Abelian group — group + commutativity.
Ring (two operations, additive abelian group + multiplicative semigroup + distributivity); field — a commutative ring where every non-zero element has a multiplicative inverse, e.g. GF(2) used in error-correcting codes.
Group facts: order of a group |G| = number of elements; order of an element = least n with aⁿ = e; Lagrange's theorem — the order of a subgroup divides |G|; a cyclic group is generated by one element; permutation group Sₙ has n! elements.
Modular arithmetic: a ≡ b (mod m) iff m | (a−b). Addition and multiplication respect congruence, which is why hashing and checksums work.
Euclid's algorithm for gcd by repeated remainders; extended version gives x, y with ax+by = gcd(a,b), hence modular inverse when gcd(a,m)=1.
Euler's totient φ(n) counts integers ≤ n coprime to n; Fermat's little theorem a^p−1 ≡ 1 (mod p) for prime p ∤ a; Euler's theorem a^φ(n) ≡ 1 (mod n) — the basis of RSA, used in India's digital-signature and UPI security stacks.
Chinese remainder theorem solves simultaneous congruences with coprime moduli — used in fast RSA decryption.

Automata, grammars and countability (where the syllabus extends)

Alphabet, string, language: Σ a finite alphabet, Σ* all strings over it; a language is a subset of Σ*.
Finite automaton (DFA/NFA): states, transitions, start state, accepting states; recognises exactly the regular languages, which match regular expressions.
Chomsky hierarchy: Type 0 unrestricted (Turing machine) ⊃ Type 1 context-sensitive ⊃ Type 2 context-free (pushdown automaton, parsers) ⊃ Type 3 regular (finite automaton, lexers).
Pumping lemma proves a language is not regular, e.g. {aⁿbⁿ} needs counting beyond finite memory.
Countability: N, Z and Q are countably infinite; R and P(N) are uncountable (Cantor's diagonal argument) — which is why some problems are undecidable.
Discrete vs continuous: discrete objects are finite or countable and separated; computers, being finite-state machines, are naturally modelled discretely.

Key points

Discrete mathematics - the mathematics of countable, separated structures; the formal basis of computer science.
Power set - |P(A)| = 2ⁿ; a 10-element set has 1,024 subsets.
Equivalence relation - reflexive + symmetric + transitive; creates a partition into disjoint classes.
Partial order - reflexive + antisymmetric + transitive; visualised by a Hasse diagram.
Bijection - one-one and onto; the only functions with inverses, and the test for equal cardinality.
Implication - p→q ≡ ¬p∨q; false only when p is true and q false; equivalent to its contrapositive only.
Tautology - a formula true in every row of its truth table; n variables give 2ⁿ rows.
Resolution - from p∨q and ¬p∨r infer q∨r; the inference rule behind Prolog and SAT solvers.
Quantifier negation - ¬∀x P(x) ≡ ∃x ¬P(x); swapping ∀ and ∃ order changes meaning.
Permutation vs combination - ⁿPᵣ = n!/(n−r)! when order matters; ⁿCᵣ = ⁿPᵣ/r! when it does not.
Pigeonhole principle - n items in m boxes ⇒ some box has ⌈n/m⌉ items; proves hash collisions must occur.
Inclusion–exclusion - add the sizes, subtract pairwise overlaps, add back triples.
Induction - base case + inductive step; the standard proof of recursive-program correctness.
Characteristic equation - turns a linear recurrence into a polynomial whose roots give the closed form.
NAND and NOR - universal gates; either alone can build any Boolean function.
K-map - Gray-coded grid; group 1s in powers of two, largest groups first, don't-cares used freely.
Group hierarchy - semigroup ⊂ monoid ⊂ group ⊂ abelian group; adds associativity, identity, inverse, commutativity.
Chomsky hierarchy - regular ⊂ context-free ⊂ context-sensitive ⊂ unrestricted; each needs a stronger machine.

Formulas and examples

|P(A)| = 2ⁿ — subsets of an n-element set (n = cardinality, dimensionless count)
|A∪B| = |A| + |B| − |A∩B|; |A∪B∪C| = |A|+|B|+|C| − |A∩B| − |B∩C| − |A∩C| + |A∩B∩C|
Relations on an n-set = 2^n²; reflexive relations = 2^n²−n; symmetric relations = 2^n(n+1)/2
ⁿPᵣ = n!/(n−r)!; ⁿCᵣ = n!/(r!(n−r)!); circular permutations = (n−1)!
Selections with repetition = ⁿ⁺ʳ⁻¹Cᵣ; arrangements with repeats = n!/(n₁!n₂!…nₖ!)
Generalised pigeonhole: minimum in the fullest box = ⌈n/m⌉ (n items, m boxes)
Linear recurrence aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ → r² − c₁r − c₂ = 0; aₙ = A r₁ⁿ + B r₂ⁿ (distinct roots)
Functions A→B = |B|^|A|; minterms for n variables = 2ⁿ; Boolean functions of n variables = 2^2ⁿ
a^φ(n) ≡ 1 (mod n) when gcd(a,n)=1; φ(p) = p−1 for prime p; φ(pq) = (p−1)(q−1) for distinct primes p, q

Example 1 — Inclusion–exclusion, a BCA class. Of 120 students, 65 know C, 50 know Java, 45 know Python; 25 know C and Java, 20 know C and Python, 15 know Java and Python, and 8 know all three. How many know at least one, and how many none?

At least one = 65 + 50 + 45 − 25 − 20 − 15 + 8 = 160 − 60 + 8 = 108.
Know none = 120 − 108 = 12.
Exactly one C-only = 65 − 25 − 20 + 8 = 28.

Example 2 — Counting passwords (product rule and subtraction). A portal needs a 5-character password from 26 lowercase letters and 10 digits, with at least one digit.

Total strings over 36 symbols = 36⁵ = 60,466,176.
All-letter strings = 26⁵ = 11,881,376.
Valid = 60,466,176 − 11,881,376 = 48,584,800.
If repetition were forbidden: ³⁶P₅ = 36×35×34×33×32 = 45,239,040 total arrangements.

Example 3 — Solving a recurrence. Solve aₙ = 5aₙ₋₁ − 6aₙ₋₂ with a₀ = 1, a₁ = 4.

Characteristic equation r² − 5r + 6 = 0 → (r−2)(r−3) = 0 → r = 2, 3.
General solution aₙ = A·2ⁿ + B·3ⁿ.
n=0: A + B = 1. n=1: 2A + 3B = 4 → subtracting twice the first: B = 2, so A = −1.
aₙ = 2·3ⁿ − 2ⁿ. Check a₂ = 2·9 − 4 = 14, and 5(4) − 6(1) = 14. ✓

Example 4 — Truth table and validity. Is (p→q) ∧ (q→r) ⇒ (p→r) valid?

p	q	r	p→q	q→r	premise ∧	p→r
T	T	T	T	T	T	T
T	T	F	T	F	F	F
T	F	T	F	T	F	T
T	F	F	F	T	F	F
F	T	T	T	T	T	T
F	T	F	T	F	F	T
F	F	T	T	T	T	T
F	F	F	T	T	T	T

In every row where the conjoined premise is T (rows 1, 5, 7, 8), p→r is also T, so the argument (hypothetical syllogism) is valid.

Example 5 — K-map simplification. Minimise F(A,B,C,D) = Σm(0,1,2,3,8,9,10,11).

Minterms 0–3 have A=0, B=0; minterms 8–11 have A=1, B=0. In all eight, B = 0 and C, D vary freely.
One group of eight → F = B′, down from 8 four-literal terms to a single inverter.

Example 6 — Pigeonhole and modular arithmetic. Among any 13 students, at least how many share a birth month, and how many users choosing 4-digit PINs are needed before a collision is certain?

13 students, 12 months → ⌈13/12⌉ = 2 share a month; with 30 students, ⌈30/12⌉ = 3.
4-digit PINs give 10,000 values, so 10,001 users guarantee a repeat — the same argument shows hash collisions are unavoidable.

Structure	Needs	Example
Semigroup	closure, associativity	(Z⁺, +)
Monoid	+ identity	(Z, ×), identity 1
Group	+ inverses	(Z, +), (Zₙ, +ₙ)
Abelian group	+ commutativity	(Z, +)
Field	two ops, inverses for non-zero	GF(2), Q, R

Where it is used

Databases and analytics: relational algebra is set theory — SELECT/JOIN/UNION are selection, Cartesian product and union; normalisation uses functional dependencies and closures. Core to roles at TCS, Infosys, Oracle India and Zoho.
Compilers and search: regular expressions and finite automata power lexers, grep, log parsers and input validation in Aadhaar/GST/PAN field checks; context-free grammars drive parsers.
Security and payments: modular arithmetic, φ(n), Fermat/Euler theorems underpin RSA and digital signatures used in UPI, NPCI systems, Income-tax e-filing and DSC tokens issued under the Information Technology Act, 2000.
Algorithm design and interviews: recurrences give complexity (merge sort, binary search), induction proves correctness, counting bounds hashing and caching — standard in Amazon, Microsoft, Flipkart and Zoho interview rounds.
Digital hardware and embedded roles: Boolean algebra and K-maps for combinational design, used in VLSI and firmware work at Intel India, Qualcomm India, ISRO and BEL.
Exams and higher study: GATE CS, NIELIT, UGC-NET Computer Science, bank and SSC aptitude sections (permutations, combinations, sets, logical reasoning) and MCA entrance tests.

Interview questions

Q: What makes a relation an equivalence relation, and why does it matter in computing? A: It is reflexive, symmetric and transitive; it partitions a set into disjoint classes, which is exactly how hash buckets, GROUP BY results and congruence classes mod n behave.
Q: Difference between a relation and a function? A: A relation is any subset of A×B; a function additionally requires every element of A to map to exactly one element of B.
Q: How many subsets and how many relations can a 3-element set have? A: 2³ = 8 subsets and 2^3² = 2⁹ = 512 relations on it.
Q: Is p→q equivalent to its converse? A: No — only to its contrapositive ¬q→¬p; assuming the converse is the "affirming the consequent" fallacy.
Q: State the pigeonhole principle and give a programming use. A: If n items go into m < n boxes, some box has at least ⌈n/m⌉ items; it proves that a hash function mapping more keys than buckets must produce collisions.
Q: Why are NAND and NOR called universal gates? A: Each can express NOT, AND and OR by itself, so any Boolean function — hence any combinational circuit — can be built using only one gate type.
Q: Difference between weak and strong induction? A: Weak induction assumes only P(k) to prove P(k+1); strong induction assumes P(1) through P(k), which helps when a term depends on several earlier terms.
Q: How do you solve aₙ = 2aₙ₋₁ + 3aₙ₋₂? A: Characteristic equation r² − 2r − 3 = 0 gives r = 3, −1, so aₙ = A·3ⁿ + B(−1)ⁿ with A, B fixed by the initial values.
Q: Does ∀x∃y P(x,y) mean the same as ∃y∀x P(x,y)? A: No — the first allows a different y for each x; the second demands one y that works for all x, which is a strictly stronger claim.
Q: What is a poset, and what does a Hasse diagram show? A: A set with a reflexive, antisymmetric, transitive order; the Hasse diagram draws only the immediate cover relations, omitting loops and transitive edges.
Q: Why is discrete mathematics preferred over calculus in computer science? A: Computers are finite-state machines handling countable data, so set, logic, counting and recurrence models fit directly, whereas continuous limits do not.
Q: Give the minimum structure needed to call a set with an operation a group. A: Closure, associativity, an identity element and an inverse for every element; commutativity is extra and makes it abelian.

Common mistakes

Treating ⁿPᵣ and ⁿCᵣ as interchangeable — writing ⁿCᵣ where arrangements (order) matter, or vice versa, is the single biggest counting error.
Confusing the converse with the contrapositive, and so accepting an invalid argument as valid.
Assuming a relation that is not reflexive can still be an equivalence relation, or calling the empty relation on a non-empty set reflexive — it is not.
Forgetting that antisymmetry is not "not symmetric"; a relation can be both symmetric and antisymmetric (e.g. equality).
Skipping or mis-stating the base case in induction, or assuming P(k+1) instead of deriving it from P(k).
In K-maps, making groups of 3, 5 or 6 cells, missing wrap-around adjacency, or ignoring don't-care cells that would give a smaller expression.
Double-counting in inclusion–exclusion — subtracting pairwise overlaps but forgetting to add the triple intersection back.
Mixing up "at least one" with "exactly one" when subtracting from the total in counting problems.