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

《数理逻辑与集合论》复习提纲第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归结推理法会运用等值式证明两个公式是否相等、判断公式的类型求命题公式的对偶式、(主)析取范式、(主)合取范式及用途常用推理规则、直接证明法、附加前提证明法、归结法第5章谓词逻辑的等值和推理演算

5.1否定型等值式（证明）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有限集合的基数包含排斥原理及应用（作业）会运用集合运算的性质证明有关集合运算的命题成立与否、进行化简，定理证明主要在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偏序关系(会画哈斯图，求特殊元素)对称闭包、自反闭包和传递闭包的定义和构造方法第11章函数11.1函数11.2函数的合成和函数的逆第12章集合的基数12.2集合的等势12.3有限集合与无限集合12.4集合的基数《数理逻辑》试题样卷一.选择题（10%）1．设S、T、M为任意集合，则下列命题中，命题真值是真的是

。A．是的子集B.

若S－T=，则S=T

C．若~S∪T=E，则S∩T≠

D.

若S∪T=S∪M，则T=M二.填空题：（20%）1、公式(pq)r的成真赋值是______________《数理逻辑》试题样卷四.运算题：（20%）1.用等值演算法判断公式q(pq)的类型解q(pq)

q(pq)（蕴涵等值式）

q(pq)（德摩根律）

p(qq)（交换律，结合律）

p0（矛盾律）

0（零律）由最后一步可知，该式为矛盾式.2.计算集合A={，{}}的幂集解：P(A)=P({,{}})={,{},{{}},{,{}}}《数理逻辑》试题样卷六.应用题：（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)①③假言推理考试和答疑安排考试时间：18周星期五(12月31日)，8:00-10:00AM考试地点：340402答疑安排：18周星期三(12月29日)，3:00-5:00答疑地点：31号楼3楼教师休息室《数理逻辑》样卷一、单选题（共10分）1．下列命题公式中，是重言式的是____________。A．(pq)qB.(pq)(pq)C.p∧qD.pq2．设A、B、C、D为任意集合，下面命题为真的是____________。A．A－(B∪C)＝(A－B)∩(A－C)B.若AB，则有~A~BC.~(A∪B)=~A∪~BD.~(A∩B)=~A∩~B3．在关于二元关系性质的叙述中，正确的是__________。A.若关系R、S具有自反性，则R∩S一定有自反性；B.存在既是对称的也是反对称的关系C.若R、S是传递的，则R∪S也是传递的；D.若R、S是自反的，则R－S也是自反的。4．含有3个元素的集合共有_______种不同的划分.A.4B.10C.5D.65．设A、B为任意集合，下面命题为真的是__________。A．P(A)∪P(B)=P(A∪B)B.P(A∩B)=P(A)∩P(B)P(A-B)=P(A)-P(B)若A-B=

，则BA《数理逻辑》样卷二、填空题（共20分）1．设p、q的真值为0；r的真值为1，则命题公式：p∨(q∧r)的真值是______________。2．设论域为{1,2}，一元谓词定义为F(x):x>2,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．在偏序关系<P({a,b,c,d},R)>的哈斯图中，最大元素是_______，极小元素是___________。《数理逻辑》样卷二、填空题（共20分）6．两个集合A和B相等(A=B)用谓词形式可定义为：_____________。7．已知集合C定义为：C={x|xZ3x6}，则集合C中的元素为：C=___________________。8.若|A|=n，则A上共有__________个不同的具有自反性的二元关系。9．用联系词↑表示公式P

Q＝________________________。10．对集合A＝{1,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上的等价关系与划分是一一对应的。

（）5．集合的最小元就是它的极小元；（）6．已知：f(x)=2x+1，则f既不是单射也不是满射。（）7．若关系R是等价关系，则它必是相容关系。（）8．实数R与自然数N是不等势的。（）9．任给二元函数f,它的逆f1一定是二元函数关系。（）10．对公式A和B，若A→B永真，必有A-→B-也永真。（）《数理逻辑》样卷五．证明题（共20分）1．用等值演算法证明等值式：

PQ=P(PQ)2.设q为命题变项，与个体变元x无关，证明：(x)(P(x)∨q)=(x)P(x)∨q3.设A={1,2,3,4,5,6,7,8},A上的关系R如下定义：

R={<x,y>|x,y∈A∧x≡y(mod3)}

证明：R是一个等价关系。4．使用推理规则证明：

P(QR)，S∨P,Q

S

R《数理逻辑》样卷六．应用题（共20分）1.甲、乙、丙、丁四人参加