CSCI3130 L01 Part 1/2 Mathematical Preliminaries and Notation

课程：CSCI3130 Formal Languages and Automata Theory · 2026T1 本讲：L01 Part 1/2 Mathematical Preliminaries and Notation · 原件 L01-数学基础-2026T1.pdf（本地课件） p.1–54 定位：把集合、关系、图与证明变成后续自动机推理可直接使用的工具；读完能逐步检查定义、运行图上的遍历，并写完整归纳证明。 前后：上一份 L00-P4-计算理论导论.md · 下一份 L01-P2-语言与文法.md

整讲导航

• Part 1 数学预备：p.1–54。
• Part 2 语言与文法：p.55–90。
• Outline 中 Some Applications 标为 omit，原件未展开，不另造 Part 3。

p.1 标题页；p.2 为 Outline；p.3 列本部分五组预备知识。

Mathematical Preliminaries and Notation

元素、集合与全集（p.4–6）【新】

p.4 A set is a collection of elements

p.4 用 $A=\{1,2,3\}$ 说明集合，$1\in A$ 表示1是元素，$4\notin A$ 表示4不是。一个集合关注成员，不关注写下来的顺序；成员与子集是两个层次，1是一个数，$\{1\}$ 是只含一个数的集合。

p.5 展示列举法与条件描述法。$\{a,b,\ldots,k\}$ 是有限集合；$\{2,4,6,\ldots\}$ 用省略号表示正偶数无限延续。原页辨析：已看渲染图，本页同时写“j > 0”与“j is nonnegative and even”，两者对0的处理不同；前者不含0，后者含0。引用条件时要按具体一行判断，不能认为这些表达在0处完全相同。

p.6 用 $U=\{1,\ldots,10\}$ 指定全集（universal set），而 $A=\{1,\ldots,5\}$ 在它内部。全集决定“其他所有元素”的范围；下一页补集必须依赖这个范围。

p.4 还有非数字集合 $B=\{train,bus,bicycle,airplane\}$，以及 $ship\notin B$。元素不必是数字，集合也可以收集交通工具名称。p.5 完整的有限列举是 $C=\{a,b,c,d,e,f,g,h,i,j,k\}$；省略号只是这一模式的简写，不能在没说明规律时任意猜中间成员。

p.6 的图在全集矩形内将 1、2、3、4、5 圈入 A，把 6、7、8、9、10 留在圈外。检验一个元素时有两层问题：“是否在这次讨论的全集内”“是否进一步属于 A”。后面的补集只从第一层范围里选剩下的元素。

并、交、差与补（p.7–9）【新】

p.7 的 $A=\{1,2,3\}$、$B=\{2,3,4,5\}$ 给四个可核的结果：并集 $A\cup B=\{1,2,3,4,5\}$；交集 $A\cap B=\{2,3\}$；差集 $A-B=\{1\}$；反向差集 $B-A=\{4,5\}$。每一个元素分别检查“至少属于一边”“同时属于两边”“在左边而不在右边”，就能自行重算。

p.8 改用 $U=\{1,\ldots,7\}$。$\overline A=U-A=\{4,5,6,7\}$；再取一次补集回到 $A$，因为原先排除的成员被选回来。p.9 将全集设为整数，所以偶数的补集是奇数，包含负奇数。若全集换成实数，补集会包含非整数，原结论便不能照搬。

算一遍：检查数字4：它不在A但在B，所以在并集中、在 $B-A$ 中，却不在交集和 $A-B$ 中。这种逐元素检查也正是集合等式证明的起点。

DeMorgan 与空集（p.10–11）【新】

p.10 的两条公式按渲染图重排为：

第一条说“不属于至少一个成立的并集”等价于“两边都不属于”；第二条说“并非同时属于两边”等价于“至少有一边不属于”。对任意元素逐项翻译，才是证明；只画一个特定维恩图作为例子不足以说明所有集合。

补充 · 算一遍（数字是我为演示取的，讲义没给）：设 $U=\{1,2,3,4\}$、$A=\{1,2\}$、$B=\{2,3\}$。$\overline{A\cup B}=\{4\}$，而 $\overline A\cap\overline B=\{3,4\}\cap\{1,4\}=\{4\}$；$\overline{A\cap B}=\{1,3,4\}$，而 $\overline A\cup\overline B=\{3,4\}\cup\{1,4\}=\{1,3,4\}$。

p.11 定义空集 $\varnothing$：没有成员。因此 $S\cup\varnothing=S$，$S\cap\varnothing=\varnothing$，$S-\varnothing=S$，$\varnothing-S=\varnothing$；$\overline\varnothing=U$。后续特别要防止把空集与只含空字符串的集合混淆。

考试角度：（A 级：HW01-2026T1-题目.pdf Q1，考本节第二条 DeMorgan 等式的证明；HW01-2025T1-题目.pdf Q1，考第一条）旧题演练见附录 A1；本次补齐的两版题目与模4等价类演练见附录 A2，均为学习说明。

由 p.10 展开的逐元素证明：固定全集中的任意元素 x。若 x 不在并集，说明它不在 A 且不在 B，因此在两个补集的交中；反过来，若它在两个补集的交中，就既不在 A 也不在 B，于是不在并集中。两个方向给出第一条等式。第二条中，若 x 不在交集，只能是“不在 A 或不在 B”，于是属于两个补集的并；反过来也成立。这里的“或”允许两边同时成立。证明对任意 x 生效，所以不是只验证图上列出的几个数。

子集、不相交和基数（p.12–14）【新】

p.12 Subset: If every element of A is also an element of B

p.12 的 $A=\{1,2,3\}$、$B=\{1,2,3,4,5\}$ 满足 $A\subseteq B$；B还有4和5，故也是真子集。子集允许相等，真子集不允许。空集是任意集合的子集，因为找不到违反“空集每个元素都在该集合中”的元素。

p.13 取 $A=\{1,2,3\}$、$B=\{5,6\}$，没有共同成员，所以交集为空，称不相交（disjoint）。不相交不等于“不是同一个集合”：两个不同集合完全可以重叠。

p.14 的 $A=\{2,5,7\}$ 有三个不同成员，基数 $\lvert A\rvert=3$。这里的竖线表示集合大小；遇到字符串时同样的记号会表示串长，须先看对象类型。

幂集、笛卡尔积与划分（p.15–17）【新】

p.15 A powerset is a set of sets

p.15 取 $S=\{a,b,c\}$，幂集含 $\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}$ 八个元素。为什么是 $2^3=8$：每个原元素各有“选入/不选入”两种选择，三个独立选择相乘。幂集的一个元素是子集，不能把a和 $\{a\}$ 混为一项。

p.16 的 $A=\{2,4\}$、$B=\{2,3,5,6\}$ 生成有序对集合。逐行列出 $(2,2),(2,3),(2,5),(2,6)$，再列 $(4,2),(4,3),(4,5),(4,6)$，共 $2\cdot4=8$ 项。$(4,2)$ 合法而 $(2,4)$ 不合法，因为第二坐标4不在B中。幂集计数和笛卡尔积计数原理不同，别见到两个集合就用 $2^n$。

p.17 定义**划分（partition）**的三个条件：各块非空、任意两块不相交、合起来覆盖原集合。补充 · 算一遍（数字是我为演示取的，讲义没给）：$\{1,2\}$ 与 $\{3\}$ 划分 $\{1,2,3\}$；若将第二块改成 $\{2,3\}$，2重叠，违反不相交；若改成空集，既有空块又漏掉3。

函数及定义域（p.18）【新】

p.18 Rules that assign to elements of one set a unique element of another set

图（p.18）：从A到B的对应。 元素：箭头为1→a、2→b、3→c；左侧矩形还画出4和5，但它们没有箭头，内圈包含1、2、3。 看什么：对实际定义的输入，输出唯一；若声明输入范围也包括4、5，这个对应是偏函数。若实际定义域等于声明的A，则为全函数。

补充：很多现代教材把B称为陪域（codomain），把实际取得的输出集合称为值域（range）；讲义图上的 range 标签更宽泛。后面 DFA 转移要求每个状态与输入符号组合都有定义，而某些图灵机采用偏转移函数，正好会用到这个差别。

渐近上界和下界（p.19–20）【新】

这两页的定义与练习为图片，已视觉核读。$f(n)=O(g(n))$ 表示存在固定 $c>0,n_0$，使所有 $n\ge n_0$ 都有 $0\le f(n)\le cg(n)$。$\Omega$ 则反向：$0\le cg(n)\le f(n)$。c是允许的常数倍，$n_0$ 允许忽略一段有限的小输入；它们都不能随着n任意变化。

题面（L01-数学基础-2026T1.pdf · 图片内练习 · p.19–20，视觉读取；公式按原题重排）

p.19 $3n^{2}+n=O(n^{2})$? $3n^{2}+n=O(n)$? $3n^{2}+n=O(n^{3})$?

p.20 $3n^{2}+n=\Omega(n^{2})$? $3n^{2}+n=\Omega(n)$? $3n^{2}+n=\Omega(n^{3})$?

对 $n\ge1$，$3n^{2}\le3n^{2}+n\le4n^{2}$。所以两个平方界都成立。它也不超过 $4n^3$，故是 $O(n^3)$；且至少为n，故是 $\Omega(n)$。但除以n得到 $3n+1$ 无界，故不是 $O(n)$；除以 $n^3$ 得 $3/n+1/n^2$ 趋于0，故不是 $\Omega(n^3)$。用n=10检查：原式310、$n^2=100$、$n^3=1000$；这个数值帮助直觉，真正证明仍是对全部足够大的n成立的不等式。

把渐近界的量词按先后读出（补充）：$\exists c>0\ \exists n_0\ \forall n\ge n_0$ 的意思是先一次性选好 c 与起点，再让任意更大的 n 来挑战。不能看到 n=100 就用 c=301，看到 n=1000 又换成 c=3001，然后说 $3n^2+n=O(n)$。若已固定 c，选择同时大于 $n_0$ 和 c 的整数 n，就有 $3n+1>c$，所以 $3n^2+n>cn$；该 n 正好打破声称的上界。否定一个“存在固定常数”的主张时，必须能击败对方任意给出的固定常数，而不是只举某个小 c 失败。

图（p.19–20）：函数增长与常数倍界。 元素：横轴 n，纵向为函数值，虚线竖标记起点 $n_0$；p.19 在该点之后让 $cg(n)$ 位于 $f(n)$ 上方，p.20 则让 $cg(n)$ 位于 $f(n)$ 下方。 看什么：起点以前曲线交叉不影响渐近结论；起点以后要求每个输入都守住相应界，而不只是“大部分点”。

p.19 还提及比值 $f(n)/g(n)$，p.20 对下界使用反向比值 $g(n)/f(n)$，均带 “if the limit exists”。补充：如何安全使用这个判断：在分母最终为正的条件下，前者收敛到有限非负数可给出 O 上界，后者收敛到有限非负数可给出 Ω 下界。有限极限为 0 也可以；例如平方与立方相比趋于0，平方仍是立方的 O。极限不存在不自动否定渐近界，此时回到常数不等式定义判断。

紧确界（p.21）

题面（L01-数学基础-2026T1.pdf · Example 1.3 · p.21）

p.21 $f(n)=2n^{2}+3n$, $g(n)=n^{3}$, $h(n)=10n^{2}+100$.

公式按讲义重排。$\Theta$ 要求同时有上下界，而O只需上界。对 $n\ge1$，$f\le5n^2\le5g$，得到 $f=O(g)$；$h\le110n^2\le110g$，得到 $g\ge h/110$，即 $g=\Omega(h)$。又有 $f\ge2n^2\ge h/55$，以及 $f\le5n^2\le h/2$，故 $f=\Theta(h)$。这些常数不是最优，但定义只要求存在。

算一遍：n=10 时 $f=230,g=1000,h=1100$。虽然这个点上g小于h，仍不妨碍 $g=\Omega(h)$；渐近下界允许常数倍，不要求从第一个输入开始就 $g\ge h$。

p.21 上半页还包含三道紧确界判断，不能只做下方 Example 1.3：

题面（L01-数学基础-2026T1.pdf · 图片内练习 · p.21，视觉读取；公式按原题重排）

p.21 $3n^2+n=\Theta(n^2)$? $3n^2+n=\Theta(n)$? $3n^2+n=\Theta(n^3)$?

第一题成立，取 $c_1=3,c_2=4,n_0=1$ 即有 $3n^2\le3n^2+n\le4n^2$。第二题不成立，因为上界 O(n) 不成立；第三题不成立，因为下界 Ω(n³) 不成立。要证 Θ 必须两边都满足，否定它只需打破其中一边。

图（p.21）：紧确界用两条常数倍曲线夹住目标曲线。 元素：横轴 n；虚线标 $n_0$；上方红色 $c_2g(n)$，中间黑色 $f(n)$，下方蓝色 $c_1g(n)$。 看什么：Θ 并非函数逐点相等，而是最终增长量级同时受上下两条常数倍界约束。页面提及的比值极限若存在，须为严格正的有限常数才能用这种极限法得到 Θ；为0只足以支持一侧。

关系与等价（p.22–24）【新】

p.22 Relations are more general than functions

p.22 把关系写成有序对集合，$xRy$ 表示 $(x,y)$ 在R内。同一个x可对应多个y；例如“>”允许3与2、1都有关系，这就不满足函数输出唯一的限制。

p.23 的**等价关系（equivalence relation）**需要自反、对称、传递三个条件：每个x与自己相关；x与y相关则y与x相关；x与y、y与z相关则x与z相关。它们分别控制自己、反向与串接，不能互相替代。

p.24 用非负整数模3同余。$2\bmod3=5\bmod3=2$，所以2与5相关；12、0、36余数同为0。自反性来自同一个余数等于自己，对称性来自等号可反向，传递性来自两个余数等式可串接。等价类为余0、余1、余2的三组，恰好满足p.17划分条件。

考试角度：（A 级：HW01-2026T1-题目.pdf Q2，考本节模数关系所诱导的等价类划分）处理有限集合时只能收录题面给的元素，不能把整套无限同余类当作答案。

图、有向边与标签（p.25–27）【新】

p.27 Walk is a sequence of adjacent edges

图（p.25–27）：五顶点有向图及标号、行走版本。 元素：顶点a、b、c、d、e；有向边a→b、b→c、b→e、c→a、c→e、d→c、e→b、e→d；p.26 给边附数字标签，p.27 选出e→d→c→a。 看什么：箭头决定能往哪走，标签提供额外信息；相反方向的b→e和e→b是两条边。

p.25 先定义顶点集合V与边集合E；p.26 的数字可以表达长度、成本或动作，本页没有定义它们的唯一物理意义。p.27 的walk要求相邻边首尾相接：$(e,d)$ 后接 $(d,c)$，再接 $(c,a)$，得到长度为3条边的行走；不能接一条起点不是当前终点的边。

表（p.26，视觉核对）：原图每条有向边及标签。

b→c 确实有箭头，但这张图没有给它数字；不能为了表格齐全补0或1。p.27 的 e→d→c→a 沿箭头可走；反方向 a→c 不是本图允许的边。

路径、环与自环（p.28–30）【新】

p.28 Path: a walk where no edge is repeated

p.28 Simple path: no node is repeated

p.28 本课把不重复边的walk叫path，不重复顶点叫simple path。补充：其他教材有时将前者叫trail；答题时先按本讲术语读约束。p.29 的cycle起终点相同，simple cycle只让起点在结尾重复。

p.30 图的边为 $v_1\to v_3$、$v_3\to v_1$、$v_3\to v_2$、$v_3\to v_3$。最后一条是loop，一条边就回到自身。序列 $v_1\to v_3\to v_2$ 是简单路径；$v_1\to v_3\to v_3\to v_1$ 是非简单cycle，因为 $v_3$ 重复出现。不要把“回到起点”与“每个中间顶点只走一次”混成一个条件。

一次走完边与一次走完点（p.31–32）【新】

p.31 A cycle that contains each edge once

p.32 A simple cycle that contains all nodes

p.31 的 Euler tour 检查边：图示顺序 e→d→c→a→b→c→e→b→e，共8条，恰好各用一次。b、c、e被多次访问不违背Euler要求。p.32 的 Hamiltonian cycle 检查顶点：e→d→c→a→b→e，共5条边，五个顶点各访问一次后回e；它故意不用图中所有边。这是旅行商要求与“清扫每条街一次”的本质差别。

从c枚举简单路径（p.33–35）【新】

p.33 把c标为origin。p.34 第一层只可能c→a或c→e，因为图中c只有这两条出边。p.35 扩展：c→a→b；c→e→b与c→e→d。每次保留已有前缀，同时把仍未出现过的邻点加到末尾。

算一遍：从c→e→d考虑下一步，d只有到c的边，但c已经在这条路径里，所以不能继续。这个判断依赖“本条路径访问过谁”，不能用一个全局visited集合把别的分支也误删。

完成枚举（p.36–37）

p.36 中c→a→b可加e，但不能加c；得到c→a→b→e。c→e→b之后，b的后继c与e都已访问，因此终止。p.37 最长分支再加d，得到c→a→b→e→d，然后d→c会重复起点，故也停止。

最终非空简单路径共有7条：c→a，c→a→b，c→a→b→e，c→a→b→e→d，c→e，c→e→b，c→e→d。若题目将长度0的路径也算入，则另加单点c；原页列表只展示非空路径。算法每次延长一条边，检查的是顶点重复，不能错误地允许一个顶点通过不同边再次出现。

树的层级（p.38–39）【新】

p.38 Trees have no cycles

图（p.38–39）：有根树。 元素：根有三个孩子；最右孩子再有两个孩子，其中右孩子继续向下有一个孩子；根标Level 0，最深叶在Level 3。 看什么：parent、child由相邻层的边确定，leaf没有孩子，root没有父节点；高度按最长根到叶路径的边数计，为3。

p.38 解释亲子与叶节点，p.39 加深度。根在Level0，因此四层节点对应三条边，不能把高度误数成4。树中每个非根节点有唯一父节点，所以从根到它的路径唯一；后面语法树的推导结构会使用这个性质。

直接证明与构造（p.40–42）【新】

p.41 Assume X is true, show directly that Y is true.

p.40 列三种证明方法。p.41 的直接证明从前提X出发，按已知事实推出Y。p.42 的图片具体展开两个奇数的乘积：设 $a=2x+1,b=2y+1$，则 $ab=4xy+2x+2y+1=2(2xy+x+y)+1$。括号内是整数，因此乘积仍奇。

算一遍（数字是我为演示取的，讲义没给）：x=1、y=2 时a=3、b=5，构造出的 $z=2xy+x+y=4+1+2=7$，所以 $ab=2z+1=15$。证明不仅说某个z存在，还给出怎样从x、y求出z。这就是constructive的含义。

数学归纳的逻辑（p.43–44）【新】

p.44 Inductive basis

p.43 给强归纳：先证明足够多的基础情形，再对任意k证明“若前面的结论都成立，下一项也成立”。p.44 把它分为basis、hypothesis、step。归纳假设是为了证明一个条件命题而暂时采用的前提，不是偷拿最终结论当事实；漏洞通常发生在没证基础情形，或使用比当前规模更大的情形。

补充：普通归纳只假设第k项，强归纳允许使用截至k的全部已知项。需要哪种，取决于规模为k+1的问题会分解成哪几个更小规模，而不是哪种名称显得高级。

二叉树叶数界：设定归纳（p.45–46）【新】

题面（L01-数学基础-2026T1.pdf · Example 1.5 · p.45）

p.45 Theorem: A binary tree of height $n$ has at most $2^{n}$ leaves.

公式按讲义重排。二叉树每个节点至多两个孩子；高度0时只有根，它也是唯一叶，所以 $L(0)=1=2^0$。p.46 假设不超过k层高度的树都满足相应上界，目标是高度k+1的情况。注意这是“最多”，有单孩子或提前结束的分支时可以远少于上界。

二叉树叶数界：完成归纳（p.47–48）

p.47–48 的原图沿底部虚线把第 k+1 层截去，用“每个原叶至多增加两个孩子”解释上界。沿该图补足论证：先把任意高度 k+1 的二叉树截成高度不超过 k 的树，归纳假设保证截断后至多有 $2^k$ 个叶。恢复底层时，每个被截断树的叶要么保持一个叶，要么长出一或两个孩子；因此对应的最终叶数最多为原来的两倍：

已经在更浅层结束的叶保留下来，不会遗漏；“至多两倍”包含它只贡献一个叶的情况。这与原图在底部扩展的思路一致，不需要把图误读成从根向下拆两棵子树。

算一遍：由基础项1起，高度1至多 $2\cdot1=2$ 叶，高度2至多 $2\cdot2=4$ 叶，高度3至多 $2\cdot4=8$ 叶。p.39 的一般树根有三个孩子，所以不能不检查“二叉”条件便套这个界。

递归不是归纳证明（p.49–51）【新】

p.49 Recursion is another thing

p.49 给递归定义 $f(n)=f(n-1)+f(n-2)$，基础值 $f(0)=f(1)=1$。递归用于定义或计算，归纳用于证明性质；两者可以配合，但不是同一种行为。算一遍：$f(2)=1+1=2$，$f(3)=2+1=3$，$f(4)=3+2=5$。

题面（L01-数学基础-2026T1.pdf · Example 1.6 · p.50）

p.50 A set $l_1,l_2,\ldots,l_n$ of mutually intersecting straight lines divides the plane into a number of separated regions

公式按讲义重排。p.50 给1、2、3条线对应2、4、7区；p.51 用 $A(n+1)=A(n)+n+1$，得到 $A(n)=n(n+1)/2+1$。补充，适用条件：这描述最大区域数，需没有平行线且没有三线共点；第n+1条线与旧n条线形成n个不同交点，切成n+1段，每段分裂一个区域。如果三线共点，三线只产生6区，不能套7。该条件可从p.51图上不同交点的用法看出，不能只凭“mutually intersecting”省略它。

算一遍：$A(1)=2$，加第二条新增2区得4；第三条新增3得7；第四条新增4得11。归纳代入为 $A(n+1)=n(n+1)/2+1+n+1=(n+1)(n+2)/2+1$，恰好是把原闭式n换成n+1。

反证法与根号2（p.52–54）【新】

p.52 we assume that P is false

p.52 先假设目标命题不成立，再推出矛盾。p.53 的定理为 $\sqrt2$ 非有理数；图中的根号在文本提取中丢失，公式按原页含义重排。假设 $\sqrt2=n/m$，先约成最简，n、m无公因子且m非零。这一步不可省，否则最后“两者都偶”不构成矛盾。

p.54 平方得 $n^2=2m^2$，故 $n^2$ 偶，从而n偶，写 $n=2k$。代回得 $4k^2=2m^2$，即 $m^2=2k^2$，因此m也偶。n、m同时含因子2，与最简假设冲突，故原假设不成立。

补充：为什么平方偶推出原数偶？若n奇，可写 $n=2r+1$，则 $n^2=4r^2+4r+1=2(2r^2+2r)+1$ 为奇。其逆否命题就是需要的结论。这是连接p.42直接构造与本页反证的关键一步。

考试角度：（A 级：HW01-2025T1-题目.pdf Q1；HW01-2026T1-题目.pdf Q1–Q2，考的是德摩根律与模4等价类。）见附录 A2。

给证明找一个不会循环的起点（补充自检）

归纳中最容易藏循环的句子是“删去一部分后仍符合条件，所以用归纳假设”。这里要同时验证两个事实：剩余对象仍在定理讨论的类别内，且规模严格变小。二叉树子树仍是二叉树，高度小于原树；这是能用叶数界的原因。若对一张有环图删掉一个节点却仍保留同样长的环，便不能借用一个要求“无环”的树定理。对象类别与规模缺一不可。

本讲核心考点

• 集合运算的逐元素解释与 DeMorgan 证明（p.7–11；A 级 HW01 Q1）。
• 模数等价关系诱导划分（p.17、23–24；A 级 HW01 Q2）。
• O、Ω、Θ 的量词与常数（p.19–21；C 级）。
• 路径、Euler 与 Hamiltonian 检查的对象不同（p.28–32；C 级）。
• 二叉树归纳、直线递推与反证法（p.43–54；C 级）。

附录

A1 作业/往年题演练（非讲义内容）：第一条 DeMorgan 定律

题面（HW01-2025T1-题目.pdf · Q1 · p.1）

p.1 Q1. Prove the first DeMorgan’s Law $\overline{A\cup B}=\overline A\cap\overline B$. (20%)

公式按原题重排。固定同一个全集U，任取 $x\in U$。逐步从左边成员关系出发：

第一步用补集定义，第二步用并集“至少一边”的否定，第三步把不属于改写为属于补集，第四步用交集定义。每步双向成立，因此已经同时证明左右互含，而非只证一个方向。任意x都如此，两集合相等。

回到正文：DeMorgan 与空集（p.10–11）

A2 作业/往年题演练（非讲义内容）：德摩根律与模4等价类

题面块（HW01-2025T1-题目.pdf（本地课件） · Q1 · p.1；补号按原图重排）：

p.1 Prove the first DeMorgan’s Law $\overline{A\cup B}=\overline A\cap\overline B$. (20%)

任取全集U中的x，x不在并集当且仅当它既不在A也不在B，当且仅当它同时在两个补集。逐项等价即同时给出两个包含方向。自取U={1,2,3}，A={1}、B={2}，左、右均{3}，用于核对“并的否定变且”。

题面块（HW01-2026T1-题目.pdf（本地课件） · Q1–Q2 · p.1；公式按原图重排）：

p.1 (25pts) Let A and B be subsets of a universal set U. Prove the second DeMorgan’s Law $\overline{A\cap B}=\overline A\cup\overline B$.

p.1 (25pts) Let S = {0, 1, 3, 4, 6, 7, 8, 10, 11, 13}. Define a relation R on S by $xRy\iff(x\bmod4)=(y\bmod4)$. Partition S into equivalence classes under R.

Q1：x不在交集中，等价于“x在A且x在B”不成立，等价于x不在A或x不在B，等价于x在右侧。逆向同一逻辑可逆，因此两集合相等。全集相同是补集定义的必要前提。

Q2：按余数0、1、2、3分别得到{0,4,8}、{1,13}、{6,10}、{3,7,11}。每个S成员出现一次，四块非空且互不相交。关系自反来自余数等于自身，对称来自等号对称，传递来自等号传递；所以这些块确实是等价类，不只是任意分组。13与1同类，因为二者余数1；10余数2，不与0同类。

2026题目页头起始年份仍写2025、截止写2026，存在日期混排；本文按文件版本与已保存课程来源识别，不据混排日期重新命名题目。

回到正文：德摩根律与模4等价类

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 HW01-2025T1-题目.pdf、HW01-2026T1-题目.pdf、HW02-2025T1-题目-更新.pdf、HW03-2025T1-题目.pdf、HW04-2025T1-题目.pdf、HW05-2025T1-题目.pdf、期中练习-含解答-学期待核.pdf、期末-2022T1-资料包.pdf、Final-Exam-2023T1-题目.pdf、Final-Exam-2024T1-题目.pdf、Final-Exam-2025T1-题目.pdf、期末-2023T1-资料包.pdf、期末-2024未核-资料包.pdf；未识别用途的 PDF：无

• 原件：L01-数学基础-2026T1.pdf（本地课件），PDF p.1–54。

• 本次复核：2026-10-13；逐页读取原件文字，视觉核对图片公式、图及文法排版，保留已发布稿的深化段落。