第一篇:离散数学a卷魏霞
离散数学试题A卷
一、单项选择题(本大题共10小题,每小题2分,共20分)
1.下列命题公式中不是重言式的是() .
A.p→(q→r)
C.p→(p→p) B.p→(q→p) D.(p→(q→r))(q→(p→r))
2.设个体域是整数集,则下列命题的真值为真的是()
A.yx(x·y=1)
C.xy (x·y=y2) B.xy (x·y≠0) D.yx(x·y=x2)
3.关于谓词公式(x)(y)(P(x,y)∧Q(y,z))∧
(x)p(x,y),下面的描述中错误的是() ..
A.(x)的辖域是(y)(P(x,y)∧Q(y,z))
B.z是该谓词公式的约束变元
C.(x)的辖域是P(x,y) D.x是该谓词公式的约束变元
4.设有代数系统G=〈A,*〉,其中A是所有命题公式的集合,*为命题公式的合取运算,则G的幺元是()
A.矛盾式
C.可满足式 B.重言式 D.公式p∧q
5.设A={Ø},B=P(P(A)),以下不正确的式子是() .
A.{{Ø },{{Ø }},{Ø ,{Ø }}}包含于B
C.{{Ø ,{Ø }}}包括于B B.{{{Ø }}}包含于B D.{{Ø },{{Ø ,{Ø }}}}包含于B
6.设Z是整数集,E={…,-4,-2,0,2,4,…},f:Z→E,f(x)=2x,则f()
A.仅是满射
C.是双射 B.仅是入射 D.无逆函数
7.设A={1,2,3,4,5},A上二元关系R={〈1,2〉,〈3,4〉,〈2,2〉},S={〈2,4〉,〈3,1〉,〈4,2〉},则S-1R-1的运算结果是()
A.{〈4,1〉,〈2,3〉,〈4,2〉} C.{〈4,1〉,〈2,3〉,〈2,4〉}
B.{〈2,4〉,〈2,3〉,〈4,2〉} D.{〈2,2〉,〈3,1〉,〈4,4〉}
8.在实数集合R上,下列定义的运算中不可结合的是() .A.a*b=a+b+2ab C.a*b=a+b+ab
B.a*b=a+b D.a*b=a-b
9.设无向图中有6条边,有一个3度顶点和一个5度顶点,其余顶点度为2,则该图的顶点数是() A.3 C.
5B.4 D.6
10.设无向图G的边数为m,结点数为n,则G是树等价于() A.G连通且m=n+1 C.G连通且m=2n
B.G连通且n=m+
1D.每对结点之间至少有一条通路
二、填空题(本大题共10小题,每小题2分,共20分)
11.不能再分解的命题称为____________,至少包含一个联结词的命题称为____________。
12.在命题演算中,五个联结词的含义是由其____________表唯一确定的,而不是由其类似的____________
语言的含义确定。
13.使公式(x)(y)(A(x)→B(y))((x)A(x)→(y)B(y))成立的条件是____________
不含有y,____________不含有x。
14.设A为任意集合,请填入适当的运算符,使式子A____________A=Ø;A____________~A=Ø成立。 15.设A={0,1,2,3,6},R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod 3)},则domR=____________,
ranR=____________。
16.称集合S是给定非空集合A的覆盖:若S={S1,S2,…,Sn},其中SiA,Si≠Ø,i=1,2,…,n,
且____________;进一步若____________,则S是集合A的划分。
17.对实数的普通加法和乘法,____________是加法的幂等元,____________是乘法的幂等元。 18.在代数系统〈A,*〉中,A={a},*是A上二元运算,则该代数系统的单位元是____________,零元
是____________。
19.设〈A,≢〉是偏序集,若A中____________都有最小上界和____________则称A关于偏序≢构成格。 20.若一条路中,所有边均不相同,则此路称作____________;若一条路中所有的结点均不相同,则称此
路为____________。
三、计算题(本大题共5小题,每小题6分,共30分) 21.求命题公式(PQ)(PQ)的真值表。
22.试求谓词公式x(P(x)xQ(x,y)yR(x,y))A(x,y)中,x,x,y的辖域,试问R(x,y)和A(x,y)
中x,y是自由变元,还是约束变元?
23.求命题公式(p→q)→(q∨p)的主析取范式。
24.设代数系统(Z,*),其中Z是整数集,二元运算定义为a,bZ,a*bab2,aZ,求a的逆元。
25.已知图D(如下图)的邻接矩阵为
v1v2v3v
40
110
01
求从v2到v4长度为2和从v3到v3长度为2的通路条数,并将它们具体写出。
v10
A(D)=v21
v30v41
10 10
四、证明题(本大题共2小题,每小题6分,共12分)
26.设〈{a,b},*〉是半群,其中a*a=b,证明:(1)a*b=b*a;(2)b*b=b。
27.若一棵树恰有2个结点的度数为1,则它必是一条欧拉路。
五、应用题(本大题共3小题,每小题6分,共18分)
28.设I是整数集,<,>,=,≢,≣,≠是I上的二元关系,分别表示小于,大于、等于、小于等于,
大于等于,不等于,那么这些关系会满足什么性质?试填写下表。
29. 完成下列推理:只要今天天气不好,就一定有考生不能提前进入考场,当且仅当所有考生提前进入考场,考试才能准时进行。所以,如果考试准时进行,那么天气就好。
30.75个儿童到公园游乐场,他们在那里可以骑旋转木马,坐滑行铁道,乘宇宙飞船,已知其中20人这
三种东西都乘过,其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元,公园游乐场 总共收入70元,求有多少儿童没有乘坐过其中任何一种。
第二篇:离散数学考试试题(A卷及答案)
一、证明题(10分)
1) (P∧Q∧AC)∧(AP∨Q∨C) (A∧(PQ))C。P<->Q=(p->Q)合取(Q->p) 证明: (P∧Q∧AC)∧(AP∨Q∨C)
(P∨Q∨A∨C)∧(A∨P∨Q∨C)
((P∨Q∨A)∧(A∨P∨Q))∨C反用分配律
((P∧Q∧A)∨(A∧P∧Q))∨C
( A∧((P∧Q)∨(P∧Q)))∨C再反用分配律
( A∧(PQ))∨C
(A∧(PQ))C
2) (PQ) PQ。
证明:(PQ)((P∧Q))(P∨Q))PQ。
二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(QR))的主析取范式与主合取范式,并写出其相应的成真赋值和成假赋值(15分)。
主析取范式与析取范式的区别:主析取范式里每个括号里都必须有全部的变元。 主析取范式可由析取范式经等值演算法算得。
证明:
公式法:因为(P(Q∨R))∧(P∨(QR))
(P∨Q∨R)∧(P∨(Q∧R)∨(Q∧R))
(P∨Q∨R)∧(((P∨Q)∧(P∨R))∨(Q∧R))分配律
(P∨Q∨R)∧(P∨Q∨Q)∧(P∨Q∨R)∧(P∨R∨Q)∧(P∨R∨R)
(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)
M4∧M5∧M6使(非P析取Q析取R)为0所赋真值,即100,二进制
为
4m0∨m1∨m2∨m3∨m7
所以,公式(P(Q∨R))∧(P∨(QR))为可满足式,其相应的成真赋值为000、00
1、0
10、0
11、111:成假赋值为:100、10
1、110。
真值表法:
为000、00
1、0
10、0
11、111:成假赋值为:100、10
1、110。
三、推理证明题(10分)
1)P∨Q,Q∨R,RSPS。
证明:
(1)P附加前提 (2)P∨QP
(3)QT(1)(2),I(析取三段论) (4)Q∨RP
(5)RT(3)(4),I(析取三段论) (6)RSP
(7)ST(5)(6),I(假言推理) (8)PSCP
2) x(P(x)Q(y)∧R(x)),xP(x)Q(y)∧x(P(x)∧R(x))
证明(1)xP(x) (2)P(a)
(3)x(P(x)Q(y)∧R(x)) (4)P(a)Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)x(P(x)∧R(x))
(11)Q(y)∧x(P(x)∧R(x))
五、已知A、B、C是三个集合,证明(A∪B)-C=(A-C)∪(B-C) (10分)
证明:因为
x∈(A∪B)-Cx∈(A∪B)-C
x∈(A∪B)∧xC (x∈A∨x∈B)∧xC
(x∈A∧xC)∨(x∈B∧xC) x∈(A-C)∨x∈(B-C) x∈(A-C)∪(B-C)
所以,(A∪B)-C=(A-C)∪(B-C)。
八、证明整数集I上的模m同余关系R={|xy(mod m)}是等价关系。其中,xy(mod m)的含义是x-y可以被m整除(15分)。X(modm)=y(modm) 证明:1)x∈I,因为(x-x)/m=0,所以xx(mod m),即xRx。
2)x,y∈I,若xRy,则xy(mod m),即(x-y)/m=k∈I,所以(y - x)/m=-k∈I,所以yx(mod m),即yRx。
3)x,y,z∈I,若xRy,yRz,则(x-y)/m=u∈I,(y-z)/m=v∈I,于是(x-z)/m=(x-y+y-z)/m=u+v ∈I,因此xRz。
九、若f:A→B和g:B→C是双射,则(gf)-1=f-1g-1(10分)。
证明:
因为f、g是双射,所以gf:A→C是双射,所以gf有逆函数(gf):C→A。同理可推f-1g-1:C→A是双射。
因为∈f-1g-1存在z(∈g-1∈f-1)存在z(∈f∈g)∈gf∈(gf)-1,所以(gf)-1=f-1g-1。
-
1离散数学考试试题(B卷及答案)
一、证明题(10分)
1)((P∨Q)∧(P∧(Q∨R)))∨(P∧Q)∨(P∧R)T
证明: 左端((P∨Q)∧(P∨(Q∧R)))∨((P∨Q)∧(P∨R))(摩根律)
((P∨Q)∧(P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R))(分配律)
((P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R)) (等幂律)T (代入)
2) xy(P(x)Q(y))(xP(x)yQ(y)) 证明:xy(P(x)Q(y))xy(P(x)∨Q(y))
x(P(x)∨yQ(y)) xP(x)∨yQ(y) xP(x)∨yQ(y) (xP(x)yQ(y))
二、求命题公式(PQ)(P∨Q) 的主析取范式和主合取范式(10分)
解:(PQ)(P∨Q)(PQ)∨(P∨Q)
(P∨Q)∨(P∨Q) (P∧Q)∨(P∨Q)(P∨P∨Q)∧(Q∨P∨Q) (P∨Q)
M1析取要使之为假,即赋真值001,即M1 m0∨m2∨m3使之为真
三、推理证明题(10分)
1)(P(QS))∧(R∨P)∧QRS
证明:(1)R(2)R∨P (3)P
p
T(1)(2)析取三段论 p
T(3)(4)I假言推理 P
T(5)(6)I假言推理 CP
(4)P(QS) (5)QS(6)Q (7)S
(8)RS
2) x(A(x)yB(y)),x(B(x)yC(y))xA(x)yC(y)。
证明:(1)x(A(x)yB(y))P(2)A(a)yB(y)T(1)ES (3)x(B(x)yC(y))P
(4)x(B(x)C(c))T(3)ES (5)B(b)C(c)T(4)US (6)A(a)B(b)T(2)US
(7)A(a)C(c)T(5)(6)I假言三段论 (8)xA(x)C(c)T(7)UG (9)xA(x)yC(y)T(8)EG
四、只要今天天气不好,就一定有考生不能提前进入考场,当且仅当所有考生提前进入考场,考试才能准时进行。所以,如果考试准时进行,那么天气就好(15分)。
解 :
设P:今天天气好,Q:考试准时进行,A(e):e提前进入考场,个体域:考生的集
合,则命题可符号化为:PxA(x),xA(x)QQP。 (1)PxA(x)P (2)PxA(x)T(1)E (3)xA(x)PT(2)E(4)xA(x)QP (5)(xA(x)Q)∧(QxA(x))T(4)E (6)QxA(x)T(5)I (7)QPT(6)(3)I
五、已知A、B、C是三个集合,证明A∩(B∪C)=(A∩B)∪(A∩C) (10分)
证明:
∵ x A∩(B∪C) x A∧x(B∪C) x A∧(xB∨xC)( x A∧
xB)∨(x A∧xC) x(A∩B)∨x A∩C x(A∩B)∪(A∩C)∴A ∩(B∪C)=(A∩B)∪(A∩C)
六、A={ x1,x2,x3 },B={ y1,y2},R={,,},求其关系矩阵及关系图(10分)。有就是1,没就是0
七、设R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>},求r(R)、s(R)和t(R),并作出它们及R的关系图(15分)。
r(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,<3,3><5,5>}(自反闭包)
s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>}(对称闭包) t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}(传递
闭包)
九、设f:AB,g:BC,h:CA,证明:如果hgf=IA,fhg=IB,gfh=IC,则f、g、h均为双射,并求出f-
1、g-1和h-1(10分)。
解因IA恒等函数,由hgf=IA可得f是单射,h是满射;因IB恒等函数,由fhg=IB可得g是单射,f是满射;因IC恒等函数,由gfh=IC可得h是单射,g是满射。从而f、g、h均为双射。
由hgf=IA,得f-1=hg;由fhg=IB,得g-1=fh;由gfh=IC,得h-1=gf。
第三篇:离散数学例题
一、证明对任意集合A,B,C,有 a)A-B)-C=A-(B∪C); b)(A-B)-C=(A-C)-B;
c)(A-B)-C=(A-C)-(B-C)。
证明
a)(A-B)-C=(A∩~B)∩~C =A∩(~B∩~C) =A∩~(B∩C) =A-B∪C)
b)(A-B)-C= A∩~B∩~C = A∩~C∩~B =(A-C)-B
c)(A-C)-(B-C)
=(A∩~C)∩~(B∩~C) =(A∩~C)∩(~B∪C)
=(A∩~C∩~B)∪(A∩~C∩C) = A∩~B∩~C =(A-B)-C
二、设命题公式G = (P→Q)∨(Q∧(P→R)), 求G的主析取范式 G = (P→Q)∨(Q∧(P→R)) = (P∨Q)∨(Q∧(P∨R)) = (P∧Q)∨(Q∧(P∨R)) = (P∧Q)∨(Q∧P)∨(Q∧R) = (P∧Q∧R)∨(P∧Q∧∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧ R) = (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) = m3∨m4∨m5∨m6∨m7 = (3, 4, 5, 6, 7).
三、假设f和g是函数,证明f∩g也是函数。
证明
f∩g={| x∈dom f∧x∈dom g∧y=f(x)∧y=g(x)} ={| x∈dom f∩dom g∧y=f(x)=g(x)} 令h=f∩g,则
dom h={ x | x∈dom f∩dom g,f(x)=g(x)}
若y1 =y2 ,因为f是函数,故必有y1 =/f(x1 ),y2 =/f(x2 ),且x1 ≠x2 ,所以h=f∩g
是一个函数。
因为dom h存在且y1 ≠y2 时x1 ≠x2 ,即 h={| x∈ Dom h,y=h(x)=f(x)=g(x)}
四、设函数f:R→R,若x≤y=>f(x)≤f(y),则称函数f是单调递增的。设f和g是在R上单调递增,证明
1)若(f十g)(x)=f(x)+g(x),则f+g是单调递增; 2)复合函数f○g是单调递增:
3)f和g的乘积不一定是单调递增。
证明
1) 因为f和g是单调递增,若x≤y,则有f(x)≤f(y),g(x) ≤g (y), (f+g)(x)=f(x)十g(x) ≤f(y)+g(y)=(f十g)(y) 所以f+g是单调递增。
2)若x≤y,则f(x)≤f(y)且g(x) ≤ g(y),
f○g(x)=f(g(x)) ≤f(g(y))=f○g(y) 所以f○g是单凋递增。
3)令f(x)=g(x)=x,则f和g是单调递增,但其积函数
g*g(x)=f(x)*g(x)=x2 在R上不是单凋递增。
五、设R和S是集合A={a, b, c, d}上的关系,其中R={(a, a),(a, c),(b, c),(c, d)},
S={(a, b),(b, c),(b, d),(d, d)}.
计算R•S, R∪S, R- 1, S- 1•R- 1.
R•S={(a, b),(c, d)},
R∪S={(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R- 1={(a, a),(c, a),(c, b),(d, c)}, S- 1•R- 1={(b, a),(d, c)}.
六、若f:A→B是双射,则f-1 :B→A是双射。
证明
因为f:A→B是双射,则f-1 是B到A的函数。下证f-1是双射。
对任意x∈A,必存在y∈B使f(x)=y,从而f-1 (y)=x,所以f-1 是满射。 对任意的y
1、y2∈B,若f-1 (y1)=f-1 (y2)=x,则f(x)=y1,f(x)=y2。因为f:A→B 是函数,则y1=y2。所以f-1 是单射。 综上可得,f-1 :B→A是双射。
七、设函数g:A→B,f:B→C,则: (1)f。g是A到C的函数;
(2)对任意的x∈A,有fg(x)=f(g(x))。
证明
(1)对任意的x∈A,因为g:A→B是函数,则存在y∈B使∈g。对于y∈B,因f:B→C是函数,则存在z∈C使∈f。根据复合关系的定义,由∈g和∈f得∈g*f,即∈。所以Df。g=A。
对任意的x∈A,若存在y
1、y2∈C,使得、∈fg=g*f,则存在t1使得∈g且∈f,存在t2使得∈g且∈f。因为g:A→B是函数,则t1=t2。又因f:B→C是函数,则y1=y2。所以A中的每个元素对应C中惟一的元素。
综上可知,f。g是A到C的函数。
(2) 对任意的x∈A,由g:A→B是函数,有∈g且g(x)∈B,又由f:B→C是函数,得∈f,于是∈g*f=f。g。又因f。g是A到C的函数,则可写为 f。g(x)=f(g(x))。
第四篇:离散数学
第一章
数学语言与证明方法
例1 设E={ x | x是北京某大学学生}, A,B,C,D是E的子集, A= { x | x是北京人},
B= { x | x是走读生}, C= { x | x是数学系学生},
D= { x | x是喜欢听音乐的学生}. 试描述下列各集合中学生的特征:
(AD) ~ C={ x | x是北京人或喜欢听音乐,但不是数学系学生} ~ AB={ x | x是外地走读生} (A-B) D={ x | x是北京住校生, 并且喜欢听音乐} ~ D ~ B={ x | x是不喜欢听音乐的住校生} 例3 证明: (1) AB=BA (交换律) 证 x
xAB
xAxB
(并的定义)
xBxA
(逻辑演算的交换律)
xBA
(并的定义) (2) A(BC)=(AB)(AC) (分配律) 证 x
xA(BC)
xA(xB xC)
(并,交的定义)
(xAxB)(xAxC)
(逻辑演算的分配律)
x(AB)(AC)
(并,交的定义) (3) AE=E (零律) 证 x
xAE
xAxE
(并的定义)
xA1
(全集E的定义)
1
(逻辑演算的零律)
xE
(全集E的定义) (4) AE=A (同一律) 证 x
xAE
xAxE
(交的定义)
xA1
(全集E的定义)
xA
(逻辑演算的同一律) 例4 证明 A(AB)=A (吸收律) 证 利用例3证明的4条等式证明
A(AB)
= (AE)(AB)
(同一律)
= A(EB)
(分配律)
= A(BE)
(交换律)
= AE
(零律)
= A
(同一律) 例5 证明 (A-B)-C=(A-C)-(B-C) 证
(A-C)-(B-C)
= (A ~C) ~(B ~C)
(补交转换律)
= (A ~C) (~B ~~C)
(德摩根律)
= (A ~C) (~B C)
(双重否定律)
= (A ~C ~B) (A ~C C)
(分配律)
= (A ~C ~B) (A )
(矛盾律)
= A ~C ~B
(零律,同一律)
= (A ~B) ~C
(交换律,结合律)
= (A – B) – C
(补交转换律) 例6 证明 (AB)(AC)= (BC)(AC))((AC)A 例7 设A,B为任意集合, 证明: (1) AAB 证 x xA xAxB
(附加律)
xAB
(2) ABA
证 x xAB xAxB
xA
(化简律) (3) A-BA
证 x xA-B xAxB
xA
(化简律) (4) 若AB, 则P(A)P(B) 证 x xP(A) xA
xB
(已知AB)
xP(B) 例8 证明 AB=AB-AB. 证
AB=(A~B)(~AB)
=(A~A)(AB)(~B~A)(~BB)
=(AB)(~B~A)
=(AB)~(AB)
=AB-AB 例3 若A-B=A, 则AB=
证 用归谬法, 假设AB, 则存在x,使得
xAB xAxB xA-BxB
(A-B=A)
xAxBxB xBxB,
矛盾 例4 证明
是无理数
证
假设
是有理数, 存在正整数n,m, 使得
=m/n,
不妨设m/n为既约分数. 于是m=n
, m2=2n2, m2是偶数, 从而m是偶数. 设m=2k, 得 (2k)2=2n2, n2=2k2, 这又得到n也 是偶数, 与m/n为既约分数矛盾. 例6 对于每个正整数n, 存在n个连续的正合数. 证
令x=(n+1)!
则 x+2, x+3,…, x+n+1是n个连续的正合数:
i | x+i,
i=2,3,…,n+1 例7 判断下述命题是真是假:
若AB=AC, 则B=C.
解
反例: 取A={a,b}, B={a,b,c}, C={a,b,d}, 有
AB=AC = {a,b} 但BC, 故命题为假. 例8 证明:对所有n1, 1+2+ … +n=n(n+1)/2 证
归纳基础. 当n=1时, 1=1(1+1)/2, 结论成立. 归纳步骤. 假设对n1结论成立, 则有
1+2+ … +n +(n+1)=n(n+1)/2 +(n+1)
(归纳假设)
= (n+1)(n+2)/2 得证当n+1时结论也成立. 例9 任何大于等于2的整数均可表成素数的乘积 证 归纳基础. 对于2, 结论显然成立. 归纳步骤. 假设对所有的k(2kn)结论成立, 要证结论 对n+1也成立. 若n+1是素数, 则结论成立; 否则n+1=ab, 2a,b
由12n-3< n和归纳假设, n-3分邮资可用4分和5分邮票组 成, 再加一张4分邮票即可得到n+1分邮资, 得证结论对n+1 也成立.
第2章
命题逻辑
例1 下列句子中那些是命题?
(1) 北京是中华人民共和国的首都. (2) 2 + 5 =8. (3) x + 5 > 3. (4) 你会开车吗?
(5) 2050年元旦北京是晴天. (6) 这只兔子跑得真快呀! (7) 请关上门! (8) 我正在说谎话. (1),(2),(5)是命题, (3),(4),(6)~(8)都不是命题
例2 将下列命题符号化.
(1) 王晓既用功又聪明. (2) 王晓不仅聪明,而且用功. (3) 王晓虽然聪明,但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解
(1) p∧q
(2) p∧q
(3) p∧q (4) 记 r:张辉是三好生, s:王丽是三好生,
r∧s (5) 简单命题,
记 t:张辉与王丽是同学 例3 将下列命题符号化 (1) 2或4是素数. (2) 2或3是素数. (3) 4或6是素数. (4) 元元只能拿一个苹果或一个梨. (5) 王晓红生于1975年或1976年. 解
(1) p∨r, 真值:1 (2)
p∨q, 真值: 1 (3) r∨s,真值: 0 (4) 记t:元元拿一个苹果,u:元元拿一个梨
(t∧u)∨(t∧u) (5) 记v:王晓红生于1975年,w:王晓红生于1976年
(v∧w)∨(v∧w) 又可形式化为
v∨w
例4 设p:天冷, q:小王穿羽绒服, 将下列命题符号化
(1) 只要天冷,小王就穿羽绒服. pq (2) 因为天冷,所以小王穿羽绒服.
pq
(3) 若小王不穿羽绒服,则天不冷.
qp 或 pq (4) 只有天冷,小王才穿羽绒服.
qp (5) 除非天冷,小王才穿羽绒服.
qp (6) 除非小王穿羽绒服,否则天不冷.
pq
(7) 如果天不冷,则小王不穿羽绒服.
pq 或 qp (8) 小王穿羽绒服仅当天冷的时候.
qp 例5 求下列复合命题的真值
(1) 2+2=4 当且仅当 3+3=6.
1 (2) 2+2=4 当且仅当 3是偶数.
0 (3) 2+2=4 当且仅当 太阳从东方升起.
1 (4) 2+2=5 当且仅当 美国位于非洲.
1 (5) f (x)在x0处可导的充要条件是它在 x0处连续.
0 例6 公式A=( p1 p2 p3 )(p1 p2)
000是成真赋值,
001是成假赋值
公式B= (pq)r
000是成假赋值,
001是成真赋值 例3 证明 p(qr) (pq)r 证
p(qr)
p(qr)
(蕴涵等值式)
(pq)r
(结合律)
(pq)r
(德摩根律)
(pq) r
(蕴涵等值式 例4 证明: p(qr)
(pq) r 方法一
真值表法(见例2)
方法二
观察法. 容易看出000使左边成真, 使右边成假. 方法三
先用等值演算化简公式, 再观察. 例5 用等值演算法判断下列公式的类型 (1) q(pq) 解
q(pq)
q(pq)
(蕴涵等值式)
q(pq)
(德摩根律)
p(qq)
(交换律,结合律)
p0
(矛盾律)
0
(零律) 该式为矛盾式. (2) (pq)(qp) 解
(pq)(qp)
(pq)(qp)
(蕴涵等值式)
(pq)(pq)
(交换律)
1 该式为重言式. (3) ((pq)(pq))r)
解
((pq)(pq))r)
(p(qq))r
(分配律)
p1r
(排中律)
pr
(同一律)
非重言式的可满足式.如101是它的成真赋值,000是它的 成假赋值. 例1 求(pq)r 的析取范式与合取范式 解
(pq)r
(pq)r
(pq)r
析取范式
(pr)(qr)
合取范式 注意: 公式的析取范式与合取范式不惟一. 例1(续) 求(pq)r 的主析取范式与主合取范式 解 (1) (pq)r (pq)r
pq (pq)1
同一律
(pq)(rr)
排中律
(pqr)(pqr)
分配律
m4m5
r (pp)(qq)r
同一律, 排中律
(pqr)(pqr)(pqr)(pqr)
m0 m2 m4 m6
得
(pq)r m0 m2 m4 m5 m6 可记作
(0,2,4,5,6) (2) (pq)r (pr)(qr)
pr p0r
同一律
p(qq)r
矛盾律
分配律
(pqr)(pqr)
分配律
M1M3
qr (pp)qr
同一律, 矛盾律
(pqr)(pqr)
分配律
M3M7 得
(pq)r M1M3M7 可记作
(1,3,7) 例2 (1) 求 A (pq)(pqr)r的主析取范式 解 用快速求法
(1) pq (pqr)(pqr) m2 m3
pqr m1
r (pqr)(pqr)(pqr)(pqr)
m1 m3 m5 m7 得
A m1 m2 m3 m5 m7 (1,2,3,5,7) (2) 求 B p(pqr)的主合取范式
解 p (pqr)(pqr)(pqr)(pqr)
M4M5M6M7
pqr M1 得
B M1M4M5M6M7 (1,4,5,6,7) 例3 用主析取范式判断公式的类型: (1) A (pq)q
(2) B p(pq)
(3) C (pq)r 解 (1) A ( pq)q ( pq)q 0
矛盾式 (2) B p(pq) 1 m0m1m2m3
重言式 (3) C (pq)r (pq)r
(pqr)(pqr)(pqr)
(pqr)(pqr)(pqr)
m0m1m3 m5m7
非重言式的可满足式 例4 用主析取范式判断下面2组公式是否等值: (1) p与(pq)(pq) 解
p p(qq) (pq)(pq) m2m3
(pq)(pq) (pq)(pq)
(pq)(pq) m2m3 故
p (pq)(pq) (2) (pq)r 与 p(qr) 解 (pq)r (pqr)(pqr)
(pqr)(pqr)(pqr)(pqr)
m1m3m5 m6m7
p(qr) (pq)(p r)
(pqr)(pqr)(pqr)(pqr)
m5 m6m7 故
(pq)r
p(qr) 例5 某单位要从A,B,C三人中选派若干人出国考察, 需满 足下述条件: (1) 若A去, 则C必须去; (2) 若B去, 则C不能去; (3) A和B必须去一人且只能去一人. 问有几种可能的选派方案? 解
记p:派A去, q:派B去, r:派C去
(1) pr,
(2) qr,
(3) (pq)(pq) 求下式的成真赋值
A=(pr)(qr)((pq)(pq)) 例6 求A=(pqr)(pqr)(pqr)的主合取范式 解
A m1m3m7
M0M2M4M5M6 例1 判断下面推理是否正确: (1) 若今天是1号, 则明天是5号. 今天是1号. 所以, 明天是5号.
解
设 p: 今天是1号, q: 明天是5号
推理的形式结构为
(p®q)Ùp®q 证明
用等值演算法
(p®q)Ùp®q
Û Ø((ØpÚq)Ùp)Úq
Û ((pÙØq)ÚØp)Úq
Û ØpÚØqÚq Û 1 得证推理正确
(2) 若今天是1号, 则明天是5号. 明天是5号. 所以, 今天是1号. 解
设p: 今天是1号, q: 明天是5号. 推理的形式结构为
(p®q)Ùq®p 证明
用主析取范式法
(p®q)Ùq®p
Û (ØpÚq)Ùq®p
Û Ø ((ØpÚq)Ùq)Úp
Û ØqÚp
Û (ØpÙØq)Ú(pÙØq)Ú (pÙØq)Ú(pÙq)
Û m0Úm2Úm3
01是成假赋值, 所以推理不正确. 例2 在自然推理系统P中构造下面推理的证明: 前提: pÚq, q®r, p®s, Øs 结论: rÙ(pÚq) 证明 ① p®s
前提引入
② Ø s
前提引入 ③ Ø p
①②拒取式 ④ pÚq
前提引入
⑤ q
③④析取三段论
⑥ q®r
前提引入
⑦ r
⑤⑥假言推理 ⑧ rÙ(pÚq)
⑦④合取 推理正确, rÙ(pÚq)是有效结论
例3 构造推理的证明: 若明天是星期一或星期三, 我就有 课. 若有课, 今天必需备课. 我今天下午没备课. 所以, 明天 不是星期一和星期三.
解 设 p:明天是星期一, q:明天是星期三,
r:我有课,
s:我备课 前提: (pÚq)®r, r®s, Øs 结论: ØpÙØq
例4 构造下面推理的证明: 前提: ØpÚq, ØqÚr, r®s 结论: p®s
证明 ① p
附加前提引入 ② ØpÚq
前提引入
③ q
①②析取三段论 ④ ØqÚr
前提引入
⑤ r
③④析取三段论
⑥ r®s
前提引入
⑦ s
⑤⑥假言推理 推理正确, p®s是有效结论 例5 构造下面推理的证明
前提: Ø(pÙq)Úr, r®s, Øs, p 结论: Øq
证明
用归缪法
① q
结论否定引入 ② r®s
前提引入 ③ Øs
前提引入 ④ Ør
②③拒取式 ⑤ Ø(pÙq)Úr
前提引入
⑥ Ø(pÙq)
④⑤析取三段论 ⑦ ØpÚØq
⑥置换
⑧ Øp
①⑦析取三段论 ⑨ p
前提引入 ⑩ ØpÙp
⑧⑨合取 推理正确, Øq是有效结论
例6 用归结证明法构造下面推理的证明: 前提: (p®q)®r, r®s, Øs 结论: (p®q)®(pÙs) 解
(p®q)®r Û Ø(ØpÚq)Úr Û (pÙØq)Úr Û (pÚr)Ù(ØqÚr)
r®s Û ØrÚs
(p®q)®(pÙs) Û Ø(ØpÚq)Ú(pÙs) Û (pÙØq)Ú(pÙs)
Û pÙ(ØqÚs) 推理可表成
前提: pÚr, ØqÚr, ØrÚs, Øs 结论: pÙ(ØqÚs)
第3章 一阶逻辑 例1 (1) 4是偶数
4是个体常项, “是偶数”是谓词常项, 符号化为: F(4) (2) 小王和小李同岁
小王, 小李是个体常项, 同岁是谓词常项. 记a:小王,
b: 小李, G(x,y): x与y同岁, 符号化为: G(a,b) (3) x< y
x,y是命题变项, < 是谓词常项, 符号化为: L(x,y) (4) x具有某种性质P
x是命题变项, P是谓词变项, 符号化为: P(x) 例2 将下述命题用0元谓词符号化, 并讨论它们的真值: (1)
是无理数, 而
是有理数 (2) 如果2>3,则3<4 解
(1) 设F(x): x是无理数, G(x): x是有理数 符号化为 真值为0 (2) 设 F(x,y): x>y, G(x,y): x
个体域分别取(a) 人类集合, (b) 全总个体域 . 解: (a) (1) 设F(x): x爱美,
符号化为 x F(x)
(2) 设G(x): x用左手写字,
符号化为 x G(x)
(b) 设M(x): x为人, F(x), G(x)同(a)中
(1) x (M(x)F(x))
(2) x (M(x)G(x)) M(x)称作特性谓词
例4 将下列命题符号化, 并讨论其真值: (1) 对任意的x, 均有x2-3x+2=(x-1)(x-2) (2) 存在x, 使得x+5=3 分别取(a) 个体域D1=N, (b) 个体域D2=R 解 记F(x): x2-3x+2=(x-1)(x-2), G(x): x+5=3 (a) (1) x F(x)
真值为1
(2) x G(x)
真值为0 (b) (1) x F(x)
真值为1
(2) x G(x)
真值为1 例5 将下面命题符号化: (1) 兔子比乌龟跑得快
(2) 有的兔子比所有的乌龟跑得快 (3) 并不是所有的兔子都比乌龟跑得快 (4) 不存在跑得一样快的兔子和乌龟
解
用全总个体域,
令F(x): x是兔子, G(y): y是乌龟,
H(x,y): x比y跑得快,
L(x,y): x和y跑得一样快 (1) xy(F(x)G(y)H(x,y)) (2) x(F(x)(y (G(y)H(x,y))) (3) xy(F(x)G(y)H(x,y)) (4) xy(F(x)G(y)L(x,y)) 例6 公式 x(F(x,y)yG(x,y,z)) x的辖域:(F(x,y)yG(x,y,z)), 指导变元为x y的辖域:G(x,y,z), 指导变元为y x的两次出现均为约束出现
y的第一次出现为自由出现, 第二次出现为约束出现 z为自由出现.
例7 公式 x(F(x)xG(x)) x的辖域:(F(x)xG(x)), 指导变元为x x的辖域:G(x), 指导变元为x x的两次出现均为约束出现. 但是, 第一次出现的x是x中 的x, 第二次出现的x是x中的x. 例8 给定解释I 如下:
(a) 个体域 D=N
(b)
(c)
(d) 谓词
说明下列公式在 I 下的含义, 并讨论其真值
(1) xF(g(x,a),x) x(2x=x)
假命题
(2) xy(F(f(x,a),y)F(f(y,a),x)) xy(x+2=yy+2=x)
假命题 (3) xyzF(f(x,y),z)
xyz (x+y=z)
真命题
(4) xF(f(x,x),g(x,x))
x(2x=x2)
真命题 (5) F(f(x,a), g(x,a)) x+2=2x
不是命题
(6) x (F(x,y)F(f(x,a), f(y,a))) x (x=yx+2=y+2)
真命题
例8 (1)~(4)都是闭式, 在I下全是命题. (5)和(6)不是闭式, 在I下(5)不是命题, (6)是命题
例9 判断下列公式的类型: (1) x(F(x)G(x)) 取解释I1, D1=R,
:x是整数,
:x是有理数, 取解释I2, D2=R,
:x是整数,
:x是自然数, 非永真式的可满足式 (2) (xF(x))(xF(x))
这是 pp 的代换实例, pp是重言式,
永真式 (3) (xF(x)yG(y)) yG(y) 这是(pq)q的代换实例, (pq)q是矛盾式
矛盾式 例1 消去公式中既约束出现、又自由出现的个体变项
真命题 假命题
(1) xF(x,y,z) yG(x,y,z) uF(u,y,z) yG(x,y,z)
换名规则 uF(u,y,z) vG(x,v,z)
换名规则
或者 xF(x,u,z) yG(x,y,z)
代替规则
xF(x,u,z) yG(v,y,z)
代替规则 (2) x(F(x,y) yG(x,y,z)) x(F(x,y) tG(x,t,z))
换名规则
或者 x(F(x,t) yG(x,y,z))
代替规则 例2 设个体域D={a,b,c}, 消去下面公式中的量词: (1) x(F(x)G(x)) (F(a)G(a))(F(b)G(b))(F(c)G(c)) (2) x(F(x)yG(y)) xF(x)yG(y)
量词辖域收缩 (F(a)F(b)F(c))(G(a)G(b)G(c)) (3) xyF(x,y) x(F(x,a)F(x,b)F(x,c)) (F(a,a)F(a,b)F(a,c))(F(b,a)F(b,b)F(b,c))
(F(c,a)F(c,b)F(c,c)) 例3 给定解释I: (a) D={2,3}, (b)
(c)
:x是奇数,
: x=2 y=2,
: x=y. 在I下求下列各式的真值: (1) x(F(f(x))G(x, f(x)))
解
(F(f(2))G(2, f(2)))(F(f(3))G(3, f(3))) (11)(01) 1 (2) xyL(x,y) 解
yL(2,y)yL(3,y) (L(2,2)L(2,3))(L(3,2)L(3,3)) (10)(01) 0 例4 证明下列等值式:
x(M(x)F(x)) x(M(x) F(x)) 证
左边 x (M(x)F(x))
量词否定等值式
x(M(x)F(x)) x(M(x) F(x)) 例5 求公式的前束范式 (1) xF(x)xG(x) 解
xF(x)xG(x)
量词否定等值式 x(F(x)G(x))
量词分配等值式 解2 xF(x)yG(y)
换名规则 xF(x)yG(y)
量词否定等值式 x(F(x)yG(y))
量词辖域扩张 xy(F(x)G(y))
量词辖域扩张
第4章 关系 例1 <2,x+5>=<3y4,y>,求 x, y. 解
3y4=2, x+5=y y=2, x= 3 例2
A={0, 1}, B={a, b, c}
AB={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>}
BA ={,,,,,}
A = {}, B =
P(A)A = {<,>, <{},>}
P(A)B =
例3
(1) R={ | x,yN, x+y<3}
={<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>}
(2) C={ | x,yR, x2+y2=1},其中R代表实数集合,
C是直角坐标平面上点的横、纵坐标之间的关系,
C中的所有的点恰好构成坐标平面上的单位圆.
(3)
R={ | x,y,zR, x+2y+z=3},
R代表了空间直角坐标系中的一个平面. 例4 A={0,1}, B={1,2,3},
R1={<0,2>}, R2=A×B, R3=, R4={<0,1>},
从A到B的关系: R1, R2, R3, R4, A上的关系R3和R4.
计数:
|A|=n, |B|=m, |A×B|=nm, A×B 的子集有
个. 所以从A到B有
元关系. |A|=n, A上有
不同的二元关系. 例如 |A|=3, 则 A上有512个不同的二元关系.
例
5A={a, b, c, d}, R={,,,,}, R的关系矩阵 MR 和关系图 GR 如下:
1110100000000100例1
R={,,<{a},{d}>,}, 则
domR =
ranR =
fldR =
例2
R={<1,2>, <2,3>, <1,4>, <2,2>}
S={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>}
R1 =
R∘S =
S∘R =
个不同的二
例3 设A = {a, b, c, d}, R = {,,,}, 求R的各次幂, 分别用矩阵和关系图表示. 解 R与R2的关系矩阵分别为
0100010001 10101010102M M0001000100 0000000000
例1
A = {a, b, c}, R1, R2, R3 是 A上的关系, 其中 R1 = {,} R2 = {,,,} R3 = {}
001010010000010101000000R2自反, R3 反自反, R1既不自反也不反自反. 例2
设A={a,b,c}, R1, R2, R3和R4都是A上的关系, 其中
R1={,},
R2={,,} R3={,},
R4={,,} R1 对称、反对称.
R2 对称,不反对称. R3 反对称,不对称.
R4 不对称、也不反对称 例3 设A={a, b, c}, R1, R2, R3是A上的关系, 其中
R1={,}
R2={,}
R3={} R1 和 R3 是A上的传递关系, R2不是A上的传递关系. 例4
证明若 IA R ,则 R 在 A 上自反. 证
任取x,
xA IA R
因此 R 在 A 上是自反的.
例5
证明若 R=R1 , 则 R 在A上对称. 证
任取
R R 1 R
因此 R 在 A 上是对称的.
例6
证明若 R∩R1IA , 则 R 在 A 上反对称.
证
任取
R R R R 1
R∩R 1 IA x=y
因此 R 在 A 上是反对称的.
例7
证明若 R∘RR , 则 R 在 A 上传递.
证
任取,
R R R∘R R
因此 R 在 A 上是传递的.
例8 判断下图中关系的性质, 并说明理由
(1) 不自反也不反自反;对称, 不反对称;不传递. (2) 反自反, 不是自反;反对称, 不是对称;传递. (3) 自反,不是反自反;反对称,不是对称;不传递. 例1 设A={a,b,c,d}, R={,,,,}, R和 r(R), s(R), t(R)的关系图如下图所示. (1) (2) (3)
例1 设 A={1, 2, …, 8}, 如下定义 A上的关系R:
R={| x,y↔A∧x≡y (mod 3)} 其中 x≡y (mod 3) 叫做 x与y 模3相等, 即 x 除以3的余数与 y 除以3的余数相等. 不难验证R为A上的等价关系, 因为
x↔A, 有x≡x(mod 3)
x,y↔A, 若x≡y(mod 3), 则有y≡x(mod 3)
x,y,z↔A, 若x≡y(mod 3), y≡z(mod 3), 则有
x≡z(mod 3) 例2 令A={1, 2, …, 8},A关于模 3 等价关系R 的商集为
A/R = { {1, 4,7}, {2, 5, 8}, {3, 6} } A关于恒等关系和全域关系的商集为:
A/IA = { {1},{2}, … ,{8}}
A/EA = { {1, 2, … ,8} }
例3 设A={a, b, c, d}, 给定 1, 2, 3, 4, 5, 6如下: 1={{a, b, c},{d}},
2={{a, b},{c},{d}} 3={{a},{a, b, c, d}}, 4={{a, b},{c}} 5={,{a, b},{c, d}}, 6={{a,{a}},{b, c, d}} 则 1和 2是A的划分, 其他都不是A的划分. 例4 给出A={1,2,3}上所有的等价关系
求解思路:先做出A的所有划分, 然后根据划分写出
对应的等价关系.
A上的等价关系与划 分之间的对应:
4对应于全域关系EA 5对应于恒等关系IA 1, 2和 3分别对应于等价关系 R1, R2和R3. 其中
R1={<2,3>,<3,2>}∪IA
R2={<1,3>,<3,1>}∪IA
R3={<1,2>,<2,1>}∪IA 例5
设A={1,2,3,4},在AA上定义二元关系 R:
<,>R x+y = u+v, 求R 导出的划分.
解
AA={<1,1>, <1,2>, <1,3>, <1,4>, <2,1>, <2,2>, <2,3>,
<2,4>,<3,1>, <3,2>, <3,3>, <3,4>, <4,1>, <4,2>, <4,3>,
<4,4>}
根据有序对的 x+y=2,3,4,5,6,7,8 将AA划分. (AA)/R={{<1,1>}, {<1,2>,<2,1>}, {<1,3>, <2,2>, <3,1>},
{<1,4>, <2,3>, <3,2>, <4,1>}, {<2,4>, <3,3>, <4,2>},
{<3,4>, <4,3>}, {<4,4>}}
例6
<{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }, R整除>
例7
已知偏序集的哈斯图如下图所示, 试求出集合A和关系R的表达式.
A={a, b, c, d, e, f, g, h}
R={,,,,,,,,
}∪IA
例8 设偏序集如下图所示,求A 的极小元、最小元、 极大元、最大元. 设B={ b, c, d }, 求B 的下界、上界、下 确界、上确界.
解:极小元:a, b, c, g;极大元:a, f, h;没有最小元与最大元.B的下界和最大下界都不存在, 上界有d 和 f, 最小上界为 d.
第5章 函数
例1 设A = {1, 2, 3}, B = {a, b}, 求BA. 解BA = { f0, f1, … , f7 }, 其中
f0={<1,a>,<2,a>,<3,a>} f1={<1,a>,<2,a>,<3,b>} f2={<1,a>,<2,b>,<3,a>} f3={<1,a>,<2,b>,<3,b>} f4={<1,b>,<2,a>,<3,a>} f5={<1,b>,<2,a>,<3,b>} f6={<1,b>,<2,b>,<3,a>} f7={<1,b>,<2,b>,<3,b>} 例2
判断下面函数是否为单射, 满射, 双射的, 为什么? (1)f : R→R, f(x)= x2+2x1 (2)f : Z+→R, f(x)=lnx, Z+为正整数集 (3)f : R→Z, f(x)=x (4)f : R→R, f(x)=2x+1 (5)f : R+→R+, f(x)=(x2+1)/x, 其中R+为正实数集. 解 (1) f : R→R, f(x)= x2+2x1
在x=1取得极大值0. 既不是单射也不是满射的.
(2) f : Z+→R, f(x)=lnx
单调上升, 是单射的. 但不满射, ranf={ln1, ln2, …}. (3) f : R→Z, f(x)= x
是满射的, 但不是单射的, 例如 f(1.5)=f(1.2)=1.
(4) f : R→R, f(x)=2x+1
是满射、单射、双射的, 因为它是单调函数并且ranf=R.
(5) f : R+→R+, f(x)=(x2+1)/x
有极小值f(1)=2. 该函数既不是单射的也不是满射的. 例3
A=P({1,2,3}), B={0,1}{1,2,3} 解
A={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.
B={ f0, f1, … , f7 }, 其中
f0={<1,0>,<2,0>,<3,0>},
f1={<1,0>,<2,0>,<3,1>}, f2={<1,0>,<2,1>,<3,0>},
f3={<1,0>,<2,1>,<3,1>},
f4={<1,1>,<2,0>,<3,0>},
f5={<1,1>,<2,0>,<3,1>},
f6={<1,1>,<2,1>,<3,0>},
f7={<1,1>,<2,1>,<3,1>}. 令
f : A→B,
f()=f0, f({1})=f1, f({2})=f2, f({3})=f3,
f({1,2})=f4, f({1,3})=f5, f({2,3})=f6, f({1,2,3})=f7 例4
A=[0,1]
B=[1/4,1/2] 构造双射 f : A→B解
令
f : [0,1]→[1/4,1/2]
f(x)=(x+1)/4
例5
A=Z, B=N,构造双射 f : A→B
将Z中元素以下列顺序排列并与N中元素对应: Z:011
2233 …
↓
↓
↓
↓
↓
↓
↓ N:0 1 2
3 4 5 6 … 则这种对应所表示的函数是:
x02xf:ZN,f(x)2x1x0例1 设 f : R→R, g : R→R x2x3f(x) x32 g(x)x2
求
f ∘g, g∘f. 如果 f 和 g 存在反函数, 求出它们的反函数. 解 fg:RRx22x3fg(x)x30gf:RR(x2)2gf(x)2x1x1 f : R→R不存在反函数;g : R→R的反函数是 g1: R→R, g1(x)=x2
第6章 图
例1 下述2组数能成为无向图的度数列吗? (1) 3,3,3,4; (2) 1,2,2,3
解 (1) 不可能. 有奇数个奇数. (2) 能
例2 已知图G有10条边, 4个3度顶点, 其余顶点的度数均小 于等于2, 问G至少有多少个顶点? 解 设G有n个顶点. 由握手定理,
43+2(n-4)210 解得
n8 例3 已知5阶有向图的度数列和出度列分别为3,3,2,3,3和 1,2,1,2,1, 求它的入度列 解
2,1,1,1,2 例4 证明不存在具有奇数个面且每个面都具有奇数条棱的 多面体.
证
用反证法. 假设存在这样的多面体, 作无向图G=, 其中 V={v | v为多面体的面},
E={(u,v) | u,vV u与v有公共的棱 uv}. 根据假设, |V|为奇数且vV, d(v)为奇数. 这与握手定理的推论矛盾. 例5 设9阶无向图的每个顶点的度数为5或6, 证明它至少有 5个6度顶点或者至少有6个5度顶点. 证
讨论所有可能的情况. 设有a个5度顶点和b个6度顶点 (1)a=0, b=9;
(2)a=2, b=7; (3)a=4, b=5; (4)a=6, b=3; (5)a=8, b=1 (1)~(3) 至少5个6度顶点, (4)和(5) 至少6个5度顶点
方法二
假设b<5, 则a>9-5=4. 由握手定理的推论, a 6 例6 画出4阶3条边的所有非同构的无向简单图
解 总度数为6, 分配给4个顶点, 最大度为3, 且奇度顶点数 为偶数, 有下述3个度数列: (1) 1,1,1,3;(2)1,1,2,2;(3)0,2,2,2. 1,1,1,3 1,1,2,2
例7 画出3个以1,1,1,2,2,3为度数列的非同构的无向简单图 0,2,2,2
例1 右图有
4 个面 R1的边界:a R2的边界:bce R3的边界:fg
R0的边界:abcdde, fg
deg(R1)=1 deg(R2)=3 deg(R3)=2 deg(R0)=8 例2 右边2个图是同一平面图的平面嵌入. R1在(1)中是外部面, 在(2)中是内部面; R2在(1)中是内部面, 在(2)中是外部面.
R3 R1 R3 R2 (1)
R2
R1 (2)
说明: (1) 一个平面图可以有多个不同形式的平面嵌入, 它们都同构. (2) 可以通过变换(测地投影法)把平面图的任何一面作为外部面 例3 证明 K5 和 K3,3不是平面图
证 K5 : n=5, m=10, l=3
K3,3 : n=6, m=9, l=4
不满足定理6.15的条件
例
5证明下面2个图均为非平面图.
与K3,3同胚也可收缩到K3,3
与K5同胚也可收缩到K5 例6 画出所有非同构的6阶11条边的简单连通非平面图 解
在K5(5阶10条边)上加一个顶点和一条边
在K3,3(6阶9条边)上加2条边
例1 某中学有3个课外活动小组:数学组, 计算机组和生物组. 有赵,钱,孙,李,周5名学生, 问分别在下述3种情况下, 能否选出3人各任一个组的组长? (1) 赵, 钱为数学组成员, 赵,孙,李为计算机组成员, 孙,李,周为生物组成员. (2) 赵为数学组成员, 钱,孙,李为计算机组成员, 钱,孙,李,周为生物组成员. (3) 赵为数学组和计算机组成员, 钱,孙,李,周为生物组成员. 解
数 计 生 数 计 生
赵 钱 孙 李 周 赵 钱 孙 李 周
(1(
2 数 计 生
赵 钱 孙 李 周
(3(1),(2)有多种方案, (3) 不可能 例2 证明下述各图不是哈密顿图:
(a(b(c)
(c) 中存在哈密顿通路
例3 证明右图不是哈密顿图
证
假设存在一条哈密顿回路, a,f,g是2度顶点, 边(a,c), (f,c)和(g,c)必在这条哈密顿回路上,从而点c出现3次, 矛盾.
a b c f d
e
g
此外, 该图满足定理6.10的条件, 这表明此条件是必要、而不充分的.又, 该图有哈密顿通路. 例4 有7个人, A会讲英语, B会讲英语和汉语, C会讲英语、意大利语和俄语, D会讲日语和汉语, E会讲德语和意大利语, F会讲法语、日语和俄语, G会讲法语和德语. 问能否将他们沿圆桌安排就坐成一圈, 使得每个人都能与两旁的人交谈? 解
作无向图, 每人是一个顶点, 2人之间有边他们有共同的语言. G F E D
A B C
ACEGFDBA是一条哈密顿回路,按此顺序就坐即可.
第五篇:离散数学习题
集合论
1. A={,1},B={{a}}求A的幂集、A×B、A∪B、A+B。 2. A={1,2,3,4,5}, R={(x,y)|x
4. A={a,b,c},R= IA ∪{(a,b),(b,a)},求a和b关于R的等价类。
5. R是A上的等价关系,A/R={{1,2},{3}},求A,R。 6. 请分别判断以下结论是否一定成立,如果一定成立请证明,否则请举出反例。
①如果A∪BC,则AC或者BC。 ②如果A×B=A×C且A,则B=C。
27. 如果R是A上的等价关系,R,r(R)是否一定是A上的等价关系?证明或举例。
8. 已知A∩CB∩C,A-CB-C,证明:AB。 9. 证明:AX(B∩C)=(AXB)∩(AXC) 10. 证明:P(A)∪P(B)P(A∪B) -111. 证明:R[sym] iff R=R
-1212. 证明:r(R)=R∪IA,S(R)=R∪R,t(R)=R∪R∪... 13. 证明:s(R∪S)=s(R)∪s(S) 14. R是A上的关系,证明:如果R是对称的,则r(R)也是对称的。
15. I是整数集,R={(x,y)|x-y是3的倍数},证明:R是I上的等价关系。
16. 如果R是A上的等价关系,则A/R一定是A的划分。 17. R是集合A上的自反关系,S是A上的自反和对称关系,证明t(R∪S)是A上的等价关系。 18. I是正整数集合,R是I×I上的二元关系,R={<,>|xv=yu},证明:R是等价关系。
19. f:AB,R是B上的等价关系,令S={|xA且yA且R},证明:S是A上的等价关系。
20. R是集合A上的自反关系,S是A上的自反和对称关系,证明t(R∪S)是A上的等价关系。
21. P和Q都是集合A上的划分,请问P∪Q,P-Q是否是A上的划分,
22. RAXA,R[irref]且R[tra],证明:r(R)是A上的偏序关系。
23. 画出{1,2,3,4,6}上整除关系的哈斯图,求{2,3,6}的4种元素。
24. A={a,b,c,d,e,f,g},R={(a,c),(a,e),(b,d),(b,f),(d,e),(d,f)},S=tr(R),画出S的哈斯图并求{b,c,d,f}的极大元等8种元素。
25. f:A→B,g:B→C都是单(满)射,证明:复合映射gof一定是单(满)射。
26. f:A→B,g:B→C,gof是单射,请问f和g是否一定是单射?请证明或举出反例。 27. R是实数集,f:R×RR×R,f()=,请问f是否为单射?是否为满射?分别证明或举反例。 28. 已知B∩C=,令f:P(B∪C)P(B)×P(C),对XP(B∪C),令f(X)=(B∩X,C∩X),证明:f是双射。
代数系统
1. 是模8加群,Z8={0,1,2,3,4,5,6,7},+8是模8加法,求出的单位元、每个元素的逆元、所有的生成元和所有的子群。
2. 求的单位元,零元,每个元素的逆元,每个元素的阶,它是循环群吗?求出它所有的子群。
3. R是实数集,在R上定义运算*为x*y=x+y+xy,问:是代数系统吗?有单位元吗?每个元素都有逆元吗? ***4. R是非零实数集合,是代数系统,对于R中元素*x,y,令xoy=2x+2y-2。请问中是否存在单位元、零元、哪些元素有逆元?运算o是否满足交换律和结合律。分别说明理由。
5. R是实数集,R上的6运算定义如下:对R中元素x,y,f1()=x+y;f2()=x-y;f3()=xy;f4()=x/y;f5()=max{x,y};f6()=|x-y|。问:哪些满足交换律、结合律、有单位元、有零元?说明理由。
6. 是一个群,证明:G是交换群当且仅当对任意G中222元素x,y,都有等式(xy)=xy成立。
7. 证明:如果群G中每个元素的逆元素都是它自已,则G是交换群。
8. 循环群一定是交换群。
9. 证明:阶为素数的群一定是循环群。
-110. 是一个群,uG,定义运算*:x*y=xouoy, 证明:是一个群。
11. 整数集Z上定义运算*:对任意整数x和y,x*y=x+y-4,其中+,-为普通加减法。证明:是一个群。
12. 证明:如果群G中至少有两个元素,则群中没有零元。 13. S是G的子群,证明:{x|x是S的左陪集}是G的一个划分
14. 是一个群,aG,n是a的阶(周期),证明:k<{a|k=0,2,…,n-1},o>是的一个子群。
15. H,K都是群G的子群,请问H∩K,H∪K,H-K是否一定是G的子群? 16. H,K是G的两个子群,aG, 试证:aHaK当且仅当HK。 17. G={1,3,4,5,9},*是模11的乘法(即x*y=xy mod 11),请问(G,*)是否构成群?
n18. 是群,e是单位元,aG,a的阶为k,证明:a=e当且仅当 n是k的倍数。
19. S是G的子群,证明:{x|x是S的左陪集}是G的一个划分
20. G是群,证明:S={aG|xG(ax=xa)},则S是G的子群。 21. 是偶数阶群,则G中必存在2阶元素。 22. 证明:6个元素的群在同构意义下只有两个。
++23. R为实数集,R为正实数集,与是否同构? 24. 是有限群,证明:G不可能表示成两个真子群的并。 25.图论
1. 如何判断二部图?完全图、完全二部图的边数。 2. 如何求E回路?
3. Petersen图是否为E图或H图。
4. 哪些完全图是H图?哪些完全图是E图? 5. n为何值时轮图为H图? 6. 如何求最小生成树。
7. 证明:奇数个顶点的二部图(两步图)不是哈密尔顿图。 8. 证明:如果G是欧拉图,则其边图L(G)也是欧拉图。 9. 证明:奇数个顶点的二部图(两步图)不是哈密尔顿图。 10. G是平面图,G有m条边,n个顶点,证明:m3n-6。并由此证明K5不是平面图。
11. 证明:有6个顶点的简单无向图G和它的补图中至少有一个三角形。
12. 证明:在至少有两个顶点的无向树中,至少有2个一度顶点。
13. G是无向简单连通图,G有n个顶点,则G最少有几条边,最多有几条边?
14. 证明:简单无向图G和它的补图中至少有一个是连通图。 15. 证明:无向图中奇度点(度数为奇数的点)有偶数个。 16. 证明:n个顶点的无向连通图至少有n-1条边。 17. G是H图,V是G的顶点集,证明:对任意顶点集S,SV,都有ω(G-S)≤|S|。其中ω(G-S)表示G-S的分图数目。 18. 一棵无向树有3个3次点,1个顶点次数为2,其余顶点次数为1,问它有几个次数为1的顶点?写出求解过程。 19. 证明:每个简单平面图都包含一个次至多为5的顶点。 20. 连通平面图G有n个顶点,m条边和f个面,证明:n-m+f=2。 21. 如果图G的最大顶点次数≤ρ,证明:G是ρ+1可点着色的。
22. G是无向简单连通图,G有n个顶点,则G最少有几条边,最多有几条边?
23. 如果一个简单图G和它的补图同构,则称G是自补图,求所有4个顶点自补图。
24. G是平面图,G有m条边,n个顶点,证明:m3n-6。如果G中无三角形,则m2n-4。 数理逻辑
1. 如果今天是星期一,则要进行英语或数理逻辑考试。
没有不犯错误的人。整数都是有理数。 有的有理数不是整数。
不存在最大的整数。有且只有一个偶数是素数。 2. 求真值表及范式:P(┓QR)、(┓QR)(PR) 3. 推理:
p(qr),┓s∨p,q ├ sr pr,qs,p∨q ├ r∨s p∨q,p┓r,st,┓sr,┓t ├ q p(┓(r∧s)┓q),p,┓s ├ ┓q 4. 如果小王是理科学生,他一定会学好数学。如果小王不是文科学生,他一定是理科学生。小王没学好数学。所以小王是文科学生。
5. 判断各公式在给定解释时的真假值,并且改变论域使该公式在新的解释下取值相反。 论域:D={-2,3,6}, F(x):x≤3, G(x):x>5, R(x,y):x+y<4 ①x(F(x)∨G(x)) ②yyR(x,y)