Skip to main content
CBE Nexus · Undergraduate Software Engineering

Chapter 3: Discrete Mathematics and Logic for Software

Discrete mathematics for software engineering: propositional and predicate logic, sets, relations, functions, proof techniques, combinatorics, graphs, trees, Boolean algebra, recurrence and applications to computing.

Back to Software Engineering course guide

Chapter overview and learning outcomes

This chapter develops foundational undergraduate knowledge in discrete mathematics and logic for software, connecting theory with practical software engineering decisions. It is designed for active study: read each section, work through the examples, draw the diagrams from memory and complete the revision questions.

1. Role of discrete mathematics in computing

Discrete mathematics studies structures that are distinct or countable rather than continuously varying. It underpins algorithms, databases, programming-language semantics, networks, cryptography, verification and digital circuits. Logic supports reasoning about program conditions; sets and relations model data; graphs represent dependencies and communication; combinatorics counts possible configurations; probability helps reason about uncertainty. Mathematical notation provides concise descriptions, but every symbol must be interpreted carefully. Students should connect formal definitions to small examples and computational applications.

Engineering application and analysis

Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.

Worked study activity

Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.

2. Propositional logic and logical connectives

A proposition is a statement that is either true or false. Common connectives are negation, conjunction, disjunction, implication and biconditional. Truth tables define their semantics. Implication P → Q is false only when P is true and Q is false; it does not mean that P causes Q. De Morgan's laws relate negation to conjunction and disjunction. Logical equivalence means two propositions have identical truth values under every assignment. These ideas are directly useful when constructing program conditions and simplifying tests.

Engineering application and analysis

Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.

Worked study activity

Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.

3. Predicate logic and quantifiers

Predicate logic extends propositions with variables and predicates. The universal quantifier states that a property holds for every element in a domain; the existential quantifier states that at least one element satisfies it. Negating a universal statement produces an existential counterexample, and negating an existential statement produces a universal negative. Quantifier order matters: for example, every user having some password is different from one password being shared by every user. Formal specifications use predicates to describe preconditions, postconditions and invariants.

Engineering application and analysis

Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.

Worked study activity

Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.

4. Sets, operations and cardinality

A set is a well-defined collection of distinct elements. Membership, subset, equality, union, intersection, difference and complement are fundamental operations. The power set contains all subsets of a set; a set with n elements has 2^n subsets. Cartesian products form ordered pairs and are useful in defining relations. Cardinality measures set size. Finite sets can be counted directly, while infinite sets require more advanced reasoning. In software, sets model permissions, tags, feature flags and collections where duplicates are not meaningful.

Engineering application and analysis

Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.

Worked study activity

Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.

5. Relations, equivalence and ordering

A binary relation on a set is a subset of its Cartesian product. Relations may be reflexive, symmetric, antisymmetric or transitive. An equivalence relation is reflexive, symmetric and transitive, partitioning a set into equivalence classes. Partial orders are reflexive, antisymmetric and transitive; they model dependencies and precedence where not every pair is comparable. Relational properties appear in database theory, type systems, access-control models, scheduling and reasoning about program states.

Engineering application and analysis

Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.

Worked study activity

Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.

6. Functions, mappings and composition

A function maps each element of a domain to exactly one element of a codomain. Injective functions map distinct inputs to distinct outputs; surjective functions cover the codomain; bijections are both. Domain and codomain must be stated to interpret these properties correctly. Function composition applies one mapping after another, and inverse functions exist for bijections. Software functions are not always mathematical functions because they may mutate state, depend on time or produce side effects. The distinction helps with reasoning and testing.

Engineering application and analysis

Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.

Worked study activity

Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.

7. Proof methods and mathematical induction

A proof establishes that a statement follows logically from definitions, axioms and previously established results. Direct proof derives the conclusion from assumptions. Contradiction assumes the opposite and derives an impossibility. Contrapositive proof establishes not-Q implies not-P for an implication P implies Q. Mathematical induction proves a base case and then shows that truth for n implies truth for n+1. Strong induction may assume all earlier cases. Proofs of algorithm correctness often use loop invariants and induction over input size.

Engineering application and analysis

Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.

Worked study activity

Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.

8. Combinatorics, counting and the pigeonhole principle

Combinatorics counts arrangements and selections. The multiplication principle counts sequential choices; permutations count ordered arrangements; combinations count selections where order does not matter. Factorials and binomial coefficients arise frequently. The pigeonhole principle states that if more objects than containers are assigned, at least one container receives multiple objects. Counting supports analysis of search spaces, test combinations, password strength and algorithm complexity. Care is needed to distinguish arrangements with repetition from those without repetition.

Engineering application and analysis

Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.

Worked study activity

Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.

9. Graph theory and representations

A graph consists of vertices and edges. Graphs may be directed or undirected, weighted or unweighted, simple or multigraphs. Degree counts incident edges; paths connect vertices; cycles return to a starting vertex. Adjacency lists store neighbours and are effective for sparse graphs; adjacency matrices use a two-dimensional representation and allow fast edge lookup. Graphs model social networks, transport routes, dependency relationships, communication networks and state transitions.

Engineering application and analysis

Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.

Worked study activity

Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.

10. Trees, traversal and spanning structures

A tree is a connected acyclic undirected graph. A rooted tree distinguishes a root and parent-child relationships. Binary trees have at most two children per node; binary search trees maintain an ordering property. Tree traversals include preorder, inorder, postorder and level order. A spanning tree connects all vertices of a connected graph without cycles. Trees support file systems, syntax structures, search indexes, decision processes and hierarchical data. Balanced trees help maintain efficient operations.

Engineering application and analysis

Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.

Worked study activity

Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.

11. Boolean algebra, digital logic and recurrence

Boolean variables take values true and false or, in digital circuits, 1 and 0. Boolean operations include AND, OR and NOT, with identities that simplify expressions. Logic gates implement these operations physically. Recurrence relations define a sequence using earlier terms and arise in recursive algorithm analysis. For example, divide-and-conquer algorithms may be described by T(n)=aT(n/b)+f(n). Solving recurrences helps estimate growth and compare algorithmic approaches.

Engineering application and analysis

Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.

Worked study activity

Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.

Figure 1. Logic reasoning
State propositions and domain→Apply definitions and laws→Construct proof or counterexample→Check conclusion

Conceptual learning diagram; adapt it to the system or example being studied.

Figure 2. Graph model
Vertices represent entities→Edges represent relationships→Weights and direction add meaning→Apply traversal or optimisation

Conceptual learning diagram; adapt it to the system or example being studied.

Figure 3. Induction proof
Prove base case→Assume statement for k→Prove statement for k plus one→Conclude for all required n

Conceptual learning diagram; adapt it to the system or example being studied.

Practical laboratory / project activity

  1. Choose a bounded problem relevant to this chapter and describe the intended users and context.
  2. Write down assumptions, constraints, inputs, outputs and measurable success criteria.
  3. Develop a small prototype, model, algorithm, specification or test artefact.
  4. Use version control and document tools, versions and important decisions.
  5. Test normal, boundary and failure conditions; retain reproducible evidence.
  6. Review the result for usability, accessibility, security, reliability and maintainability.
  7. Submit a concise report explaining the method, findings, limitations and next steps.

Only test systems and datasets for which you have permission. Protect personal information and follow institutional academic-integrity and laboratory rules.

Worked reasoning and self-assessment

Begin with a precise problem statement. Separate known facts from assumptions. Identify the relevant concepts and choose a method that fits the problem constraints. Work through a small example manually, then verify the result using a suitable tool or test. Explain why the approach works, where it may fail, and what evidence would be needed to trust it in a larger system. For a design decision, state the alternatives and the trade-offs rather than presenting one choice as universally best.

Examination and revision questions

Attempt each question before opening the answer guidance. Use examples, diagrams and precise definitions in longer responses.

  1. What is a proposition?

    Show answer guidance

    A 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. Differentiate universal and existential quantifiers.

    Show answer guidance

    Universal means every element; existential means at least one element.

  4. What is a power set?

    Show answer guidance

    The set of all subsets of a given set.

  5. Define an equivalence relation.

    Show answer guidance

    A relation that is reflexive, symmetric and transitive.

  6. What is a bijection?

    Show answer guidance

    A function that is both injective and surjective.

  7. Name two proof techniques.

    Show answer guidance

    Direct proof, contradiction, contrapositive and mathematical induction.

  8. State the pigeonhole principle.

    Show answer guidance

    If more objects than containers are assigned, at least one container receives more than one object.

  9. What is a graph?

    Show answer guidance

    A set of vertices together with edges connecting pairs of vertices.

  10. What is a tree?

    Show answer guidance

    A connected, acyclic undirected graph.

  11. Differentiate adjacency list and adjacency matrix.

    Show answer guidance

    A list stores each vertex's neighbours; a matrix records pairwise adjacency in a two-dimensional array.

  12. What is a partial order?

    Show answer guidance

    A relation that is reflexive, antisymmetric and transitive.

  13. What is function composition?

    Show answer guidance

    Applying one function to the output of another.

  14. What does a loop invariant express?

    Show answer guidance

    A property that remains true before and after each loop iteration.

  15. Give two computing applications of discrete mathematics.

    Show answer guidance

    Program verification, databases, networks, cryptography, digital circuits and algorithm analysis.

Revision checklist

Further reading and academic practice

Use current university textbooks, peer-reviewed software engineering research, recognised standards and official technical documentation. Verify edition, version, publication date and applicability before citing a source. Cite quotations, data, diagrams, software and ideas according to your institution's required referencing style. Do not invent references, results or test evidence. Compare sources critically and note where professional guidance differs by context or jurisdiction.

Academic note: These notes are an educational study resource, not a substitute for your institution's current course outline, assessment brief, professional standards or supervisor guidance. The course guide is an illustrative international framework.

Return to the complete Software Engineering course guide

Official Education References

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