B. (?x)(?y)(x?y?1) C. (?y)(?x)(x?y?x)
D. (?x)(?y)(?z)(x?y?z)
13.在命题演算中，语句为真为假的一种性质称为( ) A.真值 B.陈述句 C.命题 D.谓词
14.设P：明天天晴；q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为( ) A.p??q B. ?p??q C. ?p???q
D. ?p?q
15.下列命题公式是永真式的是( ) A.(p??p)
??q
B.?(p?q)?q D.(p?p)?(p??p)
C. (p?q)?q
二、填空题(本大题共10小题，每空1分，共20分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。
17.在一棵根树中，有且只有一个结点的入度为_____，其余所有结点的入度均为_____。
18.设
20.当f:X→Y是_____函数时，f有逆函数，且f -1。f=_____。
21.设E={1,2,3,4,5,6},A={1,4},B={1,2,3},C={2,4},则(～A∩～B)∩C=_____,幂集P((～A∩～B)∩C)=_____。 22.设论域D={a,b},则(?x)P(x)?_____,(?x)(?y)Q(x,y)?_____。
23.使公式(?x)(?y)(A(x)?B(y))?((?x)A(x)∨(?y)B(y))成立的条件是_____不含有y，_____不含有x。 24.由命题变元及其否定所组成的有限个析取式的合取式称为_____，由命题变元及其否定所组成的有限个合取式的析取式称为_____。
25.不包含_____的命题叫做原子命题，包含_____的命题称为复合命题。
三、计算题(本大题共7小题，第26、28小题每小题5分，第27、31小题每小题7分，第29、30小题每小
题8分，第32小题9分，共49分)
26.用等值演算法，求P∨(Q∧R)的主析取范式，并按P，Q，R顺序，写成编码形式。 27.设A={1,2,3}，给定A上二元关系R={<1,1>,<1,2>,<2,3>}，求r(R),s(R)和t(R)。 28.求公式(?x)(f(x)?(?y)G(x,y,z))?(?z)H(x,y,z)的前束范式。
29.对如下有向图D，求D中长度为4的路有多少条?其中回路有多少条?
30.设A={a,abc,bc,bcd,bd}，定义A上二元关系R={
21
②向R中最少添加几个序偶可使之成为等价关系?求出该等价关系所确定的集合A的划分。
31.某科研所要从3个项目A、B、C中选择1～2个项目上马，由于某种原因，立项时要满足以下条件： (1)若A上，则C也要上； (2)若B上，则C不能上；
(3)若C不上，则A或B可以上。 请找出所有的立项方案
32.设有6个城市V1，V2，…，V6，它们之间有输油管连通，其布置如下图(a),Si(数字)中Si
为边的编号，括号内数字为边的权，它是两城市间的矩离，为了保卫油管不受破坏，在每段油管间派一连士兵看守，为保证每个城市石油的正常供应最少需多少连士兵看守?输油管道总长度越短，士兵越好防守。求他们看守管道的最短的总长度。(要求写出求解过程)
四、证明题(本大题共2小题，每小题8分，共16分) 33.证明(?x) (P(x) →Q(x))├(?x)P(x)→(?x)Q(x)
34.证明当每个结点的度数大于等于3时，不存在有7条边的连通简单平面图。
全国2006年4月高等教育自学考试
离散数学试题
课程代码：02324
一、单项选择题（本大题共15小题，每小题1分，共15分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．下列命题公式为重言式的是（ ） A．p→ (p∨q) C．q∧┐q
2．下列语句中不是命题的只有（ ） ．．A．这个语句是假的。 C．飞碟来自地球外的星球。
B．1+1=1.0
D．凡石头都可练成金。 B．(p∨┐p)→q D．p→┐q
3．设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是（ ） A．┐p∧q C．┐p→┐q
4．下列等价式正确的是（ ） A．┐(?x)A?(?x)┐A B．(?x)(?y)A?(?x)(?y)A C．┐(?x)A?(?x)┐A
D．(?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)
B．┐p→q D．p→┐q
22
5．在公式(?x)(?y)(P(x,y)?Q(z))?(?y)P(y,z)中变元y是（ ） A．自由变元 B．约束变元
C．既是自由变元，又是约束变元 D．既不是自由变元，又不是约束变元
6．设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S是（ ） A．自反关系 C．对称关系
B．反自反关系 D．传递关系
7．设集合X为人的全体，在X上定义关系R、S为R={
X∧a是b的母亲}，那么关系{
B．R-1?S D．R?S-1
8．设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>} 9．下列式子不正确的是（ ） A．(A-B)-C=(A-C)-B C．(A-B)-C=(A-C)-(B-C)
10．下列命题正确的是（ ） 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．
D．
B．{1，2，3，6，12} D．{l，2，3，7}
B．(A-B)-C=A-(B∪C) D．A-(B∪C)=(A-B)∪ C
13．结点数为奇数且所有结点的度数也为奇数的连通图必定是（ ）
23
A．欧拉图 B．汉密尔顿图 C．非平面图 D．不存在的 14．无向图G是欧拉图当且仅当G是连通的且（ ） A．G中各顶点的度数均相等 B．G中各顶点的度数之和为偶数 C．G中各顶点的度数均为偶数 D．G中各顶点的度数均为奇数
15．平面图(如下)的三个面的次数分别是（ ） A．11，3，4 B．11，3，5 C．12，3，6 D．10，4，3
二、填空题（本大题共10小题，每小题2分，共20分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16．求一个公式的主析取或主合取范式的方法，有______________法和______________法。
17．给定谓词合式公式A，其中一部分公式形式为(?x)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。
那么f3?f2?f1的定义域是______________，而复合函数(f3?f2?f1)(x)= ______________。
19．集合X={a，b，c，d}上二元关系R={ d>}，则R的自反闭包r(R)= ______________，对称闭包s(R)= ______________。 20．已知G=<{l，-1，i，-i}，·>(其中i=?1，是数的乘法)是群，则-l的阶是______________；i的阶是 ______________。 21．对代数系统 则称a为运算“*”的______________，称b为运算“*”的______________。 22．设 可能有______________。 23．写出如右有向图的一条初级回路：______________，其长度是______________。 24．一个______________且______________的无向图称为树。 25．在简单无向图G= 如果V有n个结点，那么它还是______________度正则图。 三、计算题(本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共30分) 26．若集合A={a，{b，c}}的幂集为P(A)，集合B={ O / ，{ O / }}的幂集为P(B)， 求P(A)∩P(B)。 27．构造命题公式(p→ (q∧ r))→┐p的真值表。 28．求图G＝ E＝｛(v1,v2), (v2,v3), (v2,v4), (v3,v2), (v3,v4), (v3,v1), (v4,v1)｝ 24
相关推荐：
loading