第一篇：2006年7月全国自考离散数学试题试卷真题及答案（精选）
www.xiexiebang.com 专注于收集各类历年试卷和答案
2006年7月全国自考离散数学试题试卷真题
一、单项选择题（本大题共15小题，每小题1分，共15分）1．下列语句中不是命题的只有（）．A．鸡毛也能飞上天？ C．不经一事，不长一智。
B．或重于泰山，或轻于鸿毛。D．牙好，胃口就好。
2．从真值角度看，命题公式的全部类型是（）
A．永真式
B．永假式
C．永真式，永假式
D．永真式，永假式，可满足式
3．设M（x）：x是人；F（x）：x要吃饭。用谓词公式表达下述命题：所有的人都要吃饭，其中错误的表．．达式是（）A．(x)(M(x)F(x))C．(x)(M(x)F(x))
B．(x)(M(x)F(x))D．(x)(M(x)F(x))
4．下列公式是前束范式的是（）A．(x)(y)(F(z,x)G(y))B．((x)F(x)(y)G(y))H(z)C．(x)F(x,y)(y)G(y)D．(x)(F(x,y)(y)G(x,y))5．设论域为整数集，下列真值为真的公式是（）A．(x)(y)(xy0)
B．(y)(x)(xy0)C．(x)(y)(xy0)D．(x)(y)(xy0)
6．下列是谓词演算中的合式公式的是（）
A．(x)(p(x)y)
B．(x)F(x)G(x,y)
C．(x)P(x,y)Q(y,z)
D．(x)xP(x,y)．（）A．B． C．D． ．（）
8．下列式子正确的是（）A．（A－B）-C=A-（B∪C）
（）
B．A－（B∪C）=（A－B）∪C C．~（A－B）=~（B－A）D．~（A∩B）A 9．下列集合对所给的运算是封闭的只有（）
A．非零整数集合Z*上的除法运算
B．全体n×n实可逆矩阵集合Mn（R）上的矩阵加法和乘法运算 C．全体n×n实矩阵集合Mn（R）上的矩阵加法和乘法运算 D．A={1，2，„，10}，x*y=LCM（x，y），即x，y最小公倍数
+，*>是环，则下列说法不正确的是（）10．设 B． +对*是可分配的 D．○11．下列四个格，是分配格的是（） www.xiexiebang.com 专注于收集各类历年试卷和答案 12．下列各图是无向完全图的是（） 13．下列各有向图是强连通图的是（） 14．设Ｇ是具有n个结点的无向简单图，若在Ｇ中存在一条汉密尔顿路，则Ｇ中每一对结点的度数之和与n-1的关系为（） A．大于 B．大于等于 C．等于 D．小于 15．设连通平面图Ｇ，共有n个结点，e条边，r个面，则欧拉证明成立的公式是（）A．e-n+r=2 B．n+r-e=2 C．n-r+e=2 D．n-e-r=2 二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16．所谓___是指不能再分解的命题，而复合命题是由一些____经过联结词复合而成的命题。17．在命题演算中，两个____的合取、析取、条件、双条件均为____。 18．使公式(x)(y)(A(x)B(y))(x)A(x)(y)B(y)成立的条件是____中不含y，____中不含x。19．设A={1，2，3，4}，R是A上的二元关系，R={ 21．设X={1，3，5，9，15，45}，R是X上的整除关系，则R是X上的偏序，其最大元是___，极小元是____。 22．设 2-1-223．设e是群G上的幺元，若aG且a=e,则a=____ ,a=__________。24．代数系统 三、计算题（本大题共6小题，第26、27题各4分，第28、29题各5分，第30、31题各6分，共30分）26．如果论域是集合{a,b,c}，试消去下面公式中的量词：(x)(y)(xy0)27．求公式（pq)(qr)的主析取范式。 28．设A={a,b,c},A上二元关系R={ （2）奇数个顶点，奇数条边 （3）偶数个顶点，奇数条边 （4）奇数个顶点，偶数条边 30．下列各整数集合对于整除关系“|”都构成偏序集，判断哪些偏序集能构成格？并说明理由。1)L={1,2,3,4,5} 2)L={1,2,3,6,12} www.xiexiebang.com 专注于收集各类历年试卷和答案 3)L={1,2,3,4,6,9,12,18,36} 4)L={1,2,2,2,„,2} 31．设A={2，3，5，12，19}，等价关系R={ 四、证明题（本大题共3小题，第32、33题各6分，第34题8分，共20分）32．用等价变换法证明：(PQ)((RQ)((PR)Q))是永真式。 33．若无向图G是欧拉图，G中是否存在割边？为什么？ 34．设A是一个集合，X=P（A），R是X上元素之间的包含关系，试证明 五、应用题（本大题共2小题，第35题6分，第36题9分，共15分）35．设有n个村庄要修路，（1）若要使所有村庄之间都有通路，问需在两村之间至少修几条路？（2）若要使任意两村庄之间有一条直接的路，则至少修几个路？（3）若修一条连接所有村庄的环路，问有多少种修路方案？ 36．设有推理： (a)没有不守信用的人是可信赖的； (b)有些可以信赖的人是受过教育的人； (c)因此有些受过教育的人是守信用的。 试构造推理的证明，要求把推理的前提，结论符号化为谓词形式，并写出推理过程。（个体域：人的集合）提示：设F（x）表示x是守信用的人；G（x）表示x是可信赖的人；H（x）表示x是受过教育的人。 23n 3 www.xiexiebang.com 专注于收集各类历年试卷和答案 www.xiexiebang.com 专注于收集各类历年试卷和答案 www.xiexiebang.com 专注于收集各类历年试卷和答案 全国2010年7月自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是命题的是（D）．．A．中华人民共和国的首都是北京 C．雪是黑色的 B．张三是学生 D．太好了！ 2．下列式子不是谓词合式公式的是（B）．．A．（x）P(x)→R(y)B．(x)┐P（x）(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 C．P∨(P∧Q) B．P∨Q∧R→┐R 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是自由变元 C．(x)的辖域是R(x, y) B．y是约束变元 D．(x)的辖域是(y)(P(x)∧Q(y))→(x)R(x,y)6．设论域为{1,2}，与公式(x)A(x)等价的是（）A．A(1)∨A(2)C．A(1)∧A(2) B．A(1)→A(2)D．A(2)→A(1)7．设Z+是正整数集，R是实数集，f:Z+→R, f(n)=log2n ,则f（）A．仅是入射 C．是双射 B．仅是满射 D．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（） 1A．0101011 01B．0101001 1 全国2010年7月自学考试离散数学试题 0C．0100011 01D．0101010 09．设R1和R2是集合A上的相容关系，下列关于复合关系R1R2的说法正确的是（）A．一定是等价关系 C．一定不是相容关系 10．下列运算不满足交换律的是（）．．．A．a*b=a+2b C．a*b=|a-b| B．a*b=min(a,b)D．a*b=2ab B．一定是相容关系 D．可能是也可能不是相容关系 11．设A是偶数集合，下列说法正确的是（）A． B． D． 12．设*是集合A上的二元运算，下列说法正确的是（）A．在A中有关于运算*的左幺元一定有右幺元 B．在A中有关于运算*的左右幺元一定有幺元 C．在A中有关于运算*的左右幺元，它们不一定相同 D．在A中有关于运算*的幺元不一定有左右幺元 13．题13图的最大出度是（）A．0 C．2 14．下列图是欧拉图的是（） B．1 D．3 15．一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是（）A．13 C．15 B．14 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>}，则R2S=___________，全国2010年7月自学考试离散数学试题 (R)=___________。 22．设代数系统 23．在 三、计算题（本大题共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)))的真值。 27．请通过等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。 28．设A={1,2,3,4}，给定A上二元关系R={<1,1>,<1,2>,<2,4>,<4,2>}，求R的传递闭包。29．对题29图所示格，找出它的所有的4元子格。 30．用矩阵的方法求题30图中结点ui，u5之间长度为2的路径的数目。 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．两个等价关系的并集不一定是等价关系，试举例说明。-12 全国2010年7月自学考试离散数学试题 2010年7月全国自考离散数学试题参考答案 全国2010年7月自学考试离散数学试题 全国2010年7月自学考试离散数学试题 全国2010年7月自学考试离散数学试题 全国2010年7月自学考试离散数学试题 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是命题的是（D）．．A．中华人民共和国的首都是北京 C．雪是黑色的 B．张三是学生 D．太好了！ 2．下列式子不是谓词合式公式的是（B）．．A．（x）P(x)→R(y)B．(x)┐P（x）(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 C．P∨(P∧Q) B．P∨Q∧R→┐R 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是自由变元 C．(x)的辖域是R(x, y) B．y是约束变元 D．(x)的辖域是(y)(P(x)∧Q(y))→(x)R(x,y)6．设论域为{1,2}，与公式(x)A(x)等价的是（）A．A(1)∨A(2)C．A(1)∧A(2) B．A(1)→A(2)D．A(2)→A(1)7．设Z+是正整数集，R是实数集，f:Z+→R, f(n)=log2n ,则f（）A．仅是入射 C．是双射 B．仅是满射 D．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（）101A．011 100001C．001 100100B．011 101101D．010 1009．设R1和R2是集合A上的相容关系，下列关于复合关系R1R2的说法正确的是（）A．一定是等价关系 B．一定是相容关系 全国2010年7月自学考试离散数学试题 C．一定不是相容关系 10．下列运算不满足交换律的是（）．．．A．a*b=a+2b C．a*b=|a-b| D．可能是也可能不是相容关系 B．a*b=min(a,b)D．a*b=2ab 11．设A是偶数集合，下列说法正确的是（）A． B． D． 12．设*是集合A上的二元运算，下列说法正确的是（）A．在A中有关于运算*的左幺元一定有右幺元 B．在A中有关于运算*的左右幺元一定有幺元 C．在A中有关于运算*的左右幺元，它们不一定相同 D．在A中有关于运算*的幺元不一定有左右幺元 13．题13图的最大出度是（）A．0 C．2 14．下列图是欧拉图的是（） B．1 D．3 15．一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是（）A．13 C．15 B．14 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>}，则R2S=___________，(R-1)2=___________。 22．设代数系统 23．在 全国2010年7月自学考试离散数学试题 三、计算题（本大题共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)))的真值。 27．请通过等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。 28．设A={1,2,3,4}，给定A上二元关系R={<1,1>,<1,2>,<2,4>,<4,2>}，求R的传递闭包。29．对题29图所示格，找出它的所有的4元子格。 30．用矩阵的方法求题30图中结点ui，u5之间长度为2的路径的数目。 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年7月自学考试离散数学试题 全国2010年7月自学考试离散数学试题 全国2010年7月自学考试离散数学试题 全国2010年7月自学考试离散数学试题 全国2010年7月自学考试离散数学试题 全国2008年4月自考离散数学试题 课程代码：02324 一、单项选择题(本大题共15小题，每小题1分，共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.设P：天下大雨,Q：他在室内运动,命题“除非天下大雨，否则他不在室内运动”可符合化为（） A.P∧QB.P→Q C.P→QD.P→Q 2.下列命题联结词集合中，是最小联结词组的是（） A.{，}B.{，∨，∧} C.{，∧}D.{∧，→} 3.下列命题为假命题的是（） A.如果2是偶数，那么一个公式的析取范式惟一 B.如果2是偶数，那么一个公式的析取范式不惟一 C.如果2是奇数，那么一个公式的析取范式惟一 D.如果2是奇数，那么一个公式的析取范式不惟一 4.谓词公式 x(P(x)∨yR(y))→Q(x))中变元x是（） A.自由变元B.约束变元 C.既不是自由变元也不是约束变元D.既是自由变元也是约束变元 5.若个体域为整数减，下列公式中值为真的是（） A.xy(x+y=0)B.y x(x+y=0)C.x y(x+y=0)D.xy(x+y=0) 6.下列命题中不正确的是（） A.x∈{x}-{{x}}B.{x}{x}-{{x}} C.A={x}∪x,则x∈A且xAD.A-B=A=B 7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（A.PQB.PQ C.QPD.Q=P 8.下列表达式中不成立的是（） A.A∪(BC)=(A∪B)(A∪C)B.A∩(BC)=(A∩B)(A∩C)C.(AB)×C=(A×C)(B×C)D.(A-B)×C=(A×C)-(B×C)9.半群、群及独异点的关系是（） A.{群}{独异点}{半群}B.{独异点}{半群}{群} C.{独异点}{群}{半群}D.{半群}{群}{独异点} 10.下列集合对所给的二元运算封闭的是（） A.正整数集上的减法运算 B.在正实数的集R+上规定为ab=ab-a-b a,b∈R+ C.正整数集Z+上的二元运算为xy=min(x,y)x,y∈Z+ D.全体n×n实可逆矩阵集合Rn×n上的矩阵加法 11.设集合A={1，2，3}，下列关系R中不是等价关系的是（）A.R={<1,1>,<2,2>,<3,3>} B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}） C.R={<1,1>,<2,2>,<3,3>,<1,2>} D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>} 12.下列函数中为双射的是（） A.f：Z→Z,f(j)=j(mod)B.f：N→N,f(j)= C.f：Z→N,f(j)=|2j|+1D.f：R→R,f(r)=2r-15 13.设集合A={a,b, c}上的关系如下，具有传递性的是（） A.R={ 14.含有5个结点，3条边的不同构的简单图有（） A.2个B.3个 C.4个D.5个 15.设D的结点数大于1，D= A.D中至少有一条通路B.D中至少有一条回路 C.D中有通过每个结点至少一次的通路D.D中有通过每个结点至少一次的回路 二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。 16.设A={1,2,3}，B={3,4,5}，则AA=___________，AB=___________。 17.设A={1,2,3,4,5}，RA×A，R={<1,2>，<3,4>,<2,2>}，则R的自反闭包r(R)=__________。 对称闭包t(R)=__________。 18.设P、Q为两个命题，德摩根律可表示为_____________，吸收律可表示为____________。 19.对于公式 x(P(x)∨Q(x))，其中P(x)∶x=1,Q(x)∶x=2,当论域为{1,2}时，其真值为_____________ ,当论域为{0,1,2}时，其真值为_____________。 20.设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数 ,。 21.3个结点可构成_________个不同构的简单无向图，可构成________个不同构的简单有向图。 22.无向图G= Δ(G)=_____________，G的最小度δ(G)=_____________。 23.设图G 24.格L是分配格，当且仅当L既不含有与_______同构的子格，也不含有与______同格的子格。 25.给定集合A={1,2,3,4,5}，在集合A上定义两种关系：R={<1,2>,<3,4>,<2,2>}, S={<4,2>,<2,5>,<3,1>,<1,3>}，则。 三、计算题（本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共30分） 26.设A={a,b,c,d}，A上的等价关系R={ 27.构造命题公式（P∨Q）（P∧Q）的真值表。 28.求下列公式的主析取范式和主合取范式：P→（（Q→P）∧（P∧Q）） 29.设A={a, b, c, d, e}，R为A上的关系，R={ 30.给定图G如图所示，（1）G中长度为4的路有几条？其中有几条回路？（2）写出G的可达矩阵。 四、证明题（本大题共3小题，第31、32题各6分，第33题8分，共20分） 31.设（L，≤）是格，试证明： a, b, c ∈L, 有a∧（b∨c）≥（a∧b）∨（a∧c）； a∨（b∧c）≤（a∨b）∧（a∨c）。 32.设R是A上的自反和传递关系，如下定义A上的关系T，使得 x, y∈A， 证明T是A上的等价关系。 33.设有G= 五、应用题（本大题共2小题，第34题7分，第35题8分，共15分） 34.构造下面推理的证明。 每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。 35.今要将6人分成3组（每组2个人）去完成3项任务。已知每个人至少与其余5个人中的3个人能相互合作。 （1）能否使得每组的2个人都能相互合作？ （2）你能给出几种不同的分组方案？ 《离散数学》试题及答案3 一、填空题设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A(B)＝ __________________________.2.设有限集合A, |A| = n, 则 |(A×A)| = __________________________.3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________.4.已知命题公式G＝(PQ)∧R，则G的主析取范式是_______________________________ __________________________________________________________.5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________.6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从AB＝_________________________;AB＝_________________________;A－B＝ _____________________.7.设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________.8.设命题公式G＝(P(QR))，则使公式G为真的解释有__________________________，_____________________________, __________________________.9.设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则R1•R2 = ________________________,R2•R1 =____________________________,R12 =________________________.10.设有限集A, B，|A| = m, |B| = n, 则| |(AB)| = _____________________________.11 设A,B,R是三个集合，其中R是实数集，A = {x |-1≤x≤1, xR}, B = {x | 0≤x < 2, xR},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ ,.13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________.14.设一阶逻辑公式G = xP(x)xQ(x)，则G的前束范式是__________________________ _____.15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。 16.设谓词的定义域为{a, b},将表达式xR(x)→xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________.17.设集合A＝{1, 2, 3, 4}，A上的二元关系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。则RS＝_____________________________________________________, R2＝______________________________________________________.二、选择题 设集合A={2,{a},3,4}，B = {{a},3,4,1}，E为全集，则下列命题正确的是()。 (A){2}A(B){a}A(C){{a}}BE(D){{a},1,3,4}B.设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备().(A)自反性(B)传递性(C)对称性(D)反对称性 设半序集(A,≤)关系≤的哈斯图如下所示，若A的子集B = {2,3,4,5},则元素6为B的()。 (A)下界(B)上界(C)最小上界(D)以上答案都不对下列语句中，()是命题。 (A)请把门关上(B)地球外的星球上也有人 (C)x + 5 > 6(D)下午有会吗？ 设I是如下一个解释：D＝{a,b}, 则在解释I下取真值为1的公式是().(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)xyP(x,y).6.若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是().(A)(1,2,2,3,4,5)(B)(1,2,3,4,5,5)(C)(1,1,1,2,3)(D)(2,3,3,4,5,6).7.设G、H是一阶逻辑公式，P是一个谓词，G＝xP(x), H＝xP(x),则一阶逻辑公式GH是().(A)恒真的(B)恒假的(C)可满足的(D)前束范式.设命题公式G＝(PQ)，H＝P(QP)，则G与H的关系是()。 (A)GH(B)HG(C)G＝H(D)以上都不是.9 设A, B为集合，当()时A－B＝B.(A)A＝B(B)AB(C)BA(D)A＝B＝.设集合A = {1,2,3,4}, A上的关系R＝{(1,1),(2,3),(2,4),(3,4)}, 则R具有()。 (A)自反性(B)传递性(C)对称性(D)以上答案都不对下列关于集合的表示中正确的为()。 (A){a}{a,b,c}(B){a}{a,b,c}(C){a,b,c}(D){a,b}{a,b,c} 12 命题xG(x)取真值1的充分必要条件是().(A)对任意x，G(x)都取真值1.(B)有一个x0，使G(x0)取真值1.(C)有某些x，使G(x0)取真值1.(D)以上答案都不对.13.设G是连通平面图，有5个顶点，6个面，则G的边数是().(A)9条(B)5条(C)6条(D)11条.14.设G是5个顶点的完全图，则从G中删去()条边可以得到树.(A)6(B)5(C)10(D)4.15.设图G的相邻矩阵为，则G的顶点数与边数分别为().(A)4, 5(B)5, 6(C)4, 10(D)5, 8.三、计算证明题 1.设集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R为整除关系。 (1)画出半序集(A,R)的哈斯图； (2)写出A的子集B = {3,6,9,12}的上界，下界，最小上界，最大下界； (3)写出A的最大元，最小元，极大元，极小元。 2.设集合A＝{1, 2, 3, 4}，A上的关系R＝{(x,y)| x, yA 且 x y}, 求 (1)画出R的关系图； (2)写出R的关系矩阵.3.设R是实数集合，,,是R上的三个映射，(x)= x+3, (x)= 2x, (x)＝ x/4,试求复合映射•，•, •, •，••.4.设I是如下一个解释：D = {2, 3}, abf(2)f(3)P(2, 2)P(2, 3)P(3, 2)P(3, 3)32320011 试求(1)P(a, f(a))∧P(b, f(b));(2)xy P(y, x).5.设集合A＝{1, 2, 4, 6, 8, 12}，R为A上整除关系。 (1)画出半序集(A,R)的哈斯图； (2)写出A的最大元，最小元，极大元，极小元； (3)写出A的子集B = {4, 6, 8, 12}的上界，下界，最小上界，最大下界.6.设命题公式G = (P→Q)∨(Q∧(P→R)), 求G的主析取范式。 7.(9分)设一阶逻辑公式：G =(xP(x)∨yQ(y))→xR(x)，把G化成前束范式.9.设R是集合A = {a, b, c, d}.R是A上的二元关系, R = {(a,b),(b,a),(b,c),(c,d)},(1)求出r(R), s(R), t(R)； (2)画出r(R), s(R), t(R)的关系图.11.通过求主析取范式判断下列命题公式是否等价： (1)G =(P∧Q)∨(P∧Q∧R) (2)H =(P∨(Q∧R))∧(Q∨(P∧R)) 13.设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)}.(1)试写出R和S的关系矩阵； (2)计算R•S, R∪S, R－1, S－1•R－1.四、证明题 1.利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。 2.设A,B为任意集合，证明：(A-B)-C = A-(B∪C).3.(本题10分)利用形式演绎法证明：{A∨B, C→B, C→D}蕴涵A→D。 4.(本题10分)A, B为两个任意集合，求证： A－(A∩B)=(A∪B)－B.参考答案 一、填空题 1.{3};{{3},{1,3},{2,3},{1,2,3}}.2..3.1= {(a,1),(b,1)}, 2= {(a,2),(b,2)},3= {(a,1),(b,2)}, 4= {(a,2),(b,1)};3, 4.4.(P∧Q∧R).5.12, 3.6.{4}, {1, 2, 3, 4}, {1, 2}.7.自反性；对称性；传递性.8.(1, 0, 0),(1, 0, 1),(1, 1, 0).9.{(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.10.2mn.11.{x |-1≤x < 0, xR};{x | 1 < x < 2, xR};{x | 0≤x≤1, x12.12;6.13.{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}.14.x(P(x)∨Q(x)).15.21.16.(R(a)∧R(b))→(S(a)∨S(b)).17.{(1, 3),(2, 2)};{(1, 1),(1, 2),(1, 3)}.二、选择题 1.C.2.D.3.B.4.B.5.D.6.C.7.C.8.A.9.D.10.B.11.B.13.A.14.A.15.D 三、计算证明题 1.(1) (2)B无上界，也无最小上界。下界1, 3;最大下界是3.(3)A无最大元，最小元是1，极大元8, 12, 90+;极小元是1.2.R = {(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.(1) (2) 3.(1)•＝((x))＝(x)+3＝2x+3＝2x+3.(2)•＝((x))＝(x)+3＝(x+3)+3＝x+6,(3)•＝((x))＝(x)+3＝x/4+3,(4)•＝((x))＝(x)/4＝2x/4 = x/2，(5)••＝•(•)＝•+3＝2x/4+3＝x/2+3.4.(1)P(a, f(a))∧P(b, f(b))= P(3, f(3))∧P(2, f(2))= P(3, 2)∧P(2, 3)= 1∧0 = 0.(2)xy P(y, x)= x(P(2, x)∨P(3, x)) R}.6 =(P(2, 2)∨P(3, 2))∧(P(2, 3)∨P(3, 3))=(0∨1)∧(0∨1)= 1∧1 = 1.5.(1) (2)无最大元，最小元1，极大元8, 12;极小元是1.(3)B无上界，无最小上界。下界1, 2;最大下界2.6.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∧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).7.G =(xP(x)∨yQ(y))→xR(x)= (xP(x)∨yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨zR(z)= xyz((P(x)∧Q(y))∨R(z)) 9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}, s(R)＝R∪R－1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)}，t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}； (2)关系图: 11.G＝(P∧Q)∨(P∧Q∧R) ＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m7∨m3 ＝(3, 6, 7) H =(P∨(Q∧R))∧(Q∨(P∧R))＝(P∧Q)∨(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)∨(P∧Q∧R)＝m6∨m3∨m7 ＝(3, 6, 7) G,H的主析取范式相同，所以G = H.13.(1) P∧Q∧R)7 (2)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)}.四 证明题 1.证明：{P→Q, R→S, P∨R}蕴涵Q∨S(1)P∨RP (2)R→PQ(1)(3)P→QP (4)R→QQ(2)(3)(5)Q→RQ(4)(6)R→SP (7)Q→SQ(5)(6)(8)Q∨SQ(7) 2.证明：(A-B)-C =(A∩~B)∩~C = A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C) 3.证明：{A∨B, C→B, C→D}蕴涵A→D(1)AD(附加)(2)A∨BP(3)BQ(1)(2)(4)C→BP(5)B→CQ(4)(6)CQ(3)(5)(7)C→DP(8)DQ(6)(7)(9)A→DD(1)(8) 所以 {A∨B, C→B, C→D}蕴涵A→D.4.证明：A－(A∩B)= A∩~(A∩B)＝A∩(~A∪~B) ＝(A∩~A)∪(A∩~B)＝∪(A∩~B)＝(A∩~B)＝A－B 而(A∪B)－B =(A∪B)∩~B =(A∩~B)∪(B∩~B)=(A∩~B)∪ = A－B 所以：A－(A∩B)=(A∪B)－B.8 1.离散数学试题及答案2 离散数学试题 一.多重选择填空题 (本题包括16个空格，每个空格3分，共48分。每道小题都可能有一个以上的正确选项，须选出所有的正确选项，不答不得分，多选、少选或选错都将按比例扣分。)1．命题公式(P∧(P→Q))→Q是_____式。 (1)重言(2)矛盾(3)可满足(4)非永真的可满足 2．给定解释I=(D,)=(整数集，{f(x,y):f(x,y)=x-y；g(x,y):g(x,y)=x+y；P(x,y):x (1)100(2)99(3)2048(4)1024(5)512 4．集合Ａ={x|x是整数，<30}，Ｂ={x|x是质数，x<20}，C={1,3,5}，则① =_____;② =_____;③ =_____;④ =_____。(1){1,2,3,5}(2)(3){0}(4){1,3,5,7,11,13,17,19}(5){1,3,5,7}(6){7,11,13,17,19} 5．设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∈B且B C，则A∈C 6．设集合Ａ={a,b,c,d,e,f,g}，Ａ的一个划分 ={{a,b},{c,d,e},{f,g}}，则 所对应的等价关系有_____个二元组。 (1)14(2)15(3)16(4)17(5)8(6)49(7)512 7．S={1,2,3,4,5,6,7,8,9,10,11,12}，≤是S上的整除关系。S的子集Ｂ＝{2,4,6｝，则在(S，≤)中，Ｂ的最大元是_____；Ｂ的最小元是_____；Ｂ的上确界是_____；Ｂ的下确界是_____。 (1)不存在的(2)36(3)24(4)12(5)6(6)1(7)2 8．设有有限布尔代数(B,+,*,’,0,1)，则 =_____能成立。(1)1(2)2(3)3(4)4(5)5(6)8(7)9 9．G={0,1,2,„,n}，n∈N，定义 为模n加法，即x y=(x+y)mod n，则代数系统(G，)_____。 (1)是半群但不是群(2)是无限群(3)是循环群(4)是变换群(5)是交换群 10．n个结点、m条边的无向连通图是树当且仅当m=_____。(1)n+1(2)n(3)n-1(4)2n-1 二请给出命题公式 的主析取范式。(10分)三假设下列陈述都是正确的：(1)学生会的每个成员都是学生并且是班干部； (2)有些成员是女生。问是否有成员是女班干部？请将上述陈述和你的结论符号化，并给出你的结论的形式证明。(10分)四设R和S是集合Ｘ上的等价关系,则S∩R必是等价关系。(10分) 参考答案 一、1.1、3 2.4 3.4 4.1；4；2；2 5.4 6.4 7.1；7；4；7 8.2、4、6 9.3、4 10.3 二、分析：求给定命题公式的主析取范式与主合取范式，通常有两种方法——列表法和等值演算法。(1)列表法 列出给定公式的真值表，其真值为真的赋值所对应的极小项的析取，即为此公式的主析取范式。(2)等值演算法 在等值演算中，首先将公式中的蕴涵联结词和等价联结词化去，使整个公式化归为析取范式，然后删去其中所有的永假合取项，再将析取式中重复出现的合取项合并和合并合取项中相同的命题变元，最后对合取项添加没有出现的命题变元，就是合取 ,经过化简整理，即可得到主析取范式。解：（1）列表法 设 000011111 001010100 010010100 011110100 100001000 101000010 110000010 111100111 根据真值表中 真值为1的赋值所对应的极小项的析取，即为 的主析取范式。由表可知 （2）等值演算 三、解：有成员是女班干部。 将命题符号化，个体域为全总个体域。 ：x是学生会的成员。：x是学生 ：x是班干部 ：x是女性 前提：，结论： 证明： ① P ② ES①，e为额外变元 ③ P ④ T③ ⑤ T② ⑥ T② ⑦ T④⑤⑥ ⑧ T② ⑨ T⑤⑦⑧ ⑩ EG⑨ 离散数学试题及答案1 离散数学考试试题（A卷及答案） 一、（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。 解 设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D) F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D)(A∧C)∨(B∧C∧ D)∨(C∧D)T 故有三种派法：B∧D，A∧C，A∧D。 二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。()： 是专家；()： 是工人；()： 是青年人；则推理化形式为： (()∧())，()(()∧())下面给出证明： (1)()P (2)(c)T(1)，ES(3)(()∧())P (4)(c)∧(c)T(3)，US(5)(c)T(4)，I (6)(c)∧(c)T(2)(5)，I 11(7)(()∧())T(6)，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。 证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A))(BA)。 四、（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∪R－1＝{<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，1>，<5，4>，<5，5>}。 五、（10分）R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称的。 证明 对任意的x、y∈A，若xr(R)y，则由r(R)＝R∪IA得，xRy或xIAy。因R与IA对称，所以有yRx或yIAx，于是yr(R)x。所以r(R)是对称的。 下证对任意正整数n，Rn对称。 因R对称，则有xR2yz(xRz∧zRy)z(zRx∧yRz)yR2x，所以R2对称。若 对称，则x yz(x z∧zRy)z(z x∧yRz)y x，所以 对称。因此，对任意正整数n，对称。 对任意的x、y∈A，若xt(R)y，则存在m使得xRmy，于是有yRmx，即有yt(R)x。因此，t(R)是对称的。 六、（10分）若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是满射。 对任意的y1、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是双射。 七、（10分）设 证明 因为 因为S是有限集，所以必存在j＞i，使得 ＝。令p＝j－i，则 ＝ *。所以对q≥i，有 ＝ *。 因为p≥1，所以总可找到k≥1，使得kp≥i。对于 ∈S，有 ＝ * ＝ *(*)＝„＝ *。 令a＝，则a∈S且a*a＝a。 八、（20分）（1）若G是连通的平面图，且G的每个面的次数至少为l(l≥3)，则G的边数m与结点数n有如下关系： m≤(n－2)。 证明 设G有r个面，则2m＝ ≥lr。由欧拉公式得，n－m＋r＝2。于是，m≤(n－2)。 （2）设平面图G＝ 证明 设G*＝ 离散数学考试试题（B卷及答案） 一、（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，＝25－20＝5。故，不会 13 打这三种球的共5人。 四、（10分）设A1、A2和A3是全集U的子集，则形如 Ai(Ai为Ai或)的集合称为由A1、A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。 证明 小项共8个，设有r个非空小项s1、s2、„、sr(r≤8)。 对任意的a∈U，则a∈Ai或a∈，两者必有一个成立，取Ai为包含元素a的Ai或，则a∈ Ai，即有a∈ si，于是U si。又显然有 siU，所以U＝ si。 任取两个非空小项sp和sq，若sp≠sq，则必存在某个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)fog是A到C的函数； (2)对任意的x∈A，有fog(x)＝f(g(x))。 证明(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使 对任意的x∈A，若存在y1、y2∈C，使得 综上可知，fog是A到C的函数。 (2)对任意的x∈A，由g：A→B是函数，有 八、（15分）设 证明 对于任意a∈G，必有a－1∈G使得a－1*a＝e∈H，所以 若 若 综上可得，R是G中的一个等价关系。 对于任意的b∈[a]R，有 发到哪？给个邮箱啊~~~~~~~ 一、填空 20%（每小题2分） 1．设（N：自然数集，E¬¬¬+ 正偶数）则。 2．A，B，C表示三个集合，文图中阴影部分的集合表达式为。 3．设P，Q 的真值为0，R，S的真值为1，则的真值=。 4．公式 的主合取范式为。 5．若解释I的论域D仅包含一个元素，则 在I下真值为。 6．设A={1，2，3，4}，A上关系图为 则 R2 =。 7．设A={a，b，c，d}，其上偏序关系R的哈斯图为 则 R=。 8．图 的补图为。 9．设A={a，b，c，d}，A上二元运算如下： * a b c d a b c d a b c d b c d a c d a b d a b c 那么代数系统 10．下图所示的偏序集中，是格的为。 二、选择 20%（每小题 2分） 1、下列是真命题的有（） 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． ； D．。 4、设R，S是集合A上的关系，则下列说法正确的是（） A．若R，S 是自反的，则 是自反的； B．若R，S 是反自反的，则 是反自反的； C．若R，S 是对称的，则 是对称的； D．若R，S 是传递的，则 是传递的。 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 则P（A）/ R=（） 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)= C．f : R I , f(x)= [x] ； D．f :I N, f(x)= | x |。 （注：I—整数集，E—偶数集，N—自然数集，R—实数集） 8、图 中 从v1到v3长度为3 的通路有（）条。 A． 0； B． 1； C． 2； D． 3。 9、下图中既不是Eular图，也不是Hamilton图的图是（） 10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（）个4度结点。 A．1； B．2； C．3； D．4。 三、证明 26% 1、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当 < a, b> 和在R中有<.b , c>在R中。（8分） 2、f和g都是群 3、G= 四、逻辑推演 16% 用CP规则证明下题（每小题 8分） 1、2、五、计算 18% 1、设集合A={a，b，c，d}上的关系R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R的传递闭包t(R)。（9分） 2、如下图所示的赋权图表示某七个城市 及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（9分） 试卷一答案： 一、填空 20%（每小题2分） 1、{0，1，2，3，4，6}； 2、； 3、1； 4、； 5、1； 6、{<1,1>, <1,3>, <2,2>, <2,4> }； 7、{ 8、9、a ；a , b , c ,d ；a , d , c , d ； 10、c; 二、选择 20%（每小题 2分） 题目 1 2 3 4 5 6 7 8 9 10 答案 C D B、C C A D C A D B A 三、证明 26% 1、证： “ ” 若 由R对称性知，由R传递性得 “ ” 若，有 任意，因 若 所以R是对称的。 若，则 即R是传递的。 2、证，有，又 ★ ★ ★ < C , ★> 是 < G1 , ★>的子群。 3、证： ①设G有r个面，则，即。而 故 即得。（8分） ②彼得森图为，这样 不成立，所以彼得森图非平面图。（3分） 二、逻辑推演 16% 1、证明： ① P（附加前提） ② T①I ③ P ④ T②③I ⑤ T④I ⑥ T⑤I ⑦ P ⑧ T⑥⑦I ⑨ CP 2、证明 ① P（附加前提） ② US① ③ P ④ US③ ⑤ T②④I ⑥ UG⑤ ⑦ CP 三、计算 18% 1、解：，t(R)={ , , < a , c> , , , < b ,b > , < b , c.> , < b , d > , < c , d > } 2、解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图： 树权C(T)=23+1+4+9+3+17=57即为总造价。 www.xiexiebang.com 专注于收集各类历年试卷和答案 一、单项选择题(本大题共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是整数集，定义为xxy=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∪IA B.R C.R∪{〈c,a〉} D.R∩IA 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 www.xiexiebang.com 专注于收集各类历年试卷和答案 D.(x)(y)(A(x,y)→A(f(x,a),a))12.设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于（）A.(x)A(x)→B B.(x)A(x)→B C.A(x)→B D.(x)A(x)→(x)B 13.谓词公式(x)(P(x,y))→(z)Q(x,z)∧(y)R(x,y)中变元x（）A.是自由变元但不是约束变元 B.既不是自由变元又不是约束变元 C.既是自由变元又是约束变元 D.是约束变元但不是自由变元 14.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为（）A.P∨Q B.P∧┐Q C.P→┐Q D.P∨┐Q 15.以下命题公式中，为永假式的是（）A.p→(p∨q∨r) B.(p→┐p)→┐p C.┐(q→q)∧p D.┐(q∨┐p)→(p∧┐p) 二、填空题(每空1分，共20分)16.在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______。17.A={1,2,3,4}上二元关系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的关系矩阵MR中m24=______,m34=______。18.设〈s,*〉是群，则那么s中除______外，不可能有别的幂等元；若〈s,*〉有零元，则|s|=______。19.设A为集合，P(A)为A的幂集，则〈P(A)，是格，若x,y∈P(A),则x,y最大下界是______，〉最小上界是______。 20.设函数f:X→Y,如果对X中的任意两个不同的x1和x2，它们的象y1和y2也不同，我们说f是______函数，如果ranf=Y，则称f是______函数。 21.设R为非空集合A上的等价关系，其等价类记为〔x〕R。x,y∈A，若〈x,y〉∈R，则 〔x〕R与〔y〕R的关系是______，而若〈x,y〉R，则〔x〕R∩〔y〕R=______。 22.使公式(x)(y)(A(x)∧B(y))(x)A(x)∧(y)B(y)成立的条件是______不含有y，______不含有x。23.设M(x):x是人，D(s):x是要死的，则命题“所有的人都是要死的”可符号化为(x)______,其中量词(x)的辖域是______。24.若H1∧H2∧„∧Hn是______，则称H1,H2,„Hn是相容的，若H1∧H2∧„∧Hn是______，则称H1,H2,„Hn是不相容的。 25.判断一个语句是否为命题，首先要看它是否为，然后再看它是否具有唯一的。 三、计算题(共30分)26.(4分)设有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。 27.(5)设A={a,b},P(A)是A的幂集，是对称差运算，可以验证 是群。设n是正整数，求({a}-1{b}{a})n{a}-n{b}n{a}n 28.(6分)设A={1,2,3,4,5},A上偏序关系 R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA; www.xiexiebang.com 专注于收集各类历年试卷和答案 (1)作出偏序关系R的哈斯图 (2)令B={1,2,3,5}，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。29.(6分)求┐(P→Q)(P→┐Q)的主合取范式并给出所有使命题为真的赋值。 30.(5分)设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。 31.(4分)求公式┐((x)F(x,y)→(y)G(x,y))∨(x)H(x)的前束范式。 四、证明题(共20分)32.(6分)设T是非平凡的无向树，T中度数最大的顶点有2个，它们的度数为k(k≥2),证明T中至少有2k-2片树叶。 33.(8分)设A是非空集合，F是所有从A到A的双射函数的集合，是函数复合运算。 证明：〈F, 〉是群。 34.(6分)在个体域D={a1,a2,„，an}中证明等价式： (x)(A(x)→B(x))(x)A(x)→(x)B(x) 五、应用题(共15分)35.(9分)如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。 36.(6分)一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么? 参考答案 一、单项选择题(本大题共15小题，每小题1分，共15分) 1.B 2.D 3.A 4.A 5.D 6.D 7.D 8.C 9.D 10.B 11.A 12.A 13.C 14.B 15.C 二、填空题 16.0 17.1 0 18.单位元 19.x∩y x∪y 20.入射 满射 21.［x］R=［y］R 22.A(x) B(y)23.(M(x)→D(x)) M(x)→D(x) www.xiexiebang.com 专注于收集各类历年试卷和答案 24.可满足式 永假式(或矛盾式)25.陈述句 真值 三、计算题 1100101026.M= 1011001122M=21110111 121011M2ij18,ij6 M2i1i1j144 G中长度为2的路总数为18，长度为2的回路总数为6。 27.当n是偶数时，x∈P(A),xn= 当n是奇数时，x∈P(A),xn=x 于是：当n是偶数，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n =(｛a｝-1)n｛b｝n｛a｝n= 当n是奇数时，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n =｛a｝-1｛b｝｛a｝(｛a｝-1)n｛b｝n｛a｝n =｛a｝-1｛b｝｛a｝｛a｝-1｛b｝｛a｝= 28.(1)偏序关系R的哈斯图为 (2)B的最大元：无，最小元：无； 极大元：2，5，极小元：1，3 下界：4，下确界4； 上界：无，上确界：无 29.原式(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q)) ((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q)) (┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q)) (┐(P∧┐Q)∨(P∧┐Q)) (P∧Q)∨(P∧┐Q) P∧(Q∨┐Q) P∨(Q∧┐Q) (P∨Q)∧(P∨┐Q) 命题为真的赋值是P=1,Q=0和P=1,Q=1 www.xiexiebang.com 专注于收集各类历年试卷和答案 30.令e1=(v1,v3)，e2=(v4,v6) e3=(v2,v5)，e4=(v3,v6) e5=(v2,v3)，e6=(v1,v2) e7=(v1,v4)，e8=(v4,v3) e9=(v3,v5)，e10=(v5,v6) 令ai为ei上的权，则 a1 取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的总权和=1+2+3+4+5=15 31.原式┐(x1F(x1,y)→y1G(x,y1))∨x2H(x2) (换名) ┐x1y1(F(x1,y)→G(x,y1))∨x2H(x2) x1y1┐(F(x1,y1)→G(x,y1))∨x2H(x2) x1y1x2(┐(F(x1,y1)→G(x,y1))∨H(x2) 四、证明题 32.设T中有x片树叶，y个分支点。于是T中有x+y个顶点，有x+y-1 条边，由握手定理知T中所有顶点的度数之的 xy d(vi)=2(x+y-1)。 i又树叶的度为1，任一分支点的度大于等于2 且度最大的顶点必是分支点，于是 xy d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i1 从而2(x+y-1)≥x+2y+2k-4 x≥2k-2 33.从定义出发证明：由于集合A是非空的，故显然从A到A的双射函数总是存在的，如A上恒等函数，因此F非空 (1)f,g∈F,因为f和g都是A到A的双射函数，故fg也是A到A的双射函数，从而集合F关于运算是封闭的。 (2)f,g,h∈F,由函数复合运算的结合律有f(gh)=(fg)h故运算是可结合的。 (3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F，〉中的幺元 (4)f∈F,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有ff-1=f-1f=IA,因此f-1是f的逆元 由此上知〈F，〉是群 34.证明(x)(A(x)→B(x)) x(┐A(x)∨B(x)) www.xiexiebang.com 专注于收集各类历年试卷和答案 (┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨„∨(┐A(an)∨B(an))) (┐A(a1)∨A(a2)∨„∨┐A(an)∨(B(a1)∨B(a2)∨„∨(B(an)) ┐(A(a1)∧A(a2)∧„∧A(an))∨(┐B(a1)∨B(a2)∨„∨(B(an)) ┐(x)A(x)∨(x)B(x)(x)A(x)→(x)B(x) 五、应用题 35.令p：他是计算机系本科生 q：他是计算机系研究生 r：他学过DELPHI语言 s:他学过C++语言 t:他会编程序 前提：(p∨q)→(r∧s),(r∨s)→t 结论：p→t 证①p P(附加前提) ②p∨q T①I ③(p∨q)→(r∧s) P(前提引入) ④r∧s T②③I ⑤r T④I ⑥r∨s T⑤I ⑦(r∨s)→t P(前提引入) ⑧t T⑤⑥I 36.可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。 根据：构造无向简单图G= Vi∈V,d(vi)是与vi相互认识的人的数目，由题意知vi,vj∈V有d(vi)+d(vj)20,于是G中存在汉密尔顿回路。 设C=Vi1Vi2„Vi20Vi1是G中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。第二篇：2010年7月自考离散数学试题及答案
第三篇：2010年7月自考离散数学试题及答案
第四篇：全国2008年4月自考离散数学试题
第五篇：离散数学试题+答案
点击咨询 