Skip to main content
CBE Nexus · Undergraduate Computer Science

Chapter 3: Discrete Mathematics for Computer Science

Study logic, sets, relations, functions, proof methods, induction, counting, combinatorics, graph theory, trees, recurrence relations and Boolean algebra for computing.

Back to Computer Science course guide

Chapter overview and learning outcomes

This chapter develops the conceptual and practical foundations of discrete mathematics for computer science. It connects theory with implementation, evaluation and responsible computing practice.

1. Why discrete mathematics matters

Discrete mathematics studies countable, distinct structures rather than continuously varying quantities. It underpins algorithms, databases, cryptography, networks, programming-language semantics, digital circuits and formal verification. Logical reasoning helps prove program properties; graph theory models connections; combinatorics counts possibilities; number theory supports cryptography. The subject develops precision in definitions, assumptions and arguments.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

2. Propositions and logical connectives

A proposition is a declarative statement that is either true or false. Negation reverses truth value; conjunction is true when both statements are true; disjunction is true when at least one is true; implication is false only when its antecedent is true and consequent false; biconditional is true when both sides share a truth value. Truth tables enumerate all possible assignments.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

3. Logical equivalence and inference

Two propositions are logically equivalent when they have identical truth values for every assignment. De Morgan's laws relate negation to conjunction and disjunction. Valid inference rules include modus ponens and modus tollens. Distinguish validity from truth: an argument is valid when its conclusion follows from its premises, even if a premise is false. Predicate logic adds quantifiers over a domain.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

4. Sets and set operations

A set is an unordered collection of distinct elements. Membership, subset, equality, union, intersection, difference and complement describe relationships between sets. The power set contains every subset. Cartesian products form ordered pairs and are used to define relations. Venn diagrams provide intuition, while formal definitions support proofs and precise data modelling.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

5. Relations and equivalence classes

A relation from set A to set B is a subset of A × B. A relation on one set may be reflexive, symmetric, antisymmetric or transitive. An equivalence relation is reflexive, symmetric and transitive; it partitions a set into equivalence classes. Partial orders are reflexive, antisymmetric and transitive and model dependencies, precedence and hierarchical structures.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

6. Functions and mappings

A function assigns each element of a domain exactly one element in a codomain. Injective functions map distinct inputs to distinct outputs; surjective functions reach every codomain element; bijections are both. Composition applies one function after another. Inverse functions exist for bijections between the relevant sets. Functions model transformations, program behaviour and mappings between representations.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

7. Proof techniques and mathematical induction

A direct proof derives a conclusion from definitions and known results. A contrapositive proves P implies Q by proving not Q implies not P. A contradiction assumes the opposite and derives an impossibility. Mathematical induction proves a base case and then shows that truth for n implies truth for n+1. Strong induction allows use of all earlier cases.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

8. Counting principles and combinatorics

The sum rule counts alternatives that cannot occur together; the product rule counts sequences of choices. Permutations count ordered arrangements, while combinations count selections where order does not matter. Factorials and binomial coefficients support these calculations. Inclusion-exclusion corrects overcounting when sets overlap. Counting is essential for probability, complexity analysis and evaluating search spaces.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

9. Graphs and graph representations

A graph consists of vertices and edges. Graphs may be directed or undirected, weighted or unweighted, connected or disconnected. Degree counts incident edges, with special treatment for directed in-degree and out-degree. Adjacency lists are space-efficient for sparse graphs; adjacency matrices allow constant-time edge lookup but use quadratic space. Graphs model routes, dependencies, social links and communication networks.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

10. Trees, traversals and spanning structures

A tree is a connected acyclic undirected graph. A rooted tree establishes parent-child relationships. Binary trees have at most two children per node; binary search trees organise keys to support search, insertion and deletion when balanced. Traversals include preorder, inorder and postorder depth-first orders, and level-order breadth-first traversal. A spanning tree connects all vertices without cycles.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

11. Recurrence relations and Boolean algebra

A recurrence defines a sequence or algorithm cost using earlier values. Examples include factorial and divide-and-conquer algorithms. Solving recurrences helps estimate growth. Boolean algebra operates on true/false values using AND, OR and NOT, with identities that simplify expressions. These laws underpin logic gates, digital circuit design, search conditions and program optimisation.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

Figure 1. Logic reasoning
Propositions→Connectives and truth tables→Logical equivalence→Valid inference

Conceptual learning diagram; use alongside the explanations and practical work.

Figure 2. Set relationships
Set A and set B→Union and intersection→Difference and complement→Cartesian product

Conceptual learning diagram; use alongside the explanations and practical work.

Figure 3. Graph traversal
Start at selected vertex→Visit adjacent vertices→Track visited set→Continue until search ends

Conceptual learning diagram; use alongside the explanations and practical work.

Practical laboratory activity

  1. Write a short problem specification, listing inputs, outputs and constraints.
  2. Draw a diagram or write pseudocode before implementation.
  3. Implement a small example in an appropriate language or tool.
  4. Test normal, boundary and invalid cases; record actual and expected results.
  5. Explain the design trade-offs and suggest one improvement.

Use authorised software and test environments. Do not run experiments on systems or data without permission.

Worked reasoning and self-check

For every problem, state the assumptions first. Work through a small input manually, record each important state transition and compare the final result with the specification. If the result differs, isolate the smallest failing example and revise the reasoning before changing code. For performance questions, identify the input-size variable and count the dominant operation rather than guessing from execution time alone.

Examination and revision questions

Answer with definitions, explanations, diagrams, calculations or code traces as appropriate. Show working for numerical and algorithmic questions.

  1. What is a proposition?

    Show answer guidance

    A declarative statement with a truth value of true or false.

  2. State De Morgan's laws.

    Show answer guidance

    The negation of a conjunction is the disjunction of negations; the negation of a disjunction is the conjunction of negations.

  3. Define a set.

    Show answer guidance

    An unordered collection of distinct elements.

  4. What is an equivalence relation?

    Show answer guidance

    A relation that is reflexive, symmetric and transitive.

  5. Differentiate injective and surjective functions.

    Show answer guidance

    Injective functions map distinct inputs to distinct outputs; surjective functions reach every element of the codomain.

  6. What is mathematical induction?

    Show answer guidance

    A proof method establishing a base case and an inductive step from n to n+1.

  7. Differentiate permutation and combination.

    Show answer guidance

    A permutation counts ordered arrangements; a combination counts selections where order does not matter.

  8. What is a graph?

    Show answer guidance

    A structure consisting of vertices and edges representing relationships.

  9. What is a tree?

    Show answer guidance

    A connected acyclic undirected graph.

  10. What is an adjacency matrix?

    Show answer guidance

    A matrix representing graph connections between pairs of vertices.

  11. Define a recurrence relation.

    Show answer guidance

    A relation defining sequence terms using earlier terms.

  12. What is Boolean algebra used for?

    Show answer guidance

    Reasoning about true/false values and simplifying digital logic expressions.

  13. What is a Cartesian product?

    Show answer guidance

    The set of ordered pairs formed from elements of two sets.

  14. What is a bijection?

    Show answer guidance

    A function that is both injective and surjective.

  15. Why is discrete mathematics important to algorithms?

    Show answer guidance

    It provides tools for correctness proofs, counting, graph modelling and complexity reasoning.

Revision checklist

Further study and references

Consult current university textbooks, peer-reviewed computing research, official language and standards documentation, processor or operating-system manuals, and reputable open educational resources. Check edition, publication date and technical version. Programming language behaviour, security recommendations and software tools evolve; verify details against current official documentation.

Academic and responsible-use note: These notes support undergraduate learning. Verify course requirements with your university, cite sources in assessed work, respect software licences and data privacy, and test only systems for which you have authorisation.

Return to the full Computer Science course guide

Official Education References

Use these official organisations for curriculum guidance, examinations and further learning information.