Formula & Theorems Quick Reference Guide for SQA Computing | SQA 计算机公式定理速查手册

📚 Formula & Theorems Quick Reference Guide for SQA Computing | SQA 计算机公式定理速查手册

This quick reference guide collects the essential formulas, laws and theorems needed for Year 13 SQA Computing Science. It covers Boolean algebra, processor performance, data representation, networking, algorithm complexity, database normalisation and software metrics. Use this handbook to revise key quantitative relationships and logical identities that appear across the Advanced Higher Computing Science specification.

本速查手册汇集了SQA 计算机科学Year 13所需的核心公式、定律与定理，涵盖布尔代数、处理器性能、数据表示、网络传输、算法复杂度、数据库规范化和软件度量。利用本手册复习进阶高等计算科学考试中涉及的关键量化关系和逻辑恒等式。

1. Boolean Algebra Identities | 布尔代数恒等式

The fundamental identities of Boolean algebra allow simplification of logic expressions. They apply the operations AND (∧), OR (∨) and NOT (¬).

布尔代数的基本恒等式用于化简逻辑表达式，其运算包括与（∧）、或（∨）和非（¬）。

Identity laws: A ∨ 0 = A and A ∧ 1 = A.

恒等律：A ∨ 0 = A 以及 A ∧ 1 = A。

Annihilator laws: A ∨ 1 = 1 and A ∧ 0 = 0.

零一律：A ∨ 1 = 1 以及 A ∧ 0 = 0。

Idempotent laws: A ∨ A = A and A ∧ A = A.

幂等律：A ∨ A = A 以及 A ∧ A = A。

Complement laws: A ∨ ¬A = 1 and A ∧ ¬A = 0.

互补律：A ∨ ¬A = 1 以及 A ∧ ¬A = 0。

Double negation: ¬(¬A) = A.

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

Commutative laws: A ∨ B = B ∨ A and A ∧ B = B ∧ A.

交换律：A ∨ B = B ∨ A 以及 A ∧ B = B ∧ A。

Associative laws: (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 laws: 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 laws: A ∨ (A ∧ B) = A and A ∧ (A ∨ B) = A.

吸收律：A ∨ (A ∧ B) = A 以及 A ∧ (A ∨ B) = A。

2. De Morgan’s Theorems & Logic Simplification | 德摩根定理与逻辑化简

De Morgan’s theorems provide a systematic way to push negation into brackets and are essential for converting logic expressions.

德摩根定理提供了将否定运算符推入括号的系统方法，是转换逻辑表达式的关键。

¬(A ∧ B) = ¬A ∨ ¬B

¬(A ∨ B) = ¬A ∧ ¬B

These theorems allow any logic circuit to be built using only NAND or NOR gates, and they are fundamental in simplifying digital logic.

利用这两个定理可以将任何逻辑电路仅用与非门或或非门实现，它们是化简数字逻辑的基础。

When simplifying a Boolean expression, apply identities step by step: remove double negations first, then expand using distributive laws, group terms and apply absorption. De Morgan’s laws are often used to obtain sum-of-products or product-of-sums forms.

化简布尔表达式时，逐步运用恒等式：先去双重否定，用分配律展开，组合项并应用吸收律。德摩根定律常用于得到与-或式或或-与式。

Truth tables can verify that an original expression and its simplified form are equivalent.

真值表可验证原始表达式与化简形式等价。

3. Performance Metrics: CPU Time & Clock Speed | 性能指标：CPU时间与时钟速度

Processor performance is governed by clock rate, cycle count and instruction mix. The core formula is:

处理器性能由时钟频率、周期数和指令组合决定。核心公式为：

CPU Time = Instruction Count × CPI / Clock Rate

Where CPI is the average clock cycles per instruction. Clock rate is measured in Hz (cycles per second).

其中CPI是每条指令的平均时钟周期数。时钟频率以Hz（周期/秒）为单位。

Frequently you will need to calculate execution time, e.g.: a program with 5 × 10⁶ instructions, CPI = 2.5 and a 2 GHz clock gives:

经常需要计算执行时间，例如：一个程序有5×10⁶条指令，CPI=2.5，时钟频率2 GHz，则：

Time = (5×10⁶ × 2.5) / (2×10⁹) = 6.25×10⁻³ seconds = 6.25 ms

Relative performance: Speedup = Old execution time / New execution time. If a system is improved and runs a task in 4 s instead of 10 s, the speedup is 2.5.

相对性能：加速比 = 原执行时间 / 新执行时间。若系统改进后一个任务从10秒降到4秒，加速比为2.5。

Throughput (tasks per second) is the inverse of execution time per task in a pipelined or parallel system.

在流水线或并行系统中，吞吐量（每秒完成任务数）是每任务执行时间的倒数。

4. Memory & Storage Calculations | 存储器与存储计算

Memory capacity, data transfer rate and access time are common calculations in the Computer Systems unit.

内存容量、数据传输率和访问时间是计算机系统单元中的常见计算。

Capacity: Number of addressable locations × word size. For a 32-bit address bus, locations = 2³²; if each word is 8 bits, total capacity = 2³² bytes = 4 GiB.

容量：可寻址单元数 × 字长。32位地址总线，单元数=2³²；若每个字8位，总容量=2³² 字节 = 4 GiB。

Transfer rate: (Bus width in bytes) × (bus speed in transfers per second). E.g., a 64-bit (8-byte) bus running at 100 MHz provides 800 MB/s.

传输率：（总线宽度，字节）×（总线速度，传输次数/秒）。例如，64位（8字节）总线以100 MHz运行，提供800 MB/s。

Average disk access time: Seek time + Rotational latency + Transfer time. Rotational latency = 0.5 / (revolutions per second) for a typical random access. For a 7200 RPM disk, rotational latency ≈ 4.17 ms.

平均磁盘访问时间：寻道时间 + 旋转延迟 + 传输时间。旋转延迟 = 0.5 / (每秒转数)（典型随机访问）。7200 RPM磁盘的旋转延迟约4.17 ms。

Data transfer time: Data size / Transfer rate. If a 5 MB file is read at 50 MB/s, transfer time = 0.1 s.

数据传输时间：数据量 / 传输率。若5 MB文件以50 MB/s读取，传输时间=0.1秒。

5. Data Representation: Binary & Floating-Point | 数据表示：二进制与浮点数

Numbers are stored in binary using unsigned, sign-and-magnitude or two’s complement for integers. Real numbers use floating-point representation.

数字以二进制存储，整数可用无符号、原码或补码（二进制补码）表示，实数使用浮点表示法。

Range for n-bit unsigned: 0 to 2ⁿ − 1.

n位无符号数范围：0 到 2ⁿ − 1。

Range for n-bit two’s complement: −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1.

n位二进制补码范围：−2ⁿ⁻¹ 到 2ⁿ⁻¹ − 1。

Floating-point binary: value = (−1)ˢ × mantissa × 2ᵉˣᵖᵒⁿᵉⁿᵗ. Mantissa is normalised to maximise precision (typically 1 ≤ mantissa < 2 in signed representation).

浮点二进制：值 = (−1)ˢ × 尾数 × 2指数。尾数通常被规格化以最大化精度（在带符号表示中一般1 ≤ 尾数 < 2）。

To calculate the range of a floating-point format, find the most negative and most positive values using the minimum and maximum exponent. Precision is determined by the number of mantissa bits.

要计算浮点格式的取值范围，使用最小指数和最大指数找出最负和最正值。精度由尾数的位数决定。

Conversion between denary and floating-point binary requires normalising the mantissa and encoding the exponent in excess notation (e.g., excess-127 or excess-64).

十进制与浮点二进制之间的转换需要规格化尾数并以移码（如移127码或移64码）对指数编码。

6. Networking: Data Transmission Formulas | 网络：数据传输公式

Key quantitative relationships describe how quickly data moves through networks and the internet.

关键的定量关系描述了数据在网络和互联网中传输的速度。

Transmission time: Data size (bits) / Bandwidth (bits per second). Example: a 100 Mbit file over a 1 Gbps link takes 0.1 s.

传输时间：数据量（比特） / 带宽（比特/秒）。例如：100 Mbit文件通过1 Gbps链路需0.1秒。

Propagation delay: Distance / Propagation speed (approx. 2 × 10⁸ m/s in copper/fibre).

传播延迟：距离 / 传播速度（铜缆/光纤中约为2×10⁸ 米/秒）。

Total delay per packet: Transmission time + Propagation delay + Queuing delay. In a network with multiple hops, sum the delays at each link.

每数据包总延迟：传输时间 + 传播延迟 + 排队延迟。在多跳网络中，将各链路的延迟相加。

Effective throughput: Amount of data successfully delivered / time. Overhead from headers, acknowledgments and retransmissions reduces throughput below raw bandwidth.

有效吞吐量：成功交付的数据量 / 时间。报头、确认和重传造成的开销使吞吐量低于原始带宽。

Round-Trip Time (RTT): Time for a signal to go to the destination and back. Important for TCP window size: optimal window = Bandwidth × RTT.

往返时间（RTT）：信号到达目的地并返回的时间。对TCP窗口大小很重要：最佳窗口 = 带宽 × RTT。

7. Algorithm Complexity & Big O Notation | 算法复杂度与大O表示法

Big O notation describes the upper bound of an algorithm’s running time or space usage as a function of input size n. It helps compare the efficiency of algorithms independently of hardware.

大O表示法描述了算法运行时间或空间使用随输入规模n增长的上界，有助于脱离硬件比较算法效率。

O(1) – Constant time: execution independent of n (e.g., array access by index).

O(1) – 常数时间：执行与n无关（如按索引访问数组）。
O(log n) – Logarithmic: often seen in binary search.

O(log n) – 对数时间：常见于二分查找。
O(n) – Linear: simple loop iterating over n elements.

O(n) – 线性时间：遍历n个元素的简单循环。
O(n log n) – Linearithmic: efficient sorting algorithms like merge sort.

O(n log n) – 线性对数时间：高效排序算法如归并排序。
O(n²) – Quadratic: nested loops over n, e.g., bubble sort.

O(n²) – 平方时间：n²次迭代的嵌套循环，如冒泡排序。
O(2ⁿ) – Exponential: recursive solution to Towers of Hanoi.

O(2ⁿ) – 指数时间：汉诺塔的递归解法。

Space complexity is similarly expressed. When analysing algorithms, focus on the dominant term and drop constants: 3n² + 2n + 5 becomes O(n²).

空间复杂度同样表示。分析算法时关注主导项并省略常数：3n² + 2n + 5 记作 O(n²)。

Common search algorithm complexities: linear search O(n), binary search O(log n). Common sorting complexities: bubble, insertion, selection O(n²); merge sort and heap sort O(n log n); quick sort average O(n log n) but worst-case O(n²).

常见查找算法复杂度：线性查找 O(n)，二分查找 O(log n)。常见排序复杂度：冒泡、插入、选择 O(n²)；归并排序和堆排序 O(n log n)；快速排序平均 O(n log n)、最坏 O(n²)。

8. Compression Ratios | 压缩比

Compression reduces file size. The compression ratio measures the effectiveness of a compression algorithm.

压缩缩小文件大小。压缩比衡量压缩算法的有效性。

Compression ratio = Uncompressed size / Compressed size

For example, if a 10 MB image is compressed to 2 MB, the ratio is 5:1, often written as 5.

例如，若10 MB图像压缩到2 MB，压缩比为5:1，也常写作5。

Space saving percentage = (1 − Compressed size / Uncompressed size) × 100%. In the above example, space saving = 80%.

空间节省百分比 = (1 − 压缩后大小 / 原始大小) × 100%。上例中空间节省为80%。

Lossless compression (e.g., run-length encoding, Huffman coding) achieves modest ratios; lossy compression (JPEG, MP3) can achieve much higher ratios by discarding perceptually irrelevant data.

无损压缩（如游程编码、霍夫曼编码）达到的压缩比较为有限；有损压缩（JPEG、MP3）通过丢弃感知上不重要的数据可获得高得多的压缩比。

In run-length encoding, the compressed size depends on the number and length of runs. For a simple bitmap with long runs of identical pixels, the ratio can be very high.

游程编码中，压缩后大小取决于游程的数量与长度。对于相同像素长游程的简单位图，压缩比可以非常高。

9. Error Detection: Parity & Hamming Distance | 错误检测：奇偶校验与汉明距离

Error detection codes add redundancy to detect or correct transmission errors. Parity and Hamming distance are fundamental concepts.

错误检测码通过增加冗余来检测或纠正传输错误。奇偶校验和汉明距离是基础概念。

Single parity bit: appended to make the number of 1s either even (even parity) or odd (odd parity). It can detect a single-bit error but cannot correct it.

单奇偶校验位：添加一位使1的个数为偶数（偶校验）或奇数（奇校验）。可检测单比特错误但不能纠正。

Hamming distance between two code words is the number of bit positions in which they differ. A code with minimum Hamming distance d can detect up to d−1 errors and correct up to ⌊(d−1)/2⌋ errors.

汉明距离：两个码字间不同比特位的数量。最小汉明距离为d的编码可检测最多d−1个错误，纠正最多⌊(d−1)/2⌋个错误。

For example, the simple repetition code {000, 111} has d=3; it can detect 2 errors and correct 1 error.

例如，简单重复码{000, 111}的d=3，可检测2个错误并纠正1个错误。

Hamming codes are a class of error-correcting codes that use parity bits at positions that are powers of 2. The number of parity bits k needed to protect m data bits satisfies: 2ᵏ ≥ m + k + 1.

汉明码是一类纠错码，在2的幂次位置放置校验位。保护m个数据位所需的校验位数k满足：2ᵏ ≥ m + k + 1。

10. Database Normalisation: Functional Dependencies & Armstrong’s Axioms | 数据库规范化：函数依赖与阿姆斯特朗公理

Normalisation relies on functional dependencies and a set of inference rules called Armstrong’s axioms, which are rigorously applied in relational database design.

规范化基于函数依赖和一组称为阿姆斯特朗公理的推理规则，在关系数据库设计中严格应用。

A functional dependency X → Y means that the value of attribute set X uniquely determines the value of Y.

函数依赖X → Y 表示属性集X的值唯一确定Y的值。

Armstrong’s axioms:

阿姆斯特朗公理：

Reflexivity: If Y ⊆ X, then X → Y.

自反律：若Y ⊆ X，则 X → Y。
Augmentation: If X → Y, then XZ → YZ for any Z.

增广律：若X → Y，则对任意Z有 XZ → YZ。
Transitivity: If X → Y and Y → Z, then X → Z.

传递律：若X → Y 且 Y → Z，则 X → Z。

Additional derived rules: union (if X → Y and X → Z then X → YZ), decomposition (if X → YZ then X → Y and X → Z), and pseudotransitivity.

其他导出规则：合并律（若X → Y 且 X → Z 则 X → YZ）、分解律（若X → YZ 则 X → Y 和 X → Z）以及伪传递律。

Normal forms are defined by conditions on functional dependencies: 1NF requires atomic values; 2NF removes partial dependencies on the primary key; 3NF removes transitive dependencies; BCNF handles additional anomalies.

范式由函数依赖上的条件定义：1NF要求原子值；2NF消除对主键的部分依赖；3NF消除传递依赖；BCNF处理更多异常。

11. Software Complexity: Cyclomatic Complexity | 软件复杂性：循环复杂度

Cyclomatic complexity measures the number of linearly independent paths through a program’s source code. It is widely used in software testing and design.

循环复杂度衡量程序源代码中线性独立路径的数量，广泛应用于软件测试与设计。

M = E − N + 2P

Where E = number of edges in the control flow graph, N = number of nodes, P = number of connected components (usually 1 for a single program). For a single module, M = E − N + 2.

其中E为控制流图的边数，N为节点数，P为连通分量数（单个程序通常为1）。对于单一模块，M = E − N + 2。

Alternatively, for structured programs, M = number of decision points (if, while, for, case) + 1.

另外，对结构化程序，M = 判断点数（if、while、for、case）+ 1。

A module with M = 1 has no branching; M = 5 suggests complex logic that may require thorough testing. Values above 10 typically signal over-complex code that should be refactored.

M=1的模块无分支；M=5表明逻辑复杂，需要进行充分测试。值超过10通常意味着代码过于复杂，应进行重构。

Basis path testing uses cyclomatic complexity to determine the minimum number of test cases needed to execute every statement at least once.

基本路径测试利用循环复杂度确定至少执行每条语句一次所需的最小测试用例数。

12. Relations & Set Theory Theorems (Discrete Maths) | 关系与集合论定理（离散数学）

Formal methods and data modelling in computing draw on discrete mathematics, particularly sets and relations. Key theorems appear in database theory and algorithm design.

计算中的形式化方法与数据建模借鉴了离散数学，特别是集合与关系。关键定理出现在数据库理论和算法设计中。

Cartesian product: A × B = {(a, b) | a ∈ A, b ∈ B}. Its cardinality is |A| × |B|.

笛卡尔积：A × B = {(a, b) | a ∈ A, b ∈ B}，其基数为 |A| × |B|。

Properties of relations: A binary relation R on a set A can be reflexive, symmetric, antisymmetric, transitive. Equivalence relations (reflexive, symmetric, transitive) partition the set into disjoint equivalence classes.

关系性质：集合A上的二元关系R可以是自反、对称、反对称、传递的。等价关系（自反、对称、传递）将集合划分为不相交的等价类。

Partial order: reflexive, antisymmetric and transitive. Used in scheduling and dependency analysis.

偏序：自反、反对称且传递，用于调度和依赖分析。

Closures: The reflexive closure adds all (a,a); the symmetric closure adds (b,a) if (a,b) is present; the transitive closure is computed via Warshall’s algorithm.

闭包：自反闭包添加所有(a,a)；对称闭包为每个(a,b)添加(b,a)；传递闭包通过Warshall算法计算。

Set identities mirror Boolean algebra as shown in section 1, confirming the structural similarity between sets and logic.

集合恒等式与第1节中的布尔代数恒等式对应，印证了集合与逻辑之间的结构相似性。

Published by TutorHao | Computing Revision Series | aleveler.com

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

Formula & Theorems Quick Reference Guide for SQA Computing | SQA 计算机公式定理速查手册