GAC024 离散数学

重复集合成员只计一次，二进制进位可能超出固定宽度，且最少边数的路径不一定具有最小权重。离散数学明确了这些规则。

GAC024 涵盖集合、计数系统、二进制逻辑、算法和网络。你所在中心的当前大纲决定了评估任务、工具、权重和截止日期。这些原始练习纸不确立官方评分规则或大学学分决定。

求解前声明论域、表示宽度、允许输入或图假设。展示足够的演算过程以便另一读者重现结果，并区分数学模型与其实际实现。

• 集合 是一个由不同对象组成的集合。顺序和重复无关紧要。
• 并集 $A \cup B$ 是任意一个集合中的元素；交集 $A \cap B$ 是公共的元素 两者皆适用；补集（set complement）是指论域中属于全集但不属于该集合的所有元素。
• 关系 (Relation) 将两个集合的元素配对。函数 (Function) 是一种关系，其中每个
• 关系 将两个集合中的元素配对。函数 是一种关系，其中每个 在其声明的定义域内，每个输入恰好对应一个输出。不同的输入可能共享同一个输出；只有当输出能唯一标识其对应的输入时，逆关系才构成函数。
• Venn diagram 韦恩图将集合问题转化为图形，可显示不相交区域及其数量。请验证这些区域的总和是否等于给定的全集总数。

inclusion-exclusion principle 容斥原理减去被重复计算的交集一次：$|A\cup B|=|A|+|B|-|A\cap B|$。

Worked example. 仅对交集减去一次

已知：30名学生，18人学习法语，15人学习德语，7人两门都学。交集部分同时包含在两个学科的总数中。

仅学法语为$18-7=11$，仅学德语为$15-7=8$。四个不相交区域的总和为30。

练习表 4.1 包含难度递增的问题及独立核对的答案。

• 一个位置number base 进制 b 使用从零到 b-1 的数字以及位权 $b^i$。Decimal 十进制使用十，binary 二进制，十六进制
• 每一位的数值为其位值：在二进制中，数位依次为 1、2、4、8、16 等。
• Hexadecimal 十六进制是二进制的简写：一个十六进制数字恰好对应四位二进制位，因此转换可将指定宽度的二进制模式按四位一组进行分组。前导零保留宽度而不改变无符号值的大小。

对于 n 位无符号数，数值范围从零到 $2^n-1$。需区分不受限制的求和与存储的固定宽度结果；若明确给出了回绕规则，则保留低 n 位。

Worked example. 位权决定十进制值

已知数字 $1101_2$。从右向左使用位权：1、2、4 和 8。

相同的值在十六进制中为 D。前导零不会改变该非负值，但可用于记录预期的宽度。

练习表 4.2 包含难度递增的问题及独立核对的答案。

• 二进制运算 与十进制加法类似，在 2 处进位而非在 10 处。
• 布尔代数 (Boolean algebra) 在真和假之间使用 AND、OR 和 NOT 进行操作。
• 真值表 (Truth table) 列出每种输入组合及其输出，它是证明两个逻辑表达式等价
• A truth table 真值表列出所有布尔输入组合及对应的输出。逐行匹配可证明相同有限布尔输入的等价性；但这不能证明物理电路的时序或真实系统的安全性。
• Logic gates 逻辑门实现指定的运算，logic circuit 逻辑电路将它们连接起来。根据连接方式和输入约定追踪抽象逻辑。

使用包容性 OR 和显式括号。De Morgan 给出 $\neg(A\land B)=(\neg A)\lor(\neg B)$。按位 NOT 仅反转指定宽度，而非未指明的无限表示。

Worked example. OR 的输出经 NOT 反相

已知：$Y=\neg(A\lor B)$。包容性 OR 仅在两个输入均为假时为假；NOT 反转该结果。按行序 $(A,B)=(0,0),(0,1),(1,0),(1,1)$，输出列为 1, 0, 0, 0。De Morgan 给出等价表达式 $(\neg A)\land(\neg B)$。

练习表 4.3 包含难度递增的问题及独立核对的答案。

• An algorithm 算法描述任务的无歧义步骤。解决指定有限任务的程序必须终止，并针对其允许的输入给出所需结果。
• 伪代码 (Pseudocode) 用结构化英语编写，这也是考试通常要求的形式。
• Pseudocode 伪代码表示步骤而无需特定编程语言。追踪前需明确赋值语句、循环边界及索引约定。
• Tracing 追踪算法——以每变量一列、每步骤一行的表格——记录实际更新过程。追踪用于检验选定输入；若声称适用于所有允许输入，还需附加正确性论证。
• Efficiency 效率至关重要：线性搜索可提前终止，但也可能检查全部 n 个元素。二分搜索反复舍弃有序搜索范围的一半；其对数级比较次数依赖于已排序数据及边界约定。

Worked example. 重复取余步骤直至第二个数为零

已知：起始正整数 a=10，b=6。当 b 非零时，计算 r = a MOD b，然后令 a=b，b=r。完整迭代后的数对依次为 (6,4)、(4,2)、(2,0)，输出结果为 2。临时变量 r 在 a 和 b 更新前保存余数。每个非零余数均小于前一个正 b，从而保证终止。

练习表 4.4 包含难度递增的问题及独立核对的答案。

• 图（graph）是由顶点（vertices）通过边（edges）连接而成的集合。它可用于建模任何具有 连接：道路、友谊、依赖关系。
• 对于无自环且无重复边的简单无向图，degree 度统计关联边数。每条边使总度数之和增加 2。
• A tree 树是无环连通图；含 n 个顶点的有限树恰有 n−1 条边。部分层次模型采用树结构，但实际系统也可能包含交叉链接或环。
• shortest path 最短路径问题要求在给定约束下找出两顶点间总权重最小的路径，而非仅比较边数。最小生成树则在不形成环的前提下连接所有顶点，并使所含边总权重最小。

Worked example. 比较路径总权重，而非边数

已知边权：AB=2，BC=3，AC=8，CD=1。路径 A-C-D 权重为 9，而 A-B-C-D 权重为 6。因此尽管三边路径边数更多，但其总权重更短。该小网络的最小生成树选用 AB、BC、CD，总权重为 6；此处总权重相等并不意味着两个任务相同。

练习卷 4.5 包含难度递增的问题及独立核实的解答。