📚 CIE A-Level Computer Science Formula & Theorem Quick Reference | CIE A-Level 计算机公式定理速查手册
This handbook provides a concise summary of key formulas, theorems, and rules essential for the CIE A-Level Computer Science (9618) syllabus. It covers Boolean algebra, number systems, algorithm analysis, data representation, and networking fundamentals, helping you to quickly review and reinforce examination concepts.
本手册为 CIE A-Level 计算机科学（9618）课程提供关键公式、定理和规则的简明总结。内容涵盖布尔代数、数制、算法分析、数据表示和网络基础，帮助快速复习和巩固考试重点。
1. Boolean Algebra Laws | 布尔代数定律
Boolean algebra is the foundation of digital logic. The fundamental laws define how logical variables interact under AND (·) and OR (+) operations. The identity law states that A + 0 = A and A · 1 = A, while the annulment law gives A + 1 = 1 and A · 0 = 0.
布尔代数是数字逻辑的基础。基本定律定义了逻辑变量在“与”（·）和“或”（+）运算下的交互规则。同一律规定 A + 0 = A 且 A · 1 = A；零一律给出 A + 1 = 1 且 A · 0 = 0。
The idempotent law (A + A = A, A · A = A) and the complement law (A + ¬A = 1, A · ¬A = 0, where ¬A is NOT A) are also central. The involution law says ¬(¬A) = A.
等幂律（A + A = A，A · A = A）和互补律（A + ¬A = 1，A · ¬A = 0，其中 ¬A 表示非 A）也十分核心。双重否定律则是 ¬(¬A) = A。
Other essential laws include commutativity (A + B = B + A, A · B = B · A), associativity (A + (B + C) = (A + B) + C, A · (B · C) = (A · B) · C), and distributivity (A · (B + C) = A · B + A · C, A + B · C = (A + B) · (A + C)).
其他基本定律包括交换律（A + B = B + A，A · B = B · A）、结合律（A + (B + C) = (A + B) + C，A · (B · C) = (A · B) · C）以及分配律（A · (B + C) = A · B + A · C，A + B · C = (A + B) · (A + C)）。
Absorption law simplifies expressions: A + A · B = A and A · (A + B) = A. These laws are used to reduce gate counts in circuit design.
吸收律用于化简表达式：A + A · B = A 以及 A · (A + B) = A。这些定律用于减少电路设计中的门数量。
2. De Morgan’s Theorems | 德摩根定理
De Morgan’s theorems are crucial for converting between AND/OR logic and NAND/NOR implementations. The first theorem states: ¬(A · B) = ¬A + ¬B. The complement of a product equals the sum of the complements.
德摩根定理对于在“与/或”逻辑和“与非/或非”实现之间进行转换至关重要。第一定理：¬(A · B) = ¬A + ¬B。积的补等于补的和。
The second theorem states: ¬(A + B) = ¬A · ¬B. The complement of a sum is the product of the complements. These can be extended to multiple variables: ¬(A · B · C) = ¬A + ¬B + ¬C, and ¬(A + B + C) = ¬A · ¬B · ¬C.
第二定理：¬(A + B) = ¬A · ¬B。和的补等于补的积。这两个定理可推广到多个变量：¬(A · B · C) = ¬A + ¬B + ¬C 以及 ¬(A + B + C) = ¬A · ¬B · ¬C。
De Morgan’s is applied repeatedly in Boolean simplification and in converting circuits to use only NAND or only NOR gates, which are universal gates.
德摩根定理在布尔化简以及将电路转换为仅使用与非门或仅使用或非门（它们是通用门）时被反复应用。
3. Karnaugh Map Simplification Rules | 卡诺图化简规则
A Karnaugh map (K-map) provides a visual method to minimise Boolean expressions. For 2 variables, the map has 4 cells; for 3 variables, 8 cells; for 4 variables, 16 cells. Adjacency follows Gray code ordering: 00, 01, 11, 10.
卡诺图提供了一种最小化布尔表达式的可视化方法。对于两个变量，图中有 4 个单元格；三个变量有 8 个单元格；四个变量有 16 个单元格。相邻性遵循格雷码顺序：00, 01, 11, 10。
Cells containing 1 are grouped in rectangles of sizes that are powers of two (1, 2, 4, 8). Larger groups produce simpler product terms. Groups can wrap around the edges of the map because of the cyclic adjacency.
包含 1 的单元格被组合成大小为 2 的幂的矩形（1, 2, 4, 8）。更大的组得到更简单的乘积项。由于循环相邻性，组可以环绕图的边缘。
Each group yields a product term where a variable is eliminated if it appears in both true and complemented forms within the group. The final simplified expression is the sum (OR) of all group product terms.
每个组产生一个乘积项，其中如果某个变量在该组内同时以原变量和反变量形式出现，则该变量被消除。最终化简表达式是所有组乘积项之和（或）。
Don’t-care conditions (denoted by X) can be treated as either 0 or 1 to make groups as large as possible, further simplifying the expression.
无关项（记为 X）可被视为 0 或 1，以使组尽可能大，从而进一步化简表达式。
4. Binary Number Conversion & Representation | 二进制数与转换表示
Binary to decimal conversion uses positional weighting: for an n-bit binary number b_{n-1}…b_1 b_0, its decimal value is Σ b_i × 2^i. For example, 1011₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 11₁₀.
二进制转十进制使用位权：对于 n 位二进制数 b_{n-1}…b_1 b_0，其十进制值为 Σ b_i × 2^i。例如，1011₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 11₁₀。
Decimal to binary conversion uses repeated division by 2, recording remainders in reverse order. For fractional numbers, repeated multiplication by 2 captures the integer parts. Hexadecimal uses base 16 (digits 0-9, A-F), where one hex digit represents 4 bits.
十进制转二进制使用反复除以 2 取余，余数逆序排列。对于小数部分，反复乘以 2 取其整数部分。十六进制使用基数为 16（数字 0-9, A-F），其中一位十六进制数代表 4 位二进制。
Quick conversion between hex and binary: group binary digits into nibbles from the right. Example: 10111010₂ = 1011 1010 = BA₁₆. Hex to binary is the reverse: each hex digit expands to 4 bits.
十六进制与二进制之间的快速转换：从右开始将二进制数字分组为半字节。示例：10111010₂ = 1011 1010 = BA₁₆。十六进制到二进制则相反：每位十六进制数字展开为 4 位二进制。
5. Two’s Complement Arithmetic | 二进制补码运算
Two’s complement is the standard method for representing signed integers in binary. To negate a number: flip all bits (one’s complement) and add 1. For an n-bit word, range of values is –2^{n-1} to +2^{n-1} – 1.
二进制补码是表示有符号整数的标准方法。对一个数求反：将所有位取反（反码）然后加 1。对于 n 位字长，取值范围为 –2^{n-1} 至 +2^{n-1} – 1。
Addition and subtraction follow normal binary addition rules; the carry out beyond the most significant bit is ignored, but overflow must be checked. Overflow occurs when the result exceeds the representable range. For addition, if the two operands have the same sign and the result has a different sign, overflow has occurred.
加法和减法遵循正常的二进制加法规则；超出最高有效位的进位被忽略，但必须检查溢出。当结果超出表示范围时发生溢出。对于加法，如果两个操作数符号相同而结果的符号不同，则发生了溢出。
Example with 4 bits: 5 (0101) + 4 (0100) = 9 (1001 in 4-bit two’s complement is –7, overflow because 9 > 7). Similarly, subtraction is implemented as addition of the two’s complement of the subtrahend: A – B = A + (–B).
以 4 位为例：5 (0101) + 4 (0100) = 9（4 位补码中 1001 是 –7，溢出因为 9 > 7）。同样，减法实现为被减数加上减数的补码：A – B = A + (–B)。
6. Floating-Point Normalisation (Simplified) | 浮点数规格化（简版）
A simplified floating-point representation consists of a sign bit, mantissa, and exponent. Normalisation maximises precision by adjusting the mantissa so that its most significant bit after the sign is different from the sign bit. For a positive number, the mantissa’s first bit after the sign is 1; for a negative number, it is 0.
简化的浮点数表示由符号位、尾数和指数组成。规格化通过调整尾数使得符号位后的最高有效位与符号位不同，以此最大化精度。对于正数，尾数在符号位后的第一位是 1；对于负数，则是 0。
Value = (–1)^{sign} × mantissa × 2^{exponent}. The exponent is usually stored in excess or biased notation (e.g., excess-127 for single precision), but in simplified A-level problems, two’s complement may be used for exponent as well.
值 = (–1)^{sign} × 尾数 × 2^{指数}。指数通常以移码或偏置记法存储（例如单精度用偏置 127），但在简化的 A-level 题目中，指数也可能使用二进制补码。
To normalise a binary floating-point number, shift the mantissa left or right while incrementing or decrementing the exponent respectively, until the first two bits of the mantissa are different.
规格化一个二进制浮点数时，将尾数左移或右移，同时相应地增加或减少指数，直到尾数的前两位不同。
7. Logic Gates and Truth Tables | 逻辑门与真值表
Basic logic gates: AND (output 1 if all inputs 1, Boolean: A·B), OR (output 1 if at least one input 1, A+B), NOT (inverter, ¬A). NAND is ¬(A·B), NOR is ¬(A+B), XOR is A⊕B (1 when inputs differ), XNOR is ¬(A⊕B) (1 when inputs same).
基本逻辑门：与门（所有输入为 1 时输出 1，布尔表达式 A·B），或门（至少一个输入为 1 时输出 1，A+B），非门（反相器，¬A）。与非门 ¬(A·B)，或非门 ¬(A+B)，异或门 A⊕B（输入相异时出 1），同或门 ¬(A⊕B)（输入相同时出 1）。
Each gate has a truth table listing all input combinations with corresponding output. The number of rows is 2ⁿ for n inputs. Gates are combined to form circuits, and the truth table of a combinational circuit can be derived by evaluating outputs of intermediate stages.
每个门都有列出所有输入组合及对应输出的真值表。对于 n 个输入，真值表有 2ⁿ 行。门组合成电路，组合逻辑电路的真值表可通过计算中间级输出来推导。
NAND and NOR gates are functionally complete, meaning any Boolean function can be implemented using only NAND gates or only NOR gates. Circuit representation symbols follow IEEE/ANSI standards, often using distinctive shapes (AND: flat with curve, OR: shield shape, NOT: triangle with bubble).
与非门和或非门在功能上是完备的，这意味着任何布尔函数都可以仅用与非门或仅用或非门来实现。电路表示符号遵循 IEEE/ANSI 标准，通常使用独特形状（与门：平头加弧线，或门：盾形，非门：带小圆的三角形）。
8. Algorithm Complexity – Big O Notation | 算法复杂度–大O表示法
Big O notation describes the worst-case or upper bound of an algorithm’s time or space requirements as a function of input size n. Common complexities, from best to worst: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2ⁿ) exponential.
大 O 表示法描述了算法的时间或空间需求在最坏情况下的上界，作为输入规模 n 的函数。常见复杂度从优到劣依次为：O(1) 常数，O(log n) 对数，O(n) 线性，O(n log n) 线性对数，O(n²) 平方，O(2ⁿ) 指数。
O(1): execution time independent of input size, e.g., array access by index. O(log n): time grows logarithmically, often seen in binary search on a sorted array. O(n): linear scan of an array.
O(1)：执行时间与输入规模无关，例如按索引访问数组。O(log n)：时间按对数增长，常见于对有序数组的二分查找。O(n)：对数组的线性扫描。
O(n log n): typical of efficient sorting algorithms like merge sort and quicksort (average). O(n²): nested loops over the data, such as bubble sort and insertion sort. O(2ⁿ): exponential growth, seen in recursive solution to the Towers of Hanoi or brute-force subsets.
O(n log n)：典型的高效排序算法如归并排序和快速排序（平均情况）。O(n²)：对数据的嵌套循环，如冒泡排序和插入排序。O(2ⁿ)：指数增长，见于汉诺塔的递归解法或暴力求子集。
9. Searching and Sorting Algorithms Complexity | 查找与排序算法复杂度
Linear search: worst-case O(n) time, O(1) space. Binary search: O(log n) time on a sorted array, O(1) space. Binary search repeatedly divides the search interval in half: mid = (low + high) / 2.
线性查找：最坏情况时间 O(n)，空间 O(1)。二分查找：在有序数组上时间 O(log n)，空间 O(1)。二分查找反复将搜索区间对半分割：mid = (low + high) / 2。
Bubble sort: O(n²) comparisons and swaps, but O(n) in best case with early exit flag. Insertion sort: O(n²) worst, O(n) best. Both are in-place and stable. Merge sort: O(n log n) time, O(n) auxiliary space; stable. Quicksort: O(n log n) average, O(n²) worst; in-place but not stable.
冒泡排序：涉及 O(n²) 次比较和交换，但若设置提前退出标志，最佳情况为 O(n)。插入排序：最坏 O(n²)，最佳 O(n)。两者都是原地且稳定的。归并排序：时间 O(n log n)，辅助空间 O(n)；稳定。快速排序：平均 O(n log n)，最坏 O(n²)；原地但不稳定。
For A-level, the typical space-time trade-offs and qualitative understanding of why these complexities arise are important. Merge sort’s recurrence is T(n) = 2T(n/2) + O(n) leading to O(n log n).
在 A-level 阶段，理解这些复杂度出现的原因以及时空权衡的定性认识很重要。归并排序的递推关系为 T(n) = 2T(n/2) + O(n)，导出 O(n log n)。
10. Recursive Relations for Algorithms | 递归关系公式
A recurrence relation expresses the running time of a recursive algorithm in terms of smaller subproblems. A common form is T(n) = aT(n/b) + f(n), where a is number of subproblems, n/b is size of each, and f(n) is the cost of dividing/combining.
递推关系用更小的子问题来表示递归算法的运行时间。常见形式为 T(n) = aT(n/b) + f(n)，其中 a 是子问题数量，n/b 是每个子问题的规模，f(n) 是分割与合并的代价。
Binary search: T(n) = T(n/2) + O(1) ⇒ O(log n). Merge sort: T(n) = 2T(n/2) + O(n) ⇒ O(n log n). The Master Theorem (simplified) helps solve such recurrences when applicable, but CIE often expects tracing the recursion tree or repeated substitution.
二分查找：T(n) = T(n/2) + O(1) ⇒ O(log n)。归并排序：T(n) = 2T(n/2) + O(n) ⇒ O(n log n)。主定理（简化版）可在适用时帮助求解，但 CIE 常期望通过递归树或反复代入法来求解。
For recursive factorial: T(n) = T(n-1) + O(1) ⇒ O(n). For Towers of Hanoi: T(n) = 2T(n-1) + O(1) ⇒ O(2ⁿ). Understanding the base case (T(1) = O(1)) is essential.
对于递归阶乘：T(n) = T(n-1) + O(1) ⇒ O(n)。对于汉诺塔：T(n) = 2T(n-1) + O(1) ⇒ O(2ⁿ)。理解基本情况（T(1) = O(1)）至关重要。
11. Error Detection: Parity & Checksum | 错误检测：奇偶校验与校验和
Parity adds a redundant bit to make the total number of 1s in a byte either even (even parity) or odd (odd parity). It can detect a single-bit error but not correct it, and fails if two bits flip.
奇偶校验通过添加一个冗余位，使一个字节中 1 的总数为偶数（偶校验）或奇数（奇校验）。它能检测单比特错误但无法纠正，且若有两位翻转则会失效。
A checksum divides data into segments of a fixed size (e.g., bytes or words) and sums them (often ignoring overflow or using one’s complement). The checksum value is appended to the data. At the receiver, the sum is recomputed and compared. Mismatch indicates error.
校验和将数据分成固定大小的段（如字节或字），对它们求和（通常忽略溢出或使用反码）。校验和值附加在数据末尾。接收端重新计算总和并比较，不匹配则表明有错误。
Internet checksum uses one’s complement addition with end-around carry. Longitudinal redundancy check (LRC) combines parity across bytes for block error detection. These are all simple error-detection methods covered in CIE.
互联网校验和使用带循环进位的反码加法。纵向冗余校验（LRC）跨字节组合奇偶校验以实现块错误检测。这些都是 CIE 涵盖的简单错误检测方法。
12. Networking: Transmission Time & Latency | 网络：传输时间与延迟
The time to transmit a file of size S over a link of bandwidth B is given by Transmission time = S / B. Ensure consistent units: if S is in bits, B in bps, then time in seconds. For example, a 8 Megabit file over 2 Mbps link takes 8×10⁶ / 2×10⁶ = 4 seconds.
在带宽为 B 的链路上传输大小为 S 的文件，所需时间由 传输时间 = S / B 给出。确保单位一致：若 S 单位为比特，B 为 bps，则时间单位为秒。例如，在一个 2 Mbps 链路上传输 8 兆比特文件，耗时 8×10⁶ / 2×10⁶ = 4 秒。
Latency (propagation delay) is the time for a signal to travel from sender to receiver: Latency = Distance / Propagation speed. Total delay = Transmission time + Propagation delay + Queuing/Processing delays (often negligible in exam problems).
延迟（传播时延）是信号从发送端到达接收端所需的时间：延迟 = 距离 / 传播速度。总延迟 = 传输时间 + 传播延迟 + 排队/处理延迟（在考试题目中常可忽略）。
Packet switching introduces store-and-forward delay at each hop. For a message divided into P packets with H header bits each, the total time = (S + P·H) / B + (number of links) × (packet transmission time) if considering pipeline, but usually simplified to per-hop delay.
分组交换在每个跳点引入存储转发延迟。对于分为 P 个分组，每个分组带有 H 比特头部的报文，若考虑流水线，总时间 = (S + P·H) / B + （链路数）×（分组传输时间），但通常简化为每跳延迟。
Effective throughput can be lower than bandwidth due to protocol overhead and retransmissions. Understanding these basic formulas is critical for network performance questions.
由于协议开销和重传，有效吞吐量可能低于带宽。理解这些基本公式对网络性能问题至关重要。
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