全国2010年7月高等教育自学考试离散数学试题
课程代码：02324
一、单项选择题（本大题共15小题，每小题1分，共15分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．下列句子不是命题的是（）
A．中华人民共和国的首都是北京
B．张三是学生
C．雪是黑色的
D．太好了！
2．下列式子不是谓词合式公式的是（）
A．（"x）P(x)→R(y)
B．("x) ┐P（x）T("x)(P(x)→Q(x))
C．("x)($y)(P(x)∧Q(y))→($x)R(x)
D．("x)(P(x,y)→Q(x,z))∨($z)R(x,z)
3．下列式子为重言式的是（）
A．(┐P∧R)→Q
B．P∨Q∧R→┐R
C．P∨(P∧Q)
D．(┐P∨Q)?(P→Q)
4．在指定的解释下，下列公式为真的是（）
A．("x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,论域:{1,2}
B．($x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,论域: {1,2}
C．($x)(P(x) →Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4}
D．("x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4}
5．对于公式("x) ($y)(P(x)∧Q(y))→($x)R(x,y)，下列说法正确的是（）
A．y是自由变元
B．y是约束变元
C．($x)的辖域是R(x, y)
D．("x)的辖域是($y)(P(x)∧Q(y))→($x)R(x,y)
6．设论域为{1,2}，与公式("x)A(x)等价的是（）
A．A(1)∨A(2)
B．A(1)→A(2)
C．A(1)∧A(2)
D．A(2)→A(1)
7．设Z+是正整数集，R是实数集，f:Z+→R, f(n)=log2n ,则f（）
A．仅是入射
B．仅是满射
C．是双射
D．不是函数
8．下列关系矩阵所对应的关系具有反对称性的是（）
9．设R1和R2是集合A上的相容关系，下列关于复合关系R1°R2的说法正确的是（）A．一定是等价关系
B．一定是相容关系
C．一定不是相容关系
D．可能是也可能不是相容关系
10．下列运算不满足交换律的是（）
A．a*b=a+2b
B．a*b=min(a,b)
C．a*b=|a-b|
D．a*b=2ab
11．设A是偶数集合，下列说法正确的是（）
A．
B．
C．
D．
12．设*是集合A上的二元运算，下列说法正确的是（）
A．在A中有关于运算*的左幺元一定有右幺元
B．在A中有关于运算*的左右幺元一定有幺元
C．在A中有关于运算*的左右幺元，它们不一定相同
D．在A中有关于运算*的幺元不一定有左右幺元
15．一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是（）A．13
B．14
C．15
D．16来源:考试大
二、填空题（本大题共10小题，每小题2分，共20分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16．请写出表示德摩根律的两个命题公式等价定理___________，___________。
17．n个命题变元的___________称为小项，其中每个变元与它的否定不能同时出现，但两者必须___________。
18．前提引入规则：在证明的任何步骤上都可以___________，简称___________规则。
19．自由变元代入规则是指对某___________出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且___________。
20．设A=?,B={2,4}，则((A)=___________，A×B___________。
21．设A={1,2,3,4}, A上的二元关系R={<1,2>,<2,4>,<3,3>},S={<1,3>,<2,4>,<4,2>}，则R2°S=___________，(R-1)2=___________。
22．设代数系统
23．在
24．设
三、计算题（本大题共6小题，每小题5分，共30分）
26．给定论域D={1,2}，f(1)=2, f(2)=1, S(1)=F, S(2)=T, G(1,2)=T, G(2,1)=T,在该赋值下，求式子$x(S( f(x))∧G(x, f(x)))的真值。
31．求题31图的最小生成树。
四、证明题（本大题共3小题，第32小题8分，第33、34小题各6分，共20分）
32．用推理方法证明(A∨B)→(C∧D),(D∨F)→E├A→E。
33．证明：设
五、应用题（本大题共2小题，第35小题9分，第36小题6分，共15分）
35．符合化下列命题，并构造推理证明：三角函数都是周期函数，有些三角函数是连续函数，所以有些周期函数是连续函数。
36．两个等价关系的并集不一定是等价关系，试举例说明。
全国2010年4月自学考试离散数学试题
课程代码：02334
一、单项选择题(本大题共15小题，每小题1分，共15分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代
码填写在题后的括号内。错选、多选或未选均不得分。
1.下列句子为命题的是( )
A.全体起立!
B.x=0
C.我在说谎
D.张三生于1886年的春天
2.下列式子不是谓词合式公式的是( )
A.
B.
C.
D.
3.下列式子为矛盾式的是( )
A. B.
C. D.
4.设给定赋值N如下：个体域为自然数集；特定元素a=0；特定函数
f(x,y)=x+y,g(x,y)=xy；特定谓词F(x,y)为x=y。在赋值N下，下列公式为真的是( )
A.
B.
C.
D.
5.对于公式，下列说法正确的是( )
A.y是自由变元
B.x是约束变元
C. 的辖域是
D. 的辖域是P(x,y)
6.设论域为{l，2}，与公式等价的是( )
A.A(1)A(2)
B. A(1)A(2)
C.A(1)
D. A(2)A(1)
7.设Z+是正整数集合，f:Z+→Z+，f(n)=2n-2,则f()
A.仅是入射
B.仅是满射
C.是双射
D.不是函数
8.下列关系矩阵所对应的关系具有反自反性的是( )
A. B.
C. D.
9.设R1和R2是集合A上的相容关系，下列关于的说法正确的是( )
A.一定是相容关系
B.一定不是相容关系
C.可能是也可能不是相容关系
D.一定是等价关系
10.设A是奇数集合，下列构成独异点的是( )
A.
B.
C.
D.
11.设A是整数集，下列说法正确的是( )
A.
B.
C.
D.
12.下列说法不正确的是( )
A.在实数集上，乘法对加法是可分配的
B.在实数集上，加法对乘法是可分配的
C.在某集合的幂集上，∪对∩是可分配的
D.在某集合的幂集上，∩对∪是可分配的
13.右图的最大入度是( )
A.0
B.1
C.2
D.3
14.下列可一笔画成的图形是( )
15.一棵树有5个3度结点，2个2度结点，其它的都是l度结点，那么这棵树的结点数是
( )
A.13
B.14
C.16
D.17
二、填空题(本大题共10小题，每小题2分，共20分)
请在每小题的空格中填上正确答案。错填、不填均不得分。
16.请写出表示分配律的两个命题公式等价定理________,________。
17.n个命题变元的________称为大项，其中每个变元与它的否定不能同时出现，但两者必须________。
18.在谓词推理过程中，由得到P(a)，其中a为论域的某个个体，用的是________规则，记为________规则。
19.请用联结词，表示联结词和联结词：________，________。
20.设A={1，2，3，4}，B={2，4，6}，则A-B=________，A B=________。
21.给出A={l，2}上的一个等价关系________，并给出其对应的划分________。
22.设A={l，2，3，4}，A上的二元关系R={<1，2>，<2，3>，<3，2>}，S={
23.代数系统
24.若图中存在________，它经过图中所有的________，则称该图为汉密尔顿图。
25.n点完全图记为K n，那么当________时，K n是平面图，当_____时，K n是非平面图。
三、计算题(本大题共6小题，每小题5分，共30分)
26.列出
的真值表。
27.用等值演算求(Q R)的主析取范式。
28.设A={1,2,3,4}，给定A上的二元关系R={<1,2>,<2,1>,<2,3>,<3,4>}，求R 的传递闭包。
29.求右图所示格的所有5元和6元子格。
30.求
31.用矩阵的方法求右图中结点v1，v3之间长度为2的路径的数目。
四、证明题(本大题共3小题，第32小题8分，第33、34小题各6分，共20分)
32.用推理方法证明：
。
33.设H是G的非空子集，则
34．证明整数集Z 上的大于等于关系“”是一个偏序关系。
五、综合应用题(本大题共2小题，第35小题6分，第36小题9分，共15分) 35．将下面命题符号化，并构造推理证明：
所有有理数是实数，有些有理数是整数，所以有些实数是整数。
36．某城市拟在六个区之间架设有线电话网，其网点间的距离如下列有权矩阵给出，请绘出有权图，给出架设线路的最优方案，并计算线路的总长度。
全国2009年7月自考离散数学试题
课程代码：02324
一、单项选择题(本大题共15小题，每小题1分，共15分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.下列句子为命题的是( )
A.走，看电影去
B.x+y>0
C.空集是任意集合的真子集
D.你明天能来吗?
2.下列式子不是谓词合式公式的是( )
A.(x)(P(x)→(?x)(Q(x) ∧A(x，y)))
B.(x)∧(?y)∨P(x，y)
C.(x)P(x)→R(y)
D.(?x)P(x)∧Q(y，z)
3.下列式子为重言式的是( )
A.P→P∨Q
B.(﹁P∧Q)∧(P∨﹁Q)
C.﹁ (P Q)
D.(P∨Q)(P→Q)
4.设个体域为实数集，特定元素a=0，函数f(x，y)=x-y，特定谓词F(x，y)为x A.(x)(y)F(x，f(f(x，y)，y)) B.(x)(y)(﹁F(f(x，y)，x)) C.(x)(y)(z)(F(x，y)→F(f(x，z)，f(y，z))) D.(x)F(f(a，x)，a) 5.对于公式(x)(y)P(x，y)∨Q(x，z)∧(?x)P(x，y)，下列说法正确的是( ) A.x是自由变元 B.x是约束变元 C.(x)的辖域是P(x，y)∨Q(x，z) D.(x)的辖域是P(x，y) 6.设论域为{1，2}，与公式(x)﹁A(X)等价的是( ) A. ﹁A(1) ∨﹁A(2) B. ﹁A(1)→﹁(A2) C. ﹁A(1) ∧﹁A(2) D. A(1) →A(2) 7.设Z+是正整数集，f：Z+×Z+→Z+，f(n，m)=nm，则f( ) A.仅是入射 B.仅是满射 C.是双射 D.不是函数 8.下列哪个关系矩阵所对应的关系具有自反性( ) A. B. C. D. 9.设R1和R2是集合A上的相容关系，下列关系哪个可能不是相容关系( ) A.R1R2 B.Rl R2 C.R1-1 D.Rl R2 10.在整数集上，下面哪个运算不是二元运算( ) A.加法 B.减法 C.乘法 D.除法 11.设A是奇数集合，×为乘法运算，则 A.半群 B.群 C.循环群 D.交换群 12.下面不满足结合律的运算是( ) A.a*b=min(a，b) B.a*b=max(a，b) C.a*b=2(a+b) D.a*b=2ab 13.右图的最小入度是( ) A.0 B.1 C.2 D.3 14.下面既是汉密尔顿图又是欧拉图的图形是( ) 15.一棵树有3个5度点、1个4度点、3个2度点，其它的都是1度，那么它的边数是( ) A.17 B.18 C.19 D.20 二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.设命题变元为P，Q，R，则小项m100=________，大项M010=________。 17.置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以 ________，记为________规则。 18.一个公式，如果量词均在全式的________，其作用域延伸到整个公式的 ________，则该公式称为前束范式。 19.请用联结词﹁，∧表示联结词∨和联结词：________，________。 20.设A={l，2，3，4}，A上的二元关系R={<1，2>，<3，4>，<4，3>}，S={ 21.代数系统 22.在实数集R上定义运算a b=a+b+ab，则幺元为________，元素2的逆元为 ________。 23.若回路中，除________外________各不相同，则此回路称为圈(或初级回路)。 24.偶图记为Kn,m那么当________时，Kn,m是平面图，当________时，Kn,m是非平面图。 25.若图中存在________，它经过图中所有的边恰好________次，则称该图为欧拉图。 三、计算题(本大题共6小题，每小题5分，共30分) 26.用等值演算求(P→Q)→R的主合取范式。 27.列出(P→(Q∨R)) (P→Q)的真值表。 28．设A={a,b,c,d}，R={ 29.设A={2，3，6，12，24，36}，请画出A上整除关系的哈斯图，并给出子集{6，12，24，36}的下界、下确界、极大元、最大元。 30.求右图所示格的所有5元子格。 31.用矩阵的方法求右图中结点u2，u5之间长为2的路径的数目。 四、证明题(本大题共3小题，第32小题8分，第33、34小题各6分，共20分) 32.用推理方法证明：P∨Q，P→R，Q→S├R∨S。 33.设A={ 34．证明：一个图是强连通的，当且仅当图中有一个回路，它至少包含每个结点一次。 五、综合应用题（本大题共2小题，第35小题6分，第36小题9分，共15分） 35．符号化下面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的。 36．设H是G的有限子集，则 全国2009年4月高等教育自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 2．下列语句中是真命题的是（） A．我正在说谎 B．严禁吸烟 C．如果1+2=3，那么雪是黑的 D．如果1+2=5，那么雪是黑的 3．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（）A．? P∧? Q B．? P∨? Q C．?（P?Q） D．?（? P∨? Q） 4．命题公式（P∧（P→Q））→Q是（） A．矛盾式 B．蕴含式 C．重言式 D．等价式 5．命题公式?（P∧Q）的成真指派是（） A．000，001，110， B．001，011，101，110，111 C．全体指派 D．无 6．在公式（）F（x，y）→（ y）G（x，y）中变元x是（） A．自由变元 B．约束变元 C．既是自由变元，又是约束变元 D．既不是自由变元，又不是约束变元 7．集合A={1，2，…，10}上的关系R={ A．自反的 B．对称的 C．传递的、对称的 D．反自反的、传递的 8．若R和S是集合A上的两个关系，则下述结论正确的是（） A．若R和S是自反的，则R∩S是自反的 B．若R和S是对称的，则R S是对称的 C．若R和S是反对称的，则R S是反对称的 D．若R和S是传递的，则R∪S是传递的 9．R={<1，4>，<2，3>，<3，1>，<4，3>}，则下列不是t（R）中元素的是（）A．<1，1> B．<1，2> C．<1，3> D．<1，4> 10．设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的是（）A．1∈A B．{1，2，3} A C．{{4，5}} A D．?∈A 11．在自然数集N上，下列运算是可结合的是（） A．a*b=a-2b B．a*b=min{a，b} C．a*b=-a-b D．a*b=|a-b| 12．在代数系统中，整环和域的关系是（） A．整环一定是域 B．域不一定是整环 C．域一定是整环 D．域一定不是整环 13．下列所示的哈斯图所对应的偏序集中能构成格的是（） A． B． C． D． 14．设G为有n个结点的简单图，则有（） A．Δ(G)＜n B．Δ(G)≤n C．Δ(G)＞n D．Δ(G)≥n 15．具有4个结点的非同构的无向树的数目是（） A．2 B．3 C．4 D．5 二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16．（）（y）（P（x，y）Q（y，z））∧xP（x，y）中的辖域为________，x的辖域为________。 17．两个重言式的析取是________式，一个重言式与一个矛盾式的析取是 ________式。 18．设N是自然数集合，f和g是N到N的函数，且f（n）=2n+1，g（n）=n2，那么复合函数（f f）（n）=________（g f）（n）=________。 19．设复合函数g f是从A到C的函数，如果g f是满射，那么________必是 满射，如果g f是入射，那么________必是入射。 20．设A={1，2}，B={2，3}，则A-A=________，A-B=________。 21．设S是非空有限集，代数系统 22．在 23．设 24．在下图中，结点v2的度数是________。 25．设图D= 三、计算题（本大题共5小题，第26、27小题各5分，第28、29小题各6分，第30小题8分，共30分） 26．已知A={{?}，{?，1}}，B={{?，1}，{1}}，计算A∪B，A B，A的幂集P（A）。27．构造命题公式（（P∧Q）→P）∨R的真值表。 28．下图给出了一个有向图。（1）求出它的邻接矩阵A；（2）求出A2，A3，A4及可达矩阵P。 29．求下列公式的主合取范式和主析取范式：P∨（? P→（Q∨（? Q→R）））30．设A={1，2，3，4，6，8，12，24}，R为A上的整除关系，试画 四、证明题（本大题共3小题，第31、32小题各6分，第33小题8分，共20分） 31．在整数集Z上定义：，证明： 33．证明：边e是图G的一条割边，当且仅当图G中不存在包含边e的简单回路。 五、应用题（本大题共2小题，第34小题6分，第35小题9分，共15分）34．构造下面推理的证明。 如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。 35．今有n个人，已知他们中任何2人的朋友合起来一定包含其余n-2人。试证 明： （1）当n≥3时，这n个人能排成一列，使得中间任何人是其两旁的人的朋友，而两头的人是其左边（或右边）的人的朋友。 （2）当n≥4时，这n个人能排成一圆圈，使得每个人是其两旁的人的朋友。 全国2008年7月高等教育自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）A．? P∧Q B．P∧? Q C．P→? Q D．P∨? Q 2．下面联结词运算不可交换的是（） A．∧ B．→ C．∨ D． 3．下列命题公式不是重言式的是（） A．Q→（P∨Q） B．（P∧Q）→P C．?（P∧? Q）∧（? P∨Q） D．（P→Q）（? P∨Q） 4．下列等价式不正确的是（） A． B． C． D． 5．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（） A． B．?? B（x）） C．? D．?? B(x)) 6．设M={x|f1(x)=0},N={x|f2(x)=0}，则方程f1(x)〃f2(x)=0的解为（）A．M∩N B．M∪N C．M N D．M-N 7．设A-B=?，则有（） A．B=? B．B≠? C．A B D．A B 8．A，B是集合，P（A），P（B）为其幂集，且A∩B=?，则P(A)∩P(B)为（）A．? B．{?} C．{{?}} D．{?，{?}} 9．设集合A={1，2，3，……，10}，下列定义的运算关于集合A是不封闭的是（） A．x*y=max{x,y} B．x*y=min{x,y} C．x*y=GCD{x,y},即x,y的最大公约数 D．x*y=LCM{x,y},即x,y的最小公倍数 10．设H，K是群（G，）的子群，下面代数系统是（G，）的子群的是（）A．（H∩K，） B．（H∪K，） C．（K-H，） D．（H-K，） 11．设A={1，2，3，4，5}，B={6，7，8，9，10}，以下关系是从A到B的入射函数的是（） A．f ={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>} B．f ={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>} C．f ={<1,6>,<2,7>,<4,9>,<3,8>} D．f ={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>} 12．设简单图G所有结点的度数之和为12，则G一定有（） A．3条边 B．4条边 C．5条边 D．6条边 13．下列不一定是树的是（） A．无回路的连通图 B．有n个结点，n-1条边的连通图 C．每对结点之间都有通路的图 D．连通但删去一条边则不连通的图 14．下面关于关系R的传递闭包t(R)的描述最确切的是（） A．t(R)是包含R的二元关系 B．t(R)是包含R的最小传递关系 C．t(R)是包含R的一个传递关系 D．t(R)是任何包含R的传递关系 15．欧拉回路是（） A．路径 B．迹 C．既是初级回路也是迹 D．既非初级回路也非迹 二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16．设A={1，2}，B={2，3}，则A A=__________，A B=__________。 17．设A={1，2，3，4}上关系R={<1,2>,<2,4>,<3,3>,<1,3>}，则R的自反闭包r(R)= _________，对称闭包S（R）=__________。 18．命题公式（P∧Q）→ù P的成真指派为__________，成假指派为__________。19．公式（）（F（x）→G(y)）→(y)(H(x))中的自由变元为_________，约束变元为__________。 20．设f :R→R,f (x)=x2-2,g:R→R,g(x)=x-1,那么复合函数 =__________，=__________。 21．有理数集Q中的*运算定义如下：a*b=a+b-ab，则*运算的单位元是 __________，设a有逆元，则其逆元a-1=__________。 22．设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},那么dom(A∪ B)=_______,ran(A∩B)= __________。 23．如下图的有补格中，c的补元是__________，b的补元是__________。 24．在根树中，若每一个结点的出度__________m,则称这棵树为m叉树。如果每一个结点的出度__________m或0，则称这棵树为完全m叉树。 25． 试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统 二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。 《离散数学》试题及答案 一、选择题：本题共5小题，每小题3分，共15分，在每小题给出的四个选项中，只有一项是符合题目要求的。 1. 命题公式Q Q P →∨)(为 ( ) (A) 矛盾式 (B) 可满足式 (C) 重言式 (D) 合取范式 2．设P 表示“天下大雨”， Q 表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（ ）。 (A)． P Q →； (B)．P Q ∧； (C)．P Q ?→?； (D)．P Q ?∨． 3.设集合A ={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是( ) (A) 1A (B) {1,2, 3}A (C) {{4,5}}A (D) A 4. 设A ＝{1,2},B ={a ,b ,c },C ={c ,d }, 则A ×(B C )= ( ) (A) {<1,c >,<2,c >} (B) { 离散数学考试题(后附详细答案) 一、命题符号化（共6小题，每小题3分，共计18分） 1.用命题逻辑把下列命题符号化 a)假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS) b)我今天进城，除非下雨。 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→Q c)仅当你走，我将留下。 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不是有理数 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为： x(R(x) Q(x)) 或x(R(x) →Q(x)) b)对于所有非零实数x，总存在y使得xy=1。 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： x(R(x) E(x,0) →y(R(y) E(f(x,y),1)))) c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b. 设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为：F(f)a(A(a)→b(B(b) E(f(a),b) c(S(c) E(f(a),c) →E(a,b)))) 二、简答题（共6道题，共32分） 1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。 （5分） (P→(Q→R))(R→(Q→P))（PQR）(PQR) (（PQR）→(PQR)) ((PQR) →（PQR）). (（PQR）(PQR)) ((PQR) （PQR）) (PQR)(PQR) 这是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 （PQR（PQR（PQR（PQR（PQR（PQR 2.设个体域为{1,2,3}，求下列命题的真值（4分） a)xy(x+y=4) b)yx (x+y=4) a) T b) F 3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） x(F(x)→G(x))→(xF(x)→xG(x)) x(F(x)→G(x))→(yF(y)→zG(z)) x(F(x)→G(x))→yz(F(y)→G(z)) xyz((F(x)→G(x))→(F(y)→G(z))) 4.判断下面命题的真假，并说明原因。（每小题2分，共4分） 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 离散数学试题（A卷答案） 一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解：(P↓Q)→(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) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，， 《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q →P (2)?Q=>P →Q (3)P=>P →Q (4)?P ∧(P ∨Q)=>?P 答：（1），（4） 2、下列公式中哪些是永真式？( ) (1)(┐P ∧Q)→(Q →?R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q) 答：（2），（3），（4） 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q (4)P ∧(P →Q)=>Q (5) ?(P →Q)=>P (6) ?P ∧(P ∨Q)=>?P 答：（2），（3），（4），（5），（6） 4、公式 x((A(x) B(y ，x)) z C(y ，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1） 是，T （2） 是，F （3） 不是 （4） 是，T （5） 不是 （6） 不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P ：我生病，Q ：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q →? （2） Q P ?→ （3） Q P ?? （4）Q P →? 8、设个体域为整数集，则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（1）对任一整数x 存在整数 y 满足x+y=0（2）存在整数y 对任一整数x 满足x+y=0 9、设全体域D 是正整数集合，确定下列命题的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答：（1） 11、命题“2是偶数或-3是负数”的否定是（ ）。 答：2不是偶数且-3不是负数。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答：（2） 13、公式(?P ∧Q)∨(?P ∧?Q)化简为（ ），公式 Q →(P ∨(P ∧Q))可化简为（ ）。 答：?P ，Q →P 离散数学 2^m*n 一、选择题（2*10） 1．令P：今天下雨了，Q：我没带伞，则命题“虽然今天下雨了，但是我没带伞”可符号化为（）。 （A）P→?Q （B）P∨?Q （C）P∧Q （D）P∧?Q 2．下列命题公式为永真蕴含式的是（）。 （A）Q→（P∧Q）（B）P→（P∧Q） （C）（P∧Q）→P （D）（P∨Q）→Q 3、命题“存在一些人是大学生”的否定是(A)，而命题“所有的人都是要死的”的否定 是（）。 （A）所有人都不是大学生，有些人不会死 （B）所有人不都是大学生，所有人都不会死 （C）存在一些人不是大学生，有些人不会死 （D）所有人都不是大学生，所有人都不会死 4、永真式的否定是（）。 （A）永真式（B）永假式（C）可满足式（D）以上均有可能 5、以下选项中正确的是（）。 （A）0= ? （B）0 ? （C）0∈? （D）0?? 6、以下哪个不是集合A上的等价关系的性质？（） ）。 （A）2 （B）4 （C）3 （D）5 10．连通图G是一棵树，当且仅当G中（）。 （A）有些边不是割边（B）每条边都是割边 （C）无割边集（D）每条边都不是割边 二、填空题（2*10） 1、命题“2是偶数或-3是负数”的否定是________。 2、设全体域D是正整数集合，则命题?x?y(xy=y)的真值是______。 3、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为 4 5 6、设 7 8 (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下 五、（15分）设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质： 一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，ο〉，Z是整数集，ο定义为xοxy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的 等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={ 1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设 试卷二十三试题与答案 一、单项选择题：（每小题1分，本大题共10分） 1．命题公式)(P Q P ∨→是（ ）。 A 、 矛盾式； B 、可满足式； C 、重言式； D 、等价式。 2．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨?； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 3．谓词公式)())()((x Q y yR x P x →?∨?中的 x 是（ ）。 A 、自由变元； B 、约束变元； C 、既是自由变元又是约束变元； D 、既不是自由变元又不是约束变元。 4．在0 Φ之间应填入（ ）符号。 A 、= ； B 、?； C 、∈； D 、?。 5．设< A ， > 是偏序集，A B ?，下面结论正确的是（ ）。 A 、 B 的极大元B b ∈且唯一； B 、B 的极大元A b ∈且不唯一； C 、B 的上界B b ∈且不唯一； D 、B 的上确界A b ∈且唯一。 6．在自然数集N 上，下列（ ）运算是可结合的。 （对任意N b a ∈,） A 、b a b a -=*； B 、),max(b a b a =*； C 、b a b a 5+=*； D 、b a b a -=*。 7．Q 为有理数集N ，Q 上定义运算*为a*b = a + b – ab ,则 大学2013—2014学年度第二学期期末考试《离散数学》试卷 A 第一部分 选择题（共20 分） 一、单项选择题（本大题共10小题，每题只有一个正确答案，答对一题得2分共20分） 1、对任意集合A 、B 、和C ，下列论断中正确的是： 【 】 A. 若A ∈B ，B ?C ，则A ∈C B. 若A ∈B ，B ?C ，则A ?C C. 若A ?B ，B ∈C ，则A ∈C D. 若A ?B ，B ∈C ，则A ?C 2、设A={a,{a}},下列式子中正确的有： 【 】 A. {a}∈ρ(A) B. a ∈ρ(A) C. {a}?ρ(A) D. 以上都不是 3、P ：我将去镇上。Q ：我有时间。命题“我将去镇上，当且仅当我有时间”符号化为： 【 】A. P →Q B. Q →P C. P ?Q D. Q ∨?P 4、命题公式：（P ∧（P →Q ））→Q 是 【 】 A ．矛盾式 B. 可满足式 C. 重言式 D. 不能确定 5、谓词公式)())()((x Q y yR x P x →?∨?中，量词x ?的辖域是： 【 】 A. ))()((y yR x P x ?∨? B. )(x P C. )(),(x Q x P D. )()(y yR x P ?∨ 6、在如下各图中，哪一个是欧拉图？ 【 】 7、设|V|>1，G= < V , E >是强连通图，当且仅当： 【 】 A ．G 中至少有一条通路 B ．G 中至少有一条回路 C ．G 中有通过每个结点至少一次的通路 D ．G 中有通过每个结点至少一次的回路 8、设}}2,1{},1{,{Φ=S ，则 ρ(S) 有多少个元素？ 【 】 A ．3； B ．6； C ．7； D ．8 ； 9、集合A={1，2，3，4，5，6，7，8，9，10}上的关系R={ 精品文档 离散数学 10.设仃限集丸 B. |A|■申 p|p |p(AxB)| = 带伞”可符号化为( ) (C ) P A Q (D ) P A Q 2 ?下列命题公式为永真蕴含式的是( ) (A ) C H( P A Q ) ( B ) P -( P A Q ) (C ) (P A Q — P ( D (P V Q)— Q 3、 命题“存在一些人是大学生”的否定是(A)，而命题“所有的人都是要死 的”的否定是( )。 (A) 所有人都不是大学生，有些人不会死 (B) 所有人不都是大学生，所有人都不会死 (C) 存在一些人不是大学生，有些人不会死 (D) 所有人都不是大学生，所有人都不会死 4、 永真式的否定是()。 (A )永真式 (B )永假式 (C )可满足式 (D )以上均有可能 5、以下选项中正确的是()。 (A ) 0= ? (B ) 0 ? (C 0€ ? (D ) 0?? 6、以下哪个不是集合A 上的等价关系的性质？( ) (A )自反性 (B )有限性 (C )对称性 (D ) 传递性 7、集合 A={1,2,…;10}上的关系 R={ 离散数学图论部分综合练习 一、单项选择题 1．设无向图G 的邻接矩阵为 ??????? ? ??? ?? ???010 1010010000 011100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝ A．{(a, e)}是割边B．{(a, e)}是边割集 C．{(a, e) ,(b, c)}是边割集D．{(d, e)}是边割集 图三 7．设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是( )． 图四 A．（a）是强连通的B．（b）是强连通的 C．（c）是强连通的D．（d）是强连通的 应该填写：D 8．设完全图K n 有n个结点(n≥2)，m条边，当（）时，K n 中存在欧拉 回路． A．m为奇数B．n为偶数C．n为奇数D．m为偶数9．设G是连通平面图，有v个结点，e条边，r个面，则r= ( )． A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2 10．无向图G存在欧拉通路，当且仅当( )． A．G中所有结点的度数全为偶数 B．G中至多有两个奇数度结点 C．G连通且所有结点的度数全为偶数 D．G连通且至多有两个奇数度结点 11．设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树． A．1 m n-+B．m n-C．1 m n++D．1 n m -+ 12．无向简单图G是棵树，当且仅当( )． A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 一、判断正误20% （每小题2分） 1、设A.B. C是任意三个集合。 （1）若A∈B且B?C，则A?C。（） （2）若A?B且B∈C，则A?C。（） （3）若A?B且B∈C，则A?C。（） （4）A) ( ) ( ) (C A B A C B ⊕ = ⊕。（） （5）(A–B)?C=(A?C)-(B?C)。（） 2、可能有某种关系，既不是自反的，也不是反自反的。（） ３、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（） ４、一个图是平面图，当且仅当它包含与Ｋ 3， 3 或Ｋ 5 在２度结点内同构的子图。（） ５、代数系统中一个元素的左逆元并一定等于该元素的右逆元。（） ６、群是每个元素都有逆元的半群。（） 二、8% 将谓词公式)) , ( ) ( ) ( ) (( )) , ( ) ( )( (z y Q z y P y y x Q x P x? ∧ ? → → ?化为前束析取范式与前束合取范式。 三、8% 设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{ 五、10% 证明：若图Ｇ是不连通的，则Ｇ的补图G 是连通的。 六、10% 证明：循环群的任何子群必定也是循环群。 七、12% 用ＣＰ规则证明： １．F A F E D D C B A →?→∨∧→∨,。 ２．?∨??∨?(()()())()()((x P x x Q x P x )()x Q x 。 八、10% 用推理规则证明下式： 前提: ))()()(()),()()(())()()(((y W y M y y W y M y x S x F x ?∧?→?→∧? 结论：?→?)()((x F x S ))(x 九、13% 若集合Ｘ＝｛（１，２），（３，４），（５，６），……｝ }|,,,{12212211y x y x y x y x R +=+>><><<= 1、证明R 是X 上的等价关系。 2、求出X 关于R 的商集。 一、 填空 20%（每小题2分） 安徽大学20 09 — 20 10 学年第 1 学期 《 离散数学 》考试试卷（A 卷） （时间120分钟） 院/系 专业 姓名 学号 一、单项选择题（每小题2分，共20分） 1. 设:P 天没下雪，:Q 我去镇上，则命题“天正在下雪，我没去镇上”可符号化为（ D ） A.Q P ?→?； B. P Q ?→?； C.Q P ?∧； D. Q P ?∧?。 2.下列命题是重言式的是（ C ） A.)()(P Q Q P →∧→； B. )()(Q P P Q P ???∧； C. )(Q P Q P →→∧； D. Q P R Q P ∧?∧?∨→))((。 3. 设解释R 如下：论域D 为实数集，a=0, f(x,y)=x-y, A(x,y):x 离散数学试题与答案试卷一 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 8．图的补图为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ?； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A B C ?；B．{Φ，3，4}；C．{4，Φ，3，3}；D．{3，4}。 A．{4，3}Φ 3、设A={1，2，3}，则A上的二元关系有（）个。 A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） Rο是自反的； A．若R，S 是自反的，则S Rο是反自反的； B．若R，S 是反自反的，则S Rο是对称的； C．若R，S 是对称的，则S Rο是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s t s p A R= ∧ =则P（A）/ R=（） < > ∈ s (| || |} {t ) , ( | , A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 离散数学试题(A卷答案） 一、证明题（10分） 1) (P∧Q∧A→C)∧(A→P∨Q∨C)? (A∧(P?Q))→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 ??( A∧((P∧Q)∨(?P∧?Q)))∨C ??( A∧(P?Q))∨C ?(A∧(P?Q))→C 2) ?(P↑Q)??P↓?Q。 证明：?(P↑Q)??(?(P∧Q))??(?P∨?Q))??P↓?Q。 二、分别用真值表法和公式法求(P→(Q∨R))∧(?P∨(Q?R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。 证明： 公式法：因为(P→(Q∨R))∧(?P∨(Q?R)) ?(?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) ? M∧5M∧6M 4 ? m∨1m∨2m∨3m∨7m 所以，公式(P→(Q∨R))∧(?P∨(Q?R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。 真值表法： 式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。 三、推理证明题（10分） 1）?P∨Q，?Q∨R，R→S P→S。 证明：(1)P附加前提 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为 则 R= 。 8．图的补图为 。 9．设A={a ，b ，c ，d} ，A 上二元运算如下： 那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。 10．下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ? ； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 3、设A={1，2，3}，则A 上的二元关系有（ ）个。 A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） R 是自反的； A．若R，S 是自反的，则S R 是反自反的； B．若R，S 是反自反的，则S R 是对称的； C．若R，S 是对称的，则S R 是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s p R= t s ∈ =则P（A）/ R=（） < > ∧ A ) (| || |} ( , {t , | s A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（） 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 离散数学试题与答案
离散数学试题与参考答案
离散数学考试题详细答案
离散数学期末试题及答案完整版
(完整版)离散数学试卷及答案
山东大学离散数学题库及答案
离散数学试题及解答
离散数学试卷及答案一
离散数学题库
离散数学试卷二十三试题与答案
的幺元为（ ）。 A 、a ； B 、b ； C 、1； D 、0。 8．给定下列序列，（ ）可以构成无向简单图的结点度数序列。 A 、（1，1，2，2，3）； B 、（1，1，2，2，2）； C 、（0，1，3，3，3）； D 、（1，3，4，4，5）。 9．设G 是简单有向图，可达矩阵P(G)刻划下列 （ ）关系。 A 、点与边； B 、边与点； C 、点与点； D 、边与边。 10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（ ）。 A 、5； B 、7； C 、9； D 、8。
离散数学试卷
离散数学试题及解答
上海大学-离散数学2-图部分试题
离散数学试卷及答案(17)
《离散数学》(上)试卷(A卷)及参考答案
离散数学全部试卷
最新离散数学试卷及答案 (1)
离散数学试卷及答案(1)
相关主题
文本预览