交大数理逻辑课件数理逻辑和集合论复习提纲.ppt

《交大数理逻辑课件数理逻辑和集合论复习提纲.ppt》由会员分享，可在线阅读，更多相关《交大数理逻辑课件数理逻辑和集合论复习提纲.ppt（22页珍藏版）》请在装配图网上搜索。

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 否定型等值式（证明） 5.2 量词分配等值式（证明） 5.4 基本的推理公式(证明方法，(1)-(10):P77-78) 5.5 推理演算(UI,EI,UG,EG和命题推理规则) 5.6 谓词逻辑

3、的归结推理法,量词否定等值式、量词辖域收缩和扩张等值式、量词分配等值式、消去量词等值式,第9章 集 合,9.1 集合的概念和表示方法 9.2 集合间的关系和特殊集合 9.3 集合的运算 9.4 集合的图形表示法 9.5 集合运算的性质和证明(9.5.3不包括) 9.6 有限集合的基数 包含排斥原理及应用（作业）,会运用集合运算的性质证明有关集合运算的命题成立与否、进行化简，定理证明主要在9.5.1，9.5.4，而9.5.2只要记住结论,第10章 关 系,10.1 二元关系重要关系(、E、I、L、D、) 10.2 关系矩阵和关系图 10.3 关系的逆、合成、限制和象 10.4 关系的性质(性质判

4、断和证明) 10.5 关系的闭包 10.6 等价关系和划分( 会求商集、类、划分并会证明) 10.7 相容关系和覆盖( 会求类并会证明) 10.8 偏序关系(会画哈斯图，求特殊元素),对称闭包、自反闭包和传递闭包的定义和构造方法,第11章 函 数,11.1 函数 11.2 函数的合成和函数的逆,第12章 集合的基数,12.2 集合的等势 12.3 有限集合与无限集合 12.4 集合的基数,试题结构,卷面 一. 选择题（10%） 二. 填空题（20%） 三. 判断题（10%） 四. 运算题（20%） 五. 证明题（20%） 六. 应用题（20%）,各章内容比例 第一、二章 命题逻辑 (20%)

5、第四、五章 谓词逻辑 (20%) 第九章 集合 (20%) 第十章 关系 (25%) 第十一章 函数 (10%) 第十二章 集合的基数 (5%),数理逻辑试题样卷,一. 选择题（10%） 1设S、T、M为任意集合，则下列命题中，命题真值是真的是 。 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) （交换律，结合律）

6、p0 （矛盾律） 0 （零律） 由最后一步可知，该式为矛盾式. 2.计算集合A= ，的幂集 解：P(A)=P(, ) = , , , , ,数理逻辑试题样卷,三.判断题（10%） 设S、T为任意集合， 若ST= ，则S=T 。（） 五. 证明题（20%） 证明 A=B C=D AC=BD 证： 任取 AC xA yC xB yD BD,数理逻辑试题样卷,六.应用题：（20%） 证明苏格拉底三段论: “人都是要死的, 苏格拉底是人，所以苏格拉底是要死的.” 令 F(x): x是人, G(x): x是要死的, a: 苏格拉底 前提：x(F(x)G(x)，F(a) 结论：G(a) 证明： F(a)

7、前提引入 x(F(x)G(x) 前提引入 F(a)G(a) UI G(a) 假言推理,考试和答疑安排,考试时间： 18周星期五(12月31日)，8:00-10:00AM 考试地点：340402 答疑安排： 18周星期三(12月29日)，3:00-5:00 答疑地点：31号楼3楼教师休息室,数理逻辑样卷,一、单选题（共10分） 1下列命题公式中，是重言式的是_。 A (p q) q B. (p q) (p q) C. pq D. p q 2设A、B、C、D为任意集合，下面命题为真的是_。 AA(BC)(AB)(AC) B. 若AB，则有A B C. (AB)= AB D. (A B)= A B,

8、3在关于二元关系性质的叙述中，正确的是_。 A. 若关系R、S具有自反性，则RS一定有自反性； B. 存在既是对称的也是反对称的关系 C. 若R、S是传递的，则RS也是传递的； D. 若R、S是自反的，则RS也是自反的。 4含有3个元素的集合共有_种不同的划分. A. 4 B. 10 C. 5 D. 6 5设A、B为任意集合，下面命题为真的是_。 AP(A)P(B)=P(AB) B. P(AB)=P(A)P(B) P(A-B)=P(A)-P(B) 若A-B= ，则B A,数理逻辑样卷,8下列一阶谓词公式中，是逻辑有效式的是_。 x(F(x) G(x) xF(x) xF(x) C. (F(x,y

9、) R(x,y) R(x,y) D. xyF(x,y) xyF(x,y) 9设 f：BC, g：AB. 则下面命题是错误的是_。 A. 若 fg是满射.则f 是满射的 B. 若 fg是单射.则g是单射的 C. 若 fg是双射.则f 是单射的， g 是满射的。 D. 若 fg是双射.则 g是单射的， f 是满射的。 10下列关系的性质中，等价关系不具备的是_。 A自反的 B. 反对称的 C. 传递的 D. 对称的,6设A、B是集合，右图的文氏图的阴影部分的区域可用_表达式表示 A. AB B. AB A-B D. (AB)-(AB) 7集合A和B定义如下，则它们之间满足_关系。 A=x|xRx2

10、+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在偏序关系的哈斯图中，最大元素是_，极小元素是_。,数理逻辑样卷,二、填

11、空题（共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是自反的，则R1R2也是自反的。（ ） 3对任意的集合A、B，若 P(A) P(B)，则 AB （ ） 4集合A上的等价关系与划分

12、是一一对应的。（ ） 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)和传递闭包t(

13、R)。 4. 设f,g,h均为R-R的函数，f(x)=x+3, g(x)=2x+1, h(x)=x/2, 求gf, gh, gfh,数理逻辑样卷,五证明题（共20分） 1用等值演算法证明等值式： PQ = P (P Q) 2. 设q为命题变项，与个体变元x无关，证明： (x)(P(x)q) = (x)P(x) q 3.设 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上所有的等价关系,