2023年自学考试离散数学试题汇编

全国2023年4月高等教育自学考试离散数学试题课程代码：02324一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目规定的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．下列命题公式为重言式的是（）A．p→(p∨q)B．(p∨┐p)→qC．q∧┐q D．p→┐q2．下列语句中不是命题的只有（）A．这个语句是假的。B．1+1=1.0C．飞碟来自地球外的星球。D．凡石头都可练成金。3．设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化对的的是A．┐p∧qB．┐p→qC．┐p→┐q D．p→┐q4．下列等价式对的的是（）A．┐┐AB．C．┐┐AD．5．在公式中变元y是（）A．自由变元B．约束变元C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元6．设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S是（）A．自反关系 B．反自反关系C．对称关系 D．传递关系7．设集合X为人的全体，在X上定义关系R、S为R={<a，b|a，b∈X∧a是b的父亲}，S={<a，b>|a，b∈X∧a是b的母亲}，那么关系{<a，b>|a，b∈x∧a是b的祖母}的表达式为（）A．RS B．R-1SC．SR D．RS-18．设A是正整数集，R={(x，y)|x，y∈A∧x+3y=12}，则R∩({2，3，4，6}×{2，3，4，6})=（）A． B．{<3，3>}C．{<3，3>，<6，2>} D．{<3，3>，<6，2>，<9，1>}9．下列式子不对的的是（）A．(A-B)-C=(A-C)-B B．(A-B)-C=A-(B∪C)C．(A-B)-C=(A-C)-(B-C) D．A-(B∪C)=(A-B)∪C10．下列命题对的的是（）A．{l，2}{{1，2}，{l，2，3}，1} B．{1，2}{1，{l，2}，{l，2，3}，2}C．{1，2}{{1}，{2}，{1，2}} D．{1，2}∈{1，2，{2}，{l，2，3}}11．在下列代数系统中，不是环的只有（）A．<Z，+，*)，其中Z为整数集，+，*分别为整数加法和乘法。B．(Q，+，*)，其中Q为有理数集，+，*分别为有理数加法和乘法。C．<R，+，*>，其中R为实数集，+为实数加法，a*b=a+2b。D．<Mn(R)，+，*>，其中Mn(R)为实数集n×n阶矩阵结合，+，*是矩阵加法和乘法。12．下列整数集对于整除关系都构成偏序集，而能构成格的是（）A．{l，2，3，4，5} B．{1，2，3，6，12}C．{2，3，7} D．{l，2，3，7}13．结点数为奇数且所有结点的度数也为奇数的连通图必然是（）A．欧拉图 B．汉密尔顿图C．非平面图 D．不存在的14．无向图G是欧拉图当且仅当G是连通的且（）A．G中各顶点的度数均相等B．G中各顶点的度数之和为偶数C．G中各顶点的度数均为偶数D．G中各顶点的度数均为奇数15．平面图(如下)的三个面的次数分别是（）A．11，3，4 B．11，3，5C．12，3，6 D．10，4，3二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上对的答案。错填、不填均无分。16．求一个公式的主析取或主合取范式的方法，有______________法和______________法。17．给定谓词合式公式A，其中一部分公式形式为()B(x)或(x)B(x)，则量词，后面所跟的x称为______________，而称B为相应量词的______________。18．设X，U，V，Y都是实数集，f1：X→U，且fl(x)→ex；f2：U→V，且f2(u)＝u(1+u)；f3：V→Y，且f3(v)=cosv。那么f3f2f1的定义域是______________，而复合函数(f3f2f1)(x)=______________。19．集合X={a，b，c，d}上二元关系R={<a，b>，<a，c>，<a，d>，<b，c>，<b，d>，<e，d>}，则R的自反闭包r(R)=______________，对称闭包s(R)=______________。20．已知G=<{l，-1，i，-i}，·>(其中i=，是数的乘法)是群，则-l的阶是______________；i的阶是______________。21．对代数系统<S，*>，其中*是S上的二元运算，若a，b∈S，且对任意的x∈S，都有a*x=x*a=x，b*x=x*b=b，则称a为运算“*”的______________，称b为运算“*”的______________。22．设<S，*>是群，则<S，*>满足结合律和______________；若｜S｜>l，S中不也许有______________。23．写出如右有向图的一条初级回路：______________，其长度是______________。24．一个______________且______________的无向图称为树。25．在简朴无向图G=<V，E>中，假如V中的每个结点都与其余的所有结点邻接，则该图称为______________，假如V有n个结点，那么它还是______________度正则图。三、计算题(本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共30分)26．若集合A={a，{b，c}}的幂集为P(A)，集合B={，{}}的幂集为P(B)，求P(A)∩P(B)。27．构造命题公式(p→(q∧r))→┐p的真值表。28．求图G＝<V，E>的可达矩阵，其中V＝｛v1,v2,v3,v4｝ E＝｛(v1,v2),(v2,v3),(v2,v4),(v3,v2),(v3,v4),(v3,v1),(v4,v1)｝29．求下列公式的主析取范式和主合取范式：（P∧Q）∨（┐P∧R）30．设A＝｛2，3，4，6，8，12，24｝，R为A上整除关系，试画<A，R>的哈斯图，并求A中的最大元，最小元，极大元，极小元。四、证明题（本大题共3小题，第31、32小题各6分，第33题8分，共20分）31．设M是偶数集，＋和·是数的加、乘运算，证明<M，＋，·>是一个环。32．设R是集合X上的二元关系，证明R是X上传递关系当且仅当RRR。33．设G是简朴平面图，G有n个顶点m条边，且m<30，证明G中存在一项点v，d（v）≤4。五、应用题（本大题共2小题，第34题6分，第35题9分，共15分）34．判断下面推理是否对的，并证明你的结论。 假如小王今天家里有事，则他不会来开会。假如小张今天看到小王，则小王今天来开会了。小张今天看到小王。所以小王今天家里没事。35．有6个村庄Vi，i=l，2，…，6欲修建道路使村村可通。现已有修建方案如下带权无向图所示，其中边表达道路，边上的数字表达修建该道路所需费用，问应选择修建哪些道路可使得任二个村庄之间是可通的且总的修建费用最低?规定写出求解过程，画出符合规定的最低费用的道路网络图并计算其费用。2023年7月全国自考离散数学试题试卷真题课程代码：02324一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目规定的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．下列语句中不是命题的只有（）A．鸡毛也能飞上天？ B．或重于泰山，或轻于鸿毛。C．不经一事，不长一智。 D．牙好，胃口就好。2．从真值角度看，命题公式的所有类型是（）A．永真式 B．永假式C．永真式，永假式 D．永真式，永假式，可满足式3．设M（x）：x是人；F（x）：x要吃饭。用谓词公式表达下述命题：所有的人都要吃饭，其中错误的表达式是（）A． B．C． D．4．下列公式是前束范式的是（）A． B．C． D．5．设论域为整数集，下列真值为真的公式是（）A． B．C． D．6．下列是谓词演算中的合式公式的是（）A． B．C． D．（）．（）（）A．B．C．D．．（）8．下列式子对的的是（）A．（A－B）-C=A-（B∪C） B．A－（B∪C）=（A－B）∪CC．~（A－B）=~（B－A） D．~（A∩B）A9．下列集合对所给的运算是封闭的只有（）A．非零整数集合Z*上的除法运算B．全体n×n实可逆矩阵集合Mn（R）上的矩阵加法和乘法运算C．全体n×n实矩阵集合Mn（R）上的矩阵加法和乘法运算D．A={1，2，…，10}，x*y=LCM（x，y），即x，y最小公倍数10．设<A，eq\o\ac(○,+)，*>是环，则下列说法不对的的是（）A．<A，eq\o\ac(○,+)>是互换群 B．<A，*>是半群C．*对eq\o\ac(○,+)是可分派的 D．eq\o\ac(○,+)对*是可分派的11．下列四个格，是分派格的是（）C．D．．（）A．B．12．下列各图是无向完全图的是（）13．下列各有向图是强连通图的是（）14．设Ｇ是具有n个结点的无向简朴图，若在Ｇ中存在一条汉密尔顿路，则Ｇ中每一对结点的度数之和与n-1的关系为（）A．大于 B．大于等于C．等于 D．小于15．设连通平面图Ｇ，共有n个结点，e条边，r个面，则欧拉证明成立的公式是（）A．e-n+r=2 B．n+r-e=2C．n-r+e=2 D．n-e-r=2二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上对的答案。错填、不填均无分。16．所谓____是指不能再分解的命题，而复合命题是由一些____通过联结词复合而成的命题。17．在命题演算中，两个____的合取、析取、条件、双条件均为____。18．使公式成立的条件是____中不含y，____中不含x。19．设A={1，2，3，4}，R是A上的二元关系，R={<x,y>|x/y是素数}，则domR=_____;ranR=____。20．设无向图Ｇ有n个结点m条边，每个结点的度数为k或k+1，记Nk为度数等于k的结点数，则Nk=_____。假如无向简朴图C的结点的度数均为相同的偶数，且m=7，则n=____。21．设X={1，3，5，9，15，45}，R是X上的整除关系，则R是X上的偏序，其最大元是___，极小元是____。22．设<>是有界格，a,bL,若ab=0,则a=b=_____；若ab=1,则a=b=____。23．设e是群G上的幺元，若aG且a2=e,则a-1=____,a-2=__________。24．代数系统<A,。>，其中A为命题公式集合，。为析取运算，则<A，。>中零元素是____，幺元是____。25．树是不包含_____的___图。三、计算题（本大题共6小题，第26、27题各4分，第28、29题各5分，第30、31题各6分，共30分）26．假如论域是集合{a,b,c}，试消去下面公式中的量词：27．求公式（的主析取范式。28．设A={a,b,c},A上二元关系R={<a,a>,<a,c>,<b,a>},用关系矩阵法求最小的自然数m,n,m<n使Rm=Rn。29．根据下列条件假如能画则请画出一个欧拉图，假如不能画则请说明理由。（1）偶数个顶点，偶数条边（2）奇数个顶点，奇数条边（3）偶数个顶点，奇数条边（4）奇数个顶点，偶数条边30．下列各整数集合对于整除关系“|”都构成偏序集，判断哪些偏序集能构成格？并说明理由。1)L={1,2,3,4,5}2)L={1,2,3,6,12}3)L={1,2,3,4,6,9,12,18,36}4)L={1,2,22,23,…,2n}31．设A={2，3，5，12，19}，等价关系R={<x,y>|x,(mod3)},写出各元素的等价类，并求A/R。四、证明题（本大题共3小题，第32、33题各6分，第34题8分，共20分）32．用等价变换法证明：是永真式。33．若无向图G是欧拉图，G中是否存在割边？为什么？34．设A是一个集合，X=P（A），R是X上元素之间的包含关系，试证明<X,R>是偏序集。（注：P（A）为A的幂集）五、应用题（本大题共2小题，第35题6分，第36题9分，共15分）35．设有n个村庄要修路，（1）若要使所有村庄之间都有通路，问需在两村之间至少修几条路？（2）若要使任意两村庄之间有一条直接的路，则至少修几个路？（3）若修一条连接所有村庄的环路，问有多少种修路方案？36．设有推理：(a)没有不守信用的人是可信赖的；(b)有些可以信赖的人是受过教育的人；(c)因此有些受过教育的人是守信用的。试构造推理的证明，规定把推理的前提，结论符号化为谓词形式，并写出推理过程。（个体域：人的集合）提醒：设F（x）表达x是守信用的人；G（x）表达x是可信赖的人；H（x）表达x是受过教育的人。全国2023年4月高等教育自学考试离散数学试题课程代码：02324一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目规定的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．下列命题公式中不是重言式的是（）A．p→(q→r) B．p→(q→p)C．p→(p→p) D．(p→(q→r))(q→(p→r))2．下列语句中为命题的是（）A．这朵花是谁的？ B．这朵花真美丽啊！C．这朵花是你的吗？ D．这朵花是他的。3．设个体域是整数集，则下列命题的真值为真的是（）A．yx(x·y=1) B．xy(x·y≠0)C．xy(x·y=y2) D．yx(x·y=x2)4．关于谓词公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中错误的是（）A．（x）的辖域是（y）（P（x,y）∧Q(y,z)）B．z是该谓词公式的约束变元C．（x）的辖域是P（x,y） D．x是该谓词公式的约束变元5．设论域D={a,b}，与公式xA（x）等价的命题公式是（）A．A（a）∧A（b） B．A（a）→A（b）C．A（a）∨A（b） D．A（b）→A（a）6．集合A={1，2，3}上的下列关系矩阵中符合等价关系条件的是（）A． B．C． D．7．设A={Ø}，B=P（P（A）），以下不对的的式子是（）A．{{Ø}，{{Ø}}，{Ø，{Ø}}}包含于B B．{{{Ø}}}包含于BC．{{Ø，{Ø}}}涉及于B D．{{Ø}，{{Ø，{Ø}}}}包含于B8．设Z是整数集，E={…，-4，-2，0，2，4，…}，f：Z→E，f（x）=2x，则f（）A．仅是满射 B．仅是入射C．是双射 D．无逆函数9．设A={1，2，3，4，5}，A上二元关系R={〈1，2〉，〈3，4〉，〈2，2〉}，S={〈2，4〉，〈3，1〉，〈4，2〉}，则S-1R-1的运算结果是（）A．{〈4，1〉，〈2，3〉，〈4，2〉} B．{〈2，4〉，〈2，3〉，〈4，2〉}C．{〈4，1〉，〈2，3〉，〈2，4〉} D．{〈2，2〉，〈3，1〉，〈4，4〉}10．设有代数系统G=〈A，*〉，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的幺元是（）A．矛盾式 B．重言式C．可满足式 D．公式p∧q11．在实数集合R上，下列定义的运算中不可结合的是（）A．a*b=a+b+2ab B．a*b=a+bC．a*b=a+b+ab D．a*b=a-b12．下列集合关于所给定的运算成为群的是（）A．已给实数a的正整数次幂的全体，且a{0，1，-1}，关于数的乘法B．所有非负整数的集合，关于数的加法C．所有正有理数的集合，关于数的乘法D．实数集，关于数的除法13．设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（）A．3 B．4C．5 D．614．下列各图中既是欧拉图，又是汉密尔顿图的是（）A．B．C．D．15．设无向图G的边数为m，结点数为n，则G是树等价于（）A．G连通且m=n+1 B．G连通且n=m+1C．G连通且m=2n D．每对结点之间至少有一条通路二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上对的答案。错填、不填均无分。16．不能再分解的命题称为____________，至少包含一个联结词的命题称为____________。17．在命题演算中，五个联结词的含义是由其____________表唯一拟定的，而不是由其类似的____________语言的含义拟定。18．使公式（x）（y）（A（x）→B（y））（（x）A（x）→（y）B（y））成立的条件是____________不具有y，____________不具有x。19．设A为任意集合，请填入适当的运算符，使式子A____________A=Ø；A____________~A=Ø成立。20．设A={0，1，2，3，6}，R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod3)}，则domR=____________，ranR=____________。21．称集合S是给定非空集合A的覆盖：若S={S1，S2，…，Sn}，其中SiA，Si≠Ø，i=1，2，…，n，且____________；进一步若____________，则S是集合A的划分。22．对实数的普通加法和乘法，____________是加法的幂等元，____________是乘法的幂等元。23．在代数系统〈A，*〉中，A={a}，*是A上二元运算，则该代数系统的单位元是____________，零元是____________。24．设〈A，≤〉是偏序集，若A中____________都有最小上界和____________则称A关于偏序≤构成格。25．若一条路中，所有边均不相同，则此路称作____________；若一条路中所有的结点均不相同，则称此路为____________。三、计算题（本大题共6小题，第26、27小题各4分，第28、29小题各5分，第30、31小题各6分，共30分）36．试画出结点数为3的（1）强连通图；（2）单向连通图；（3）弱连通图；（4）非连通图。27．设A={0，1，2，3}，R={〈x,y〉|x,y∈A∧(y=x+1∨y=)}，S={〈x,y〉|x,y∈A∧（x=y+2）}。试求RSR28．在全体正整数集合Z+中规定∩，∪为：对任意的a,b∈Z+， a∪b=[a,b]，即求a,b的最小公倍数； a∩b=(a,b)，即求a,b的最大公约数； 则运算∩，∪满足结合律，互换律和吸取律，于是〈Z+，∩，∪〉是一个格。判断下列集合是否是<Z+，∩，∪>的子格？ 1）A={1，2，3，9，12，72} 2）A={1，2，3，12，18} 3）A={5，52，53，…，5n} 4）T=2Z+={2k|k∈Z+}29．求命题公式（p→q）→（q∨p）的主析取范式。30．结出命题公式（p∨(p∧q)）∧((p∨q)∧q)的二叉树表达。31．设A={a,b,c,d},R={〈a,c〉，〈c,b〉，〈b,a〉，〈a,d〉}，求R，r(R),s(R),t(R)的关系图。四、证明题（本大题共3小题，第32、33小题各6分，第34小题8分，共20分）32．设A是非空集合，P（A）是A的幂集，是集合的包含关系，则〈P（A），〉是格，证明：〈P（A），〉是有补格。33．设〈{a,b},*〉是半群，其中a*a=b，证明：（1）a*b=b*a；（2）b*b=b。34．若一棵树恰有2个结点的度数为1，则它必是一条欧拉路。五、应用题（本大题共2小题，第35小题6分，第36小题9分，共15分）35．设I是整数集，<，>，＝，≤，≥，≠是Ｉ上的二元关系，分别表达小于，大于、等于、小于等于，大于等于，不等于，那么这些关系会满足什么性质？试填写下表自反反自反对称反对称传递<>=≤≥≠≤∩≥≤∪≥36．设R=，Z是整数集，则： （1）R对矩阵的加法和乘法构成一个环； （2）R中存在元素x是右零因子但不是左零因子。全国2023年7月高等教育自学考试离散数学试题课程代码：02324一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目规定的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）A．P→Q B．P∨QC．P∧Q D．P∧Q2．下列命题公式为重言式的是（）A．Q→（P∧Q） B．P→（P∧Q）C．（P∧Q）→P D．（P∨Q）→Q3．下列4个推理定律中，不对的的是（）A．A（A∧B） B．（A∨B）∧ABC．（A→B）∧AB D．（A→B）∧BA4．谓词公式x(P(x)∨yR(y))→Q(x)中量词的辖域是（）A． B．P（x）C．(P(x)∨yR(y)) D．P(x),Q(x)5．设个体域A={a,b}，公式xP(x)∧xS(x)在A中消去量词后应为（）A．P(x)∧S(x) B．P(a)∧P(b)∧(S(a)∨S(b))C．P(a)∧S(b) D．P(a)∧P(b)∧S(a)∨S(b)6．下列选项中错误的是（）A．ØØ B．Ø∈ØC．Ø{Ø} D．Ø∈{Ø}7．设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，则相应于R的A的划分是（）A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}8．设R为实数集，函数f：R→R，f(x)=2x，则f是（）A．满射函数 B．入射函数C．双射函数 D．非入射非满射9．设R为实数集，R+={x|x∈R∧x>0}，*是数的乘法运算，<R+，*>是一个群，则下列集合关于数的乘法运算构成该群的子群的是（）A．{R+中的有理数} B．{R+中的无理数}C．{R+中的自然数} D．{1，2，3}10．下列运算中关于整数集不能构成半群的是（）A．ab=max{a,b} B．ab=bC．ab=2ab D．ab=|a-b|11．设Z是整数集，+，分别是普通加法和乘法，则（Z，+，）是（）A．域 B．整环和域C．整环 D．含零因子环12．设A={a,b,c}，R是A上的二元关系，R={<a,a>,<a,b>,<a,c>,<c,a>}，那么R是（）A．反自反的 B．反对称的C．可传递的 D．不可传递的13．设D=<V,E>为有向图，V={a,b,c,d,e,f},E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}是（）A．强连通图 B．单向连通图C．弱连通图 D．不连通图14．在有n个结点的连通图中，其边数（）A．最多有n-1条 B．至少有n-1条C．最多有n条 D．至少有n条15．连通图G是一棵树，当且仅当G中（）A．有些边不是割边 B．每条边都是割边C．无割边集 D．每条边都不是割边二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上对的答案。错填、不填均无分。16．任意两个不同的小项的合取为________________式，全体小项的析取式必为________________式。17．公式x(P(x)→Q(x,y)∨zR(y,z))→S(x)中的自由变元为________________，约束变元为________________。18．设集合M={x|1≤x≤12,x被2整除，x∈Z},N={x|1≤x≤12,x被3整除，x∈Z}，则M∩N=________________，M∪N=________________。19．设X={1，2，3}，f：X→X，g：X→X，f={<1,2>,<2,3>,<3,1>}, g={<1,2>,<2,3>,<3,3>}，则fg=________________，gf=________________。20．设A={a,b,c}，R是A上的二元关系，且给定R={<a,b>,<b,c>,<c,a>}，则R的自反闭包r(R)=________________，对称闭包s(R)=________________。21．设Q为有理数集，笛卡尔集S=Q×Q，*是S上的二元运算，<a,b>,<x,y>∈S,<a,b>*<x,y>=<ax,y+b>,则*运算的幺元是________________。<a,b>∈S,若a≠0，则<a,b>的逆元是________________。22．设*是集合S上的二元运算，若运算*满足________________且存在________________，则称<S，*>为独异点。23．令A={a,b,c}，<A,*>是循环群，a是单位元，则b2=________________，c的阶是________________。24．如下无向图割点是________________，割边是________________。25．无向图G具有生成树，当且仅当________________。G的所有生成树中________________的生成树称为最小生成树。三、计算题（本大题共5小题，第26、27小题各5分，第28、29小题各6分，第30小题8分，共30分）26．集合A={a,b,c,d,e}上的二元关系R为 R={<a,a>,<a,b>,<a,c>,<a,d>,<a,e>,<b,b>,<b,c>,<b,e>, <c,c>,<c,d>,<c,e>,<d,d>,<d,e>,<e,e>} （1）写出R的关系矩阵； （2）判断R是不是偏序关系，为什么？27．运用真值表判断公式（（P∨Q）∧（Q→R））→（P∧R）是否为重言式。28．给定图G如下所示，（1）写出G的可达矩阵；（2）G中长度为4的路有几条？29．求下列公式的主析取范式和主合取范式：（P→Q）∧（Q→R）30．设A为54的因子构成的集合，RA×A，x,y∈A,xRyx整除y。画出偏序集<A,R>的哈斯图，并求A中的最大元，最小元，极大元，极小元。五、证明题（本大题共3小题，第31、32小题各6分，第33小题8分，共20分）31．设R是A上的一个自反关系，证明：R是一个等价关系，当且仅当若<a,b>∈R，<a,c>∈R，则<b,c>∈R。32．设<G，*>是一个群，x∈G，定义：ab=a*x*b，a,b∈G。证明：<G,>也是一个群。33．设图G是具有6个结点，12条边的无向简朴图，证明图G是汉密尔顿图。五、应用题（本大题共2小题，第34小题8分，第35小题7分，共15分）34．构造下面推理的证明。假如今天是星期六，我们就要到颐和园或圆明园去玩。假如颐和园游人太多，我们就不去颐和园玩。今天是星期六，颐和园游人太多，所以我们去圆明园玩。35．n个城市用k条公路的网络连结。一条公路定义为两个城市间的一条不穿过任何中间城市的道路。任意两个城市之间至多修一条公路。证明假如k>(n-1)(n-2)，则人们总能通过连结的公路，在任何两个城市间旅行。全国2023年4月自考离散数学试题课程代码：02324一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个备选项中只有一个是符合题目规定的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.设P：天下大雨,Q：他在室内运动,命题“除非天下大雨，否则他不在室内运动”可符合化为（）A.P∧Q B.P→QC.P→Q D.P→Q2.下列命题联结词集合中，是最小联结词组的是（）A.{，} B.{，∨，∧}C.{，∧} D.{∧，→}3.下列命题为假命题的是（）A.假如2是偶数，那么一个公式的析取范式惟一B.假如2是偶数，那么一个公式的析取范式不惟一 C.假如2是奇数，那么一个公式的析取范式惟一D.假如2是奇数，那么一个公式的析取范式不惟一4.谓词公式x(P(x)∨yR(y))→Q(x))中变元x是（）A.自由变元 B.约束变元C.既不是自由变元也不是约束变元 D.既是自由变元也是约束变元5.若个体域为整数减，下列公式中值为真的是（）A.xy(x+y=0) B.yx(x+y=0) C.xy(x+y=0) D.xy(x+y=0)6.下列命题中不对的的是（）A.x∈{x}-{{x}} B.{x}{x}-{{x}} C.A={x}∪x,则x∈A且xA D.A-B=A=B7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项对的的是（）A.PQ B.PQC.QP D.Q=P8.下列表达式中不成立的是（）A.A∪(BC)=(A∪B)(A∪C) B.A∩(BC)=(A∩B)(A∩C)C.(AB)×C=(A×C)(B×C) D.(A-B)×C=(A×C)-(B×C)9.半群、群及独异点的关系是（）A.{群}{独异点}{半群} B.{独异点}{半群}{群}C.{独异点}{群}{半群} D.{半群}{群}{独异点}10.下列集合对所给的二元运算封闭的是（）A.正整数集上的减法运算 B.在正实数的集R+上规定为ab=ab-a-b a,b∈R+C.正整数集Z+上的二元运算为xy=min(x,y) x,y∈Z+D.全体n×n实可逆矩阵集合Rn×n上的矩阵加法11.设集合A={1，2，3}，下列关系R中不是等价关系的是（）A.R={<1,1>,<2,2>,<3,3>}B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>} C.R={<1,1>,<2,2>,<3,3>,<1,2>} D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>} 12.下列函数中为双射的是（）A.f：Z→Z,f(j)=j(mod) B.f：N→N,f(j)=C.f：Z→N,f(j)=|2j|+1 D.f：R→R,f(r)=2r-1513.设集合A={a,b,c}上的关系如下，具有传递性的是（）A.R={<a,c>,<c,a>,<a,b>,<b,a>} B.R={<a,c>,<c,a>} C.R={<a,b>,<c,c>,<b,a>,<b,c>} D.R={<a,a>}14.具有5个结点，3条边的不同构的简朴图有（）A.2个 B.3个C.4个 D.5个15.设D的结点数大于1，D=<V,E>是强连通图，当且仅当（）A.D中至少有一条通路 B.D中至少有一条回路C.D中有通过每个结点至少一次的通路 D.D中有通过每个结点至少一次的回路二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上对的答案。错填、不填均无分。16.设A={1,2,3}，B={3,4,5}，则AA=___________，AB=___________。17.设A={1,2,3,4,5}，RA×A，R={<1,2>，<3,4>,<2,2>}，则R的自反闭包r(R)=__________。对称闭包t(R)=__________。18.设P、Q为两个命题，德摩根律可表达为_____________，吸取律可表达为____________。19.对于公式x(P(x)∨Q(x))，其中P(x)∶x=1,Q(x)∶x=2,当论域为{1,2}时，其真值为_____________,当论域为{0,1,2}时，其真值为_____________。20.设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数,。21.3个结点可构成_________个不同构的简朴无向图，可构成________个不同构的简朴有向图。22.无向图G=<V,E>如左所示，则G的最大度Δ(G)=_____________，G的最小度δ(G)=_____________。23.设图G<V,E>,V={v1,v2,v3,v4},若G的邻接矩阵，则deg-(v1)=_________,deg+(v4)=____________。24.格L是分派格，当且仅当L既不具有与_______同构的子格，也不具有与______同格的子格。25.给定集合A={1,2,3,4,5}，在集合A上定义两种关系：R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>,<1,3>}，则，。三、计算题（本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共30分）26.设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，画出R的关系图，并求出A中各元素的等价类。27.构造命题公式（P∨Q）（P∧Q）的真值表。28.求下列公式的主析取范式和主合取范式：P→（（Q→P）∧（P∧Q））29.设A={a,b,c,d,e}，R为A上的关系，R={<a,d>，<a,c>，<a,b>,<a,e>,<b,e>,<c,e>,<d,e>}∪IA，试画<A，R>的哈斯图，并求A中的最大元，最小元，极大元，极小元。30.给定图G如图所示，（1）G中长度为4的路有几条？其中有几条回路？（2）写出G的可达矩阵。四、证明题（本大题共3小题，第31、32题各6分，第33题8分，共20分）31.设（L，≤）是格，试证明：a,b,c∈L,有a∧（b∨c）≥（a∧b）∨（a∧c）；a∨（b∧c）≤（a∨b）∧（a∨c）。32.设R是A上的自反和传递关系，如下定义A上的关系T，使得x,y∈A，<x,y>∈T<x,y>∈R∧(y,x)∈R。证明T是A上的等价关系。33.设有G=<V,E>,V的结点数|V|=n，称该图为n阶图，若从结点vi到vj存在路，证明从vi到vj必存在长度小于等于n-1的一条路。五、应用题（本大题共2小题，第34题7分，第35题8分，共15分）34.构造下面推理的证明。每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。35.今要将6人提成3组（每组2个人）去完毕3项任务。已知每个人至少与其余5个人中的3个人能互相合作。（1）能否使得每组的2个人都能互相合作？（2）你能给出几种不同的分组方案？全国2023年7月自考试题离散数学课程代码：02324一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目规定的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化对的的是（）A．P∧Q B．P∧QC．P→Q D．P∨Q2．下面联结词运算不可互换的是（）A．∧ B．→C．∨ D．3．下列命题公式不是重言式的是（）A．Q→（P∨Q） B．（P∧Q）→PC．（P∧Q）∧（P∨Q） D．（P→Q）（P∨Q）4．下列等价式不对的的是（）A． B．C． D．5．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（）A． B．B（x））C． D．B(x))6．设M={x|f1(x)=0},N={x|f2(x)=0}，则方程f1(x)·f2(x)=0的解为（）A．M∩N B．M∪NC．MN D．M-N7．设A-B=，则有（）A．B= B．B≠C．AB D．AB8．A，B是集合，P（A），P（B）为其幂集，且A∩B=，则P(A)∩P(B)为（）A． B．{}C．{{}} D．{，{}}9．设集合A={1，2，3，……，10}，下列定义的运算关于集合A是不封闭的是（）A．x*y=max{x,y} B．x*y=min{x,y}C．x*y=GCD{x,y},即x,y的最大公约数 D．x*y=LCM{x,y},即x,y的最小公倍数10．设H，K是群（G，）的子群，下面代数系统是（G，）的子群的是（）A．（H∩K，） B．（H∪K，）C．（K-H，） D．（H-K，）11．设A={1，2，3，4，5}，B={6，7，8，9，10}，以下关系是从A到B的入射函数的是（）A．f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>}B．f={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>}C．f={<1,6>,<2,7>,<4,9>,<3,8>}D．f={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>}12．设简朴图G所有结点的度数之和为12，则G一定有（）A．3条边 B．4条边C．5条边 D．6条边13．下列不一定是树的是（）A．无回路的连通图 B．有n个结点，n-1条边的连通图C．每对结点之间都有通路的图 D．连通但删去一条边则不连通的图14．下面关于关系R的传递闭包t(R)的描述最确切的是（）A．t(R)是包含R的二元关系 B．t(R)是包含R的最小传递关系C．t(R)是包含R的一个传递关系 D．t(R)是任何包含R的传递关系15．欧拉回路是（）A．途径 B．迹C．既是初级回路也是迹 D．既非初级回路也非迹二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上对的答案。错填、不填均无分。16．设A={1，2}，B={2，3}，则AA=__________，AB=__________。17．设A={1，2，3，4}上关系R={<1,2>,<2,4>,<3,3>,<1,3>}，则R的自反闭包r(R)=_________，对称闭包S（R）=__________。18．命题公式（PQ）→P的成真指派为__________，成假指派为__________。19．公式（）（F（x）→G(y)）→()(H(x))中的自由变元为_________，约束变元为__________。20．设f:R→R,f(x)=x2-2,g:R→R,g(x)=x-1,那么复合函数=__________，=__________。21．有理数集Q中的*运算定义如下：a*b=a+b-ab，则*运算的单位元是__________，设a有逆元，则其逆元a-1=__________。22．设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},那么dom(A∪B)=_______,ran(A∩B)=__________。23．如下图的有补格中，c的补元是__________，b的补元是__________。24．在根树中，若每一个结点的出度__________m,则称这棵树为m叉树。假如每一个结点的出度__________m或0，则称这棵树为完全m叉树。25．<Zn,>是一个群，其中Zn={0,1,2,……,n-1},xy=(x+y)modn，则在<Z6,>中，1的阶是__________，4的阶是__________。三、计算题（本大题共5小题，第26、27小题各5分，第28、29小题各6分，第30小题8分，共30分）26．构造命题公式（）→PR的真值表。27．若集合A={1，{2，3}}的幂集为P（A），集合B={{，2}，{2}}的幂集为P（B），求P(A)∩P(B)。28．设X={1，2，3，4}，R是X上的二元关系，R={<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>}。（1）画出R的关系图；（2）写出R的关系矩阵；（3）说明R是否具有自反、反自反、对称、传递性质。29．求下列公式的主析取范式和主合取范式：（P→（QR））（P→（Q→R））。30．设A={a,b,c},P(A)是A的幂集，R为A上的包含关系，试给出<P(A),R>的哈斯图，并给出子集{{a,b},{a,c},{c}}的极大元、极小元、最大元、最小元。四、证明题（本大题共3小题，第31、32小题各6分，第33小题8分，共20分）31．设H是形如的2×2阶矩阵的集合，H中定义通常的矩阵乘法运算。验证H是群，=。32．设R为N×N上的二元关系，∈N×N，证明R为等价关系。33．简朴图G有n个结点，m条边，设m>(n-1)(n-2)，证明：G是连通的。五、应用题（本大题共2小题，第34小题7分，第35小题8分，共15分）34．构造下面推理的证明。只要A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。A曾到过受害者房间。假如在11点以前离开，看门人会看见他。看门人没有看见他。所以A犯了谋杀罪。35．在某次国际会议的预备会中，共有8人参与，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。全国2023年4月自学考试离散数学试题课程代码：02324一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目规定的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．下列为两个命题变元P，Q的小项是（）A．P∧Q∧P B．P∨QC．P∧Q D．P∨P∨Q2．下列语句中是真命题的是（）A．我正在说谎 B．严禁吸烟C．假如1+2=3，那么雪是黑的 D．假如1+2=5，那么雪是黑的3．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（）A．P∧Q B．P∨QC．（PQ） D．（P∨Q）4．命题公式（P∧（P→Q））→Q是（）A．矛盾式 B．蕴含式C．重言式 D．等价式5．命题公式（P∧Q）→R的成真指派是（）A．000，001，110， B．001，011，101，110，111C．全体指派 D．无6．在公式（）F（x，y）→（y）G（x，y）中变元x是（）A．自由变元 B．约束变元C．既是自由变元，又是约束变元 D．既不是自由变元，又不是约束变元7．集合A={1，2，…，10}上的关系R={<x，y>|x+y=10，x∈A，y∈A}，则R的性质是（）A．自反的 B．对称的C．传递的、对称的 D．反自反的、传递的8．若R和S是集合A上的两个关系，则下述结论对的的是（）A．若R和S是自反的，则R∩S是自反的B．若R和S是对称的，则RS是对称的C．若R和S是反对称的，则RS是反对称的D．若R和S是传递的，则R∪S是传递的9．R={<1，4>，<2，3>，<3，1>，<4，3>}，则下列不是t（R）中元素的是（）A．<1，1> B．<1，2>C．<1，3> D．<1，4>10．设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项对的的是（）A．1∈A B．{1，2，3}AC．{{4，5}}A D．∈A11．在自然数集N上，下列运算是可结合的是（）A．ab=a-2b B．ab=min{a，b}C．ab=-a-b D．ab=|a-b|12．在代数系统中，整环和域的关系是（）A．整环一定是域 B．域不一定是整环C．域一定是整环 D．域一定不是整环13．下列所示的哈斯图所相应的偏序集中能构成格的是（）A． B．C． D．14．设G为有n个结点的简朴图，则有（）A．Δ(G)＜n B．Δ(G)≤nC．Δ(G)＞n D．Δ(G)≥n15．具有4个结点的非同构的无向树的数目是（）A．2 B．3C．4 D．5二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上对的答案。错填、不填均无分。16．（x）（y）（P（x，y）Q（y，z））∧xP（x，y）中x的辖域为________，x的辖域为________。17．两个重言式的析取是________式，一个重言式与一个矛盾式的析取是________式。18．设N是自然数集合，f和g是N到N的函数，且f（n）=2n+1，g（n）=n2，那么复合函数（ff）（n）=________（gf）（n）=________。19．设复合函数gf是从A到C的函数，假如gf是满射，那么________必是满射，假如gf是入射，那么________必是入射。20．设A={1，2}，B={2，3}，则A-A=________，A-B=________。21．设S是非空有限集，代数系统<P（S），∪>中，其中P（S）为集合S的幂集，则P（S）对∪运算的单位元是________，零元是________。22．在<Z6,eq\o\ac(○,+)>中，2的阶是________。23．设<A，≤>是格，其中A={1，2，3，4，6，8，12，24}，≤为整除关系，则3的补元是________。24．在下图中，结点v2的度数是________。25．________，从v2到v4长度为2的路有________条。三、计算题（本大题共5小题，第26、27小题各5分，第28、29小题各6分，第30小题8分，共30分）26．已知A={{}，{，1}}，B={{，1}，{1}}，计算A∪B，Aeq\o\ac(○,+)B，A的幂集P（A）。27．构造命题公式（（P∧Q）→P）∨R的真值表。28．29．求下列公式的主合取范式和主析取范式：P∨（P→（Q∨（Q→R）））30．设A={1，2，3，4，6，8，12，24}，R为A上的整除关系，试画<A，R>的哈斯图，并求A中的最大元、最小元、极大元、极小元。四、证明题（本大题共3小题，第31、32小题各6分，第33小题8分，共20分）31．在整数集Z上定义：，证明：<Z，>是一个群。32．R是集合A上自反和传递的关系，试证明：RR=R。33．证明：边e是图G的一条割边，当且仅当图G中不存在包含边e的简朴回路。五、应用题（本大题共2小题，第34小题6分，第35小题9分，共15分）34．构造下面推理的证明。假如小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。35．今有n个人，已知他们中任何2人的朋友合起来一定包含其余n-2人。试证明：（1）当n≥3时，这n个人能排成一列，使得中间任何人是其两旁的人的朋友，而两头的人是其左边（或右边）的人的朋友。（2）当n≥4时，这n个人能排成一圆圈，使得每个人是其两旁的人的朋友。全国2023年7月自考离散数学试题课程代码：02324一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个备选项中只有一个是符合题目规定的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.下列句子为命题的是()A.走，看电影去 B.x+y>0C.空集是任意集合的真子集 D.你明天能来吗?2.下列式子不是谓词合式公式的是()A.(x)(P(x)→(x)(Q(x)∧A(x，y))) B.(x)∧(y)∨P(x，y)C.(x)P(x)→R(y) D.(x)P(x)∧Q(y，z)3.下列式子为重言式的是()A.P→P∨Q B.(﹁P∧Q)∧(P∨﹁Q)C.﹁(PQ) D.(P∨Q)(P→Q)4.设个体域为实数集，特定元素a=0，函数f(x，y)=x-y，特定谓词F(x，y)为x<y，下列公式真值为真的是()A.(x)(y)F(x，f(f(x，y)，y))B.(x)(y)(﹁F(f(x，y)，x))C.(x)(y)(z)(F(x，y)→F(f(x，z)，f(y，z)))D.(x)F(f(a，x)，a)5.对于公式(x)(y)P(x，y)∨Q(x，z)∧(x)P(x，y)，下列说法对的的是()A.x是自由变元 B.x是约束变元C.(x)的辖域是P(x，y)∨Q(x，z) D.(x)的辖域是P(x，y)6.设论域为{1，2}，与公式(x)﹁A(X)等价的是()A.﹁A(1)∨﹁A(2) B.﹁A(1)→﹁(A2)C.﹁A(1)∧﹁A(2) D.A(1)→A(2)7.设Z+是正整数集，f：Z+×Z+→Z+，f(n，m)=nm，则f()A.仅是入射 B.仅是满射C.是双射 D.不是函数8.下列哪个关系矩阵所相应的关系具有自反性()A. B.C. D.9.设R1和R2是集合A上的相容关系，下列关系哪个也许不是相容关系()A.R1R2 B.RlR2C.R1-1 D.RlR210.在整数集上，下面哪个运算不是二元运算()A.加法 B.减法C.乘法 D.除法11.设A是奇数集合，×为乘法运算，则<A，×>是()A.半群 B.群C.循环群 D.互换群12.下面不满足结合律的运算是()A.a*b=min(a，b) B.a*b=max(a，b)C.a*b=2(a+b) D.a*b=2ab13.右图的最小入度是()A.0B.1C.2D.314.下面既是汉密尔顿图又是欧拉图的图形是()15.一棵树有3个5度点、1个4度点、3个2度点，其它的都是1度，那么它的边数是()A.17 B.18C.19 D.20二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上对的答案。错填、不填均无分。16.设命题变元为P，Q，R，则小项m100=________，大项M010=________。17.置换规则：在证明的任何环节上，命题公式中的任何子命题公式都可以________，记为________规则。18.一个公式，假如量词均在全式的________，其作用域延伸到整个公式的________，则该公式称为前束范式。19.请用联结词﹁，∧表达联结词∨和联结词：________，________。20.设A={l，2，3，4}，A上的二元关系R={<1，2>，<3，4>，<4，3>}，S={<l，3>，<3，4>，<4，1>}，则R～S=________，(RS)-1=________。21.代数系统<A，*，>是整环，则<A，*>是________，<A，>是________，且无零因子。22.在实数集R上定义运算ab=a+b+ab，则幺元为________，元素2的逆元为________。23.若回路中，除________外________各不相同，则此回路称为圈(或初级回路)。24.偶图记为Kn,m那么当________时，Kn,m是平面图，当________时，Kn,m是非平面图。25.若图中存在________，它通过图中所有的边恰好________次，则称该图为欧拉图。三、计算题(本大题共6小题，每小题5分，共30分)26.用等值演算求(P→Q)→R的主合取范式。27.列出(P→(Q∨R))(P→Q)的真值表。28．设A={a,b,c,d}，R={<a，b>，<a，d>，<b，c>，<c，a>，<d，a>}，求R的传递闭包。29.设A={2，3，6，12，24，36}，请画出A上整除关系的哈斯图，并给出子集{6，1