1904-全国-离散数学-考前模拟卷-001总分:100一、单项选择题(本大题共15小题,每小题1分,共15分。在每小题列出的备选项中,只有一项是符合题目要求的,请将其选出。)1、下列式子为重言式的是()(1分)A:(┐P∧R)→QB:P∨Q∧R→┐RC:P∨(P∧Q)D:(┐P∨Q)↔(P→Q)2、设A是含n(n≥1)个命题变项的公式,若A是重言式,则A的主析取范式含极小项个数为()(1分)A:0B:1C:nD:2^n3、设论域为{1,2},与公式(∀x)A(x)等价的是()(1分)A:A(1)∨A(2)B:A(1)→A(2)C:A(1)∧A(2)D:A(2)→A(1)4、对于公式(∀x)(∃y)(P(x)∧Q(y))→(∃x)R(x,y),下列说法正确的是()(1分)A:y是自由变元B:y是约束变元C:(∃x)的辖域是R(x,y)D:(∀x)的辖域是(∃y)(P(x)∧Q(y))→(∃x)R(x,y)5、设X={∅,{a},{a,∅}},则下列陈述错误的是()(1分)A:∅∈XB:C:{a}∈X1D:6、下列关系矩阵所对应的关系具有反自反性的是()(1分)A:B:C:D:7、设R是A上的二元关系,r、s、t分别指关系的自反闭包、对称闭包、传递闭包、则下列描述不正确的是()(1分)A:B:C:D:8、等价关系一定不是()(1分)A:对称的B:自反的C:可传递的D:反自反的29、设f是从实数集合R到R的函数,则不是双射函数f(x)的是()(1分)A:x³B:x²C:2x+1D:10、在整数集Z上,下列定义的运算能构成一个群的是()(1分)A:B:C:D:11、下图中d的补元是()(1分)A:0B:1C:bD:c12、设简单图G所有结点的度数之和为24,则G的边数为()(1分)A:6B:8C:12D:2413、下图的最大出度是()(1分)3A:0B:1C:2D:314、下列图中,是欧拉图的为()(1分)A:B:C:D:15、下列无向图一定是树的是()(1分)A:无回路的连通图B:无环的连通图C:每对结点之间都有通路的图D:结点数比边数多1的图4二、填空题(本大题共10小题,每小题2分,共20分。)16、n个命题变元的称为小项,其中每个变元与它的否定不能同时出现,但两者必须。(2分)17、公式(∀x)(∀y)(P(y)→Q(x,z))∧(∃y)R(x,y)的约束变元为,自由变元为。(2分)18、在正整数域中,命题公式∀x∃y(x·y=0)的真值为,命题公式∃x∀y(x·y=1)的真值为.(2分)19、。(2分)20、设有集合A和B,|A|=5,|B|=2,则从A到B不同的满射函数共有个。(2分)21、设A={<1,2>,<2,3>,<2,4>},B={<1,3>,<2,4>,<5,2>},则dom(A∩B)=,ran(A∪B)=。(2分)22、设A为非空有限集合,P(A)为A的幂集,∩为集合的交运算,则群<P(A),∩>的单位元是,零元是。(2分)23、如下图所示的格中,a的补元是,d的补元是。(2分)24、设无向树r有4个度数为3的结点,其余结点都为树叶,则T的树叶数为。(2分)525、(2分),。三、计算题(本大题共10小题,共65分。)26、用列真值表的方法说明下列逻辑等价式成立(P→(Q→R))⇔((P→Q)→(P→R))。(6分)27、用等值演算求P→(Q↔R)的主析取范式。(6分)28、A,B,C是集合,证明:(A-B)-C=A-(B∪C)(6分)。29、下面是某偏序集<A,R>的哈斯图,写出集合A和偏序关系R的表达式。(6分)30、设<S,·>是独异点,e是单位元,且S中任意x,有x·x=e。证明:<S,·>是交换群。(6分)31、(7分)32、设R、S都是A上的二元关系,证明dom(R∪S)=dom(R)∪dom(S)。(7分)33、设G是有n个结点、n条边的简单连通图,且G中存在度数为3的结点。证明:G中至少有一个度数为1的结点。(7分)34、某城市拟在六个城区之间架设有线电视网,其网点间的距离如下列的无向有权图矩阵给出,试给出架设线路的最优方案,请画出图,并计算出最优方案下线6路的长度。(7分)KAOQIANMONIJUANA=35、符号化下列命题,并构造推理证明。一个人只有努力,才能获得成功;每个人或者获得成功,或者曾经失败过;有些人未曾失败过,所以有些人很努力。(7分)7162O8no-O-l90-71o030n4035040052087090261904-全国-离散数学-考前模拟卷-001总分:100一、单项选择题(本大题共15小题,每小题1分,共15分。在每小题列出的备选项中,只有一项是符合题目要求的,请将其选出。)1、【主考点】定义1.10【副考点】定义1.12答案:D解析:(┐P∨Q)⇔(P→Q),所以(┐P∨Q)↔(P→Q)在它的各种指派情况下,其取值均为真,因此为重言式。2、【主考点】定义2.6【副考点】定义2.7答案:D解析:在公式...