2002年4月全国自考离散数学试题试卷真题及答案
全国2002年4月高等教育自学考试
离散数学试题
一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。
1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( B )
A.汉密尔顿回路
B.欧拉回路
C.汉密尔顿通路
D.初级回路
2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( D )
A.10
B.12
C.16
D.14
3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( A )
A.b∧(a∨c)
B.(a∧b)∨(a’∧b)
C.(a∨b)∧(a∨b∨c)∧(b∨c)
D.(b∨c)∧(a∨c)
4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( A )
A.<{1},·>
B.〈{-1},·〉
C.〈{i},·〉
D.〈{-i},·〉
5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交
运算，下列系统中是代数系统的有( D )
A.〈Z，+，/〉
B.〈Z，/〉
C.〈Z，-，/〉
D.〈P(A)，∩〉
6.下列各代数系统中不含有零元素的是( D )
A.〈Q，*〉Q是全体有理数集，*是数的乘法运算
B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算
C.〈Z， 〉，Z是整数集， 定义为x xy=xy, ?x,y∈Z
D.〈Z，+〉，Z是整数集，+是数的加法运算
7.设A={1,2,3}，A上二元关系R的关系图如下：
R具有的性质是( D )
A.自反性
B.对称性
C.传递性
D.反自反性
8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，
则关系R的对称闭包S(R)是( C )
A.R∪I A
B.R
C.R∪{〈c,a〉}
D.R∩I A
9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的
等价关系，R应取( D )
A.｛〈c,a〉，〈a,c〉｝
B.{〈c,b〉，〈b,a〉}
C.{〈c,a〉，〈b,a〉}
D.{〈a,c〉，〈c,b〉}
10.下列式子正确的是( B )
A. ?∈?
B.???
C.{?}??
D.{?}∈?
11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x ( A ) A.( ?x)( ?y)( ?z)(A(x,y))→A(f(x,z),f(y,z)) B.( ?x)A(f(a,x),a) C.(?x)(?y)（A(f(x,y),x)) D.(?x)(?y)(A(x,y)→A(f(x,a),a)) 12.设B是不含变元x的公式，谓词公式(?x)(A(x)→B)等价于( A ) A.(?x)A(x)→B B.(?x)A(x)→B C.A(x)→B D.(?x)A(x)→(?x)B 13.谓词公式(?x)(P(x,y))→(?z)Q(x,z)∧(?y)R(x,y)中变元x( C ) A.是自由变元但不是约束变元 B.既不是自由变元又不是约束变元 C.既是自由变元又是约束变元 D.是约束变元但不是自由变元 14.若P ：他聪明；Q ：他用功；则“他虽聪明，但不用功”，可符号化为( B ) A.P ∨Q B.P ∧┐Q C.P →┐Q D.P ∨┐Q 15.以下命题公式中，为永假式的是( C ) A.p →(p ∨q ∨r) B.(p →┐p)→┐p C.┐(q →q)∧p D.┐(q ∨┐p)→(p ∧┐p) 二、填空题(每空1分，共20分) 16.在一棵根树中，仅有一个结点的入度为 0 ，称为树根，其余结点的入度均为 1 。 17.A={1,2,3,4}上二元关系R={〈2，4〉，〈3，3〉，〈4，2〉}，R 的关系矩阵M R 中 m 24= 1 ,m 34= 0 。 18.设〈s,*〉是群，则那么s 中除 单位元 外，不可能有别的幂等元；若〈s,*〉有零元，则 |s|= 1 。 19.设A 为集合，P(A)为A 的幂集，则〈P(A)，?〉是格，若x,y ∈P(A),则x,y 最大下界是 x ∩y ，最小上界是 x ∪y 。 20.设函数f:X →Y,如果对X 中的任意两个不同的x 1和x 2，它们的象y 1和y 2也不同，我们说f 是 入射 函数，如果ranf=Y ，则称f 是 满射 函数。 21.设R 为非空集合A 上的等价关系，其等价类记为〔x 〕R 。?x,y ∈A ，若〈x,y 〉∈R ，则 〔x 〕R 与〔y 〕R 的关系是［x ］R =［y ］R ，而若〈x,y 〉?R ，则〔x 〕R ∩〔y 〕R =______。 22.使公式(?x)( ?y)(A(x)∧B(y))?(?x)A(x)∧(?y)B(y)成立的条件是 A(x) 不含有y ， B(y) 不含有x 。 23.设M(x):x 是人，D(s):x 是要死的，则命题“所有的人都是要死的”可符号化为(?x) (M(x)→D(x)) ,其中量词(?x)的辖域是M(x)→D(x) 。 24.若H 1∧H 2∧…∧H n 是 可满足式 ，则称H1,H2,…Hn 是相容的，若H 1∧H 2∧…∧H n 是永假式(或矛盾式) ，则称H 1,H 2,…H n 是不相容的。 25.判断一个语句是否为命题，首先要看它是否为 陈述句 ，然后再看它是否具有唯一的 真值 。 三、计算题 (共30分) 26.(4分)设有向图G=(V ,E)如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。 答：26. M=110010101 0110 011?????????????? M 2=2110211121 211011???????????? ?? M ij j i 2141418==∑∑=, M ij i 2 146=∑= G中长度为2的路总数为18，长度为2的回路总数为6。 27.(5)设A={a,b},P(A)是A的幂集，⊕是对称差运算，可以验证 整数，求({a}-1{b}{a})n⊕{a}-n{b}n{a}n 答：当n是偶数时，?x∈P(A),x n=? 当n是奇数时，?x∈P(A),x n=x 于是：当n是偶数，(｛a｝-1｛b｝｛a｝)n⊕｛a｝-n｛b｝n｛a｝n =?⊕(｛a｝-1)n｛b｝n｛a｝n=?⊕?=? 当n是奇数时， (｛a｝-1｛b｝｛a｝)n⊕｛a｝-n｛b｝n｛a｝n =｛a｝-1｛b｝｛a｝⊕(｛a｝-1)n｛b｝n｛a｝n =｛a｝-1｛b｝｛a｝⊕｛a｝-1｛b｝｛a｝=? 28.(6分)设A={1,2,3,4,5},A上偏序关系 R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪I A; (1)作出偏序关系R的哈斯图 (2)令B={1,2,3,5}，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。答：(1)偏序关系R的哈斯图为 (2)B的最大元：无，最小元：无； 极大元：2，5，极小元：1，3 下界：4，下确界4； 上界：无，上确界：无 29.(6分)求┐(P→Q)?(P→┐Q)的主合取范式并给出所有使命题为真的赋值。 答：原式?(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q)) ((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q)) (┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q)) (┐(P∧┐Q)∨(P∧┐Q)) (P∧Q)∨(P∧┐Q) P∧(Q∨┐Q) P∨(Q∧┐Q) (P∨Q)∧(P∨┐Q) 命题为真的赋值是P=1,Q=0和P=1,Q=1 30.(5分)设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。 答：令e1=(v1,v3), e2=(v4,v6) e 3=(v 2,v 5), e 4=(v 3,v 6) e 5=(v 2,v 3), e 6=(v 1,v 2) e 7=(v 1,v 4), e 8=(v 4,v 3) e 9=(v 3,v 5), e 10=(v 5,v 6) 令a i 为e i 上的权，则 a 1 取a 1的e 1∈T,a 2的e 2∈T,a 3的e 3∈T,a 4的e 4∈T,a 5的e 5∈T,即， T 的总权和=1+2+3+4+5=15 31.(4分)求公式┐((?x)F(x,y)→(?y)G(x,y))∨(?x)H(x)的前束范式。 答：原式?┐(?x 1F(x 1,y)→?y 1G(x,y 1))∨?x 2H(x 2) (换名) ?┐?x 1?y 1(F(x 1,y)→G(x,y 1))∨?x 2H(x 2) ??x 1?y 1┐(F(x 1,y 1)→G(x,y 1))∨?x 2H(x 2) ??x 1?y 1?x 2(┐(F(x 1,y 1)→G(x,y 1))∨H(x 2) 四、证明题 (共20分) 32.(6分)设T 是非平凡的无向树，T 中度数最大的顶点有2个，它们的度数为k(k ≥2),证明T 中至少有2k-2片树叶。 证明：设T 中有x 片树叶，y 个分支点。于是T 中有x+y 个顶点，有x+y-1 条边，由握手定理知T 中所有顶点的度数之的 d v i i x y ()=+∑1 =2(x+y-1)。 又树叶的度为1，任一分支点的度大于等于2 且度最大的顶点必是分支点，于是 d v i i x y ()=+∑1 ≥x ·1+2(y-2)+k+k=x+2y+2K-4 从而2(x+y-1)≥x+2y+2k-4 x ≥2k-2 33.(8分)设A 是非空集合，F 是所有从A 到A 的双射函数的集合， 是函数复合运算。 证明：〈F, 〉是群。 证明：从定义出发证明：由于集合A 是非空的，故显然从A 到A 的双射函数总是存在的，如A 上恒等函数，因此F 非空 (1)?f,g ∈F,因为f 和g 都是A 到A 的双射函数，故f g 也是A 到A 的双射函数，从而集合F 关于运算 是封闭的。 (2)?f,g,h ∈F,由函数复合运算的结合律有f (g h)=(f g) h 故运算 是可结合的。 (3)A 上的恒等函数I A 也是A 到A 的双射函数即I A ∈F,且?f ∈F 有I A f=f I A =f,故I A 是〈F ， 〉中的幺元 (4)?f∈F,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有f f-1=f-1 f=I A,因此f-1是f的逆元 由此上知〈F， 〉是群 34.(6分)在个体域D={a1,a2,…，a n}中证明等价式： (?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x) 证明：(?x)(A(x)→B(x)) ??x(┐A(x)∨B(x)) ?(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨…∨(┐A(a n)∨B(a n))) ?(┐A(a1)∨A(a2)∨…∨┐A(a n)∨(B(a1)∨B(a2)∨…∨(B(a n)) ?┐(A(a1)∧A(a2)∧…∧A(a n))∨(┐B(a1)∨B(a2)∨…∨(B(a n)) ?┐(?x)A(x)∨(?x)B(x) ?(?x)A(x)→(?x)B(x) 五、应用题(共15分) 35.(9分)如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而 且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。 证明：令p：他是计算机系本科生 q：他是计算机系研究生 r：他学过DELPHI语言 s:他学过C++语言 t:他会编程序 前提：(p∨q)→(r∧s),(r∨s)→t 结论：p→t 证①p P(附加前提) ②p∨q T①I ③(p∨q)→(r∧s) P(前提引入) ④r∧s T②③I ⑤r T④I ⑥r∨s T⑤I ⑦(r∨s)→t P(前提引入) ⑧t T⑤⑥I 36.(6分)一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。 但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么? 答：可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。 根据：构造无向简单图G= ?V i∈V,d(v i)是与v i相互认识的人的数目，由题意知?v i,v j∈V有d(v i)+d(v j)≥20,于是G 中存在汉密尔顿回路。 设C=V i1V i2…V i20V i1是G中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．． 命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．． 谓词合式公式的是（ B ） A ．（?x ）P (x )→R (y ) B ．(?x ) ┐P （x ）?(?x )(P (x )→Q (x )) C ．(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D ．(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3．下列式子为重言式的是（ ） A ．(┐P ∧R )→Q B ．P ∨Q ∧R →┐R C ．P ∨(P ∧Q ) D ．(┐P ∨Q )?(P →Q ) 4．在指定的解释下，下列公式为真的是（ ） A ．(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B ．(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C ．(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D ．(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5．对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元 C ．(?x )的辖域是R(x , y ) D ．(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2}，与公式(?x )A (x )等价的是（ ） A ．A (1)∨A (2) B ．A (1)→A (2) C ．A (1)∧A (2) D ．A (2)→A (1) 7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（ ） A ．???? ??????001110101 B ．??????????101110001 C ．??????????001100100 D ．???? ??????001010101 9．设R 1和R 2是集合A 上的相容关系，下列关于复合关系R 1?R 2的说法正确的是（ ） A ．一定是等价关系 B ．一定是相容关系 ??????????????????????精品自学考料推荐?????????????????? 浙江省 2019 年 7 月高等教育自学考试 离散数学试题 课程代码： 02324 一、单项选择题 (在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在 题干的括号内。每小题 1 分，共 14 分 ) 1.给定如下 4 个语句 : (1) 我不会游泳。(2)如果天不下雨,我就去踢足球。 (3) 我每天都看新闻联播。(4)火星上有人吗? 其中不是复合命题的是()。 A.(1)(4) B.(1)(3)(4) C.(1)(3) D.(3)(4) 2.设 P,Q,R 是命题公式 ,则 P→ R， Q→ R， P∨Q ()。 A. P B. Q C. R D. ┐ R 3.下列公式中正确的等价式是()。 A. ┐ ( x)A(x)(x) ┐ A(x) B. ┐ ( x)A(x)(x)┐ A(x) C. ( x)( y)A(x,y)( y)( x)A(x,y) D. ( x)( (x)∧ B(x))( x)A(x) ∨ ( x)B(x) 4.谓词公式 ( x)(P(x) ∨ ( y)R(y)) → Q(x) 中的 x()。 A.只是约束变元 B.只是自由变元 C.既非约束变元又非自由变元 D.既是约束变元又是自由变元 5.设个体域为整数集 ,则下列公式中值为真的是 ()。 A. (y)(x)(x · y=2) B. (x)(y)(x · y=2) C. (x)(x · y=x) D. (x)(y)(x+y=2y) 6.设 A={a,b,c}, 则 A 中的双射共有 ()。 A.3 个 B.6 个 C.8 个 D.9 个 7.设 S={a,b,c}, 则 S 的幂集的元素的个数有()。 A.3 个 B.6 个 C.8 个 D.9 个 8.设 A={a,b,c}, 则 A ×A 中的元素有 ()。 A.3 个 B.6 个 1 全国2018年7月高等教育自学考试 离散数学试题 课程代码：02324 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填 在题干的括号内。每小题1分，共14分) 1.下列语句不是 ．．命题的是( )。 A.黄金是非金属。 B.要是他不上场，我们就不会输。 C.他跑100米只用了10秒钟，你说他是不是运动健将呢? D.他跑100米只用了10秒钟，他是一个真正的运动健将。 2.关于命题变元P和Q的大项M01表示( )。 A.┐P∧Q B.┐P∨Q C.P∨┐Q D.P∧┐Q 3.公式(?x)(?y)(P(x,z)→Q(y))S(x,y)中的(?x)的辖域是( )。 A.(?y)(P(x,z)→Q(y)) B.P(x,z)→Q(y) C.P(x,z) D.S(x,z) 4.下列等价式不成立 ．．．的是( )。 A.┐(?x)A(x)?(?x)┐A(x) B.┐(?x)A(x)?(?x)┐A(x) C.(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x) D.(?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x) 5.公式(?x)(?y)(P(x,y)∧Q(z))→R(x)中的x( )。 A.只是约束变元 B.只是自由变元 C.既是约束变元又是自由变元 D.既非约束变元又非自由变元 6.设A={a,{a}}，则下列各式正确的是( )。 A.{a}∈p(A)(A的幂集) B.{a}?p(A) C.{{a}}?p(A) D.{a,{a}}?p(A) 7.集合的以下运算律不成立 ．．．的是( )。 A.A∩B=B∩A B.A∪B=B∪A C.A⊕B=B⊕A D.A-B=B-A 8.设N是自然数集，R是实数集，函数f：Ｎ→R，f(n)=lgn是( )。 A.入射 B.满射 C.双射 D.非以上三种的一般函数 9.设实数集R上的二元运算o为：xoy=x+y-2xy,则o不满足( )。 A.交换律 B.结合律 1 全国2009年4月自学考试离散数学试题（附答案） 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 2．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟 C．如果1+2=3，那么雪是黑的D．如果1+2=5，那么雪是黑的 3．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q）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，111 C．全体指派D．无 6．在公式（x ?）F（x，y）→（?y）G（x，y）中变元x是（） A．自由变元B．约束变元 C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元 7．集合A={1，2，…，10}上的关系R={ 一、单项选择题(本大题共１５小题，每小题1分,共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列句子不是．． 命题的是( D ) A.中华人民共和国的首都是北京?B ．张三是学生 C.雪是黑色的? D.太好了! 2．下列式子不是．． 谓词合式公式的是（ Ｂ ) A.(?x ）P (x ）→R (y ） B.（?x ) ┐Ｐ（x ）?(?x )(P (x )→Q （x ）) Ｃ.(?x )(?y )(P (x )∧Q (y ))→（?ｘ)R (x ) D ．(?x )(P (x ，y )→Ｑ(x ，z ))∨(?ｚ）R (ｘ,z ） 3．下列式子为重言式的是( ） A ．（┐P ∧R )→Q ?B.Ｐ∨Q ∧R →┐Ｒ C ．P ∨(P ∧Q ）?D.(┐P ∨Q )?(P →Q ） 4．在指定的解释下，下列公式为真的是（ ) Ａ．(?x )(P （x )∨Q (ｘ)），P (x ）:x =1,Q (x ):x =2,论域:{1,2｝ B ．(?x )(P (x ）∧Q (x ))，P （ｘ):x =1,Ｑ(ｘ)：x =2,论域： {1，2} C ．(?x )(P (x ) →Q (ｘ))，Ｐ(x ):ｘ>2,Q (x )：x =０，论域:{3,4} Ｄ．(?x ）(P （ｘ)→Ｑ(x )）,P (ｘ):ｘ>２,Q （x ):x ＝0，论域：｛3，4} 5.对于公式(?x ) （?y )（Ｐ(x )∧Q (y ))→(?x ）Ｒ(x ,y )，下列说法正确的是（ ) A ．y 是自由变元? B ．y 是约束变元 Ｃ．（?x ）的辖域是R(x , ｙ) D.(?x )的辖域是(?ｙ）(Ｐ(x ）∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2},与公式(?x ）A (x )等价的是( ) Ａ．A (1)∨A (2)?B.A (1)→Ａ(2) C.Ａ(1）∧Ａ(2)?D ．A (2)→A （1) 7．设Z ＋是正整数集,R 是实数集，ｆ:Z ＋ →R , ｆ(n )=lo ｇ2n ,则f ( ） A ．仅是入射? B ．仅是满射 C ．是双射 Ｄ．不是函数 ８.下列关系矩阵所对应的关系具有反对称性的是（ ) Ａ.???? ??????001110101 B ．??????????101110001 C ．??????????001100100 D.???? ??????001010101 9.设R 1和R 2是集合A 上的相容关系,下列关于复合关系R １?R ２的说法正确的是( ) A.一定是等价关系? B.一定是相容关系 全国2018年7月自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是 ．．命题的是（） A．中华人民共和国的首都是北京B．张三是学生 C．雪是黑色的D．太好了！ 2．下列式子不是 ．．谓词合式公式的是（） A．（?x）P(x)→R(y) B．(?x) ┐P（x）?(?x)(P(x)→Q(x)) C．(?x)(?y)(P(x)∧Q(y))→(?x)R(x) D．(?x)(P(x,y)→Q(x,z))∨(?z)R(x,z) 3．下列式子为重言式的是（） A．(┐P∧R)→Q B．P∨Q∧R→┐R C．P∨(P∧Q) D．(┐P∨Q)?(P→Q) 4．在指定的解释下，下列公式为真的是（） A．(?x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,论域:{1,2} B．(?x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,论域: {1,2} C．(?x)(P(x) →Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} D．(?x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} 5．对于公式(?x) (?y)(P(x)∧Q(y))→(?x)R(x,y)，下列说法正确的是（） A．y是自由变元B．y是约束变元 C．(?x)的辖域是R(x, y) D．(?x)的辖域是(?y)(P(x)∧Q(y))→(?x)R(x,y) 6．设论域为{1,2}，与公式(?x)A(x)等价的是（） A．A(1)∨A(2) B．A(1)→A(2) C．A(1)∧A(2) D．A(2)→A(1) 7．设Z+是正整数集，R是实数集，f:Z+→R, f(n)=log2n ,则f（） 1 全国2010年7月自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．．命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．．谓词合式公式的是（ B ） A ．（?x ）P (x )→R (y ) B ．(?x ) ┐P （x ）?(?x )(P (x )→Q (x )) C ．(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D ．(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3．下列式子为重言式的是（ ） A ．(┐P ∧R )→Q B ．P ∨Q ∧R →┐R C ．P ∨(P ∧Q ) D ．(┐P ∨Q )?(P →Q ) 4．在指定的解释下，下列公式为真的是（ ） A ．(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B ．(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C ．(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D ．(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5．对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元 C ．(?x )的辖域是R(x , y ) D ．(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2}，与公式(?x )A (x )等价的是（ ） A ．A (1)∨A (2) B ．A (1)→A (2) C ．A (1)∧A (2) D ．A (2)→A (1) 7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（ ） A ．???? ? ?????001110101 B ．???? ? ?????101110001 习题参考答案 1、设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点。 阮允准同学提供答案: 解：设度数小于3的结点有x个，则有 3×4＋4×3＋2x≥2×16 解得：x≥4 所以度数小于3的结点至少有4个 所以G至少有11个结点 2、设无向图G有9个结点，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。 阮允准同学答案： 证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。 若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5个结论成立。 若度数为5的结点数为6,8个，结论显然成立。 由上可知，G中至少有5个6度点或至少有6个5度点。 3、证明：简单图的最大度小于结点数。 阮同学认为题中应指定是无向简单图. 晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有n-1条边与其他结点相连，因此其度数最多只有n-1条，小于结点数n. 4、设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3 。阮同学给出证明如下： 证明：设G中所有结点的度数都小于3，即每个结点度数都小于等于2，则所有结点度数之和小于等于2n，所以G的边数必小于等于n，这和已知G有n+1条边相矛盾。所以结论成立。 5、试证明下图中两个图不同构。 晓津证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。 6、画出所有5个结点3条边，以及5个结点7条边的简单图。 解：如下图所示：(晓津与阮同学答案一致) 旧版关于一些教材勘误的讨论（2003-12-3 17:19:00） -------------------------------------------------------------------------------- 一串重要问题的讨论。晓津和虫虫。|jinxbin|虫虫： 我先和你探讨一下.:) （1）、在第18页，倒数第3行第2个式子应由"│PVQV"修改为“│PVQV│R”. 应该是倒数第8行，呵呵，害得我找了半天，算你行！:))) （2）、P74的例2 :我认为“f 。g”和“g。f”中的元素整个颠倒了。 这个理解开始时我也像你一样，但是后来发现他是对的。f。g=f(g(x),你用x=1,2,3代入算一下，是不是符合他的结果 （3）、在P75的定理中的（1）应为“f^-1。f = Ix ”“f。f^-1 = Iy”，你可以结合P75的例3看一下！ 你的意思是不是要将Ix和Iy换一下这个也一样，我开始时也这么理解，但是他是对的。 （4）、对于节的第3小题的第二个空我觉的答案应为（R是自反的）. 这个答案阮同学指出是因为A≠φ （5）、对于节的第1小题、在证明S具有传递性质的时候，我决的这样证明比较合适：设＜a，b＞，＜b，d＞∈S 则存在c使＜a，c＞，＜c，b＞，＜b，c＞，＜c，d＞∈R ∵R是传递的 有＜a，c＞、＜c，d＞∈R => ＜a，d＞∈R ∴＜a，d＞∈S 即:sS = { 离散数学自学考试复习题 课程代码：02324 一、单项选择题 1．下列命题公式为重言式的是（ ） A ．p → (p ∨q) B ．(p ∨┐p)→q C ．q ∧┐q D ．p→┐q 2．下列语句中不是．．命题的只有（ ） A ．这个语句是假的。 B ．1+1=1.0 C ．飞碟来自地球外的星球。 D ．凡石头都可练成金。 3．下列等价式正确的是（ ） A ．┐)()(x A x ???┐A B ．A y x A y x ))(())((????? C ．┐)()(x A x ???┐A D ．)()()()())()()((x B x x A x x B x A x ?∨??∧? 4．在公式),()())(),()()((z y P y z Q y x P y x ?→∧??中变元y 是（ ） A ．自由变元 B ．约束变元 C ．既是自由变元，又是约束变元 D ．既不是自由变元，又不是约束变元 5．设A={1，2，3}，A 上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S 是（ ） A ．自反关系 B ．反自反关系 C ．对称关系 D ．传递关系 6．设集合X 为人的全体，在X 上定义关系R 、S 为R={|a ，b ∈X ∧a 是b 的母亲}，那么关系{|a ，b ∈x ∧ a 是b 的祖母}的表达式为（ ） A ．R S B ．R -1 S C ．S R D ．R S -1 7．设A 是正整数集，R={(x ，y)|x ，y ∈A ∧x+3y=12}，则R ∩ ({2，3，4，6}×{2，3，4，6})= （ ） A ． O / B ．{<3，3>} C ．{<3， 3> ，<6，2>} D ．{<3，3>，<6，2>，<9，1>} 全国2002年4月 离散数学试题 课程代码：02324 一、单项选择题(本大题共15小题，每 小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G ，如果它的所有 结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G 是连通简单平面图，G 中有11 个顶点5个面，则G 中的边是 ( ) 3.在布尔代数L 中，表达式(a ∧b)∨(a ∧b ∧c)∨(b ∧c)的等价式是 ( ) ∧(a ∨c) B.(a ∧b)∨(a ’∧b) C.(a ∨b)∧(a ∨b ∨c)∧(b ∨c) D.(b ∨c)∧(a ∨c) 4.设i 是虚数，·是复数乘法运算，则 G=<{1,-1,i,-i},·>是群，下列是G 的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D. 〈{-i},·〉 5.设Z 为整数集，A 为集合，A 的幂集 为P(A),+、-、/为数的加、减、除 运算，∩为集合的交运算，下列系 统中是代数系统的有( ) A.〈Z ，+，/〉 B. 〈Z ，/〉 C.〈Z ，-，/〉 D. 〈P(A)，∩〉 6.下列各代数系统中不含有零元素的 是( ) A.〈Q ，*〉Q 是全体有理数集，*是数 的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n 阶实矩阵集合，*是矩阵乘法运算 C.〈Z ，ο〉，Z 是整数集，ο定义为x οxy=xy,?x,y ∈Z D.〈Z ，+〉，Z 是整数集，+是数的加法运算 7.设A={1,2,3}，A 上二元关系R 的关系图如下： R 具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A 上二元关系R={〈a,a 〉，〈b,b 〉,〈a,c 〉}，则关系R 的对称闭包S(R)是( ) ∪I A ∪{〈c,a 〉} ∩I A 9.设X={a,b,c},Ix 是X 上恒等关系，要使Ix ∪{〈a,b 〉，〈b,c 〉，〈c,a 〉，〈b,a 〉}∪R 为X 上的等价关系，R 应取( ) A.｛〈c,a 〉，〈a,c 〉｝ B.{〈c,b 〉，〈b,a 〉} C.{〈c,a 〉，〈b,a 〉} D.{〈a,c 〉，〈c,b 〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R 如下：论域D 为实数集，a=0,f(x,y)=x-y,A(x,y):x 全国2013年7月自学考试离散数学试题 课程代码：02324 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1．答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2．每小题选出答案后，用2B 铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均不得分。 1．设p ：天下雨；q ：我走路上学。命题“只要不下雨，我就走路上学”可符号化为 A ．p → q B ．q →p C ．┐p → q D ．q → ┐p 2．设简单无向图G 有16条边，有3个4度结点，有4个3度结点，其余结点的度数均小3，则G 中的结点个数至． 少． 为 A ．4 B ．8 C ．9 D ．1l 3．设Z （x ）：x 是整数;f （x ）：x 的绝对值；L （x ，y ）：x 大于等于y ；命题“整数的绝对值大于等于O”可符号化为 A.(()((),0))x Z x L f x ?∧ B ．(()((),0))x Z x L f x ?→ C.()((),0)xZ x L f x ?∧ D ．()((),0)xZ x L f x ?→ 4．设,αβ是集合A 上的等价关系，则下列关系一定是等价关系的是 A ．αβ? B ．αβ- C ．αβ D ．αβ⊕ 5．设论域为实数集，下列公式中真值为假的是 离散数学自学考试复 习题 离散数学自学考试复习题 课程代码：02324 一、单项选择题 1．下列命题公式为重言式的是（ ） A ．p → (p ∨q) B ．(p ∨┐p)→q C ．q ∧┐q D ．p→┐q 2．下列语句中不是．． 命题的只有（ ） A ．这个语句是假的。 B ．1+1=1.0 C ．飞碟来自地球外的星球。 D ．凡石头都可练成金。 3．下列等价式正确的是（ ） A ．┐)()(x A x ???┐A B ．A y x A y x ))(())((????? C ．┐)()(x A x ???┐A D ．)()()()())()()((x B x x A x x B x A x ?∨??∧? 4．在公式),()())(),()()((z y P y z Q y x P y x ?→∧??中变元y 是（ ） A ．自由变元 B ．约束变元 C ．既是自由变元，又是约束变元 D ．既不是自由变元，又不是约束变元 5．设A={1，2，3}，A 上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S 是（ ） A ．自反关系 B ．反自反关系 C ．对称关系 D ．传递关系 6．设集合X 为人的全体，在X 上定义关系R 、S 为R={|a ，b ∈X ∧a 是b 的母亲}，那么关系{|a ，b ∈x ∧ a 是b 的祖母}的表达式为（ ） A ．R οS B ．R -1οS C ．S οR D ．R οS -1 7．设A 是正整数集，R={(x ，y)|x ，y ∈A ∧x+3y=12}，则R ∩ ({2，3，4，6}×{2，3，4， 6})=（ ） 做试题,没答案?上自考365,网校名师为你详细解答! 全国2005年4月高等教育自学考试 离散数学试题 课程代码：02324 一、单项选择题(本大题共15小题，每小题1分，共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列各图是平面图的是( ) 2.设G是n个顶点的无向简单图，则下列说法不．正确的是) A.若G是树，则其边数等于n-1 B.若G是欧拉图，则G中必有割边 C.若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点 D.若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路 3.格L是分配格的充要条件是L不．含与下．面哪一个选项同构的子格( ) A.链 B.钻石格 C.五角格 D.五角格与钻石格 4.设 自考离散数学练习题 一、 单项选择题 1.下列句子为命题的是( ) A.全体起立! B.x=0 C.我在说谎 D.张三生于1886年的春天 2．下列语句是命题的是( ) A.月亮是圆的 B.0>+y x C.请勿吸烟 D.我正在说谎 3．下列语句中是真命题的是（ ） A ．我正在说谎 B ．严禁吸烟 C ．如果1+2=3，那么雪是黑的 D ．如果1+2=5，那么雪是黑的 4．下列公式是重言式的有( ) A.)(Q P ?? B.Q Q P →∧)( C.P P Q ∧→?)( D.P Q P ?→)( 5．下列为两个命题变元P ，Q 的小项是（ ） A ．P ∧Q ∧? P B ．? P ∨Q C ．? P ∧Q D ．? P ∨P ∨Q 6．在公式（x ?）F （x ，y ）→（? y ）G （x ，y ）中变元x 是（ ） A ．自由变元 B ．约束变元 C ．既是自由变元，又是约束变元 D ．既不是自由变元，又不是约束变元 7.设论域为{l ，2}，与公式()()x A x ?等价的是( ) A.A(1)∨A(2) B. A(1)→A(2) C.A(1) D. A(2)→A(1) 8．集合A={1，2，…，10}上的关系R={ A ．1∈A B ．{1，2，3}?A C ．{{4，5}}?A D ．?∈A 10. 设Z+是正整数集合，f:Z+→Z+，f(n)=2n-2,则f( ) A.仅是入射 B.仅是满射 C.是双射 D.不是函数 11．已知集合{}1,2,3A =上的关系{}3,3,3,1R =<><>，则=)(R s ( ) A ．{}><><31,33，， B ．{}><><><31,13,33，，， C ．{}><><><22,11,33，，， D ．{}><><><><11,31,13,33，，，， 12．设} 3 ,2 ,1 {=S ，S 上关系R 的关系图如下 ，则R 具有( )性质 A ．自反性、对称性、传递性 B ．反自反性、反对称性 C ．反自反性、反对称性、传递性 D ．自反性 13．集合},2{N n x x A n ∈==对( )运算封闭 A. 乘法 B.减法 C. 加法 D.|x-y| 14．在自然数集N 上，（对任意,a b N ∈）下列( )运算是可结合的 A.b a b a -=* B.b a b a 5+=* C.),max(b a b a =* D.b a b a -=* 15. 若要保证连通图G 是一棵树，下面所给的条件中，当且仅当必须满足的是（ ） A. 有些边不是割边 B. 每条边都是割边 C. 无割边集 D. 每条边都不是割边 二、 填空题 1. n 个命题变元的________称为大项，其中每个变元与它的否定不能同时出现，但两者必须________。 2. ()()((,)(,))(,)x y p x y Q y z xp x y ???∧?中x ?的辖域为________，x ? 1．如果R1和R2是A 上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 个． 2．()r R = __ _ __. 3．图的可达矩阵()()ij P G P =中ij P 表示___ __. 4．对于图,,G V E V =<>∈结点v(v )，则deg(v)是指___ __. 5．设个体域D ＝{a, b}，则谓词公式(?x)A(x)∧（?x ）B （x ）消去量词后的等值式为 ． 6．()()()P x x P x ??称为___ __规则. 7．在合式公式()(()()(,))x P x y R x y ?→?中，()x ?的辖域是 ， ()y ?的辖域是 . 8．设,A <≤>是一个偏序集，如果A 中任何两个元素都有 和 ，则称,A <≤>为格. 9．若函数f 既是__ _____又是__ _____，则称f 为双射的. 10．()P P P →?→?是_____ __式，()P P Q ∧?€是_______式(填永真，永假或可满足). 11．设S 为非空有限集，代数系统(),,P s <>U I 中，()P s 上，对U 的幺元为 ，零元为 ; ()P s 上，对I 的幺元为 ，零元为 . 12. 设集合A 有n 个元素，那么A 的幂集合()P A 的元素个数为 ． 13. 连通无向图G 有6个顶点9条边，从G 中删去 条边才有可能得到G 的一棵生成树T ． 14．设连通平面图G 的结点数为5，边数为6，则面数为 ． 一、填空题（本题每空 1 分，共 20分） 15．在图G ＝ 全国2018年4月高等教育自学考试 离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列命题公式为重言式的是（） A．p→(p∨q) B．(p∨┐p)→q C．q∧┐q D．p→┐q 2．下列语句中不是 ．．命题的只有（） A．这个语句是假的。B．1+1=1.0 C．飞碟来自地球外的星球。D．凡石头都可练成金。 3．设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是 （）A．┐p∧q B．┐p→q C．┐p→┐q D．p→┐q 4．下列等价式正确的是（） A．┐) x? A ? ?┐A ( ) (x B．A (? ? )( ? ) ? ? x) A x y y )( ( C．┐) ? ?┐A x? A ) (x ( D．) B x x x x A A x ? ∧ ? ∨ x? ? ( ) ( ( ) ( ) )) )( (x ( ) ( B 5．在公式) Q y P z y x P ∧ ? → x? y ?中变元y是（） )( ( )) ) y , ( ( (z )( ( ) , 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={ 自考离散数学02324真题含答案(20094-20164年整理版) 全国2009年4月自学考试离散数学试题（附答案） 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15 分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列为两个命题变元P，Q的小项是（）A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 2．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟 C．如果1+2=3，那么雪是黑的D．如果1+2=5，那么雪是黑的 3．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q）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，111 C．全体指派D．无 6．在公式（x?）F（x，y）→（?y）G（x，y）中变元x 是（） A．自由变元B．约束变元 C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元 7．集合A={1，2，…，10}上的关系R={自考离散数学试题及答案
2020年7月全国自考离散数学试题及答案解析试卷及答案解析真题.docx
7月全国自考离散数学试题及答案解析试卷及答案解析
自考离散数学02324真题含答案(2009.4-2016.4年整理版)
2010年7月自考离散数学试题及标准答案
7月全国自考离散数学试题及答案解析
离散数学及答案
自考离散数学教材课后题第五章答案
自考离散数学教材
离散数学自学考试复习题
离散数学自学考试真题附答案打印版
全国2013年7月自学考试离散数学试题
离散数学自学考试复习题说课讲解
2005年4月全国自考离散数学试题试卷真题
自考离散数学期末练习题
自考离散数学试题
(全新整理)4月全国自考离散数学试题及答案解析试卷及答案解析真题
自考离散数学02324真题含答案(20094-20164年整理版)
- 2016年4月自学考试离散数学02324试卷及答案解释完整版
- 自考离散数学02324真题含答案(2009.4-2016.4年整理版)
- 自考离散数学教材
- 离散数学自学考试真题附答案打印版
- (全新整理)4月全国自考离散数学试题及答案解析试卷及答案解析真题
- 4月全国自考离散数学试题及答案解析试卷及答案解析真题
- 自考离散数学教材课后题第五章答案
- 全国2013年7月自学考试离散数学试题
- 自考离散数学试题及答案
- 自考 离散数学教材
- 离散数学自考第二章(课堂课资)
- 自考离散数学课件
- 自考离散数学期末复习汇总
- 自考离散数学试题
- 2015年7月自考离散数学试题及答案(最新)
- 离散数学及答案
- 离散数学自学考试真题附答案打印版
- 自考离散数学02324真题含答案(2009.4-2016.4年整理版)
- (完整版)自考离散数学02324真题含答案(2009.4-2016.4年整理版),推荐文档
- 自考离散数学试题及答案