GateShala
Playground

Discrete Mathematics

Discrete Mathematics is the mathematical foundation of computer science and a large part of the GATE paper. These lessons explain every syllabus topic with worked examples, and check the counting formulas (relations, functions, derangements, colourings) by brute-force enumeration with small programs.

Start the first lesson

1Logic

  1. Propositional LogicPropositions and connectives, truth tables, tautologies and contradictions, logical equivalences, converse, inverse and contrapositive, normal forms, and checking arguments with rules of inference.
  2. First-Order (Predicate) LogicPredicates and domains, the universal and existential quantifiers, negating quantified statements, nested quantifiers and their order, translating English, and which quantifier laws are valid.

2Sets and Relations

  1. Sets, Functions and Counting FunctionsSet operations and identities, power sets and Cartesian products, functions and their kinds (one-to-one, onto, bijective), counting functions between finite sets, composition and inverses, and the pigeonhole principle.
  2. RelationsBinary relations and their matrix and graph forms, reflexive, symmetric, antisymmetric and transitive relations, counting relations of each kind, closures, equivalence relations and partitions, and Bell numbers.
  3. Partial Orders and LatticesPartially ordered sets, Hasse diagrams, maximal, minimal, greatest and least elements, upper and lower bounds, lattices, distributive, complemented and Boolean lattices, and the divisor lattices Dâ‚™.

3Algebraic Structures

  1. Semigroups, Monoids and GroupsBinary operations and their properties, semigroups, monoids and groups, abelian groups, the order of an element, subgroups and Lagrange's theorem, and cyclic groups with their generators.

4Combinatorics

  1. Counting and CombinatoricsThe sum and product rules, permutations and combinations, arrangements with repeated letters, circular arrangements, selections with repetition (stars and bars), inclusion–exclusion, and derangements.
  2. Recurrence Relations and Generating FunctionsSetting up recurrences for counting problems, solving linear homogeneous recurrences with the characteristic equation (distinct and repeated roots), non-homogeneous recurrences, generating functions, and Catalan numbers.

5Graph Theory

  1. Graph TheoryGraph terms and the handshaking lemma, connectivity, Euler and Hamiltonian paths, trees and Cayley's formula, bipartite graphs, planar graphs and Euler's formula, colouring, matchings, independent sets, cliques and vertex covers.

6GATE Practice

  1. Discrete Mathematics GATE Practice SetMixed GATE-style questions on logic, functions, relations, lattices, groups, counting, recurrences and graph theory.