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.设是格,其中一个命题P是a≤(a∨b) ∧(a∨c),则P的对偶命题是a_____(a∧b)_____(a∧c)。 19.设Z是整数集,+是整数加法运算,则
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={|a,b∈
X∧a是b的母亲},那么关系{|a,b∈x∧ a是b的祖母}的表达式为( ) A.R?S C.S?R
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 ,其中*是S上的二元运算,若a,b∈S,且对任意的x∈S,都有a*x=x*a=x,b*x=x*b=b,是群,则满足结合律和______________;若|S|>l,S中不
相关推荐: