📚 Pre-U CCEA Computer Science: Formulas & Theorems Quick Reference Guide | Pre-U CCEA 计算机：公式定理速查手册
This quick reference guide brings together the essential formulas, theorems, and numerical concepts required for the Pre-U CCEA Computer Science specification. Use it to review key quantitative relationships across digital logic, algorithm analysis, data representation, and computer architecture. Each section is presented in a bite‑sized English–Chinese bilingual format for rapid assimilation.
本速查手册汇集了 Pre‑U CCEA 计算机科学课程中不可或缺的公式、定理与核心数值概念。覆盖数字逻辑、算法分析、数据表示和计算机体系结构等领域的定量关系，以简明中英双语对照呈现，便于快速回顾和巩固。
1. Boolean Algebra Laws | 布尔代数基本定律
Boolean algebra provides the mathematical foundation for digital logic circuits. The following laws allow simplification of logic expressions.
布尔代数是数字逻辑电路的数学基础，以下定律用于简化逻辑表达式。
Commutative Laws:
A + B = B + A
A · B = B · A
交换律：
A + B = B + A
A · B = B · A
Associative Laws:
(A + B) + C = A + (B + C)
(A · B) · C = A · (B · C)
结合律：
(A + B) + C = A + (B + C)
(A · B) · C = A · (B · C)
Distributive Laws:
A · (B + C) = A · B + A · C
A + (B · C) = (A + B) · (A + C)
分配律：
A · (B + C) = A · B + A · C
A + (B · C) = (A + B) · (A + C)
Identity Laws:
A + 0 = A
A · 1 = A
同一律：
A + 0 = A
A · 1 = A
Annulment Laws:
A + 1 = 1
A · 0 = 0
零一律：
A + 1 = 1
A · 0 = 0
Idempotent Laws:
A + A = A
A · A = A
幂等律：
A + A = A
A · A = A
Complement Laws:
A + ¬A = 1
A · ¬A = 0
互补律：
A + ¬A = 1
A · ¬A = 0
Double Negation:
¬(¬A) = A
双重否定律：
¬(¬A) = A
De Morgan’s Theorems:
¬(A · B) = ¬A + ¬B
¬(A + B) = ¬A · ¬B
德摩根定理：
¬(A · B) = ¬A + ¬B
¬(A + B) = ¬A · ¬B
Absorption Law:
A + (A · B) = A
A · (A + B) = A
吸收律：
A + (A · B) = A
A · (A + B) = A
2. Logic Gate Truth Tables | 基本逻辑门真值表
Each standard logic gate is defined by a truth table that maps input combinations to output values.
每种标准逻辑门都由真值表定义，给出所有输入组合对应的输出值。
| A | B | AND (A·B) | OR (A+B) | NOT A (¬A) | NAND | NOR | XOR (A⊕B) | XNOR |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
In CCEA questions, you are often asked to complete a truth table for a given expression or to derive a Boolean expression from a truth table by taking the OR of minterms (SOP form) or the AND of maxterms (POS form).
在 CCEA 考题中，常需根据给定表达式填写真值表，或从真值表推导布尔表达式——取所有输出为1的极小项之或（SOP 形式）或所有输出为0的极大项之与（POS 形式）。
3. Karnaugh Maps (K-Maps) | 卡诺图简化
A Karnaugh map is a visual tool for simplifying Boolean expressions of up to 4 variables. Adjacent cells differ by only one variable.
卡诺图是一种用于简化最多四变量布尔表达式的可视化工具。相邻单元仅有一个变量发生变化。
2‑variable K‑map layout: rows for A, columns for B.
二变量卡诺图布局： 行按 A，列按 B。
3‑variable K‑map (A, B, C): rows: 00, 01, 11, 10 for AB; columns: 0, 1 for C. Gray code ordering ensures adjacency.
三变量卡诺图（A, B, C）： 行按 AB 的格雷码顺序 00, 01, 11, 10；列按 C 的 0, 1。
Simplification rules: Group sizes must be powers of two (1, 2, 4, 8). Groups must be as large as possible, and may wrap around map edges. The simplified product term retains only those variables that remain constant within the group.
简化规则： 组合大小须为2的幂（1, 2, 4, 8），组合应尽可能大且可循环环绕边界。简化后的乘积项仅保留在组合内部保持不变的变量。
Example: Group of two 1’s where A=1, B varies, C=0 gives term A·¬C.
示例： 两个1的组合中 A 恒为 1，B 变化，C 恒为 0，则化简项为 A·¬C。
4. Set Theory Operations | 集合论基本运算
Set theory is used in databases, searching, and the study of finite state machines. Key operations are defined below.
集合论应用于数据库、搜索以及有限状态机的研究中，以下为关键运算。
- Union (A ∪ B): all elements in A or B.
- 并集 (A ∪ B)： 属于 A 或 B 的所有元素。
- Intersection (A ∩ B): elements common to both A and B.
- 交集 (A ∩ B)： 同时属于 A 和 B 的元素。
- Difference (A \ B): elements in A but not in B.
- 差集 (A \ B)： 属于 A 但不属于 B 的元素。
- Complement (A’ or ¬A): all elements not in A (relative to the universal set).
- 补集 (A’ 或 ¬A)： 不属于 A 的所有元素（相对于全集）。
- Cardinality |A|: number of elements in set A.
- 基数 |A|： 集合 A 中元素的个数。
- Cartesian Product (A × B): set of all ordered pairs (a,b) where a ∈ A and b ∈ B. Size: |A × B| = |A| × |B|.
- 笛卡尔积 (A × B)： 所有有序对 (a, b) 的集合，其中 a ∈ A，b ∈ B。大小：|A × B| = |A| × |B|。
Laws reminiscent of Boolean algebra: De Morgan’s laws for sets: (A ∪ B)’ = A’ ∩ B’ and (A ∩ B)’ = A’ ∪ B’.
类似布尔代数的定律： 集合的德摩根律：(A ∪ B)’ = A’ ∩ B’ 以及 (A ∩ B)’ = A’ ∪ B’。
5. Number Systems Conversion | 数制转换公式
CCEA pre‑U expects fluency in binary, denary, hexadecimal conversions and fixed‑point binary.
CCEA Pre‑U 要求熟练掌握二进制、十进制、十六进制之间转换以及定点二进制。
Binary to Denary: Sum of (bit × 2position) where positions start from 0 at the rightmost bit. For fractional binary, positions are negative.
二进制转十进制： 求各位 (bit × 2位权) 之和，位权从最右位 0 开始。小数部分位权为负。
Denary to Binary: Repeatedly divide the integer part by 2, recording remainders; read remainders bottom-up. For fractional part, repeatedly multiply by 2 and record integer parts.
十进制转二进制： 整数部分不断除以 2 记录余数，自下而上读取；小数部分不断乘以 2 记录整数部分。
Hexadecimal to Binary: Replace each hex digit with its 4‑bit binary equivalent. Hex digits: 0–9, A–F. Example: 3F₁₆ = 0011 1111₂.
十六进制转二进制： 每位十六进制数替换为对应的4位二进制。十六进制数字：0–9, A–F。例如 3F₁₆ = 0011 1111₂。
Binary to Hexadecimal: Group bits in fours from the binary point outward, then replace each group with the corresponding hex digit.
二进制转十六进制： 从小数点向两侧每4位分组，替换为对应十六进制数字。
6. Binary Arithmetic & Overflow | 二进制算术与溢出
Addition and subtraction of fixed‑size binary numbers follow specific rules. Subtraction is usually performed via two’s complement addition.
固定位宽二进制数的加减法遵循特定规则。减法通常通过补码加法实现。
Two’s complement of an n‑bit number: Invert all bits and add 1. Range for n bits: –2n–1 to 2n–1 – 1.
n 位数的二进制补码： 所有位取反后加 1。n 位表示范围：–2n–1 至 2n–1 – 1。
Addition: Add bits columnwise, carrying 1 to the next column when sum ≥ 2.
加法： 按位相加，和 ≥ 2 时向高位进位 1。
Subtraction (A – B): Compute two’s complement of B, then add to A. Discard carry beyond the n‑th bit if using n‑bit representation.
减法 (A – B)： 求 B 的补码，然后与 A 相加；若使用 n 位表示则丢弃第 n 位以外的进位。
Overflow detection: In two’s complement addition, overflow occurs when the carry into the most significant bit (MSB) is not equal to the carry out of the MSB. Alternatively, when the sum of two positive numbers gives a negative result, or sum of two negatives gives a positive result.
溢出检测： 在补码加法中，当进入最高位 (MSB) 的进位不等于出最高位的进位时发生溢出。亦可表述为：两个正数之和为负或两个负数之和为正即溢出。
7. Floating-Point Representation (IEEE 754) | 浮点数表示（IEEE 754）
IEEE 754 single precision uses 32 bits: 1 sign bit, 8 exponent bits (biased by 127), 23 mantissa (fraction) bits with a hidden ‘1’.
IEEE 754 单精度使用 32 位：1 位符号、8 位阶码（偏置 127）、23 位尾数（小数部分），并隐含一个 ‘1’。
Formula: Value = (–1)sign × (1 + fraction) × 2(exponent – 127).
公式： 值 = (–1)符号 × (1 + 小数) × 2(阶码 – 127)。
Special cases:
特殊情况：
- Exponent = 0, fraction = 0: ±0.
- 阶码 = 0, 小数 = 0：±0。
- Exponent = 0, fraction ≠ 0: subnormal numbers, value uses 0.fraction instead of 1.fraction.
- 阶码 = 0, 小数 ≠ 0：非规格化数，使用 0.fraction 而非 1.fraction。
- Exponent = 255, fraction = 0: ±∞.
- 阶码 = 255, 小数 = 0：±∞。
- Exponent = 255, fraction ≠ 0: NaN (Not a Number).
- 阶码 = 255, 小数 ≠ 0：NaN（非数）。
Precision: The mantissa provides about 7 decimal digits of precision because 2–23 ≈ 1.19 × 10–7.
精度： 尾数提供约 7 位十进制有效数字，因 2–23 ≈ 1.19 × 10–7。
8. Big‑O, Big‑Ω, Big‑Θ Notation | 大O、大Ω、大Θ表示法
Asymptotic notations describe the limiting behaviour of algorithms in terms of input size n.
渐近记号用于描述算法随输入规模 n 增长的时间或空间复杂度的极限行为。
Big‑O (upper bound): f(n) = O(g(n)) if there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀.
大O（上界）： 若存在正常数 c、n₀ 使对所有 n ≥ n₀ 有 0 ≤ f(n) ≤ c·g(n)，则 f(n) = O(g(n))。
Big‑Ω (lower bound): f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀.
大Ω（下界）： 若存在正常数 c、n₀ 使对所有 n ≥ n₀ 有 0 ≤ c·g(n) ≤ f(n)，则 f(n) = Ω(g(n))。
Big‑Θ (tight bound): f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω(g(n)).
大Θ（紧界）： 若 f(n) 同时满足 O(g(n)) 和 Ω(g(n))，则 f(n) = Θ(g(n))。
Common complexities: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2ⁿ) exponential.
常见复杂度： O(1) 常数阶，O(log n) 对数阶，O(n) 线性阶，O(n log n) 线性对数阶，O(n²) 平方阶，O(2ⁿ) 指数阶。
9. Recursive Algorithms & Recurrence Relations | 递归算法与递推关系
Many divide‑and‑conquer algorithms are modelled by recurrences. A recurrence relates T(n) to values for smaller inputs.
许多分治算法可用递推关系建模，将 T(n) 与较小输入的取值联系起来。
Master Theorem (basic form): For T(n) = a·T(n/b) + f(n) with a ≥ 1, b > 1:
主定理（基本形式）： 对于 T(n) = a·T(n/b) + f(n)，a ≥ 1，b > 1：
- If f(n) = O(nlogba – ε) for some ε > 0, then T(n) = Θ(nlogba).
- 若 f(n) = O(nlogba – ε)（ε > 0），则 T(n) = Θ(nlogba)。
- If f(n) = Θ(nlogba), then T(n) = Θ(nlogba · log n).
- 若 f(n) = Θ(nlogba)，则 T(n) = Θ(nlogba · log n)。
- If f(n) = Ω(nlogba + ε) and a·f(n/b) ≤ c·f(n) for some c < 1, then T(n) = Θ(f(n)).
- 若 f(n) = Ω(nlogba + ε) 且满足正则条件，则 T(n) = Θ(f(n))。
Example: Binary Search: T(n) = T(n/2) + Θ(1). Here a = 1, b = 2, log21 = 0, f(n) = Θ(1) = Θ(n0). By case 2, T(n) = Θ(log n).
示例：二分搜索： T(n) = T(n/2) + Θ(1)，a=1, b=2, log21=0, f(n)=Θ(1)=Θ(n0)，属于情况2，T(n)=Θ(log n)。
10. Graph Algorithms & Trees | 图算法与树
Graph theory underpins network routing, dependency analysis, and data structures. Important formulas relate to trees and traversal.
图论是网络路由、依赖分析和数据结构的基础。以下是关于树和遍历的重要公式。
For a tree with n vertices: Number of edges = n – 1.
有 n 个顶点的树： 边数 = n – 1。
Binary tree properties:
二叉树性质：
- Maximum number of nodes at level L = 2L (root level 0).
- 第 L 层最多节点数 = 2L（根为第0层）。
- Maximum total nodes in a binary tree of height h = 2h+1 – 1.
- 高度为 h 的二叉树最大节点数 = 2h+1 – 1。
- Relationship between leaf nodes (L) and nodes with two children (N): L = N + 1.
- 叶节点数 L 与双孩子节点数 N 的关系：L = N + 1。
Traversal orderings (Depth‑First): pre‑order (root, left, right), in‑order (left, root, right), post‑order (left, right, root).
深度优先遍历顺序： 前序（根左右）、中序（左根右）、后序（左右根）。
Dijkstra’s shortest path: Does not work with negative edge weights. Time complexity with adjacency list + min‑heap: O((V+E) log V).
Dijkstra 最短路径： 不能有负权边。使用邻接表+最小堆时间复杂度为 O((V+E) log V)。
11. Cache & Memory Access Time | 缓存与内存访问时间
The average memory access time (AMAT) formula captures the performance benefit of a cache hierarchy.
平均内存访问时间 (AMAT) 公式量化了缓存层次结构的性能收益。
Formula: AMAT = Hit time + Miss rate × Miss penalty.
公式： AMAT = 命中时间 + 缺失率 × 缺失代价。
Hit time is the time to access the cache on a hit. Miss rate is the fraction of accesses that miss in the cache. Miss penalty is the extra time to fetch a block from main memory into the cache, including the time to deliver the word to the processor.
命中时间指命中时访问缓存的时间；缺失率是缓存访问中缺失的比例；缺失代价是将一个块从主存读入缓存的额外时间，包括将字送至处理器的时间。
Multilevel cache: AMAT = L1 Hit time + L1 Miss rate × (L2 Hit time + L2 Miss rate × Main memory access time).
多级缓存： AMAT = L1 命中时间 + L1 缺失率 × (L2 命中时间 + L2 缺失率 × 主存访问时间)。
Effective CPI (Cycles Per Instruction) with stalls: CPI = Base CPI + Memory stall cycles per instruction. Memory stall cycles = Misses per instruction × Miss penalty (in cycles).
考虑停顿的有效 CPI： CPI = 基本 CPI + 每条指令的内存停顿周期数。内存停顿周期数 = 每条指令缺失次数 × 缺失代价（周期）。
12. Disk Access Time & RAID | 磁盘访问时间与RAID
Magnetic disk performance is dominated by mechanical delays. The total access time is the sum of seek time, rotational latency, and transfer time.
磁性磁盘的性能受机械延迟主导。总访问时间为寻道时间、旋转延迟和传输时间之和。
Total access time = Seek time + Rotational latency + Transfer time.
总访问时间 = 寻道时间 + 旋转延迟 + 传输时间。
Rotational latency (average): half of the time for one full disk revolution. If rotational speed is R rpm, average latency = (0.5 / R) minutes = (30 / R) seconds.
平均旋转延迟： 磁盘旋转一圈时间的一半。若转速为 R rpm，平均延迟 = 0.5 / R 分钟 = 30 / R 秒。
Transfer time: (Amount of data to transfer) / (Transfer rate). Transfer rate = (rotational speed) × (sectors per track) × (bytes per sector).
传输时间： 传输数据量 / 传输率。传输率 = 转速 × 每磁道扇区数 × 每扇区字节数。
RAID 0 (striping): No redundancy. Capacity = N × disk capacity. Data split into blocks striped across N disks. Improves performance but no fault tolerance.
RAID 0（条带化）： 无冗余。总容量 = N × 单盘容量。数据按块分条存储在 N 个盘上，提升性能但无容错能力。
RAID 1 (mirroring): Full data redundancy. Capacity = single disk capacity. Every write is duplicated to a second disk. Tolerates one disk failure.
RAID 1（镜像）： 完全数据冗余。容量 = 单盘容量。每次写入同时复制到镜像盘。可承受单盘故障。
RAID 5 (block‑level striping with distributed parity): Capacity = (N – 1) × disk capacity. Parity blocks are distributed across all disks. Tolerates a single disk failure. Write penalty: each small write requires reading old data and old parity to compute new parity.
RAID 5（块级条带化＋分布式奇偶校验）： 容量 = (N – 1) × 单盘容量。奇偶校验块分布所有磁盘，可承受单盘故障。小写会产生写惩罚：需读取旧数据与旧校验以计算新校验。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply