离散数学题库.doc

阅卷密封装订线常熟理工学院20 20 学年第 学期离散数学考试试卷（试卷库01卷）试题总分： 100 分 考试时限：120 分钟题号一二三四五总分阅卷人得分一、单项选择题（每题2分，共20分）1. 下列表达式正确的有( )（a） （b）（c）（d）2. 设p：22=5，q：雪是黑的，r：24=8，s：太阳从东方升起，下列( )命题的真值为真。（a）（b）（c）（d）3. 集合a=1,2,10上的关系r=|x+y=10,x,ya，则r 的性质为( )（a）自反的（b）对称的 （c）传递的，对称的 （d）传递的4. 设，其中表示模3加法，*表示模2乘法，在集合上定义如下运算：有称为的积代数，则的积代数幺元是( )（a）（b）（c）（d）5. 下图中既不是eular图，也不是hamilton图的图是( )6. 设为无向图，则g一定是( )（a）完全图（b）树（c）简单图（d）多重图7. 设p：我将去镇上,q：我有时间。命题“我将去镇上,仅当我有时间”符号化为（ ）。（a） pq（b）qp（c）pdq（d）8. 在有n个结点的连通图中,其边数（ ）（a）最多有n-1条 （b）最多有n 条 （c）至少有n-1条 （d）至少有n条9. 设ab,则有（ ）（a）b （b）b （c）ab （d）ab10. 设集合a上有3个元素,则a上的不同的等价关系的个数为（ ）（a）5 （b）7 （c）3 （d）6二、填空题（每题2分，共20分）1 n个命题变元组成的命题公式共有 种不同的等价公式。 2 设l，为有界格，a为l中任意元素，如果存在元素bl,使 ，则称b是a的补元。3 设*，是定义在集合a上的两个可交换二元运算，如果对于任意的x,ya,都有 ,则称运算*和运算满足吸收律。4 设t是一棵树，则t是一个连通且 的图。5 一个公式的等价式称作该公式的主合取范式是指它仅由 组成。6 量词否定等价式 (x)p(x) ， ($x)p(x) 。7 二叉树有5个度为2的结点，则它的叶子结点数为 。8 设是一个群，是阿贝尔群的充要条件是 。9 集合s=，上的二元运算*为*那么，代数系统中的幺元是 ， 的逆元是 。10 设a=，b=， = 。= 。三、判断题（每题1分，共10分）1. 命题公式是一个矛盾式。（ ）2. ，若，则必有。（ ）3. 设s为集合x上的二元关系，则s是传递的当且仅当(ss)s。（ ）4. 任何一棵二叉树的结点可对应一个前缀码。（ ）5. 代数系统中一个元素的左逆元一定等于该元素的右逆元。（ ）6. 一个有限平面图，面的次数之和等于该图的边数。（ ）7. ab = ba （ ）8. 设*定义在集合a上的一个二元运算，如果a中有关于运算*的左零元l和右零r,则a中有零元。（ ）9. 一个循环群的生成元不是唯一的。（ ）10. 任何一个前缀码都对应一棵二叉树。（ ）四、解答题（5小题，共30分）1. （5分）什么是欧拉路？如何用欧拉路判定一个图g是否可一笔画出？2. （8分）求公式 (pq)r 的主析取范式和主合取范式。3. （5分）已知一棵无向树中有2个2度顶点、1个3度顶点、3个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？4. （7分）权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。5. （5分）集合上的关系，写出关系矩阵，画出关系图并讨论r的性质。五、证明（3小题，共20分）1. （10分）用推理p,t规则证明：pq， pr, qs rs。2. （5分）设，是三个集合，证明：(ab)(ac)=a(bc)。3. （5分）设是群，ag。令h=xg|a*x=x*a。试证：h 是g 的子群。常熟理工学院20 20 学年第 学期离散数学考试试卷（试卷库02卷）试题总分： 100 分 考试时限：120 分钟题号一二三四五总分阅卷人得分一、选择题（每题2分，共20分）1. 下列公式中哪些是永真式？( )（a）(pq)(qr)（b） (pq)p （c） p(qq) （d）p(pq)2. 下列推导错在( )pusesug（a）（b） （c） （d）无3. 集合a=1，2，3，4上的偏序关系图为图(0)，则它的hass图为( )4. 设r是实数集合，“”为普通乘法，则代数系统 不是( )（a）群（b）独异点（c）半群（d）广群5. 连通非平凡的无向图g有一条欧拉回路当且仅当图g ( )（a）只有一个奇度结点（b）只有两个奇度结点（c）只有三个奇度结点（d）没有奇度结点6. 若一棵完全二元（叉）树有2n-1个顶点，则它( )片树叶（a）n（b）2n （c）n-1 （d）27. 在谓词演算中,是的有效结论,根据是（ ）。（a）us规则 （b） ug规则 （c） es规则 （d） eg规则8. 设在上海工作；是上海人。则命题“在上海工作的人未必都是上海人”的符号化为（ ）。a （b） （c） （d） 9. 集合a上的关系r是相容关系的必要条件是（ ）（a）自反,反对称的（b）反自反,对称的（c）传递,自反的（d）自反,对称的10. 下列各式错误的是（ ）（a）（b）（c）（d）二、填空题（每题2分，共20分）1. 设p、q是命题公式，填写如下的基本等价关系式：（1）(pq) $ ；（2） pdq ；2. 若集合a上的关系r 满足 的三个性质，则r是偏序关系。3. 设a，b是两命题公式，当且仅当 。4. 给定无孤立点图g，若存在一条路满足 ，该条路称为欧拉路。5. 一个 称为布尔格。6. 对于实数集合r，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“y”或“n” maxmin+可结合性可交换性存在幺元存在零元7. 设为偏序集，ba，记b = y | ya且y是b的上界，若b有最小元，则称该最小元为b的 。8. 一个公式的等价式称作该公式的主析取范式是指它仅由 组成。9. 由集合a和b的所有共同元素组成的集合称为a和b的交集，记作ab ，即ab= 。 10. 的图称为完全图。三、判断题（每题1分，共10分）1. “北京与天津的距离很近”是复合命题。（ ）2. 如果acbc，则有ab。（ ）3. 设r1和r2是集合a上的关系，且r1r2，则有r(r1) r(r2)。（ ）4. 若平面图共有v个结点，e条边和r个面，则v-e+r=2。（ ）5. 任何循环群必定是阿贝尔群，反之亦真。（ ）6. 命题公式是没有真假值的。（ ）7. 格l,所诱导的代数系统为l,，则运算，满足交换律。（ ）8. 设函数f: ab, 则f 的逆关系是函数当且仅当f 是入射。（ ）9. 群的运算表中的每一行或每一列不一定是g的元素的一个置换。（ ）10. 任何一棵二叉树可对应一个前缀码。（ ）四、解答题（3小题，共20分）1. （5分）简述二叉树的定义。如何将任何一棵有序树（m叉树）改写为对应的二叉树？ 2. （8分）求公式 (pq)r 的主析取范式和主合取范式。3. （7分）如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 五、证明（4小题，共30分）1. （10分）用推理p,t规则证明：pq，qr，r，sps。2. （10分）若r和s都是非空集a上的等价关系，则rs是a上的等价关系。3. （6分）若图g不连通，则g的补图是连通的。4. （4分）i(整数集)上的二元运算*定义为：a,bi，a*b=a+b-2。证明是群。常熟理工学院20 20 学年第 学期离散数学考试试卷（试卷库03卷）试题总分： 100 分 考试时限：120 分钟题号一二三四五总分阅卷人得分一、单项选择题（每题2分，共20分）1. 在下述公式中不是重言式为( )（a）（b）（c）（d）2. 设，则ba是( )（a） （b） （c） （d）3. 设a=1，2，10 ，则下面定义的运算*关于a封闭的有( )（a）x*y=max(x ，y)（b）x*y=质数p的个数使得（c）x*y=gcd(x ， y)(gcd (x ，y)表示x和y的最大公约数)（d）x*y=lcm(x ，y) （lcm(x ，y) 表示x和y的最小公倍数）4. 设是偏序集，“”定义为：，则当集合a=( )时，是格（a）1,2,3,4,6,12 （b）1,2,3,4,6,8,12,14 （c）1,2,3,12 （d）1,2,3,45. 在有n个顶点的连通图中，其边数( )（a）最多有n-1条（b）至少有n条（c）最多有n条（d）至少有n-1条6. 一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为( )（a）5（b）7 （c）8 （d）97. 公式g=pp ,则g是（ ）（a）永真的 （b）永假的 （c）可满足的 （d）析取的8. 设p,q的真值为0,r,s的真值为t,则下面命题公式中真值为t的是（ ）.（a）rp （b）qs （c）pds （d）qr9. a=1,2,3上的关系r=,则r具备（ ）（a）传递性与反对称性 （b）传递性与对称性 （c） 自反性与对称性 （d）反自反性与对称性10. 连通图g是一颗树,当且仅当满足下述条件中那一个（ ）（a）有些边不是割边。 （b）每条边都是割边 （c）每条边都不是割边 （d）无割边集二、填空题（每题2分，共20分）1. 设p、q是命题公式，填写如下的基本等价关系式：（1） pq ；（2）pq ；2. 若对命题p赋值t，q赋值f，则命题pdq的真值为 。3. 代数系统中，|a|1，如果分别为的幺元和零元，则的关系为 （填相等或不相等） 。4. 设集合a=1，2，3，4，5，6，7，8，9，10，定义a上的二元关系“”为x y = x|y ， 则xy= 。5. 公式的根树表示为 。6. 重言式又叫 式，其定义为 。7 给定无孤立点图g，若存在一条回路满足 ，该回路称为欧拉回路。8 设r为x到y的关系，s为从y到z上的关系， rs称为r和s的复合关系，则rs= 。9 设为群，若在g中存在一个元素a,使得 ，则称该群为循环群。10 设g是一个连通平面图，一个面的 称作该面的次数。三、判断题（每题1分，共10分）1. 设 命题“所有的研究生都读过大学”符号化为：。（ ）2. 设p，q是两个命题，当且仅当p，q的真值均为t时，pdq的值为t。（ ）3. 设a=a，b，c， r aa且r=， 则r是传递的。（ ） 4. 在有向图中顶点间的相互可达关系是等价关系。（ ）5. 代数系统中一个元素若有左逆元，则该元素一定也有右逆元。（ ）6. 合式公式的定义是用一个递归形式给出的。（ ）7. 格l,所诱导的代数系统为l,，则运算，满足分配律。（ ）8. 设函数f: ab, 则f 的逆关系是函数当且仅当f 是满射。（ ）9. 群的运算表中的每一行或每一列都是g的元素的一个置换。（ ）10. k3，3不是平面图。（ ）四、解答题（4小题，共30分）1. （5分）请解释谓词演算推理理论的us规则，ug规则，es规则和eg规则。2. （8分）求公式 (pq)(rp) 的主析取范式和主合取范式。3. （10分）集合上的偏序关系r为整除关系。设，试画出r的哈斯图，并求a，b，c的最大元素、极大元素、下界、上确界。4. （7分）假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happy new year的编码信息。五、证明（3小题，共20分）1. （8分）用推理p,t规则证明：bd，(ef)d，eb。2. （6分）证明在6个结点12条边的简单连通平面图中， 每个面的次数都是3。3. （6分）是一个群,设iex|x=2n,ni,证明是的子群。常熟理工学院20 20 学年第 学期离散数学考试试卷（试卷库04卷）试题总分： 100 分 考试时限：120 分钟题号一二三四五总分阅卷人得分一、选择题（每题2分，共20分）1. 命题“尽管有人聪明，但未必一切人都聪明”的符号化（p(x)：x是聪明的，m(x)：x是人）( )（a）（b）（c）（d）2. 谓词公式中的x是( )（a）自由变元（b）约束变元（c） 既不是自由变元又不是约束变元（d）既是自由变元又是约束变元3. 集合a=1，2，3，4上的偏序关系如图(0)，则它的哈斯图为( )4. 设是布尔代数，f是从an到a的函数，则( )（a）f是布尔代数（b）f能表示成析取范式，也能表示成合取范式（c）若a=0，1，则f一定能表示成析取范式，也能表示成合取范式（d）若f是布尔函数，它一定能表示成析（合）取范式5. 设，*为普通乘法，则是( )（a）代数系统（b）半群（c）群（d）都不是6. 设无向图g有18条边且每个顶点的度数都是3，则图g有( )个顶点（a）10（b）4（c）8（d）127. 一个割边集与任何生成树之间( )（a）没有关系（b）至少有一条公共边（c）有一条公共边（d）割边集诱导子图是生成树8. 集合a上的等价关系r,决定了a的一个划分,该划分就是（ ）（a）商集a/r（b）交集ar（c）差集a-r（d）并集ar9. 公式g=pp ,则g是（ ）（a）永真的 （b）永假的 （c）可满足的 （d）析取的10. 在有n个结点的连通图中,其边数（ ）（a）最多有n-1条 （b）至少有n-1条 （c）最多有n 条 （d）至少有n条二、填空题（每题2分，共20分）1. 设p、q是命题公式，填写如下的基本等价关系式：（1）(pq) # ；（2） pdq ；2. n个命题变元有 个互不等价的极小项。3. 设n阶图g中有m条边，每个结点的度数不是k的是k+1，若g中有nk个k度顶点，nk+1个k+1度顶点，则nk= 。4. 设集合s=，s上的运算*定义为*则代数系统中幺元是 ，左逆元是 。5. 具有 的图称为欧拉图。6. 设*是定义在集合a上的一个二元运算，为a中的一个元素，如果对于任一xa,有 ，则称为a中关于运算*的零元。7. 是存在量词消去规则，简称es规则。 8. r在a上是自反的 r。 9. 若偏序集a的每一个非空子集存在最小元，则称偏序集a为 集。10. 设图g=，如果有图g= ，使得 ，则称图g是图g的子图。三、判断题（每题1分，共10分）1. 命题公式是重言式。（ ）2. 公式中的辖域为。（ ）3. 不可能有某种关系，既是对称的，又是反对称的。（ ）4. 在任何有向图中，所有结点的入度的平方和等于所有结点的出度的平方和。（ ）5. 设s=1，2，则s在普通加法和乘法运算下都封闭。（ ）6. pq是一个合取范式。（ ）7. 格l,所诱导的代数系统为l,，则运算，满足结合律。（ ）8. 设函数f: ab, 则f 的逆关系是函数当且仅当f 是双射。（ ）9. 群中，除幺元e外，不可能有任何别的等幂元。（ ）10. 在任意图中,存在奇数个度数为奇数的结点。（ ）四、解答题（5小题，共30分）1. （5分）简述warshall在1962年提出的求传递闭包的方法。2. （8分）求公式 q(pr) 的主析取范式和主合取范式。3. （4分）设全集u=a,b,c,d,e, a=a,d, b=a,b,c,求p(a)-p(b)。4. （9分）在二叉树中（1）求带权为2，3，5，7，8的最优二叉树t;（2）求t对应的二元前缀码。5. （4分）设s=qq，q为有理数集合，*为s上的二元运算：对任意，s,有 *=,求出s关于二元运算*的幺元以及当a0时，关于*的逆元。6. 五、证明（2小题，共20分）1. （10分）用推理p,t规则证明：p(qr)，r(qs) p(qs)。2. （10分）设是半群,e是左幺元且对每一个,存在,使得。证明：对于任意的,如果a*b=b*c则b=c。通过证明e是a中的幺元,证明是群。常熟理工学院20 20 学年第 学期离散数学考试试卷（试卷库05卷）试题总分： 100 分 考试时限：120 分钟题号一二三四五总分阅卷人得分一、选择题（每题2分，共20分）1. 下列是真命题的有( )（a） （b）（c）（d）2. 下列集合中哪个是最小联结词集( )（a）（b）,d（c） ,d（d）3. 设，s上关系r的关系图如下 ，则r具有( )性质（a）自反性、对称性、传递性（b）反自反性、反对称性（c）反自反性、反对称性、传递性 （d）自反性4. 设，*为普通乘法，则是( )（a）代数系统（b）半群（c）群（d）都不是5. 如右图 相对于完全图k5的补图为( )6. 设g是n个结点、m条边和r个面的连通平面图，则m等于( )（a）n+r-2 （b）n-r+2 （c）n-r-2 （d）n+r+2 7. 连通图g是一颗树,当且仅当满足下述条件中那一个（）（a）有些边不是割边。 （b）每条边都是割边 （c）每条边都不是割边 （d）无割边集8. 设集合a=1,2,3,10,在集合a上定义运算,不是封闭的为（ ）（a） （b）（最大公约数）（c）（最小公倍数） （d）9. 设r和s是集合a上的等价关系,则rs的对称性（ ）（a）一定不成立 （b）一定成立 （c）不一定成立 （d）不可能成立10. 图g和g的结点和边分别存在一一对应关系是g和g同构的（ ）（a） 必要条件 （b） 充分条件 （c）充要条件 （d）既不充分也不必要条件二、填空题（每题2分，共20分）1. 设p、q是命题公式，填写如下的基本等价关系式：（1） pq ；（2）pq ；2. 任意两个不同小项的合取为 ，全体小项的析取式为 。3. 设s=a1，a2，a8，bi是s的子集，且设b1=a8,则由b31所表达的子集是 。4. 设集合s=，s上的运算*定义为*则代数系统中幺元是 ，左逆元是 。5. n阶完全图kn的点色数x(kn)= 。6. 无向图g具有一条欧拉路，当且仅当g是连通的，且 。7. *是定义在a上的一个二元运算， e是a中关于运算*的幺元。如果对于a中的一个元素a存在着a中的某个元素b,使得 ，那么就称b是a的一个逆元。8. 是存在量词引入规则，简称eg规则。9. 设x和y是任意两个集合，而f 是x到y的一个关系，如果 ，称关系f 为函数。10. 设图g的子图为g，如果 ,则称该图g为g的生成子图。三、判断题（每题1分，共10分）1. 命题公式是重言式。（ ）2. 设 命题“所有的研究生都读过大学”符号化为：。（ ）3. ab当且仅当ab=a。（ ）4. 在有向图中，所有结点的入度平方之和等于出度平方之和。（ ）5. 设是群的子群，则中幺元不一定是中幺元。（ ）6. 对于n个结点的完全图kn，有x(kn)n。（ ）7. a(bc) = (ab)(ac) （ ）8. 群中的运算不满足消去律。（ ）9. 质数阶群必定是循环群。（ ）10. ($x)(a(x)b(x) ($x)a(x)($x)b(x)（ ）四、解答题（5小题，共30分）1. （5分）什么是集合的划分，如何根据集合a的一个划分确定a的元素间的一个等价关系？ 2. （8分）求公式 (pr)(pq)的主析取范式和主合取范式。3. （4分）设a=a,d, b=a,b,c, c=b,d。求集合(a-b)(b-c)。4. （7分）在通讯中，八进制数字出现的频率如下：0：20%、1：30%、2：10% 、3：15%、4：10%、5：5%、6：5%、7：5%,求传输它们最佳前缀码（写出求解过程）。5. （6分）某年级共有9门选修课程，期末考试前必须提前将这9门课程考完，每人每天只在下午考一门课，若以课程表示结点，有一人同时选两门课程，则这两点间有边（其图如右），问至少需几天？五、证明（2小题，共20分）1. （10分）用推理p,t规则证明：pq，pr，rssq。2. （10分）设，在上定义关系当且仅当，证明是上的等价关系，并求出r。常熟理工学院20 20 学年第 学期离散数学考试试卷（试卷库06卷）试题总分： 100 分 考试时限：120 分钟题号一二三四五总分阅卷人得分一、单项选择题（每题2分，共20分）1. 设是人，犯错误,命题“没有不犯错误的人”符号化为( )（a）（b）（c）（d）2. 下列公式是重言式的有( )（a）（b）（c）（d）3. 设a= ，b=(a) 下列( )表达式不成立 （a） （b） （c） （d） 4. 下面偏序集( )能构成格5. 6阶有限群的任何子群一定不是( )（a）2阶（b）3 阶（c）4 阶（d）6 阶6. 一棵无向树t有7片树叶，3个3度顶点，其余顶点均为4度。则t有( )个4度结点（a）1（b）2（c）3（d）47. 设g是一个哈密尔顿图，则g一定是( )（a）欧拉图 （b）树 （c）平面图 （d）连通图 8. 设r和s是集合a上的等价关系,则rs的对称性（）（a）不一定成立 （b）一定不成立 （c）一定成立 （d）不可能成立9. 设g=,|v|=n,|e|=m为连通平面图且有r个面,则r=（ ）（a）n-m-2（b）m-n+2 （c）n+m-2 （d）m+n+210. 在0_之间填上正确的符号是（ ） （a） = （b） （c） （d）二、填空题（每题2分，共20分）1. 设p、q是命题公式，填写如下的基本等价关系式：（1）(pq) # ；（2） pdq ；2. 若p，q，为二命题，真值为f 当且仅当 。3. 设考虑下列子集，。，。则是a的覆盖的子集有 ，是a的划分的子集有 。4. 设是一个群，则（a）若a，b，xg，ax=b，则x= 。（b）若a，b，xg，ax=ab，则x= 。5. n阶无向完全图kn的边数是 ，每个结点的度数是 。6. 无向图g具有一条欧拉回路，当且仅当g是连通的，且 。7. 一般来说，命题公式用 联结词组表示。8. 是反对称的rrc 。9. 设函数f : ab，g: cd，如果a=c，b=d，且 ，则称函数f和g相等，记作f = g。10. 在无向图g中，如果结点u和v之间 ，则结点u和v称为是连通的。三、判断题（每题1分，共10分）1. 若p为命题变元，pp为主合取范式。 （ ）2. 如果ab，则有ab。（ ）3. 设r1和r2是集合a上的关系，且r1r2，则有t(r1) t(r2)。（ ）4. 在完全二元树中，若有片叶子，则边的总数。（ ）5. 独异点的运算表中任意两行都是不相同的。（ ） 6. 任意平面图g最多是5-色的。（ ）7. ab = ba （ ）8. 群中的运算不满足消去律。（ ）9. 质数阶群不一定是循环群。（ ）10. (x)f(x) ($x)f(x) （ ）四、解答题（5小题，共30分）1. （5分）已知一个偏序关系，如何画出它的哈斯图？2. （8分）求公式 (pq)(rp) 的主析取范式和主合取范式。3. （6分）如右图给出的赋权图表示六个城市及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。4. （7分）构造h、a、p、n、e、w、r、对应的前缀码，并画出与该前缀码对应的二叉树，写出英文短语happy new year的编码信息。5. （4分）设全集u=a,b,c,d,e, a=a,d, b=a,b,c, c=b,d。求集合(ab)c。五、证明（2小题，共20分）1. （10分）用推理p,t和cp规则证明：abcd，defaf。2. （10分）r是实数集，是一个代数系统，*是r-1上的一个二元运算，使得对于r-1中任意元素a,b都有a*b=a+b+ab，证明0是的幺元，而且是群。常熟理工学院20 20 学年第 学期离散数学考试试卷（试卷库07卷）试题总分： 100 分 考试时限：120 分钟题号一二三四五总分阅卷人得分一、选择题（每题2分，共20分）1. 设l(x)：x是演员，j(x)：x是老师，a(x , y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为( )（a）（b）（c）（d）2. 命题逻辑演绎的cp规则为( )（a）在推演过程中可随便使用前提（b）在推演过程中可随便使用前面演绎出的某些公式的逻辑结果（c）设是含公式a的命题公式，则可用b替换中的a（d）如果要演绎出的公式为形式，那么将b作为前提，演绎出c3. 下列命题正确的是( )（a）（b）（c）（d）4. 设是一个有界格，如果它也是有补格，只要满足( )（a） 每个元素都至少有一个补元（b） 每个元素都有多个补元（c）每个元素都无补元（d） 每个元素都有一个补元 5. 设，*为普通乘法。则代数系统的幺元为( )（a）不存在 （b）（c）（d）6. 下列图中( )是根树（a）（b）（c）（d）7. 左图(0)相对于完全图k5的补图为( ) 8. 集合a上的关系r是相容关系的必要条件是（ ）（a）自反、反对称的 （b）反自反、对称的 （c）传递、自反的 （d）自反、对称的9. 公式g=pp ,则g是（ ）。（a）永真的 （b）永假的 （c）可满足的 （d）析取的10. 在图g=中,结点总度数与边数的关系是（ ）（a）（b）（c）（d） 二、填空题（每题2分，共20分）1. 设p、q是命题公式，填写如下的基本等价关系式：（1） pq ；（2）pq ；2. 论域d=1，2，指定谓词pp (1，1)p (1，2)p (2，1)p (2，2)ttff则公式真值为 。3. 下图所示的哈斯图中，是格的为 。 4. 在一个群g，*中，若g中的元素a的阶是k，则a-1的阶是 。5. 一个图的欧拉回路是一条通过图中 的回路。6. 给定图g，若存在一条路满足 ，这条路称作汉密尔顿路。7. 一个代数系统,如果运算*是 和 ，则称代数系统为半群。8. 一个命题公式称为合取范式，当且仅当它具有形式 。9. 设*是定义在集合a上的二元运算，如果对于任意的x,ya, 都有 ，则称该二元运算*是可交换的。10. 若图g=v,e满足 ，则g称为连通图。三、判断题（每题1分，共10分）1. 若命题合式公式a的对偶式是a*，则aa*。（ ）2. “今天你吃饭了吗？”这句话不是命题。（ ）3. 设s为集合x上的二元关系，则s是传递的当且仅当sss。（ ）4. 不可能有偶数个结点，奇数条边的欧拉图。（ ）5. 有最大元和最小元的偏序集并不一定是格。（ ）6. 连通图的生成树是唯一的。（ ）7. 在任意图中,存在奇数个度数为奇数的结点。（ ）8. 群的运算表中的每一行或每一列不一定是g的元素的一个置换。（ ）9. 设是一个群，是的一个子群，则中的幺元e一定是中的幺元。（ ）10. k5不是平面图。（ ）四、解答题（5小题，共30分）1. （5分）什么是集合的覆盖，如何根据集合a的一个覆盖确定a元素间的一个相容关系？ 2. （3分）设a=0,1,2，b=0,2,4，列出二元关系r=|x,y的所有元素。3. （8分）求公式 (pq)( pr) 的主析取范式和主合取范式。（10分）设集合a,b,c,d上的关系,写出它的关系矩阵和关系图，并用矩阵运算方法求出的传递闭包。4. （6分）某年级共有9门选修课程，期末考试前必须提前将这9门课程考完，每人每天只在下午考一门课，若以课程表示结点，有一人同时选两门课程，则这两点间有边（其图如右），问至少需几天？ 五、证明（2小题，共20分）1. （10分）用规则p ,t和cp推证： bd, (ca)dbc。2. （10分）设i+是正整数集，a=|xi+yi+，r=,|xv=yuaa，证明r是一个等价关系。常熟理工学院20 20 学年第 学期离散数学考试试卷（试卷库08卷）试题总分： 100 分 考试时限：120 分钟题号一二三四五总分阅卷人得分一、选择题（每题2分，共20分）1. 命题“有的人喜欢所有的花”的逻辑符号化为( )设d：全总个体域，f（x）：x是花，m(x) ：x是人，h(x,y)：x喜欢y（a） （b）（c） （d）2. 给定公式，当d=a,b时，解释( )使该公式真值为f。（a）p(a)=0、p(b)=0（b）p(a)=0、p(b)=1（c）p(a)=1、p(b)=1（d）p(a)=1、p(b)=03. 下面集合( )关于整除关系构成格（a）2,3,6,12,24,36 （b）1,2,3,4,6,8,12（c）1,2,3,5,6,15,30 （d）3,6,9,124. q为有理数集n，q上定义运算*为a*b=a+bab，则的幺元为( ) （a）a（b）b（c）1（d）05. 设n阶图g有m条边，每个结点度数不是k就是k+1，若g中有nk个k度结点，则nk=( )（a）nk（b）n(k+1)（c）n(k+1)-m（d）n(k+1)-2m 6. 设g是一棵树，n,m分别表示顶点数和边数，则( )（a）n=m （b） n=m+1 （c） m=n+1 （d）不能确定7. 集合a上的关系r是相容关系的必要条件是（ ）（a）自反、反对称的 （b）反自反、对称的 （c）传递、自反的 （d）自反、对称的8. z是整数集合,对于下列*运算,哪个代数系统是半群（ ）（a） （b） （c） （d）9. 无向图g中的边e是其割边的充分必要条件是（ ）（a）边e是平行边 （b）边e不是平行边 （c）边e不包含在g的任一简单回路中 （d）边e不包含在g的某一回路中。10. 设集合a=1,2,3,10,在集合a上定义运算,不是封闭的为（ ）（a）（最小公倍数） （b）（最大公约数）（c） （d）二、填空题（每题2分，共20分）1. 设p、q是命题公式，填写如下的基本等价关系式：（1）(pq) $ ；（2） pq ；2. 若解释i的论域d仅包含一个元素，则 在i下真值为 。3. 设a=a，b，c，d ，a上二元运算如下：*a b c dabcda b c db c d ac d a bd a b c那么代数系统的幺元是 ，有逆元的元素为 。4. n个结点的有向完全图边数是 ，每个结点的度数是 。5. 给定图g，若存在一条回路满足 ，这个回路称作汉密尔顿