Year 12 OCR Computer Science: Formula & Theorem Quick Reference Handbook | Year 12 OCR 计算机：公式定理速查手册

📚 Year 12 OCR Computer Science: Formula & Theorem Quick Reference Handbook | Year 12 OCR 计算机：公式定理速查手册

This handbook concisely presents the essential formulae, theorems, and computational rules required for the Year 12 OCR A-level Computer Science course. It covers Boolean algebra, data representation, binary arithmetic, and algorithmic efficiency – equipping you with a one‑stop reference for revision and problem‑solving.

本手册简明地列出了 Year 12 OCR A-level 计算机科学课程中所必需的核心公式、定理和计算规则。内容涵盖布尔代数、数据表示、二进制运算以及算法效率，为你提供复习与解题的一站式参考。

1. Fundamental Boolean Algebra Laws | 基本布尔代数定律

Boolean algebra operates on binary variables (0 and 1) under the operations AND (·), OR (+), and NOT (¬). The following laws form the foundation of all logic simplification.

布尔代数在二进制变量（0 和 1）上使用与（·）、或（+）、非（¬）运算。下列定律是所有逻辑化简的基础。

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

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

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

零律：A + 1 = 1 且 A · 0 = 0

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

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

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

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

Involution Law: ¬(¬A) = A

双重否定律：¬(¬A) = A

Commutative Law: A + B = B + A and A · B = B · A

交换律：A + B = B + A 且 A · B = B · A

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

结合律：(A + B) + C = A + (B + C) 且 (A · B) · C = A · (B · C)

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 Law: A + (A · B) = A and A · (A + B) = A

吸收律：A + (A · B) = A 且 A · (A + B) = A

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

De Morgan’s theorems provide a powerful way to transform ANDs into ORs (and vice versa) under negation. They are critical for circuit simplification and NAND/NOR gate design.

德摩根定理提供了在取反条件下将“与”转换为“或”（以及反向转换）的强大方法，对电路化简和与非/或非门设计至关重要。

¬(A · B) = ¬A + ¬B

¬(A + B) = ¬A · ¬B

These theorems also extend to multiple variables, e.g., ¬(A·B·C) = ¬A + ¬B + ¬C.

这些定理也可推广到多个变量，例如 ¬(A·B·C) = ¬A + ¬B + ¬C。

In practice, De Morgan’s laws allow you to replace an AND gate with bubbled inputs by a NOR gate, and an OR gate with bubbled inputs by a NAND gate.

实践中，德摩根定律允许你用带泡输入的或非门替代与门，用带泡输入的与非门替代或门。

3. Simplification Using Boolean Laws | 使用布尔定律化简表达式

Complex Boolean expressions can be reduced to simpler forms using the fundamental laws. This minimises the number of logic gates in a circuit.

复杂的布尔表达式可利用基本定律化简为更简单的形式，从而减少电路中逻辑门的数量。

Example: Simplify A·B + A·¬B

示例：化简 A·B + A·¬B

Factor A: A·(B + ¬B) = A·1 = A

提取 A：A·(B + ¬B) = A·1 = A

Example: Simplify ¬A·¬B + ¬A·B

示例：化简 ¬A·¬B + ¬A·B

Factor ¬A: ¬A·(¬B + B) = ¬A·1 = ¬A

提取 ¬A：¬A·(¬B + B) = ¬A·1 = ¬A

Look for opportunities to apply absorption, distribution, and complementary pairs. Always double-check using truth tables if unsure.

需寻找应用吸收律、分配律和互补项的机会。如有疑问，始终使用真值表进行双重验证。

4. Karnaugh Maps (K‑Maps) | 卡诺图

Karnaugh maps provide a visual method for simplifying Boolean expressions with up to 4 variables. Group adjacent 1s in powers of two to obtain minimal sum-of-products (SOP) or product-of-sums (POS) forms.

卡诺图为最多四个变量的布尔表达式化简提供了可视化方法。将相邻的“1”按 2 的幂次分组，以获得最简的“与或式”（SOP）或“或与式”（POS）。

For a 2-variable K‑map, the cells correspond to minterms: ¬A·¬B, ¬A·B, A·¬B, A·B.

对于两变量卡诺图，单元格对应于最小项：¬A·¬B, ¬A·B, A·¬B, A·B。

For 3 variables (A, B, C), the map uses Gray code ordering: 00, 01, 11, 10 for BC, and rows for A=0 and A=1.

对于三个变量（A, B, C），卡诺图采用格雷码排序：BC 为 00, 01, 11, 10，行分别表示 A=0 和 A=1。

Groups can wrap around edges. Each group eliminates the variable that changes within the group.

分组可以环绕边界。每个分组可消去在该组内发生变化的变量。

Rule: A group of 2ⁿ cells eliminates n variables. The final simplified term is the product of the constant variables.

规则：2ⁿ 个单元格的分组可消去 n 个变量。最终化简项为那些保持不变的变量之积。

5. Logic Gate Equivalences & Universal Gates | 逻辑门等价与通用门

Any Boolean function can be implemented using only NAND gates or only NOR gates. The equivalences below are essential for circuit conversion.

任何布尔函数都可以仅用与非门或仅用或非门来实现。以下等价关系对于电路转换至关重要。

NOT using NAND: Connect both inputs together: ¬A = A NAND A

用与非门实现非门：将两个输入端连接在一起：¬A = A NAND A

AND using NAND: A AND B = ¬(A NAND B) using two NANDs (the first NAND followed by a NAND inverter).

用与非门实现与门：A AND B = ¬(A NAND B)，使用两个与非门（先与非，再接一个非门形式的与非门）。

OR using NAND: A OR B = (¬A NAND ¬B) by De Morgan.

用与非门实现或门：根据德摩根定理，A OR B = (¬A NAND ¬B)。

Similarly, for NOR gates: NOT = A NOR A; OR = ¬(A NOR B); AND = (¬A NOR ¬B).

类似地，对于或非门：非门 = A NOR A；或门 = ¬(A NOR B)；与门 = (¬A NOR ¬B)。

6. Number System Conversion Formulae | 数制转换公式

Computers store data in binary, but humans often work in decimal or hexadecimal. The conversion rules below are precise and testable.

计算机以二进制存储数据，但人类常使用十进制或十六进制。下面的转换规则精确且可考。

Binary to Decimal: Multiply each bit by 2ⁿ, where n is the position from right starting at 0. Sum the products.

二进制转十进制：将每一位乘以 2ⁿ，其中 n 为从右开始以 0 计数的位置。将乘积求和。

Decimal = ∑ (bitₖ × 2ᵏ)

十进制 = ∑ (bitₖ × 2ᵏ)

Decimal to Binary: Repeatedly divide the number by 2; read remainders from bottom to top.

十进制转二进制：反复将数值除以 2；从下往上读取余数。

Binary to Hexadecimal: Group bits into nibbles (4 bits) from right to left. Convert each nibble to its hex symbol (0‑9, A‑F).

二进制转十六进制：从右向左将位每四位一组（半字节）。将每组转换为相应的十六进制符号（0‑9, A‑F）。

Hexadecimal to Binary: Replace each hex digit with its 4‑bit binary equivalent.

十六进制转二进制：将每个十六进制数字替换为其等价的 4 位二进制数。

Denary to Hex: Divide by 16 repeatedly; read remainders from bottom to top, converting 10‑15 to A‑F.

十进制转十六进制：反复除以 16；从下往上读取余数，并将 10‑15 转换为 A‑F。

7. Binary Arithmetic & Overflow Rules | 二进制运算与溢出规则

Binary addition and subtraction (using two’s complement) follow fixed‑width rules. Recognising overflow is key for signed arithmetic.

二进制加法和减法（使用补码）遵循固定位宽规则。识别溢出对有符号运算至关重要。

Binary Addition Half‑Adder: Sum = A ⊕ B, Carry = A · B

半加器二进制加法：和 = A ⊕ B，进位 = A · B

Full‑Adder: Sum = A ⊕ B ⊕ Cᵢₙ, Carry‑out = (A·B) + (Cᵢₙ·(A⊕B))

全加器：和 = A ⊕ B ⊕ Cᵢₙ，进位输出 = (A·B) + (Cᵢₙ·(A⊕B))

Two’s Complement Negation: Invert all bits and add 1. For an n‑bit number N, its negative is 2ⁿ – N.

补码取负：将所有位取反后加 1。对于一个 n 位的数 N，其负数为 2ⁿ – N。

Overflow Rule for Signed Addition: Overflow occurs when two numbers with the same sign produce a result of the opposite sign. (Carry into sign bit ≠ carry out of sign bit).

有符号加法溢出规则：当两个符号相同的数相加得到符号相反的结果时，发生溢出。（进入符号位的进位 ≠ 出符号位的进位）。

8. Floating‑point Representation | 浮点表示

Floating‑point stores numbers in the form ± mantissa × 2ᵉˣᵖᵒⁿᵉⁿᵗ. OCR usually uses a simplified model with a fixed‑size mantissa and exponent in two’s complement.

浮点数以 ±尾数 × 2ᵉˣᵖᵒⁿᵉⁿᵗ 的形式存储。OCR 通常使用尾数和用补码表示的固定长度阶码的简化模型。

Form: Mantissa (signed fraction) and exponent (signed integer). Value = mantissa × 2ᵉˣᵖᵒⁿᵉⁿᵗ.

形式：尾数（有符号小数）和阶码（有符号整数）。数值 = 尾数 × 2ᵉˣᵖᵒⁿᵉⁿᵗ。

To normalise a positive binary floating‑point number, shift the mantissa left until its first two bits are 01 (for positive) or 10 (for negative), adjusting the exponent accordingly.

要对一个正二进制浮点数进行规格化，将尾数左移直至其前两位为 01（正数）或 10（负数），并相应调整阶码。

Precision: The number of mantissa bits determines precision; the exponent range determines the magnitude limits.

精度：尾数的位数决定精度；阶码的范围决定数值的极限。

Conversion from Denary: Convert the number to binary fixed‑point, then shift the point to the normalised form and encode mantissa and exponent.

从十进制转换：将数字转换为二进制定点形式，然后移动小数点至规格化形式，并对尾数和阶码进行编码。

9. Data Compression Metrics | 数据压缩度量

Compression reduces file size. The compression ratio formula is fundamental for comparing lossless and lossy techniques.

压缩可减小文件大小。压缩率公式是比较无损与有损技术的基础。

Compression Ratio = Uncompressed Size / Compressed Size

压缩率 = 压缩前大小 / 压缩后大小

A ratio of 2:1 means the compressed file is half the original size. Lossless methods (e.g., run‑length encoding, Huffman coding) allow exact reconstruction; lossy methods (e.g., JPEG, MP3) sacrifice some fidelity for higher ratios.

2:1 的比率表示压缩文件大小为原始大小的一半。无损方法（如游程编码、哈夫曼编码）可精确重建；有损方法（如 JPEG、MP3）为获得更高的压缩率会牺牲部分保真度。

Run‑length Encoding (RLE): Replaces repeated characters with a count and the character. Efficiency depends on data repetition.

游程编码（RLE）：用计数和字符本身替换重复的字符。效率依赖于数据重复程度。

10. Algorithm Complexity – Big‑O Notation | 算法复杂度 – 大 O 标记法

Big‑O notation describes how the runtime or memory usage of an algorithm grows as the input size n increases. It is vital for comparing algorithms.

大 O 标记法描述算法运行时间或内存使用随输入规模 n 增长的方式，对于比较算法至关重要。

Complexity	Big‑O	Example Algorithm
Constant	O(1)	Array index access
Logarithmic	O(log n)	Binary search
Linear	O(n)	Linear search
Log‑linear	O(n log n)	Merge sort, quicksort (average)
Quadratic	O(n²)	Bubble sort, insertion sort
Cubic	O(n³)	Naïve matrix multiplication
Exponential	O(2ⁿ)	Recursive Fibonacci

For Year 12, focus on O(1), O(log n), O(n), O(n²), and recognising these growth patterns from pseudocode loops.

在 Year 12 阶段，重点关注 O(1)、O(log n)、O(n)、O(n²)，并能从伪代码循环中识别这些增长模式。

11. Searching Algorithms – Step Count Formulae | 搜索算法 – 步数公式

Understanding the worst‑case and average number of comparisons helps in evaluating search efficiency.

理解最坏情况和平均比较次数有助于评估搜索效率。

Linear Search: Checks each element sequentially.

线性搜索：顺序检查每个元素。

Worst‑case comparisons: n. Average comparisons for a successful search: (n+1)/2.

最坏情况比较次数：n。成功搜索的平均比较次数：(n+1)/2。

Binary Search: Requires a sorted array; repeatedly divides the search interval in half.

二分搜索：要求数组已排序；反复将搜索区间减半。

Maximum comparisons = ⌈log₂(n+1)⌉. This logarithmic growth makes binary search extremely efficient on large datasets.

最大比较次数 = ⌈log₂(n+1)⌉。这种对数增长使得二分搜索在大型数据集上极为高效。

12. Sorting Algorithms – Key Performance Metrics | 排序算法 – 关键性能指标

Sorting algorithms are compared by time complexity and stability. A stable sort preserves the relative order of equal elements.

排序算法通过时间复杂度和稳定性进行比较。稳定排序能保持相等元素的相对顺序。

Algorithm	Best	Average	Worst	Stable?
Bubble Sort	O(n)	O(n²)	O(n²)	Yes
Insertion Sort	O(n)	O(n²)	O(n²)	Yes
Merge Sort	O(n log n)	O(n log n)	O(n log n)	Yes
Quicksort	O(n log n)	O(n log n)	O(n²)	No (usually)

Bubble sort performs n−1 passes, each making up to n−i−1 comparisons. Insertion sort shifts elements one position at a time. Merge sort uses divide‑and‑conquer; quicksort employs a pivot.

冒泡排序进行 n−1 趟，每趟最多进行 n−i−1 次比较。插入排序一次移动一个位置。归并排序采用分治法；快速排序使用基准值。

These metrics are vital for OCR exam questions on algorithm analysis and selection.

这些指标对于 OCR 考试中有关算法分析和选择的题目至关重要。

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

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

Year 12 OCR Computer Science: Formula & Theorem Quick Reference Handbook | Year 12 OCR 计算机：公式定理速查手册