1、数理逻辑与集合论复习提纲第1章 命题逻辑的基本概念 1.1 命题1.2 命题联结词及真值表1.3 合式公式1.4 重言式（三类公式的关系：P8）1.5 命题形式化1.6 波兰表达式第2章 命题逻辑的等值和推理演算 2.1 等值定理2.2 等值公式2.4 联结词的完备集PQ = (PQ)， PQ = (PQ)2.5 对偶式2.6 范式2.7 推理形式（重言蕴涵的几个结果：P31）2.8 基本的推理公式（(1)-(11):P31）2.9 推理演算2.10 归结推理法会运用等值式证明两个公式是否相等、判断公式的类型会运用等值式证明两个公式是否相等、判断公式的类型求命题公式的对偶式、求命题公式的对偶式
2、、(主主)析取范式、析取范式、(主主)合取范式及用途合取范式及用途常用推理规则、直接证明法、附加前提常用推理规则、直接证明法、附加前提证明法、归结法证明法、归结法第4章 谓词逻辑的基本概念 4.1 谓词和个体词4.2 函数和谓词4.3 合式公式（合法性判断）4.4 自然语句的形式化（与作业结合复习）4.5 有限域下公式(x)P(x)、(x)P(x)的表示法在在1,2上的量化公式、解释上的量化公式、解释谓词的定义，谓词逻辑与命题逻辑的关系谓词的定义，谓词逻辑与命题逻辑的关系自由变元、约束变元及量词的辖域自由变元、约束变元及量词的辖域第5章 谓词逻辑的等值和推理演算 5.1 否定型等值式（证明）（
3、证明）5.2 量词分配等值式（证明）（证明）5.4 基本的推理公式(证明方法，(1)-(10):P77-78)5.5 推理演算(UI,EI,UG,EG和命题推理规则)5.6 谓词逻辑的归结推理法量词否定等值式、量词辖域收缩和扩张等值量词否定等值式、量词辖域收缩和扩张等值式、量词分配等值式、消去量词等值式式、量词分配等值式、消去量词等值式第9章 集 合9.1 集合的概念和表示方法9.2 集合间的关系和特殊集合9.3 集合的运算9.4 集合的图形表示法9.5 集合运算的性质和证明(9.5.3不包括)9.6 有限集合的基数包含排斥原理及应用（作业）包含排斥原理及应用（作业）会运用集合运算的性质证明有
4、关集会运用集合运算的性质证明有关集合运算的命题成立与否、进行化简，合运算的命题成立与否、进行化简，定理证明主要在定理证明主要在9.5.1，9.5.4，而，而9.5.2只要记住结论只要记住结论第10章 关 系10.1 二元关系重要关系(、E、I、L、D、)10.2 关系矩阵和关系图10.3 关系的逆、合成、限制和象10.4 关系的性质(性质判断和证明)10.5 关系的闭包10.6 等价关系和划分( 会求商集、类、划分并会证明)10.7 相容关系和覆盖( 会求类并会证明)10.8 偏序关系(会画哈斯图，求特殊元素)对称闭包、自反闭包和传递闭包的定义和构造方法对称闭包、自反闭包和传递闭包的定义和构造
5、方法第11章 函 数11.1 函数11.2 函数的合成和函数的逆第12章 集合的基数12.2 集合的等势12.3 有限集合与无限集合12.4 集合的基数试题结构卷面卷面一一. 选择题（选择题（10%）二二. 填空题（填空题（20%）三三. 判断题（判断题（10%）四四. 运算题运算题（20%）五五. 证明题（证明题（20%）六六. 应用题（应用题（20%）各章内容比例第一、二章 命题逻辑 (20%)第四、五章 谓词逻辑 (20%)第九章 集合 (20%)第十章 关系 (25%)第十一章 函数 (10%)第十二章 集合的基数 (5%)数理逻辑试题样卷一. 选择题（10%）1设S、T、M为任意集合
6、，则下列命题中，命题真值是真的是 。A 是是的子集的子集B. 若若ST= ，则，则S=T C若若ST=E，则，则ST D. 若若ST=SM，则，则T=M二. 填空题：（20%）1、 公式 (pq) r 的成真赋值是_数理逻辑试题样卷四. 运算题：（20%） 1.用等值演算法判断公式q(pq)的类型 解 q(pq) q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律） 由最后一步可知，该式为由最后一步可知，该式为矛盾式矛盾式. . 2.计算集合A= ，的幂集n 解：P(A)=P(, ) = , , , , 数理逻辑试题样卷三.判断题
7、（10%）设设S、T为任意集合，为任意集合， 若若ST= ，则，则S=T 。（）。（）五. 证明题（20%） 证明 A=B C=D AC=BD 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) 证明：证明： F(a) 前提引入前提引入 x(F(x)G(x) 前提引入前提引入 F(a)G(a) UI G(a)
8、 假言推理假言推理 考试和答疑安排n考试时间：18周星期五周星期五(12月月31日日)，8:00-10:00AM考试地点：考试地点：340402n答疑安排： 18周星期三周星期三(12月月29日日)，3:00-5:00答疑地点：答疑地点：31号楼号楼3楼教师休息室楼教师休息室数理逻辑样卷一、单选题（共一、单选题（共10分）分）1下列命题公式中，是重言式的是_。 A (p q) q B. (p q) (p q) C. pq D. p q2设A、B、C、D为任意集合，下面命题为真的是_。AA(BC)(AB)(AC)B. 若AB，则有A BC. (AB)= AB D. (A B)= A B3在关于二
9、元关系性质的叙述中，正确的是_。A. 若关系R、S具有自反性，则RS一定有自反性；B. 存在既是对称的也是反对称的关系C. 若R、S是传递的，则RS也是传递的；D. 若R、S是自反的，则RS也是自反的。4含有3个元素的集合共有_种不同的划分. A. 4 B. 10 C. 5 D. 65设A、B为任意集合，下面命题为真的是_。AP(A)P(B)=P(AB) B. P(AB)=P(A)P(B)C. P(A-B)=P(A)-P(B) D. 若A-B= ，则B A数理逻辑样卷8下列一阶谓词公式中，是逻辑有效式的是_。A. x(F(x) G(x) B. xF(x) xF(x)C. (F(x,y) R(x
10、,y) R(x,y) D. xyF(x,y) xyF(x,y) 9设 f：BC, g：AB. 则下面命题是错误的是_。 A. 若 f g是满射.则f 是满射的 B. 若 f g是单射.则g是单射的 C. 若 f g是双射.则f 是单射的， g 是满射的。 D. 若 f g是双射.则 g是单射的， f 是满射的。10下列关系的性质中，等价关系不具备的是_。 A自反的 B. 反对称的 C. 传递的 D. 对称的6设A、B是集合，右图的文氏图的阴影部分的区域可用_表达式表示A. AB B. AB C. A-B D. (AB)-(AB) 7集合A和B定义如下，则它们之间满足_关系。 A=x|xRx2+
11、x-2=0, B=y|yQy2+y-2=0 AA=B BBA CAB DAB数理逻辑样卷二、填空题（共二、填空题（共20分）分）1设p、q的真值为0；r的真值为1，则命题公式：p (qr)的真值是_。2设论域为1,2，一元谓词定义为F(x): x2, G(x): x=0，则 (x)(F(x)G(x) 的真值为_。3设P(x)：x是正整数，Q(x)：x是偶数，R(x)：x是奇数，则公式： (x)(P(x) (Q(x)R(x)翻译成自然语句为: _。4设A=a, b, c，则A的全部子集共有_个，A的幂集P(A)共有_个元素。 5在偏序关系的哈斯图中，最大元素是_，极小元素是_。数理逻辑样卷二、填
12、空题（共二、填空题（共20分）分）6两个集合A和B相等(A=B)用谓词形式可定义为：_。7已知集合C定义为： C=x|x Z 3x6 ，则集合C中的元素为：C=_。8. 若|A|=n，则A上共有_ 个不同的具有自反性的二元关系。9用联系词表示公式 P Q_。10对集合A1,2,3，R是A上的关系，如 右图所示，列出它所具有的性质：_。数理逻辑样卷三判断题（三判断题（10分）分）1对非空集合A上的关系R，若R是自反的，则s(R)是自反的。（ ）2对A上的关系R1和R2，若R1和R2是自反的，则R1 R2也是自反的。（ ）3对任意的集合A、B，若 P(A) P(B)，则 AB （ ）4集合A上的等
13、价关系与划分是一一对应的。（ ）5集合的最小元就是它的极小元；（ ）6已知：f(x)=2x+1， 则f 既不是单射也不是满射。（ ）7若关系R是等价关系，则它必是相容关系。 （ ）8实数R与自然数N是不等势的。（ ）9任给二元函数f , 它的逆f 1一定是二元函数关系。（ ）10对公式A和B，若AB永真，必有A-B-也永真。（ ）数理逻辑样卷四运算题（四运算题（20分）分）1求命题公式： (PQ)R 的主析取范式和成真赋值。2. 已知A=1,2,3 ，B=1,4，求AB、A-B、AB和P(AB)。3. 设A=a, b, c, d，R=, , ，求R的自反闭包r(R)、对称闭包s(R)和传递闭包
14、t(R)。4. 设f,g,h均为R-R的函数，f(x)=x+3, g(x)=2x+1, h(x)=x/2, 求g f, g h, g f h数理逻辑样卷五证明题（共五证明题（共20分）分）1用等值演算法证明等值式： PQ = P (P Q)2. 设q为命题变项，与个体变元x无关，证明： (x)(P(x)q) = (x)P(x) q3.设 A=1,2,3,4,5,6,7,8, A上的关系 R如下定义： R = | x,yAxy(mod 3) 证明：R是一个等价关系。4使用推理规则证明： P(QR)，SP, Q S R数理逻辑样卷六应用题（共应用题（共20分）分）1. 甲、乙、丙、丁四人参加考试，有人问他们，谁的成绩最好，甲说：“不是我”,乙说：“是丁”,丙说：“是乙”,丁说：“不是我”.四人的回答只有一人符合实际，问是谁的成绩最好，若只有一人成绩最好，他是谁？2符号化下面命题，并用谓词逻辑构造其推证结论的过程： 乌鸦都不是白色的. 北京鸭是白色的. 因此，北京鸭不是乌鸦.3求1到1000之间（包含1和1000在内）既不能被 5 和6 整除，也不能被 8 整除的数有多少个？4.设 A=1,2,3，求出A上所有的等价关系
