当前位置：文档之家› 计算机离散数学期中试卷答案

计算机离散数学期中试卷答案

泉州师院2009-2010学年度第一学期 C. ( x)(A(x)人B(x)) ( x)A(x)人(x)B(x)

2008级计算机《离散数学》期中试卷

D. ( x)( y)(A(x) T B(y)) ( X)A(X)T( y)B(y)

7、若s={1,2,3,4}, S上关系R的关系图为：

题序-一一-二二四五总分成绩

签名

一、单项选择题：（20%,每空2分）

1.设A={a,{a}},下列命题错误的是( B )。

A. {a} P(A)

B. {a} P(A)

得分评卷人

C. {{a}} P(A)

D. {{a}} P(A)

2、假定全集E= {1,2,3,4,5,6,7,8,9,10},A={3,4,5} , B= {2,3,4,7,8,9}，贝U A U B 的位串是

(D )。

A. 01

B. 0011100000

C. 00

3、下列文氏图阴影部分所表示的集合是( A )。

A. (A-(B U C))U ((B U C)-A)

B. (A-(B A C))U ((B A C)-A)

C. (A-(B A C))U ((B U C)-A)

D. (A-(B U C))U ((B A C)-A)

4 .设p:你主修计算机科学，q :你是新生，r:

D. 00

你可以从校园网访问因特网。只有你主修计算机科学或不是新生，你才可以从校园

网访问因特网。可符号化为

A. r^p V q

C. r T p V q

5. 下列是两个命题变元

A.q p A q

C. p An p A q

6、下列等值式不正确的是

(C )。

B. r T p A q

D. r T p V q

p, q的极小项是( A )

B.n p V q

D.n p V p V q ( C )

A.n ( x)A ( x)n A

B. ( X)(B T A(x)) B T( x)A(x) 则R具有（ B ）性质。

A、自反性

C、反自反性、反对称性

B、自反性、对称性

D、自反性、对称性、传递性

&设A={a,b,c,d}, A上的等价关系

的划分是（D ）

A. {{a},{b,c},{d}}

R={,,,}U I A，则对应于R 的A

B. {{a,b},{c},{d}}

C. {{a},{b},{c},{d}}

9、设A={1, 2, 3},则A上的二元关系有(

{{a,b},{c,d}}

C )个。

3 2 3 3 Q2 2

A. 23

B. 32

C. 2

D. 3

10 .下列函数是双射的为（

集, R—实数集

A. f : I E , f (x) = 2x

A ），其中：I—整数集，E—偶数集，N—自然数

B. f : N N N, f (n) =

C. f : R I , f （x）=凶

D. f :I N, f （x） = | x |

二.填空题（20%,每题2分）

1 .集合的表示法有—列举法、描述法

__________________________________________________

。

得分

评卷人

2、设A j 0,； ,i 1,2,3,...,贝卩A i {0 }

i i 1

3 .令p:今天下雪了，q :路滑，则命题“虽然今天下雪了，但是路不滑”可符号化

为 ________ p T q ________________________ 。

10、给定函数f : 4 S,S=[0,1],f(x)=x )2+1/4,f 是单射 ___________ (满射或单射或双射或

都不是)。

三、计算题(20%,每题5分)

1、问 A U (BC)=(A U B)(A U C)吗为什么解：上式不成立。

设 A={1,2,3},B={2,3,4},C={3,4,5}

3、设 A={a,b,c,d}，其上关系 R={, , }, S={,} 求

(1) R S

(2) R 的对称闭包及传递闭包。

(1) R S={,}

(2) R 的对称闭包 S(R)= {, , , , } (3) R 的传递闭包 t(R)= {, , , }

有：

A U (BC)= {1,2,3}U {2,5}={1,2,3,5} (A U B)(A U C)= {1,2,3,4}{1,2,3,4,5}={5}

4 ?复合命题(p i q) V (p i q)是

永真式(永真式或永假式或可满足式)。

5 .令谓词P(x,y)表示”爱y ”,个体域是全世界所有人的集合，用 P(x,y)、量词和逻辑 2、求公式(p A q) V r 的标准析取范式，再根据标准析取范式求标准合取范式。

词符号化"所有人都爱某些人” ： xyP(x,y) 6. xF(x)xG(x)的前束范式是 yx F(y) G(x) ________________________ 。 7 .设 A={a,b,c,d},下列左图所示关系矩阵所表示的关系 R={ ,,,,,, }。 M R

110 0 10 0 1

0 110 0 0 10

8、设某偏序集的哈斯图如下列右图，该偏序集的拓扑排序为 1,5,3,2,7,964,8

9、设 f : N i N ,且 f (x) 1,当x 为奇数 x 当X 为偶数，则f ({1,3,4,6}=血3

2，解: (p

A q)V r

(pqr)(pqr) (pqr) (pqr)(pqr)(pqr) m 1?m 3?m 5? m e ?m 7

M o A M 2 A M 4

得分

评卷人

解:

4、设 A {X 1，X 2,X 3, X 4, X 5}，偏序集

的Hass 图为：

2、证明下列推理：前提：(pq) r, rs, sp

求①A 中最小元与最大元。

结论：q

②｛X 2,X 3,X 4｝的极小兀和极大兀。

③｛X 2X 3｝的上界与下界。

(1) (P q) r 前提引入 ④｛X 3X 4｝的上确界与下确界。

(2)r s

前提引入

? ?

解

>4 \ ⑶(p q) s

(1)(2)假言三段论

(4) s p 前提引入

(2)化简

①A 中无最小兀，最大兀为

x1。

(5)p ②｛X 2,X 3,X 4｝的极小兀为X4,极大兀为 x2,x3。

(6) s (2)化简

③｛X 2X 3｝的上界为X1，下界为X4。

(7) (p q)

⑶(6)拒取式

④｛X 3X 4｝的上确界为X3,下确界为X4。

(8) p q ⑺置换

(9) q

(5)(8)析取三段论

3、设F , G 是任意的关系，证明：(FGj 1= G -1?F 1

证：

1、设 A 、B 是任意集合，证明： (A-B)U (B-A)= (A U B)-(A Q B) 证：

=(A U B)-(A A B) =(A U B)n ~ (A n B) =(A U B)n (~A U ~B)

=A n (~A U ~B))U B n (~A U ~B) =A n ~B U B n ~A =(A-B) U (B-A)

四、证明题(20%,每题5分)

任取

x, y

(F G)

y, x

F G

t( y,t

t, x G)

t( t, y

F 1 x,t

G 1

)

t( X, t

G 1

t, y

F 1)

x, y

G 1 F

4.任何人如果他喜欢步行，他就不喜欢乘汽车，对于每个人或者喜欢乘汽车或者喜欢骑自行车，有的人不爱骑自行车，因而有的人不爱步行。逻辑推证此结论的有效性。(设个体域是人类)

Q(x): x喜欢步行；S(x): x喜欢乘汽车；R(x): x喜欢骑自行车。

前提：x(Q(x): S(x)), x(S(x) R(x)), xR(x)

结论：xQ(x)

证：

(1) x R(x) 前提引入

⑵ R(a) (1) ES规则

⑶ x(S(x) R(x)) 前提引入

⑷ S(a) R(a) (3)US规则

(5)S(a) (2)(4)析取三段论

(6) x(Q(x) S(x)) 前提引入

(7)Q(a) S(a) (6)US规则

(8) Q(a) (5)(7)拒取式

(9) x Q(x) (8)EG规则五、判断题(20%,每题2分)

(在括号中写“对”或“错”)

1、gcd(21,7)的值为7,的值为-2。( 对

)

2、设A,B,C均为E的子集，贝U ABA U (B-A)=A ( 错)

3、间接证明法可形式化地表示为：A—BB^A o (对)

4、对每个最大项而言，只有与下标编码相同的赋值是成假赋值，其余都是成真赋值。(对)

5、设个体域是整数集乙则xyz((x+y=z^J真值为1。(错 )

6、逻辑公式(xF(x) yG(y)) yG(y)不是永真式。(对)

7、因为若R是A上的关系，且

m,nN,则R m R n=R m+n，所以RF-1=F0=I A.( 错) &一个关系若是自反的，则必定不是反自反的，若是对称的，则必定不是反对称的。(错)

9、设A={a,b,c,d,e},R={,vb,a>,vc,d>,vd,c>}l A，则A/R={{a,b},{c,d}}。(对)

10、设A={1,2,3,4}, A—A 的函数f={v1,2>,v2,3>,v3,1>,<4,1>则f 的反函数不存在。(对)

离散数学期末考试试题(有几套带答案)

离散数学试题(A卷及答案）一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D

(7) R∨S 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明（1）?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍证明设 1 a，2a，…，1+m a为任取的m＋1个整数，用m去除它们所得余数只能是0，1，…，m－1，由抽屉原理可知， 1 a，2a，…，1+m a这m＋1个整数中至少存在两个数 s a和t a，它们被m除所得余数相同，因此s a和t a的差是m的整数倍。五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分）证明∵x∈ A-（B∪C）? x∈ A∧x?（B∪C）? x∈ A∧（x?B∧x?C）?（x∈ A∧x?B）∧（x∈ A∧x?C）? x∈（A-B）∧x∈（A-C）? x∈（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C）六、已知R、S是N上的关系，其定义如下：R={| x,y∈N∧y=x2}，S={| x,y∈N∧y=x+1}。求R-1、R*S、S*R、R{1,2}、S[{1,2}]（10分）解：R-1={| x,y∈N∧y=x2}，R*S={| x,y∈N∧y=x2+1}，S*R={| x,y∈N∧y=（x+1）2}，七、若f:A→B和g:B→C是双射，则（gf）-1=f-1g-1（10分）。证明：因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数

离散数学第五版模拟试题及答案

《离散数学》模拟试题3 一、填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A得幂集合p（A）=_____ _。 2. 设集合E ={a, b, c, d, e}, A= {a, b, c}, B = {a, d, e}, 则A∪B =___ ___， A∩B =____ __，A－B =___ ___，～A∩～B =____ ____。 3. 设A，B是两个集合，其中A= {1, 2, 3}, B= {1, 2}，则A－B =____ ___， ρ（A）－ρ（B）=_____ _ _。 4. 已知命题公式R Q P G→ ∧ ? =) (，则G的析取范式为。 5. 设P：2＋2＝4，Q：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化，其真值为。二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A、B是两个集合，A＝{1,3,4}，B＝{1,2}，则A－B为（）. A.{1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X＝{x, y}，则ρ（X）＝（）。 A. {{x},{y}} B. {φ,{x},{y}} C. {φ,{x},{y},{x, y}} D. {{x},{y},{x, y}} 4. 设集合A＝{1,2,3}，A上的关系R＝{(1,1),(2,2),(2,3),(3,3),(3,2)}，则R不具备（）. 三、计算题（共50分） 1. （6分）设全集E＝N，有下列子集：A＝{1，2，8，10}，B＝{n|n2<50 ，n∈N}，C＝ {n|n可以被3整除，且n<20 ，n∈N}，D＝{n|2i，i<6且i、n∈N}，求下列集合：（1）A∪(C∩D) （2）A∩(B∪(C∩D)) （3）B－(A∩C) （4）(～A∩B) ∪D 2. （6分）设集合A＝{a, b, c}，A上二元关系R1，R2，R3分别为：R1＝A×A， R2 ＝{(a，a)，(b，b)}，R3 ＝{(a，a)}，试分别用定义和矩阵运算求R1·R2 ，22R，R1·R2 ·R3 ， (R1·R2 ·R3 )－1 。 3.（6分）化简等价式（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）. 4.(8分) 设集合A＝{1,2,3}，R为A上的二元关系，且 M R＝写出R的关系表达式，画出R的关系图并说明R的性质. 5. （10分）设公式G的真值表如下. 试叙述如何根据真值表求G的主析取范式和主合取范式，并写出G的主析取范式和主合取范式. 1 0 0 1 1 0 1 0 0

离散数学期末试题

离散数学考试试题（A 卷及答案）一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不是上海人，也不是杭州人。王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？解设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有：甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。证明设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。

离散数学考试试题(A卷及答案)

离散数学考试试题（A卷及答案）一、（10分）证明?(A∨B)→?(P∨Q)，P，(B→A)∨?P A。证明：(1)?(A∨B)→?(P∨Q) P (2)(P∨Q)→(A∨B) T(1)，E (3)P P (4)A∨B T(2)(3)，I (5)(B→A)∨?P P (6)B→A T(3)(5)，I (7)A∨?B T(6)，E (8)(A∨B)∧(A∨?B) T(4)(7)，I (9)A∧(B∨?B) T(8)，E (10)A T(9)，E 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。请推出哪两个人参加了围棋比赛。解符号化命题，设A：甲参加了比赛；B：乙参加了比赛；C：丙参加了比赛；D：丁参加了比赛。依题意有， (1)甲和乙只有一人参加，符号化为A⊕B?(?A∧B)∨(A∧?B)； (2)丙参加，丁必参加，符号化为C→D； (3)乙或丁至多参加一人，符号化为?(B∧D)； (4)丁不参加，甲也不会参加，符号化为?D→?A。所以原命题为：(A⊕B)∧(C→D)∧(?(B∧D))∧(?D→?A) ?((?A∧B)∨(A∧?B))∧(?C∨D)∧(?B∨?D)∧(D∨?A) ?((?A∧B∧?C)∨(A∧?B∧?C)∨(?A∧B∧D)∨(A∧?B∧D))∧((?B∧D)∨(?B∧?A)∨(?D∧?A)) ?(A∧?B∧?C∧D)∨(A∧?B∧D)∨(?A∧B∧?C∧?D)?T 但依据题意条件，有且仅有两人参加竞赛，故?A∧B∧?C∧?D为F。所以只有：(A∧?B∧?C∧D)∨(A∧?B∧D)?T，即甲、丁参加了围棋比赛。三、（10分）指出下列推理中，在哪些步骤上有错误？为什么？给出正确的推理形式。 (1)?x(P(x)→Q(x)) P (2)P(y)→Q(y) T(1)，US (3)?xP(x) P (4)P(y) T(3)，ES (5)Q(y) T(2)(4)，I (6)?xQ(x) T(5)，EG 解 (4)中ES错，因为对存在量词限制的变元x引用ES规则，只能将x换成某个个体常元c，而不能将其改为自由变元。所以应将(4)中P(y)改为P(c)，c为个体常元。正确的推理过程为： (1)?xP(x) P (2)P(c) T(1)，ES (3)?x(P(x)→Q(x)) P (4)P(c)→Q(c) T(3)，US (5)Q(c) T(2)(4)，I (6)?xQ(x) T(5)，EG 四、（10分）设A＝{a，b，c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性。解设R＝{，，，}，则

计算机《离散数学》期中试卷答案

系专业年级班级学号姓名 ……………………装……………………订……………………线…………………… 泉州师院2009-2010学年度第一学期 2008级计算机《离散数学》期中试卷题序一二三四五总分成绩签名一、单项选择题:（20%，每空2分） 1．设A={a,{a}}，下列命题错误的是（ B ）。 A ．{a}P(A) B ．{a}P(A) C ．{{a}}P(A) D ．{{a}}P(A) 2、假定全集E ＝{1,2,3,4,5,6,7,8,9,10},A={3,4,5}，B ＝{2,3,4,7,8,9}，则A ∪B 的位串是（ D ）。 A ．01 B ．0011100000 C ．00 D ．00 3、下列文氏图阴影部分所表示的集合是( A )。 A. (A-(B ∪C))∪((B ∪C)-A) B. (A-(B ∩C))∪((B ∩C)-A) C. (A-(B ∩C))∪((B ∪C)-A) D. (A-(B ∪C))∪((B ∩C)-A) 4．设p ：你主修计算机科学，q ：你是新生， r ：你可以从校园网访问因特网。只有你主修计算机科学或不是新生，你才可以从校园网访问因特网。可符号化为( C )。 A ．r →p ∨q B ．r →p ∧q C ．r →p ∨q D ．r →p ∨q 5．下列是两个命题变元p ，q 的极小项是（ A ） A ．┐p ∧q B ．┐p ∨q C ．p ∧┐p ∧q D ．┐p ∨p ∨q 6、下列等值式不正确的是（ C ） A ．┐(x)A(x)┐A B ．(x)(B →A(x))B →(x)A(x) C ．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x) D ．(x)(y)(A(x)→B(y))( x)A(x)→(y)B(y) 7、若s={1,2,3,4}，S 上关系R 的关系图为：则R 具有（ B ）性质。 A 、自反性 B 、自反性、对称性 C 、反自反性、反对称性 D 、自反性、对称性、传递性 8．设A={a,b,c,d}，A 上的等价关系R={,,,}∪I A ，则对应于R 的A 的划分是（ D ） A ．{{a},{b,c},{d}} B ．{{a,b},{c},{d}} C ．{{a},{b},{c},{d}} D ．{{a,b},{c,d}} 9、设A={1，2，3}，则A 上的二元关系有（ C ）个。 A. 2 3 B. 3 2 C. D. 10．下列函数是双射的为（ A ），其中：I —整数集，E —偶数集， N —自然数集，R —实数集。 A. f : IE , f (x) = 2x B. f : NNN, f (n) = C. f : RI , f (x) = [x] D. f :IN, f (x) = | x | 二．填空题（20%，每题2分） 1．集合的表示法有列举法、描述法。。则设、 } {0 A 1 ==??????=∞ =I i i i A i i ,...,,,,,3211023．令p ：今天下雪了，q ：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为 p →q 。 4．复合命题(p →q)∨(p → q)是___ 永真____式（永真式或永假式或可满足式）。 5．令谓词P(x,y)表示”x 爱y ”,个体域是全世界所有人的集合，用P(x,y)、量词得分评卷人得分评卷人

离散数学试卷及答案一

一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，ο〉，Z是整数集，ο定义为xοxy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x

离散数学期末试题及答案完整版

离散数学期末试题及答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】

326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).

离散数学试卷及答案(2)

一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为；“虽然你努力了，但还是失败了”的翻译为。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为。 2、设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是。 3、设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是；是否有幂等性；是否有对称性。 7、4阶群必是群或群。 8、下面偏序格是分配格的是。

9、n 个结点的无向完全图K n 的边数为，欧拉图的充要条件是。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为。二、选择 20% （每小题2分） 1、在下述公式中是重言式为（） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（），成真赋值的个数为（）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产生的S S ?上一个划分共有（）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为