2026年10月自考02324离散数学押题及答案

2026年10月高等教育自学考试02324《离散数学》押题（第1套）（满分100分，考试时间150分钟）▎一、单项选择题（本大题共15小题，每小题2分，共30分）1.设P：明天下雨，Q：我去爬山。命题“只要明天不下雨，我就去爬山”符号化为A.P→QB.┐P→QC.Q→┐PD.┐Q→P2.下列命题公式中，属于重言式（永真式）的是A.P∧┐PB.P∨┐PC.P∧QD.P→Q3.含3个命题变元的重言式，其主析取范式所含小项的个数是A.3B.6C.8D.94.论域为{1,2}，谓词公式∀x∃y(x+y=3)的真值为A.真（1）B.假（0）C.可真可假D.无法确定5.设S(x)：x是学生，P(x)：x是党员。“有的学生是党员”符号化为A.∀x(S(x)→P(x))B.∃x(S(x)∧P(x))C.∃x(S(x)→P(x))D.∀x(S(x)∧P(x))6.设X={1,2,3}，R={<1,1>,<2,2>,<3,3>,<1,2>}，则R一定具有A.对称性B.反对称性C.反自反性D.以上都不具有7.设f:R→R，f(x)=x²，则fA.是单射B.是满射C.是双射D.既不是单射也不是满射8.设|A|=3，|B|=2，则A到B的函数共有A.6个B.8个C.9个D.12个9.偏序关系必须满足的三条性质是A.自反性、反对称性、传递性B.自反性、对称性、传递性C.反自反性、对称性D.对称性、反对称性、传递性10.若A⊆B，则下列各式中正确的是A.A∪B=AB.A∩B=AC.A−B=AD.A⊕B=B11.实数集上定义x∗y=x+y−xy，则运算∗的幺元是A.0B.1C.−1D.不存在12.在6阶循环群中，a为生成元，则元素a²的阶为A.2B.3C.6D.113.有理数集Q关于普通加法和乘法构成A.环但不是整环B.整环但不是域C.域D.偏序集14.下列度数序列中，能构成简单无向图的是A.{4,4,1,1,0}B.{3,3,2,2,0}C.{4,2,2,2,1}D.{3,3,3,1,0}15.n个顶点的树，其边数为A.nB.n−1C.n+1D.n(n−1)/2▎二、填空题（本大题共10小题，每小题2分，共20分）16.公式P∨┐P称为排中律，它是____式。17.任意两个不同小项的合取为____式。18.设E(x)：x是偶数，D(x)：x能被2整除。“所有偶数都能被2整除”符号化为____。19.设A={1,2,3,4,5}，则幂集P(A)的元素个数|P(A)|=____。20.设R={<1,2>,<2,3>,<1,3>}，则定义域domR=____，值域ranR=____。21.设A={a,b}，则A×A=____。22.在群中，(a∗b)⁻¹=____。23.一个连通无向图恰有两个奇点，则该图存在____（填欧拉回路或欧拉通路）。24.完全图K₄的边数为____。25.完全二叉树有n₀个叶子，则度为2的顶点个数n₂=____。▎三、简答题（本大题共7小题，每小题5分，共35分）26.求命题公式(P∨Q)→R的主析取范式。27.用真值表判断命题公式(P∧Q)→(P∨Q)的类型（重言式、矛盾式或可满足式）。28.设集合A={1,2,3,4,6,12}上的整除关系为偏序关系，B={2,3,4,6}。试画出该偏序关系的哈斯图，并求B的极大元与极小元。29.设A={1,2,3}，R={<1,1>,<1,2>,<2,3>,<3,1>}。求R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)。30.设A={1,2,3,4,5}，B={2,4,6,8}。求A∪B、A∩B、A−B、B−A及对称差A⊕B。31.某连通带权图如图所示，试用Kruskal算法求其最小生成树，写出选边过程并计算最小生成树的权。32.给定算术表达式(a+b)∗(c−d)，画出其二叉树表示，并分别写出先序、中序、后序遍历序列。▎四、证明题（本大题共3小题，每小题5分，共15分）33.证明：连通简单平面图的边数m与顶点数n满足m≤3n−6。34.设f:X→Y为一函数，在X上定义关系R：xRy当且仅当f(x)=f(y)。证明R是X上的等价关系。35.用自然推理系统证明：前提P→Q，R→┐Q，R，结论┐P。密押试卷（第2套）（满分100分，考试时间150分钟）▎一、单项选择题（本大题共15小题，每小题2分，共30分）1.设P：努力学习，Q：取得好成绩。“只有努力学习，才能取得好成绩”符号化为A.P→QB.Q→PC.P∧QD.P↔Q2.下列命题公式中，属于矛盾式（永假式）的是A.P∨┐PB.P∧┐PC.P∨QD.P→P3.含3个变元的可满足式（非重言、非矛盾），其主析取范式所含小项个数不可能是A.0B.1C.4D.74.论域为整数集，公式∃x∀y(x≤y)的真值为A.真（1）B.假（0）C.可真可假D.无法确定5.设R(x)：x是实数，I(x)：x是虚数。“所有的实数都不是虚数”符号化为A.∀x(R(x)→┐I(x))B.∃x(R(x)∧I(x))C.∀x(R(x)∧I(x))D.∃x(R(x)→I(x))6.设X={1,2}，R={<1,2>,<2,1>,<1,1>,<2,2>}，则R是A.偏序关系B.等价关系C.反自反关系D.反对称关系7.设f:Z→Z，f(x)=2x，则fA.是单射B.是满射C.是双射D.不是函数8.设|A|=2，|B|=3，则A到B的单射共有A.3个B.6个C.8个D.9个9.关于偏序关系哈斯图的画法，下列说法正确的是A.可以出现双向边B.较小的元素画在下方C.必须画出全部自环D.边表示元素相等10.设A={1,2}，B={2,3}，则对称差A⊕B=A.{1,3}B.{1,2,3}C.{2}D.∅11.集合S上定义x∗y=6（结果恒为6，且6∈S），则该运算A.满足结合律B.必有幺元C.每个元素必有逆元D.满足幂等律12.群中元素a的阶为4，则元素a³的阶为A.2B.3C.4D.113.整数集Z关于普通加法和乘法构成A.域B.整环C.没有乘法幺元的环D.只有加法结构14.无向图所有顶点的度数之和不可能是A.10B.14C.15D.1815.n阶完全图K_n的边数为A.n(n−1)/2B.n²C.n−1D.2n▎二、填空题（本大题共10小题，每小题2分，共20分）16.公式P∧┐P称为矛盾律，它是____式。17.小项m_i与大项M_i之间满足┐m_i=____。18.设I(x)：x是整数，N(x)：x是负数。“有的整数是负数”符号化为____。19.设A={1,2}，用列举法写出幂集P(A)=____。20.设R={<a,b>,<b,c>,<a,c>}，则逆关系R⁻¹=____。21.设|A|=2，|B|=4，则|A×B|=____。22.Klein四元群中，除幺元外每个元素的阶都等于____。23.有向图基图连通且每个顶点入度等于出度，则该图存在____。24.6个顶点的树，其边数为____。25.完全二部图K_{2,3}的边数为____。▎三、简答题（本大题共7小题，每小题5分，共35分）26.求命题公式(P→Q)∧R的主合取范式。27.用真值表判断((P→Q)∧(Q→R))→(P→R)的类型。28.设A={1,2,4,8}上整除关系为偏序关系，B={1,2,4}。画出哈斯图，并求B的极大元与极小元。29.设X={a,b,c}，R={<a,b>,<b,a>,<b,c>,<c,b>}。求r(R)、s(R)、t(R)。30.设A={2,4,6,8,10}，B={3,6,9}。求A∪B、A∩B、A−B、B−A及A⊕B。31.某连通带权图如图所示，用Kruskal算法求最小生成树，写出选边过程并求权。32.给定算术表达式a/(b+c∗d)，画出二叉树，并写出先序、中序、后序遍历序列。▎四、证明题（本大题共3小题，每小题5分，共15分）33.证明：完全图K₅不是平面图。34.在整数集Z上定义关系R：xRy当且仅当x≡y(modn)（即n整除x−y，n为给定正整数）。证明R是等价关系。35.用CP规则证明：前提P→(Q→R)，S→P，Q，结论S→R。密押试卷（第3套）（满分100分，考试时间150分钟）▎一、单项选择题（本大题共15小题，每小题2分，共30分）1.设P：你努力，Q：你会失败。“除非你努力，否则你会失败”符号化为A.P→QB.┐P→QC.Q→PD.┐Q→P2.下列公式中，属于重言式的是A.((P→Q)∧P)→QB.P∧QC.(P∨Q)∧┐PD.P→┐P3.含2个命题变元的矛盾式，其主析取范式所含小项的个数是A.0B.2C.4D.14.论域为{1,2,3}，公式∃x(x²=2x)的真值为A.真（1）B.假（0）C.可真可假D.无法确定5.设M(x)：x是人，L(x)：x能长生不老。“没有人能长生不老”符号化为A.∀x(M(x)→┐L(x))B.∃x(M(x)∧L(x))C.∀x(M(x)∧L(x))D.∃x(M(x)→L(x))6.设X={1,2,3}，R={<1,2>,<2,3>,<1,3>}，则R具有A.自反性B.对称性C.传递性D.自反且对称7.设f:R→R，f(x)=eˣ，则fA.是单射B.是满射C.是双射D.不是函数8.设|A|=4，|B|=2，则A到B的函数共有A.8个B.16个C.6个D.24个9.等价关系必须满足A.自反性、对称性、传递性B.自反性、反对称性、传递性C.对称性、反对称性D.反自反性、传递性10.若A∩B=∅，则对称差A⊕B=A.A∪BB.∅C.A∩BD.A−B11.在实数集上定义x∗y=max(x,y)，则该运算A.不满足结合律B.不满足交换律C.不满足幂等律D.结合律、交换律、幂等律都满足12.在8阶循环群中，a为生成元，则a⁴的阶为A.2B.4C.8D.113.偶数集2Z关于普通加法和乘法构成A.域B.整环C.环（无乘法幺元）D.乘法群14.6个顶点的树，所有顶点度数之和为A.5B.10C.12D.615.完全图K₅的边数为A.10B.5C.20D.15▎二、填空题（本大题共10小题，每小题2分，共20分）16.当P=1、Q=0时，公式P→Q的真值为____。17.重言式的主合取范式所含大项的个数为____。18.设E(x)：x是偶数，P(x)：x是素数。“存在偶素数”符号化为____。19.设A={1,2,3,4}，则|P(A)|=____。20.设R={<1,2>,<2,1>}，则复合关系R∘R（即R²）=____。21.已知|A×B|=12，|A|=3，则|B|=____。22.在群中，方程x∗a=b的唯一解x=____。23.一个图能一笔画成（有欧拉回路），则该图奇点的个数为____。24.n个顶点的连通图至少有____条边。25.完全二叉树有5个叶子，则度为2的顶点有____个。▎三、简答题（本大题共7小题，每小题5分，共35分）26.求命题公式┐(P∧Q)∨R的主析取范式。27.用真值表判断P→(Q→P)的类型。28.设A={1,2,3,6,9,18}上整除关系为偏序关系，B={2,3,9}。画出哈斯图，求B的极大元与极小元。29.设A={1,2,3}，R={<1,2>,<2,1>,<1,1>,<3,3>}。求r(R)、s(R)、t(R)。30.设A={1,2,3}，B={2,3,4}，C={3,4,5}。求A∪B∪C、A∩B∩C及(A⊕B)⊕C。31.某连通带权图如图所示，用Kruskal算法求最小生成树，写出选边过程并求权。32.给定算术表达式(a−b)∗c+d/e，画出二叉树，并写出三种遍历序列。▎四、证明题（本大题共3小题，每小题5分，共15分）33.证明：若连通简单平面图每个面的次数都不小于4，则m≤2n−4。34.证明：正有理数集Q⁺关于普通乘法构成交换群。35.用归谬法证明：前提P→┐Q，Q∨┐R，R∧S，结论┐P。密押试卷（第4套）（满分100分，考试时间150分钟）▎一、单项选择题（本大题共15小题，每小题2分，共30分）1.设P：气温降到0度以下，Q：水结冰。“如果气温降到0度以下，水就会结冰”符号化为A.P→QB.Q→PC.┐P→QD.P∧Q2.下列公式中，属于可满足式（非重言）的是A.P∧┐PB.P∨QC.P∨┐PD.P→P3.含4个变元的重言式，其主合取范式所含大项的个数是A.16B.4C.0D.84.论域为实数集，公式∀x∃y(y>x)的真值为A.真（1）B.假（0）C.可真可假D.无法确定5.设F(x)：x是函数，C(x)：x连续。“有的函数不连续”符号化为A.∀x(F(x)→C(x))B.∃x(F(x)∧┐C(x))C.∃x(F(x)→C(x))D.∀x(F(x)∧┐C(x))6.集合{1,2,3}上关系R的关系矩阵为（110/011/001），则R是A.等价关系B.偏序关系C.对称关系D.反自反关系7.设f:R→R，f(x)=x³，则fA.是单射但非满射B.是满射但非单射C.是双射D.不是函数8.设|A|=3，|B|=3，则A到B的双射共有A.3个B.6个C.9个D.27个9.集合上的划分与下列哪一项一一对应A.等价关系B.偏序关系C.函数D.全序关系10.设A={1,2,3}，B={1,2}，则下列正确的是A.B⊆AB.A⊆BC.A=BD.A∩B=A11.定义x∗y=x（取第一元素），则该运算A.满足交换律B.不满足结合律C.满足结合律但不满足交换律D.不满足幂等律12.群中元素a的阶为12，则a⁸的阶为A.2B.3C.4D.613.模5剩余类集合Z₅关于模5加法和乘法构成A.域B.只是环C.整环但不是域D.乘法群14.下列度数序列中，不能构成无向图的是A.{2,2,2}B.{3,1,1,1}C.{2,2,1,1}D.{3,3,3,1}15.连通且不含回路的无向图称为A.树B.完全图C.欧拉图D.二部图▎二、填空题（本大题共10小题，每小题2分，共20分）16.当P、Q真值相同时，P↔Q的真值为____。17.矛盾式的主析取范式所含小项的个数为____。18.设I(x)：x是整数，Q(x)：x是有理数。“每个整数都是有理数”符号化为____。19.设集合A有6个元素，则|P(A)|=____。20.设R={<a,b>,<b,c>,<c,a>}，则R⁻¹=____。21.设A={x,y,z}，则|A×A|=____。22.群中若a∗a=e，则a的逆元a⁻¹=____。23.连通平面图的欧拉公式为n−m+r=____。24.完全二部图K_{2,4}的边数为____。25.有10个顶点的树，其边数为____。▎三、简答题（本大题共7小题，每小题5分，共35分）26.求命题公式(P∨┐Q)→R的主合取范式。27.用真值表判断(P↔Q)→(P∨Q)的类型。28.设A={1,2,4,5,10,20}上整除关系为偏序关系，B={2,4,5,10}。画出哈斯图，求B的极大元与极小元。29.设X={a,b,c}，R={<a,a>,<a,c>,<b,a>,<c,c>}。求r(R)、s(R)、t(R)。30.设A={2,3,5,7}，B={1,2,3,4,6,12}。求A∪B、A∩B、A−B、B−A及A⊕B。31.某连通带权图如图所示，用Kruskal算法求最小生成树，写出选边过程并求权。32.给定算术表达式a∗b+c/d−e，画出二叉树，并写出三种遍历序列。▎四、证明题（本大题共3小题，每小题5分，共15分）33.证明：简单平面图中至少存在一个度数不超过5的顶点。34.在实数集R上定义x∗y=x+y+1，证明(R,∗)构成群（并判断是否为交换群）。35.用自然推理系统证明：前提P→Q，Q→R，┐R，结论┐P。密押试卷（第5套）（满分100分，考试时间150分钟）▎一、单项选择题（本大题共15小题，每小题2分，共30分）1.双条件联结词P↔Q取真值（1）的条件是A.P、Q同真或同假B.P真Q假C.P假Q真D.P、Q都为假2.下列公式中，属于矛盾式的是A.(P↔Q)∧P∧┐QB.P∨QC.P→QD.P∨┐Q3.含2个变元的公式，其主析取范式为m0∨m1，则该公式A.是重言式B.是矛盾式C.是可满足式D.无法判断4.论域为{1,2,3,4}，公式∀x(x<5)的真值为A.真（1）B.假（0）C.可真可假D.无法确定5.设R(x)：x是实数，Q(x)：x是有理数。“并非所有实数都是有理数”符号化为A.∀x(R(x)→Q(x))B.┐∀x(R(x)→Q(x))C.∃x(R(x)∧Q(x))D.∀x(R(x)∧Q(x))6.设X={1,2}，R={<1,1>,<1,2>,<2,1>,<2,2>}，则R不具有A.自反性B.对称性C.传递性D.反对称性7.设f:R→R，f(x)=|x|，则fA.是单射B.是满射C.是双射D.既不是单射也不是满射8.设|A|=2，|B|=5，则A到B的单射共有A.10个B.20个C.25个D.5个9.偏序集中若存在两个不可比的元素，则该偏序关系一定不是A.全序关系B.偏序关系C.良序关系D.等价关系10.对称差A⊕B等于A.(A−B)∪(B−A)B.A∪BC.A∩BD.A−B11.定义x∗y=x+y+1，则该运算的幺元是A.1B.0C.−1D.212.循环群中元素a的阶为5，则a³的阶为A.5B.3C.2D.113.下列集合关于普通加法和乘法构成域的是A.整数集ZB.有理数集QC.偶数集2ZD.自然数集N14.无向图有9条边，则所有顶点度数之和为A.9B.18C.36D.4.515.完全图K₆的边数为A.15B.6C.30D.12▎二、填空题（本大题共10小题，每小题2分，共20分）16.蕴含等值式P→Q⇔____。17.任意两个不同大项的析取为____式。18.设B(x)：x是鸟，F(x)：x会飞。“有的鸟不会飞”符号化为____。19.若幂集P(A)含有16个元素，则|A|=____。20.设R={<1,2>,<3,2>,<3,1>}，则domR=____，ranR=____。21.设A={1}，B={1,2}，则A×B=____。22.在群中，(a⁻¹)⁻¹=____。23.连通平面图n=6、m=12，则面数r=____。24.若完全图K_n有15条边，则n=____。25.完全二叉树有3个度为2的顶点，则叶子数n₀=____。▎三、简答题（本大题共7小题，每小题5分，共35分）26.求命题公式P→(Q∧R)的主析取范式。27.用真值表判断(P→Q)↔(┐Q→┐P)的类型。28.设集合{a,b,c}的幂集P({a,b,c})上的包含关系为偏序关系，B={{a,b},{a,c},{b,c}}。画出哈斯图，求B的极大元与极小元。29.设A={1,2,3}，R={<1,2>,<2,3>,<3,1>,<1,3>}。求r(R)、s(R)、t(R)。30.某班共50人，爱好数学的有30人，爱好语文的有25人，两科都爱好的有15人。求两科中至少爱好一科的人数，以及两科都不爱好的人数。31.某连通带权图如图所示，用Kruskal算法求最小生成树，写出选边过程并求权。32.给定算术表达式(a+b)/(c−d∗e)，画出二叉树，并写出三种遍历序列。▎四、证明题（本大题共3小题，每小题5分，共15分）33.证明：完全二部图K_{3,3}不是平面图。34.证明：在任何群中，幂等元（满足a∗a=a的元素）只有幺元e。35.用自然推理系统证明：前提P∨Q，P→R，Q→R，结论R。密押试卷（第6套）（满分100分，考试时间150分钟）▎一、单项选择题（本大题共15小题，每小题2分，共30分）1.设P：小王去，Q：小李去。“并非小王和小李都去”符号化为A.┐P∧┐QB.┐(P∧Q)C.┐P∨QD.P∧┐Q2.命题公式P→(P∨Q)的类型是A.重言式（永真式）B.矛盾式（永假式）C.可满足式（非重言）D.无法判定3.含2个变元的公式，其主合取范式为M0∧M1，则该公式A.是重言式B.是矛盾式C.是可满足式D.无法判断4.论域为{2,4,6}，公式∃x(x>5)的真值为A.真（1）B.假（0）C.可真可假D.无法确定5.设M(x)：x是人，B(x)：x呼吸。“并非有的人不呼吸”符号化为A.┐∃x(M(x)∧┐B(x))B.∃x(M(x)∧┐B(x))C.∀x(M(x)∧B(x))D.┐∀x(M(x)→B(x))6.设X={1,2,3}，R={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}，则R的等价类个数是A.1B.2C.3D.57.设f:{1,2,3}→{a,b}，f={<1,a>,<2,b>,<3,a>}，则fA.是单射B.是满射C.是双射D.不是函数8.设|A|=3，|B|=4，则A到B的单射共有A.12个B.24个C.64个D.4个9.偏序集中每个非空子集都有最小元，称该偏序为A.全序B.良序C.等价关系D.格10.集合差A−B等于A.A∩~BB.A∪BC.~A∩BD.A∪~B11.定义x∗y=(x+y)/2，则该运算A.满足结合律B.不满足结合律，但满足交换律和幂等律C.不满足交换律D.必有零元12.循环群中元素a的阶为9，则a⁶的阶为A.3B.6C.9D.213.模4剩余类集合Z₄关于模4加法和乘法（2·2=0）构成A.域B.整环C.含有零因子的环D.乘法群14.n个顶点的简单图，其顶点的最大度数不超过A.nB.n−1C.n+1D.2n15.一棵树有m条边，则其顶点数为A.mB.m+1C.m−1D.2m▎二、填空题（本大题共10小题，每小题2分，共20分）16.德摩根律：┐(P∧Q)⇔____。17.两个不同小项m_i、m_j（i≠j）的合取为____。18.设P(x)：x是素数，G(x)：x大于1。“所有素数都大于1”符号化为____。19.若幂集P(A)含有8个元素，则|A|=____。20.设R={<a,b>,<a,c>,<b,a>}，则值域ranR=____。21.设|A|=4，|B|=5，则|A×B|=____。22.在群中，方程a∗x∗a=b的唯一解x=____。23.连通平面图r=4、m=8，则顶点数n=____。24.若完全图K_n有10条边，则n=____。25.完全二叉树有6个叶子，则度为2的顶点有____个。▎三、简答题（本大题共7小题，每小题5分，共35分）26.求命题公式(P∧Q)∨(┐P∧R)的主合取范式。27.用真值表判断(P∨(P∧Q))↔P的类型。28.设A={1,2,3,4,6,8,12,24}上整除关系为偏序关系，B={2,3,4,8}。画出哈斯图，求B的极大元与极小元。29.设X={a,b,c}，R={<a,b>,<b,c>,<c,a>,<a,a>}。求r(R)、s(R)、t(R)。30.设A={1,2,4,8}，B={2,4,6,8}。求A∪B、A∩B、A−B、B−A及A⊕B。31.某连通带权图如图所示，用Kruskal算法求最小生成树，写出选边过程并求权。32.给定算术表达式a+(b−c)∗d/e，画出二叉树，并写出三种遍历序列。▎四、证明题（本大题共3小题，每小题5分，共15分）33.证明：边数m<30的简单平面图中，必有一个顶点的度数小于5。34.证明：在群中，方程a∗x=b有唯一解，并写出该解。35.用CP规则证明：前提P→Q，Q→R，结论P→R。第二部分参考答案及评分参考（共6套）第1套参考答案及评分参考▎一、单项选择题（每小题2分，共30分）1.B2.B3.C4.A5.B6.B7.D8.B9.A10.B11.A12.B13.C14.B15.B▎二、填空题（每小题2分，共20分）16.重言（永真）17.矛盾（永假，恒为0）18.∀x(E(x)→D(x))19.3220.domR={1,2}；ranR={2,3}21.{<a,a>,<a,b>,<b,a>,<b,b>}22.b⁻¹∗a⁻¹23.欧拉通路24.625.n₀−1▎三、简答题（每小题5分，共35分）26.主析取范式：m7∨m5∨m3∨m1∨m0=(P∧Q∧R)∨(P∧┐Q∧R)∨(┐P∧Q∧R)∨(┐P∧┐Q∧R)∨(┐P∧┐Q∧┐R)。27.由真值表，公式在全部指派下均取1，故(P∧Q)→(P∨Q)是重言式（永真式）。28.哈斯图如下图。B={2,3,4,6}：B内2|4、2|6、3|6。极大元为{4,6}；极小元为{2,3}。29.r(R)={<1,1>,<1,2>,<2,2>,<2,3>,<3,1>,<3,3>}；s(R)={<1,1>,<1,2>,<1,3>,<2,1>,<2,3>,<3,1>,<3,2>}；t(R)={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}。30.A∪B={1,2,3,4,5,6,8}；A∩B={2,4}；A−B={1,3,5}；B−A={6,8}；A⊕B={1,3,5,6,8}。31.按权升序依次加入不构成圈的边：e-f(1)、a-b(2)、d-e(2)、a-f(3)、b-c(3)，共5条边（n−1）。最小生成树的权=1+2+2+3+3=11。32.二叉树如下图。先序（前缀）：*+ab-cd；中序：a+b*c-d；后序（后缀）：ab+cd-*。▎四、证明题（每小题5分，共15分）33.设面数为r。简单平面图每个面的次数不小于3，而各面次数之和等于2m，故3r≤2m，即r≤2m/3。由欧拉公式n−m+r=2得r=2−n+m。代入上式：2−n+m≤2m/3，两边乘3整理：6−3n+3m≤2m，即m≤3n−6。证毕。34.①自反性：对任意x∈X，f(x)=f(x)，故xRx；②对称性：若xRy，则f(x)=f(y)，从而f(y)=f(x)，故yRx；③传递性：若xRy、yRz，则f(x)=f(y)、f(y)=f(z)，由等号传递f(x)=f(z)，故xRz。R同时满足自反、对称、传递性，故为等价关系。35.(1)R（P规则）(2)R→┐Q（P规则）(3)┐QT(1)(2)假言推理(4)P→Q（P规则）(5)┐PT(3)(4)拒取式，证毕。第2套参考答案及评分参考▎一、单项选择题（每小题2分，共30分）1.B2.B3.A4.B5.A6.B7.A8.B9.B10.A11.A12.C13.B14.C15.A▎二、填空题（每小题2分，共20分）16.矛盾（永假）17.M_i18.∃x(I(x)∧N(x))19.{∅,{1},{2},{1,2}}20.{<b,a>,<c,b>,<c,a>}21.822.223.有向欧拉回路24.525.6▎三、简答题（每小题5分，共35分）26.主合取范式：M6∧M5∧M4∧M2∧M0=(┐P∨┐Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨Q∨R)∧(P∨┐Q∨R)∧(P∨Q∨R)。27.由真值表，公式在全部指派下均取1，故该式是重言式（即假言三段论）。28.哈斯图为一条链（1—2—4—8）。B={1,2,4}：极大元为{4}，极小元为{1}。29.r(R)={<a,a>,<a,b>,<b,a>,<b,b>,<b,c>,<c,b>,<c,c>}；s(R)={<a,b>,<b,a>,<b,c>,<c,b>}；t(R)={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>,<c,a>,<c,b>,<c,c>}。30.A∪B={2,3,4,6,8,9,10}；A∩B={6}；A−B={2,4,8,10}；B−A={3,9}；A⊕B={2,3,4,8,9,10}。31.选边：d-e(1)、b-c(2)、e-f(2)、a-b(3)、b-e(4)。最小生成树权=1+2+2+3+4=12。32.二叉树如下图。先序：/a+b*cd；中序：a/b+c*d；后序：abcd*+/。▎四、证明题（每小题5分，共15分）33.K₅有n=5个顶点、m=10条边。若K₅是平面图，则应满足m≤3n−6=3×5−6=9。但m=10>9，与上式矛盾，故K₅不是平面图。34.①自反性：n|(x−x)=0，故xRx；②对称性：若xRy，则n|(x−y)，从而n|(y−x)，故yRx；③传递性：若xRy、yRz，则n|(x−y)、n|(y−z)，于是n|[(x−y)+(y−z)]=x−z，故xRz。故R是等价关系。35.(1)S附加前提（CP）(2)S→P（P规则）(3)PT(1)(2)假言推理(4)P→(Q→R)（P规则）(5)Q→RT(3)(4)假言推理(6)Q（P规则）(7)RT(5)(6)假言推理(8)S→RCP规则，证毕。第3套参考答案及评分参考▎一、单项选择题（每小题2分，共30分）1.B2.A3.A4.A5.A6.C7.A8.B9.A10.A11.D12.A13.C14.B15.A▎二、填空题（每小题2分，共20分）16.017.018.∃x(E(x)∧P(x))19.1620.{<1,1>,<2,2>}21.422.b∗a⁻¹23.024.n−125.4▎三、简答题（每小题5分，共35分）26.主析取范式：m7∨m5∨m4∨m3∨m2∨m1∨m0=(P∧Q∧R)∨(P∧┐Q∧R)∨(P∧┐Q∧┐R)∨(┐P∧Q∧R)∨(┐P∧Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧┐Q∧┐R)。27.由真值表，公式在全部指派下均取1，故P→(Q→P)是重言式。28.哈斯图如下图。B={2,3,9}：B内3|9。极大元为{2,9}，极小元为{2,3}。29.r(R)={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}；s(R)={<1,1>,<1,2>,<2,1>,<3,3>}；t(R)={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}。30.A∪B∪C={1,2,3,4,5}；A∩B∩C={3}；A⊕B={1,4}，故(A⊕B)⊕C={1,3,5}。31.选边：d-e(2)、a-c(3)、e-f(3)、a-b(4)、b-f(4)。最小生成树权=2+3+3+4+4=16。32.二叉树如下图。先序：+*-abc/de；中序：a-b*c+d/e；后序：ab-c*de/+。▎四、证明题（每小题5分，共15分）33.每个面次数不小于4，各面次数之和为2m，故4r≤2m，即r≤m/2。由欧拉公式r=2−n+m，代入：2−n+m≤m/2，两边乘2整理：4−2n+2m≤m，即m≤2n−4。证毕。34.①封闭性：两个正有理数之积仍为正有理数；②结合律：普通乘法满足结合律；③幺元：1是正有理数，且1·a=a·1=a；④逆元：对任意正有理数a，1/a也是正有理数，且a·(1/a)=1；⑤交换律：普通乘法可交换。故Q⁺关于乘法构成交换群。35.(1)P归谬假设（否定结论）(2)P→┐Q（P规则）(3)┐QT(1)(2)假言推理(4)Q∨┐R（P规则）(5)┐RT(3)(4)析取三段论(6)R∧S（P规则）(7)RT(6)化简(8)R与┐R矛盾，故假设不成立，┐P成立。证毕。第4套参考答案及评分参考▎一、单项选择题（每小题2分，共30分）1.A2.B3.C4.A5.B6.B7.C8.B9.A10.A11.C12.B13.A14.D15.A▎二、填空题（每小题2分，共20分）16.1（真）17.018.∀x(I(x)→Q(x))19.6420.{<b,a>,<c,b>,<a,c>}21.922.a23.224.825.9▎三、简答题（每小题5分，共35分）26.主合取范式：M6∧M4∧M0=(┐P∨┐Q∨R)∧(┐P∨Q∨R)∧(P∨Q∨R)。27.由真值表，当P=Q=0时公式取0，其余指派取1，故(P↔Q)→(P∨Q)是可满足式（非重言）。28.哈斯图如下图。B={2,4,5,10}：B内2|4、2|10、5|10。极大元为{4,10}，极小元为{2,5}。29.r(R)={<a,a>,<a,c>,<b,a>,<b,b>,<c,c>}；s(R)={<a,a>,<a,b>,<a,c>,<b,a>,<c,a>,<c,c>}；t(R)={<a,a>,<a,c>,<b,a>,<b,c>,<c,c>}。30.A∪B={1,2,3,4,5,6,7,12}；A∩B={2,3}；A−B={5,7}；B−A={1,4,6,12}；A⊕B={1,4,5,6,7,12}。31.选边：a-b(1)、c-d(2)、b-c(3)、e-f(3)、b-e(4)。最小生成树权=1+2+3+3+4=13。32.二叉树如下图。先序：-+*ab/cde；中序：a*b+c/d-e；后序：ab*cd/+e-。▎四、证明题（每小题5分，共15分）33.反证。设每个顶点的度数都不小于6，则Σdeg(v)≥6n。由握手定理Σdeg(v)=2m，故2m≥6n，即m≥3n。但平面图满足m≤3n−6，与m≥3n矛盾。故至少存在一个度数不超过5的顶点。34.①封闭性：x+y+1仍为实数；②结合律：(x∗y)∗z=(x+y+1)+z+1=x+y+z+2，x∗(y∗z)=x+(y+z+1)+1=x+y+z+2；③幺元：e∗x=e+x+1=x，得e=−1；④逆元：x∗y=−1，即x+y+1=−1，得y=−x−2∈R；故(R,∗)构成群；又x∗y=x+y+1=y∗x，故为交换群。35.(1)┐R（P规则）(2)Q→R（P规则）(3)┐QT(1)(2)拒取式(4)P→Q（P规则）(5)┐PT(3)(4)拒取式，证毕。第5套参考答案及评分参考▎一、单项选择题（每小题2分，共30分）1.A2.A3.C4.A5.B6.D7.D8.B9.A10.A11.C12.A13.B14.B15.A▎二、填空题（每小题2分，共20分）16.┐P∨Q17.重言（永真，恒为1）18.∃x(B(x)∧┐F(x))19.420.domR={1,3}；ranR={1,2}21.{<1,1>,<1,2>}22.a23.824.625.4▎三、简答题（每小题5分，共35分）26.主析取范式：m7∨m3∨m2∨m1∨m0=(P∧Q∧R)∨(┐P∧Q∧R)∨(┐P∧Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧┐Q∧┐R)。27.由真值表，公式在全部指派下均取1，故(P→Q)↔(┐Q→┐P)是重言式（逆否命题等值）。28.哈斯图如下图。B中三个二元子集两两互不包含，故极大元=极小元={{a,b},{a,c},{b