第一篇：离散数学衔接试卷1解答
离散数学试卷
（课程代码 02324）
1、下列句子是命题的是[ D ]。
A、x + y > 3
B、这朵玫瑰花真美呀
C、请全体同学起立
D、我是一位大学生
2、下列式子为重言式的是[ B ]。
A、(┐P∧R)→QB、P∨（┐P）
C、P∨(P∧Q)D、(┐P∨Q)→(P→Q)
3、对于公式(x)(y)(P(x)∧Q(y))→(x)R(x，y)，下列说法正确的是[ C ]。
A、y是自由变元B、y是约束变元
C、(x)的辖域是R(x, y)D、(x)的辖域是(y)(P(x)∧Q(y))→(x)R(x,y)
4、设R是实数集，f:R→R, f(x)=x^2+2，则f 是[D ]。
A、单射B、满射
C、双射D、映射
5、下列运算不满足交换律的是[A ]。
A．a*b=a+2b B．a*b=min(a,b)
C．a*b=|a-b| D．a*b=2ab 101100011011
6、下列关系矩阵所对应的关系具有对称性的是[D ]。1100B、1001 1A、001010C、0 01D、
7、如右图所示的有向图的最大出度是010[C ]。100A、0 B、1
C、2 D、38、下列图是欧拉图的是[D ]。
9、下列正确的说法是[D]。
A、满足自反性、对称性的二元关系称为等价关系
B、满足自反性、传递性的二元关系称为等价关系
C、满足自反性、反对称性、传递性的二元关系称为等价关系
D、满足自反性、对称性、传递性的二元关系称为等价关系
10、一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是 [ B]。
A、13 B、14
C、15 D、16
二、填空题（本大题共10小题，每小题3分，共30分。请将正确答案填入括号内。填错或不填都不得分。）
1、P表示“王一学习努力”，Q表示“王一身体好”。则“王一学习努力身体又好”的符号表述为：
2、设命题变元P、Q、R的真值都是0，则命题公式(┐P∧R)→Q的真值为 1。
3、设论域为{1 , 2}，与公式(x)A(x)等价的是PQ。A1A2A3。
R6,6。
4、设H =｛f，m，s，d｝依次表示一个家庭里的父母子女四个人的集合，R是H上的长幼关系，则R =f,s,f,ds,m,d,m,。
5、设A=｛1，3，6｝，H上的关系R={（1，1），（1，3），（3，3）}，则R的自反闭包为r（R）=
6、全体整数的集合Z上定义关系R为模4同余关系，则Z关于R的分类Z/R = 10011007、设S为非空集合，T为S的幂集，代数系统
8、已知有向图的邻接矩阵为
0011。3度点，其它的都是叶子，则这棵树的叶子数为：
9、一棵树有2个4度点，3个 9。101010、周游树的前序行遍法的访问次序为：树根、左子树、右子树。
三、计算题（本大题共5小题，每小题8分，共40分。）
1、设集合，求集合的幂集。
解：。
2、设集合，是集合上的整除关系，画出
解： 01,2,3,0AAa,bPA,a,b,a,bAA1,2,4,8RA,R的哈斯图。
3、求下图的最小生成树。
解：
4、构造下列命题公式
pqp 的真值表。
1、今有a、b、c、d、e、f、g等7人，已知以下信息：a会说英语，b会说英语和汉语，c会说英语、意大利语和俄语，d会讲日语和汉语，e会讲德语和意大利语，f会讲法语、日语和俄语，g会讲法语和德语。用图来证明这7个人按照适当顺序围成一圈，相邻的两人可以交谈。
解：
经观察哈密顿回路是：。
2、证明整数集合上的“大于或者等于”关系是偏序关系。
证明：（1）任意给出一个整数，则。即“大于或者等于”关系满足自反性；
（2）如果有两个整数，使得，且，则。即“大于或者等于”关系满足反对称性；
（3）如果有三个整数，使得，且，则。即“大于或者等于”关系满足传递性。
综上所述，整数集合上的“大于或者等于”关系是偏序关系。abdfgecaaaaabbaaba,babbcaca,b,c
第二篇：离散数学练习题1
1、下列句子是简单命题的是（）
A)3是素数。B)2x+3<
5C)张三跟李四是同学吗？D)我在说谎。
2、下列公式不是永真式的是（）．．
A)((p∧q))→p)∨rB)p→(p∨q∨r)
C)┓(q→r)∧rD)(p→q)→(┓q→┓p)
3、设命题公式G<=>┓(p→q)，H<=>p→(q →┓p)，则G与H的关系是()。
A)G<=>HB)H→GC)H => GD)G => H4、下列命题不为真的是（）．
A)Φ ΦB)Φ∈Φ
C){a,b}∈{a,b,c,{a,b}}}D){a,b}{a,b,c,{a,b}}
5、1到300之间（包含1 和1000）不能被3、5和7整除的数有（）个。
13、下列运算在指定集合上不符合交换律的是（）。
A)复数C集合上的普通加法B)n阶实矩阵上的乘法 C)集合S的幂集上的∪D)集合S的幂集上的
14、下列集合对所给的二元运算封闭的是（）
A)正实数集合R+和。运算，其中。运算定义如下：a,b∈R+，a。b=ab-a-b B)n∈Z+，nZ={nZ|z∈Z}，nZ关于普通的加法运算 C)S={2x-1|x∈Z+}关于普通的加法运算
D)S={x|x=2n, n∈Z+}，S关于普通的加法运算
15、设V=
A)半群、独异点、群B)半群、独异点C)半群D)二元运算
上有○
A)138B)120C)68D)1246、设A, C, B, D为任意集合，以下命题一定为真的是（）
A)A∪B= A∪C =>B=C B)A×C= A×B =>B= C
C)A∪(B×C)=(A∪B)×(A∪C)D)存在集合A,使得A A ×A7、设A={1,2,3,4}，R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>} 是A上的关系，则R的性质是（）
A)既是对称的也是反对称的 B)既不是对称的也不是反对称的 C)是对称的但不是反对称的D)不是对称的但是反对称的8、设R是A上的关系，则R在A上是传递的当且仅当（）
则这4个运算中满足幂等律的是（）
17、在上述四个运算中有单位元的是（）
18、在上述四个运算中有零元的是（）
19、与命题公式P（QR）等值的公式是()
A)(PQ)RB)(PQ)RC)(PQ)RD)P(QR)
20、下列集合都是N的子集，能够构成代数系统V=
A)｛x| x∈N∧x与5互为素数｝B)｛x| x∈N∧x是30的因子｝ C){x| x∈N∧x是30的倍数}D){x|x=2k+1, k∈N }
二、填空题(1分/空，共20分。请将正确答案填在相应的横线上。)
1、公式┓(p∨q)→p的成假赋值为00__,公式┓(q→p)∧p的成真赋值为。
2、设Ａ，Ｂ为任意命题公式，Ｃ为重言式，若Ａ∧Ｃ<=>Ｂ∧Ｃ，那么Ａ<->Ｂ是重言式（重言式、矛盾式或可满足式）。
3、f：N->N×N，f(x)=
其中，x=y(mod 3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等。则1的等价类，即[1]，为（）
A){1,4,7}B){2,5,8}C){3,6}D){1,2,3,4,5,6,7,8}
10、当集合A=Φ且B≠Φ时，则BA结果为（）
A)ΦB){Φ} C){Φ, {Φ}}D)错误运算
11、函数f:R→R,f(x)= x2-2x+1,则f(x)是（）函数。
A)单射B)满射C)双射D)不是单射，也不是满射
12、设X={a,b,c,d},Y={1,2,3}，f={
A)f是从X到Y的二元关系，但不是从X到Y的函数 B)f是从X到Y的函数，但不是满射的，也不是单射的 C)f是从X到Y的满射，但不是单射 D)f是从X到Y的双射
双射）函数，A在f下的像f(A)＝_{<5,6>}_，B在f下的完全原像f-1(B)=____。
4、已知公式A中含有3个命题变项p,q,r，并且它的成真赋值为000，011，110，则A的主合取范式为（用极大项表示）__M∧_M∧_M∧_M∧_M，主析取范式为（用极小项表示）
5、公式x(F(x,y)→yG(x,y,z))的前束范式为_
6、列出从集合A={1,2}到B={1}的所有二元关系。
7、设A为集合且∣A∣=n，则A共有nP(A)有n
8、设 f，g，h ∈RR 且f(x)=x+3, g(x)=2x+1, h(x)=x/2, 则复合函数
⑦ x(F(x)∧G(x)→H(x))前提引入 ⑧ F(a)∧G(a)→H(a)T ⑦UI⑨ F(a)∧G(a)T ③ ⑥合取(10)H(a)T ⑧ ⑨ 假言推理
f。g。h(x)=__，f。g。h(x)=_____。
9、含有n个命题变项的公式共有_____个不同的赋值，最多可以生成___个不同的真值表；n个命题变项共可产生___n_____个极小项（极大项）；含n个命题变项的所有有穷多个合式公式中，与它们等值的主析取范式（主合取范式）共有___2^2___种不同的情况。
10、已知集合A={,{}}，则A的幂集P(A)＝_____。
n
n
n
五、设A={1,2,3,4}，在A×A上定义二元关系R，
(1)证明R是A×A上的等价关系
(2)确定由R引起的对A×A的划分。(5分)
三、利用公式的主合取范式判断下列公式是否等值。（5分）
p→(q→r)与(p∧q)∨r p→(q→r)
<=>p∨(q∨r)<=>p∨q∨r <=>M6
(p∧q)∨r
<=>(p∨q)∨r <=>p∨q)∨r <=>M6
(1)证明:
=> x+v+u+n=y+u+v+m => x+n=y+m =>
解:{{<1,1>,<2,2>,<3,3>,<4,4>},{<1,2>,<2,3>,<3,4>},{<1,3>,<2,4>},{<1,4>,<4,1>},{<3,1>,<4,2>},{<2,1>,<3,2>,<4,3>}}
四、符号化命题，并推理证明(给出每个符号的准确含义，及每一步推理的根据)。（5分）
每个科学工作者都是刻苦钻研的。每个刻苦钻研而又聪明的人在他的事业中都将获得成功。华有为是科学工作者并且是聪明的，所以华有为在他的事业中将获得成功。
六、A= {1,2,3,4,6,8,12}，R是A上的整除关系，请作出偏序集
求出A的极大元、极小元、最大元和最小元。若B={2,3,4}，求出B的上界，下界，最小上界，最大下界。（5分）
解:
首先符号化：M(x)：x是科学工作者；F(x)：x是刻苦钻研的；G(x)：x是聪明的；H(x)：x
在事业中获得成功；a：华有为。
前提： x(M(x)→F(x)），x(F(x)∧G(x)→H(x)),M(a)∧ G(a)
结论：H(a)
证明：① M(a)∧ G(a)前提引入 ② M(a)T ①化简规则 ③ G(a)T ①化简规则 ④ x(M(x)→F(x)）前提引入 ⑤ M(a)→F(a)T ④
⑥ F(a)T ② ⑤ 假言推理
解:A的极大元为8、12,极小元为1，无最大元，最小元为1。
B的上界为12，下界为1，最小上界为12，最大下界为1。
七、在自然推理系统P中构造下面推理的证明。（5分）(1)前提：(p∨q)→(r∧s),(s∨t)→u
结论：p→u(2)前提：x(F(x)→(G(a)∧ R(x)))，x F(x).九、证明下列恒等式 A-(B∪C)=(A-B)∩(A-C)。（5分）证明：A-(B∪C)
结论： x(F(x)∧ R(x)).(1)证明：① p附加前提引入规则② p ∨ q①附加规则③(p ∨ q)→(r ∧ s)前提引入
④ r ∧ s②③ 假言推理⑤ s④化简规则⑥ s ∨ t⑤附加规则⑦(s ∨ t)→ u前提引入
⑧ u⑥ ⑦假言推理
(2)证明：① x F(x)前提引入② F(b)① EI③ x(F(x)→(G(a)∧ R(x)))前提引入④ F(b)→(G(a)∧ R(b))③ UI
⑤ G(a)∧ R(b)② ④假言推理⑥ R(b)⑤化简⑦ F(b)∧ R(b)②⑥合取⑧x(F(x)∧ R(x))⑦EG
八、设有理数集合Q上的 * 运算定义如下：a，b∈Q, a*b=a+b-ab。请指出该运算的性质，并求出其单位元、零元及所有可能的逆元。（5分）
解：(1)因为a*b=a+b-ab =b+a-ba=b*a，所以运算满足交换律。
(2)因为(a*b)*c=(a+b-ab)*c= a+b-ab+c-(a+b-ab)c=a+b+c-ab-bc-ac+abca*(b*c)=a*(b+c-bc)=a+b+c-bc-a(b+c-bc)= a+b+c-ab-bc-ac+abc故运算满足结合律。
(3)任意x∈Q，因为x*x=x+x-xx=2x+x2≠x，故不满足幂等律(4)因为对a∈Q，有a*0=a+0-a0=a，所以0是单位元。(5)因为对a∈Q，有a*1=a+1-a=1，所以1是零元。
(6)对a∈Q，令a*x=a+x-ax=0，则有x=a/(a-1)。所以当a≠1时，其逆元为a=a/(a-1)，1没有逆元。
1＝A∩～(B∪C)＝A∩～B∩～C = A∩A∩～B∩～C ＝(A∩～B)∩(A∩～C)=(A-B)∩(A-C)
十、设A,B为任意集合，证明：AB<=>P(A)P(B)。（5分）证明：先证明充分性（=>）
X∈P(A)=> XA=> XB=> X∈P(B)再证明必要性（<=）
x∈A=> {x}A=> {x}∈P(A)=> {x}∈P(B)=> {x}B=>x∈B 综上所述，AB<=>P(A)P(B)
第三篇：离散数学复习题1
逻辑
1、给出的真值表
2、证明为永真式 谓词量词和推理
1、使用量词和谓词表达不存在这一事实
2、证明前提“在这个班上的某个学生没有读过书”和班上的每个学生都通过了第一门考试蕴含结论“通过考试的某个人没有读过书” 集合、函数、数列与求和
1、全集为，求集合A=的位串？它的补集的位串是什么？写出集合A=的所有子集，写出集合
2、从集合到集合能定义多少个函数？下面给出的函数其定义为：该函数是双射吗？是满射吗？该函数是否存在逆函数？如果存在请给出其逆函数。计数
1、计算机系统的美国用户有一个6～8个字符构成的密码，其中每个字符是一个大写字母或数字，且每个密码必须至少包含一个数字，问总共有多少个合适的密码？
2、在30天的一个月里，某棒球队一天至少打一场比赛，但最多打45场。证明一定有连续的若干天内这个球队恰好打了14场比赛
3、证明n个元素的集合中允许重复的r组合数等于
4、按照字典顺序生成整数1，2，3的所有排列（不允许重复），在362541后面按照字典顺序的下一个最大排列是什么？找出在1000100111后面的下一个最大的二进制串。关系
1、求下面给出关系R的自反闭包、对称闭包和传递闭包的0-1关系矩阵，其中
2、S是所有比特串的集合，关系定义为当s=t或者s和t的长度至少是3，且前3个比特相同时具有关系，例如0101，0011100101，但01010，0101101110。证明是S上的等价关系，由产生的S的等价类是那些集合？
3、偏序集（{2,4,5,10,12,20,25},|）的那些元素是极大的，那些元素是极小的？ 图与树
1、在下图所示的图中，从a 到d的长度为4的通路有几条？该图是否是Euler图，是否是Hamilton图，该图的度序列是什么？该图是否可平面，如果是请给出平面画图，该图的点色数和边色数等于多少？给出该图的一个生成树，2、求下面赋权图从a到z的最短距离是多少？最短路径是什么？（画图给出标号过程）
3、用哈夫曼编码方法来编码下列符号，这些符号具有下列频率：A:0.08，B:0.10，C:0.12，D:0.15，E:0.20，F:0.35,该编码方法编码一个字符的平均位数是多少？
4、下面树的高度是多少？那些节点是内部节点，那些节点是叶子节点，该树是否是3元正则树？分别给出该树节点的前序、中序、后序遍历的节点访问次序
第四篇：离散数学 期末考试试卷答案
离散数学试题(B卷答案1）
一、证明题（10分）
1)(P∧(Q∧R))∨(Q∧R)∨(P∧R)R 证明: 左端(P∧Q∧R)∨((Q∨P)∧R)((P∧Q)∧R))∨((Q∨P)∧R)((P∨Q)∧R)∨((Q∨P)∧R)((P∨Q)∨(Q∨P))∧R ((P∨Q)∨(P∨Q))∧R T∧R(置换)R 2)x(A(x)B(x)) xA(x)xB(x)证明 ：x(A(x)B(x))x(A(x)∨B(x))xA(x)∨xB(x)xA(x)∨xB(x)xA(x)xB(x)
二、求命题公式(P∨(Q∧R))(P∧Q∧R)的主析取范式和主合取范式（10分）。
证明：(P∨(Q∧R))(P∧Q∧R)(P∨(Q∧R))∨(P∧Q∧R))（P∧(Q∨R)）∨(P∧Q∧R)(P∧Q)∨(P∧R))∨(P∧Q∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R))∨(P∧Q∧R))∨(P∧Q∧R)m0∨m1∨m2∨m7 M3∨M4∨M5∨M6
三、推理证明题（10分）
1）C∨D，(C∨D) E，E(A∧B)，(A∧B)(R∨S)R∨S 证明：(1)(C∨D)E(2)E(A∧B)
P P
P(3)(C∨D)(A∧B)T(1)(2)，I(4)(A∧B)(R∨S)(5)(C∨D)(R∨S)(6)C∨D
T(3)(4)，I P(7)R∨S T(5)，I 2)x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧x(P(x)∧R(x))证明(1)xP(x)P
(2)P(a)T(1)，ES(3)x(P(x)Q(y)∧R(x))P(4)P(a)Q(y)∧R(a)T(3)，US(5)Q(y)∧R(a)T(2)(4)，I(6)Q(y)T(5)，I(7)R(a)T(5)，I(8)P(a)∧R(a)T(2)(7)，I(9)x(P(x)∧R(x))T(8)，EG(10)Q(y)∧x(P(x)∧R(x))T(6)(9)，I
四、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数（10分）。
解：A，B，C分别表示会打排球、网球和篮球的学生集合。则|A|=12，|B|=6，|C|=14，|A∩C|=6，|B∩C|=5，|A∩B∩C|=2。
先求|A∩B|。
∵6=|（A∪C）∩B|=|（A∩B）∪（B∩C）|=|（A∩B）|+|（B∩C）|-|A∩B∩C|=|（A∩B）|+5-2，∴|（A∩B）|=3。
于是|A∪B∪C|=12+6+14-6-5-3+2=20。不会打这三种球的人数25-20=5。
五、已知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）
六、已知R、S是N上的关系，其定义如下：R={
解：R={
七、设R={
解：r(R)={
12-1
2s(R)={
八、证明整数集I上的模m同余关系R={
证明：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）=fg（10分）。
1-1-14325证明：因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数（gf）：C→A。同理可推fg：C→A是双射。
因为
1-1
-1-1-1-1
-1-1-1
-1离散数学试题(B卷答案2）
一、证明题（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 m0∨m2∨m3
三、推理证明题（10分）
1)(P(QS))∧(R∨P)∧QRS 证明：(1)R(2)R∨P(3)P(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)P T(2)，E(4)xA(x)Q P(5)(xA(x)Q)∧(QxA(x))T(4)，E(6)QxA(x)T(5)，I(7)QP T(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={
七、设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>,<4,4>,<5,5>} s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>} R=R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>} R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}
八、设R1是A上的等价关系，R2是B上的等价关系，A≠且B≠。关系R满足：<
证明 对任意的
对任意的
5∈R，即
对任意的
综上可得，R是A×B上的等价关系。
九、设f：AB，g：BC，h：CA，证明：如果hgf＝IA，fhg＝IB，gfh＝IC，则f、g、h均为双射，并求出f、g和h（10分）。
解 因IA恒等函数，由hgf＝IA可得f是单射，h是满射；因IB恒等函数，由fhg＝IB可得g是单射，f是满射；因IC恒等函数，由gfh＝IC可得h是单射，g是满射。从而f、g、h均为双射。
由hgf＝IA，得f＝hg；由fhg＝IB，得g＝fh；由gfh＝IC，得h＝gf。－
1－1
－1－1－1
－1离散数学试题(B卷答案3）
一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程)1)P(P∨Q∨R)2)((QP)∨P)∧(P∨R)3)((P∨Q)R)((P∧Q)∨R)解：1)重言式；2)矛盾式；3)可满足式
二、（10分）求命题公式（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)∨(P∧R)∨(P∨Q)∨R ((P∨Q)∨(P∨Q))∨(P∧R)∨R 1∨((P∧R)∨R)1 m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7 该式为重言式，全部赋值都是成真赋值。
三、（10分）证明((P∧Q∧A)C)∧(A(P∨Q∨C))(A∧(PQ))C 证明：((P∧Q∧A)C)∧(A(P∨Q∨C))((P∧Q∧A)∨C)∧(A∨(P∨Q∨C))((P∨Q∨A)∨C)∧((A∨P∨Q)∨C)
((P∨Q∨A)∧(A∨P∨Q))∨C ((P∨Q∨A)∧(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∧((P∨Q)∧(P∨Q)))C (A∧((QP)∧(PQ)))C (A∧(PQ))C
四、（10分）个体域为{1，2}，求xy（x+y=4）的真值。
解：xy（x+y=4）x（（x+1=4）∨（x+2=4））
（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+2=4））（0∨0）∧（0∨1）0∧10
五、（10分）对于任意集合A，B，试证明：P(A)∩P(B)=P(A∩B)解：xP(A)∩P(B)，xP(A)且xP(B)，有xA且xB，从而xA∩B，xP(A∩B)，由于上述过程可逆，故P(A)∩P(B)=P(A∩B)
六、（10分）已知A={1，2，3，4，5}和R={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>}，求r(R)、s(R)和t(R)。
解：r(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<3，2>，<4，3>，<4，5>} t(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<1，3>，<2，2>，<2，4>，<1，4>}
七、（10分）设函数f：R×RR×R，R为实数集，f定义为：f(
解：1）
2）
∈R×R，由f( ，通过计算可得x=(p+q)/2；y=(p-q)/2；从而 的原象存在，f是满射。 八、（10分） 证明：1）a，b∈G，ab=a*u*b∈G，运算是封闭的。 2）a，b，c∈G，（ab）c=（a*u*b）*u*c=a*u*（b*u*c）=a（bc），运算是可结合的。 3）a∈G，设E为的单位元，则aE=a*u*E=a，得E=u，存在单位元u。4）a∈G，ax=a*u*x=E，x=u*a*u，则xa=u*a*u*u*a=u=E，每个元素都有逆元。 所以 九、（10分）已知：D= 解：1）D的邻接距阵A和可达距阵P如下： A= 0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1- 1-1 P= 1 1 1 1 十、（10分）求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。 解：最优二叉树为 权＝(2+4)×4+6×3+12×2+(8+10)×3+14×2＝148 离散数学试题(B卷答案4） 一、证明题（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)x(P(x)Q(x))∧xP(x)x(P(x)∧Q(x))证明：x(P(x)Q(x))∧xP(x)x((P(x)Q(x)∧P(x))x((P(x)∨Q(x)∧P(x))x(P(x)∧Q(x))xP(x)∧xQ(x)x(P(x)∧Q(x)) 二、求命题公式(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)M1m0∨m2∨m3 三、推理证明题（10分） 1)(P(QS))∧(R∨P)∧QRS 证明：（1）R 附加前提(2)R∨P P(3)P T(1)(2),I(4)P(QS)P(5)QS T(3)(4),I(6)Q P(7)S T(5)(6),I(8)RS CP 2)x(P(x)∨Q(x))，xP(x)x Q(x)证明：(1)xP(x)P(2)P(c)T(1),US(3)x(P(x)∨Q(x))P(4)P(c)∨Q(c)T(3),US(5)Q(c)T(2)(4),I(6)x Q(x)T(5),EG 四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8（10分）。 证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。 五、已知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） 六、={A1，A2，„，An}是集合A的一个划分，定义R={ 证明：a∈A必有i使得a∈Ai，由定义知aRa，故R自反。a,b∈A，若aRb，则a,b∈Ai，即b,a∈Ai，所以bRa，故R对称。 a,b,c∈A，若aRb 且bRc，则a,b∈Ai及b,c∈Aj。因为i≠j时Ai∩Aj=，故i=j，即a,b,c∈Ai，所以aRc，故R传递。 总之R是A上的等价关系。 七、若f:A→B是双射，则f:B→A是双射（15分）。 证明:对任意的x∈A，因为f是从A到B的函数，故存在y∈B，使 对任意的x∈A，若存在y1,y2∈B，使得 因此f是双射。 八、设 证明 假设A≠G且B≠G，则存在aA，aB，且存在bB，bA（否则对任意的aA，aB，从而AB，即A∪B＝B，得B＝G，矛盾。） 对于元素a*bG，若a*bA，因A是子群，aA，从而a *(a*b)＝b A，所以矛盾，故a*bA。同理可证a*bB，综合有a*bA∪B＝G。综上所述，假设不成立，得证A＝G或B＝G。 九、若无向图G是不连通的，证明G的补图G是连通的（10分）。 证明 设无向图G是不连通的，其k个连通分支为G1、G2、„、Gk。任取结点u、v∈G，若u和v不在图G的同一个连通分支中，则[u，v]不是图G的边，因而[u，v] 1-1-1 -1-1-1-1是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支Gi（1≤i≤k）中，在不同于Gi的另一连通分支上取一结点w，则[u，w]和[w，v]都不是图G的边，因而[u，w]和[w，v]都是G的边。综上可知，不管那种情况，u和v都是可达的。由u和v的任意性可知，G是连通的。 离散数学试题（B卷答案5） 一、（10分）求命题公式(P∧Q)(PR)的主合取范式。 解：(P∧Q)(PR)（(P∧Q)(PR)）∧（(PR)(P∧Q)）（(P∧Q)∨(P∧R)）∧（(P∨R)∨(P∨Q)）(P∧Q)∨(P∧R)(P∨R)∧（Q∨P）∧（Q∨R） (P∨Q∨R)∧(P∨Q∨R)∧（P∨Q∨R）∧（P∨Q∨R）M1∧M3∧M4∧M5 二、（8分）叙述并证明苏格拉底三段论 解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。符号化：F（x）：x是一个人。G（x）：x要死的。A：苏格拉底。命题符号化为x（F（x）G（x）），F（a）G（a）证明： （1）x(F(x)G(x))P（2）F(a)G(a)T(1),US（3）F(a)P（4）G(a)T(2)(3),I 三、（8分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)证明：∵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） 四、（10分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。 解：x∈A，因为R和S是自反关系，所以 x、y∈A，若 x、y、z∈A，若 总之R∩S是等价关系。 2）因为x∈[a]R∩S 五、(10分)设A＝{a，b，c，d}，R是A上的二元关系，且R＝{ 解 r(R)＝R∪IA＝{ t(R)＝R＝{ 4232-1d>， 六、(15分)设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×CB×D且 证明：1）先证h是满射。 2）再证h是单射。 到D的双射，所以a1＝a2，c1＝c2，所以 综合1）和2），h是双射。 七、(12分)设 证明： a,b∈H有b∈H，所以a*b∈H。a∈H，则e=a*a∈H a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*（b）∈H ∵HG且H≠,∴*在H上满足结合律 ∴ 八、（10分）设G= 解：设G的每个结点的度数都大于等于6，则2|E|=d(v)≥6|V|，即|E|≥3|V|，与简单无向平面图的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。九.G= 1-1 -1-1-1-1-1 -1-1（1）G是否为阿贝尔群？ （2）找出G的单位元；（3）找出G的幂等元（4）求b的逆元和c的逆元 解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b)(b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c)所以G是阿贝尔群 （2）因为a*a=a a*b=b*a=b a*c=c*a=c 所以G的单位元是a（3）因为a*a=a 所以G的幂等元是a（4）因为b*c=c*b=a，所以b的逆元是c且c的逆元是b 十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。 解：最优二叉树为 权＝148 离散数学试题（B卷答案6） 一、（20分）用公式法判断下列公式的类型：(1)(P∨Q)(PQ)(2)(PQ)(P∧(Q∨R))解：（1）因为(P∨Q)(PQ)(P∨Q)∨(P∧Q)∨(P∧Q) (P∧Q)∨(P∧Q)∨(P∧Q)m1∨m2∨m3 M0 所以，公式(P∨Q)(PQ)为可满足式。 （2）因为(PQ)(P∧(Q∨R))((P∨Q))∨(P∧Q∧R)) (P∨Q)∨(P∧Q∧R)) (P∨Q∨P)∧(P∨Q∨Q)∧(P∨Q∨R)(P∨Q)∧(P∨Q∨R) (P∨Q∨(R∧R))∧(P∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)M0∧M1 m2∨m3∨m4∨m5∨m6∨m7 所以，公式(PQ)(P∧(Q∨R))为可满足式。 二、（15分）在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋 又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。 解：论域：所有人的集合。Q(x)：x是勤奋的；H(x)：x是身体健康的；S(x)：x是科学家；C(x)：x是事业获得成功的人；F(x)：x是事业半途而废的人；则推理化形式为： x(S(x)H(x))Q(x))，x(Q(x)∧H(x)C(x))，x(S(x)∧x(C(x)∨F(x))下面给出证明： (1)x(S(x)∧H(x)) P(2)S(a)∧H(a) T(1)，ES(3)x(S(x)Q(x)) P(4)S(a)Q(a) T(1)，US(5)S(a) T(2)，I(6)Q(a) T(4)(5)，I(7)H(a) T(2)，I(8)Q(a)∧H(a) T(6)(7)，I(9)x(Q(x)∧H(x)C(x)) P(10)Q(a)∧H(a)C(a) T(9)，Us(11)C(a) T(8)(10)，I(12)xC(x) T(11)，EG(13)x(C(x)∨F(x)) T(12)，I 三、（10分）设A＝{，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)B。解 P(A)＝{，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}} P(B)－{0}＝{，{0}，{{0}}，{0，{0}}－{0}＝{，{0}，{{0}}，{0，{0}} P(B)B＝{，{0}，{{0}}，{0，{0}}{0，{0}}＝{，0，{{0}}，{0，{0}} 四、（15分）设R和S是集合A上的任意关系，判断下列命题是否成立？(1)若R和S是自反的，则R*S也是自反的。(2)若R和S是反自反的，则R*S也是反自反的。(3)若R和S是对称的，则R*S也是对称的。 (4)若R和S是传递的，则R*S也是传递的。(5)若R和S是自反的，则R∩S是自反的。(6)若R和S是传递的，则R∪S是传递的。 解 (1)成立。对任意的a∈A，因为R和S是自反的，则 (2)不成立。例如，令A＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，则R和S是反自反的，但R*S＝{<1，1>}不是反自反的。 (3)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，则R和S是对称的，但R*S＝{<1，3>，<3，2>}不是对称的。 (4)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，3>，<1，3>}，S＝{<2，3>，<3，1>，<2，1>}，则R和S是传递的，但R*S＝{<1，3>，<1，1>，<2，1>}不是传递的。 (5)成立。对任意的a∈A，因为R和S是自反的，则 五、（15分）令X＝{x1，x2，„，xm}，Y＝{y1，y2，„，yn}。问(1)有多少个不同的由X到Y的函数？ (2)当n、m满足什么条件时，存在单射，且有多少个不同的单射？(3)当n、m满足什么条件时，存在双射，且有多少个不同的双射？ 解 (1)由于对X中每个元素可以取Y中任一元素与其对应，每个元素有n种取法，所以不同的函数共nm个。 (2)显然当|m|≤|n|时，存在单射。由于在Y中任选m个元素的任一全排列都形成X到 mY的不同的单射，故不同的单射有Cnm!＝n(n－1)(n―m―1)个。 (3)显然当|m|＝|n|时，才存在双射。此时Y中元素的任一不同的全排列都形成X到Y的不同的双射，故不同的双射有m!个。 六、（5分）集合X上有m个元素，集合Y上有n个元素，问X到Y的二元关系总共有多少个？ 解 X到Y的不同的二元关系对应X×Y的不同的子集，而X×Y的不同的子集共有个2mn，所以X到Y的二元关系总共有2mn个。 七、（10分）若 b。 证明 设e是群 － － －所以，x＝a1*b是a*x＝b的解。－若x∈G也是a*x＝b的解，则x＝e*x＝(a1*a)*x＝a1*(a*x)＝a1*b＝x。所以，x － － －＝a1*b是a*x＝b的惟一解。－ 八、（10分）给定连通简单平面图G＝ 证明 由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是d(f)＝2|E|＝ fF24。若存在f∈F，使得d(f)＞3，则3|F|＜2|E|＝24，于是|F|＜8，与|F|＝8矛盾。故对任意f∈F，d(f)＝3。 离散数学试题（B卷答案7） 一、（15分）设计一盏电灯的开关电路，要求受3个开关A、B、C的控制：当且仅当A和C同时关闭或B和C同时关闭时灯亮。设F表示灯亮。 (1)写出F在全功能联结词组{}中的命题公式。(2)写出F的主析取范式与主合取范式。 解 (1)设A：开关A关闭；B：开关B关闭；C：开关C关闭；F＝(A∧C)∨(B∧C)。在全功能联结词组{}中： A(A∧A)AA A∧C(A∧C)(AC)(AC)(AC) A∨B(A∧B)((AA)∧(BB))(AA)(BB)所以 F((AC)(AC))∨((BC)(BC))(((AC)(AC))((AC)(AC)))(((BC)(BC))((BC)(BC)))(2)F(A∧C)∨(B∧C) (A∧(B∨B)∧C)∨((A∨A)∧B∧C)(A∧B∧C)∨(A∧B∧C)∨(A∧B∧C)∨(A∧B∧C)m3∨m5∨m7 主析取范式 M0∧M1∧M2∧M4∧M6 主合取范式 二、（10分）判断下列公式是否是永真式？(1)(xA(x)xB(x))x(A(x)B(x))。(2)(xA(x)xB(x))x(A(x)B(x)))。解 (1)(xA(x)xB(x))x(A(x)B(x))(xA(x)∨xB(x))x(A(x)B(x))(xA(x)∨xB(x))∨x(A(x)∨B(x))(xA(x)∧xB(x))∨xA(x)∨xB(x)(xA(x)∨xA(x)∨xB(x))∧(xB(x)∨xA(x)∨xB(x))x(A(x)∨A(x))∨xB(x)T 所以，(xA(x)xB(x))x(A(x)B(x))为永真式。 (2)设论域为{1，2}，令A(1)＝T；A(2)＝F；B(1)＝F；B(2)＝T。 则xA(x)为假，xB(x)也为假，从而xA(x)xB(x)为真；而由于A(1)B(1)为假，所以x(A(x)B(x))也为假，因此公式(xA(x)xB(x))x(A(x)B(x))为假。该公式不是永真式。 三、（15分）设X为集合，A＝P(X)－{}－{X}且A≠，若|X|＝n，问(1)偏序集 (3)偏序集 偏序集 考察P(X)的哈斯图，最底层的顶点是空集，记作第0层，由底向上，第一层是单元集，第二层是二元集，…，由|X|＝n，则第n－1层是X的n－1元子集，第n层是X。偏序集 相比，恰好缺少第0层和第n层。因此 四、（10分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，－ <4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，i11>，<5，4>，<5，5>}。 五、（10分）设函数g：A→B，f：B→C，(1)若fg是满射，则f是满射。(2)若fg是单射，则g是单射。 证明 因为g：A→B，f：B→C，由定理5.5知，fg为A到C的函数。 (1)对任意的z∈C，因fg是满射，则存在x∈A使fg(x)＝z，即f(g(x))＝z。由g：A→B可知g(x)∈B，于是有y＝g(x)∈B，使得f(y)＝z。因此，f是满射。 (2)对任意的x1、x2∈A，若x1≠x2，则由fg是单射得fg(x1)≠fg(x2)，于是f(g(x1))≠f(g(x2))，必有g(x1)≠g(x2)。所以，g是单射。 六、（10分）有幺元且满足消去律的有限半群一定是群。 证明 设 考虑a，a2，„，ak，„。因为G只有有限个元素，所以存在k＞l，使得ak＝al。令m＝k－l，有al*e＝al*am，其中e是幺元。由消去率得am＝e。 于是，当m＝1时，a＝e，而e是可逆的；当m＞1时，a*am-1＝am-1*a＝e。从而a是可逆的，其逆元是am-1。总之，a是可逆的。 七、（20分）有向图G如图所示，试求：(1)求G的邻接矩阵A。 (2)求出A2、A3和A4，v1到v4长度为1、2、3和4的路有多少？ (3)求出ATA和AAT，说明ATA和AAT中的第(2，2)元素和第(2，3)元素的意义。(4)求出可达矩阵P。(5)求出强分图。 解 (1)求G的邻接矩阵为： 00A00101011 101100(2)由于 002A001110220130A0211102011120322044A 031201012313 2322所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。(3)由于 00ATA000002131212TAA 21011102132110 2121再由定理10.19可知，所以ATA的第(2，2)元素为3，表明那些边以v2为终结点且具有不同始结点的数目为3，其第(2，3)元素为0，表明那些边既以v2为终结点又以v3为终结点，并且具有相同始结点的数目为0。AAT中的第(2，2)元素为2，表明那些边以v2为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以v2为始结点又以v3为始结点，并且具有相同终结点的数目为1。 (4)00B4AA2A3A40000所以求可达矩阵为P0000(5)因为PPT0010100110+10101000111111。 11111111101111∧1111111100001110＝01110111000111，所以{v1}，{v2，v3，v4} 111111因 1110 2010 + 1110 0110 2120312204+ 2120320101231323220 000 为 741 747，747 434构成G的强分图。 离散数学试题（B卷答案8） 一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R 证明 因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。(1)R 附加前提(2)PR P(3)P T(1)(2)，I(4)P∨Q P(5)Q T(3)(4)，I(6)QS P(7)S T(5)(6)，I(8)RS CP(9)S∨R T(8)，E 二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。 设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))x(P(x)∧B(x))。 (1)x(P(x)Q(x)) P(2)x(P(x)∨Q(x)) T(1)，E(3)x(P(x)∧Q(x)) T(2)，E(4)P(a)∧Q(a) T(3)，ES(5)P(a) T(4)，I(6)Q(a) T(4)，I(7)x(P(x)(A(x)∨B(x)) P(8)P(a)(A(a)∨B(a)) T(7)，US(9)A(a)∨B(a) T(8)(5)，I(10)x(A(x)Q(x)) P (11)A(a)Q(a) T(10)，US(12)A(a) T(11)(6)，I (13)B(a) T(12)(9)，I(14)P(a)∧B(a) T(5)(13)，I(15)x(P(x)∧B(x)) T(14)，EG 三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。 解 设A、B、C分别表示会打排球、网球和篮球的学生集合。则： |A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|ABC|＝25－20＝5。故，不会打这三种球的共5人。 四、（10分）设A1、A2和A3是全集U的子集，则形如Ai(Ai为Ai或Ai)的集合称 i13为由A1、A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。 证明 小项共8个，设有r个非空小项s1、s2、…、sr(r≤8)。 对任意的a∈U，则a∈Ai或a∈Ai，两者必有一个成立，取Ai为包含元素a的Ai或Ai，则a∈Ai，即有a∈si，于是Usi。又显然有siU，所以U＝si。 i1i1i1i1i13rrrr任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp∩sq＝。 综上可知，{s1，s2，…，sr}是U的一个划分。 五、（15分）设R是A上的二元关系，则：R是传递的R*RR。 证明 (5)若R是传递的，则 反之，若R*RR，则对任意的x、y、z∈A，如果xRz且zRy，则 六、（15分）若G为连通平面图，则n－m＋r＝2，其中，n、m、r分别为G的结点数、边数和面数。 证明 对G的边数m作归纳法。 当m＝0时，由于G是连通图，所以G为平凡图，此时n＝1，r＝1，结论自然成立。假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。 设e是G的一条边，从G中删去e后得到的图记为G，并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论： 若e为割边，则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1＋n2＝n＝n，m1＋m2＝m＝m－1，r1＋r2＝r＋1＝r＋1。由归纳假设有n1－m1＋r1＝2，n2－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。 若e不为割边，则n＝n，m＝m－1，r＝r－1，由归纳假设有n－m＋r＝2，从而n－(m－1)＋r－1＝2，即n－m＋r＝2。 由数学归纳法知，结论成立。 七、（10分）设函数g：A→B，f：B→C，则：(1)fg是A到C的函数； (2)对任意的x∈A，有fg(x)＝f(g(x))。 证明 (1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使 对任意的x∈A，若存在y1、y2∈C，使得 综上可知，fg是A到C的函数。 (2)对任意的x∈A，由g：A→B是函数，有 八、（15分）设 证明 对于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以 － － 若 － － －a>∈R。 若 － － －1*b)*(b1*c)＝a1*c∈H，故 对于任意的b∈[a]R，有 －于是b∈aH，[a]RaH。对任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H， 离散数学试题（B卷答案9） 一、（10分）证明(P∧Q∧AC)∧(AP∨Q∨C)(A∧(PQ))C。证明：(P∧Q∧AC)∧(AP∨Q∨C)(P∨Q∨A∨C)∧(A∨P∨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。 二、（10分）举例说明下面推理不正确：xy(P(x)Q(y))，yz(R(y)Q(z))xz(P(x)R(z))。 解：设论域为{1，2}，令P(1)＝P(2)＝T；Q(1)＝Q(2)＝T；R(1)＝R(2)＝F。则： xy(P(x)Q(y))x((P(x)Q(1))∨(P(x)Q(2))) ((P(1)Q(1))∨(P(1)Q(2)))∧((P(2)Q(1))∨(P(2)Q(2)))((TT)∨(TT))∧((TT)∨(TT))T yz(R(y)Q(z))y((R(y)Q(1))∨(R(y)Q(2))) ((R(1)Q(1))∨(R(1)Q(2)))∧((R(2)Q(1))∨(R(2)Q(2))) ((FT)∨(FT))∧((FT)∨(FT)) T 但 xz(P(x)R(z))x((P(x)R(1))∧(P(x)R(2)))((P(1)R(1))∧(P(1)R(2)))∨((P(2)R(1))∧(P(2)R(2)))((TF)∧(TF))∨((TF)∧(TF))F 所以，xy(P(x)Q(y))，yz(R(y)Q(z))xz(P(x)R(z))不正确。 三、（15分）在谓词逻辑中构造下面推理的证明：所有牛都有角，有些动物是牛，所以，有些动物有角。 解：令P(x)：x是牛；Q(x)：x有角；R(x)：x是动物；则推理化形式为： x(P(x)Q(x))，x(P(x)∧R(x))x(Q(x)∧R(x))下面给出证明： (1)x(P(x)∧R(x)) P(2)P(a)∧R(a) T(1)，ES(3)x(P(x)Q(x)) P(4)P(a)Q(a) T(3)，US(5)P(a) T(2)，I(6)Q(a) T(4)(5)，I(7)R(a) T(2)，I(8)Q(a)∧R(a) T(6)(7)，I(9)x(Q(x)∧R(x)) T(8)，EG 四、（10分）证明(A∩B)×(C∩D)＝(A×C)∩(B×D)。 证明：因为 五、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，－ <4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，i11>，<5，4>，<5，5>}。 六、（10分）若函数f：A→B是双射，则对任意x∈A，有f1(f(x))＝x。 －证明 对任意的x∈A，因为f：A→B是函数，则 －由f－1是B到A的函数，于是可写为f1(f(x))＝x。 － 七、（10分）若G为有限群，则|G|＝|H|·[G:H]。 证明 设[G:H]＝k，a1、a2、…、ak分别为H的k个左陪集的代表元，由定理8.38得 G[ai]RaiH i1i1kk又因为对H中任意不同的元素x、y∈H及a∈G，必有a*x≠a*y，所以|a1H|＝…＝|akH|＝|H|。因此 |G||aiH|i1k|aH|k|H|＝|H|·[G:H]。 ii1k 八、（20分）（1）画出3阶2条边的所有非同构有向简单图。 解：由握手定理可知，所画的有向简单图各结点度数之和为4，且最大出度和最大入度均小于或等于2。度数列与入度列、出度列为： 1、2、1：入度列为0、1、1或0、2、0或1、0、1；出度列为1、1、0或1、0、1或0、2、0 2、2、0：入度列为1、1、0；出度列为1、1、0 四个所求有向简单图如图所示。 （2）设G是n(n≥4)阶极大平面图，则G的最小度≥3。 证明 设v是极大平面图G的任一结点，则v在平面图G－{v}的某个面f内。由于G－{v}是一个平面简单图且其结点数大于等于3，所以d(f)≥3。由G的极大平面性，v与f上的结点之间都有边，因此d(v)≥3。由v的任意性可得，G的最小度≥3。 离散数学试题（B卷答案10） 一、（10分）使用将命题公式化为主范式的方法，证明(PQ)(P∧Q)(QP)∧(P∨Q)。 证明：因为(PQ)(P∧Q)(P∨Q)∨(P∧Q) (P∧Q)∨(P∧Q)(QP)∧(P∨Q)(Q∨P)∧(P∨Q)(P∧Q)∨(Q∧Q)∨(P∧P)∨(P∧Q)(P∧Q)∨P (P∧Q)∨(P∧(Q∨Q))(P∧Q)∨(P∧Q)∨(P∧Q)(P∧Q)∨(P∧Q)所以，(PQ)(P∧Q)(QP)∧(P∨Q)。 二、（10分）证明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。 解 设A：A努力工作；B、C、D分别表示B、C、D愉快；则推理化形式为： AB∨C，BA，DCAD (1)A 附加前提(2)AB∨C P(3)B∨C T(1)(2)，I(4)BA P(5)AB T(4)，E(6)B T(1)(5)，I(7)C T(3)(6)，I (8)DC P(9)D T(7)(8)，I(10)AD CP 三、（10分）证明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)) 四、（10分）设A＝{，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)B。解 P(A)＝{，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}} P(B)－{0}＝{，{0}，{{0}}，{0，{0}}－{0}＝{，{0}，{{0}}，{0，{0}} P(B)B＝{，{0}，{{0}}，{0，{0}}{0，{0}}＝{，0，{{0}}，{0，{0}} 五、（15分）设X＝{1，2，3，4}，R是X上的二元关系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)画出R的关系图。(2)写出R的关系矩阵。 (3)说明R是否是自反、反自反、对称、传递的。解(1)R的关系图如图所示：(2)R的关系矩阵为： 10M(R)111011101100 00(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的； 经过计算可得 10M(R2)111011101100M(R)，所以R是传递的。00 六、（15分）设函数f：R×RR×R，f定义为：f( (4)求复合函数ff和ff。 证明(1)对任意的x，y，x1，y1∈R，若f( (2)对任意的 1uwuwuwuw，y＝，则f( －1 ( xyxy，2xy(xy)>＝ 七、（15分）给定群 证明 对G中任意元a和b。 因为a*b＝(a*b)，所以a*a*b*b＝a*(a*b)*b，即得a*b＝(b*a)。同33 333 2255 13 111理，由a*b＝(a*b)可得，a*b＝(b*a)。由a*b＝(a*b)可得，a*b＝(b*a)。 于是(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。同理可得，(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。 3333334 344433555444 由于(a*b)*b＝a*b＝b*a＝b*(b*a)＝b*(a*b)＝(b*a)*b，故a*b＝b*a。 八、（15分）（1）证明在n个结点的连通图G中，至少有n－1条边。 证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。设G中结点为v1、v2、„、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、„、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、„、vn1中的某个结点相邻，得新边en1，由此可见G中至少有n－1条边。 （2）试给出|V|＝n，|E|＝(n－1)(n－2)的简单无向图G＝ 解 下图满足条件但不连通。 12344333 临沂大学2015—2016学第1学期 离散数学单元测试试题一 (适用于2014级计算机科学与技术、软件工程、网络工程专业本科学生) 一、选择题(共10题，每题3分，共30分)1.下列语句中为命题的是（D)。A.这朵花是谁的？ B.这朵花真美丽啊！C.这朵花是你的吗？ D.这朵花是他的。 2.若p：他聪明；q：他用功；则“他虽聪明，但不用功”，可符号化为(B)。A.p∨q B.p∧┐q C.p→┐q D.p∨┐q 3.命题公式p∨q→q的公式类型为（D)。A.矛盾式 B.非重言可满足式 C.重言式 D.条件式 4.若F(x)：x是有理数，G(x)：x能被2整除，则“有的有理数能被2整除”，可符号化为（A)。 A.x(F(x)∧G(x)) B.F(x)∧G(x) C.xF(x) D.xG(x)5.设F(x)表示x是火车，G(x)表示y是汽车，H(x，y)表示x比y快，命题“某些汽车比所有火车慢”的符号化公式是（B)。 A.y(G(y)→x(F(x)∧H(x,y)))B.y(G(y)∧x(F(x)→H(x,y)))C.xy(G(y)→(F(x)∧H(x,y)))D.y(G(y)→(x)(F(x)→H(x,y)))6．设集合A={1,2,3},A上的关系R={<1,2>,<1,3>,<3,3>},则R具有(D)。A.自反性 B.传递性 C.对称性 D.以上答案都不对 ######7.谓词公式x(P(x)∨yR(y))→Q(x)中的 x是(C)。A.自由变元 B.约束变元 C.既是自由变元又是约束变元 D.既不是自由变元又不是约束变元 8.设X、Y是两个集合且|X|＝n，|Y|＝m，则从X到Y可产生(A)个二元关系。A.n m B.mn C.2n m D.nm 9.下列关于集合的表示中正确的为(C)。A.{a}{a,b,c} B.{a}{a,b,c} C.{a,b,c} D.{a,b}{a,b,c} 10．设集合A={1,2,3,4,5},下列哪些是集合A的划分(D)。A.{{1,2},{3,5}} B.{{1,2,3,4},5} C.{ ,{1,2},{3},{4,5}} D.{{1},{2},{3},{4},{5}} 二、填空题(共10空，每空3分，共30分)1.设p：2＋2＝5，q：明天是阴天，则命题“只要2＋2＝5，那么明天是阴天”可符号化为 p->q，其真值是 1。 2.设p:你陪伴我，q:你代我叫车子，r:我出去，则“如果你不陪伴我或不代我叫车子,我就不出去。”的符号化形式为 ¬p/¬q->r。 3.设p: 天下雨，q: 天刮风，r: 我去书店，则“如果天不下雨并且不刮风，我就去书店”的符号化形式为。 4.设S(x)∶x是大学生；K(x)∶x是运动员。则“有些运动员不是大学生”的符号化为。 5.设P(x)：x非常聪明；Q(x):x非常能干；a：小李；则“小李非常聪明且能干”的符号化形式为。 6.设F(x): x是人，G(x): x用右手写字，则“有的人并不用右手写字”的符号化形式为。 7.设S(x)：x是学生；L(x)：x喜欢英语。则“有些学生喜欢英语”的符号化为：。8.在公式x(P(z)→Q(x,z))∧zR(x,z)中，x的辖域是 ，z的辖域是。 三、计算与证明(共2题，每题20分，共40分)1.用等值演算求下公式的主析取范式(p→q)∧r。 2.在命题逻辑自然推理系统中，构造下面推理的证明。前提： p∨q, q→r, p→s, ┐s，结论：r ∧ (p∨q)。第五篇：离散数学单元测试试题1
点击咨询 