期末复习 · 离散结构
离散结构考前复习
344 道学习通原题(已去重)
错题与进度
我的复习计划
这里按老师发布的作业统计;章节自测的记录仍可在题库里查看。
作答保存在当前浏览器,可导出为 JSON 自行留存。
离散结构考前速通笔记
先看考前速查,再按需要复习概念与例题。量词翻译和偏序确界的常见误区在相应章节单列说明。
范围按老师划出的重点整理:逻辑等价证明、谓词逻辑翻译、命题逻辑推理、关系闭包、等价关系与等价类、偏序特殊元素。上下界与确界作为偏序的配套内容纳入。谓词逻辑需要会翻译,课堂说明推理题掌握命题逻辑推理即可。其他章节是否出题,课堂转写没有给出明确结论。
后面的「补充一」至「补充四」来自刷章节自测时补学的内容:谓词逻辑推理、证明方法、元素与幂集、函数与映射。它们是刷题用的补充,不代表老师扩大了划定的考试范围。
考前重点提醒|先核对行列。 即使读对了量词,把一种表头的「找行/找列」套到另一种表头,结果也会错。先标行变量、列变量;用一格校准;最后固定最外层量词的变量。
考前速查
| 考点 | 拿到题先做什么 | 交卷前检查 |
|---|---|---|
| 逻辑等价 | 消去蕴含符号,按目标式整理;也可列真值表 | 每步写依据,或核对两列在全部赋值下相同 |
| 谓词翻译 | 写论域,再定外层量词、谓词和计数对象 | 检查括号作用域、变量类型,以及“恰好两个”的不等式 |
| 命题推理 | 符号化前提和结论,再匹配规则 | 每行写行号与规则。反例逐条核对前提 |
| 关系闭包 | 写原关系矩阵,再按所求闭包计算 | 布尔幂逐项取或。新增边要和原关系比较 |
| 等价关系 | 分别证明自反、对称、传递,再求类 | 商集内各类去重,并集应覆盖原集合 |
| 偏序特殊元素 | 确认题目采用的偏序,标清总集合与子集 | 极值与最值分别判断。求确界先列全候选界 |
一 逻辑等价
条件式只有前真后假时为假。下表的等价式可以双向使用; 表示恒真, 表示恒假。
| 定律 | 等价式 |
|---|---|
| 结合律:只改括号的位置 | ; |
| 第一分配律:析取对合取 | |
| 第二分配律:合取对析取 | |
| 交换律:交换左右两项 | ; |
| 德摩根律:否定推入括号 | ; |
| 双重否定 | |
| 吸收律 | ; |
| 幂等律 | ; |
| 恒等律 | ; |
| 支配律 | ; |
| 排中与矛盾 | ; |
| 蕴含等价式、否定与逆否 | ;; |
| 双条件的展开 |
用韦恩图理解等价式。 可以把命题对应到一个集合。以所有真值赋值为全集,每个命题圈出使它为真的赋值。合取 对应交集,析取 对应并集,否定 对应相对于全集的补集。两边圈出的区域完全相同,就表示两式逻辑等价。比如 只排除「 真而 假」的区域,剩下的正好是 。
答题用语。 从 改写为 时,在推导旁写「蕴含等价式()」。反过来改写也可注明同一依据。
结合还是分配? 连续两个 或两个 ,只是换括号,叫结合。外层和内层分别是 与 ,外面的同一项分别同括号里的两项运算,叫分配。分配也可以倒着用来提公共项。 不能像 、 一样直接换括号。
课堂范题 证明 。
也可以列 行真值表。两式仅在 时为假,其余为真。要判定两个式子不等价,找到一组赋值让结果不同即可。例如 时,,而 。
模拟卷第 21 题用到的分配律 消去蕴含后,对 用德摩根律,得到 。用交换律把 写到前面,就能套第一分配律:
把两项分别还原成蕴含,得到 。这一步把同一个 分给了两个式子,因此用的是分配律。
复习检查点 先把“如果”和“那么”后的两部分各自圈出,再写箭头。之前把“没发现鲨鱼”的否定看漏过,属于读题疏忽。看到 时,用括号确认否定作用在哪个整体。
等价定律速查
| 定律 | 公式 |
|---|---|
| 交换律 | ; |
| 结合律 | ; |
| 分配律 | ; |
| 德摩根律 | ; |
| 吸收律 | ; |
| 幂等律与双重否定 | ; |
| 同一律与互补律 | ;, |
结合律只移动同类联结词的括号;分配律把一项分别分给括号内两项。蕴含一般不满足结合律。
双条件的否定(模拟卷第 5 题):。双条件比较两侧真值是否相同,否定其中任意一整侧,就把同真值和不同真值互换。两侧都否定则仍等价于原式。这个方法不能直接套到单向蕴含上:。
二 谓词逻辑翻译
以下两种句型假设 的论域比 所限定的范围更大:
| 中文句型 | 公式 |
|---|---|
| 所有 都满足 | |
| 有些 满足 | |
| 并非所有对象都满足 | |
| 没有任何对象满足 |
全称句需要检查所有对象,对属于 的对象提出要求。存在句需要找到一个同时满足 和 的见证。如果论域已限定为 ,就可以直接写 或 。
模拟卷第 22(1) 题:可以先用中文处理否定。 「并非所有本班学生都提交了实验报告」可以先读成「至少有一名本班学生没有提交实验报告」,再写 。其中 表示「 是本班学生」, 表示「 已交报告」。用符号推导也会得到同一个式子:
先用「甲交了、乙没交,两人都在本班」验算:原句为真,「所有本班学生都没交」为假。如果保留 、只把 改成 ,就说成了后者。如果换成 却保留箭头,班外学生会让 自动为真,充当不合格的见证。找到的同一个人要同时满足在本班、没交报告。
作业范题 有些计科学生没有修任何课程。设 遍历学生, 遍历课程, 表示计科学生, 表示学生 选修课程 。
把内层写成 ,表达的是“至少有一门没修”。一个修了离散结构但没修操作系统的学生也能满足这个写法。
计数模板 先固定外层对象,再写完整的计数条件 。确立见证后,用全称量词排除其他合格对象。
复习变式范题 每位计科学生都恰好选修两门课程。设 遍历学生, 遍历课程, 表示学生 选修课程 。
放在当前学生的要求内,允许不同学生选择不同课程。换成“有些计科学生”时,外层改为 ,内层计数规则仍然适用。
量词前移:以上面「每位计科学生恰好选两门课」为例。 通常假定课程论域非空。先把 提出合取,因为前面的 、、 都没用到 ;再把 从蕴含的后件提出来,因为前件 没用到这三个变量:
这叫前束范式。两种写法都按同一顺序读:先任取学生 ;如果是计科学生,就为他选定两门课 ,再用任意 检查有没有第三门。把 交换到 前,就要求所有计科学生共享同一对课程;把 换到 前,就允许每检查一门课时重选一对。比如某人选了 A、B、C 三门,每次都能选一对覆盖当前检查的课程,却无法用固定的一对覆盖三门。
考场写法。 题目只要求翻译时,保留量词在各自的括号里更容易复核。若要前移,检查它跨过的那部分有没有该变量的自由出现(没被那部分里的量词绑定的使用),并按等价式变换。跨过否定或穿出蕴含的前件时量词要互换,不能照搬上例。如果题目允许课程论域为空,直接保留上面的嵌套写法。
如果换成“存在一个项目,其负责人中恰好有一名开发者”,先用 找项目,再对开发者负责人计数。设 表示员工 是开发者, 表示 负责项目 。完整计数条件是 :
复习检查点
- 先圈出“每位”“有些”“没有任何”。曾把全称句中的类别限制写成合取,也曾把“有些”的外层符号写成全称。
- 检查每个变量的论域,以及每次使用是否落在相应量词的括号内。排除第三门课时,检查的是课程是否被当前学生选修。数项目的开发者负责人时,检查条件要同时包含开发者身份和负责人关系。
- “恰好两个”逐项勾掉:两者存在、彼此不同、没有第三个。重复写同一条件属于冗余。漏写 则会允许两个见证指向同一个对象。
模拟卷第 22 题:否定与量词位置
「并非所有本班学生都提交」可先改述为「至少一个本班学生没有提交」,直接写 。若只否定谓词而保留全称,就变成「所有本班学生都没交」;若把箭头保留在存在量词内,可能误让非本班学生成为见证。
量词可以通过等价变换移到前面,得到前束形式,但不能只搬符号并丢掉作用域。恰好两个项目可写成 ,其中 ,。项目论域非空时可变为 。移量词前检查变量是否在其他部分自由出现,并保留依赖顺序;如 先挑一个共同对象, 则允许逐人重选。考试优先写能直读原句的嵌套式。
★ 行列映射:先看表头,再固定外层变量
典型错因(嵌套量词题): 我知道 C 是「先固定一个 ,再检查所有 」,但把表中 、 对应的行列弄反了。这是坐标映射的问题;之前从内往外读量词是另一次错误。
- 标表头。 两种画法都可以:行是 时,固定 就扫列;行是 时,固定 就扫行。
- 用一格校准。 如果行是 、列是 ,那么 要填在第 3 行第 1 列。换表头时也要转置数据。
- 再读量词。 C 是 。按行=、列= 填:
| 行 /列 | 1 | 2 | 3 |
|---|---|---|---|
| 1 | 0 | 1 | 1 |
| 2 | 0 | 0 | 1 |
| 3 | 1 | 0 | 1 |
没有一行全为 1,所以 C 为假。第 3 列全为 1,固定的是 ,因此为真的其实是 A:。别背「存在就找行」;先看存在量词管谁,再查另一维。 关系矩阵题若已指定第一个分量对应行、第二个对应列,就按题目约定。
三 命题逻辑推理
论证有效,要求前提全真时结论必真。要否定有效性,只需找一组赋值,让所有前提为真、结论为假。
| 规则 | 已知 | 推出 |
|---|---|---|
| 假言推理 | , | |
| 取拒式 | , | |
| 假言三段论 | , | |
| 析取三段论 | , | |
| 化简律 | 可取出 或 | |
| 合取律 | , | |
| 附加律 |
课堂范题 设 分别表示停电、空调停转、服务器需迁移、完成备份。从以下前提推出服务器需迁移。
| 步骤 | 公式 | 依据 |
|---|---|---|
| 1 | 前提 | |
| 2 | 前提 | |
| 3 | 前提 | |
| 4 | 前提 | |
| 5 | 1、2,假言三段论 | |
| 6 | 3、4,析取三段论 | |
| 7 | 5、6,假言推理 |
反例范题 、、 能否推出 ?先让结论假,取 。为了使第三个前提为真,取 。此时前两个前提都是 ,第三个也为真,反例成立。等价演算也可以做:三个前提的合取化简为 ,因此 可以取 0 或 1。
复习检查点 正向推理第 12 题已写对。第 16 题中把 看成 ,已确认是看错符号。单独记住反例的验算步骤:先让结论假,再核对每条前提。例如 会令第三个前提为假。论证无效表示前提允许结论为假,是否也允许结论为真要另外检查。
四 关系性质与闭包
同一集合 上的关系是 的子集。关系矩阵按相同元素次序排列行和列,行是起点,列是终点。 是恒等关系,对应单位矩阵 。
| 性质 | 检查方式 |
|---|---|
| 自反 | 每个元素都有自环 |
| 对称 | 每条边都有反向边 |
| 反对称 | 不同元素之间没有双向边,自环允许 |
| 传递 | 每条两步走法都有对应的直接边,允许重复顶点 |
闭包是包含原关系且满足指定性质的最小关系。设 有 个元素,原矩阵为 :
| 闭包 | 矩阵公式 | 考试操作 |
|---|---|---|
| 自反闭包 | 主对角线全置 1 | |
| 对称闭包 | 对角线两侧的对应位置同时置为两者的或 | |
| 传递闭包 | 各次布尔幂逐项取或,保留所有至少走一条边可达的位置 |
三种闭包分别从原矩阵出发。 在对应位置取或,矩阵的幂用布尔乘法。沿用普通矩阵乘法的行对列结构,将乘换成与、加换成或。也可以用普通乘法算出 0/1 矩阵的乘积,再把正数改成 1。
求传递闭包时,先用布尔乘法求幂,再逐项取或。 若记 ,则 ,( 表示布尔矩阵乘法)。 记录恰好走 条边能到达的位置。传递闭包记录所有可以经过至少一步到达的位置。
一步可达的位置由 提供。在 的记号下,首项写 即可。各次幂之间用 逐项合并。例如只有一条边 时,,这条边仍由 保留在传递闭包中。求自反传递闭包时,再并上单位矩阵 。
闭包范题 按 排列,设 。这是课堂服务器通信例题的关系。
- 自反闭包补 。
- 对称闭包补 。
- 本题 ,所以传递闭包为 。结果每一行都是 。走不到 ,因此第一列全为 0。 处在回路上,因此三者都有自环。
复习检查点 只有自环与 的关系可以是传递的,因为 与 都已有直接边。以前漏掉了回路 所要求的 ,又把已有的 算进新增边。题目如果问“新增”,最后用闭包减去原关系。布尔矩阵计算练习已做对。
五 等价关系与等价类
等价关系满足自反、对称、传递。 是与 等价的一组元素。等价关系具有对称性,因此用关系矩阵的第 行找所有为 1 的列,也可得到 。商集 由所有不同的等价类组成。
课堂范题 整数集上规定 。 表示左边的 整除右边的 ,即 ,其中 是整数。
- 自反:,所以 。
- 对称:若 ,则 ,所以 。
- 传递:若 、,则 ,所以 。
等价类为 、、,所以商集是 。余数相同的元素属于同一类,例如 。
有限集合范题 ,。从 1 找到 ,划去这两个元素。从剩下的 2 找到 ,再划去两者。最后得到 。商集为 ,共 3 类。
复习检查点 指定的 、、 都求对了,后来商集漏掉 ,已确认是疏忽。求完商集,把各类取并集并与原集合核对。题目第一问点名的元素可能只覆盖一部分等价类。
规范例题:整数按模 5 分类
设 ,论域为 。等价关系必须同时自反、对称、传递。等价类 是与 等价的全体元素;商集是所有不同等价类的集合。同类元素都可作代表元;不同的类不相交,所有类合起来覆盖论域。
- 自反:任取 ,,故 。
- 对称:若 ,则 (),所以 ,故 。
- 传递:若 、,则 、,故 ,所以 。综上, 是等价关系。
- 带余除法写成 ,其中 、。、,故 ,包含 。商集是 ,共五类。非负的是标准余数,类中的整数不受这个限制。
六 偏序与特殊元素
偏序满足自反、反对称、传递。哈斯图只画覆盖关系,省略自环与传递边。从下往上沿边可以判断可比性。若 ,且集合里没有 满足 ,则 覆盖 。
| 元素 | 判断依据 |
|---|---|
| 极小元/极大元 | 没有元素严格在它下面/上面 |
| 最小元/最大元 | 它在所有元素下面/上面,允许相等 |
| 上界/下界 | 从总集合选候选,与子集的每个元素比较 |
| 上确界/下确界 | 在所有上界中取最小元/在所有下界中取最大元 |
极值与覆盖范题 ,按整除排序。1 整除所有元素,所以是最小元,也是唯一极小元。12、18 各自上方都没有元素,所以都是极大元。两者互不整除,集合中没有最大元。12、18 都直接覆盖 6。写答案时用“最大元不存在”,数字 0 代表的是一个具体元素。
确界对照范题 固定总集合 ,规定 。
| 被考察子集 | 上界集合 | 下界集合 | 上确界 | 下确界 |
|---|---|---|---|---|
| 不存在 | 1 | |||
| 12 | 2 |
第一行中,12、18 都是共同倍数,但互不整除。要作上确界,候选必须整除所有上界。数值较小的 12 在这里也做不到。若把 6 加回总集合,6 就成为上确界。
第二行中, 且 ,所以 12 也能作上界。 且 ,所以 2 也能作下界。先筛候选,再按整除关系排序。候选集合只有一个元素时,它同时是该候选集合的最小元和最大元。另外,若 自身有最大元或最小元,它们分别就是 的上确界或下确界。
复习检查点 上界列表曾带入上一题的 6,已确认是没注意总集合换了。另一题漏掉子集里的 2 和 12。因此先在草稿上分别写 和 ,再用“ 中每个元素都整除候选”筛上界,用“候选整除 中每个元素”筛下界。比较使用 ,允许相等。 先把两个候选集合列全,确界只在对应的候选集合里选。
规范例题:整除偏序中的极值、界和确界
设总集合 ,用整除作为偏序 ,取 。
| 概念 | 候选从哪里找 | 判定标准 |
|---|---|---|
| 极小元/极大元(对集合 ) | 内 | 没有严格在它下方/上方的 中元素;可以有多个 |
| 最小元/最大元(对集合 ) | 内 | 小于等于/大于等于 的每个元素;存在时唯一 |
| 下界/上界(对 ) | 整个 | 对所有 ,分别满足 /;界不必在 内 |
| 下确界/上确界 | 下界集/上界集 | 分别是该集合的最大元/最小元 |
- 覆盖对。 若 且 ,并且在 中没有介于二者之间的第三个元素,则 覆盖 。逐项得以下八对:、、、、、、、。例如 ,但 且 ,故 不是覆盖对。
- 求 的极值与最值。 整除 中所有元素,故它是最小元,也是唯一极小元。 和 在 中都没有严格更大的元素,其余元素都有,故极大元恰为 。二者不可比,因此 无最大元。
- 求 的界。 下界集合为 ;上界集合为 。
- 在界的集合内求最值。 下界集只有 ,故 。若上确界存在,必须属于 且整除其中每个元素。、,所以没有上确界。 是通常意义下的最小公倍数,但不在 中;若把 加入 ,它才是上确界。
若题目改问 自身的极值,候选只取 。二者不可比,所以既都是极小元,也是极大元; 本身没有最小元、最大元。这不妨碍它在 中有下确界 。
补充一 谓词逻辑推理
有效论证指不存在「所有前提都真、结论却假」的情况。证明有效,要说明每一步依据哪条前提或哪条已推出的判断;证明无效,要构造一个让所有前提同时为真、结论为假的反例。
| 规则 | 从哪里到哪里 | 使用条件 |
|---|---|---|
| 全称实例 | 从 得到 | 是论域中的对象,可以是题目已经点名的人 |
| 存在实例 | 从 出发,把一个见证暂记为 ,在推导中使用 | 用新名字;不能认定它就是已知的某人,也不能把这个见证当任意对象 |
| 全称引入 | 对任取的 证明 后,推出 | 不得依赖 的特殊条件;只能概括到原先任取对象的范围 |
| 存在引入 | 已知 ,推出 | 找到一个真正满足目标全部条件的见证即可 |
做题顺序:从目标倒着列条件,再从前提正着找依据。 先用「因此」分开前提和结论,再写论域和会反复用到的谓词。前提可以给事实,也可以给规则;不要试图用前提 A 去证明题目已经给出的前提 B。应该从 A 取出需要的事实,把 B 的规则用在同一个对象上,再组合得到目标。
范题:本班有人到过法国;所有到过法国的人都参观过卢浮宫;所以本班有人参观过卢浮宫。 设 、、 分别表示「是本班学生」「到过法国」「参观过卢浮宫」。从 取见证 ,得到 。取出 ,把 用到同一个 上,再由 和 得到 。回到第一条事实取出 ,与 合取,最后推出 。如果要求逐行写清规则,两项分别取出,各记一次化简;选项有时会把其中一次取项写成隐含步骤。
几个容易混的判断:
- 「某人」和「点名」不同。 前提说「班上某人」,用存在实例找见证;直接说「本班学生 Linda 有红色敞篷车」,则已经有 Linda,可以直接用她。不必另找一个人。
- 论域大,类别写入公式;论域已经限定,类别由取值范围保证。 对全体学生写「室友都选过离散」是 ;若只从室友取人,则可以写 。室友选算法题按题库路线,用两次全称实例、假言推理、全称引入;保留 时,也可用假言三段论接起两个箭头。不要把任取的一位室友概括成所有学生。
- 有量词不等于每个量词都要展开。 「有红色敞篷车的人至少收到过一张罚单」可写成 。箭头只要求有车者收到罚单, 对当前这个人选罚单。若只需要证明 Linda 收到过罚单,把 整体记为 即可;不必指出是哪张罚单。
- 认清「且」怎么用。 从 取一项是化简;已知两项再拼成「且」是合取;从 推出 才是附加。「有 PC 的人都会 Word」是 ,不是 ;若改写为析取,等价式是 。
对应原题:1.10 第 2 题:卢浮宫、第 15 题:Linda、第 26 题:室友选课。
补充二 证明方法与反例
| 方法 | 从哪里开始 | 什么时候好用 |
|---|---|---|
| 直接证明 | 假设 成立,然后推出 | 从定义或已知条件能直接算到结论 |
| 逆反证明(逆否证明) | 为证明 ,改证 | 从「结论不成立」出发,更容易推出「前提不成立」 |
| 归谬法(反证法) | 假设整个待证命题为假,再推出矛盾 | 假设为假后,会与已知事实冲突 |
| 分情形证明 | 按一个性质分成若干种情况,每种都证明结论 | 对象很多,但只有少数情况影响结果 |
| 穷举证明 | 列出论域内的每一个候选对象,逐个验证 | 对象总数很少,能直接查完 |
| 给出反例 | 找到一个符合论域和条件,却不满足结论的对象 | 要否定全称命题时,一例就够 |
范题 1:正偶数的平方只以 0、4、6 结尾。 个位只由原数的个位决定,故把正偶数分为末位为 0、2、4、6、8 的五类。对应平方末位为 0、4、6、6、4。每类都可能有无限多个数,仍已覆盖所有正偶数,这叫分情形。
范题 2:对所有小于 6 的正整数,。 候选只有 。左边依次为 ,右边依次为 ,逐个比较即可,这是穷举。把原句否定成「存在一个小于 6 的正整数使 」是在找反例;若用逆反证明,仍要对正整数证明「若 ,则 」。全称取否定才变成存在;改写成逆否命题不会。
对应原题:1.11 第 8 题:偶数平方个位、第 22 题:阶乘不等式。
补充三 元素、子集与幂集
- :整个 是 中的一项。若 ,则 ,但 。
- :把 的最外层打开,里面每一项都在 中。集合可以是自己的子集; 是每个集合的子集,但不一定是元素。
- 幂集 是所有子集组成的集合。 。若有限集合 有 个元素,每项选或不选,故幂集有 个元素。
范题:,判断哪个选项是 的元素。 先算出 ;再取幂集时,能选的是整个 和整个 :
| 第二次取幂集时选了什么 | 得到的元素 |
|---|---|
| 都不选 | |
| 只选空集 | |
| 只选集合 | |
| 两项都选 |
判断选项 时不必全列:把 改读为 ,再只拆 的最外层,查各项能否从 中选出。 可以;直接含数字 的选项不行。选了一项以后,还要套一层括号,把选出的项组成集合。
对应原题:2.2 第 9 题:两次取幂集。
补充四 函数与映射
中, 是定义域(合法输入), 是陪域(指定的目标集合)。值域 是实际能得到的输出,可能只是陪域的一部分。判断是不是函数,从输入往外看;判断单射、满射,从目标值往回看。
| 要判断什么 | 检查方法 | 怎么判定不成立 |
|---|---|---|
| 函数 | 每个 都有恰好一个输出,且输出属于 | 找一个合法输入,它没输出、有多个输出,或输出不在陪域 |
| 单射(一对一) | 每个 最多一个原像;等价于 | 找两个不同输入得到同一输出 |
| 满射(映上的) | 每个 至少一个原像;等价于 | 找一个陪域中的值,没有任何合法输入能得到它 |
| 双射 | 既单射又满射,每个目标值有恰好一个原像 | 单射或满射任意一项不成立即可 |
范题 1: ,,。从任意目标 往回解:,,唯一解是 ,且它仍是整数有序对。有解说明满射,解唯一说明单射,所以是双射。判断满射时,解出来的输入还必须属于原定义域。
范题 2: 是所有长度至少为 1 的位串。规则「取前两位」不能定义 :合法输入 "0" 没有第二位,规则未指定该输入的输出。规则「总是输出 "1"」却是合法的常值函数:每个输入都能得到恰好一个合法输出。它既不是单射("0" 和 "1" 得到同一个输出),也不是满射(目标 "0" 永远得不到)。先检查边界输入,再问会不会撞值、会不会漏目标。
对应原题:2.2 第 10 题:整数对映射、第 13 题:位串函数。
我的错因与考前自检
下面汇总容易混淆的概念和相应的自查办法。
| 题型 | 错因或不熟练点 | 下次怎么查 |
|---|---|---|
| 命题翻译与等价 | 把「只有」读成「只要」;曾把结论取反当成整句取反;模拟卷第 5 题易把单向条件当成双条件 | 先把条件句读成「有谁就能推出谁」;,双条件的否定则可翻转任意一整侧。结合律只换括号,分配律会展开或提取共同项 |
| 量化命题的否定(模拟卷第 22 题第 1 问) | 对先用中文否定再翻译没把握;原先试写的式子未提供,具体错因待核对 | 先说成「存在一个本班学生没提交」。用「有人交、有人没交」检验是否误写成「所有人都没交」;核对见证必须在本班 |
| 量词位置和恰好两个(第 22 题第 2 问) | 不确定何时能把量词移到开头;此前作答漏过不同性,或括号没有盖住后续条件 | 先写嵌套式,勾掉「两个都满足、两者不同、没有第三个」;移位时检查自由变量、原作用域和依赖顺序 |
| 嵌套量词与表格(第 6 题) | 确认读对了 C,错在把表头的行列弄反;早先另有一次先读内层的错误 | 标表头 → 用一格校准 → 固定外层变量 → 检查内层 |
| 谓词的论域与参数 | 混淆「没有修任何」和「至少一门没修」;曾把判断式当成关系的参数,或把计数扩大到题目没要求的对象 | 「没有任何」用 ;谓词的参数填学生、课程等对象;唯一性要重复检查完整的合格条件 |
| 推理的依据 | 曾想直接用一个前提证明另一个前提;不熟悉何时用实例、化简、合取和引入 | 看结论缺哪些事实,把通用规则套到同一对象。已点名的 Linda 不必再找见证;未点名的「某人」才用存在实例。找反例要确认每条前提真、结论假 |
| 证明方法 | 容易混淆找反例、逆否、逐个枚举和按性质分组 | 逆否还是证明一个蕴含;找反例是让全称命题为假。有限个位分组是分情形,零散的有限输入逐个代入是穷举 |
| 关系与闭包 | 自反曾只检查部分对角元;传递闭包漏过回路产生的自环,并把原有边计入「新增」;曾把笛卡尔积大小当作关系个数 | 对角全查;闭包先求全部可达有序对,再减去原关系找新增;每个候选对都可选或不选,关系个数是 |
| 等价类(第 25 题) | 把代表元或标准余数的范围误当成类中元素的范围 | 先看论域是整个整数集,再按差能否被 5 整除分组。 和 同类,类中可有负数、零或正数 |
| 偏序和确界(第 26 题) | 曾把公倍数 18 当成上确界;求界练习也曾误用上题的总集合 | 写清 、 和比较规则。在 找界,再按整除比较界;12 和 18 不可比,所以有上界却无上确界。极大元只要求上方没人,最大元要求在所有元素上方 |
| 元素、子集和幂集 | 曾混淆「属于幂集」和「是幂集的子集」,以及空集本身和把空集选进去 | 。遇 整体对照,遇 只拆最外一层; 总是子集,却未必是元素 |
| 函数、单射与满射 | 曾拿定义域外的负数判断撞值;取整后平方漏检平方撞值;把陪域漏值当成函数没定义 | 先查每个合法输入是否有唯一合法输出,再查单射和满射。单射的反例要两个合法输入;向下取整后还要检查相反数平方相同;值域可小于陪域,漏目标只说明不满射 |
合上笔记自测
- 设 表示员工 是开发者, 表示 负责项目 。分别翻译“有些开发者恰好负责两个项目”和“存在一个项目,其负责人中恰好有两名开发者”。
- 设 、。分别写三个闭包新增的有序对。
- 在 的整除偏序中,对 和 分别求四项:所有上界、所有下界、上确界、下确界。
- 在整数集上用 定义 。独立写出三个性质的证明,再给出 。
核对答案
- 第一题外层用 找开发者,内层数项目,计数条件为 。第二题外层用 找项目,内层数员工,计数条件为 。两题都将完整的计数条件代入“恰好两个”模板,检查见证不同。
- 自反新增 。对称新增 。传递新增 。1 没有入边,所以传递闭包中没有 。
- 时依次为 、、12、2。 时依次为 、、4、2。
- 依次用 、、。商集是 ,其中 。