数理逻辑和集合论复习提纲2014

1、数理逻辑复习提纲2014.12.第1章 命题逻辑的基本概念 1.2 命题联结词及真值表u 联结词的优先顺序为：联结词的优先顺序为： , , , , 1.3 合式公式u 合法性判断合法性判断(P7-8)1.4 重言式u 公式的类型及它们之间的关系公式的类型及它们之间的关系(P8)1.5 命题形式化第2章 命题逻辑的等值和推理演算 2.2 等值公式 (P15-18)u 会运用常用等值公式证明两个公式是否相等、会运用常用等值公式证明两个公式是否相等、判断公式的类型判断公式的类型2.3 命题公式与直值表的关系u 会按真值表列出命题公式会按真值表列出命题公式 AB = A B PQ=(P Q) (QP)

2、=(P Q) ( PQ)=(PQ) ( P Q) (A B) = AB (A B) = AB第2章 命题逻辑的等值和推理演算 2.4 联结词的完备集u n元命题公式的个数，元命题公式的个数，连结词连结词( 、 )的性质的性质2.5 对偶式定理2.5.1-2.5.6 2.6 范式u 求主析求主析(合合)取范式和成真、成假赋值及应用取范式和成真、成假赋值及应用2.8 基本的推理公式（P31: -）2.9 推理演算u 常用推理规则常用推理规则, 直接证明法、附加前提证明法直接证明法、附加前提证明法2.10 归结推理法第4章 谓词逻辑的基本概念 4.2 函数和量词u 量词及使用，量词及使用，自由变元、

3、约束变元自由变元、约束变元4.3 合式公式（合法性判断）4.4 自然语句的形式化（与作业结合复习）4.5 有限域下公式(x)P(x)、(x)P(x)的表示法u 有限论域下公式的表示法有限论域下公式的表示法u 在域在域1,2上的量化公式、解释上的量化公式、解释第5章 谓词逻辑的等值和推理演算 5.1 否定型等值式（P69-70: 证明）证明）5.2 量词分配等值式（P71-73: 证明）证明）u量词对量词对、 和和的分配律的分配律 u量词量词 对对的分配律，量词的分配律，量词 对对的分配律的分配律5.3 范式 (前束范式、含词Skolem标准形)5.4 基本的推理公式(证明方法，P77-78:

4、-)5.5 推理演算u与与量词有关的推理规则和命题推理量词有关的推理规则和命题推理规则规则5.6 谓词逻辑的归结推理法第9章 集 合9.1 集合的概念和表示方法(N,Z,Q,R)9.2 集合间的关系和特殊集合u 集合间关系的谓词表示集合间关系的谓词表示9.3 集合的运算u 集合运算的谓词表示集合运算的谓词表示, 幂集、笛卡儿积幂集、笛卡儿积9.4 集合的文氏图表示9.5 集合运算的性质和证明(9.5.3除外)9.6 有限集合的基数包含排斥原理及应用u 会运用集合运算的性质证明有关集合运算的命题成会运用集合运算的性质证明有关集合运算的命题成立与否、进行化简，定理证明主要在立与否、进行化简，定理证

5、明主要在9.5.1，9.5.4，而而9.5.2只要记住结论只要记住结论n 证明证明 X Y命题演算法命题演算法包含传递法包含传递法等价条件法等价条件法反证法反证法并交运算法并交运算法n 证明证明 X=Y命题演算法命题演算法等式代入法等式代入法反证法反证法运算法运算法第10章 关系n10.1 二元关系 u 重要重要关系关系(、E、I I、L、D、 )，定义域和值域，定义域和值域n10.2 关系矩阵和关系图n10.3 关系的运算u 逆逆、合成合成、限制和象、限制和象u 逆、合成运算的性质逆、合成运算的性质(P166-167)n10.4 关系的性质u 性质的谓词定义、判断、证明、充要条件性质的谓词定

6、义、判断、证明、充要条件u 性质运算后的保持性性质运算后的保持性第10章 关系n 10.5 关系的闭包u 闭包的定义、性质和构造方法闭包的定义、性质和构造方法n 10.6 等价关系和划分u 等价等价关系的定义、判断和证明关系的定义、判断和证明u 会会求商集求商集、等价类、等价类、划分划分n 10.7 相容关系和覆盖u 相容关系相容关系的定义、判断和的定义、判断和证明，会求最大相容类证明，会求最大相容类n 10.8 偏序关系u 偏序、拟序、全序关系偏序、拟序、全序关系的定义、判断和的定义、判断和证明证明u 会画会画哈斯图，特殊哈斯图，特殊元素，链、反链元素，链、反链试题结构卷面卷面一一. 选择题

7、（选择题（20%）二二. 填空题（填空题（20%）三三. 计算题计算题（20%）四四. 证明题（证明题（20%）五五. 应用题（应用题（20%）各章内容比例第一、二章 命题逻辑 (25%)第四、五章 谓词逻辑 (25%)第九章 集合 (20%)第十章 关系 (30%)数理逻辑试题样题一. 选择题（20%）1设A、B、C为任意集合，则下列命题中，是真命题是 。A若若A B=A C，则，则B=CB. 若若 AB = ，则，则A=B C若若A B=A C，则，则B=C D. 二二. 填空题填空题：（20%）1、 公式 (PQ) R的成真赋值是_数理逻辑试题样题三. 计算题：（20%） 1.用等值演算

8、法判断公式Q(PQ)的类型 解：解：Q(PQ) Q ( P Q) Q (P Q) P (Q Q) P F F 由最后一步可知，该式为由最后一步可知，该式为矛盾式矛盾式. . 2.计算集合A= ，的幂集n 解：解：P(A)=P(, ) =, , , , 数理逻辑试题样题四四. 证明题（证明题（20%） 证明证明 A=B C=D A C=B D n 证：证： 任取任取 A C x A y C x B y D B D 数理逻辑试题样题五.应用题：（20%）证明: “金属都是导电体, 铜是金属，所以铜是导电体。”解解：令令 F(x): x是是金属金属, G(x): x是导电体是导电体, a:铜铜 前提：前提： x(F(x)G(x)，F(a) 结论：结论：G(a) 证明