📚 Year 13 CAIE Computer Science: Formula & Theorem Quick Reference | A Level计算机科学公式定理速查手册
This quick reference handbook compiles the essential formulas, theorems, and key relationships required for the CAIE A Level Computer Science (9618) Year 13 syllabus. From Boolean algebra and Karnaugh maps to processor performance and network delay, each section is presented in concise paired statements – English followed by its Chinese translation – to support rapid revision and deep understanding.
本速查手册汇编了 CAIE A Level 计算机科学(9618) Year 13 课程所必需的基本公式、定理和关键关系。从布尔代数、卡诺图到处理器性能与网络延迟，每个小节均以简明的中英对照形式呈现，便于快速复习和深入理解。
1. Boolean Algebra Laws | 布尔代数基本定律
Boolean algebra operates on binary variables with values 0 and 1. The fundamental laws – commutative, associative, distributive, identity, complement, and idempotent – form the backbone of logic simplification.
布尔代数对取值为 0 和 1 的二进制变量进行运算。交换律、结合律、分配律、恒等律、互补律和幂等律等基本定律构成了逻辑化简的骨架。
Identity Law: A + 0 = A and A · 1 = A. A variable ORed with 0 or ANDed with 1 remains unchanged.
恒等律：A + 0 = A，A · 1 = A。任何变量与 0 相或或与 1 相与都保持不变。
Complement Law: A + A’ = 1 and A · A’ = 0. A variable ANDed with its complement yields 0; ORed yields 1.
互补律：A + A’ = 1，A · A’ = 0。变量与其反变量相与得 0，相或得 1。
Idempotent Law: A + A = A and A · A = A. Repeating a variable does not change the outcome.
幂等律：A + A = A，A · A = A。重复同一变量不会改变结果。
Domination Law: A + 1 = 1 and A · 0 = 0. Any variable ORed with 1 yields 1; ANDed with 0 yields 0.
支配律：A + 1 = 1，A · 0 = 0。任何变量与 1 相或结果为 1，与 0 相与结果为 0。
Double Negation: (A’)’ = A. Complementing twice returns the original variable.
双重否定律：(A’)’ = A。两次取反恢复原变量。
2. De Morgan’s Theorems | 德摩根定理
De Morgan’s theorems are powerful tools for transforming expressions between AND and OR forms, enabling efficient NAND/NOR implementations.
德摩根定理是在与形式和或形式之间转换表达式的强大工具，可以实现高效的与非/或非门实现。
First theorem: (A · B)’ = A’ + B’ – The complement of a conjunction equals the disjunction of complements.
第一定理：(A · B)’ = A’ + B’ —— 与运算的补等于各补的或运算。
Second theorem: (A + B)’ = A’ · B’ – The complement of a disjunction equals the conjunction of complements.
第二定理：(A + B)’ = A’ · B’ —— 或运算的补等于各补的与运算。
These theorems generalise to any number of variables: (A₁ · A₂ · … · Aₙ)’ = A₁’ + A₂’ + … + Aₙ’.
这两个定理可以推广到任意数量变量：(A₁ · A₂ · … · Aₙ)’ = A₁’ + A₂’ + … + Aₙ’。
Equivalently, (A₁ + A₂ + … + Aₙ)’ = A₁’ · A₂’ · … · Aₙ’. Use these to convert bubbled gates and eliminate long complement bars.
同理，(A₁ + A₂ + … + Aₙ)’ = A₁’ · A₂’ · … · Aₙ’。利用这些定理可以转换带圈的逻辑门并消除长反号。
3. Karnaugh Maps & Simplification | 卡诺图与化简
Karnaugh maps (K-maps) provide a visual method for simplifying Boolean expressions by grouping adjacent 1s. The number of cells is 2ⁿ for n variables.
卡诺图通过组合相邻的 1 提供了一种可视化化简布尔表达式的方法。对于 n 个变量，格数为 2ⁿ。
A two-variable K-map has 4 cells; three-variable 8 cells; four-variable 16 cells. Each cell corresponds to a minterm from the truth table.
二变量卡诺图有 4 格；三变量 8 格；四变量 16 格。每格对应真值表的一个最小项。
Simplification rules: group 1s in rectangles of size 1, 2, 4, 8, etc. Groups must be powers of 2 and as large as possible; they may wrap around edges.
化简规则：将 1 组合成大小为 1、2、4、8 等的矩形。组合必须是 2 的幂且尽可能大；可以跨越边界环绕。
Each group yields a product term where a variable is eliminated if it changes within the group (appears in both true and complemented forms). The minimal SOP expression is the sum of all prime implicants.
每组产生一个乘积项，如果某个变量在组内发生变化（同时以原变量和反变量出现），则该项中被消除。最简的积之和表达式是所有基本质蕴含项的和。
4. Logic Gates & Truth Tables | 逻辑门与真值表
Basic gates form the building blocks of digital circuits. Their truth tables define the output for every input combination.
基本逻辑门构成了数字电路的积木。它们的真值表定义了每种输入组合下的输出。
| Gate | Symbol (Boolean) | Truth Table |
|---|---|---|
| AND | X = A · B | 0·0=0, 0·1=0, 1·0=0, 1·1=1 |
| OR | X = A + B | 0+0=0, 0+1=1, 1+0=1, 1+1=1 |
| NOT | X = A’ | 0’=1, 1’=0 |
| NAND | X = (A · B)’ | (0·0)’=1, (0·1)’=1, (1·0)’=1, (1·1)’=0 |
| NOR | X = (A + B)’ | (0+0)’=1, (0+1)’=0, (1+0)’=0, (1+1)’=0 |
| XOR | X = A ⊕ B = A’B + AB’ | 0⊕0=0, 0⊕1=1, 1⊕0=1, 1⊕1=0 |
| XNOR | X = (A ⊕ B)’ = AB + A’B’ | (0⊕0)’=1, (0⊕1)’=0, (1⊕0)’=0, (1⊕1)’=1 |
NAND and NOR gates are functionally complete, meaning any Boolean function can be implemented using only NAND gates or only NOR gates.
与非门和或非门具备功能完备性，即任何布尔函数都可以仅用与非门或仅用或非门来实现。
5. Data Representation Formulas | 数据表示公式
Numbers in computing are stored in binary, hexadecimal, or floating-point formats. Understanding conversion and range formulas is essential.
计算机中的数字以二进制、十六进制或浮点格式存储。理解转换和范围公式至关重要。
For unsigned n-bit integers, range = 0 to (2ⁿ – 1). Example: 8-bit gives 0 to 255.
对于 n 位无符号整数，范围 = 0 到 (2ⁿ – 1)。例如 8 位范围为 0 到 255。
For two’s complement n-bit signed integers, range = –2ⁿ⁻¹ to (2ⁿ⁻¹ – 1). Example: 8-bit gives –128 to +127.
对于 n 位二进制补码有符号整数，范围 = –2ⁿ⁻¹ 到 (2ⁿ⁻¹ – 1)。例如 8 位范围为 –128 到 +127。
To negate a two’s complement number: invert all bits and add 1. Proof: –X = (X’ + 1) mod 2ⁿ.
对二进制补码取相反数：将所有位取反后加 1。证明：–X = (X’ + 1) mod 2ⁿ。
IEEE 754 single-precision 32-bit floating point: value = (–1)ˢ × 1.M × 2ᴱ⁻¹²⁷, where s = sign, M = mantissa (23 bits), E = biased exponent (8 bits). Special values: exponent = 0, mantissa = 0 → ±0; exponent = 255, mantissa = 0 → ±∞; exponent = 255, mantissa ≠ 0 → NaN.
IEEE 754 单精度 32 位浮点数：值 = (–1)ˢ × 1.M × 2ᴱ⁻¹²⁷，其中 s 为符号位，M 为尾数(23 位)，E 为移码指数(8 位)。特殊值：指数=0且尾数=0 → ±0；指数=255且尾数=0 → ±∞；指数=255且尾数≠0 → NaN。
6. File Size Calculations | 文件大小计算
Estimating file sizes for images, audio, and text helps in storage planning and transmission analysis.
估算图像、音频和文本文件的大小有助于存储规划和传输分析。
Uncompressed image size (bytes) = width × height × colour depth (bits) ÷ 8. Colour depth is the number of bits per pixel (e.g. 24-bit true colour).
未压缩图像大小(字节) = 宽度 × 高度 × 色彩深度(位) ÷ 8。色彩深度是每像素位数（如 24 位真彩色）。
Uncompressed audio file size (bytes) = sampling rate (Hz) × sample resolution (bits) × number of channels × duration (seconds) ÷ 8.
未压缩音频文件大小(字节) = 采样率(Hz) × 采样分辨率(位) × 声道数 × 时长(秒) ÷ 8。
Text file size (bytes) ≈ number of characters × bits per character ÷ 8. For ASCII, 1 byte per character; for Unicode UTF-8, 1–4 bytes per character.
文本文件大小(字节) ≈ 字符数 × 每字符位数 ÷ 8。ASCII 每字符 1 字节；Unicode UTF-8 每字符 1 至 4 字节。
Compression ratio = uncompressed size / compressed size. A ratio of 5:1 means the compressed file is one-fifth the original size.
压缩比 = 未压缩大小 / 压缩后大小。5:1 的压缩比意味着压缩文件是原始大小的五分之一。
7. Communication Fundamentals | 通信基础
Key formulas for data transmission over channels link baud rate, bit rate, and bandwidth, governed by Nyquist and Shannon theorems.
信道数据传输的关键公式将波特率、比特率和带宽联系起来，由奈奎斯特定理和香农定理支配。
Bit rate (bps) = baud rate × bits per signal element. Baud rate is the number of signal changes per second.
比特率(bps) = 波特率 × 每信号单元的比特数。波特率是每秒信号变化的次数。
Nyquist theorem for a noiseless channel: maximum bit rate = 2 × Bandwidth × log₂ L, where L is the number of signal levels.
奈奎斯特定理（无噪声信道）：最大比特率 = 2 × 带宽 × log₂ L，其中 L 为信号电平数。
Shannon-Hartley theorem for noisy channel: channel capacity C = B × log₂ (1 + S/N), where B = bandwidth (Hz), S/N = signal-to-noise ratio (linear, not dB). If SNR given in dB: S/N = 10^(SNR_dB/10).
香农-哈特利定理（有噪声信道）：信道容量 C = B × log₂ (1 + S/N)，其中 B 为带宽(Hz)，S/N 为信噪比（线性值，非分贝值）。若 SNR 以 dB 给出：S/N = 10^(SNR_dB/10)。
2ʸ = x equivalently y = log₂ x. Always convert bandwidth to Hz and time to seconds for consistent units.
2ʸ = x 等价于 y = log₂ x。计算时始终将带宽转换为 Hz、时间转换为秒以保持单位一致。
8. Processor Performance Metrics | 处理器性能指标
Processor execution time is determined by the clock frequency, cycles per instruction (CPI), and instruction count.
处理器执行时间由时钟频率、每指令周期数(CPI)和指令数决定。
Clock period T = 1 / f, where f is clock frequency in Hz. If f = 2 GHz, T = 0.5 ns.
时钟周期 T = 1 / f，其中 f 为时钟频率(Hz)。若 f = 2 GHz，则 T = 0.5 ns。
Execution time per program = Instruction count × CPI × T. Alternatively, = (Instruction count × CPI) / f.
程序执行时间 = 指令数 × CPI × T。或写作 = (指令数 × CPI) / f。
Average CPI = Σ (instruction frequency_i × CPI_i) for all instruction classes. This accounts for different instructions requiring different cycles.
平均 CPI = Σ (指令频度_i × CPI_i)，对所有指令类别求和。这考虑了不同指令需要不同周期数的情况。
MIPS rate = (Instruction count) / (Execution time × 10⁶). MFLOPS similarly measures floating-point operations per second.
MIPS 速率 = 指令数 / (执行时间 × 10⁶)。MFLOPS 同理衡量每秒百万次浮点运算。
9. Network Delay and Transmission Time | 网络延迟与传输时间
Total latency in a packet-switched network comprises transmission, propagation, queuing, and processing delays.
分组交换网络的总延迟由传输延迟、传播延迟、排队延迟和处理延迟组成。
Transmission time t_trans = L / R, where L = packet length (bits), R = link bandwidth (bps). This is the time to push all bits onto the wire.
传输时间 t_trans = L / R，其中 L 为分组长度(位)，R 为链路带宽(bps)。这是将所有比特推送到线路上的时间。
Propagation delay t_prop = d / s, where d = distance (metres), s = propagation speed (m/s). In copper or fibre, s ≈ 2 × 10⁸ m/s.
传播延迟 t_prop = d / s，其中 d 为距离(米)，s 为传播速度(米/秒)。在铜线或光纤中，s ≈ 2 × 10⁸ m/s。
Total delay per hop ≈ t_trans + t_prop + t_queue + t_proc. For multiple hops, sum all per-hop delays.
每跳总延迟 ≈ t_trans + t_prop + t_queue + t_proc。对于多跳路径，汇总所有跳的延迟。
Round-trip time (RTT) = 2 × (sum of per-hop t_trans and t_prop) in the absence of queuing. Essential for TCP timeout estimation.
往返时间(RTT) = 2 × (各跳 t_trans 与 t_prop 之和)，假设无排队。这对于 TCP 超时估计至关重要。
10. Relational Databases: Armstrong’s Axioms | 关系数据库：阿姆斯特朗公理
Armstrong’s axioms are inference rules for functional dependencies (FDs), fundamental to database normalisation.
阿姆斯特朗公理是函数依赖的推理规则，是数据库规范化的基础。
Reflexivity: If Y ⊆ X, then X → Y. Trivial dependencies are always satisfied.
自反律：若 Y ⊆ X，则 X → Y。平凡函数依赖始终成立。
Augmentation: If X → Y, then XZ → YZ for any attribute set Z. Adding the same attributes to both sides preserves the dependency.
增广律：若 X → Y，则 XZ → YZ，对于任意属性集 Z。将相同的属性添加到两侧，依赖关系保持不变。
Transitivity: If X → Y and Y → Z, then X → Z. This allows chaining of dependencies.
传递律：若 X → Y 且 Y → Z，则 X → Z。这允许依赖链的传递。
From these axioms, derive union (if X → Y and X → Z then X → YZ), decomposition (if X → YZ then X → Y and X → Z), and pseudotransitivity. These rules underpin closure of attribute sets and canonical cover.
由这些公理可推导出合并律（若 X → Y 且 X → Z，则 X → YZ）、分解律（若 X → YZ，则 X → Y 且 X → Z）以及伪传递律。这些规则支撑了属性集闭包和规范覆盖。
11. Algorithm Complexity: Big O Notation | 算法复杂度：大O表示法
Big O notation describes the upper bound of an algorithm’s time or space complexity as input size n grows.
大 O 表示法描述了随着输入规模 n 的增长，算法时间或空间复杂度的上界。
Formal definition: f(n) = O(g(n)) if there exist constants c > 0 and n₀ ≥ 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀. It captures the worst-case growth rate.
正式定义：若存在常数 c > 0 和 n₀ ≥ 0，使得对所有 n ≥ n₀ 有 0 ≤ f(n) ≤ c·g(n)，则 f(n) = O(g(n))。它刻画了最坏情况增长率。
Common complexities: O(1) constant, O(log n) logarithmic (binary search), O(n) linear (linear search), O(n log n) linearithmic (merge sort), O(n²) quadratic (bubble sort, insertion sort), O(2ⁿ) exponential (brute-force).
常见复杂度：O(1) 常数，O(log n) 对数（二分查找），O(n) 线性（线性查找），O(n log n) 线性对数（归并排序），O(n²) 平方（冒泡排序、插入排序），O(2ⁿ) 指数（暴力搜索）。
Binary search recurrence: T(n) = T(n/2) + O(1) → O(log n). Merge sort recurrence: T(n) = 2T(n/2) + O(n) → O(n log n). Master theorem can solve such recurrences.
二分查找递推式：T(n) = T(n/2) + O(1) → O(log n)。归并排序递推式：T(n) = 2T(n/2) + O(n) → O(n log n)。主定理可求解此类递推。
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