Discrete & Engineering Mathematics

Why this unit matters

Discrete and Engineering Mathematics is the broadest unit in ISRO CS. It covers pure discrete mathematics (logic, sets, counting, graph theory) that appear in other units (TOC uses logic and graph theory, algorithms use counting and probability) as well as engineering mathematics (linear algebra, probability) that GATE CS covers in a separate unit. ISRO combines both, contributing 10-14 marks.

The questions vary: propositional logic truth tables (1 mark), modular arithmetic (1 mark), eigenvalue calculation (2 marks), Bayes' theorem probability (2 marks), counting problems (1 mark). No single sub-topic dominates, so broad preparation is essential.

Syllabus map

• Mathematical logic

  • Propositional logic: syntax, semantics, truth tables
  • Logical connectives: NOT, AND, OR, implication, biconditional
  • Equivalences: De Morgan, absorption, distribution
  • Normal forms: conjunctive normal form (CNF), disjunctive normal form (DNF)
  • Predicate logic: quantifiers (universal, existential), scope, bound/free variables
  • Inference rules: modus ponens, modus tollens, hypothetical syllogism, disjunctive syllogism, resolution

• Set theory

  • Sets, subsets, power set, Cartesian product
  • Operations: union, intersection, complement, difference, symmetric difference
  • Venn diagrams and inclusion-exclusion
  • Relations: reflexive, symmetric, antisymmetric, transitive
  • Equivalence relations and partitions
  • Partial order (POSET), total order, Hasse diagram
  • Functions: injective (one-to-one), surjective (onto), bijective; composition, inverse

• Counting

  • Permutations: ordered, without and with repetition
  • Combinations: unordered, without and with repetition
  • Pigeonhole principle and its generalisations
  • Inclusion-exclusion principle
  • Recurrence relations: linear homogeneous with constant coefficients, characteristic equation
  • Generating functions (brief)

• Graph theory

  • Basic definitions: graph, digraph, degree sequence, path, cycle, walk, trail
  • Euler path/circuit: conditions (degree requirements)
  • Hamiltonian path/cycle: conditions (no simple necessary and sufficient condition)
  • Planar graphs: Euler's formula (V - E + F = 2), K5 and K3,3 non-planarity (Kuratowski's theorem)
  • Graph colouring: chromatic number, four-colour theorem
  • Trees: properties, spanning trees, minimum spanning tree

• Linear algebra

  • Matrices: types (identity, diagonal, symmetric, skew-symmetric, orthogonal, upper/lower triangular)
  • Matrix operations: addition, multiplication, transpose, inverse
  • Determinant: cofactor expansion, Sarrus rule for 3x3
  • System of linear equations: Gaussian elimination, Gauss-Jordan
  • Consistency: unique solution, infinite solutions, no solution (rank conditions)
  • Rank of a matrix
  • Eigenvalues and eigenvectors: characteristic equation det(A - lambda I) = 0
  • Properties: trace = sum of eigenvalues, determinant = product of eigenvalues
  • Cayley-Hamilton theorem

• Probability

  • Sample space, events, axioms of probability
  • Conditional probability: P(A|B) = P(A intersection B) / P(B)
  • Independence: P(A intersection B) = P(A) * P(B)
  • Bayes' theorem: P(A|B) = P(B|A) * P(A) / P(B)
  • Random variables: discrete and continuous
  • Probability mass function (PMF), probability density function (PDF), cumulative distribution function (CDF)
  • Expectation and variance
  • Common distributions: uniform, Bernoulli, binomial, Poisson, geometric, normal (Gaussian)

Mathematical logic

Propositional equivalences

Key equivalences:

• De Morgan: NOT(A AND B) = (NOT A) OR (NOT B). NOT(A OR B) = (NOT A) AND (NOT B).
• Implication: A => B = (NOT A) OR B.
• Contrapositive: A => B is equivalent to (NOT B) => (NOT A).
• Double negation: NOT(NOT A) = A.

To check if an argument is valid, verify that the premises imply the conclusion (i.e., the argument form is a tautology).

CNF: conjunction of clauses, each clause is a disjunction of literals. SAT asks whether a CNF formula has a satisfying assignment (NP-complete).

DNF: disjunction of terms, each term is a conjunction of literals. DNF satisfiability is easy (check if any term is consistent).

Predicate logic

Universal quantifier: for all x, P(x) means P holds for every element in the domain. Existential quantifier: there exists x, P(x) means P holds for at least one element.

Negation: NOT(for all x, P(x)) = there exists x, NOT P(x). NOT(there exists x, P(x)) = for all x, NOT P(x).

ISRO trap: the order of quantifiers matters. "For all x there exists y, R(x,y)" and "there exists y for all x, R(x,y)" have different meanings. The second is stronger.

Set theory and relations

Inclusion-exclusion

|A union B| = |A| + |B| - |A intersection B|. |A union B union C| = |A| + |B| + |C| - |A intersection B| - |A intersection C| - |B intersection C| + |A intersection B intersection C|.

Relations

A relation R on set A is:

• Reflexive: (a, a) in R for all a in A.
• Symmetric: (a, b) in R implies (b, a) in R.
• Antisymmetric: (a, b) in R and (b, a) in R implies a = b.
• Transitive: (a, b) in R and (b, c) in R implies (a, c) in R.

Equivalence relation: reflexive + symmetric + transitive. Partitions the set into equivalence classes.

Partial order (POSET): reflexive + antisymmetric + transitive. Example: divisibility on integers.

Total order: partial order where every pair is comparable. Example: integers under <=.

Functions

A function f: A -> B is:

• Injective (one-to-one): f(a1) = f(a2) implies a1 = a2. |A| <= |B|.
• Surjective (onto): every element of B is an image of some element of A. |A| >= |B|.
• Bijective: both injective and surjective. |A| = |B|. Bijection has an inverse.

Number of functions from A (|A| = m) to B (|B| = n): n^m. Number of injections: n * (n-1) * ... * (n-m+1) = n! / (n-m)! (if n >= m). Number of bijections (permutations): n! (if n = m).

Counting

Permutations and combinations

P(n, r) = n! / (n - r)!: number of ways to arrange r items from n distinct items. C(n, r) = n! / (r! * (n-r)!): number of ways to choose r items from n (unordered).

With repetition:

• Permutations: n^r (r items chosen from n with repetition allowed, ordered).
• Combinations: C(n+r-1, r) (r items from n types, unordered, repetition allowed).

Pigeonhole principle

If n+1 or more objects are placed in n boxes, at least one box contains at least two objects. Generalised: if kn+1 objects are in n boxes, at least one box contains at least k+1 objects.

Classic application: among any 367 people, at least two share a birthday (366 boxes + 1 pigeons).

Recurrence relations

Linear homogeneous recurrence with constant coefficients: a_n = c1 * a_(n-1) + c2 * a_(n-2) + ... + ck * a_(n-k).

Solve by finding characteristic roots: substitute a_n = r^n, divide by r^(n-k), get characteristic equation. If roots r1, r2, ... rk are distinct: a_n = A1 * r1^n + A2 * r2^n + ... + Ak * rk^n. Use initial conditions to find A1, A2, etc.

Fibonacci: a_n = a_(n-1) + a_(n-2). Characteristic equation: r^2 = r + 1, or r^2 - r - 1 = 0. Roots: (1 + sqrt(5))/2 (golden ratio phi) and (1 - sqrt(5))/2.

Graph theory

Eulerian and Hamiltonian graphs

Euler circuit (visits every edge exactly once, returns to start): exists if and only if the graph is connected and every vertex has even degree.

Euler path (visits every edge exactly once, need not return to start): exists if and only if the graph is connected and has exactly two vertices of odd degree (the start and end of the path).

Hamiltonian cycle (visits every vertex exactly once, returns to start): no simple necessary and sufficient condition. NP-complete to determine in general.

Planar graphs

Euler's formula: for a connected planar graph, V - E + F = 2 (V = vertices, E = edges, F = faces, including the outer infinite face).

For a simple planar graph: E <= 3V - 6. If the graph is also bipartite: E <= 2V - 4.

K5 (complete graph on 5 vertices) and K3,3 (complete bipartite on 3+3 vertices) are not planar. Kuratowski's theorem: a graph is planar if and only if it contains no subdivision of K5 or K3,3.

Graph colouring

The chromatic number chi(G) is the minimum number of colours needed to colour vertices such that no two adjacent vertices share a colour.

For any graph: chi(G) <= Delta(G) + 1 (where Delta is the maximum degree). For most graphs, chi(G) <= Delta(G) (Brooks' theorem, except for complete graphs and odd cycles).

The four-colour theorem: every planar graph has chi(G) <= 4 (proven by computer, 1976).

Bipartite graphs: chi(G) = 2 (if at least one edge exists) or 1. A graph is bipartite if and only if it has no odd-length cycles.

Linear algebra

Matrix operations

Matrix multiplication: (AB)_ij = sum over k of A_ik * B_kj. Not commutative in general.

Transpose: (A^T)_ij = A_ji. Properties: (AB)^T = B^T A^T, (A^T)^T = A.

Inverse of a 2x2 matrix: [[a,b],[c,d]]^(-1) = (1/(ad-bc)) * [[d,-b],[-c,a]].

System of linear equations

Ax = b. Use Gaussian elimination (row reduction) to bring the augmented matrix [A|b] to row echelon form.

Consistency:

• rank(A) = rank([A|b]) = n (number of unknowns): unique solution.
• rank(A) = rank([A|b]) < n: infinitely many solutions (n - rank free variables).
• rank(A) < rank([A|b]): no solution (inconsistent system).

Eigenvalues

Find eigenvalues by solving det(A - lambda I) = 0 (characteristic equation). Find eigenvectors: for each eigenvalue lambda, solve (A - lambda I)x = 0.

Key properties:

• Trace of A = sum of all eigenvalues.
• Det(A) = product of all eigenvalues.
• Eigenvalues of A^k are lambda_k (kth power of each eigenvalue).
• Eigenvalues of A^(-1) are 1/lambda (if A is invertible).
• A symmetric matrix has real eigenvalues. An orthogonal matrix has eigenvalues of absolute value 1.

Cayley-Hamilton theorem: every square matrix satisfies its own characteristic equation.

Probability

Bayes' theorem

P(A|B) = P(B|A) * P(A) / P(B).

Total probability: P(B) = sum over all partitions Ai of P(B|Ai) * P(Ai).

Common distributions

Bernoulli(p): single trial. P(X=1) = p, P(X=0) = 1-p. E[X] = p, Var(X) = p(1-p).

Binomial(n, p): n independent Bernoulli trials. P(X=k) = C(n,k) * p^k * (1-p)^(n-k). E[X] = np, Var(X) = np(1-p).

Poisson(lambda): limit of binomial for large n, small p, lambda = np. P(X=k) = e^(-lambda) * lambda^k / k!. E[X] = lambda, Var(X) = lambda.

Geometric(p): number of trials until first success. P(X=k) = (1-p)^(k-1) * p. E[X] = 1/p. Memoryless property.

Uniform: discrete or continuous. For continuous Uniform(a,b): E[X] = (a+b)/2, Var(X) = (b-a)^2/12.

Normal N(mu, sigma^2): symmetric bell curve. E[X] = mu, Var(X) = sigma^2. Standard normal Z = (X - mu)/sigma.

Worked examples

Example 1: Logic equivalence

Show that (P => Q) AND (Q => R) => (P => R) is a tautology.

(P => Q) = (NOT P OR Q). (Q => R) = (NOT Q OR R). (P => R) = (NOT P OR R).

Suppose (P => Q) AND (Q => R) is true, and P is true. Then Q is true (from P => Q and P). Then R is true (from Q => R and Q). So P => R holds. The implication is valid. This is the hypothetical syllogism inference rule.

Example 2: Euler's formula for planar graphs

Graph: K4 (complete graph on 4 vertices). V = 4, E = 6.

F = 2 - V + E = 2 - 4 + 6 = 4.

Check: K4 is planar. Drawn in the plane, it has 3 interior triangular faces + 1 outer face = 4. Consistent.

For K5: V = 5, E = 10. If planar: F = 2 - 5 + 10 = 7. But E <= 3V - 6 = 9 for simple planar. 10 > 9, so K5 is not planar.

Example 3: Eigenvalues of a matrix

A = [[4, 1], [2, 3]].

Characteristic equation: det(A - lambda I) = 0. det([[4-lambda, 1], [2, 3-lambda]]) = (4-lambda)(3-lambda) - 2 = 0. = 12 - 4lambda - 3lambda + lambda^2 - 2 = lambda^2 - 7lambda + 10 = 0. = (lambda - 5)(lambda - 2) = 0.

Eigenvalues: lambda1 = 5, lambda2 = 2.

Check: trace = 4 + 3 = 7 = 5 + 2. Det = 43 - 12 = 10 = 5 * 2. Consistent.

Eigenvector for lambda = 5: (A - 5I)x = [[−1, 1], [2, −2]]x = 0. Row reduce: x1 = x2. Eigenvector: [1, 1].

Example 4: Bayes' theorem

A diagnostic test: 99% sensitivity (P(positive|disease) = 0.99), 95% specificity (P(negative|no disease) = 0.95). Disease prevalence: P(disease) = 0.01.

P(positive|no disease) = 1 - 0.95 = 0.05. P(positive) = P(positive|disease)*P(disease) + P(positive|no disease)*P(no disease) = 0.99 * 0.01 + 0.05 * 0.99 = 0.0099 + 0.0495 = 0.0594.

P(disease|positive) = P(positive|disease) * P(disease) / P(positive) = 0.99 * 0.01 / 0.0594 = 0.0099 / 0.0594 = 0.1667 = about 16.7%.

Despite a 99% sensitivity, only 16.7% of positive tests indicate actual disease (because prevalence is low). This is the base-rate fallacy.

Example 5: Recurrence solution

a_n = 5a_(n-1) - 6a_(n-2), a_0 = 1, a_1 = 4.

Characteristic equation: r^2 - 5r + 6 = 0. Roots: r = 2 and r = 3.

General solution: a_n = A * 2^n + B * 3^n.

Apply initial conditions: a_0 = A + B = 1. a_1 = 2A + 3B = 4.

From first: B = 1 - A. Substitute: 2A + 3(1-A) = 4. 2A + 3 - 3A = 4. -A = 1. A = -1, B = 2.

a_n = -2^n + 2 * 3^n.

Verify: a_2 = -4 + 18 = 14. Check: 5a_1 - 6a_0 = 54 - 61 = 14. Correct.

Quick-revision summary

• Implication A => B is false only when A is true and B is false. Equivalent to NOT A OR B.
• Contrapositive is equivalent to the original; converse and inverse are not.
• Equivalence relation: reflexive + symmetric + transitive. Partial order: reflexive + antisymmetric + transitive.
• Injective: no two elements map to same image. Surjective: every element in codomain has a preimage.
• Euler circuit: all vertices even degree. Euler path: exactly 2 odd degree vertices.
• Euler's formula: V - E + F = 2 for connected planar graphs.
• K5 and K3,3 are not planar. E <= 3V - 6 for simple planar graphs.
• Eigenvalues: solve det(A - lambda I) = 0. Trace = sum, det = product of eigenvalues.
• Rank condition for Ax = b: rank(A) vs rank([A|b]) vs n (number of unknowns).
• Bayes': P(A|B) = P(B|A)*P(A) / P(B). Total probability formula for P(B).
• Binomial: E[X] = np, Var = np(1-p). Poisson: E = Var = lambda. Geometric: E = 1/p, memoryless.

How to study this unit

1. Practise truth table construction and equivalence verification for compound propositions. Know all standard equivalences (De Morgan, distribution, absorption) by heart.
2. For graph theory, practise checking Eulerian conditions and applying Euler's formula on small graphs (5-8 vertices). Verify K5 non-planarity by the edge count condition.
3. For eigenvalues, practise on 2x2 and 3x3 matrices. For 3x3, cofactor expansion for the determinant. Always verify using trace and determinant checks.
4. For probability, practise Bayes' theorem on 3-5 different scenarios (disease testing, spam filtering, quality control). The low base-rate effect is a common ISRO question style.
5. Solve recurrence relations by finding characteristic roots. Practise at least 3 problems with distinct real roots and one with repeated roots (a_n = (A + Bn) * r^n for repeated root r).
6. Counting problems: practise distinguishing permutation from combination, and with-repetition from without-repetition scenarios. The stars-and-bars technique (C(n+r-1, r)) for distributing identical items is a frequent trap in ISRO questions.