离散数学7.doc

常熟理工学院20 ~20 学年第学期
《离散数学》考试试卷(试卷库07卷)
试题总分: 100 分考试时限:120 分钟
题号
一
二
三
四
五
总分
阅卷人
得分
一、选择题(每题2分,共20分)
设L(x):x是演员,J(x):x是老师,A(x , y):x钦佩y,命题“所有演员都钦佩某些老师”符号化为( )
(A) (B)
(C) (D)
命题逻辑演绎的CP规则为( )
(A)在推演过程中可随便使用前提
(B)在推演过程中可随便使用前面演绎出的某些公式的逻辑结果
(C)设是含公式A的命题公式,,则可用B替换中的A
(D)如果要演绎出的公式为形式,那么将B作为前提,演绎出C
下列命题正确的是( )
(A) (B)
(C) (D)
设<A,£>是一个有界格,如果它也是有补格,只要满足( )
(A) 每个元素都至少有一个补元 (B) 每个元素都有多个补元 (C)每个元素都无补元 (D) 每个元素都有一个补元
设,*为普通乘法。则代数系统的幺元为( )
(A)不存在(B) (C) (D)
下列图中( )是根树
(A) (B)
(C) (D)
左图(0)相对于完全图K5的补图为( )

集合A上的关系R是相容关系的必要条件是( )
(A)自反、反对称的(B)反自反、对称的(C)传递、自反的(D)自反、对称的
公式G=PÙ￢P ,则G是( )。
(A)永真的(B)永假的(C)可满足的(D)析取的
在图G=<V,E>中,结点总度数与边数的关系是( )
(A) (B) (C) (D)
二、填空题(每题2分,共20分)
设P、Q是命题公式,填写如下的基本等价关系式:
(1) P→Q ; (2)PQ ;
论域D={1,2},指定谓词P
P (1,1)
P (1,2)
P (2,1)
P (2,2)
T
T
F
F
则公式真值为。
下图所示的哈斯图中,是格的为。

在一个群〈G,*〉中,若G中的元素a的阶是k,则a-1的阶是。
一个图的欧拉回路是一条通过图中的回路。
给定图G,若存在一条路满足,这条路称作汉密尔顿路。
一个代数系统<S,*>,如果运算*是和,则称代数系统<S,*>为半群。
一个命题公式称为合取范式,当且仅当它具有形式。
设*是定义在集合A上的二元运算,如果对于任意的x,y∈A, 都有,则称该二元运算*是可交换的。
若图G=〈V,E〉满足,则G称为连通图。
三、判断题(每题1分,共10分)
若命题合式公式A的对偶式是A*,则AÛA*。( )
“今天你吃饭了吗?”这句话不是命题。( )
设S为集合X上的二元关系,则S是传递的当且仅当SSS。( )
不可能有偶数个结点,奇数条边的欧拉图。( )
有最大元和最小元的偏序集并不一定是格。( )
连通图的生成树是唯一的。( )
在任意图中,存在奇数个度数为奇数的结点。( )
群<G,*>的运算表中的每一行或每一