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解析：在公式...
