离散数学复习 (I)

期中考试时间: 2025.11.20
期末考试时间: 2026.01.07

第一章 命题逻辑

1. 命题, 真值, 真命题, 假命题.
2. 将命题描述的事物替换为变量, 用来表示一系列命题, 这叫做命题变项. 命题变项不是命题. 需要凸显与命题变项相对时, 命题也称命题常项.
3. 简单命题, 复合命题, 联结词.
4. 否定 , 合取 , 析取 , 蕴涵 , 等价 . 中 为前件, 为后件.
5. 联结词的优先级: 从高到低为 .
6. 命题的符号化. 这门课里约定 “ 仅当 ” 指的是 而非 .
7. (命题) 公式. 公式的层次 (从 开始计算). 公式的解释与赋值 (成真赋值, 成假赋值).
8. 含 个命题变项的公式有 个赋值, 全部列出可得到真值表. 含 个命题变项的公式, 其真值表有 种可能.
9. 永真式 (重言式), 永假式 (矛盾式), 可满足式.
10. 等值 (). 注意 与 是不同范畴的概念.
11. 置换规则与等值演算.
12. 24 个重要等值式:
    1. 双重否定律.
    2. 等幂律, 交换律, 结合律, 分配律.
    3. 德摩根律, 吸收律.
    4. 零律, 同一律, 排中律, 矛盾律.
    5. 蕴涵等值式, 等价等值式, 假言易位, 等价否定等值式.
    6. 归谬论.
13. 涉及蕴涵的几个等值式:
    1. .
    2. .
    3. .
    4. .
14. 文字, 简单析取式, 简单合取式, 析取范式, 合取范式.
15. 范式存在定理: 任一命题公式都存在与之等值的析取范式和合取范式. 事实上, 只需进行三个步骤:
    1. 消去除 外的联结词.
    2. 利用 , 内移或消去否定联结词.
    3. 利用 对 的分配律求析取范式, 利用 对 的分配律求合取范式.
16. 极小项及其记号. 主析取范式.

17. 主析取范式存在唯一定理. 任何命题公式均存在主析取范式, 且主析取范式唯一.

    唯一性显然. 存在性的证明方式是把简单合取式都扩充成若干极小项 (这就是主析取范式的构造方法).

18. 极大项及其记号, 主合取范式.
19. 主合取范式也满足存在性和唯一性. 事实上, 主合取范式的各个极大项的出现的下标就是主析取范式各个极小项中没有出现的下标.
20. 联结词完备集. 显然 是一个联结词完备集.
21. 都是联结词完备集.
22. 与非 , 或非 .
23. 都是联结词完备集. 事实上, $$p\uparrow p\Leftrightarrow\neg p\Leftrightarrow p\downarrow p,\\(p\uparrow q)\uparrow(p\uparrow q)\Leftrightarrow p\land q\Leftrightarrow (p\downarrow p)\downarrow(q\downarrow q),\\ (p\uparrow p)\uparrow(q\uparrow q)\Leftrightarrow p\lor q\Leftrightarrow(p\downarrow q)\downarrow(p\downarrow q).$$
24. 推理及其形式结构. 前提与结论. 推理的正确性.
25. 推出 (). 注意 与 是不同范畴的概念.
26. 8 条推理定律:
    1. 附加
    2. 化简
    3. 假言推理
    4. 拒取式
    5. 析取三段论
    6. 假言三段论
    7. 等价三段论
    8. 构造性二难
27. 推理规则: 前提引入, 结论引入, 合取引入, 推理定律.
28. 推理的证明.
29. 附加前提证明法与归谬法.

第二章 一阶逻辑

1. 个体词: 个体常项, 个体变项.

2. 个体域, 全总个体域. 个体域不能为空.

3. 谓词: 谓词常项, 谓词变项.
4. 量词: 全称量词 , 存在量词 . 有限个体域中量词可展开.
5. 一阶逻辑中命题的符号化.

   例 1. 在一阶逻辑中将下列命题符号化:
   (1) 有的兔子比所有的乌龟跑得快.
   (2) 不存在同样高的两个人.
   解 (1) , 其中 : 是兔子, : 是乌龟, : 比 跑得快.
   (2) , 其中 : 是人, : , : 和 同样高.

6. 项, 原子公式.

7. (逻辑) 公式.

8. 指导变项, 辖域, 约束出现, 自由出现.
9. 闭式. 在最前面加量词可使任意公式变为闭式.
10. 解释. 注意, 解释的对象包括谓词变项, 但不包括个体变项.
11. 赋值. 赋值的对象是自由出现的个体变项. 赋值 中 的值记为 .
12. 永真式, 永假式 (矛盾式), 可满足式.

    例 2. 判断下列逻辑公式的类型:
    (1) .
    (2) .
    解 (1) 记此公式为 . 设 为 的任意一个解释, 其个体域为 . 若 为假, 则 为真. 若 为真, 由于 非空, 可设 , 则 为真, 于是 为真, 仍为真. 因此解释 下 为真. 由 的任意性知 为永真式.
    (2) 记此公式为 . 取解释 : 个体域为 , . 在 下, 的前后件均为真, 故 为真.
    再取解释 : 个体域为 , . 在 下, 前件为真, 后件为假, 故 为假.
    由于 在解释 下为真, 而在解释 下为假, 是非永真的可满足式.

13. 代换实例: 用谓词公式代换命题公式的命题变项得到的逻辑公式.

14. 永真式的代换实例均为永真式, 永假式的代换实例均为永假式.

    例 3. 判断逻辑公式

    $$(\exists xF(x)\lor\exists yG(y))\land\neg\exists yG(y)\rightarrow\exists xF(x)$$

    的类型.
    解 此公式是 的代换实例, 而 , 故此公式是永真式.

15. 等值 (). 显然, 命题逻辑中的等值式的代换实例均为等值式.

16. 一阶逻辑中重要的等值式:

    1. 换名规则: 将公式中某个量词的指导变项及其在辖域内的所有出现都换成辖域内未曾出现过的某个个体变项, 所得公式与原公式等值.
    2. 量词否定等值式: .
    3. 量词辖域收缩与扩张等值式:
    4. 量词分配等值式:

       例 4. 证明下列等值式:
       (1) .
       证 (1)

       $$\begin{align*} \neg\exists x\exists y(F(x,y)\land G(x,y)) &\Leftrightarrow \forall x\forall y\neg(F(x,y)\land G(x,y)) \\ &\Leftrightarrow \forall x\forall y(\neg F(x,y)\lor\neg G(x,y)) \\ &\Leftrightarrow \forall x\forall y(F(x,y)\rightarrow\neg G(x,y)).\end{align*}$$

17. 前束范式.
18. 前束范式存在定理: 任一谓词公式均存在与之等值的前束范式. 事实上, 只需进行以下步骤:
    1. 消去除 外的联结词.
    2. 利用量词否定等值式将联结词 向内深入, 使之直接作用于原子公式.
    3. 利用换名规则, 使所有个体变项的名字均不同.
    4. 利用量词分配等值式和量词辖域收缩与扩张等值式, 将所有量词移至公式的开始, 即辖域覆盖整个公式.

19. 一个公式可能存在与之等值的若干有 “非平凡” 的区别的前束范式. 例如, 与前束范式 与 均等值.

    这个例子也告诉我们 .

20. , 其中 根据以下规则确定: 当 为 或 时, 就是 ; 当 为 时, 是与 对偶的量词 (即 和 一个为 , 一个为 ).
21. 上一条的一个推论是 .
22. 一阶逻辑的推理定律的来源:
    1. 将命题逻辑的推理定律中的公式变为其代换实例.
    2. 由基本等值式生成推理定律 (24 条 + 换名规则).
    3. 量词分配蕴涵式:
23. 一阶逻辑的推理规则:
    1. 前提引入, 结论引入, 合取引入.
    2. 推理定律.
    3. 全称量词消去 (UI): 或 , 其中 不能在 中约束出现.
    4. 全称量词引入 (UG): , 其中 不能在 中约束出现.
    5. 存在量词引入 (EG): , 其中 不能在 中出现.
    6. 存在量词消去 (EI): , 其中 除 外没有其他自由出现的个体变项. 这里 表示 “为了对 应用 EI 而专门创造的个体常项”. “专门创造” 的设定的效果是禁止对另一公式 应用 EI 而引入 .

       例 5. 证明下面的推理:
       (1) 前提: , .
       结论: .
       (2) 前提: , .
       结论: .
       (3) 前提: .
       结论: .
       证 (1)
       [1] (前提引入)
       [2] ([1] EI)
       [3] (前提引入)
       [4] ([3] UI)
       [5] ([2] 化简)
       [6] ([4][5] 假言推理)
       [7] ([2] 化简)
       [8] ([6][7] 合取)
       [9] ([8] EG)
       (2)
       [1] (前提引入)
       [2] ([1] 置换)
       [3] ([2] 置换)
       [4] ([3] UI)
       [5] (前提引入)
       [6] ([5] UI)
       [7] ([6][4] 假言三段论)
       [8] ([7] UG)
       (3)
       [1] (前提引入)
       [2] ([1] 置换)
       [3] ([2] 置换)
       [4] ([3] 置换)
       [5] ([4] UI)
       [6] ([5] UI)
       [7] ([6] UG)