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

离散数学试题(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 的整数倍

证明 设1a ，2a ，…，1+m a 为任取的m ＋1个整数，用m 去除它们所得余数只能是0，1，…，m －1，由抽屉原理可知，

1a ，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=x 2

}，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=x 2

}，R*S={| x,y ∈N ∧y=x 2

+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有逆函数（gf）-1：C→A。同理可推f-1g-1：C→A是双射。

因为∈f-1g-1?存在z（∈g-1∧∈f-1）?存在z（∈f∧∈g）?∈gf?∈（gf）-1,所以（gf）-1=f-1g-1。

R{1,2}={<1,1>,<2,4>}，S[{1,2}]={1,4}。

八、（15分）设是半群，对A中任意元a和b，如a≠b必有a*b≠b*a，证明：

(1)对A中每个元a，有a*a＝a。

(2)对A中任意元a和b，有a*b*a＝a。

(3)对A中任意元a、b和c，有a*b*c＝a*c。

证明由题意可知，若a*b＝b*a，则必有a＝b。

(1)由(a*a)*a＝a*(a*a)，所以a*a＝a。

(2)由a*(a*b*a)＝(a*a)*(b*a)＝a*b*(a*a)＝(a*b*a)*a，所以有a*b*a＝a。

(3)由(a*c)*(a*b*c)＝(a*c*a)*(b*c)＝a*(b*c)＝(a*b)*c＝(a*b)*(c*a*c)＝(a*b*c)*(a*c)，所以有a*b*c＝a*c。

九、给定简单无向图G＝，且|V|＝m，|E|＝n。试证：若n≥21-m

C＋2，则G是哈密尔顿图

证明若n≥21-m

C＋2，则2n≥m2－3m＋6 （1）。

若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝∑

∈V

w

w

d)

(＜m＋(m－2)(m－3)＋m＝m2－3m＋6，与（1）矛

盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m，所以G是哈密尔顿图。

离散数学试题(B卷及答案）

一、证明题（10分）

1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T

证明左端?((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律) ? ((P∨Q)∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律) ? ((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R)) (等幂律) ?T (代入)

2)?x(P(x)→Q(x))∧?xP(x)??x(P(x)∧Q(x))

证明?x(P(x)→Q(x))∧?xP(x)??x((P(x)→Q(x)∧P(x))??x((?P(x)∨Q(x)∧P(x))??x(P(x)∧Q(x))??xP(x)∧?xQ(x)??x(P(x)∧Q(x))

二、求命题公式(?P→Q)→(P∨?Q) 的主析取范式和主合取范式（10分）

解：(?P→Q)→(P∨?Q)??(?P→Q)∨(P∨?Q)??(P∨Q)∨(P∨?Q)?(?P∧?Q)∨(P∨?Q) ?(?P∨P∨?Q)∧(?Q∨P∨?Q)?(P∨?Q)?M1?m0∨m2∨m3

三、推理证明题（10分）

1)(P→(Q→S))∧(?R∨P)∧Q?R→S

证明：（1）R 附加前提

(2)?R∨P P

(3)P T(1)(2),I

(4)P→(Q→S) P

(5)Q→S T(3)(4),I

(6)Q P

(7)S T(5)(6),I

(8)R→S CP

2) ?x(P(x)∨Q(x))，?x?P(x)??x Q(x)

证明：(1)?x?P(x) P

(2)?P(c) T(1),US

(3)?x(P(x)∨Q(x)) P

(4)P(c)∨Q(c) T(3),US

(5)Q(c) T(2)(4),I

(6)?x Q(x) T(5),EG

四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超

过1/8（10分）。

证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）

面积不超过小正方形的一半，即1/8。

五、已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) （10分）

证明：∵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）

六、π={A1，A2，…，A n}是集合A的一个划分，定义R={|a、b∈A i，I=1，2，…，n}，则R是A上的等价关系（15分）。

证明：?a∈A必有i使得a∈A i，由定义知aRa，故R自反。

?a,b∈A，若aRb ，则a,b∈A i，即b,a∈A i，所以bRa，故R对称。

?a,b,c∈A，若aRb 且bRc，则a,b∈A i及b,c∈A j。因为i≠j时A i∩A j=Φ，故i=j，即a,b,c∈A i，所以aRc，故R传递。

总之R是A上的等价关系。

七、若f:A→B是双射，则f-1:B→A是双射（15分）。

证明:对任意的x∈A，因为f是从A到B的函数，故存在y∈B，使∈f，∈f-1。所以,f-1是满射。

对任意的x∈A，若存在y1,y2∈B，使得∈f-1且∈f-1,则有∈f且∈f。因为f是函数，则y1=y2。所

以，f-1是单射。因此f-1是双射。

八、设是群，和是的子群，证明：若A∪B＝G，则A＝G或B＝G（10分）。

证明假设A≠G且B≠G，则存在a∈A，a?B，且存在b∈B，b?A（否则对任意的a∈A，a∈B，从而A?B，即A∪B＝B，得B＝G，

矛盾。）

对于元素a*b∈G，若a*b∈A，因A是子群，a-1∈A，从而a-1 * (a*b)＝b∈A，所以矛盾，故a*b?A。同理可证a*b?B，综合

有a*b?A∪B＝G。

综上所述，假设不成立，得证A＝G或B＝G。

九、若无向图G是不连通的，证明G的补图G是连通的（10分）。

证明设无向图G是不连通的，其k个连通分支为1G、2

G、…、k G。任取结点u、v∈G，若u和v不在图G的同一个连通分

支中，则[u，v]不是图G的边，因而[u，v]是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支i G（1

≤i≤k）中，在不同于i G的另一连通分支上取一结点w，则[u，w]和[w，v]都不是图G的边，，因而[u，w]和[w，v]

都是G的边。综上可知，不管那种情况，u和v都是可达的。由u和v的任意性可知，G是连通的。

一、选择题.(每小题2分，总计30)

1.给定语句如下：

（1）15是素数（质数）

（2）10能被2整除，3是偶数。

（3）你下午有会吗？若无会，请到我这儿来！

（4）2x+3>0.

（5）只有4是偶数，3才能被2整除。

(6)明年5月1日是晴天。

以上6个语句中，是简单命题的为（A）,是复合命题的为（B）,是真命题的为（C）,是假命题的是（D）,真值待定的命题是（E）

A: ①(1)(3)(4)(6) ②(1)(4)(6) ③(1)（6） B: ①(2)(4) ②(2)(4)(6) ③(2)(5)

C: ①(1)(2)(5)(6) ②无真命题③（5） D: ①(1)(2) ②无假命题③(1)(2)(4)(5)

E: ①(4)(6) ②（6）③无真值待定的命题

2.将下列语句符号化：

（1）4是偶数或是奇数。（A）设p：4是偶数，q：4是奇数

（2）只有王荣努力学习，她才能取得好成绩。（B ）设p ：王荣努力学习，q ：王荣取得好成绩 （3）每列火车都比某些汽车快。（C ）设F(x):x 是火车，G(y):y 是汽车，H(x,y):x 比y 快。 A: ① p ∨q ② p ∧q ③ p →q B: ① p →q ② q →p ③ p ∧q

C: ①?x ?y ((F(x) ∧G(y)) → (H(x,y))②?x (F(x) →?y (G(y)∧H(x,y)))③?x (F(x) ∧?y (G(y)∧H(x,y))) 3. 设S={1,2,3},下图给出了S 上的5个关系,则它们只具有以下性质:R 1是（A ）,R 2是(B),R 3是(C)。

A B C:①自反的，对称的，传递的 ②反自反的，对称的 ③自反的

④

反对称的 ⑤对称的 ⑥自反的，对称的，反对称的，传递的

4. 设S={Ф，{1}，{1，2}}，则有

（1）（A ）∈S （2） (B)?S

（3） P(S)有（C ）个元数。 （4）（D ）既是S 的元素，又是S 的子集 A: ① {1,2} ② 1 B: ③{{1,2}} ④{1} C: ⑤ 3 ⑥ 6 ⑦ 7 ⑧ 8 D: ⑨ {1} ⑩Ф

二、证明（本大题共2小题，第1小题10分，第2小题10分，总计20分） 1、用等值演算算法证明等值式 (p ∧q)∨(p ∧?q)?p 2、构造下面命题推理的证明

如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。

三、计算（本大题共4小题，第1小题5分，第2小题10分，第3小题15分， 总计30分） 1、设()(){}212,，，个体域为为，整除为

，求公式： ()()()()()x Q y x P y x →??,的真值。

2、设集合{}A A ,4,3,2,1=上的关系 {4,33,21,2,2,1,1,1=R ，求出它的自反闭包，对称闭包和传递闭包。

3、设

{},24,12,8,4,2,1=A 上的整除关系{}2

12121,,,a a A a a a a R 整除∈=，R 是否为A 上的偏序关系？若是，则：

1、画出R 的哈斯图；（10分）

2、求它的极小元，最大元，极大元，最大元。（5分） 四、用推导法求公式()()p q p →→的主析取范式和主合取范式。（本大题10分）

答案： 一、 选择题

1. A:③ B: ③ C:③ D:① E:②

2.A:① B: ② C:②

3.A:③ B: ④ C:⑥

4.A:① B: ③ C:⑧ D:⑩ 二、证明题

1. 证明 左边?（(p ∧q)∨p ）∧（(p ∧q)∨?q)） （分配律） ? p ∧（(p ∧q)∨?q)） (吸收律) ? p ∧（(p ∨?q) ∧ (q ∨?q)） （分配律） ? p ∧（(p ∨?q)∧1） （排中律）

? p ∧ (p ∨?q) （同一律） ? p （吸收律） 2.解：p ：今天是星期三。 q ：我有一次英语测验。 r ：我有一次数学测验。 s ：数学老师有事。

前提：p →(q ∨r) , s →?r , p ∧s 结论：q

证明：①p ∧s 前提引入

②p ①化简 ③p →(q ∨r) 前提引入 ④q ∨r ②③假言推理 ⑤s ①化简 ⑥s →?r 前提引入 ⑦?r ⑤⑥假言推理 ⑧q ④⑦析取三段论 推理正确。

三、计算

1. ()()()()()

()()()()()()()()

()()()()()()()()()()()()()()

,1,12,21,112,121,212,22x y P x y Q x y P y Q P y Q P Q P Q P Q P Q ??→??→Λ→?

→Λ→∨→Λ→

()()()()()()()()()()()()1,11,1,21,2,10,2,21,11,20110011101

P P P P Q Q ======∴?→Λ→∨→Λ→?

该公式的真值是1，真命题。

或者()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()T

T T F T T T F T F F T T T T Q P Q P Q P Q P x Q x P x Q x P x x Q y x P y x ?∧?∨∧∨?→∨→∧→∨→?→∨→∧→∨→?→∨→??→??22,221,212,111,12,1,,

2、{}4,4,3,,2,2,4,,3,2,1,22,1,1,1)

(=R r

{}3,4,2,,4,,3,21,2,2,1,1,1)(=R s

{}4,14,2,2,2,3,14,33,21,2,2,1,1,1)(=R t

3、（1） R 是

A 上的偏序关系。

（2）极小元、最小元是1,极大元、 最大元是24。 四、

()()()()

()()

()()()()()

2301p q p p q p p q p p

p q q p q p q →→???∨∨?∧?∨??∧∨??∧?∨∧?∴∑

∏，

主合取范式，

安徽大学2004-2005学年第二学期《离散数学》期末考试试卷（A 卷）参考答案

一、单项选择

1 在自然数集N 上，下列哪种运算是可结合的？（ ）

A. b a b a -=*

B. },max{*b a b a =

C. b a

b a 2*+= D. )3(mod *b a b a ?=

2 下列代数系统中，哪个是群？（ ）

A. }5,3,1,0{=S ，*是模7加法

B. Q S =（有理数集合）

，*是一般乘法 C. Z S

=（整数集合）

，*是一般减法 D. }9,5,4,3,1{=S ，*是模11乘法 3 若是的真子群，且

n H =，m G =，则有（ ）

。 A. n 整除m B. m 整除n

C. n 整除m 且 m 整除n

D. n 不整除m 且 m 不整除n 4 下面哪个集合关于指定的运算构成环？（ ）

A. },|2{3Z b a b a

∈+，关于数的加法和乘法

B.n {阶实数矩阵}，关于矩阵的加法和乘法

C. },|2{Z b a b a

∈+，关于数的加法和乘法

D. ??

?

???????∈?

??? ??Z b a a b b a ,，关于矩阵的加法和乘法 5 在代数系统中，整环和域的关系为（ ）。

A. 域一定是整环

B.域不一定是整环

C. 整环一定是域

D. 域一定不是整环

6 N 是自然数集，≤是小于等于关系，则),(≤N 是（ ）。

A. 有界格

B.有补格

C. 分配格

D. 有补分配格 7 图1-1给出的哈斯图表示的格中哪个元素无补元？（ ）

A. a

B. c

C. e

D.

f

图1-1

8 给定下列序列，可构成无向简单图的结点度数序列的是（ ）。

A.（1，1，2，2，3）

B.（1，3，4，4，5）

C.（0，1，3，3，3）

D.（1，1，2，2，2） 9 欧拉回路是（ ）。

A.路径

B.简单回路

C.既是基本回路也是简单回路

D.既非基本回路也非简单回路 10 哈密尔顿回路是（ ）。

A.路径

B.简单回路

C.既是基本回路也是简单回路

D.既非基本回路也非简单回路

二、填空题（以下每个下划线为一空，请按要求填入合适的内容。每空2分，共30分）。

1 设S 是非空有限集，代数系统） ,),((S P 中，)(S P 对 运算的单位元是＿＿＿＿，零元是＿＿＿＿，)(S P 对 运算的单位元是＿＿＿＿。

2 在运算表2-1中空白处填入适当符号，使)},,,({ c b a 成为群。 ①＿＿＿＿，②＿＿＿＿，③＿＿＿＿，④＿＿＿＿。

3 设}8,4,0{=H

，>+<12,H 是群>+<1212,N 的子群，其中

}11,,2,1,0{12???=N ，12+是模12加法，则>+<1212,N 有＿＿＿＿

个真子群，H 的左陪集=H

3＿＿＿＿，=H 4＿＿＿＿。

4设>-∧∨<,,,A 是一个布尔代数，如果在A 上定义二元运算⊕为：

)()(b a b a b a ∧∨∧=⊕，则>⊕<,A 是一个＿＿＿＿。

表2-1

5 任何一个具有n

2个元素的有限布尔代数都是＿＿＿＿。 6 若连通平面图G 有4个结点，3个面，则G 有＿＿＿＿条边。

7 一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，它有＿＿＿＿个度数为1的结点。 8 无向图G 是由k （2≥k

）棵数组成的森林，至少要添加＿＿＿＿条边才能使G 成为一棵树。

三、求解题（20分） 1 试写出>+<

66,N 中每个子群及其相应的左陪集。 （6分）

2 若一个有向图G 是欧拉图，它是否一定是强连通的？若一个有向图G 是强连通的，它是否一定是欧拉图？说明理由。 （6分）

3 有向图G 如图3-1所示。 （1）求G 的邻接矩阵

A ； （2分）

（2）G 中1v 到4v 长度为4的路径有几条？ （2分） （3）G 中1v 到自身长度为3的回路有几条？ （2分） （4）G 是哪类连通图？ （2分）

图3-1

四、证明题（30分）

1 设><,*G 是一群，G x ∈。定义：b x a b a **= ，G b a ∈?,。证明>< ,G 也是一群。

2 证明：（1）证明在格中成立：)(*)()*()*(d b c a d c b a ⊕⊕≤⊕。 （5分）

（2）证明布尔恒等式：)*()*()*()*()*(b a c a c b b a c a '⊕=⊕'⊕。 （5分）

7 4 v 3

e

3 证明：（1）在6个结点12条边的连通平面简单图中，每个面由3条边围成。 （5分）

（2）证明当每个结点的度数大于等于3时，不存在有7条边的简单连通平面图。

安徽大学2004-2005学年第二学期《离散数学》期末考试试卷（A 卷）参考答案

一、单项选择

1．B; 2.D; 3.A; 4.C; 5.A; 6.C; 7.B; 8.D; 9.B; 10.C. 二、填空题

1 Φ，S ，S ；

2 c ，b ，b ，a ；

3 5，}11,7,3{，}0,8,4{；

4 交换群；

5 同构；

6 5；

7 9；

8 1-k

。

三、求解题

1 解：子群有：>+<6

},0{，>+<6},3,0{，>+<6},4,2,0{。

>+<6},0{的左陪集为：}0{，}1{，}2{，}3{，}4{，}5{ >+<6},3,0{的左陪集为：}3,0{，}4,1{，}5,2{

>+<6},4,2,0{的左陪集为：}4,2,0{，}5,3,1{

2 答：（1）一个有向欧拉图一定是强连通图。因为G 是欧拉图，存在欧拉回路C ，G 中的每个结点至少在C 中出现一次。因而G 中任意两点u ，v 都在C 中，相互可达，故G 是强连通的。（2）一个强连通图不一定是有向欧拉图。因为强连通图中每个结点的入度不一定等于其出度。

3 解：

（1）?????????

???=0100

10000100

0121

A ???????

??

???=10000100

10001321

2A ???????

??

???=01001000

01003421

3A ?

?

??

?

?

?

??

???=10000100

10004621

4A

（2）由

4A 中44

14

=a 可知，1v 到4v 长度为4的路径有条（6411e e e e ，6764e e e e ，6521e e e e ，6531e e e e ）。 （3）由

3A 中13

11

=a 可知，1v 到自身长度为3的回路有1条（111e e e ）。 （4）G 是单向连通图。 四、证明题

1 证明：显然 是G 上的二元运算（即满足封闭性），要证G 是群，需证结合律成立，同时有单位元，每个元素有逆元。 G c b a ∈?,,，有

)()**(****)**()(c b a c x b x a c x b x a c b a === 运算是可结合的。 其次，1

-x

是>< ,G 的单位元。事实上，G a ∈?，有

a x x a x a ==--11** ；a a x x a x ==--**11

最后证明，G a ∈?，111

**---x a x

是a 在>< ,G 中的逆元。事实上，

1111111****)**(-------==x x a x x a x a x a 1111111****)**(-------==x a x x a x a x a x

由以上证明，>< ,G 是群。

2 证明：（1）))*((*))*(()*()*(d b a c b a d c b a ⊕⊕≤⊕ （公式(13)分配不等式） 又因为a b a ≤*，b b a ≤*，所以)(*)()*()*(d b c a d c b a ⊕⊕≤⊕。 （2）因为1='⊕a a ，)*()*(*1c b c b =，所以有，

))*(*)(()*()*()*()*()*(c b a a b a c a c b b a c a '⊕⊕'⊕=⊕'⊕ ))**()**(()*()*(c b a c b a b a c a '⊕⊕'⊕=

))**()*(())**()*((c b a b a b c a c a '⊕'⊕⊕= （吸收律） )*()*(b a c a '⊕=

即等式成立。

3 证明：（1）因图中结点数和边数分别为

6

=n ，

12=m ，根据欧拉公式2=+-k m n ，得8

=k 。又

∑==242)deg(m v i

，而简单连通平面图的每个面至少由3条边围成，所以在6个结点12条边的连通平面简单图中，每个

面由3条边围成。

（2）设),(m n 图为简单连通平面图，有k 个面。（反证法） 若7=m ，由欧拉公式知92=+=+m k n ，而每个面至少由3条边围成，有m k 23≤，则3

14

32=≤

m k ，且k 是整数，所以4≤k ；又对任结点V

v ∈，3)deg(≥v ，有m n 23≤，故3

14

32=≤

m n ，且n 是整数，所以4≤n 。这样就有844=+≤+k

n ，与9=+k n 矛盾，所以结论正确。

安徽大学2007— 2008学年第 2 学期 《离散数学（下）》考试试卷（A 卷）

一、单项选择题（每小题2分，共20分）

1. 下列集合关于数的加法和乘法运算不能构成环的是（ ）

A.自然数集合；

B.整数集合；

C.有理数集合；

D.实数集合。 2. 设I 为整数集合，则下列集合关于数的加法运算不能构成独异点的是（ ）

A.I ；

B.{2|}k k I ∈；

C.{21|}k

k I +∈； D.{35|,}m n m n I +∈。

3. 设6

{0,1,

,5}N =，6+为模6加法，则下列元素是66,N <+>的生成元的是（ ）

A.2；

B.3；

C.4；

D.5。

4. 设>?+<

,,F 是整环，则>?+<,,F 不一定是（ ）

A.可交换环；

B.无零因子环；

C.含么环；

D.域。 5. 格不一定具有（ ）

A.交换律；

B.结合律；

C.分配律；

D.吸收律。 6. 设{1,2,4,8}S

=，和*分别表示求最小公倍数和最大公约数运算，则,,S <*>是（ ）

A.有补格；

B.分配格；

C.有补分配格；

D.布尔代数。

7. 一个含4个结点的无向图中有3个结点的度数分别为1,2,3，则第4个结点的度数不可能是（ ）

A.0；

B.1；

C.2；

D.4。

8. 设连通的简单平面图G 中有10条边和5个面，则G 的结点数为（ ）

A.6；

B.7；

C.8；

D.9。

9. 设无向树T 中有1个结点度数为2，2个结点度数为3，3个结点度数为4，则T 中的树叶数为（ ）

A.10；

B.11；

C.12；

D.13。

10.设G 为连通的无向图，若G 仅有2个结点的度数是奇数，则G 一定具有（ ）

A 、欧拉路径；

B 、欧拉回路；

C 、哈密尔顿路径；

D 、哈密尔顿回路。 二、填空题（每小空2分，共20分） 1. 设R 为实数集合，{|01}S

x x R x =∈∧≤≤，则在代数,max S <>中，

S 关于max 运算的么元是＿ ＿＿，零元是＿ ＿＿。

2. 设10+为模10加法，则在10{0,1,

,9},<+>中，元素5的阶为 ，6的阶为＿ ＿＿。

3. 设110

{1,2,5,10,11,22,55,110}S =，gcd 和lcm 分别为求最大公约数和最小公倍数运算，

则在布尔代数110,gcd,lcm S <

>中，原子的个数为＿ ＿＿，元素22的补元为＿ ＿＿。

4. 在格,,L <*⊕>中，,a b L ?∈，a b ≤当且仅当a b *=＿ ＿＿当且仅当a b ⊕=＿ ＿＿。

5. 一个具有n 个结点的简单连通无向图的边数至少为＿ ＿＿，至多为＿ ＿＿。 三、解答题（第1小题12分，第2小题8分，共20分）

1. 设图G 如图1所示， (1) 求G 的邻接矩阵A ；

(2) 求

(2)(3)(4),,A A A ，说明从1v 到4v 的长为2,3,4的路径各有几条；

(3) 求G 的可达矩阵P ； (4) 求G 的强连通分图。 2. 求群88,N <

+>的所有子群及由元素5确定的各子群的左陪集，其中8{0,1,,7}N =???，8+是模8加法。

四、证明题（每小题10分，共40分）

1. 证明布尔恒等式：()()()()a b a c b c a b c ''*⊕*⊕*=*⊕。

2. 设R 为实数集合，+和?为数的加法和乘法运算，对,a b R ?∈，b a b a b a ?++=*，

证明：,R <

*>为独异点。

3. 证明：若),(m n 简单无向图G 满足)2)(1(2

1

-->

n n m ，则图G 是连通图。 4. 设,G <*>是一个群，a G ∈；定义一个映射

:f G G →，使得对于x G ?∈有1()f x a x a -=**；

证明：

f 是,G <*>

安徽大学2007— 2008学年第 2 学期 《离散数学（下）》考试试卷（A 卷）

一、单项选择题（每小题2分，共20分）

1.A ；

2.C ；

3.D ；

4.D ；

5.C ；

6.B ；

7.B ；

8.B ；

9.A ； 10.A 。 二、填空题（每小空2分，共20分）

1.0，1；

2.2，5；

3.3，5；

4.a ，b ；

5.1n -，(1)/2n n -。 三、解答题（第1小题12分，第2小题8分，共20分）

1. (1) G 的邻接矩阵0

1110

01001010

010A ??

?

?

= ?

?

??

； 2分

(2)

(2)

0121010100200

101A ?? ? ?= ?

???；(3)

222002002020

020A ??

?

?= ?

???；(4)

242020200400

202A ??

?

?

= ?

?

??

； 5分

从1v 到4v 的长为2,3,4的路径的条数分别为1,2,2； 8分

(3) G 的可达矩阵为0

1110

11101110111P ??

?

?

= ?

?

??

； 10分

(4) 因0000011101110

111T

P P ??

?

?

∧= ?

?

??

，故G 的强连通分图的结点集为1{}v ，234{,,}v v v 。 12分

2. 88,N <

+>的子群为：8{0},<+>，8{0,2,4,6},<+>，8{0,4},<+>，88,N <+>； 4分

元素5确定的各子群的左陪集对应为：{5}，{1,3,5,7}，{1,5}，8N 。 8分 四、证明题（每小题10分，共40分）

1. ()()()()(())a b a c b c a b a b c ''''*⊕*⊕*=*⊕⊕* 2分

()(())(()())(())a b a b c a b a b a b c ''=*⊕**=*⊕***⊕ 6分 1(())()a b c a b c =**⊕=*⊕。 10分

2. 因R 对+和?运算封闭，故R 对*运算封闭；对,,x y z R ?∈， 2分

xyz yz xz xy z y x z xy y x z xy y x z y x y x z y x ++++++=++++++=?++=)(*)(*)*(, xyz yz xz xy z y x yz z y x yz z y x z y z y x z y x ++++++=++++++=?++=)()(*)*(*

故()()x y z

x y z **=**，从而R 上的*运算满足结合律； 6分

因对x R ?∈，x x x x =?++=00*0，x x x x =?++=000*，故0为*运算的么元；

综合以上，*为R 上的可结合的二元运算，且R 关于*运算有么元，所以,R <*>为独异点。 10分

3. 假设G 有(2)k k ≥个连通分图，则因G 为简单无向图，故12()(1)m n k n k ≤--+， 4分

因为2k

≥，所以02n k n ≤-≤-，011n k n ≤-+≤-， 8分

所以1

12

2()(1)(1)(2)m n k n k n n ≤

--+≤--，这与1

2(1)(2)m n n >--矛盾！

所以图G 是连通图。 10分 4. 对12,x x G ?∈，若

12()()f x f x =，则1112a x a a x a --**=**，故12x x =，从而f

为单射； 3分

y G ?∈，1a y a G -**∈且1()f a y a y -**=，因此x G ?∈，使()f x y =，所以f

为满射； 6分

,x y G ?∈，111()()()()()()f x y a x y a a x a a y a f x f y ---*=***=*****=*，故f

为同态； 9分

所以

f 是,G <*>的群自同构。 10分

离散数学复习题及答案

1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨) ()(Q P Q P Q P ?∧?∨∧??Q) P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)() ()(R P Q P ∨∧∧?

①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q 7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥x 。 答案： 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??

离散数学期末试题

离散数学考试试题（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 。

《 离散数学》期中考试试卷(2006—2007学年第2学期)

《离散数学J》考试试卷（期中） 课程代码143140320命题单位学院：计算机学院信息教研室 学院:_______________班级:_____________姓名:_______________学号:____________ 1．将下列命题将其符号化。（4分） ①.李平不是不聪明，而是不用功。 假设p:李平聪明，q:李平用功 ②.如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。 假设p：我懂得希腊文，q：我了解柏拉图 2．在一阶逻辑中将下列命题符号化。（9分） ①.整数都是有理数，并不是每个有理数一定是整数，有些有理数不是整数。 假设I(x)：x是整数，Q(x)：x是有理数。 ②.某些汽车比所有的火车慢。 假设F(x)：x是火车。G(x)：y是汽车。H(x,y)：x比y快 ③.谁要是游戏人生，他就一事无成；谁不能主宰自己，他就是一个奴隶。 假设：M(x)表示“x是人”，K(x)表示“x游戏人生”，L(x)表示“x 一事无成”，H(x,y)表示“x主宰y”，N(x)表示“x是奴隶”。 3．试证明： (┐P∧(┐Q∧R))∨((Q∧R)∨(P∧R))=R(10分) 4．求公式G＝(P→Q)∧R的主析取范式和主合取范式。(12分) 5．先将些列论断符号化，再证明论断的正确性。（15分） 所有的大一学生都要学习英语；并非所有的大一学生都要学习离散数学；故有些学习英语的不学习离散数学。 假设谓词如下：P(x)：x是大一学生；Q(x)：x要学习英语； R(x)：x要学习离散数学。 6．某班学生50人，会排球的有40人，会篮球的35人，会足球的10人，以上三种运动都会的5人，都不会的没有，问只会两种运动的有几人？

离散数学复习题参考带答案

一、选择题：（每题2’） 1、下列语句中不是命题的有（ ）。 A ．离散数学是计算机专业的一门必修课。 B ．鸡有三只脚。 C ．太阳系以外的星球上有生物 。 D ．你打算考硕士研究生吗? 2、命题公式A 与B 是等价的，是指（ ）。 A ． A 与B 有相同的原子变元 B ． A 与B 都是可满足的 C ． 当A 的真值为真时，B 的真值也为真 D ． A 与B 有相同的真值 3、所有使命题公式P∨(Q∧?R)为真的赋值为（ ）。 A ． 010，100，101，110，111 B ． 010，100，101，111 C ． 全体赋值 D ． 不存在 4、合式公式 (P∧Q)R 的主析取范式中含极小项的个数为（ ）。 A ．2 B ．3 C ．5 D ．0 5、一个公式在等价意义下，下面哪个写法是唯一的（ ）。 A ．析取范式 B ．合取范式 C ．主析取范式 D ．以上答案都不对 6、下述公式中是重言式的有（ ）。 A ．(P ∧Q) (P ∨Q) B ．(P Q) (( P Q)∧(Q P)) C ．(P Q)∧Q D ．P (P ∧Q) 7、命题公式 (P Q) ( Q ∨P) 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0 B ．1 C ．2 D ．3 8、若公式 (P∧Q)∨(P∧R) 的主析取范式为 m 001∨m 011∨m 110∨m 111 则它的主合取范式为（ ）。 A ．m 001∧m 011∧m 110∧m 111 B ．M 000∧M 010∧M 100∧M 101 C ．M 001∧M 011∧M 110∧M 111 D ．m 000∧m 010∧m 100∧m 101 9、下列公式中正确的等价式是（ ）。 A ．(x)A(x) ( x)A(x) B ．(x) (y)A(x, y) (y) (x) A(x, y) C ．(x)A(x) (x)A(x) D ．(x) (A(x) ∧B(x)) ( x) A(x) ∨(x) B(x) 10、下列等价关系正确的是（ ）。 A ．x ( P(x) ∨Q(x) ) x P(x) ∨x Q(x) B ．x ( P(x) ∨Q(x) ) x P(x) ∨x Q(x) C ．x ( P(x) Q ) x P(x) Q D ． x ( P(x) Q ) x P(x) Q 11、设个体域为整数集，下列真值为真的公式是（ ）。 A ．x y （x·y=1） B ．x y （x·y=0） C ． x y （x·y=y） D ．x y （x+y=2y ） 12、设S={,{1},{1,2}}，则有（ ）S 。 A ．{{1,2}} B ．{1,2 } C ．{1} D ．{2} 13、下列是真命题的有（ ）。 A ．{a}{{a}} B ．{{}}{,{}} C ．{,{}} D ．{}{,{}}

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

离散数学期末试题及答 案 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的补元( ).

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

系 专业 年级 班级 学号 姓名 ……………………装……………………订……………………线…………………… 泉州师院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)、量词 得 分 评卷人 得 分 评卷人

离散数学课后习题答案(左孝凌版)

离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。

R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解：

【浙江工商大学】《离散数学》期末考试题(B)

《离散数学》期末考试题(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 是欧拉图. 二、单选题(每小题3分，共15分) 1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数，则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”. 1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( )

河海大学文天学院09级离散数学期中考试试卷答案

2010-2011学年第一学期离散数学期中考试试卷答案 一、（本题满分12分）在命题逻辑中将下列命题符号化。 （1）小王边走路边听音乐。（2）除非a能被2整除，a才能被4整除。 （3）派小张、小李中的一人去开会。（4）小张和小李是同学。 （5）今天是星期一仅当明天是星期二。（6）若2+2≠4，则3+3≠6；反之亦然。 解：（1）令p：小王走路；q：小王听音乐。符号化为p∧q （2）令p：a能被2整除；q：a能被4。符号化为q→p （3）令p：派小张去开会；q：派小李去开会。符号化为（p∧┐q）∨（┐p∧q） （4）令p：小张和小李是同学。符号化为p （5）令p：今天是星期一；q：明天是星期二。符号化为p→q （6）令p：2+2=4；q：3+3=6。符号化为┐p?┐q 二、（本题满分12分）在一阶逻辑中将下列命题符号化。 （1）有的有理数能被2整除。（2）没有不犯错误的人。 （3）人都不一样高。（4）说火车比汽车跑的快是不对的。 （5）4>2与3≥1互为充要条件。（6）除非李键是东北人，否则他一定怕冷。解：（1）令F(x)：x为有理数；G(x)：x能被2整除。符号化为?x(F(x)∧G(x)) （2）令F(x)：x是人，G(x)：x犯错误，则命题符号化为：?x（F（x）→G(x)） （3）令F(x)：x是人；H(x,y)：x与y一样高。符号化为?x?y（F（x）∧F（y）→┐H（x，y））（4）令F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快，┐?x?y（F（x）∧G（y）→H（x，y））（5）令F(x,y)：x>y，G(x,y):x≥y，a:4，b:2，c:3，d:1。符号化为F(a,b)?G(c,d) （6）令F(x)：x是东北人，G(x)：x怕冷，a：李键，符号化为┐G（a）→F（a） 三、（本题满分8分）给出公式(q →r) ∧ ( p→p)的真值表并求出成真赋值和成假赋值。解：真值表如下 成真赋值：000、001、011、100、101、111；成假赋值：010、110 四、（本题满分10分）设p:2能整除5，q:太阳从西方升起，r:一年分四季。求下列复合命题的真值： （1）((p ∨q) → r)∧(r→ (p ∧q)) （2）((┐q ?p) → (r ∨p)) ∨ ((┐p ∧┐q) ∧r) 解：由题意，p、q、r的真值分别为0、0、1。（1）的真值为0；（2）的真值为1。 五、（本题满分12分）使用等值演算法判断公式下列公式的类型。

离散数学课后习题答案第二章

第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为) ?，在（a）中为假命题，在(b)中为真命题。 (x xF (2)在两个个体域中都解释为) (x ?，在（a）(b)中均为真命题。 xG 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) x x∧ ? ?? F ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) x F H x→ ?? (x ) ( ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F x G y x→ ? ? y ∧ )) ( , ( ) x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) y x F G y→ ?? ∧ ? x ( ) ( , H ( x ) (y ( 9.给定解释I如下: (a) 个体域D为实数集合R.

离散数学期末考试试题及答案

离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ

（2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={| x,ｙN∧y=ｘ2} R*S＝｛| x，y N∧y＝x２+1} Ｓ*R=｛<ｘ,y>| x,ｙN∧y=(x＋1)２},R{1，２}＝{＜1，1>，＜2，４>｝,Ｓ[{1,2}]={1,4}。 七、设Ｒ={<ａ，b>,,＜c，ａ>}，求ｒ(R)、s(Ｒ)和t(Ｒ) （１5分）。 解：r(R）=｛,，,,<ｂ,b＞，｝

离散数学期末试卷A卷及答案

《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???.

2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？

离散数学部分答案

第十四章部分课后习题参考答案 5、设无向图G 有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G 至少有多少个顶点？在最少顶点的情况下，写出度数列、)()(G G δ、?。 解：由握手定理图G 的度数之和为：20102=? 3度与4度顶点各2个，这4个顶点的度数之和为14度。 其余顶点的度数共有6度。 其余顶点的度数均小于3，欲使G 的顶点最少，其余顶点的度数应都取2, 所以，G 至少有7个顶点, 出度数列为3,3,4,4,2,2,2,2)(,4)(==?G G δ. 7、设有向图D 的度数列为2，3，2，3，出度列为1，2，1，1，求D 的入度列，并求)(),(D D δ?， )(),(D D ++?δ,)(),(D D --?δ. 解：D 的度数列为2，3，2，3，出度列为1，2，1，1，D 的入度列为1,1,1,2. 2)(,3)(==?D D δ,1)(,2)(==?++D D δ,1)(,2)(==?--D D δ 8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？ 解：由握手定理图G 的度数之和为：1262=? 设2度点x 个，则1221513=+?+?x ，2=x ，该图有4个顶点. 14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。 (1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解：(1) 2+2+3+3+4+4+5=23 是奇数，不可图化； (2) 2＋2+2+2+3+3+4+4=16, 是偶数，可图化； 18、设有3个4阶4条边的无向简单图G 1、G 2、G 3，证明它们至少有两个是同构的。 证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列为2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1对应的图不是简单图。所以

离散数学期末考试试题及答案

离散数学试题(B卷答案1） 一、证明题（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 P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4)， I (6) C∨D P (7) R∨S T(5)，I 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P

离散数学期末试卷及答案

一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法构成环。( ) 8．若无向连通图G中有桥，则G的点连通度和边连通度皆为1。( ) 9．设A={a,b,c},则A上的关系R={,}是传递的。( ) 10．设A、B、C为任意集合，则A?(B?C)=(A?B)?C。( ) 二、填空题（共10题，每题3分，共30分） 11．设p：天气热。q：他去游泳。则命题“只有天气热，他才去游泳”可符号 化为。 12．设M(x)：x是人。S(x)：x到过月球。则命题“有人到过月球”可符号 化为。 13．p?q的主合取范式是。 14．完全二部图K r,s（r < s）的边连通度等于。 15．设A={a,b}，,则A上共有个不同的偏序关系。 16．模6加群中，4是阶元。 17．设A={1,2,3,4,5}上的关系R={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>}，则R的传递闭包t(R) = 。. 18．已知有向图D的度数列为(2,3,2,3)，出度列为(1,2,1,1)，则有向图D的入度

列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{,}，则R是A上的等价关系。求等价类[a]R、[c]R及商集A/R。 24．求图示带权图中的最小生成树，并计算最小生成树的权。 25．设R*为正实数集，代数系统< R*,+>、< R*,·>、< R*,/>中的运算依次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群？是群者，求其单位元及每个元素的逆元。 四、证明题（共3小题，共20分） 26 （8分）在自然推理系统P中构造下述推理的证明： 前题：p→(q∨r)，?s→?q，p∧?s 结论：r 27 （6分）设是群，H={a| a∈G∧?g∈G，a*g=g*a},则是G的子群 28．（6分）设G是n(≥3)阶m条边、r个面的极大平面图，则r=2n-4。

离散数学复习题参考带答案

. 一、选择题：（每题2’） 1、下列语句中不是命题的有（）。 A．离散数学是计算机专业的一门必修课。B．鸡有三只脚。 C．太阳系以外的星球上有生物。D．你打算考硕士研究生吗? 2、命题公式A与B是等价的，是指（）。 A．A与B有相同的原子变元B．A与B都是可满足的 C．当A的真值为真时，B的真值也为真D．A与B有相同的真值 3、所有使命题公式P∨(Q∧?R)为真的赋值为（）。 A．010，100，101，110，111 B．010，100，101，111 C．全体赋值D．不存在 4、合式公式?(P∧Q)→R的主析取范式中含极小项的个数为（）。 A．2 B．3 C．5 D．0 5、一个公式在等价意义下，下面哪个写法是唯一的（）。 A．析取范式B．合取范式C．主析取范式D．以上答案都不对 6、下述公式中是重言式的有（）。 A．(P∧Q) → (P∨Q) B．(P?Q) ? (( P→Q)∧(Q→P)) C．?(P →Q)∧Q D．P →(P∧Q) 7、命题公式(?P→Q) →(?Q∨P)中极小项的个数为（），成真赋值的个数为（）。 A．0 B．1 C．2 D．3 8、若公式(P∧Q)∨(?P∧R) 的主析取范式为m001∨m011∨m110∨m111则它的主合取范式为（）。 A．m001∧m011∧m110∧m111B．M000∧M010∧M100∧M101 C．M001∧M011∧M110∧M111D．m000∧m010∧m100∧m101 9、下列公式中正确的等价式是（）。 A．?(?x)A(x) ? (?x)?A(x) B．(?x) (?y)A(x, y) ? (?y) (?x) A(x, y) C．?(?x)A(x) ? (?x)?A(x) D．(?x) (A(x) ∧B(x)) ? (?x) A(x) ∨(?x) B(x) 10、下列等价关系正确的是（）。 A．?x ( P(x) ∨Q(x) ) ??x P(x) ∨?x Q(x) B．?x ( P(x) ∨Q(x) ) ??x P(x) ∨?x Q(x) C．?x ( P(x) →Q ) ??x P(x) → Q D．?x ( P(x) →Q ) ??x P(x) → Q 11、设个体域为整数集，下列真值为真的公式是（）。 A．?x?y（x·y=1）B．?x?y（x·y=0）C．?x?y（x·y=y）D．?x?y（x+y=2y） 12、设S={?,{1},{1,2}}，则有（）?S。 A．{{1,2}} B．{1,2 } C．{1} D．{2} 13、下列是真命题的有（）。 A．{a}?{{a}} B．{{?}}∈{?,{?}} C．?∈{?,{?}} D．{?}∈{?,{?}} 14、设S={?,{1},{1,2}}，则2S有（）个元素。 A．3 B．6 C．7 D．8

《离散数学》期末考试试题

《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。

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

泉州师院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 ．1000000001 B ．0011100000 C ．0111001110 D ．0111101110 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. 23 B. 32 C. 3 32 ? D. 2 23 ? 10．下列函数是双射的为（ A ），其中：I —整数集，E —偶数集， N —自然数集，R —实数集。 A. f : I →E , f (x) = 2x B. f : N →N ?N, f (n) = C. f : R →I , f (x) = [x] D. f :I →N, f (x) = | x | 二．填空题（20%，每题2分） 1．集合的表示法有 列举法、描述法 。 。则设、 } {0 A 1 ==??????=∞ = i i i A i i ,...,,,,,3211023．令p ：今天下雪了，q ：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为 p →?q 。