📚 Year 12 Edexcel Computer Science: Formula & Theorem Quick Reference | Year 12 Edexcel 计算机：公式定理速查手册
This quick reference guide compiles the essential formulas, laws, and theorems you will encounter in the Year 12 Edexcel Computer Science curriculum. From Boolean algebra simplification to algorithm complexity, keep this handbook close for revision and exam preparation.
本速查手册汇集了 Year 12 Edexcel 计算机科学课程中你必须掌握的关键公式、定律和定理。从布尔代数化简到算法复杂度，复习和备考时请随身携带本手册。
1. Boolean Algebra Laws | 布尔代数基本定律
Boolean algebra provides the mathematical foundation for digital logic circuits. The following identities hold for any Boolean variables A, B, and C. The AND operation is often denoted by a dot (·) or by simple juxtaposition, while OR is denoted by a plus sign (+). NOT is indicated by an overbar or a negation symbol (¬).
布尔代数为数字逻辑电路提供了数学基础。对于任意布尔变量 A、B 和 C，下列恒等式成立。AND 运算常以点号（·）或直接并列表示，OR 运算以加号（+）表示，NOT 运算以上划线或否定符号（¬）表示。
Identity: A + 0 = A A · 1 = A
Null: A + 1 = 1 A · 0 = 0
Idempotent: A + A = A A · A = A
Complement: A + ¬A = 1 A · ¬A = 0
Double Negation: ¬(¬A) = A
Commutative: A + B = B + A A · B = B · A
Associative: (A + B) + C = A + (B + C) (A · B) · C = A · (B · C)
Distributive: A + (B · C) = (A + B) · (A + C) A · (B + C) = (A · B) + (A · C)
Absorption: A + (A · B) = A A · (A + B) = A
2. De Morgan's Theorem | 德摩根定理
De Morgan's theorem describes how to transform the complement of an AND expression into an OR expression of complements, and vice versa. It is essential for simplifying circuits and converting between NAND/NOR logic.
德摩根定理描述了如何将 AND 表达式的补转换为补的 OR 表达式，反之亦然。它对简化电路以及 NAND/NOR 逻辑之间的转换至关重要。
First theorem: ¬(A · B) = ¬A + ¬B
Second theorem: ¬(A + B) = ¬A · ¬B
Generalised for n variables: ¬(A₁ · A₂ · ... · Aₙ) = ¬A₁ + ¬A₂ + ... + ¬Aₙ, and ¬(A₁ + A₂ + ... + Aₙ) = ¬A₁ · ¬A₂ · ... · ¬Aₙ.
推广到 n 个变量：¬(A₁ · A₂ · ... · Aₙ) = ¬A₁ + ¬A₂ + ... + ¬Aₙ，以及 ¬(A₁ + A₂ + ... + Aₙ) = ¬A₁ · ¬A₂ · ... · ¬Aₙ。
3. Karnaugh Maps and Minimisation | 卡诺图与化简
A Karnaugh map (K-map) is a visual method for simplifying Boolean expressions without having to apply algebraic laws repeatedly. You group adjacent 1s in powers of two to eliminate variables that appear in both true and complemented forms.
卡诺图（K-map）是一种可视化的布尔表达式化简方法，无需反复套用代数定律。将相邻的 1 以 2 的幂次分组，可以消除那些同时以原变量和反变量出现的变量。
For a 2-variable map the layout uses Gray code order: 00, 01, 11, 10. For 3 variables: 000, 001, 011, 010, 110, 111, 101, 100. The group size can be 1, 2, 4, or 8. Each group yields a product term. Summing all product terms from the groups gives the minimal sum-of-products (SoP) expression.
对于二变量卡诺图，布局采用格雷码顺序：00, 01, 11, 10。三变量：000, 001, 011, 010, 110, 111, 101, 100。分组大小可以是 1, 2, 4 或 8。每个分组产生一个乘积项。将所有分组的乘积项相加即得到最简的积之和（SoP）表达式。
4. Binary and Hexadecimal Conversions | 二进制与十六进制转换
Understanding number base conversions is fundamental for representing data, memory addresses, and machine code. In the Edexcel specification you must confidently convert between denary, binary, and hexadecimal.
理解进制转换是表示数据、内存地址和机器码的基础。Edexcel 考纲要求你能自信地在十进制、二进制和十六进制之间进行转换。
to Denary: ∑ (bit × 2^position) where position starts at 0 from the least significant bit.
Denary to Binary: Repeated division by 2, recording remainders from bottom to top.
Binary to Hex: Group bits in fours from the right; each nibble maps to 0–F.
n-bit range (unsigned): 0 to 2ⁿ − 1
n-bit range (signed two's complement): −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1
5. Two's Complement Representation | 二进制补码表示
Two's complement is the standard method for representing signed integers in binary. It avoids the double‑zero problem of sign‑and‑magnitude and simplifies arithmetic hardware.
补码是二进制表示有符号整数的标准方法，它避免了原码表示中的双零问题，并简化了算术硬件。
To obtain −N: invert all bits of N, then add 1.
For an n-bit number: Value = (−bₙ₋₁ × 2ⁿ⁻¹) + (bₙ₋₂ × 2ⁿ⁻²) + ... + (b₀ × 2⁰)
bits: 1101 0110₂ = −128 + 64 + 16 + 4 + 2 = −42₁₀ (if the MSB is 1, it is negative in two's complement interpretation).
以 8 位为例：1101 0110₂ = −128 + 64 + 16 + 4 + 2 = −42₁₀（当最高有效位为 1 时，按补码解释即为负数）。
6. Floating‑Point Binary and Normalisation | 浮点二进制与规范化
Floating‑ nt. Normalisation ensures maximum precision by adjusting the mantissa so that the most significant bit (after the sign bit) is a 1, avoiding leading zeros.
浮点数表示以 尾数 × 2^指数 的形式存储实数。规范化通过调整尾数使得符号位之后的最高有效位为 1，从而避免前导零，确保最大精度。
A typical 16‑ ^exponent. In normalised form a positive mantissa has the first bit of its magnitude as 1, e.g., 0.1xxx... for positive numbers.
典型的 16 位格式可能分配 10 位给尾数（含符号位），6 位给指数（含符号位）。十进制数值计算为：尾数 × 2^指数。在规范形式中，正尾数的数值部分首位为 1，例如对于正数为 0.1xxx...。
7. Error Detection: Parity Bits and Check Digits | 错误检测：奇偶校验位与校验位
Simple error detection techniques are used to identify single‑bit errors in transmission or storage. Parity bits and check digits like the Luhn algorithm are explicitly mentioned in the specification.
简单的错误检测技术用于识别传输或存储中的单比特错误。考纲中明确提到了奇偶校验位和如 Luhn 算法之类的校验位。
Even parity bit: set so that total number of 1s (including parity) is even.
Odd parity bit: set so that total number of 1s is odd.
Parity bits can detect an odd number of bit flips but cannot correct errors. The Luhn algorithm is used for credit card numbers and employs a weighted sum to produce a check digit. It catches most single‑digit errors and transpositions.
奇偶校验位能检测奇数个比特翻转，但无法纠错。Luhn 算法用于信用卡号码，通过加权和生成校验位，可检测大多数单数字错误和相邻数字换位。
8. Algorithm Complexity and Big‑O Notation | 算法复杂度与大 O 表示法
Big‑O notation describes the upper bound of an algorithm's time or space requirements as the input size n grows. Constant factors are ignored, and only the dominant term is considered.
大 O 表示法描述了随着输入规模 n 增长，算法时间或空间需求的上界。常数因子被忽略，只考虑主导项。
O(1) – constant time
O(log n) – logarithmic time (e.g., binary search)
O(n) – linear time (e.g., linear search)
O(n log n) – linearithmic time (e.g., merge sort)
O(n²) – quadratic time (e.g., bubble sort, insertion sort)
O(2ⁿ) – exponential time (e.g., brute force travelling salesman)
In the exam you may be asked to compare algorithms by their growth rates or to determine the complexity of a given pseudocode loop structure.
考试中可能要求你根据增长率比较算法，或判断给定伪代码循环结构的复杂度。
9. Search Algorithms | 搜索算法
Two fundamental search algorithms are linear search and binary search. Understanding their mechanics and complexity is a core requirement for Year 12.
两种基本搜索算法是线性搜索和二分搜索。理解其机制与复杂度是 Year 12 的核心要求。
Linear search: worst‑case O(n), average O(n). Does not require sorted data.
Binary search: worst‑case O(log n), average O(log n). Requires sorted data. Each step halves the search interval.
t) / 2 (integer division). Recursive implementations use a call stack with depth O(log n).
二分搜索中点公式：mid = left + (right − left) / 2（整数除法）。递归实现使用调用栈，深度为 O(log n)。
10. Sorting Algorithms | 排序算法
Sorting algorithms are vital for data organisation. Year 12 Edexcel focuses on bubble sort, insertion sort, and merge sort. You need to know how they work and their time complexity.
排序算法对数据整理至关重要。Year 12 Edexcel 重点考查冒泡排序、插入排序和归并排序。你需要了解它们的工作原理和时间复杂度。
Bubble sort: Compare adjacent items, swap if out of order. Worst/average O(n²). Best O(n) if already sorted (with optimisation). Stable.
Insertion sort: Build sorted sublist one element at a time. O(n²) worst/average, O(n) best. Stable.
Merge sort: Divide array into halves recursively, then merge sorted halves. Worst/average/best O(n log n). Requires O(n) auxiliary space. Stable.
For the exam be prepared to trace these algorithms on small arrays and to identify the number of comparisons or swaps.
考试中要准备能在小型数组上追踪这些算法，并识别比较次数或交换次数。
11. Logic Gates and Truth Tables | 逻辑门与真值表
A solid command of basic logic gates is required for designing and interpreting combinational circuits. The fundamental gates are AND, OR, NOT, NAND, NOR, XOR, and XNOR.
掌握基本逻辑门是设计和解读组合电路的必要条件。基本门包括与门、或门、非门、与非门、或非门、异或门和同或门。
| Gate | Symbol (Boolean) | Truth table summary |
|---|---|---|
| AND | A · B | Output 1 only when all inputs are 1. |
| OR | A + B | Output 1 when at least one input is 1. |
| NOT | ¬A | Inverts the input. |
| NAND | ¬(A · B) | Opposite of AND. |
| NOR | ¬(A + B) | Opposite of OR. |
| XOR | A ⊕ B | Output 1 when inputs differ. |
| XNOR | ¬(A ⊕ B) | Output 1 when inputs are the same. |
12. Data Structures: Stacks and Queues | 数据结构：栈与队列
Stacks and queues are abstract data structures used to manage data in a particular order. A stack follows Last‑In‑First‑Out (LIFO), while a queue follows First‑In‑First‑Out (FIFO). Operations are standardised and appear frequently in algorithm pseudocode.
栈和队列是用于按特定顺序管理数据的抽象数据结构。栈遵循后进先出（LIFO），而队列遵循先进先出（FIFO）。其操作已标准化，且频繁出现在算法伪代码中。
Stack operations: push(item), pop(), peek(), isEmpty(), size()
Queue operations: enqueue(item), dequeue(), peek(), isEmpty(), size()
Applications: stacks are used in recursion, expression evaluation, and undo features; queues are used in scheduling, buffering, and breadth‑first search. Understanding their pointer manipulation (top/rear pointers) helps in tracing algorithms.
应用：栈用于递归、表达式求值和撤销功能；队列用于调度、缓冲和广度优先搜索。理解其指针操作（栈顶/队尾指针）有助于追踪算法。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图