Pre-U Cambridge Computer Science: Formula & Theorem Quick Reference | Pre-U Cambridge 计算机：公式定理速查手册

📚 Pre-U Cambridge Computer Science: Formula & Theorem Quick Reference | Pre-U Cambridge 计算机：公式定理速查手册

This handbook provides a concise collection of essential formulas and theorems encountered in the Cambridge Pre-U Computer Science syllabus. Mastery of these principles supports robust problem-solving in digital logic, processor architecture, data representation and algorithm analysis.

本手册汇集了 Cambridge Pre-U 计算机科学课程中必考的核心公式与定理。掌握这些原理，能帮助你在数字逻辑、处理器体系结构、数据表示和算法分析中游刃有余。

---

1. Boolean Laws and Theorems | 布尔代数定律与定理

Boolean algebra operates on binary variables (0 and 1) and forms the backbone of digital circuit design. The following identities are fundamental.

布尔代数处理二进制变量（0 与 1），是数字电路设计的基石。以下恒等式是基础中的基础。

Identity Law: A + 0 = A and A · 1 = A

同一律：A + 0 = A 且 A · 1 = A

Complement Law: A + A’ = 1 and A · A’ = 0

互补律：A + A’ = 1 且 A · A’ = 0

Idempotent Law: A + A = A and A · A = A

幂等律：A + A = A 且 A · A = A

Distributive Law: A · (B + C) = A · B + A · C and A + B · C = (A + B) · (A + C)

分配律：A · (B + C) = A · B + A · C 以及 A + B · C = (A + B) · (A + C)

Absorption Theorem: A + A · B = A and A · (A + B) = A

吸收定理：A + A · B = A 且 A · (A + B) = A

A + A’ · B = A + B

A · (A’ + B) = A · B

---

2. De Morgan’s Theorems | 德摩根定理

De Morgan’s theorems enable the transformation between AND and OR forms via negation, a crucial technique for minimising logic circuits.

德摩根定理通过取反实现与门和或门形式的相互转换，是化简逻辑电路的关键技巧。

(A · B)’ = A’ + B’

(A + B)’ = A’ · B’

In general, the complement of an AND expression is the OR of the complements, and the complement of an OR expression is the AND of the complements.

一般地，与运算的取反等于各自取反后的或运算，或运算的取反等于各自取反后的与运算。

These theorems extend to any number of variables:

这些定理可推广到任意多个变量：

(A · B · C)’ = A’ + B’ + C’

(A + B + C)’ = A’ · B’ · C’

---

3. Karnaugh Map Simplification | 卡诺图化简

Karnaugh maps (K-maps) provide a visual method for simplifying Boolean expressions by grouping adjacent cells containing a ‘1’. The number of cells in a valid group must be a power of two (1, 2, 4, 8…).

卡诺图（K-map）通过将相邻的“1”分组，提供了一种可视化的布尔表达式化简方法。一个有效组内的单元格数必须是2的幂（1, 2, 4, 8…）。

For a function of n variables, the maximum size of a prime implicant is 2ⁿ⁻ᵏ cells, where k is the number of variables eliminated during simplification. Each grouping removes literals.

对于一个 n 变量函数，最大质蕴含项由 2ⁿ⁻ᵏ 个单元格组成，其中 k 是在化简过程中被消去的变量数。每次分组可消去文字因子。

Rule for adjacency: cells differ by only one bit. This is essential for constructing Gray-coded maps.

相邻规则：单元格之间仅相差一个比特。这对构建格雷码图至关重要。

An example of a simplified sum-of-products after K-map reduction:

常见的 K-map 化简后与或式示例：

F = A’B’ + AC

---

4. Half and Full Adders | 半加器与全加器

Adders are fundamental arithmetic circuits. A half adder adds two single bits, producing a sum (S) and a carry (C).

加法器是基本的算术电路。半加器将两个单独的位相加，产生和（S）与进位（C）。

S = A ⊕ B

C = A · B

A full adder extends this to account for an incoming carry (Cᵢₙ). Its outputs are sum and carry-out (Cₒᵤₜ).

全加器考虑输入进位（Cᵢₙ），输出为和与进位输出（Cₒᵤₜ）。

S = A ⊕ B ⊕ Cᵢₙ

Cₒᵤₜ = A · B + Cᵢₙ · (A ⊕ B)

An n-bit ripple-carry adder cascades n full adders. Its propagation delay is proportional to n, because the carry must ripple through all stages.

一个 n 位行波进位加法器级联了 n 个全加器。其传播延迟与 n 成正比，因为进位必须逐级传递。

---

5. Sequential Circuits: Flip-Flops | 时序电路：触发器

Flip-flops are memory elements that store one bit. The D-type flip-flop captures the input D on a triggering clock edge.

触发器是能存储一个比特的存储单元。D 型触发器在触发时钟边沿捕获输入 D。

Qₙₑₓₜ = D

The JK flip-flop has no undefined state and toggles when J = K = 1. Its characteristic equation is:

JK 触发器没有不定态，当 J = K = 1 时实现翻转。其特征方程为：

Qₙₑₓₜ = J · Q’ + K’ · Q

For a T flip-flop (toggle), the next state is simply Qₙₑₓₜ = T ⊕ Q.

对于 T 触发器（翻转触发器），次态就是 Qₙₑₓₜ = T ⊕ Q。

State diagrams and state tables model the behaviour of finite state machines (FSMs). The number of states required determines the number of flip-flops needed via 2ⁿ ≥ number of states.

状态图和状态表用于对有限状态机（FSM）建模。所需的状态数决定了触发器的数量，满足 2ⁿ ≥ 状态数。

---

6. Number System Conversions | 数制转换

Data within a computer is represented in binary. Conversions between binary, decimal, octal and hexadecimal are essential for low-level programming and hardware design.

计算机内部的数据采用二进制表示。二进制、十进制、八进制和十六进制之间的相互转换对于底层编程和硬件设计必不可少。

Binary to Decimal: sum of (digit × 2^position). For instance, 1011₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 11₁₀.

二进制转十进制：每位数字乘以 2 的位权求和。例如，1011₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 11₁₀。

Decimal to Binary: repeatedly divide the integer by 2, recording remainders; the binary number is the remainders read backwards. For fractional parts, multiply by 2, recording the integer part.

十进制转二进制：对整数部分反复除以 2，记录余数；余数的逆序就是二进制数。对小数部分，乘以 2 并保留整数部分，继续处理剩余的小数。

Hexadecimal to Binary: each hex digit maps directly to a 4-bit binary nibble. Example: A7₁₆ = 1010 0111₂.

十六进制转二进制：每一位十六进制数字直接映射为 4 位二进制半字节。例：A7₁₆ = 1010 0111₂。

---

7. Two’s Complement Representation | 二进制补码表示

Two’s complement is the standard way to represent signed integers. It simplifies subtraction by using the same addition hardware. To obtain the two’s complement of a binary number, invert all bits (one’s complement) and add 1.

二进制补码是表示有符号整数的标准方法。它利用相同的加法硬件简化了减法运算。要获取一个二进制数的补码，先对所有位取反（反码），然后加 1。

−x = (invert bits of x) + 1

For an n-bit number, the range of representable values is −2ⁿ⁻¹ to (2ⁿ⁻¹ − 1). The most significant bit acts as a sign bit (0 for positive, 1 for negative).

对于一个 n 位数，可表示的范围是 −2ⁿ⁻¹ 到（2ⁿ⁻¹ − 1）。最高位充当符号位（0 表示正，1 表示负）。

Overflow detection for two’s complement addition: overflow occurs if the carry into the sign bit differs from the carry out of the sign bit. Alternatively, if two positive numbers produce a negative result, or two negatives produce a positive result, overflow has occurred.

补码加法的溢出检测：若进入符号位的进位与离开符号位的进位不同，则发生溢出。另一种判断方式：两个正数相加得负数，或两个负数相加得正数时，均为溢出。

---

8. Floating-Point Format (IEEE 754) | 浮点数格式（IEEE 754）

The IEEE 754 standard dominates floating-point representation. A number is stored as V = (-1)^S × 1.M × 2^(E − Bias), where S is the sign bit, M is the mantissa (fractional part), and E is the biased exponent.

IEEE 754 标准主导了浮点数表示。一个数存储为 V = (-1)^S × 1.M × 2^(E − Bias)，其中 S 是符号位，M 是尾数（小数部分），E 是带偏移的指数。

Single precision (32 bits): 1 bit for sign, 8 bits for exponent (Bias = 127), 23 bits for mantissa.

单精度（32 位）：1 位符号、8 位指数（偏移量=127）、23 位尾数。

Double precision (64 bits): 1 bit for sign, 11 bits for exponent (Bias = 1023), 52 bits for mantissa.

双精度（64 位）：1 位符号、11 位指数（偏移量=1023）、52 位尾数。

The smallest normalized positive value in single precision is 1.0 × 2^(−126) ≈ 1.18 × 10⁻³⁸, and the largest is approximately 3.4 × 10³⁸. Denormalized numbers allow gradual underflow.

单精度中最小规格化正值为 1.0 × 2^(−126) ≈ 1.18 × 10⁻³⁸，最大值约为 3.4 × 10³⁸。非规格化数允许逐渐下溢。

---

9. Error Detection: Parity and Hamming Code | 错误检测：奇偶校验与海明码

Error detection and correction codes protect data integrity. Parity adds a single bit to make the total number of 1s even (even parity) or odd (odd parity).

错误检测与纠正码保护数据完整性。奇偶校验添加一个比特，使得所有位中 1 的个数为偶数（偶校验）或奇数（奇校验）。

Hamming code not only detects single-bit errors but also corrects them. The positions of parity bits p₁, p₂, p₄, … are at powers of two (1, 2, 4, 8 …).

海明码不仅能检测单比特错误，还能纠正。校验位 p₁, p₂, p₄, … 位于 2 的幂次位置（1, 2, 4, 8 …）。

For a message of m data bits, the number of parity bits k must satisfy:

对于 m 位数据位，所需的校验位数 k 必须满足：

2^k ≥ m + k + 1

Hamming distance is the number of bit positions in which two codewords differ. To detect d errors, a minimum Hamming distance of d + 1 is required; to correct c errors, a distance of 2c + 1 is needed.

海明距离指两个码字间不同比特位的数目。要检测 d 个错误，最小海明距离需为 d + 1；要纠正 c 个错误，距离需为 2c + 1。

---

10. CPU Performance Equations | CPU 性能公式

Processor performance is often defined by the execution time of a program. The classic CPU time equation decomposes performance into three factors.

处理器性能通常由程序执行时间定义。经典的 CPU 时间公式将性能分解为三个因素。

CPU Time = IC × CPI × Clock Cycle Time

CPU Time = (IC × CPI) / Clock Rate

Where IC = instruction count, CPI = average clock cycles per instruction. Improving any multiplier reduces overall execution time. MIPS (Millions of Instructions Per Second) is a rate metric:

其中 IC = 指令数，CPI = 平均每指令周期数。改善任意一个因子都能减少总执行时间。MIPS（每秒百万指令数）是一个速率指标：

MIPS = Clock Rate / (CPI × 10⁶)

Benchmark programs often use the SPEC ratio, which normalizes performance against a reference machine. Be cautious: a high MIPS does not always equate to a fast computer because CPI and instruction sets differ radically.

基准程序常用 SPEC 比值，将性能相对于参考机器进行归一化。需注意：高 MIPS 未必意味着计算机快，因为 CPI 和指令集差异巨大。

---

11. Amdahl’s Law | 阿姆达尔定律

Amdahl’s Law predicts the theoretical speedup of a task when only a portion of it can be improved. It imposes a hard limit on performance gains from parallelization.

阿姆达尔定律预言了当任务只有一部分能够被改进时，可获得的理论上加速比。它给并行化的性能提升设定了严格上限。

Speedup ≤ 1 / ((1 − P) + P / N)

where P is the proportion of the program that can be made parallel, (1 − P) is the sequential fraction, and N is the number of parallel processors.

其中 P 是可并行化的程序比例，(1 − P) 是串行部分，N 是并行处理器的数目。

Even with an infinite number of processors, the maximum speedup is bounded by 1 / (1 − P). For instance, if 90% of code is parallelizable, the ultimate speedup cannot exceed 10×.

即使处理器数量趋近无穷，最大加速比也被限制在 1 / (1 − P)。例如，若 90% 的代码可并行，则极限加速比不会超过 10 倍。

This law highlights the importance of optimizing the sequential parts of an algorithm. It is widely applied in multicore architecture design and GPU computing.

这一定律突显了优化算法串行部分的重要性。它在多核架构设计和 GPU 计算中被广泛应用。

---

12. Algorithm Complexity Measures | 算法复杂度度量

Algorithm efficiency is described using Big O notation, which captures the upper bound of growth rate for time or space as input size n increases.

算法效率用大 O 表示法描述，它刻画了随着输入规模 n 增长，时间或空间增长的上界。

Complexity Class	Notation	Examples
Constant	O(1)	Array access
Logarithmic	O(log n)	Binary search
Linear	O(n)	Linear search
Linearithmic	O(n log n)	Merge sort
Quadratic	O(n²)	Bubble sort
Exponential	O(2ⁿ)	Recursive Fibonacci

Recurrence relations often describe recursive algorithms. For example, the merge sort recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n) by the Master Theorem.

递归关系常用于描述递归算法。例如，归并排序的递推式 T(n) = 2T(n/2) + O(n) 利用主定理可解得 O(n log n)。

The Master Theorem provides a cookbook solution for recurrences of the form T(n) = aT(n/b) + f(n). Applying the case where a = b^k yields a direct order of growth.

主定理为形式 T(n) = aT(n/b) + f(n) 的递推式提供了公式化解法。当 a = b^k 时，可以直接得出增长阶。

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）