成都信息工程学院离散数学往年考题1

一 单项选择题(请将答案填在下表中，每小题2分，共20分) ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩

① 命题公式Q→(P∨¬P)是( )。

(A) 矛盾式 (B) 重言式

(C) 非永真的可满足式 (D) 以上都不对

② 设个体域为全体自然数集合，下列公式中真值为T是( )。

__(A) _∀x∃y(x+y=) (B) ∀x∀y(x+y=)

__(C) ∃x∃y(x+y=) (D) ∃x∀y (x+y=)

____③谓词公式∀x(P(x)∧∃xQ(x,y)→∃yR(x,y))∨A(x,y)，以下陈述错误的是（___号(A) x的辖域是P(x)xQ(x,y)yR(x,y) 学__(B) x的辖域是Q(x,y)

___(C) R(x,y)中的x是自由出现

___题 (D)此公式等值于 ∀z(P(z)∧∃xQ(x,y)→∃yR(z,y))∨A(x,y) ___答④ 设A,B,C为任意集合,下列表达正确的是( )。

名_不(A)  (B) A－B＝  A＝B 姓_内(C)AB＝AC  B＝C (D) AB＝A  AB=A __⑤ 设A＝{1,2},B={a,d,c},C={c,d}, 则(B－C)×A= ( )。

_线___封(A){<1,a>,<2,a>} (B){,<2,c>}

____密(C){,} (D){,}

_级⑥设V=，其中N是自然数，+是普通加法。令 f(x)=3x (∀x∈N), 班 以下四个命题是真的是( )。

___ (A) f是V的满自同态 (B) f是V的单自同态 __ (C) f是V的自同构 (D) 以上都不对 ___⑦设N是自然数集合，则下列四个陈述不对是( )。

___(A) 是N上的偏序关系 (B) =不是N上的等价关系 _名(C) 是N上的偏序关系 (D) 是N上的线序关系

系⑧设是一个10阶群,a是G中一个确定元素.a的阶不可能是( )。

(A) 1 (B) 2 (C) 8 (D) 10 ⑨在自然数集合N上，下列运算可结合的是（ ）。

(A) xymax(x,y) (B) xy2xy

(C) xyx2y2 (D) xyxy

⑩下面四个图中，哪个是欧拉图( )。

——第1页——

。 ）

系名____________班级____________姓名____________学号____________

二 填空题(每小题2分，共20分)

①设A是一个非空集合,P(A)是A的幂集,则的单位元是 。 ②使命题公式P (PQ)成假的赋值是 。 ③n个顶点的无向完全图的边数一定是 。

④设N(x)：x是自然数，Z(y)；y是整数，则命题“一切自然数都是整数，而有的整数不是自然数”符号化为 。

⑤命题公式A含3个命题变元P，Q，R，其成真赋值为000，010，100，110，A的主析取范式为 。

⑥若G为连通的平面图，有a个顶点，b个面，则G的边数是 。

⑦连通无向图G有6个顶点10条边，要得到G的一棵生成树，必须删去 条边。 ⑧若集合A上的二元关系R的关系矩阵主对角线上元素全是1，则关系R具有 性质。

⑨无向完全图K3的不同构的生成子图的个数为 。 ⑩已知有向图G的邻接矩阵为1001110001000111010111，则110密封线内不答题 G的边数是 。

三 解答下列各题(①6分, ②4分，③8分，共18分)

① 构造命题公式(PQ)((PQ)P)的真值表，并判断该公式的类型． ②求谓词公式∀x(P→Q(x))∨R(4)的真值．

其中P：43，Q(x)：x1，R(x)：x2，个体域D={0,4}．

③判断下列推理是否正确(先将前提和结论的各命题符号化，然后进行判断，必须构造证明过程)

如果本周是这学期第十九周,则要进行英语或离散数学考试.如果英语老师去外地开会,则不考英语.本周是第十九周,英语老师外地有会.所以要进行离散数学考试. 四 解答下列各题(1,3小题各5分，2小题6分,共16分) 1 设A={a,b,c,d}，A上的二元关系R={,,} ①画出R的关系图，求出R的逆关系； ②求R的对称闭包s(R)

2 偏序集的哈斯图如下所示。 ①试写出A和R的集合表达式；

②求A的子集B={b,c,d}的极大元,最大元和上界。

——第2页——

系名____________班级____________姓名____________学号____________

3 设R和S是集合A＝{1,2,3}上的二元关系， R＝{<1,2>,<3,1>} S={<1,2>,<2,1>,<3,3>} 求RS，R－S,写出合成关系矩阵MRS． 五 解答下列各题(1题6分, 2题8分,共14分)

1.设V=，S={a, b, c}，*的运算表给定如下：

* a a b c a b c b b b c c c c c ①指出V=的零元、单位元；

密封线内不答题 ②找出可逆元及其逆元；

③*运算是否满足交换律、结合律,给出理由。

2若I是整数集，I上的二元运算*定义为x*y=x+y-3，证明是一个阿贝尔群。 六解答下列各题(每小题6分,共12分)

1一棵树有两个顶点度数为2，一个顶点度数为3，三个顶点度数为4，其余都是一度顶点。问它有几个1度顶点？ 2下图给出的赋权图表示七个村镇,a,b,c,d,e,f,g及架起它们间通信线路的预测造价,试给出一个设计方案,使得各村镇之间能够通信且造价最小,要求计算出最小总造价(单位:万元).

——第3页——