Free degree-level computing lessons for careful independent study.
Aplailasain by Static Carnival

Degree Level Programmes · Formal Computing Foundations · Lesson 1

Why Formal Foundations Matter in Computing

Explain why formal notation, modelling and proof support reliable computing work.

Back to courseNext lesson

Lesson overview

Explain why formal notation, modelling and proof support reliable computing work.

CourseFundamentals of Computing
Topic strandOrientation
Assessment styleDigital exam practice
EvidenceWorked answer plus justification

Starter: make the model explicit

Before reading the worked example, write down the objects involved, the claim being made and the notation you expect to use. This prevents the common error of calculating before modelling.

Learning objectives

  • Distinguish informal intuition from formal modelling.
  • Connect formal topics to programming, data, networks and software design.
  • Describe what good evidence looks like in a mathematical computing answer.

Learning outcomes

  • By the end of this lesson, you can distinguish informal intuition from formal modelling.
  • By the end of this lesson, you can connect formal topics to programming, data, networks and software design.
  • By the end of this lesson, you can describe what good evidence looks like in a mathematical computing answer.

Key vocabulary

formal modelabstractionprecisionevidence

What this lesson is about

Formal foundations are the precise ideas that let computing move from informal descriptions to reliable systems. They include sets for collections, logic for conditions, functions for mappings, graphs for connections and proof for justification.

The aim is not to memorise isolated mathematics. It is to use formal ideas to make computing claims clearer, testable and less ambiguous.

Terms, acronyms and named methods

These are the phrases and named techniques used in this lesson. Read this section before the worked example so the notation and examples have a clear meaning.

Formal modelPhrase. A deliberately precise representation of part of a computing situation. It names the objects, assumptions and rules so that a claim can be checked rather than guessed.
AbstractionPhrase. The act of keeping the details that matter for the current question and ignoring details that do not. For example, a network model may keep devices and links but ignore cable colour.
EvidencePhrase. The working, definition, calculation, proof or counterexample that justifies an answer. At degree level, a correct result without evidence is usually incomplete.

Formal notation and definitions

Model: real situation → formal objects → valid inference → computing decision. The arrow symbol → means 'leads to' or 'is translated into' in this learning route.A claim is useful only when its domain, assumptions and conclusion are explicit. A domain is the collection of objects the claim is about.

How to read the symbols

domainThe collection of objects, inputs, states or cases the claim is about.
→\toRead as 'leads to' or 'is translated into' in the modelling route.
claimA statement that should be justified from definitions, assumptions or evidence.

Use the arrow symbol → to mean 'is translated into' or 'leads to'. In a formal model, state the domain first: the collection of inputs, users, records, states or cases that the claim is about.

First precise model: sets

A set is a well-defined collection of objects. In computing, sets are useful whenever we need to say exactly which records, users, states, files or permissions are included in a rule.

UThe universal set: the whole collection currently under discussion.
x ∈ AMembership: x is an individual object, A is a set, and x is an element of A.
x ∉ ANon-membership: x is an individual object, A is a set, and x is not an element of A.
A ⊆ USubset: A and U are sets, and every element of A is also inside U.
A ∩ PIntersection: A and P are sets, and this means objects that are in A and also in P.
A ∪ PUnion: A and P are sets, and this means objects that are in A, in P, or in both.
A \ PDifference: A and P are sets, and this means objects that are in A but not in P.

How to read the diagram

The rectangle is U, the universal set, meaning all users in this example. The left circle is A, users with admin rights. The right circle is P, users with paid accounts. The overlap is A ∩ P, users who are both admins and paid-account users.

The diagram supports understanding, but it is not the proof. A degree-level answer must still use the definitions: membership, subset, intersection, union and difference.

Worked interpretation

Scenario: A system rule says that only paid admins may approve refunds.

Formal model: Let U be all users, A be users with admin rights, and P be users with paid accounts. The eligible users are A ∩ P.

Reasoning: If x ∈ A ∩ P, then x ∈ A and x ∈ P. In plain English, x is an admin and x is a paid-account user. Therefore x satisfies both parts of the approval rule.

Computing meaning: The implementation should check both conditions. Checking only x ∈ A would allow unpaid admins; checking only x ∈ P would allow paid users without admin rights.

Degree-level reasoning

Formal methods support computing by making claims testable and assumptions inspectable. This matters in requirements, algorithms, data modelling, networking and security.

The habit to develop is not memorising symbols, but using symbols to remove ambiguity.

Do not stop at a correct-looking answer. State why the method is valid, whether the result depends on a hidden assumption, and what would count as a counterexample.

Worked formal model

This section shows the model, notation, calculation and interpretation as one worked answer. The notation is part of the reasoning, not decoration.

1. Context and objects

A password rule, a database filter and a network route all need exact meaning before they can be implemented safely.

Objects: a computing situation, the formal objects chosen to represent it, the assumptions, and the claim to be justified.

Model cue: Use a modelling chain: start with the real computing situation, name the formal objects, state assumptions, derive a conclusion, then translate that conclusion back into a computing decision.

2. Mathematical working

Scenario→objects→assumptions→claim→justified decision\text{Scenario}\to\text{objects}\to\text{assumptions}\to\text{claim}\to\text{justified decision}U={all system users},A={u∈U∣u is an admin},P={u∈U∣u is paid}U=\{\text{all system users}\},\quad A=\{u\in U\mid u\text{ is an admin}\},\quad P=\{u\in U\mid u\text{ is paid}\}Eligible=A∩P,Approve(u)⇒u∈EligibleEligible=A\cap P,\quad \text{Approve}(u)\Rightarrow u\in Eligible
Plain text version
Model: real situation → formal objects → valid inference → computing decision. The arrow symbol → means 'leads to' or 'is translated into' in this learning route.
A claim is useful only when its domain, assumptions and conclusion are explicit. A domain is the collection of objects the claim is about.

Worked use: For a refund-approval rule, let U be all users, A be admin users and P be paid-account users. The policy 'only paid admins may approve refunds' is modelled by Eligible = A ∩ P. If x ∈ Eligible, then x ∈ A and x ∈ P, so x satisfies both required conditions.

3. How to read the working

  1. Read the first line as a modelling route: an informal scenario is turned into named objects, assumptions, a claim and then a justified computing decision.
  2. In the set definitions, U fixes the domain of users, A names admins and P names paid-account users; the vertical bar means 'such that'.
  3. Eligible = A ∩ P says a refund approver must belong to both sets. The implication Approve(u) ⇒ u ∈ Eligible is a rule about every user u, not one example.
  4. Check the implementation meaning: if a user can approve without being in both A and P, the formal rule and the program disagree.

4. Computing meaning and check

The formal model makes the boundary of a computing claim visible: which objects are in scope, which assumptions are being made, and which conclusion is justified.

Now check: Explain why the formal model would be wrong if the implementation checked only A or only P. State the counterexample user in each case.

Worked example

From scenario to formal reasoning

Scenario: A password rule, a database filter and a network route all need exact meaning before they can be implemented safely.

Method: Use the definitions and notation introduced above, then state what the result means in this computing scenario.

Reveal model answer

For a refund-approval rule, let U be all users, A be admin users and P be paid-account users. The policy 'only paid admins may approve refunds' is modelled by Eligible = A ∩ P. If x ∈ Eligible, then x ∈ A and x ∈ P, so x satisfies both required conditions.

Worked solution structure

How a strong answer should be written

  1. Define: State the domain and the objects under discussion. For this lesson, begin from Model: real situation → formal objects → valid inference → computing decision. The arrow symbol → means 'leads to' or 'is translated into' in this learning route.
  2. Apply: Use the relevant definition from orientation; do not rely on the diagram, wording or intuition alone.
  3. Check: Test a boundary case, counterexample candidate or representation limit.
  4. Conclude: Write one sentence that connects the formal result back to the computing scenario.

Common misconception

A common mistake is treating this module as separate from computing practice. The point is to make hidden assumptions visible before code or systems depend on them.

Guided practice

  1. Model a refund-approval rule with U as all users, A as admins and P as paid-account users. Write the eligible set and explain the implementation check.
  2. Give one counterexample user that would pass an admin-only check but fail the intended paid-admin rule.
  3. Write two sentences explaining why a formal model is stronger evidence than a vague statement such as 'check the right users'.
  4. Translate the formal result back into a coding decision: which two boolean conditions must be checked?

Quick checks

1. For 'only paid admins may approve refunds', which set describes eligible users?

2. Which user is a counterexample to an admin-only check?

Digital exam practice

Example exam task

A refund system should allow approvals only for users who are both admins and paid-account users. Define U, A and P, write the eligible set, state the permission implication, and give one counterexample for checking only A and one for checking only P.

Notation toolkit

UU

Means: the universe or domain being discussed

How to use: State it before using any set such as A or P.

A∩PA\cap P

Means: the overlap: objects that are in both A and P

How to use: Use it when a rule requires two conditions at the same time.

P⇒QP\Rightarrow Q

Means: if P is true, then Q must be true

How to use: Use it to express a permission rule or required consequence.

What a good answer is expected to show

A strong answer for this lesson defines a computing situation, the formal objects chosen to represent it, the assumptions, and the claim to be justified, applies the orientation method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

  1. Read the first line as a modelling route: an informal scenario is turned into named objects, assumptions, a claim and then a justified computing decision.
  2. In the set definitions, U fixes the domain of users, A names admins and P names paid-account users; the vertical bar means 'such that'.
  3. Eligible = A ∩ P says a refund approver must belong to both sets. The implication Approve(u) ⇒ u ∈ Eligible is a rule about every user u, not one example.
  4. Check the implementation meaning: if a user can approve without being in both A and P, the formal rule and the program disagree.

Model answer

Reveal model answer
U={u∣u is a system user},A={u∈U∣Admin⁡(u)},P={u∈U∣Paid⁡(u)}U=\{u\mid u\text{ is a system user}\},\quad A=\{u\in U\mid \operatorname{Admin}(u)\},\quad P=\{u\in U\mid \operatorname{Paid}(u)\}Eligible=A∩PEligible=A\cap PApprove⁡(u)⇒u∈Eligible\operatorname{Approve}(u)\Rightarrow u\in Eligible

Let U be all users, A be admin users and P be paid-account users. The eligible approvers are Eligible = A ∩ P. The permission rule is Approve(u) ⇒ u ∈ Eligible, so approval requires both admin status and paid-account status. An unpaid admin is a counterexample to checking only A; a paid non-admin is a counterexample to checking only P.

Practise next

  1. Model a refund-approval rule with U as all users, A as admins and P as paid-account users. Write the eligible set and explain the implementation check.
  2. Give one counterexample user that would pass an admin-only check but fail the intended paid-admin rule.

Self-marking criteria

  • Defines U, A and P before using notation.
  • Uses Eligible = A ∩ P or an equivalent condition.
  • States that approval requires membership of both A and P.
  • Gives two clear counterexample users.
  • Connects the model to implementation checks.

Extension

Change one assumption in the worked scenario and decide whether the same method still applies. If it does not, name the exact point where the reasoning breaks.

Study route

Save one clean worked answer from this lesson. Include the problem statement, notation, working, final answer and a short note explaining the computing meaning of the result.

Next lesson: Mathematical Notation, Sets and Statements.