离散数学全部试卷.doc

.离散数学试题与答案试卷一一、填空 20% （每小题2分）1设 （N：自然数集，E+ 正偶数） 则 。2A，B，C表示三个集合，文图中阴影部分的集合表达式为 A B C 。3设P，Q 的真值为0，R，S的真值为1，则的真值= 。4公式的主合取范式为 。5若解释I的论域D仅包含一个元素，则 在I下真值为 。6设A=1，2，3，4，A上关系图为则 R2 = 。8图的补图为 。二、选择 20% （每小题 2分）1、下列是真命题的有（）A ； B；C ； D 。2、下列集合中相等的有（ ） A4，3；B，3，4；C4，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=（ ）AA ；BP(A) ；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A7、下列函数是双射的为（ ）Af : IE , f (x) = 2x ； Bf : NNN, f (n) = ；Cf : RI , f (x) = x ； Df :IN, 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度结点。A1；B2；C3；D4 。五、计算 18%2、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（分）试卷二一、填空 20% （每小题2分）1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。2、论域D=1，2，指定谓词PP (1,1)P (1,2)P (2,1)P (2,2)TTFF则公式真值为 。2、 设S=a1 ，a2 ，a8，Bi是S的子集，则由B31所表达的子集是 。3、 设A=2，3，4，5，6上的二元关系，则R= （列举法）。R的关系矩阵MR= 。9、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是 。10、公式的根树表示为 二、选择 20% （每小题2分）1、在下述公式中是重言式为（ ）A；B；C； D。2、命题公式 中极小项的个数为（ ），成真赋值的个数为（ ）。A0； B1； C2； D3 。3、设，则 有（ ）个元素。A3； B6； C7； D8 。4、 设，定义上的等价关系则由 R产 生的上一个划分共有（ ）个分块。A4； B5； C6； D9 。5、设，S上关系R的关系图为则R具有（ ）性质。A自反性、对称性、传递性； B反自反性、反对称性；C反自反性、反对称性、传递性； D自反性 。6、设 为普通加法和乘法，则（ ）是域。A BC D= N 。7、下面偏序集（ ）能构成格。8、在如下的有向图中，从V1到V4长度为3 的道路有（ ）条。A1； B2； C3； D4 。9、在如下各图中（ ）欧拉图。四、计算 14%1、 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）试卷三试题与答案填空 20% （每空 2分）1、 设 f，g是自然数集N上的函数，则 。2、 设A=a，b，c，A上二元关系R= , , , 则s（R）= 。3、 A=1，2，3，4，5，6，A上二元关系，则用列举法 T= ；T的关系图为 ；T具有 性质。4、 集合的幂集= 。5、 P，Q真值为0 ；R，S真值为1。则的真值为 。6、 的主合取范式为 。7、 设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词的自然语言是 。8、 谓词的前束范式为 。二、 选择 20% （每小题 2分）1、 的主析取范式中含极小项的个数为（ ）。A 、2； B、 3； C、5； D、0； E、 8 。2、 给定推理PUSPESTIUG推理过程中错在（ ）。A、-; B、-; C、-; D、-; E、-3、 设S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5，在条件下X与（ ）集合相等。A、 X=S2或S5 ； B、X=S4或S5；C、X=S1，S2或S4； D、X与S1，S5中任何集合都不等。4、 设R和S是P上的关系，P是所有人的集合，则表示关系 （ ）。A、；B、；C、 ； D、。5、 下面函数（ ）是单射而非满射。A、；B、；C、；D、。其中R为实数集，Z为整数集，R+，Z+分别表示正实数与正整数集。6、 设S=1，2，3，R为S上的关系，其关系图为 则R具有（ ）的性质。A、 自反、对称、传递； B、什么性质也没有；C、反自反、反对称、传递； D、自反、对称、反对称、传递。7、 设，则有（ ）。A、1,2 ；B、1,2 ； C、1 ； D、2 。8、 设A=1 ,2 ,3 ，则A上有（ ）个二元关系。A、23 ； B、32 ； C、； D、。10、全体小项合取式为（ ）。A、可满足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。三、 用CP规则证明 16% （每小题 8分）1、2、四、（14%） 集合X=, , , ，R=,|x1+y2 = x2+y1 。1、 证明R是X上的等价关系。 （10分）2、 求出X关于R的商集。（4分）五、（10%）设集合A= a ,b , c , d 上关系R= , , , 要求 1、写出R的关系矩阵和关系图。（4分） 2、用矩阵运算求出R的传递闭包。（6分）六、（20%）1、（10分）设f和g是函数，证明也是函数。2、（10分）设函数，证明 有一左逆函数当且仅当f是入射函数。试卷四试题与答案1填空 10% （每小题 2分）1、 若P，Q，为二命题，真值为0 当且仅当 。2、 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x为实数，则命题的逻辑谓词公式为 。3、 谓词合式公式的前束范式为 。4、 将量词辖域中出现的 和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。5、 设x是谓词合式公式A的一个客体变元，A的论域为D，A(x)关于y是自由的，则 被称为存在量词消去规则，记为ES。2选择 25% （每小题 2.5分）6、 下列语句是命题的有（ ）。A、 明年中秋节的晚上是晴天； B、；C、当且仅当x和y都大于0； D、我正在说谎。7、 下列各命题中真值为真的命题有（ ）。A、 2+2=4当且仅当3是奇数；B、2+2=4当且仅当3不是奇数；C、2+24当且仅当3是奇数； D、2+24当且仅当3不是奇数；8、 下列符号串是合式公式的有（ ）A、；B、；C、；D、。9、 下列等价式成立的有（ ）。A、；B、；C、 ； D、。10、 若和B为wff，且则（ ）。A、称为B的前件； B、称B为的有效结论C、当且仅当；D、当且仅当。11、 A，B为二合式公式，且，则（ ）。A、为重言式； B、；C、； D、； E、为重言式。12、 “人总是要死的”谓词公式表示为（ ）。（论域为全总个体域）M(x)：x是人；Mortal(x)：x是要死的。A、； B、C、；D、13、 公式的解释I为：个体域D=2，P(x)：x3, Q(x)：x=4则A的真值为（ ）。A、1； B、0； C、可满足式； D、无法判定。14、 下列等价关系正确的是（ ）。A、；B、；C、；D、。15、 下列推理步骤错在（ ）。PUSPESTIEGA、；B、；C、；D、3逻辑判断30% 16、 用等值演算法和真值表法判断公式的类型。（10分）17、 下列问题，若成立请证明，若不成立请举出反例：（10分）（1） 已知，问成立吗？（2） 已知，问成立吗？18、 如果厂方拒绝增加工资，那么罢工就不会停止，除非罢工超过一年并且工厂撤换了厂长。问：若厂方拒绝增加工资，面罢工刚开始，罢工是否能够停止。（10分）四、计算10%1、 设命题A1，A2的真值为1，A3，A4真值为0，求命题的真值。（5分）2、 利用主析取范式，求公式的类型。（5分）五、谓词逻辑推理 15%符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。六、证明：（10%）设论域D=a , b , c，求证：。试卷五试题与答案一、填空15%（每空3分）1、设G为9阶无向图，每个结点度数不是5就是6，则G中至少有 个5度结点。2、n阶完全图，Kn的点数X (Kn) = 。3、有向图 中从v1到v2长度为2的通路有 条。4、设R，+，是代数系统，如果R，+是交换群 R，是半群 则称R，+，为环。5、设是代数系统，则满足幂等律，即对有 。二、选择15%（每小题3分）1、 下面四组数能构成无向简单图的度数列的有（ ）。A、（2，2，2，2，2）； B、（1，1，2，2，3）；C、（1，1，2，2，2）； D、（0，1，3，3，3）。2、 下图中是哈密顿图的为（ ）。3、 如果一个有向图D是强连通图，则D是欧拉图，这个命题的真值为（ ）A、真； B、假。4、 下列偏序集（ ）能构成格。5、 设，*为普通乘法，则S，*是（）。A、代数系统； B、半群； C、群； D、都不是。三、证明 48%1、（10%）在至少有2个人的人群中，至少有2 个人，他们有相同的朋友数。2、（8%）若图G中恰有两个奇数度顶点，则这两个顶点是连通的。3、（8%）证明在6个结点12条边的连通平面简单图中， 每个面的面数都是3。4、（10%）证明循环群的同态像必是循环群。5、（12%）设是布尔代数，定义运算*为，求证B，*是阿贝尔群。四、计算22%1、在二叉树中1） 求带权为2，3，5，7，8的最优二叉树T。（5分）2） 求T对应的二元前缀码。（5分）2、 下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。试卷六试题与答案一 填空 15% （每小题 3分）1、 n阶完全图结点v的度数d(v) = 。2、 设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶点，Nk+1个k+1度顶点，则N k = 。3、 算式 的二叉树表示为 。4、 如图给出格L，则e的补元是 。5、 一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元是 。二、选择 15% （每小题 3分）1、设S=0,1,2,3,为小于等于关系，则S，是（ ）。A、群；B、环；C、域；D、格。2、设a , b , c，*为代数系统，*运算如下：*abcaabcbbaccccc则零元为（ ）。A、a； B、b； C、c； D、没有。3、如右图 相对于完全图K5的补图为（ ）。4、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（ ）4度结点。A、1； B、2； C、3； D、4。5、设A，+，是代数系统，其中+，为普通加法和乘法，则A=（ ）时，A，+，是整环。A、； B、；C、； D、。三、证明 50%1、设G是（n,m）简单二部图，则。（10分）2、设G为具有n个结点的简单图，且，则G是连通图。（10分）3、记“开”为1，“关”为0，反映电路规律的代数系统0，1，+，的加法运算和乘法运算。如下：+0101001000110101证明它是一个环，并且是一个域。（14分）4、 是一代数格，“”为自然偏序，则L，是偏序格。（16分）四、10%设是布尔代数上的一个布尔表达式，试写出的析取范式和合取范式（10分）五、10%如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。试卷七试题与答案一、 填空 15% （每小题 3分）1. 任何(n,m) 图G = (V,E) , 边与顶点数的关系是 。2. 当n为 时,非平凡无向完全图Kn是欧拉图。3. 已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,则T中有 个1度顶点。4. n阶完全图Kn的点色数X(KN)= 。5. 一组学生,用两两扳腕子比赛来测定臂力大小,则幺元是 。二、 选择 15% （每小题 3分）1、下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7； B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。2、图 的邻接矩阵为( )。A、；B、；C、；D、。3、下列几个图是简单图的有( )。A. G1=(V1,E1), 其中 V1=a,b,c,d,e,E1=ab,be,eb,ae,de；B. G2=(V2,E2)其中V2=V1,E2=,；C. G=(V3,E3), 其中V3=V1,E3=ab,be,ed,cc；D. G=(V4,E4),其中V4=V1,E4=（a,a）,（a,b）,（b,c）,（e,c）,（e,d）。4、下列图中是欧拉图的有( )。5、，其中，为集合对称差运算，则方程的解为（ ）。A、； B、； C、； D、。三、 证明 34% 1、 证明：在至少有2 个人的人群中，至少有2 个人，他的有相同的朋友数。（8分）2、 若图G中恰有两个奇数顶点，则这两个顶点是连通的。（8分）3、 证明：在6个结点12条边的连通平面简单图中，每个面的面度都是3。（8分）4、 证明循环群的同态像必是循环群。（10分）四、 中国邮递员问题13%求带权图G中的最优投递路线。邮局在v1点。根树的应用 13%在通讯中，八进制数字出现的频率如下：0：30%、1：20%、2：15% 、3：10%、4：10%、5：5%、6：5%、7：5%求传输它们最佳前缀码（写出求解过程）。10%设B4=e , a , b , ab ，运算*如下表，*证明是一个群（称作Klein四元群试卷八试题与答案一、 填空 15% （每小题 3分）1、 n阶完全图Kn的边数为 。2、 右图 的邻接矩阵A= 。 3、 图 的对偶图为：4、 完全二叉树中，叶数为nt，则边数m= 。5、 设为代数系统，* 运算如下：*abcaabcbbaccccc则它的幺元为 ；零元为 ； a、b、c的逆元分别为 。二、 选择 15% （每小题 3分）1、 图 相对于完全图的补图为（ ）。 2、 对图G 则分别为（ ）。A、2、2、2； B、1、1、2； C、2、1、2； D、1、2、2 。3、 一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有（ ）片树叶。A、3； B、4； C、5； D、64、 设是代数系统，其中+，为普通的加法和乘法，则A=（ ）时是整环。A、； B、；C、； D、。5、 设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的最小公倍数）。三、 证明 45% 1、设G是（n,m）简单二部图，则。（8分）2、设G为具有n个结点的简单图，且则G是连通图。（8分）3、设G是阶数不小于11的简单图，则G或中至少有一个是非平图。（14分）4、记“开”为1，“关”为0，反映电路规律的代数系统0，1，+，的加法运算和乘法运算。如下：+0101001000110101证明它是一个环，并且是一个域。（15分）四、 生成树及应用 10%1、（10分）如下图所示的赋权图表示某七个城市及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。2、（10分）构造H、A、P、N、E、W、R、对应的前缀码，并画出与该前缀码对应的二叉树，写出英文短语HAPPY NEW YEAR的编码信息。五、 5%对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N”。MaxMin+可结合性可交换性存在幺元存在零元试卷九试题与答案一、 填空 30% （每空 3分）1、 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”则A= 。2、 集合A=,的幂集P(A) = 。3、 设A=1，2，3，4，A上二元关系R=，画出R的关系图 。4、 设A=, , B=,则= 。= 。5、 设|A|=3，则A上有 个二元关系。6、 A=1，2，3上关系R= 时，R既是对称的又是反对称的。7、 偏序集的哈斯图为，则= 。8、 设|X|=n，|Y|=m则（1）从X到Y有 个不同的函数。（2）当n , m满足 时，存在双射有 个不同的双射。9、 是有理数的真值为 。10、 Q：我将去上海，R：我有时间，公式的自然语言为 。11、 公式的主合取范式是 。12、 若是集合A的一个分划，则它应满足 。二、 选择 20% （每小题 2分）1、 设全集为I，下列相等的集合是（ ）。A、； B、；C、； D、。2、 设S=N，Q，R，下列命题正确的是（ ）。A、； B、；C、； D、。3、 设C=a,b,a,b，则分别为（ ）。A、C和a,b；B、a,b与；C、a,b与a,b；D、C与C4、 下列语句不是命题的有（ ）。A、 x=13； B、离散数学是计算机系的一门必修课； C、鸡有三只脚；D、太阳系以外的星球上有生物； E、你打算考硕士研究生吗？5、 的合取范式为（ ）。A、 ；B、 ；C、 D、。6、 设|A|=n，则A上有（）二元关系。A、2n ； B、n2 ； C、； D、nn ； E、。7、 设r为集合A上的相容关系，其简化关系图（如图），则 I r产生的最大相容类为（ ）；A、； B、； C、； D、II A的完全覆盖为（ ）。A、； B、；C、； D、。8、 集合A=1，2，3，4上的偏序关系图为 则它的哈斯图为（ ）。9、 下列关系中能构成函数的是（ ）。A、；B、；C、； D、。10、N是自然数集，定义（即x除以3的余数），则f是（ ）。A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。三、 简答题 15% 1、(10分)设S=1 , 2 , 3 , 4, 6 , 8 , 12 , 24，“”为S上整除关系，问：（1）偏序集的Hass图如何？（2）偏序集的极小元、最小元、极大元、最大元是什么?2、（5分）设解释R如下：DR是实数集，DR中特定元素a=0，DR中特定函数，特定谓词，问公式的涵义如何？真值如何？四、 逻辑推理 10%或者逻辑难学，或者有少数学生不喜欢它；如果数学容易学，那么逻辑并不难学。因此，如果许多学生喜欢逻辑，那么数学并不难学。五、10%设X=1,2,3,4,5，X上的关系R= , , , , ，用Warshall方法，求R的传递闭包t (R)。六、证明 15%1、 每一有限全序集必是良序集。（7分）2、 设是复合函数，如果满射，则也是满射。（8分）试卷十试题与答案一、 填空 10% （每小题 2分）1、 若P，Q为二命题，真值为1，当且仅当 。2、 对公式中自由变元进行代入的公式为 。3、 的前束范式为 。4、 设x是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y的自由的，则 被称为全称量词消去规则，记为US。5、 与非门的逻辑网络为 。二、 选择 30% （每小题 3分）1、 下列各符号串，不是合式公式的有（ ）。A、； B、；C、； D、。2、 下列语句是命题的有（ ）。A、2是素数；B、x+5 6；C、地球外的星球上也有人；D、这朵花多好看呀！。3、 下列公式是重言式的有（ ）。A、；B、；C、；D、4、 下列问题成立的有（ ）。A、 若，则； B、若，则；C、若，则； D、若，则。5、 命题逻辑演绎的CP规则为（ ）。A、 在推演过程中可随便使用前提；B、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果；C、如果要演绎出的公式为形式，那么将B作为前提，设法演绎出C；D、设是含公式A的命题公式，则可用B替换中的A。6、 命题“有的人喜欢所有的花”的逻辑符号化为（ ）。设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y A、；B、；C、；D、。7、 公式换名（ ）。A、；B、；C、；D、。8、 给定公式，当D=a,b时，解释（ ）使该公式真值为0。A、P(a)=0、P(b)=0；B、P(a)=0、P(b)=1；C、P(a)=1、P(b)=0；D、P(a)=1、P(b)=19、 下面蕴涵关系成立的是（ ）。A、；B、；C、；D、。10、下列推理步骤错在（ ）。PUSESUGEGA、；B、；C、；D、。三、 逻辑判断 28%1、（8分）下列命题相容吗？2、（10分）用范式方法判断公式 是否等价。3、（10分）下列前提下结论是否有效？今天或者天晴或者下雨。如果天晴，我去看电影；若我去看电影，我就不看书。故我在看书时，说明今天下雨。四、 计算 12%1、（5分）给定3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数。 求复合命题：的真值。2、（7分）给定解释I：D=2，3，L（x,y）为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求谓词合式公式的真值。五、 逻辑推理20%1、（10分）所有有理数是实数，某些有理数是整数，因此某些实数是整数。2、（10分）符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是骗子”。并推证其结论。试卷十一试题与答案一、 填空 20% （每小题 2分）1、 称为命题。2、命题PQ的真值为0，当且仅当 。3、一个命题含有4个原子命题，则对其所有可能赋值有 种。4、所有小项的析取式为