离散数学期末总复习

期末考试的题型：一、选择题：10题*2分二、填空题：5题*2分三、计算题：5题*9分四、证明题：2题*8分五、综合题：1题:9分第一局部

1、命题指真假唯一的陈述句。〔1〕否认“┐〞2、5个逻辑联结词及其真值表〔2〕合取“∧〞0001(3)析取“∨〞0111〔4〕蕴含“→〞1101只要p,就有q.p→qP仅当q.只有p,才q.除非p,才有q.除非p,否那么没有q.p→qq→pq→pq→p〔5〕等价“〞10013、真值表(大题)pqr010000100101100110101111011例1

写出真值表.0000011111110011111014.定义(1)假设A在它的任何赋值下均为真,那么称A为重言式或永真式;(2)假设A在它的任何赋值下均为假,那么称A为矛盾式或永假式;(3)假设A不是矛盾式,那么称A是可满足式.5.主析取范式与主合取范式〔大题〕相关知识点：〔1〕、等值式分配律A

(B

C)

(A

B)

(A

C),A

(B

C)

(A

B)

(A

C)蕴涵等值式A

B

A

B假言易位A

B

B

A〔2〕、析取范式与合取范式文字——命题变项及其否认的总称例如：p,q,r,

p,

q,

r…例如：p,

q,p

q,p

q

r,…例如：p,

q,p

q,p

q

r,…简单合取式——有限个文字构成的合取式简单析取式——有限个文字构成的析取式析取范式——由有限个简单合取式组成的析取式例如：p,

p

q,p

q,(p

q)(p

q

r)(q

r)合取范式——由有限个简单析取式组成的合取式例如：p,p

q,

p

q,(p

q)

p(p

q

r)范式——析取范式与合取范式的总称〔3〕、主析取范式与主合取范式在含有n个命题变项的简单合取式〔简单析取式〕中，假设每个命题变项和它的否认式恰好出现且仅出现一次，而且命题变项和它的否认式按下标从小到大或按字典顺序排列，称这样的简单合取式〔简单析取式〕为极小项(极大项).每个极小项只有一个成真赋值，用m表示；每个极大项只有一个成假赋值，用M表示。用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示.mi〔Mi〕称为极小项〔极大项〕的名称.主析取范式——由极小项构成的析取范式主合取范式——由极大项构成的合取范式

(2)假设某个Bj既不含pi,又不含pi,那么将Bj展开成BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单合取式都是长度为n的极小项为止(3)消去重复出现的极小项,即用mi代替mimi(4)将极小项按下标从小到大排列(1)求A的析取范式A

=B1

B2

…

Bs,其中Bj是简单合取式j=1,2,…,s求公式主析取范式的步骤:设公式A含命题变项p1，p2，…，pn例2(1)求公式A=(p

q)∨r的主析取范式解(p

q)

(p

q)

(

r

r)

(p

q

r)

(p

q

r)

m6

m7r

(

p

p)

(

q

q)

r

(

p

q

r)

(

p

q

r)

(p

q

r)

(p

q

r)

m1

m3

m5

m7所以A=(p

q)∨r

m1

m3

m5

m6

m7求公式的主合取范式的步骤:设公式A含命题变项p1,p2,…,pn(1)求A的合取范式A=B1B2…Bs,其中Bj是简单析取式j=1,2,…,s(2)假设某个Bj既不含pi,又不含pi,那么将Bj展开成BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单析取式都是长度为n的极大项为止(3)消去重复出现的极大项,即用Mi代替MiMi(4)将极大项按下标从小到大排列例3〔2〕求公式A=(pq)∨r的主合取范式A=(p

q)∨rp

r

(p

r)

(q

r)

(p

q

r)

(p

q

r)

p

(q

q)

r

M0

M2q

r

(p

p)

q

r

M0

M4

(p

q

r)

(

p

q

r)

A=(p

q)∨r

M0

M2

M46.联结词完备集设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，那么称S是联结词完备集.推论以下都是联结词完备集(1)S1={

,

,

,

}(2)S2={

,

,

,

,

}(3)S3={

,

}(4)S4={

,

}(5)S5={

,

}{,,,}不是联结词完备集,7.自然推理系统P〔大题〕

假言推理：A→BA∴B拒取式规那么：例4构造推理的证明。(课本54页18题)8、一阶逻辑命题符号化例5

将下面两个命题符号化:(1)凡人都呼吸.(2)有的人用左手写字.解:令M(x):

是人；F(x):x呼吸；G(x):x用左手写字.于是(1)，(2)的符号化形式分别为

(M(x)→F(x))(M(x)∧F(x))例6将以下命题符号化:

(1)有的兔子比所有的乌龟跑得快.

(2)并非兔子都比乌龟跑得快.解:令F(x):x是兔子.G(y):y是乌龟.H(x,y):x比y跑得快.这2个命题分别符号化为9、辖域、自由与约束

在公式

xA和

xA

中，称x为指导变元，A为相应量词的辖域.在

x和

x的辖域中,x的所有出现都称为约束出现.A中不是约束出现的其他变项均称为是自由出现的.例7指出以下各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项:x是指导变元.量词

x的辖域是F(x,y)→G(x,z)其中，x是约束出现的.y和z均为自由出现的.

x(F(x,y)

G(x,z))定义设A,B为集合,A与B的差运算定义如下:A–B＝{x|x∈A∧x∉B}

E差

A

B由定义可知A–B＝A-(A∩B)

1、集合的运算第二局部定义设A,B为集合,A与B的对称差集A⊕B,定义为A⊕B={x|x∈A∪B∧x

A∩B}也可定义为A⊕B=(A-B)∪(B-A)也可定义为A⊕B=(A∪B)-(A∩B)E对称差

A

B2、有穷集的计数〔大题〕例8某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球，6个会打网球的人都会打篮球或排球，求不会打球的人数。

蓝排网解：24351055所以不会打球的人数是5个人。3、关系的运算〔大题〕(1)R中所有有序对的第一元素构成的集合称为R的定义域(domain)，记为domR。(2)R中所有有序对的第二元素构成的集合称为R的值域(range)，记作ranR。(3)R的定义域和值域的并集称为R的域(field)，记作fldR。例如R={<1,2>,<1,3>,<2,4>,<4,3>},那么domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}〔4〕设F,G为二元关系，G对F的复合记作FG，其中FG=|<x,z>|y(<x,y>F<y,z>G)}例9

(课本131页16题)4、幂运算的性质定理设R是A上的关系,假设存在自然数s,t(s<t)使得Rs=Rt,那么(1)对任何k∈N有Rs+k=Rt+k(2)对任何k,i∈N有Rs+kp+i=Rs+i,其中p=ts例10、假设R3=R7,试化简R2023.解：由R3=R7可知p=7-3=4因此，2023=3+2023=3+4*502+2R2023=R3+2=R5.5、关系的性质设R为A上的关系,1．自反性与反自反性(1)假设x(x∈A→<x,x>∈R),那么称R在A上是自反的.(2)假设x(x∈A→<x,x>R),那么称R在A上是反自反.2．对称性与反对称性(1)假设xy(x,y∈A∧<x,y>∈R→<y,x>∈R),那么称R为A上对称的关系.(2)假设xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),那么称R为A上反对称的关系.3．传递性假设xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),那么称R是A上的传递关系.设R是非空集合A上的关系,R的自反〔对称或传递〕闭包是A上的关系R,使得R满足以下条件：〔1〕R是自反的〔对称的或传递的〕〔2〕RR〔3〕对A上任何包含R的自反〔对称或传递〕关系R有RR.一般将R的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).6、关系的闭包设R为非空集合上的关系.如果R是自反的、对称的和传递的,那么称R为A上的等价关系.7、等价关系〔大题〕A上的等价关系与A的集合划分是一一对应的.例11课本133页36题〔1〕例12A＝{1,2,3}上等价关系有多少个？解如以下图,做出A的所有划分：123123123123123因此A＝{1,2,3}上等价关系有5个.8、偏序关系〔1〕哈斯图〔大题〕特点：〔1〕每个结点没有环; 〔2〕两个连通的结点之间的序关系通过结点位置的上下表示，位置低的元素的顺序在前,即：假设x<y,那么x画在y的下层;〔3〕具有覆盖关系的两个结点之间连边.〔2〕最小元、最大元、极小元、极大元设<A,≼>为偏序集,BA,y∈B.〔1〕假设x(x∈B→y≼x)成立,那么称y为B的最小元.〔2〕假设x(x∈B→x≼y)成立,那么称y为B