Mathematical foundations

Software engineering uses mathematics to represent data, reason about correctness, estimate cost, and interpret measurements. Learn the parts required by the problem; most application work does not require a survey of every mathematical field.

Number representation

Positional notation

For base \(b\), digits \(d_i\) represent:

\[ \sum_{i=0}^{k} d_i b^i \]

Binary uses base 2. Hexadecimal uses base 16 and maps each digit to four bits, making it a compact notation for bytes, masks, addresses, and encoded values.

An \(n\)-bit unsigned integer represents values from \(0\) through \(2^n-1\). An \(n\)-bit two's-complement signed integer represents:

\[ -2^{n-1} \text{ through } 2^{n-1}-1 \]

Integer overflow behavior depends on the language and type. It may wrap, trap, raise an exception, or be undefined. Check the actual contract.

Bitwise operations

Operation	Meaning	Common use
x & mask	AND	retain selected bits
x \| mask	OR	set selected bits
x ^ mask	XOR	toggle selected bits
~x	NOT	invert within the language's integer model
x << n	left shift	move bit pattern left
x >> n	right shift	move bit pattern right; signed behavior is language-specific

Always state the integer width when explaining masks, complements, shifts, and overflow. ~x is not meaningful as a fixed bit pattern without that context.

Use bit tricks when the representation is the requirement. Do not assume they outperform clear arithmetic without measurement; compilers and runtimes already optimize common operations.

Floating-point and decimal values

Binary floating-point stores a sign, significand, and exponent in finite space. Most real numbers—and familiar decimals such as 0.1—cannot be represented exactly.

Consequences:

• arithmetic rounds after operations;
• addition is not generally associative;
• subtracting close values can lose significant digits;
• values include positive and negative infinity, signed zero, and NaN;
• comparisons involving NaN do not behave like ordinary numbers.

For measured values, compare using an error model appropriate to their scale rather than a universal epsilon. For money or rules requiring exact decimal rounding, use an integer minor unit or a decimal type with explicit precision and rounding. Decimal arithmetic is exact only for values and operations representable under the chosen context.

When aggregating many values, order and algorithm can affect error. Validate numerical code against known cases and analyse acceptable error, not only type width.

Boolean logic

Boolean logic supports conditions, predicates, queries, and proofs.

Form	Meaning
\(A \land B\)	both are true
\(A \lor B\)	at least one is true
\(\lnot A\)	A is false
\(A \Rightarrow B\)	if A is true, B must be true
\(A \Leftrightarrow B\)	A and B have the same truth value

De Morgan's laws are useful when transforming conditions:

\[ \lnot(A \land B) = \lnot A \lor \lnot B \]

\[ \lnot(A \lor B) = \lnot A \land \lnot B \]

The implication \(A \Rightarrow B\) is false only when \(A\) is true and \(B\) is false. Its converse, \(B \Rightarrow A\), is a different claim.

Quantifiers express scope:

• \(\forall x\): the statement holds for every \(x\) in the domain;
• \(\exists x\): at least one such \(x\) exists.

Negating a quantified statement swaps the quantifier: \(\lnot \forall x\,P(x)\) means \(\exists x\,\lnot P(x)\).

Sets, relations, and functions

A set contains distinct elements. Important operations are union, intersection, difference, and membership.

A relation is a set of ordered pairs. Useful properties include:

• reflexive: \(xRx\);
• symmetric: \(xRy \Rightarrow yRx\);
• transitive: \(xRy \land yRz \Rightarrow xRz\).

An equivalence relation is reflexive, symmetric, and transitive; it partitions a set into equivalence classes.

A function maps each input in its domain to one output. It may be:

• injective: different inputs have different outputs;
• surjective: every target value is reached;
• bijective: both, so an inverse exists.

These concepts appear directly in database relations, type mappings, deduplication, identity, and API transformations.

Counting

Sum and product rules

• Mutually exclusive alternatives with \(m\) and \(n\) possibilities give \(m+n\) possibilities.
• A choice with \(m\) possibilities followed by one with \(n\) possibilities gives \(mn\) ordered outcomes.

Permutations and combinations

The number of ways to order \(n\) distinct items is:

\[n!\]

The number of ordered selections of \(k\) items from \(n\) is:

\[P(n,k)=\frac{n!}{(n-k)!}\]

The number of unordered selections is:

\[\binom{n}{k}=\frac{n!}{k!(n-k)!}\]

Counting is useful for estimating state spaces and test combinations. It also shows why exhaustive testing becomes infeasible quickly.

Probability

For events \(A\) and \(B\):

\[P(A \mid B)=\frac{P(A \cap B)}{P(B)}\]

when \(P(B)>0\).

\(A\) and \(B\) are independent when:

\[P(A \cap B)=P(A)P(B)\]

Mutual exclusion is not independence: two mutually exclusive events with positive probability cannot both occur.

Bayes' rule reverses a conditional probability:

\[ P(A \mid B)=\frac{P(B \mid A)P(A)}{P(B)} \]

The expected value of a discrete random variable is:

\[ E[X]=\sum_x xP(X=x) \]

Expectation describes a long-run average, not the value of a particular observation. Variance describes spread around the mean:

\[ \operatorname{Var}(X)=E[(X-E[X])^2] \]

Do not assume observations are independent merely because the formula is convenient. Requests, failures, and benchmark samples often share causes.

Statistics for engineering

Use statistics to describe evidence, not decorate a conclusion.

• median: central observation, resistant to extreme values;
• mean: total divided by count, useful but sensitive to extremes;
• percentile: value below which a proportion of observations falls;
• range and interquartile range: simple descriptions of spread;
• standard deviation: spread around the mean under its assumptions;
• confidence interval: range produced by a procedure with stated repeated-sampling coverage.

For latency, retain the distribution and relevant percentiles; an average can hide a slow tail. For benchmarks:

1. define the population and workload;
2. control relevant inputs;
3. repeat independent runs;
4. retain all results, not only the fastest;
5. report centre, spread, sample count, and environment;
6. distinguish statistical difference from practically useful difference.

Correlation measures association, not causation. A causal claim needs a defensible design that rules out plausible alternatives.

Logarithms and growth

\(\log_b n\) answers: “to what power must \(b\) be raised to produce \(n\)?” In algorithm analysis the base is usually omitted because different constant bases differ only by a constant factor.

Common growth classes, from slower to faster, include:

\[ 1,\ \log n,\ n,\ n\log n,\ n^2,\ 2^n,\ n! \]

Asymptotic growth predicts scaling, not elapsed time. Constants, input distribution, memory behavior, and implementation still require measurement.

Practical checks

You should be able to:

• convert small values between binary, decimal, and hexadecimal;
• state the width and signedness of an integer representation;
• explain why floating-point equality can fail;
• transform a condition with De Morgan's laws;
• count a small state space using sum, product, permutations, or combinations;
• distinguish conditional probability, independence, and mutual exclusion;
• describe a latency sample with a distribution rather than one average;
• compare growth rates without claiming they are runtime measurements.