常熟理工学院20 ～20 学年第 学期
《离散数学》考试试卷（试卷库01卷）
试题总分： 100 分 考试时限：120 分钟
题号 得分 一 二 三 四 五 总分 阅卷人 一、单项选择题（每题2分，共20分）
1. 下列表达式正确的有( )
（A） ( P Q ) Q （B）PQP
（C）(PQ)(PQ)P （D）P(PQ)T
2. 设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为真。
（A）PQR （B）RPS （C）SQR （D）(PR)(QS) 3. 集合A={1,2,…,10}上的关系R={ （A）自反的 （B）对称的 （C）传递的，对称的 （D）传递的 4. 设G1{0,1,2},，G2{0,1},*，其中表示模3加法，*表示模2乘法，在集合G1G2上定义如下运算： a,b,c,dG1G2,有a,bc,dac,bd,称G1G2,为G1G2的积代数，则G1G2的积代数幺元是( ) （A）<0，0> （B）<0，1> （C）<1，0> （D）<1，1> 5. 下图中既不是Eular图，也不是Hamilton图的图是( ) 6. 设GV,E为无向图，V7,E23，则G一定是( ) （A）完全图 （B）树 （C）简单图 （D）多重图 7. 设P：我将去镇上,Q：我有时间。命题“我将去镇上,仅当我有时间”符号化为（ ）。 （A） PQ （B）QP （C）PQ （D）QP 8. 在有n个结点的连通图中,其边数（ ） （A）最多有n-1条 （B）最多有n 条 （C）至少有n-1条 （D）至少有n条 9. 设A－B＝,则有（ ） （A）B＝ （B）B （C）AB （D）AB 10. 设集合A上有3个元素,则A上的不同的等价关系的个数为（ ） （A）5 （B）7 （C）3 （D）6 二、填空题（每题2分，共20分） 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 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— * α β γ δ α δ α β α β α β γ δ γ β γ γ γ δ γ δ γ δ 那么，代数系统 设A={<1，2>，<2，4>，<3，3>}，B={<1，3>，<2，4>，<4，2>} AB= 。 AB= 。 三、判断题（每题1分，共10分） 1. 命题公式(A(AB))B是一个矛盾式。（ ） 2. A,B,C是集合，若ABAC，则必有BC。（ ） 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分）求公式 (P∨Q)R 的主析取范式和主合取范式。 3. （5分）已知一棵无向树中有2个2度顶点、1个3度顶点、3个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？ 4. （7分）权数1，4，9，16，25，36，49，，81，100构造一棵最优二叉树。 5. （5分）集合A{1,2,3,4}上的关系，R{1,3,3,1,3,4,4,3}IA，写出关系矩阵M，画出关系图并讨论R的 R性质。 五、证明（3小题，共20分） 1. （10分）用推理P,T规则证明：PQ， P→R, Q→S RS。 2. （5分）设Ａ，Ｂ，Ｃ是三个集合，证明：(A－B)(A－C)=A－(BC)。 3. （5分）设 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库02卷） 试题总分： 100 分 考试时限：120 分钟 题号 得分 一 二 三 四 五 总分 阅卷人 一、选择题（每题2分，共20分） 1. 下列公式中哪些是永真式？( ) （A）(┐PQ)→(Q→R) （B） (PQ)→P 2. 下列推导错在( ) ①xy(xy) P （C） P→(Q→Q) （D）P→(PQ) 第 2 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— ②y(zy) ③zz ④x(xx) （A）② US① ES② UG③ （C） ③ （D）无 （B） ④ 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）2 7. 在谓词演算中,P(a)是xP(x)的有效结论,根据是（ ）。 （A）US规则 （B） UG规则 （C） ES规则 （D） EG规则 8. 设F(x):x在上海工作；G(x):x是上海人。则命题“在上海工作的人未必都是上海人”的符号化为（ ）。 A．x(F(x)G(x)) （B）x(F(x)G(x)) （C）x(F(x)G(x)) （D） x(F(x)G(x)) 9. 集合A上的关系R是相容关系的必要条件是（ ） （A）自反,反对称的 （B）反自反,对称的 （C）传递,自反的 10. 下列各式错误的是（ ） （A） （B）{} （C） （D）{} （D）自反,对称的 二、填空题（每题2分，共20分） 1. 设P、Q是命题公式，填写如下的基本等价关系式： （1）┐(P∨Q) ； （2） PQ ； 2. 若集合A上的关系R 满足 的三个性质，则R是偏序关系。 3. 设A，B是两命题公式，AB当且仅当 。 4. 给定无孤立点图G，若存在一条路满足 ，该条路称为欧拉路。 5. 一个 称为布尔格。 6. 对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N” 可结合性 可交换性 存在幺元 存在零元 Max Min + 7. 设 9. 由集合A和B的所有共同元素组成的集合称为A和B的交集，记作AB ，即AB={ }。 10. 的图称为完全图。 三、判断题（每题1分，共10分） 第 3 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 1. “北京与天津的距离很近”是复合命题。（ ） 2. 如果A∨CB∨C，则有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: A→B, 则f 的逆关系是函数当且仅当f 是入射。（ ） 9. 群 四、解答题（3小题，共20分） 1. （5分）简述二叉树的定义。如何将任何一棵有序树（m叉树）改写为对应的二叉树？ 2. （8分）求公式 (P→Q)R 的主析取范式和主合取范式。 3. （7分）如下图所示的赋权图表示某七个城市v1,v2,,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方 案，使得各城市之间能够通信而且总造价最小。 五、证明（4小题，共30分） 1. （10分）用推理P,T规则证明：P→Q，QR，R，SPS。 2. （10分）若R和S都是非空集A上的等价关系，则RS是A上的等价关系。 3. （6分）若图G不连通，则G的补图G是连通的。 4. （4分）I(整数集)上的二元运算*定义为：a,bI，a*b=a+b-2。证明 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库03卷） 试题总分： 100 分 考试时限：120 分钟 题号 得分 一 二 三 四 五 总分 阅卷人 一、单项选择题（每题2分，共20分） 1. 在下述公式中不是重言式为( ) （A）(PQ)(PQ) （B） （C）(PQ)Q （D）P(PQ) 2. 设A,B{,{}}，则B－A是( ) （A）{{}} （B）{} （C）{,{}} （D） 3. 设A={1，2，…，10 }，则下面定义的运算*关于A封闭的有( ) （A）x*y=max(x ，y) （B）x*y=质数p的个数使得xpy （C）x*y=(x ， y) ( (x ，y)表示x和y的最大公约数) （D）x*y=lcm(x ，y) （lcm(x ，y) 表示x和y的最小公倍数） 4. 设 第 4 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— （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,4} 5. 在有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）9 7. 公式G=P￢P ,则G是（ ） （A）永真的 （B）永假的 （C）可满足的 （D）析取的 8. 设P,Q的真值为0,R,S的真值为T,则下面命题公式中真值为T的是（ ）. （A）RP （B）QS （C）PS （D）QR 9. A={1,2,3}上的关系R={<1,1><1,2><1,3><3,3>},则R具备（ ） （A）传递性与反对称性 （B）传递性与对称性 （C） 自反性与对称性 （D）反自反性与对称性 10. 连通图G是一颗树,当且仅当满足下述条件中那一个（ ） （A）有些边不是割边。 （B）每条边都是割边 （C）每条边都不是割边 （D）无割边集 二、填空题（每题2分，共20分） 1. 设P、Q是命题公式，填写如下的基本等价关系式： （1） P→Q ； （2）PQ ； 2. 若对命题P赋值T，Q赋值F，则命题PQ的真值为 。 3. 代数系统 x ≤ y = x|y ， 则xy= 。 5. 公式(P(PQ))((PQ)R的根树表示为 。 6. 重言式又叫 式，其定义为 。 7． 给定无孤立点图G，若存在一条回路满足 ，该回路称为欧拉回路。 8． 设R为X到Y的关系，S为从Y到Z上的关系， R°S称为R和S的复合关系，则R°S= 。 9． 设 三、判断题（每题1分，共10分） Q(x)：x曾读过大学，1. 设P(x)：x是研究生， 命题“所有的研究生都读过大学”符号化为：x(P(x)Q(x))。（ ） 2. 设P，Q是两个命题，当且仅当P，Q的真值均为T时，PQ的值为T。（ ） 3. 设A={a，b，c}， RA×A且R={ 5. 代数系统中一个元素若有左逆元，则该元素一定也有右逆元。（ ） 6. 合式公式的定义是用一个递归形式给出的。（ ） 7. 格〈L,≤〉所诱导的代数系统为〈L,∧，∨〉，则运算∧，∨满足分配律。（ ） 8. 设函数f: A→B, 则f 的逆关系是函数当且仅当f 是满射。（ ） 9. 群 四、解答题（4小题，共30分） 1. （5分）请解释谓词演算推理理论的US规则，UG规则，ES规则和EG规则。 2. （8分）求公式 (P→Q)(RP) 的主析取范式和主合取范式。 3. （10分）集合A{2,3,6,12,24,36}上的偏序关系R为整除关系。设B{6,12}，C{2,3,6}，试画出R的哈斯图， 第 5 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 并求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，(E→F)→D，EB。 2. （6分）证明在6个结点12条边的简单连通平面图中， 每个面的次数都是3。 3. （6分） 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库04卷） 试题总分： 100 分 考试时限：120 分钟 题号 得分 一 二 三 四 五 总分 阅卷人 一、选择题（每题2分，共20分） 1. 命题“尽管有人聪明，但未必一切人都聪明”的符号化（P(x)：x是聪明的，M(x)：x是人）( ) （A）x(M(x)P(x))(x(M(x)P(x))) （B）x(M(x)P(x))(x(M(x)P(x))) （C）x(M(x)P(x))(x(M(x)P(x))) （D）x(M(x)P(x))(x(M(x)P(x))) 2. 谓词公式x(P(x)yR(y))Q(x)中的x是( ) （A）自由变元 （C） 既不是自由变元又不是约束变元 （B）约束变元 （D）既是自由变元又是约束变元 3. 集合A={1，2，3，4}上的偏序关系如图(0)，则它的哈斯图为( ) 4. 设A , ,,是布尔代数，f是从An到A的函数，则( ) （A）f是布尔代数 （B）f能表示成析取范式，也能表示成合取范式 （C）若A={0，1}，则f一定能表示成析取范式，也能表示成合取范式 （D）若f是布尔函数，它一定能表示成析（合）取范式 5. 设s{1,111,2,,3,,4}，*为普通乘法，则 （C）群 （D）都不是 （A）代数系统 6. 设无向图G有1边且每个顶点的度数都是3，则图G有( )个顶点 （A）10 （B）4 （C）8 （D）12 7. 一个割边集与任何生成树之间( ) （A）没有关系 （B）至少有一条公共边 （C）有一条公共边 （D）割边集诱导子图是生成树 8. 集合A上的等价关系R,决定了A的一个划分,该划分就是（ ） （A）商集A/R （B）交集AR （C）差集A-R （D）并集AR 9. 公式G=P￢P ,则G是（ ） （A）永真的 （B）永假的 （C）可满足的 （D）析取的 10. 在有n个结点的连通图中,其边数（ ） （A）最多有n-1条 （B）至少有n-1条 （C）最多有n 条 （D）至少有n条 第 6 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 二、填空题（每题2分，共20分） 1. 设P、Q是命题公式，填写如下的基本等价关系式： （1）┐(P∧Q) ； （2） PQ ； 2. n个命题变元有 个互不等价的极小项。 3. 设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶点，Nk+1个k+1度顶点，则 Nk= 。 4. 设集合S={α，β，γ，δ，ζ}，S上的运算*定义为 * α β γ δ ζ α α β γ δ ζ β β δ α α δ γ γ α β γ α δ δ γ α δ γ ζ ζ δ β γ ζ 则代数系统 5. 具有 的图称为欧拉图。 6. 设*是定义在集合A上的一个二元运算，θ为A中的一个元素，如果对于任一x∈A,有 ，则称θ为A中关 于运算*的零元。 7. 是存在量词消去规则，简称ES规则。 8. R在A上是自反的 R。 9. 若偏序集A的每一个非空子集存在最小元，则称偏序集A为 集。 10. 设图G= 三、判断题（每题1分，共10分） 1. 命题公式(P(PQ))Q是重言式。（ ） 2. 公式x(P(x)Q(x))R(y)中x的辖域为P(x)。（ ） 3. 不可能有某种关系，既是对称的，又是反对称的。（ ） 4. 在任何有向图中，所有结点的入度的平方和等于所有结点的出度的平方和。（ ） 5. 设S={1，2}，则S在普通加法和乘法运算下都封闭。（ ） 6. PQ是一个合取范式。（ ） 7. 格〈L,≤〉所诱导的代数系统为〈L,∧，∨〉，则运算∧，∨满足结合律。（ ） 8. 设函数f: A→B, 则f 的逆关系是函数当且仅当f 是双射。（ ） 9. 群 四、解答题（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上的二元运算：对任意 关于二元运算*的幺元以及当a0时， 6. 五、证明（2小题，共20分） 1. （10分）用推理P,T规则证明：P→(Q→R)，R→(Q→S) P→(Q→S)。 ˆA,使得xˆ*xe。 2. （10分）设 第 7 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库05卷） 试题总分： 100 分 考试时限：120 分钟 题号 得分 一 二 三 四 五 总分 阅卷人 一、选择题（每题2分，共20分） 1. 下列是真命题的有( ) （A） {a}{{a}} （B）{{}}{{},} 2. 下列集合中哪个是最小联结词集( ) （A）{,} （B）{,} （C） {,} （D）{,,} （C）{{},} （D）{{}} 3. 设S{ 1, 2, 3 }，S上关系R的关系图如下 ，则R具有( )性质 （A）自反性、对称性、传递性 （B）反自反性、反对称性 （C）反自反性、反对称性、传递性 （D）自反性 4. 设s{1,111,2,,3,,4}，*为普通乘法，则 （C）群 （D）都不是 （A）代数系统 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上定义运算,不是封闭的为（ ） （B）a,bA,a*b{a,b}（最大公约数） （A）a,bA,a*bmax{a,b} （C）a,bA,a*blcm{a,b}（最小公倍数） （D）a,bA,a*bmin{a,b} 9. 设R和S是集合A上的等价关系,则RS的对称性（ ） （A）一定不成立 （B）一定成立 （C）不一定成立 （D）不可能成立 10. 图G和G’的结点和边分别存在一一对应关系是G和G’同构的（ ） （A） 必要条件 （B） 充分条件 （C）充要条件 （D）既不充分也不必要条件 二、填空题（每题2分，共20分） 1. 设P、Q是命题公式，填写如下的基本等价关系式： （1） P→Q ； （2）PQ ； 2. 任意两个不同小项的合取为 ，全体小项的析取式为 。 3. 设S={a1，a2，…，a8}，Bi是S的子集，且设B1={a8},则由B31所表达的子集是 。 4. 设集合S={α，β，γ，δ，ζ}，S上的运算*定义为 第 8 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— * α β γ δ ζ α α β γ δ ζ β β δ α α δ γ γ α β γ α δ δ γ α δ γ ζ ζ δ β γ ζ 则代数系统 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. 命题公式(P(PQ))Q是重言式。（ ） Q(x)：x曾读过大学，2. 设P(x)：x是研究生， 命题“所有的研究生都读过大学”符号化为：x(P(x)Q(x))。（ ） 3. AB当且仅当A∩B=A。（ ） 4. 在有向图中，所有结点的入度平方之和等于出度平方之和。（ ） 5. 设 10. (x)(A(x)∨B(x)) (x)A(x)∨(x)B(x)（ ） 四、解答题（5小题，共30分） 1. （5分）什么是集合的划分，如何根据集合A的一个划分确定A的元素间的一个等价关系？ 2. （8分）求公式 ┐(P∧R)∧(P∨Q)的主析取范式和主合取范式。 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规则证明：P→Q，P→R，R→SS→Q。 2. （10分）设A{1,2,3,,9}，在AA上定义关系R:a,b,c,dR当且仅当adbc，证明R是AA上的 等价关系，并求出[<2,5>]R。 第 9 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库06卷） 试题总分： 100 分 考试时限：120 分钟 题号 得分 一 二 三 四 五 总分 阅卷人 一、单项选择题（每题2分，共20分） x犯错误,命题“没有不犯错误的人”符号化为( ) x是人，P(x)：1. 设M(x)：（A）x(M(x)P(x)) （B）(x(M(x)P(x))) （C）(x(M(x)P(x))) （D）(x(M(x)P(x))) 2. 下列公式是重言式的有( ) （A）(PQ)Q （B） （C）(QP)P （D） 3. 设A={} ，B=Р(Р(A)) 下列( )表达式不成立 （A）B （B）B （C） B B （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）4 7. 设G是一个哈密尔顿图，则G一定是( ) （A）欧拉图 （B）树 （C）平面图 （D）连通图 8. 设R和S是集合A上的等价关系,则RS的对称性（ ） （A）不一定成立 （B）一定不成立 （C）一定成立 （D）不可能成立 9. 设G= （A）n-m-2 （B）m-n+2 （C）n+m-2 （D）m+n+2 （D） 10. 在0____之间填上正确的符号是（ ） （A） = （B） （C） 二、填空题（每题2分，共20分） 1. 设P、Q是命题公式，填写如下的基本等价关系式： （1）┐(P∧Q) ； 3. 设A{a,b,c}考虑下列子集 S1{{a,b},{b,c}}，S2{{a},{a,b},{a,c}}，S3{{a},{b,c}}，S4{{a,b,c}}。 （2） PQ ； 2. 若P，Q，为二命题，PQ真值为F 当且仅当 。 S5{{a},{b},{c}}，S6{{a},{a,c}}。 则是A的覆盖的子集有 ，是A的划分的子集有 。 4. 设 （A）若a，b，x∈G，ax=b，则x= 。 （B）若a，b，x∈G，ax=ab，则x= 。 5. n阶无向完全图Kn的边数是 ，每个结点的度数是 。 第 10 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 6. 无向图G具有一条欧拉回路，当且仅当G是连通的，且 。 7. 一般来说，命题公式用 联结词组表示。 8. 是反对称的RR 。 9. 设函数f : AB，g: CD，如果A=C，B=D，且 ，则称函数f和g相等，记作f = g。 10. 在无向图G中，如果结点u和v之间 ，则结点u和v称为是连通的。 c 三、判断题（每题1分，共10分） 1. 若P为命题变元，P∧P为主合取范式。 （ ） 2. 如果AB，则有￢A￢B。（ ） 3. 设R1和R2是集合A上的关系，且R1R2，则有t(R1) t(R2)。（ ） 4. 在完全二元树中，若有t片叶子，则边的总数e2t1。（ ） 5. 独异点的运算表中任意两行都是不相同的。（ ） 6. 任意平面图G最多是5-色的。（ ） 7. AB = BA （ ） 8. 群中的运算不满足消去律。（ ） 9. 质数阶群不一定是循环群。（ ） 10. (x)F(x) (x)F(x) （ ） 四、解答题（5小题，共30分） 1. （5分）已知一个偏序关系，如何画出它的哈斯图？ 2. （8分）求公式 (P→Q)(RP) 的主析取范式和主合取范式。 3. （6分）如右图给出的赋权图表示六个城市a,b,c,d,e,f及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各 城市间能够通讯且总造价最小，并计算出最小总造价。 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规则证明：A∨B→C∧D，D∨E→FA→F。 2. （10分）R是实数集， 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）x(L(x)A(x,y)) （B）x(L(x)y(J(y)A(x,y))) （C）xy(L(x)J(y)A(x,y)) （D）xy(L(x)J(y)A(x,y)) 第 11 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 2. 命题逻辑演绎的CP规则为( ) （A）在推演过程中可随便使用前提 （B）在推演过程中可随便使用前面演绎出的某些公式的逻辑结果 （C）设(A)是含公式A的命题公式，BA，则可用B替换(A)中的A （D）如果要演绎出的公式为BC形式，那么将B作为前提，演绎出C 3. 下列命题正确的是( ) （A）2N,NS 则2S （C）NQ,QR 则NR （B）NQ,QS 则NS （D）N,S 则NS 4. 设 （A） 每个元素都至少有一个补元 （B） 每个元素都有多个补元 （C）每个元素都无补元 （D） 每个元素都有一个补元 mn5. 设G{23m,nI}，*为普通乘法。则代数系统G,的幺元为( ) （A）不存在 （B）e2030 （C）e23 6. 下列图中( )是根树 （A）G1{a,b,c,d},{a,a,a,b,c,d} （C）G3{a,b,c,d},{a,b,a,d,c,a} 7. 左图(0)相对于完全图K5的补图为( ) （D）e2131 （B）G2{a,b,c,d},{a,b,b,d,c,d} （D）G4{a,b,c,d},{a,b,a,c,d,d} 8. 集合A上的关系R是相容关系的必要条件是（ ） （A）自反、反对称的 （B）反自反、对称的 （C）传递、自反的 （D）自反、对称的 9. 公式G=P￢P ,则G是（ ）。 （A）永真的 （B）永假的 （C）可满足的 （D）析取的 10. 在图G= （A）deg(vi)2|E| （B）deg(vi)|E| （C） deg(v)2|E| ivV（D） deg(v)|E| ivV二、填空题（每题2分，共20分） 1. 设P、Q是命题公式，填写如下的基本等价关系式： （1） P→Q ； 2. 论域D={1，2}，指定谓词P P (1，1) P (1，2) P (2，1) P (2，2) T T F F （2）PQ ； 则公式xyP(y,x)真值为 。 3. 下图所示的哈斯图中，是格的为 。 4. 在一个群〈G，*〉中，若G中的元素a的阶是k，则a-1的阶是 。 5. 一个图的欧拉回路是一条通过图中 的回路。 6. 给定图G，若存在一条路满足 ，这条路称作汉密尔顿路。 7. 一个代数系统 第 12 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 9. 设*是定义在集合A上的二元运算，如果对于任意的x,y∈A, 都有 ，则称该二元运算*是可交换的。 10. 若图G=〈V,E〉满足 ，则G称为连通图。 三、判断题（每题1分，共10分） 1. 若命题合式公式A的对偶式是A*，则AA*。（ ） 2. “今天你吃饭了吗？”这句话不是命题。（ ） 3. 设S为集合X上的二元关系，则S是传递的当且仅当SSS。（ ） 4. 不可能有偶数个结点，奇数条边的欧拉图。（ ） 5. 有最大元和最小元的偏序集并不一定是格。（ ） 6. 连通图的生成树是唯一的。（ ） 7. 在任意图中,存在奇数个度数为奇数的结点。（ ） 8. 群 9. 设 四、解答题（5小题，共30分） 1. （5分）什么是集合的覆盖，如何根据集合A的一个覆盖确定A元素间的一个相容关系？ 2. （3分）设A={0,1,2}，B={0,2,4}，列出二元关系R={ （10分）设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{ 4. （6分）某年级共有9门选修课程，期末考试前必须提前将这9门课程考完，每人每天只在下午考一门课，若以课程表示结点， 有一人同时选两门课程，则这两点间有边（其图如右），问至少需几天？ 五、证明（2小题，共20分） 1. （10分）用规则P ,T和CP推证： B∨D, (C→A)→DB→C。 2. （10分）设I+是正整数集，A={ 关系。 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库08卷） 试题总分： 100 分 考试时限：120 分钟 题号 得分 一 二 三 四 五 总分 阅卷人 一、选择题（每题2分，共20分） 1. 命题“有的人喜欢所有的花”的逻辑符号化为( ) 设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y （A） x(M(x)y(F(y)H(x,y))) （B）x(M(x)y(F(y)H(x,y))) （C） x(M(x)y(F(y)H(x,y))) （D）x(M(x)y(F(y)H(x,y))) 第 13 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 2. 给定公式xP(x)xP(x)，当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)=0 3. 下面集合( )关于整除关系构成格 （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,12} 4. Q为有理数集N，Q上定义运算*为a*b=a+b–ab，则 （A）a （B）b （C）1 （D）0 5. 设n阶图G有m条边，每个结点度数不是k就是k+1，若G中有Nk个k度结点，则Nk=( ) （A）n×k （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） a*ba （B） a*bab （C）a*baab （D）a*bab 9. 无向图G中的边e是其割边的充分必要条件是（ ） （A）边e是平行边 （B）边e不是平行边 （C）边e不包含在G的任一简单回路中 （D）边e不包含在G的某一回路中。 10. 设集合A={1,2,3,,10},在集合A上定义运算,不是封闭的为（ ） （A）a,bA,a*blcm{a,b}（最小公倍数） （B）a,bA,a*b{a,b}（最大公约数） （C）a,bA,a*bmax{a,b} （D）a,bA,a*bmin{a,b} 二、填空题（每题2分，共20分） 1. 设P、Q是命题公式，填写如下的基本等价关系式： （1）┐(P∨Q) ； （2） PQ ； 2. 若解释I的论域D仅包含一个元素，则 xP(x)xP(x) 在I下真值为 。 3. 设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 那么代数系统 4. n个结点的有向完全图边数是 ，每个结点的度数是 。 5. 给定图G，若存在一条回路满足 ，这个回路称作汉密尔顿回路。 6. 含有 的半群称为独异点。 7. 要证明AB ，必须证明 。 8. 设 RAA 且 A, 则r( R ) = 。 9. 设*是定义在集合A上的二元运算，如果对于任意的x,y∈A,都有 ,则称二元运算*在A上是封闭的。 10. 简单有向图G=〈V,E〉中，任意一对结点间，至少有一个结点到另一个结点是可达的，则称这个图为 连通图。 三、判断题（每题1分，共10分） 1. 关系R是对称的，当且仅当关系矩阵是对称的，或在关系图上，任两个结点间若有定向弧线，必是成对出现的。（ ） 2. “这件作品多有创意！”这句话不是命题。（ ） 3. 设集合S={1，2，3，4}，S上的关系R={<1，1>，<2，2>，<1，3>}，则R具有自反性。（ ） 4. 无多重边的图是简单图。（ ） 5. 循环群的任何子群必定是循环群。（ ） 6. 连通图的生成树是不唯一的。（ ） 第 14 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 7. A(BC) = (AB)(AC) （ ） 8. 群中可以有零元。（ ） 9. 如果〈L, ≤〉是格，S是L的子集且〈S, ≤〉是格，则〈S, ≤〉一定是〈L, ≤〉的子格。（ ） 10. 任何一棵有序树都可以改写为唯一的一棵二叉树，同样，任何一棵二叉树都对可以改回成唯一的一棵有序树。（ ） 四、解答题（5小题，共30分） 1. （5分）什么是商集，如何根据集合A的一个等价关系R求得A关于R的一个商集？ 2. （8分）求公式 (R→Q)P 的主析取范式和主合取范式。 3. （10分）设集合Ａ＝{a,b,c,d,e}上的关系Ｒ＝{ 求出Ｒ的传递闭包。 4. （3分）设A={1,2,3,4,5}，B={1,2}，列出二元关系R={ 五、证明（3小题，共20分） 1. （8分）利用规则P，T或CP推证：（P∧Q）,Q∨R,RP。 2. （6分）求一棵带权为1,1,1,2,2,3,4,5的最优二叉树T,并计算W(T)。 ˆA,使得xˆ*xe。证明e是 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库09卷） 试题总分： 100 分 考试时限：120 分钟 题号 得分 一 二 三 四 五 总分 阅卷人 一、单项选择题（每题2分，共20分） 1. 公式xy(P(x,y)Q(y,z))xP(x,y)换名( ) （A）xu(P(x,u)Q(u,z))xP(x,y) （B）xy(P(x,u)Q(u,z))xP(x,u)； （C）xy(P(x,y)Q(y,z))xP(x,u) （D）uy(P(u,y)Q(y,z))uP(u,y)。 2. 下面蕴涵关系不成立的是( ) （A）xP(x)xQ(x)x(P(x)Q(x)) （B）xP(x)xQ(x)x(P(x)Q(x)) （C）xP(x)xQ(x)x(P(x)Q(x)) （D）xyA(x,y)yxA(x,y) 3. 判断下列命题哪个为正确？( ) （A）{Ф}∈{Ф,{{Ф}}} （B）{Ф}{Ф,{{Ф}}}` （C）Ф∈{{Ф}} （D）{a,b}∈{a,b,{a},{b}} （D）(P（A），) 4. 下列哪个偏序集构成有界格( ) （A）（N，） （B）（Z，） （C）（{2，3，4，6，12}，|（整除关系）） 5. 6阶群的子群的阶数可以是( ) （A）1，2，5 （B）2，4 （C）3，6，7 （D）2，3 6. 一棵树有7片树叶，3个3度结点，其余全是4度结点，则该树有( )个4度结点 （A）1 （B）2 （C）3 （D）4 7. 设G是有n个结点m条边的连通平面图，且有k个面，则k等于( ) （A）m-n+2 （B）n-m-2 （C）n+m-2 （D）m+n+2 8. 设F(x):x在上海工作；G(x):x是上海人。则命题“在上海工作的人未必都是上海人”的符号化为（ ） （A）x(F(x)G(x)) （B）x(F(x)G(x)) （C）x(F(x)G(x)) （D） x(F(x)G(x)) 9. 设V={a,b,c,d},则与V构成强连通图的边集为（ ） （A）E1={ （C）E3={ 第 15 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 10. 下列公式中不是合式公式的是（ ） （A）QRS （B）P（RS） （C）PQR （D）P（RS） 二、填空题（每题2分，共20分） 1. 设P、Q是命题公式，填写如下的基本等价关系式： （1） PQ ； （2）PQ ； 2. 一般说来，n个命题变元共有 个小项（或大项）。 3. 设 (1)若ca=b，则c= ; (2) 若ca=ba，则c= 。 4. 具有 的图称为汉密尔顿图。 5. 设 ，则称 6. n个命题变元的析取式，称为布尔析取或大项，是指： 。 7. 的传递性是指： 。 8. 设 RAA 且 A, 则s( R ) = 。 9. 设*是定义在集合A上的二元运算，如果对于任意的x,y,z∈A都有 ,则称该二元运算*是可结合的。 10. 简单有向图G=〈V,E〉中，如果对于图G中的任意两个结点两者之间是互相可达的，则称这个图为 图。 三、判断题（每题1分，共10分） 1. 任意两个矛盾式的合取还是矛盾式。（ ） 2. 如果￢A￢B，则有AB。（ ） 3. 任意无限集合必含有可数子集。（ ） 4. 没T是一棵m叉树，它有t片树叶，i个分枝点，则(m-1)i = t-1。（ ） 5. 设Q为有理数集，Q上运算*定义为abmax(a,b)，则 7. 在任意图中,度数为奇数的结点不一定是偶数个。（ ） 8. 设*定义在集合A上的一个二元运算，如果A中有关于运算*的左幺元el和右幺er,则A中有幺元。（ ） 9. 任何一个循环群必定是阿贝尔群。（ ） 10. 简单图除了K5和K3，3外都是平面图。（ ） 四、解答题（5小题，共30分） 1. （5分） 2. （8分）求公式（PR）Q 的主析取范式和主合取范式。 3. （4分）设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求RR和R-1的关系矩阵。 4. （8分）求出带权为2，3，5，7，8，9的最优二叉树T，并求W（T）。 5. （5分）图给出的赋权图表示五个城市v1，v2，v3，v4，v5及对应两城镇间公路的长度。试给出一个最优化的设计方案使 得各城市间能够有公路连通。 五、证明（2小题，共20分） 1. （10分）用推理P,T规则证明：（P Q）,（Q R）,（R S）（P S）。 2. （10分）设集合A＝{a,b,c,d}，A上的关系R={ （1）写出关系R的关系矩阵； （2）求R的自反闭包,对称闭包和传递闭包； （3）求包含R的最小的等价关系。 第 16 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库10卷） 试题总分： 100 分 考试时限：120 分钟 题号 得分 一 二 三 四 五 总分 阅卷人 一、选择题（每题2分，共20分） 1. 下列哪个公式为永真式？( ) （A）QQ→P （B）QP→Q 2. 设S{,{1},{1,2}}，则有( )S （A）{{1,2}} （B）{1,2 } （C）{1} （D）{2} （C）PP→Q （D）P(PQ)P 3. 下列结果正确的是( ) （A）(AB)AB （B）(AB)A （C）(AB)BA （D）{} 4. 设I为整数集合，m是任意正整数，Zm是由模m的同余类组成的同余类集合，在Zm上定义运算[i][j][(ij)modm]，则代 数系统Zm,m最确切的性质是( ) （A）封闭的代数系统 （B）半群 （C）独异点 （D）群 5. 一棵无向树T有4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有( )片树叶 （A）3 （B）4 （C）6 （D）5 6. 设V{a,b,c,d,e,f}，E{a,b,b,c,c,a,a,d,d,e,f,e}，则有向图 GV,E是( ) （A）强连通的 （B）单侧连通的 （C）弱连通的 （D）不连通的 7. 设有33盏灯,拟公用一个电源,则至少需有五插头的接线板数（ ） （A）7 （B）8 （C）9 （D）14 8. 下列代数系统 （A）G为整数集合 （B）G为偶数集合 （C）G为有理数集合 （D）G为自然数集合 9. 谓词公式x(P(x)yR(y))Q(x)中量词x的辖域是（ ）。 （A）x(P(x)yR(y)) （B）P(x) （C）(P(x)yR(y)) （D）Q(x) 10. 无向图G是欧拉图,当且仅当（ ） （A）G中所有结点的度数全为偶数 （B）G连通且所有结点度数全为偶数 （C）G的所有结点的度数全为奇数 （D）G连通且所有结点度数全为奇数 二、填空题（每题2分，共20分） 1. 设P、Q是命题公式，填写如下的基本等价关系式： （1）┐(P∧Q) ； b c b c a c c c （2） PQ ； 2. 设< {a，b，c}， * >为代数系统，* 运算如下： * a a a b b c c 则它的幺元为 ；a、b的逆元分别为 。 3. 当G8时，群G,只能有 阶非平凡子群，平凡子群为 。 4. 树T的边数e与点数v有关系 。 5. 设G＝〈V，E〉是一个无向图，如果能够在平面上把G画成 ，就称G是一个平面图。 6. 设 第 17 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 7. 设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x，y)：x可以整数y。则谓词wffx(P(x)y(O(y)N(y,x)))的自然语言是 。 8. 设 RAA 且 A, 则t( R ) = 。 9. 设*，Δ是定义在集合A上的两个二元运算，如果对于任意的x,y,z∈A都有 ,则称运算 *对于运算Δ是可分配的。 10. 简单有向图G=〈V,E〉中，如果在图G中略去方向，将它看成是无向图，图是连通的，则称该有向图为 。 三、判断题（每题1分，共10分） 1. “北京到天津的距离很近”是复合命题。（ ） 2. 一个有限平面图，面的次数之和等于该图的结点度数。（ ） 3. 有人能够证明存在一个无限集，其基数是严格介于0与之间的。（ ） 4. 一条回路和任何一棵生成树至少有一条公共边。（ ） 5. 循环群不一定是Abel群。（ ） 6. PQ不是一个析取范式。（ ） 7. K5不是平面图。（ ） 8. 设*定义在集合A上的一个二元运算，如果A中有关于运算*的左零元θl和右零θr,且θl=θr,则A中有零元。（ ） 9. x(F(y) →G(x))F(y) →xG(x)。（ ） -1 10. 设 四、解答题（5小题，共30分） 1. （5分）请叙述群的定义。 2. （8分）求公式（PQ）R的主析取范式和主合取范式。 3. （4分）设A={a,b}，P(A)为A的幂集，求集合P(A)A。 4. （5分）设Ａ＝｛1,2,3,4,5,6｝，B={0,1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=2｝，求：(1)RR ；(2) R 。 -1 y 5. （8分）若传递a ，b， c， d ，e， f 的频率分别为2%， 3% ，5 %， 7% ，8% ，9%，求传输它的最佳前缀码，要求写出 详细的求解过程。 五、证明（3小题，共20分） 1． （8分）用推理P,T,CP规则证明：A→(B→C),(C∧D)→E,G→(D∧E) A→(B→G)。 2． （8分）设 (1)求a的等价类[a]R； (2)求商集A/R。 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库11卷） 试题总分： 100 分 考试时限：120 分钟 题号 得分 一 二 三 四 五 总分 阅卷人 一、单项选择题（每题2分，共20分） 1. 下列等价关系正确的是( ) （A）x(P(x)Q(x))xP(x)xQ(x) （C）x(P(x)Q)xP(x)Q （B）x(P(x)Q(x))xP(x)xQ(x) （D）x(P(x)Q)xP(x)Q 2. 设R,S是集合A上的关系，则下列说法正确的是( ) （A）若R,S 是自反的， 则RS是自反的 （B）若R,S 是反自反的， 则RS是反自反的 （C）若R,S 是对称的， 则RS是对称的 （D）若R,S 是传递的， 则RS是传递的 3. 设f，g是函数，当( )时，f=g 第 18 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— （A）xdomf 都有 f(x)g(x) （C） domgdomf 且 fg （B） f与g的表达式相同 （D）domgdomf,rangefrangef 4. 在Peterson图 中，至少填加( )条边才能构成Euler图 （A）1 （B）2 （C）4 （D）5 则Q中满足( ) （D）所有元素都无逆元 5. 在有理数集Q上定义的二元运算*，x,yQ有x*yxyxy， （A）只有唯一逆元 （B） xQ,x1时有逆元x1 6. 下面给出的符号串集合中,哪一个不是前缀码（ ） （A）｛1,10,110,1111｝ （B）｛01,001,000,1｝ （C）｛b,c,aa,ac,aba,abc｝ （D）｛0011,01,101,11,100｝ （C） 所有元素都有逆元 7. 在自然数集合N上定义的二元运算,满足结合律的运算是（ ） （A）ab=a-b （B）ab=a+4b （C）ab=min{a,b} （D）ab=|a-b| 8. 设集合A={1,2,3,,10},在集合A上定义如下运算,不是封闭的有（ ） （A）a,bA,a*blcm{a,b}（最小公倍数） （B）a,bA,a*b{a,b}（最大公约数） （C）a,bA,a*bmax{a,b} （D）a,bA,a*bmin{a,b} 9. 设S={0，1}，*为普通乘法，则< S ， * >是( ) （A）半群，但不是独异点 （B）群 （C）环，但不是群 10. 在0____之间填上正确的符号是（ ） （A） = （B） （C） （D） （D） 只是独异点，但不是群 二、填空题（每题2分，共20分） 1． 由集合A的 组成的集合,称为A的幂集，记作P (A)，即P (A)={x|xA}。 2． 若一个集合A的若干个非空子集S1,S2 ,…,Sm满足 ，则这些非空子集的全体叫做A的一个覆盖。 3． 设 6． 设G是一个连通平面图，由图中的边所包围的区域，在区域内既不包含图的 ，也不包含图的 ，这样的区域称为图G 的一个面。 7． 设P、Q是命题公式，填写如下的基本等价关系式： （1）P→Q ； （2） PQ ； 8． 给定集合A的一个覆盖S={S1,S2 ,…,Sm}，若 ，则S称作是A的一个划分。 9． 图的补图为 。 10． n个结点的无向完全图Kn的边数为 。 三、判断题（每题1分，共10分） 1. (x)(A(x)∧B(x)) (x)A(x)∧(x)B(x)（ ） 2. 使命题公式P(QR)的真值为F的真值指派的P、Q、R值分别是T、T、F。（ ） 3. 集合A上的恒等关系是一个双射函数。（ ） 4. 任一简单图G的最大度数Δ（G）不一定小于G的顶点数。（ ） 5. 设A,,是布尔代数，则A,,一定为有补分配格。（ ） 6. 命题公式是有真假值的。（ ） 7. 设〈L,≤〉是一个格，那么对L中任何元素a,b,c,d,若a≤b，则a∨c≤b∨c，a∧c≤b∧c。（ ） 8. 存在基数严格介于其0与之间的无限集。（ ） 第 19 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 9. 群中的运算不满足消去律。（ ） 10. K3，3不是平面图。（ ） 四、解答题（5小题，共30分） 1. （5分）什么是偏序关系？如何确定偏序集〈L，≤〉中最大元，极大元。 2. （8分）求公式 (PR)(QR)P 的主析取范式和主合取范式。 3. （7分）权数1，2，3，4，5，6，7，8，9，10构造一棵最优二叉树。 4. （5）集合A{1,2,3,4}上的关系R{1,1,1,3,2,2,3,3,3,1,3,4,4,3,4,4}，写出关系矩阵 MR，画出关系图并讨论R的性质。 5. （5分）已知一棵无向树中有3个2度顶点、1个3度顶点、2个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？ 五、证明（3小题，共20分） 1. （10分）用推理P,T规则证明：PQ， P→R, Q→S RS。 2. （5分）证明对集合A、B和C,有（A∩B）∪C=A∩(B∪C) 当且仅当CA。 3. （5分）设 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库12卷） 试题总分： 100 分 考试时限：120 分钟 题号 得分 一 二 三 四 五 总分 阅卷人 一、选择题（每题2分，共20分） 1. 下列推理步骤错在( ) ①x(F(x)G(x)) P ②F(y)G(y) ③xF(x) ④F(y) ⑤G(y) ⑥xG(x) （A）② P ES③ T②④I （C） ④ （D）⑥ US① EG⑤ （B） ⑤ 2. 设A={1，2，3，4}，P(A)（P(A)是A的幂集）上规定二元系R{s,t|s,tp(A)(|s||t|}则P(A)/ R=( ) （A）A （B）P（A） （C）{[]R,[{1}]R,[{1,2}]R,[{1,2,3}]R,[{1,2,3,4}]R } （D）{[]R,[2]R,[2,3]R,[2,3,4]R,[A]R } 3. Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确 ( ) （A）AB，BC则AC （B）AB，BC则 A∈B 4. 下图中是哈密顿图的为( ) （D）A∈B，B∈C则 AC （C）A∈B，B∈C则 A∈C 5. 在有n个顶点的连通图中，其边数( ) （A）最多有n-1条 （B）至少有n 条 （C）最多有n条 （D）至少有n-1 条 6. 在自然数集合N上定义的二元运算,满足结合律的是（ ） （A）ab=a-b （B）ab=min{a,b} （C）ab=a+4b （D）ab=|a-b| 第 20 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 7. 连通图G是一棵树当且仅当G中（ ） （A）有些边不是割边 （B）每条边都是割边 （C）无割边集 （D）每条边都不是割边 8. 集合A上的关系R是相容关系的必要条件是（ ） （A）自反,反对称的 （B）反自反,对称的 （C）传递,自反的 （D）自反,对称的 9. 具有6个结点的树的边数为（ ） （A）4 （B）6 （C）5 （D）8 10. 集合A上的一个覆盖确定A的元素间的关系为：（ ） （A）相容关系 （B） 全序关系 （C）等价关系 （D）偏序关系 二、填空题（每题2分，共20分） 1. 设S={a，b，c} 若S1={c},则S6的集合表示为 。 2. 若S{S1 ,S2 ,, Sm}是集合A的一个划分，则它应满足 。 3. 设S是非空有限集，代数系统＜P（S），，＞中，P（S）对的幺元为 ， 零元为 。P(S）对的幺元为 ，零元为 。 4. n阶完全图结点v的度数deg(v) = 。 5. 设*是定义在集合A上的一个二元运算，如果对于任意的x∈A,都有 ,则称运算*是等幂的。 6. 集合A={，{}}的幂集P(A) = 。 7. 证明AB，即证AB是重言式，有两种证法：（1） ，（2） 。 8. R在A上被称为传递的 。 9. 设 三、判断题（每题1分，共10分） 1. (x)(F(x) →G(y))(x)F(x) →G(y)。（ ） 2. 如果f是函数，则其逆关系f也是函数。（ ） 3. 对任意集合A， B， C有(A－B)－C=A－(B∩C)。（ ） 4. 任何有向图中各结点入度之和等于边数。（ ） 5. 在有幺元e的代数系统< S,> 中，如果*是可结合的运算，且每个元素都有左逆元,那么这个代数系统中任何一个元素的左逆 元必定也是该元素的右逆元，且每个元素的逆元是唯一的。（ ） 6. 一个有限平面图，面的次数之和等于该图的边数的二倍。（ ） 7. (AB)C = A(BC) （ ） 8. 设 10. 谓词公式xP(x)xQ(x)yR(y)的前束范式是xzy(P(x)Q(z)R(y))。（ ） c 四、解答题（3小题，共20分） 1. （5分）请简述“哥尼斯堡七桥问题”，该问题是否有解？为什么？ 2. （8分）求公式 (P∧R)∧(P∨Q) 的主析取范式和主合取范式。 （7分）如下图所示的赋权图表示某七个城市v1,v2,,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 五、证明（4小题，共30分） 1. （10分）用推理P,T规则证明：P→Q，QR，R，SPS。 2. （10分）若R和S都是非空集A上的等价关系，则RS是A上的等价关系。 第 21 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 3. （4分）设Ａ，Ｂ，Ｃ是三个集合，证明：A (B－C)＝(AB)－(AC)。 4. （6分）I(整数集)上的二元运算*定义为：a,bI，a*b=a+b-2。证明 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库13卷） 试题总分： 100 分 考试时限：120 分钟 题号 得分 一 二 三 四 五 总分 阅卷人 一、单项选择题（每题2分，共20分） 1. 若公式(PQ)(PR)的主析取范式为m001m011m110m111则它的主合取范式为( ) （A）m001m011m110m111 （B）M000M010M100M101 ； （C）M001M011M110M111 （D）m000m010m100m101 。 （B）x(P(x)Q(x))xP(x)xQ(x) （D）x(P(x)Q)xP(x)Q 2. 下列各式中哪个不成立( ) （A）x(P(x)Q(x))xP(x)xQ(x) （C）x(P(x)Q(x))xP(x)xQ(x) 3. 设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为( ) 4. 设[{a ， b ， c}，*]为代数系统，*运算如下： * a b c 则零元为( ) （A）a （B）b a a b c b b a c c c c c （C） 没有 （D） c 5. 下面那一个图可一笔画出( ) 6. 在任何图中必定有偶数个( ) （A）度数为偶数的结点 （B）入度为奇数的结点 （C）度数为奇数的结点 （D）出度为奇数的结点 7. 下列命题正确的是（ ） （A）{a}{a,b,c} （B）（A） （C）{a,b,c} （D）{a,b}{a} 8. 设集合A上有四个元素,则A上的不同的划分的个数为（ ） （A）11 （B）14 （C）17 （D）15 9. 设 （A）B的上确界bA且唯一 （C）B的上界bB且不唯一 （B）B的极大元bA且不唯一 （D）B的极大元bB且唯一 10. 无向图G中的边e是G的割边的充要条件为（ ） （A）e是重边 （B）e不是重边 （C）e不包含在G的任一简单回路中 （D）e不包含在G的某一回路中 第 22 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 二、填空题（每题2分，共20分） 1. 设A={a,b,c},A上二元关系R={ [i]3[j][(ij)mod3]， 4. 欧拉图的充要条件是 。 5. 设A，R A A，若R是 ，则称R为A上的等价关系。 6. 设*是定义在集合A上的一个二元运算， e为A中的一个元素, 如果对于任意x∈A,有 ，则称e为Ａ中关于 运算*的幺元。 7. 在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的 范式。 8. 由所有集合A和B的所有元素组成的集合称为A和B的并集，记作AB ，即AB={ }。 9. 设 住元素x。 10. n个结点的无向完全图 Kn 的边数为 。 三、判断题（每题1分，共10分） 1. (x)(A→G(x))A →(x)G(x)（ ） 2. 设集合A，B，C都是D的子集，则AB当且仅当A∩B= A。（ ） 3. 整数集合上的相等关系可确定A的一个划分。（ ） 4. 一个图是平面图，当且仅当它包含与Ｋ3，3或Ｋ5在２度结点内同构的子图。（ ） 5. 任何一个循环群必定是阿贝尔群。（ ） 6. 设G为有v个结点e条边的连通平面图，若v≥3，则e≥3v-6。（ ） 7. A(BC) = (AB)(AC) （ ） 8. 群中不可以有零元。（ ） 9. 任何群都有非平凡子群。（ ） 10. 谓词公式xP(x)xQ(x)yR(y)的前束范式是 。（ ） 四、解答题（5小题，共30分） 1. （5分）什么是图的正常着色？简述韦尔奇·鲍威尔法(Welch Powell)对图进行着色的方法。 2. （8分）求公式(P→Q)→R的主析取范式和主合取范式。 3. （4分）设A={a,b}, B={c}。求集合(AB)2。 4. （7分）设集合A={3,5,15,27,},A上的偏序关系为R={ 大元素、极小元素、下界、上确界。 5. （6分）求一棵带权为1,4,9,16,25,36,49,的最优二叉树T,并计算W(T)。 五、证明（3小题，共20分） 1. （8分）用推理P,T规则证明：A∨B→C∧D, D∨E→FA→F。 2. （4分）设Ａ，Ｂ是二个集合，证明：AB=A(B-A)。 3. （8分）已知S是一个非空集合,为对称差运算满足结合律,P(S)为S的幂集,证明代数系统 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库14卷） 试题总分： 100 分 考试时限：120 分钟 第 23 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 题号 得分 一 二 三 四 五 总分 阅卷人 一、选择题（每题2分，共20分） 1. 下述命题公式中，是重言式的为( ) （A）(pq)(pq) （B）pq((pq)(qp)) （C）(pq)q （D）(pq)q 2. 对任意集合A,B,C,下列结论正确的是（ ） （A）若AB,BC,则AC； （B）若AB,BC,则AC； （C）若AB,BC,则AC； （D）若AB,BC,则AC； 3. 设S{ 1, 2, 3 }，定义SS上的等价关系, SS上一个划分共有( )个分块。 ,则由R产生的 （D）9 （A）4 （B）5 （C）6 4. 下列偏序集( )能构成格 5. 连通图G是一棵树当且仅当G中( ) （A）有些边是割边 （B）每条边都是割边 （C）所有边都不是割边 （D）图中存在一条欧拉路径 6. 有n个结点(n3)，m条边的连通简单图是平面图的必要条件( ) （A） m3n6 （B）n3m6 （C）m3n6 （D） n3m6 7. 设P,Q的真值为0,R,S的真值为1,则下面命题公式中真值为1的是（ ） （A）RP （B）QS （C）PS （D）QR 8. 在图G= （A）deg(vi)2|E| （B）deg(vi)|E| （C） deg(v)2|E| ivV（D） deg(v)|E| ivV9. 设有33盏灯,拟公用一个电源,则至少需有五插头的接线板数（ ） （A）７ （B）８ （C）９ （D）１４ 10. 设集合A上有四个元素,则A上的不同的等价关系的个数为（ ） （A）11 （B）14 （C）17 （D）15 二、填空题（每题2分，共20分） 1. 设A={a，b，c，d}，其上偏序关系R的哈斯图为 则R= 。 2. 设A{x|x2n,nN}，定义A上的二元运算*为普通乘法、除法和加法，则代数系统 3. A，B，C表示三个集合，文氏图中阴影部分的集合表达式为 。 A B C 。 4. 矛盾式又叫 式，其定义为 。 5. 的图称为无向图。 6. 设 8. 设R是非空集合A上的等价关系，对任意的aA，定义 为a关于R的等价类。 9. 设 第 24 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 10. 的无向图称为树。 三、判断题（每题1分，共10分） 1. 公式xP(x)yQ(x,y)的前束范式为xy(P(x)Q(x,y))。（ ） 2. (AB)C=(AC) (BC)。（ ） 3. 不存在既对称又反对称的关系。（ ） 4. 若无向连通图G中存在桥，则G的点连通度和边连通度都是1。（ ） 5. {{Ø}}{ Ø，{{Ø}}}。（ ） 6. 任意图结点度数的总和等于边数的两倍。（ ） 7. 设A,,是布尔代数，则A,,一定为有补分配格。（ ） 8. 群中有零元。（ ） 9. 质数阶群没有非平凡子群。（ ） 10. (x)A(x)∨(x)B(x) (x)(A(x)∨B(x))（ ） 四、解答题（3小题，共20分） 1. （5分）考虑在七天内安排七们功课的考试，使得同一位教师所任的两们课程考试不安排在接连的两天里，试说明如果没有教 师担任多于四门课程，则符合上述要求的考试安排总是可能的。 2. （8分）求公式(QP) ∧P∧R的主析取范式和主合取范式。 3. （7分）已知无向图G有11条边,2度与3度顶点各2个,其余都是4度顶点,求G有几个顶点，写出过程 4. 五、证明（5小题，共30分） 1. （10分）用推理P,T规则证明：P→(Q→R)，R→(Q→S) P→(Q→S)。 2. 对于正整数k,Nk＝{0,1,2,…,k-1},设*k是Nk上的一个二元运算,使得a*kb=a*b(mod k),这里a,b∈Nk。当k＝4时构造出的*k 运算表。（4分） 3. （6分）设R为集合A上的二元关系，如果R是反自反的和可传递的，则R一定是反对称的。 4. （4分）设Ａ，Ｂ，Ｃ是三个集合，证明：A－(BC)＝(A－B)－C。 5. （6分）设G是连通简单平面图，结点数为n（n3），边数为m，面数为r，则r2n4。 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库15卷） 试题总分： 100 分 考试时限：120 分钟 题号 得分 一 二 三 四 五 总分 阅卷人 一、选择题（每题2分，共20分） 1. 给定推理 ①x(F(x)G(x)) ②F(y)G(y) ③xF(x) ④F(y) ⑤G(y) ⑥xG(x) P US① P ES③ T②④I UG⑤ x(F(x)G(x))xG(x) 推理过程中错在( ) （A）①->② （A）domSA （B）②->③ （C）③->④ （D）④->⑤ E. ⑤->⑥ 2. 设SAB，下列各式中( )是正确的 （B） domSB （C）ranSA （D）domS ranS = S 3. 在( )中，补元是唯一的 （A）有界格 （B）有补格 （C）分配格 （D）有补分配格 第 25 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 4. 给定无向图GV,E，如右图所示，下面哪个边集不是其边割集( ) （A）{v1,v4,v3,v4} （C）{v4,v7,v4,v8} （B）{v4,v5,v4,v6} （D）{v1,v2,v2,v3} （B） 连通但删去任何一条边便不连通的图 （D） 每对顶点间都有通路的图 5. 下列哪一种图不一定是树( ) （A）无回路的简单连通图 （C）有n个顶点n-1条边的连通图 6. 命题公式(PQ)P是（ ） （A）永真式 （B）永假式 （C）可满足式 （D）合取范式 7. 设G是简单有向图,可达矩阵P（G）刻画下列（ ）关系 （A）点与边 （B）边与点 （C）边与边 （D）点与点 8. 下列命题正确的是（ ） （A）{ a }{ a,b,c } （B） (A) （C） { a,b,c } （D）{ a,b } { a } 9. 设 A={a,b,c,d},B={1,2,3},从A到B不同的函数共有( )个。 （A） 12 （B） （C） 81 （D）1024 10. 设V={a,b,c,d},则与V构成强连通图的边集为（ ） （A） E1={ 二、填空题（每题2分，共20分） 1. A，B，C表示三个集合，文氏图中阴影部分的集合表达式为 。 A B C 2. 设A={1,2,3}，写出A上既不是对称的又不是反对称的关系R= ；A上既是对称的又是反对称的关系R= 。 3. 已知一棵无向树T有3个3顶点，1个2度顶点，其余的都是1度顶点，则T中有 个1度顶点。 4. 当且仅当 时，我们称“P蕴含Q”，记为 。 5. 的图称为混合图。 6. 在偏序集 关系或线序关系。 7. 如果一个含三个命题变元的公式的主析取范式为：1,3,4,5,7 ，则它的主合取范式为： 。 8. 集合A的一个划分确定A的元素间的一个 关系。 9. 设 三、判断题（每题1分，共10分） 1. 设A、B为任意的命题公式，则(A∧B)∨AA。（ ） 2. 在布尔格 5. 设A,,是布尔代数，则A,,一定为有补分配格。（ ） 6. PQ不是一个析取范式。（ ） 7. 设G为有v个结点e条边的连通平面图，若v≥3，则e≥3v-6。（ ） 8. 设函数 f :A→B, g: B→C都是双射,则(gf )-1= g-1f-1。（ ） 9. 群 四、解答题（5小题，共30分） 1. （5分）什么是汉密尔顿图？请找出一个无向图具有汉密尔顿路的充分条件。 2. （8分）求公式 P(P(Q(QR))) 的主析取范式和主合取范式。 第 26 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— 3. （7分）在通讯中，八进制数字出现的频率如下：0：30%、1：20%、2：15% 、3：10%、4：10%、5：5%、6：5%、7：5%,求传 输它们最佳前缀码（写出详细的求解过程）。 4. （6分）某年级共有9门选修课程，期末考试前必须提前将这9门课程考完，每人每天只在下午考一门课，若以课程表示结点， 有一人同时选两门课程，则这两点间有边（其图如右），问至少需几天？ 2，3，4，5，6}，7为模7乘法。试说明G，7是否构成群？是否为循环群？若是，生成元是什么？ 5. （4分）已知G{1，6. 五、证明（3小题，共20分） 1. （10分）用推理P,T规则证明：（┐P Q）,（┐Q R）,（RS）（PS） 2. （10分）设R是一个二元关系，S={ 等价关系。 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库16卷） 试题总分： 100 分 考试时限：120 分钟 题号 得分 一 二 三 四 五 总分 阅卷人 一、单项选择题（每题2分，共20分） 1. 下列语句是命题的有( ) （A） 我正在说谎 （B）xy0 （C）xy0当且仅当x和y都大于0 （D）今天是晴天 （D）{{a}}P(A) 2. 设A={a,{a}}，下列命题错误的是( ) （A）{a}P(A) （B）{a}P(A) （C）{{a}}P(A) 3. 设R，S是集合A上的关系，则下列( )断言是正确的 （A）R,S自反的，则RS是自反的 （B）若R,S对称的，则RS是对称的 （C）若R,S传递的，则RS是传递的 （D）若R,S反对称的，则RS是反对称的 4. 下列图中是欧拉图的有( ) 5. 在如下的有向图中，从V1到V4长度为3 的道路有( )条 （A）3 （B）2 （C）1 （D）4 6. n个结点的无向完全图Kn的边数为( ) 第 27 页/共 39 页 ———————————阅————卷————密————封————装————订————线—————————— n(n1) 2n(n1) 2（A）n(n1) （B） （C）n(n1) （D） 7. 在谓词演算中,P(a)是xP(x)的有效结论,根据是（ ）。 （A）US规则 （B）UG规则 （C）ES规则 （D）EG规则 8. Z是整数集合,对于下列*运算,哪个 （A）a*bab （B） a*ba （C）a*baab （D）a*bab 9. 设P：我将去镇上,Q：我有时间。命题“我将去镇上,仅当我有时间”符号化为（ ） （A） PQ （B）QP （C）PQ （D）QP 10. 设 A={a,b,c,d},B={1,2,3},从A到B不同的函数共有( )个。 （A） 12 （B） （C） 81 （D）1024 二、填空题（每题2分，共20分） 1. 设E为全集， 称为A的绝对补，记作～A， 且～（～A）= ，～E = ，～= 。 2. 若关系R是等价关系，则R满足 性质。 3. 设A={3，6，9}，A上的二元运算*定义为：a*b=min{a，b}，则在独异点 零元是 。 4. 一个图的哈密尔顿路是一条通过图中 的路。 5. n个命题变元组成的命题公式共有 种不同的等价公式。 6. 在一个图中，两个结点由 关联，则这两个结点称为邻接点。 7. 设 9. 设