第 1 章 基础 -- 逻辑和证明
# 第 1 章 基础: 逻辑和证明
# 1.1 命题逻辑
# 1.1.1 引言
# 1.1.2 命题
笔记
- 命题的定义
- 命题的否定、合取、析取与异或
- 联结词的定义
# 1.1.3 条件语句
笔记
- 条件语句也被称为蕴含
- 前提为假时,整个语句为真
- 逆命题、逆否命题与反命题
- 双条件语句,"当且仅当"
# 1.1.4 复合命题的真值表
# 1.1.5 逻辑运算符的优先级
笔记
运算符 | 优先级 |
---|---|
1 | |
2 | |
3 | |
4 | |
5 |
# 1.1.6 逻辑运算和比特运算
笔记
- 位运算可以扩展到比特串上
# 1.2 命题逻辑的应用
# 1.2.1 引言
# 1.2.2 语句翻译
笔记
- 将语句翻译为复合命题可以消除歧义
# 1.2.3 系统规范说明
笔记
- 生成精确而无二义性的规范说明
# 1.2.4 布尔搜索
# 1.2.5 逻辑谜题
# 1.2.6 逻辑电路
# 1.3 命题等价式
# 1.3.1 引言
笔记
- 数学证明中一个重要步骤就是用真值相同的一条语句替换另一条语句
# 1.3.2 逻辑等价式
# 1.3.3 德·摩根率的应用
# 1.3.4 构造新的逻辑等价式
# 1.3.5 可满足性
# 1.3.6 可满足性的应用
例 10 n 皇后问题
- 推导中有部分错误
- 对角线部分的按照斜率为 1 或 -1 来确定
- 每格有皇后可以做为一个单独的命题,问题最终可转化为
个命题组成的复合命题
# 1.3.7 可满足性问题的求解
# 1.4 谓词和量词
# 1.4.1 引言
笔记
- 谓词逻辑比一般的命题逻辑表达能力更强
# 1.4.2 谓词
笔记
- 谓词相当于引入了变量,不再像命题那样具有确定的真值
- 只有变量确定后,才能确定的真值
# 1.4.3 量词
笔记
- 量词量化的表示在何种程度上谓词对于一定范围内的个体成立
- 当使用量词时,指定论域是必需的
唯一性量词
- 可以用全称量词
和存在量词 以及命题逻辑来表达唯一性,因此唯一性量词可省略 - 参见 例 12 (P55)
# 1.4.4 有限域上的量词
# 1.4.5 受限域上的量词
# 1.4.6 量词的优先级
笔记
- 量词比命题演算中的所有逻辑运算符都具有更高的优先级
# 1.4.7 绑定变量
# 1.4.8 涉及量词的逻辑等价式
# 1.4.9 量化表达式的否定
量词的德·摩根率
- P41
# 1.4.10 语句到逻辑表达式的翻译
笔记
表示,对于任意的 ,要么 为假,要么 为真且 为真
# 1.4.11 系统规范说明中量词的使用
# 1.4.12 选自路易斯·卡罗尔的例子
# 1.4.13 逻辑程序设计
# 1.5 嵌套量词
# 1.5.1 引言
笔记
- 嵌套量词,即一个量词出现在另一个量词的作用域内
# 1.5.2 理解涉及嵌套量词的语句
将量化当做多层循环
- 可以方便理解
# 1.5.3 量词的顺序
# 1.5.4 数学语句到嵌套量词语句的翻译
# 1.5.5 嵌套量词到自然语言的翻译
# 1.5.6 汉语语句到逻辑表达式的翻译
# 1.5.7 嵌套量词的否定
# 1.6 推理规则
# 1.6.1 引言
# 1.6.2 命题逻辑的有效论证
# 1.6.3 命题逻辑的推理规则
笔记
- P64 常用的推理规则
注意
- 证明永真式是证明公式的整体为真,而不是证明由蕴含式的左端可以推导出右端
- 每个推理规则均对应一个永真式
# 1.6.4 使用推理规则建立论证
# 1.6.5 消解率
# 1.6.6 谬误
笔记
- 错将可满足式当成永真式
- 肯定结论的谬误
- 否定假设的谬误
# 1.6.7 量化命题的推理规则
# 1.6.8 命题和量化命题推理规则的组合使用
# 1.7 证明导论
# 1.7.1 引言
形式化证明与非形式化证明
# 1.7.2 一些专业术语
# 1.7.3 理解定理是如何陈述的
# 1.7.4 证明定理的方法
# 1.7.5 直接证明法
# 1.7.6 反证法
笔记
- 反证法借助逆否命题来证明
#
空证明和平凡证明
# 1.7.7 归谬证明法
- 反证法可以改可为归谬证明
等价证明法
#
证明一组命题等价
反例证明法
# 1.7.8 证明中的错误
肯定结论
否定假设
窃取论题
# 1.8 证明的方法和策略
# 1.8.1 引言
# 1.8.2 穷举证明法和分情形证明法
不失一般性
# 1.8.3 存在性证明
# 1.8.4 唯一性证明
需要证明存在性与唯一性
# 1.8.5 证明策略
正向和反向推理
改编现有证明
# 1.8.6 寻找反例
# 1.8.7 证明策略实践
# 1.8.8 拼接
# 1.8.9 开放问题的作用
# 1.8.10 其它证明方法
编辑 (opens new window)