西工大明德学院离散数学试卷A第 页 共 页诚信保证本人知晓我院考场规则和违纪处分条例的有关规定，保证遵守考场规则，诚实做人。

本人签字： 编号：西北工业大学明德学院考试试题（卷）－ 学年第 学期开课单位 课程 学时 考试日期 命题教师 审题教师 考试时间 小时 考试形式（闭开）（A ）卷 题号 一 二三四五六七总分得分考生班级序号学号姓名一、选择题1．下列是两个命题变元p ，q 的小项是（ ）A ．p ∧┐p ∧qB ．┐p ∨qC ．┐p ∧qD ．┐p ∨p ∨q2．设P ：我将去镇上，Q ：我有时间。

命题“我将去镇上，仅当我有时间时”符号化为（）A.P →QB.Q →PC.P ↔QD.⌝Q ∨⌝P3．谓词公式(∀x)(∀y)(A(x,y)∧B(y,z))∧(∃x)A(x,y)中量词(∀x)的辖域是（ ）A ．(∀y)(A(x,y)∧B(y,z))B ．(∀y)(A(x,y)C ．A(x,y)∧B(y,z)D ．(∀y)(A(x,y)4．设A={a,b,c,d}，A 上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪I A ，则对应于R的A 的划分是（ ）A ．{{a},{b,c},{d}}B ．{{a,b},{c},{d}}C ．{{a},{b},{c},{d}}D ．{{a,b},{c,d}}5．以下关系属于偏序关系的是（ ）。

（A ）实数集上两实数间的“等于”关系 （B ） 同余关系 （C ）整数集上两实数间的“大于”关系 （D ） 良序关系6. 在自然数集N 上，下列定义的运算中不可结合的只有（ ）A ．a*b=min(a,b)B ．a*b=a+bC ．a*b=GCD(a,b)(a,b 的最大公约数)D ．a*b=a(mod b)7．设R为实数集，R+={x| x∈R ∧x>0}，*是数的乘法运算，<R+，*>是一个群，则下列集合关于数的乘法运算构成该群的子群的是（）A．{R+中的有理数} B．{R+中的无理数}C．{R+中的自然数} D．{1，2，3}8. 下列哪一组命题公式是等值的？（）A. ⌝P∧⌝Q,P∨QB.A→(B→A),⌝A→(A→⌝B)C.Q→(P∨Q),⌝Q∧ (P∨Q)D.⌝A∨ (A∧B),B9. 下面哪一个命题是假命题？（）A.如果2是偶数，那么一个公式的析取范式惟一B.如果2是偶数，那么一个公式的析取范式不惟一C.如果2是奇数，那么一个公式的析取范式惟一D.如果2是奇数，那么一个公式的析取范式不惟一10. 下列运算中，哪种运算关于整数集不能构成半群？（）A.aοb=max{a,b}B.aοb=bC.aοb=2abD.aοb=|a-b|11. 设A={a,b,c}上的关系如下，有传递性的有（）A.ρ1={<a,c>,<c,a>,<a,b>,<b,a>}B.ρ2={<a,c>,<c,a>}C.ρ3={<a,b>,<c,c>,<b,a>,<b,c>}D.ρ4={<a,a>}12. 设D=<V,E>为有向图，则有（）A.E⊆V×VB.E⊄V×VC.V×V⊂ED.V×V=E13. 设G为有n个结点的简单图，则有（）A.△(G)<nB.△(G)≤nC.△(G)>nD.△(G)≥n14. 设|V|>1，D=<V,E>是强连通图，当且仅当（）A.D中至少有一条通路B.D中至少有一条回路C.D中有通过每个结点至少一次的通路D.D中有通过每个结点至少一次的回路二、填空题(每空3分，共30分)1. 设F(x): x是人，G(x): x用右手写字，命题“有的人并不用右手写字”在一阶逻辑中符号化的形式为_______________。

2. 设A={1,2,3}，f，g，h是A到A的函数，其中f(1)=f(2)=f(3)=1；g(1)=1，g(2)=3，g(3)=2；h(1)=3，h(2)=h(3)=1，则①是单射；②是满射；③是双射。

第页共页第 页 共 页3. 设图D=<V ,E>；V={v 1,v 2,v 3,v 4}，若D 的邻接矩阵⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=0001001111011010A ，则deg -(v 1)=① ,deg +(v 4)= ② ，从v 2到v 4长度为2的通路有 ③ 条。

4. 设A={1,2,3}上的关系R={<1,1>,<1,2>,<1,3>,<3,3>}，则关系R 具备 ① 性，不具备 ② 性。

5. 设A={1,2,3,4}上关系R={<1,2>,<2,4>,<3,3>,<1,3>}，则r(R)= ① ，s(R)= ② 。

6. 令R(x)：x 是实数，Q(x)：x 是有理数。

(1) 命题“并非每个实数都是有理数”。

其符号化为 ① 。

(2) 命题“虽然有些实数是有理数，但并非一切实数都是有理数”。

则其符号化可表示为 ② 。

7. .Q →(P ∨(P ∧Q)) 可化简为 。

8. 后面是图的题33. A={2,3,4,5,6,8,10,12,24}，R 是A 上的整除关系。

那么A 的极大元是 ① ，极小元是 ② 。

假如上午不下雨，我去看电影，否则就在家里读书或看报符号化形式为_______________。

P: 上午下雨。

Q:我去看电影。

R:我在家里读书。

S:我在家里看报。

(┓P→Q)∧(P→(R∨S))由n 个命题变元组成不等值的命题公式的个数为（）A.2nB.2nC.n2D.2n21. 设P ：我将去镇上，Q ：我有时间。

命题“我将去镇上，仅当我有时间时”符号化为（） A.P →Q B.Q →P C.P ↔Q D.⌝Q ∨⌝P2. 设P ：我们划船，Q ：我们跑步。

命题“我们不能即划船又跑步”符号化为（） A. ⌝p ∧⌝Q B. ⌝P ∨⌝Q C. ⌝(P ↔Q) D.P ↔⌝Q3. 设P ：张三可以作这件事，Q ：李四可以作这件事。

命题“张三或李四可以做这件事”符号化为（） A.P ∨Q B.P ∨⌝Q C.P ↔Q D. ⌝(⌝P ∨⌝Q)4. 下列语句中哪个是真命题？（）A.我正在说谎。

B.严禁吸烟。

C.如果1+2=3，那么雪是黑的。

D.如果1+2=5，那么雪是黑的。

2.谓词公式∀x(P(x)∨∃yR(y))→Q(x)中量词∀x的作用域是（）A. ∀x(P(x)∨∃yR(y))B.P(x)C. (P(x)∨∃yR(y))D.P(x)，Q(x)3.谓词公式∀x(P(x)∨∃yR(y))→Q(x)中变元x是（）A.自由变量B.约束变量C.既不是自由变量也不是约束变量D.既是自由变量也是约束变量4.设C(x)：x是运动员，G(x)：x是强壮的。

命题“没有一个运动员不是强壮的”可符号化为（）A.⌝∀x(C(x)∧⌝G(x))B.⌝∀x(C(x)→⌝G(x))C.⌝∃x(C(x)∧⌝G(x))D.⌝∃x(C(x)→⌝G(x))5.设A(x)：x是人，B(x)：x犯错误，命题“没有不犯错误的人”符号化为（）A.∀x(A(x)∧B(x))B.⌝∃x(A(x)→⌝B(x))C.⌝∃x(A(x)∧B(x))D.⌝∃x(A(x)∧⌝B(x))6.令F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快。

则语句“某些汽车比所有的火车慢”可表示为（）A.∃y(G(y)→∀x(F(x)∧H(x,y)))B.∃y(G(y)∧∀x(F(x)→H(x,y)))C.∀x∃y(G(y)→(F(x)∧H(x,y)))D.∃y(G(y)→∀x(F(x)→H(x,y)))2.f:Z→Z，对任意的i∈Z，有f(i)=i(mod 8)，则f是（）A.不是双射B.单射C.满射D.双射2.设集合A={1,2,3,…,10}，下面定义的哪种运算关于集合A是不封闭的？（）A.x*y=max{x,y}B.x*y=min{x,y}C.x*y=GCD(x,y)，即x，y的最大公约数D.x*y=LCM(x,y)，即x，y的最小公倍数7.Q是有理数，(Q,*)（其中*为普通乘法）不能构成（）A.群B.独异点C.半群D.交换半群8.R为实数集，运算*定义为：a,b∈R，a*b=a⋅|b|，则代数系统(R,*)是（）A.半群B.独异点C.群D.阿贝尔群下列代数系统(S,*)中，哪个是群？（）A.S={0,1,3,5}，*是模7的加法B.S=Q(有理数集合)，*是一般乘法C.S=Z(整数集合)，*是一般乘法D.S={1,3,4,5,9}，*是模11的乘法10. 具有如下定义的代数系统(G,*)，哪个不够成群？（）A.G={1,10}，*是模11的乘法B.G={1,3,4,5,9}，*是模11的乘法第页共页C.G=Q，*是普通加法D.G=Q，*是普通乘法2. 下面哪一个偏序集（其中均略去了反映自反关系的序对）能构成格？（）A.A={a,b,c,d},≤={<d,c>,<c,b>,<b,a>,<d,b>,<d,a>}B.A={a,b,c,d,e},≤={<b,a>,<c,b>,<d,b>,<e,c>,<e,d>,<e,b>}C.A={a,b,c,d,e,f,g},≤={<b,a>,<d,a>,<c,b>,<c,d>,<f,e>,<g,f>}D.A={1,2,3,4},≤={<1,2>,<1,3>,<2,4>,<3,4>}3. 下面哪个偏序集构成有界格？（）A.(N,≤)B.(Z,≥)C.({2,3,4,6,12},|)D.(P(A),⊆)其中|为整除关系，A={a,b,c}。

7.用谓词和量词将下列命题符号化：(1).没有不犯错误的人；(2).尽管有人聪明，但未必一切人都很聪明；(3).每个计算机系的学生都学离散数学；(4).所有的人都学习和工作；(5).并非一切推理都能用计算机完成；(6).任何自然数都有惟一的一个后继数。

2.设G=<V,E>为无环的无向图，|V|=6，|E|=16，则G是（）A.完全图B.零图C.简单图D.多重图3.含5个结点、3条边的不同构的简单图有（）A.2个B.3个C.4个D.5个4.任何无向图中结点间的连通关系是（）A.偏序关系B.等价关系C.相容关系D.拟序关系2.设A={1,2,3,4,5}，ρ={<i,j>|i<j,i,j∈A}，则°ρ的性质是（）A.对称的B.自反的C.反对称的D.反自反、反对称、传递的设集合A={a,b,c}，R是A上的二元关系，R={<a,a>,<a,b>,<a,c>,<c,a>}，那么R是（）A.反自反的B.反对称的C.可传递的D.不可传递的5.下列句子中，是命题的有(1).我是教师。