AS Edexcel Computer Science: Formula & Theorem Quick Reference | AS Edexcel 计算机：公式定理速查手册

📚 AS Edexcel Computer Science: Formula & Theorem Quick Reference | AS Edexcel 计算机：公式定理速查手册

This quick reference handbook compiles the essential formulas, theorems, and concepts required for the AS Edexcel Computer Science specification. It is designed for rapid revision and to reinforce your understanding of key areas such as data representation, Boolean logic, algorithm analysis, and more.

本速查手册汇编了 AS Edexcel 计算机科学课程所需的基本公式、定理和核心概念，旨在帮助快速复习并强化对数据表示、布尔逻辑、算法分析等关键领域的理解。

1. Number Systems & Conversion | 数字系统与转换

Digital computers use binary, but programmers often work with decimal and hexadecimal. The conversions follow systematic rules.

数字计算机使用二进制，但程序员常与十进制和十六进制打交道。相互转换遵循系统化规则。

Decimal to Binary: Repeatedly divide the decimal number by 2, record the remainder each time. Read the remainders from bottom to top.

十进制转二进制： 将十进制数不断除以 2，记录每次的余数，由下往上读取余数。

N₁₀ → bₙ₋₁ … b₁ b₀₂

Binary to Decimal: Multiply each bit by 2 raised to its position index, then sum up.

二进制转十进制： 将每一位乘以 2 的对应位权，再求和。

D = Σ (bᵢ × 2ⁱ)

Hexadecimal Conversion: Group binary digits into nibbles of 4 bits, then replace each group with the equivalent hex digit. For decimal to hex, repeatedly divide by 16.

十六进制转换： 二进制数每 4 位一组，每组替换为对应十六进制数码。十进制转十六进制则不断除以 16。

1011 0100₂ = B4₁₆

2. Binary Arithmetic & Two’s Complement | 二进制运算与补码

Addition in binary follows the same rules as decimal, carrying when the sum exceeds 1. Subtraction is performed by adding the two’s complement of the subtrahend.

二进制加法与十进制类似，满 2 进 1。减法通过加上减数的补码（二进制补码）来实现。

Two’s complement of a binary number: Invert all bits (flip) and then add 1 to the least significant bit.

二进制补码： 所有位取反（翻转），然后在最低位加 1。

−A = (flip bits of A) + 1

Overflow detection: In signed two’s complement addition, if the carry into the sign bit differs from the carry out of the sign bit, an overflow has occurred.

溢出检测： 在带符号补码加法中，若进入符号位的进位与离开符号位的进位不同，则发生溢出。

Range: For n bits, two’s complement represents integers from −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1.

范围： 对于 n 位补码，可表示 −2ⁿ⁻¹ 到 2ⁿ⁻¹ − 1 之间的整数。

3. Floating-Point Representation | 浮点数表示

Real numbers are stored in binary as mantissa × 2^exponent. Edexcel AS typically uses a fixed-length format with a sign bit, mantissa (fraction), and exponent stored in two’s complement or excess notation.

实数以二进制存储为 尾数 × 2^指数。Edexcel AS 通常采用固定长度格式，包含符号位、尾数（小数部分）和指数（二进制补码或余码表示）。

Value = (−1)ˢ × mantissa × 2ᵉᵡᵖᵒⁿᵉⁿᵗ

Normalisation: A floating-point number is normalised when the mantissa has exactly one non-sign bit before the binary point (i.e., 1.xxx for positive, 1.xxx or 0.1xxx for two’s complement mantissa).

规格化： 当尾数的小数点前正好有一位非符号位时（正数为 1.xxx，补码尾数常为 0.1xxx 或 1.xxx），浮点数即已规格化。

Bias: The exponent is often stored with a bias (e.g., 127 for single precision). For AS, the exponent may be stored in two’s complement or excess representation.

偏移： 指数常用一个偏移量（如单精度 127）存储。AS 课程中指数可能用补码或余码表示。

4. Boolean Algebra Laws | 布尔代数定律

Boolean algebra simplifies logic circuits and expressions. The following laws are fundamental, using ‘+’ for OR, ‘·’ for AND, and ‘ (prime) for NOT.

布尔代数用于化简逻辑电路和表达式。以下基本定律中，’+’ 表示或运算，’·’ 表示与运算，’ (撇号) 表示非运算。

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

交换律：A + B = B + A ; A · B = B · A
Associative Law: (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 Law: 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 Law: A + 0 = A ; A · 1 = A

同一律：A + 0 = A ; A · 1 = A
Complement Law: A + A’ = 1 ; A · A’ = 0

补余律：A + A’ = 1 ; A · A’ = 0
Idempotent Law: A + A = A ; A · A = A

幂等律：A + A = A ; A · A = A
Domination Law: A + 1 = 1 ; A · 0 = 0

支配律：A + 1 = 1 ; A · 0 = 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

5. Logic Gates & Truth Tables | 逻辑门与真值表

Every digital circuit is built from basic gates. The core gates, their Boolean expressions, and truth tables are listed below.

每个数字电路都由基本门构成。以下是核心门的布尔表达式和真值表。

Gate	Boolean Expression	Truth Table Summary
AND	X = A · B	X=1 only when A=1 and B=1
OR	X = A + B	X=1 when at least one input is 1
NOT	X = A’	X is the inverse of A
NAND	X = (A · B)’	Inverse of AND; X=0 only when A=1 and B=1
NOR	X = (A + B)’	Inverse of OR; X=1 only when A=0 and B=0
XOR	X = A ⊕ B = A’·B + A·B’	X=1 when inputs differ
XNOR	X = (A ⊕ B)’	X=1 when inputs are same

All gates can be implemented using only NAND or only NOR gates (universal gates).

所有门均可仅用 NAND 或 NOR 门（通用门）实现。

6. Karnaugh Maps | 卡诺图

Karnaugh maps (K-maps) provide a visual method to simplify Boolean expressions. Adjacent cells differ by only one bit (Gray code).

卡诺图提供了一种化简布尔表达式的图形方法。相邻格只有一个二进制位不同（格雷码）。

2-variable K-map: Covers 4 minterms; loops of size 1, 2, or 4.

2 变量卡诺图： 覆盖 4 个最小项；可圈大小为 1、2 或 4 的组。

3-variable K-map: 8 cells, layout A\BC 00 01 11 10. Loops must be rectangular and contain 1, 2, 4, or 8 cells.

3 变量卡诺图： 8 个单元格，布局 A\BC 00 01 11 10。所圈矩形必须包含 1、2、4 或 8 个格。

4-variable K-map: 16 cells, grouped in powers of two, wrap-around permitted for top/bottom and left/right edges.

4 变量卡诺图： 16 个单元格，按 2 的次幂分组，允许上下和左右边缘环绕。

Simplification steps: Plot 1s → Group adjacent 1s in largest possible power-of-two rectangles → Write the minimal sum-of-products.

化简步骤：填入 1 → 用尽可能大的 2 的次幂矩形圈出相邻的 1 → 写出最简积之和表达式。

7. Propositional Logic Equivalences | 命题逻辑等价式

Propositional logic underpins program conditions and reasoning. Statements can be simplified using standard equivalences, which closely mirror Boolean algebra.

命题逻辑是程序条件和推理的基础。语句可使用标准等价式进行简化，它们与布尔代数非常相似。

Implication: p → q ≡ p’ + q

蕴含等价：p → q ≡ p’ + q
Contrapositive: p → q ≡ q’ → p’

逆否等价：p → q ≡ q’ → p’
Exportation: (p · q) → r ≡ p → (q → r)

输出律：(p · q) → r ≡ p → (q → r)
Absurdity: (p → q) · (p → q’) ≡ p’

归谬律：(p → q) · (p → q’) ≡ p’
De Morgan’s for Propositions: (p + q)’ ≡ p’ · q’ ; (p · q)’ ≡ p’ + q’

命题德摩根律：(p + q)’ ≡ p’ · q’ ; (p · q)’ ≡ p’ + q’

These equivalences help transform complex logical conditions into simpler, equivalent forms for coding or proof.

这些等价关系可用于在编码或证明中将复杂的逻辑条件转化为更简单的等价形式。

8. Algorithm Complexity (Big O) | 算法复杂度（大O记法）

Big O notation describes the upper bound of an algorithm’s running time or space usage. It focuses on the dominant term as input size n grows.

大O记法描述算法运行时间或空间占用的上界，侧重于输入规模 n 增大时的主导项。

Algorithm	Typical Time Complexity
Linear search (unsorted list)	O(n)
Binary search (sorted array)	O(log n)
Bubble sort, insertion sort (average/worst)	O(n²)
Merge sort (all cases)	O(n log n)
Towers of Hanoi (recursive)	O(2ⁿ)

The formal definition: 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₀.

正式定义：若存在正常数 c 和 n₀，使得对所有 n ≥ n₀ 有 0 ≤ f(n) ≤ c·g(n)，则 f(n) = O(g(n))。

Space complexity is expressed similarly, measuring extra memory used.

空间复杂度类似，度量额外使用的内存。

9. Data Storage Calculations | 数据存储计算

Understanding how to compute file sizes is essential for justifying storage requirements

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

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

AS Edexcel Computer Science: Formula & Theorem Quick Reference | AS Edexcel 计算机：公式定理速查手册