离散数学期末复习题
淮海工学院2011-2012-2离散数学期末复习题答案
一、选择题（每题3分）
1、下列句子中哪个不是命题？ ( C )
A 、你通过了离散数学考试
B 、我俩五百年前是一家
C 、 我说的是真话
D 、 淮海工学院是一座工厂
2、下列联接词运算不可交换的是( C )
A 、∧
B 、∨
C 、 →
D 、 ?
3、命题公式P Q ?→不能表述为( B )
A 、P 或Q
B 、非P 每当Q
C 、非P 仅当Q
D 、除非P ，否则Q
4、 下列公式中为永真式的是 ( C )
A 、()P P Q →∧
B 、()P P Q ?→∧
C 、()P Q Q ∧→
D 、()P Q Q ∨→
5、 下列公式中为非永真式的是( B )
A 、 ()P P Q ∧?→
B 、()P P Q ∨?→
C 、()P P Q ∧?→
D 、()P P Q ∨?→
6、设个体域{,}A a b =，则谓词公式(()())x F x G x ?∧消去量词后，可表示为为（ C ）
A 、(()())(()())F a F b G a G b ∧∨∧
B 、(()())(()())F a F b G a G b ∨∧∨
C 、(()())(()())F a G a F b G b ∧∨∧
D 、(()())(()())F a G a F b G b ∨∧∨
7、设个体域{,}A a b =，则谓词公式(),x yR x y ??去掉量词后，可表示为（ D ）
A 、()()()(),,,,R a a R a b R b a R b b ∧∧∧
B 、()()()(),,,,R a a R a b R b a R b b ∨∨∨
C 、()()()()()()
,,,,R a a R a b R b a R b b ∧∨∧ D 、()()()()()()b b R a b R b a R a a R ,,,,∨∧∨
8、设D ：全总个体域，()H x ：x 是人， ()P x ：x 犯错误，
则命题“没有不犯错误的人”的逻辑符号化为（ D ）
A 、(()())x H x P x ?∧
B 、(()())x H x P x ?→
C 、(()())x H x P x ?∧
D 、(()())x H x P x ?→
9、设D ：全总个体域，()F x ：x 是花，()M x ：x 是人，(,)H x y ：x 喜欢y ， 则命题“有的人喜欢所有的花”的逻辑符号化为（ D ）
A 、(()(()(,))x M x y F y H x y ?∧?→
B 、(()(()(,))x M x y F y H x y ?∧?→
C 、 (()(()(,))x M x y F y H x y ?∧?→
D 、(()(()(,))x M x y F y H x y ?∧?→
10、设?为空集，则下列为假命题的是（ A ）
A 、?∈?
B 、???
C 、{}?∈?
D 、{}???
11、设,a b 各不相同，则下述等式为真的是（ D ）
A 、{,}{{},{}}a b a b =
B 、{,}{{,}}a b a b =
C 、{{}{}}{,}a b a b =
D 、{{}{}}{{,}}a b a b =
12、 设集合{0,}A =?，?为空集， ()A ρ为A 的幂集，则下列为假命题的是（ B ）
A 、()A ρ?∈
B 、0()A ρ∈
C 、{}()A ρ?∈
D 、{0}()A ρ∈
13、 设集合{0,}A =?，?为空集， ()A ρ为A 的幂集，则下列为假命题的是（ B ）
A 、()A ρ??
B 、{0}()A ρ?
C 、{}()A ρ??
D 、{{0}}()A ρ?
14、非空集合X 上的空关系?不具备的性质是（ A ）
A 、自反性
B 、反自反性
C 、对称性
D 、传递性
10、设{1,2,3}A =上的关系R 的关系图如下，则R 不具备的性质为（ A ）
A 、自反性
B 、反自反性
C 、反对称性
D 、传递性
15、{1,2,3,4}A =上的关系{}1,3,1,4,2,3,2,4,3,4R =<><><><><>只不具备（ C ）
A 、 反自反性
B 、 反对称性
C 、对称性
D 、传递性
16、设R 为{1,2,3}A =上的关系，其关系图如下，则下列为真命题的是（ C ）
A 、R 对称，但不反对称
B 、R 反对称，但不对称
C 、R 对称，又反对称
D 、R 不对称，也不反对称
17、设R 为{1,2,3,4}A =上的关系，其关系图如下，则下列为假命题的是（ C ）
A 、R 不自反，也不反自反
B 、R 不对称，也不反对称
C 、R 传递
D 、R 不传递
18、设{ 1, 2, 3 }A =，则A 上不同等价关系的个数为（ C ）
A 、3
B 、4
C 、5
D 、6
19、设{ 1, 2, 3, 4 }A =，则A 上不同等价关系的个数为（ C ）
A 、13
B 、14
C 、15
D 、16
20、设R Z 、分别为实数集、整数集，则下列函数为满射而非单射的是（ C ）
A 、:,
()6f R R f x x →=+ B 、2:,()(6)f R R f x x →=+ C 、:,
()[]f R Z f x x →= D 、6:,()6f R R f x x x →=+ 21、设R R Z +、、分别为实数集、非负实数集、正整数集，下列函数为单射而非满射的是（ B ） A 、2:,
()71f R R f x x x →=-+- B 、x x f R Z f ln )(,:=→+； C 、:,()f R R f x x →= D 、:,
()71f R R f x x →=+ 22、设3,4X Y ==，则从X 到Y 可以生成不同的单射个数为（ B ）．
A 、12
B 、24
C 、64
D 、81
23、设3,2X Y ==，则从X 到Y 可以生成不同的满射个数为（ B ）．
A 、6
B 、8
C 、9
D 、64
24、设集合A 的幂集为()A ρ，-? 、
、、为集合的交、并、差、笛卡尔乘积运算，则下列系统中是代数系统的为（ D ）
A 、()A ρ ,
B 、()A ρ ,
C 、(),A ρ-
D 、(),A ρ?
25、在自然数集上定义的下列四种运算，其中满足结合律的是（C ）
A 、a b a b *=-
B 、||a b a b *=-
C 、max{,}a b a b *=
D 、2a b a b *=+
26、设k N 为前2k ≥个自然数集，k +表示模k 加法，对代数系统k k A N =+,，有（ A ）
A 、0是么元，无零元
B 、1是么元，无零元
C 、无么元，0是零元
D 、无么元，无么元
27、设k N 为前2k ≥个自然数集，k ?表示模k 乘法，对代数系统k k A N =?,，有（ B ）
A 、1是么元，无零元
B 、1是么元，0是零元
C 、无么元，0是零元
D 、无零元，无么元
28、设非空有限集S 的幂集为()S ρ，对代数系统()A S ρ=
,，有（ B ） A 、Φ是么元，S 是零元 B 、Φ是零元，S 是么元 C 、唯一等幂元 D 、无等幂元
29、设非空有限集S 的幂集为()S ρ，对代数系统()A S ρ= ,，有（ A ） A 、Φ是么元，S 是零元 B 、Φ是零元，S 是么元 C 、唯一等幂元 D 、无等幂元
30、设Z 是由所有整数组成的集合，对于下列*运算，代数系统
A 、a *b=a b
B 、a *b=a
C 、a *b=a+ab
D 、a *b=max(a ,b )
31、任意具有多个等幂元的半群，它（A ）
A 、不能构成群
B 、不一定能构成群
C 、能构成群
D 、能构成阿贝尔群
32、下列命题正确的是（ B ）
A 、简单回路必为基本回路
B 、基本回路必为简单回路
C 、简单回路必不是基本回路
D 、基本回路必不是简单回路
33、欧拉回路是（ B ）
A 、路径
B 、简单回路
C 、既是基本回路也是简单回路
D 、既非基本回路也非简单回路
34、哈密尔顿回路是（ C ）
A 、路径
B 、简单回路
C 、既是基本回路也是简单回路
D 、既非基本回路也非简单回路
35、在任何有向图中，下列命题正确的是（ C ）
A 、任意顶点的入度与出度都相等
B 、任意顶点的入度与出度都不相等
C 、所有顶点的入度之和与出度之和都相等
D 、所有顶点的入度之和与出度之和都不相等
36、设有向线图G 的顶点集12{,,,}n V v v v = ，邻接矩阵()ij n n A a ?=，则d e g ()i v -=（ D ）
A 、ii a
B 、1n ii i a
=∑ C 、1n ij j a =∑ D 、1n ji j a =∑
37、设有向线图G 的顶点集12{,,,}n V v v v = ，邻接矩阵()ij n n A a ?=，则d e g ()i v +=（ C ）
A 、ii a
B 、1n ii i a
=∑ C 、1n ij j a =∑ D 、1n ji j a =∑
38、在有n 个结点的简单无向图中，其边数（ C ）
A 、 最多有n-1条
B 、至少有n-1条
C 、最多有(1)2n n -条
D 、至少有(1)2
n n -条 39、在有n 个结点的简单有向图中，其边数（ C ）
A 、 最多有n-1条
B 、至少有n-1条
C 、最多有(1)n n -条
D 、至少有(1)n n -条
40、在有n 个结点的连通图中，其边数（ B ）
A 、 最多有n-1条
B 、至少有n-1条
C 、最多有n 条
D 、至少有n 条
41、设{,{1},{1,3},{1,2,3}}A =?，则A 上包含关系“?”的哈斯图为（ C ）
42、集合{ 1, 2, 3,4 }A =上的偏序关系图为
则它的哈斯图为（ A ）
43、下列哪一种图不一定是树（ C ）
A 、无简单回路的连通图
B 、 有n 个顶点n-1条边的连通图
C 、每对顶点间都有通路的图
D 、连通但删去一条边便不连通的图
44、设G 是有5个结点的无向完全图，则从G 中删去（ C ）条边可以得到树
A 、 4
B 、5
C 、6
D 、10
1、当赋予极小项足标相同的指派时，该极小项的真值为1，当赋予极大项足标相同的指派时，该极大项的真值为0.
2、任意两个不同极小项的合取式的真值为0，而全体极小项的析取式的真值为1.
3、任意两个不同极大项的析取式的真值为1，而全体极大项的合取式的真值为0.
4、n 个命题变元可构造包括F 的不同的主析取范式类别为22n .
5、n 个命题变元可构造包括T 的不同的主合取范式类别为22n .
6、若已证()xA x ?为真，则可假设某一确定的个体y 使()A y 为真，此推理规则被称为ES ．
7、令Γ是公理与前提的合取，Γ中无x 的自由出现，若从Γ可推出()A x ，则从Γ也可推出()xA x ?，此推理规则被称为UG ．
8、()ρ?={}?，(())ρρ?={,{}}??， (({}))ρρΦ={,{},{{}},{,{}}}?????．
9、()ρ?-?={}?，(())()ρρρ?-?={{}}?．
10、设{}A a =，则()()A A ρρ?= {},,,,,,,a A A A <>．
11、设集合,A B 分别含有,m n 个不同元素，则A B ?的基数为mn ，()A B ρ?的基数为2mn ， 12、()A B ρ?的基数为2n m ，()A B ρ?的基数为2m n ，()()A B ρρ?的基数为2m n +．
13、设{ 1,2,3,4,6,8,12,24 }A =，“≤”为A 上整除关系，则偏序集,A <≤>的极小元为1，最小元为1，极大元为24、最大元为24．
14、设{ 2,3,4,6,8,12 }A =，“≤”为A 上整除关系，则偏序集,A <≤>的极小元为2,3，最小元为无，极大元为8,12，最大元为无，既非极小元也非极大元的是4,6．
15、设,X m Y n ==，则从X 到Y 有2mn 种不同的二元关系，有m n 种不同的函数． 16、在一个有n 个元素的集合上，可以有22n 种不同的二元关系，有n n 种不同的函数， 有!n 种不同的双射．
17、设A={2,4,6}，A 上*为：a*b=max{a,b}，则在代数系统
18、设A={3,6,9}，A 上*为：a*b=min{a,b}，则在代数系统
19、设〈G,*〉是一个群，则
(1) 若a,b,x ∈G ，a *x=b ，则x= a *-1b ；(2) 若a,b,x ∈G ，a *x=a *b ，则x= b ．
20、群
21、设a 是12阶群的生成元， 则2a 是6阶元素，3a 是4阶元素．
22、设a 是10阶群的生成元， 则4a 是5阶元素，3a 是10阶元素．
23、在一个群〈G ,*〉中，若G 中的元素a 的阶是k ，则1a -的阶是k ．
24、n 阶无向完全图Kn 的边数是(1)2
n n -，每个结点的度数是1n -． 25、设有向图G = < V ，E >，1234{,,,}V v v v v =的邻接矩阵0101101111001
000A ?? ? ?= ? ???
， 则1v 的入度1deg ()v -= 3 ，4v 的出度4deg ()v +=1 ． 26、设无向图G 有18条边且每个顶点的度数都是3，则图G 有12个顶点．
27、一棵无向树的顶点数为n ，则其边数为n-1 ，其结点度数之和是2n-2.
28、设T=〈V ,E 〉是一棵树，若|V|>1，则T 中至少存在2片树叶.
1、若个体域{1,3,6}D =-，()S x ：3x >，()Q x ：5x =,a ：3，P :53>， 则谓词公式(()())x S x Q a P ?→∧为真吗？为什么？
答：为真；
(()())(((1)())((3)())((6)()))1x S x Q a P S Q a S Q a S Q a ?→∧?-→∨→∨→∧
((00)(00)(10))1(110)11?→∨→∨→∧?∨∨∧?.
2、谓词公式(,)(,)x yP x y y xP x y ??→??为真吗？为什么？
答：不为真；设个体域D ：实数域，(,)P x y ：0x y +=，
则(,)(,)100x yP x y y xP x y ??→???→?.
3、设{}1,2,3A =，问A 上存在一个既不是自反又不是反自反的关系吗？为什么？ 答：存在；如{}1,1,1,2R =<><>．
4、设{}1,2,3A =，问A 上存在一个既不是对称又不是反对称的关系吗？为什么？ 答：存在；如{}1,2,1,3,2,1R =<><><>．
5、设{}1,2,3A =，问A 上存在一个既是对称又是反对称的关系吗？为什么？
答：存在；如{}1,1,2,2,3,3R =<><><>．
6、设{234}A =，，
，}12,10742{，，，=B ，从A 到B 的关系 },,,{b a B b A a b a R 整除且∈∈><=，试给出R 的关系图和关系矩阵，并说明此关系R 及其逆关系1R -是否为函数？为什么？
解：}12,4,4,4,12,3,12,2,10,2,4,2,2,2{><><><><><><><=R ，则R 的关系图为：
R 的关系矩阵为 110110*********R M ????=?????? 关系R 不是A 到B 的函数，
因为元素2，4的象不唯一 逆关系1R -也不是B 到A 的函数
因为元素7的象不存在．
7、设Z 为整数集，函数f ：Z Z Z ?→，且(,)f x y x y =+，问f 是单射还是满射？ 为什么？并求(,),f x x (,)f x x -．
解：x Z ?∈, 0,x Z Z ?<>∈?，总有(0,)f x x =，则f 是满射；
对于1,2,2,1,Z Z <><>∈?，有(1,2)3(2,1)f f ==，而1,22,1<>≠<>，则f 非单射；
(,)2,(,)0f x x x f x x =-=．
8、设Z 为整数集合，“?”定义为：a ?b=a b ，问其在Z 上封闭吗？可交换吗？可结合吗？ 答：①取a ＝2，b ＝-1，a ?b =2-1?Z ，其在Z 上不封闭；
②取a ＝2，b ＝1时，a ?b=a b =2，b ?a=b a =1，a ?b ≠b ?a ，其在Z 上不可交换；
③取a =2，b=1，c =2，(a ?b )?c =4，a ?(b ?c ) =2，(a ?b )?c ≠a ?(b ?c )，其在Z 上不可结合．
9、设Z 为整数集合，“?”定义为：a ?b=2ab ，问其在Z 上封闭吗？可交换吗？可结合吗？ 答：①整数乘法运算在Z 上封闭，
②?a,b ∈Z ，a ?b=2ab =2ba =b ?a ，其在Z 上可交换；
③?a,b,c ∈Z ，(a ?b )?c =2(2ab )?c =4abc =2a ×2bc =2a (b ?c )=a ?(b ?c ) ，其在Z 上可结合． A
2
3
4 B 2 4 7
10 12
10、设无向图,G V E =有12条边，已知有6个3度顶点，其余顶点的度数均小于3，问G 中至少有多少个顶点？
答：设G 中度数小于3的顶点有k 个，则由欧拉定理deg()24v V
v ∈=∑知，
度数小于3 的顶点度数之和为6，故当其余的顶点度数都为2时，G 的顶点最少， 即G 中至少有9个顶点.
11、n 取怎样的值，无向完全图K n 有一条欧拉回路?
答： n 为奇数，?v ∈V ，deg(v )=n -1为偶数，
所以，当n 是大于或等于3的奇数时，K n 有欧拉回路.
12、判断下列无向图是否存在欧拉路径？是否为欧拉图？说明理由. A B
C
D E
F
答：d(A)=2, d(B) =d(C)= d(D)=4 d(E) =d(F)=3
只有两个奇数度的结点, 有欧拉路径，如EDBEFCABCDF ；
由于每个结点的次数不均为偶数，所以不是欧拉图.
13、判断下列图是否为欧拉图？说明理由，是否存在哈密尔顿回路？
? ? ?
? ?
答：一个无向图D 是欧拉图?D 是连通的，且所有顶点的度等于偶数，
所以是欧拉图，但无哈密尔顿回路．
14、判断下列图是否存在欧拉路径？是否为欧拉图？说明理由.
A B
C
D
答：一个有向图D 是欧拉图? D 是连通的，且所有顶点的入度等于出度，
所以是欧拉图，存在欧拉路径．
四、填表计算题（每题10分）
1、对命题公式 ()()A p q p q =?→∧∨，要求
（1）用0或1填补其真值表的空格处；（2）求该命题公式的主析取范式与主合取范式. 解：
p q p q → ()p q ?→ p q ∨ A
0 0 1 0 0 0
0 1 1 0 1 0
1 0 0 1 1 1
1 1 1 0 1 0
主析取范式(2)A ?∑ ；主合取范式(0,1,3)A ?∏.
2、对命题公式 ()A p q r =→?，要求
（1）用0或1填补其真值表的空格处；（2）求该命题公式的主析取范式与主合取范式. 解： p q r
p q → A 0 0 0 1 0
0 0 1 1 1
0 1 0 1 0
0 1 1 1 1
1 0 0 0 1
1 0 1 0 0
1 1 0 1 0
1 1 1 1 1
主析取范式(1,3,4,7)A ?∑ ；主合取范式(0,2,5,6)A ?∏.
3、设代数系统，其中A =?a ,b ,c ?，?是A 上的二元运算，由下列表给出，试列表分别讨论交换性、幂等性、么元和逆元． ? a
b c a a
b c b b
c a c
c a b
解：
交换律
幂等律 么元 逆元 有 无 a a –1= a , b –1= c , c –1= b
4、设代数系统，其中A =?a ,b ,c ?，?是A 上的二元运算，由下列表给出，试列表分别讨论交换性、幂等性、么元和逆元．
?
a b c a
a b c b
a b c c a b c
解：
交换律
幂等律 么元 逆元 有 无 a a –1= a , b –1= b
五、计算问答题（每题10分）
1、集合}4,3,2,1{=A 上的关系
}4,4,3,4,4,3,1,3,3,3,2,2,3,1,1,1{><><><><><><><><=R ，写出关系矩阵R M ，画出关系图并讨论R 的五种性质．
解：R 的关系矩阵为??????
? ??=1100110100100101R M ，R 的关系图为 因R M 对角元皆为1，故R 是自反的，不是反自反的；因R M 为对称矩阵，故R 是对称的； 因1,3,3,1R <><>∈，故R 不是反对称的；
又因1,3,3,4R <><>∈，但1,4R <>?，故R 无传递性．
2、设R 是集合}4,3,2,1{=A 上的二元关系，
{1,1,1,2,1,3,3,1,3,2,3,3,4,1,4,2,4,3}R =<><><><><><><><><>， 写出关系矩阵R M ，画出关系图并讨论R 的五种性质．
解：R 的关系矩阵为1110000011101110R M ?? ? ?= ? ???
，R 的关系图为 因R M 对角元不全为1，也不全为0，故R 不是自反的，也不是反自反的；
因R M 为非对称矩阵，故R 是反对称的，不是对称的；因2
R R =，故R 是传递的．
3、有向图G 如图9.27所示，
⑴ 求G 的邻接矩阵；
⑵ 根据邻接矩阵求各结点的出度和入度；
⑶ 求G 中长度为3的路的总数，其中有多少条回路；
⑷ 求G 的可达性矩阵． 解：⑴M R =440110100001010
000??? ? ? ? ???； ⑵deg ＋(v 1)=2，deg －(v 1)=1，deg ＋(v 2)=1，deg －(v 2)=2，
deg ＋(v 3)=2，deg －(v 3)=1，deg ＋(v 4)=0，deg －(v 4)=1；
⑶ A 2=441101011010000000??? ? ? ? ??? ，A 3=44
1110110101100000??? ? ? ? ??? ， 长度为3的路有8条，其中回路3条；
⑷ C 3=A 0+A 1+A 2+A 3=443321231112210001??? ? ? ? ??? P =1111111111110001?? ? ? ? ???
．
4、有向图,D V E =<>，其中结点集1234{,,,}V v v v v =，有向边集E 可表示为：
12233132344142{,,,,,,,,,,,,,}E v v v v v v v v v v v v v v =<><><><><><><>
（1） 求D 的邻接矩阵A ；（2）求D 的可达性矩阵P ；
（3）说明2v 到3v 长度为4的路径有几条？（4）2v 到其它各顶点长度为3的路径有几条？
解：（1）0100001011011
100A ??????=?????? ； （2）2001011011210011
0A ??????=??????，31101121012211111A ??????=??????，41210122134222311A ??????=?????? 23442421354269544632R A A A A ??????=+++=??????
，1111111111111111P ??????=?????? ； （3）2v 到3v 长度为4的路径有2条 ；
（4）2v 到其它各顶点长度为3的路径有2条．
5、有向图,D V E =<>，其中结点集1234{,,,}V v v v v =，
有向边集121314214243{,,,,,,,,,,,}E v v v v v v v v v v v v =<><><><><><>
（1）求D 的邻接矩阵A ；（2）求D 的可达性矩阵P ；
（3）说明D 中经过1v 长度为3的回路有几条？
（4）说明D 中1v 到3v 长度为4的路径有几条？
（5）说明D 中1v 到3v 所有的路径有几条？
解：（1） 0111100000000
110A ??????=?????? ； （2）21110011100001000A ??????=??????，31111111000000
111A ??????=??????，41221111100001110A ??????=??????
， 23443553333200002331R A A A A ??????=+++=??????，1111111100001111P ??
????=??????
； （3）D 中经过1v 长度为3的回路有1条；（4）D 中1v 到3v 长度为4的路径有2条；
（5）D 中1v 到3v 所有的路径有5条. 四、证明计算题（每题10分）
1、设{1,2,3,4}A =，在A A ?上定义:,,,R a b c d R <<><>>∈? c b d a +=+， “+”为普通加法，证明：R 是A A ?上的等价关系，并求出[2,4],/R A A R <>?． 证明：（1）,,,,,,,a b A A a b b a a b a b R ?<>∈?+=+∴<<><>>∈ 即R 自反；
（2）,,,,,,a b c d R a d b c c b d a ?<<><>>∈+=++=+∴则
则,,,c d a b R <<><>>∈，即R 对称；
（3）,,,,,,,,a b c d R c d e f R ?<<><>>∈<<><>>∈
,a d b c c f d e a d c f b c d e +=++=++++=+++∴则
有 a f b e +=+，,,,,a b e f R ∴<<><>>∈即R 传递；
综上得出，R 是A A ?上的等价关系，
且[2,4]R <>{,,,2}{1,3,2,4}a b a b A A a b =<><>∈?=-=<><>,
/{[1,1],[1,2],[2,1],[1,3],[3,1],[1,4],[4,1]}R R R R R R R A A R ?=<><><><><><><>．
2、设{1,2,3,4}A =，在A A ?上定义:,,,R a b c d R <<><>>∈? a d b c =
， “ ” 为普通乘法，证明： R 是A A ?上的等价关系，并求出[2,4],/R A A R <>?． 证明：（1）,,,,,,,a b A A a b b a a b a b R ?<>∈?=∴<<><>>∈ 即R 自反；
（2）,,,,,,a b c d R a d b c c b d a ?<<><>>∈==∴ 则
则,,,c d a b R <<><>>∈，即R 对称；
（3）,,,,,,,,a b c d R c d e f R ?<<><>>∈<<><>>∈
,a d b c c f d e a d c f b c d e ===∴ 则，
有 a f b e =
，,,,,a b e f R ∴<<><>>∈即R 传递； 综上得出，R 是A A ?上的等价关系，
且[2,4]R <>{,,,2}{1,2,2,4}a b a b A A a b =<><>∈?==<><>,
/{[1,1],[1,2],[2,1][1,3],[3,1],[1,4],[4,1]}R R R R R R R A A R ?=<><><><><><><>
3、设R 是实数集，R 上的二元运算*定义为：a *b=a+b+ab ，
证明：
证明：⑴由于实数经加法和乘法运算后，其运算结果仍为实数，所以运算*对于R 是封闭的； 由于a *b=a+b+ab=a (b +1)+(b +1)?1=(a +1) (b +1)?1
从而有(a *b )*c=((a +1)(b +1)?1)*c=(((a +1)(b +1)?1)+1)(c +1)?1=(a +1)(b +1)(c +1)?1
a *(
b *
c )=a *((b +1)(c +1)?1)=(a +1)(((b +1)(c +1)?1)+1)?1=(a +1)(b +1)(c +1)?1
于是 (a *b )*c=a *(b *c )，所以*是可结合运算；
在
故0是
对
4、某无向连通图G 中有10条边，二个2度顶点，二个3度顶点，一个4度顶点，其余顶点的度数都是1，求G 的顶点个数，并证明G 为树.
解：设G 中度数为1的顶点个数为x
由握手定理知22234210x +?+?+=?
解得6x =
于是G 中的顶点个数为22111x +++=
因G 为连通图，且G 中的边数比其顶点个数少1-故G 为树.
五、证明题（每题10分）
1、用逻辑推理规则证明：()()p q r s ?→→?∨，()q p r →∨?， r p q ??. 证明: (1) r P
(2) ()q p r →∨? P
(3) q p → T (1),(2) (析取三段论)
(4) r s ∨ T (1) (加法式)
(5) ()()p q r s ?→→?∨ P
(6) p q → T (4)，(5) (拒取式)
(7) ()()p q q p →∧→
T (3)，(6) (合取式)
(8) p q ? T (7) (等值表达式) .
2、用逻辑推理规则证明：()()p q r s ∨→∧，()r s t p t ∨→?→ .
证明：（1）p P (附加前提)
(2)p q ∨ T (1)（加法式）
(3)()()p q r s ∨→∧ P
(4)r s ∧ T (2)，(3)（假言推理）
(5)r T (4)（简化式）
(6)r s ∨ T (5)（加法式）
(7)()r s t ∨→ P
(8)t T (6)，(7)（假言推理）
(9)p t → CP .
3、用逻辑推理规则证明：(()()),(()()),()()x F x G x x G x R x xR x xF x ?∨?→????．
证明：⑴()xR x ?
P ⑵()R c
T ⑴（US ） ⑶(()())x G x R x ?→?
P ⑷()()G c R c →?
T ⑶（US ） ⑸()G c ?
T ⑵，⑷（拒取式） ⑹(()())x F x G x ?∨
P ⑺()()F c G c ∨
T ⑹（US ） ⑻()F c
T ⑸，⑺（析取三段论） ⑼()xF x ? T ⑻（UG ）．
4、用逻辑推理规则证明：()(()()()),()()xF x y F y G y R y xF x xR x ?→?∨→???．
证明：⑴()xF x ?
P ⑵()F c
T ⑴（ES ） ⑶()(()()())xF x y F y G y R y ?→?∨→
P ⑷(()()())y F y G y R y ?∨→
T ⑴，⑶（假言推理） ⑸()()()F c G c R c ∨→
T ⑷（US ） ⑹()()F c G c ∨
T ⑵（加法式） ⑺()R c
T ⑸，⑹（假言推理） ⑻()xR x ? T ⑺（EG ）．
5、用逻辑推理规则证明： (()())()()x P x Q x xP x xQ x ?→??→?.
证明：⑴()xP x ?
P （附加前提） ⑵()P a
T ⑴（ES ） ⑶(()())x P x Q x ?→
P ⑷()()P a Q a →
T ⑶（US ） ⑸()Q a T ⑵，⑷（假言推理）
⑹()xQ x ?
T ⑸（EG ）
⑺()()xP x xQ x ?→?
CP ． 6、设R 为集合A 上的二元关系，如果R 是反自反的和可传递的，则R 一定是反对称的． 证明：假设R 不是反对称的，则 y x R x y R y x ≠>∈<>∈
由R 的传递性知， R x x >∈<, ，此与R 反自反矛盾，故R 反对称．
7、设R 是A 上的对称和传递关系，
证明：若,,,a A b A a b R ?∈?∈?<>∈，则R 是A 上的等价关系．
证明：,,,a A b A a b R ?∈?∈?<>∈，因R 是对称的，有,b a R <>∈，
又因R 是传递的，所以,a a R <>∈，则R 在A 上自反，故R 是A 上的等价关系．
8、设,R S 是A 上的偏序关系，证明：R S 是A 上的偏序关系．
证明：（1）x A ?∈，因,R S 在A 上的自反性，则,x x R S <>∈ ，有R S 在A 上自反；
（2）设,,x y R S <>∈ 而x y ≠，则,,,,x y R x y S <>∈<>∈因,R S 在A 上的反对称性，有,,,,y x R y x S <>?<>?则,,y x R S <>? 于是，R S 在A 上是反对称的；
（3）设,,,x y R S y z R S <>∈<>∈ ，
则,,,;,,,x y R y z R x y S y z S <>∈<>∈<>∈<>∈，因,R S 在A 上的传递性， 有,,,x z R x z S <>∈<>∈,则,x z R S <>∈ ，于是，R S 在A 上是传递的； 综上所述，可证R S 是A 上的偏序关系． 9、设R 是S 上的等价关系，证明：1
R -是S 上的等价关系．
证明：（1）因R 在S 上的自反性，有S I R ?，则11S S I I R --=?，有1R -在S 上自反； （2）因R 在S 上的对称性，有1R R -=，则111()R R R ---==，有1R -在S 上对称；
（3）因R 在S 上的传递性，有2
R R ?，则1221()R R R R --=?=，有1R -在S 上可传递； 则2'(')('(''))('')'R R R R S S R S S R ????= ，有'R 在'S 上是对称的； 综上所述，可证1R -是S 上的等价关系．
10、设Z 是整数集，Z 上的二元运算*定义为：a *b=ab+2(a+b+1)，证明：
注意到，a *b=ab+2(a+b+1)=ab+2a+2b+2=a (b +2)+2(b +2)?2=(a +2)(b +2)?2
从而有(a *b )*c=((a +2)(b +2)?2)*c=(((a +2)(b +2)?2)+2)(c +2)?2=(a +2)(b +2)(c +2)?2
a *(
b *
c )=a *((b +2)(c +2)?2)=(a +2)(((b +2)(c +2)?2)+2)?2=(a +2)(b +2)(c +2)?2
于是 (a *b )*c=a *(b *c )，则*是可结合运算，故代数系统
11、设R 是实数集，R 上的运算*定义为：a *b=a+b+ab ，令A=R ???1?，证明：是群． 证明：首先证明*对于A 是封闭的，由于a *b=(a +1)(b +1)?1
所以当a 和b 为不等于?l 的实数时，a+1≠0，b+1≠0，也即有(a +1)(b +1)≠0，
由此可知a *b=(a +1)(b +1)?1≠?1，因此*对于A 是封闭的；
(a *b )*c=((a +1)(b +1)?1)*c=(((a +1)(b +1)?1)+1)(c +1)?1=(a +1)(b +1)(c +1)?1
a *(
b *
c )=a *((b +1)(c +1)?1)=(a +1)(((b +1)(c +1)?1)+1)?1=(a +1)(b +1)(c +1)?1
于是 (a *b )*c=a *(b *c )，所以*是可结合运算；
在中，对于任何实数a ，都有0*a=a *0=0+a+0·a=a ，故0是中的么元； 对于A 中a (a 是不等于?1的实数)，都有a *(
11+a ?1)=(a +1)(11+a ?1+1)?1=0 由于0是么元，所以a 的逆元是1
1+a ?1；综上证明，是群． 12、
求证：
证明：1）?a ，b ∈G ，a ?b=a*u -1*b ∈G ，运算是封闭的；
2）?a ，b ，c ∈G ，（a ?b ）?c=（a*u -1*b ）*u -1*c=a*u -1*（b*u -1*c ）=a ?（b ?c ），运算可结合；
3）?a ∈G ，设E 为?的单位元，则a ?E=a*u -1*E=a ，得E=u ，存在么元u ；
4）?a ∈G ，a ?x=a*u -1*x=E ，x=u*a -1*u ，则x ?a=u*a -1*u*u -1*a=u=E ，各元素都有逆元；
所以
13、设图G=
证明：由已知可知，G 中k+1度顶点为n-nk 个。再由欧拉握手定理可知
2m=deg()v V
v ∈∑=k k n +(k+1)(n-k n )=(k+1)n-k n ，k
n = (k+1)n -2m . 14、设G =
m 2≤?(G ) . 证明：根据最小度的定义，?v ∈V ，deg(v )≥δ(G )，所以，2m=∑=n i v 1)deg(≥()∑=n i G 1
δ=n δ(G )
即 n δ(G ) ≤2m ，整理后得，δ(G )≤n
m 2 另一方面，根据最大度的定义，?v ∈V ，deg(v )≤?(G )，与前面推理类似的可得，2m ≤n ?(G ) 整理后得，?(G )≥n m 2，,所以， δ(G )≤n
m 2≤?(G ) . 15、设图G 有n 个结点，n ＋1条边，证明：G 中至少有1个结点度数大于等于3. 证明：用反证法，设G =
所有结点的度数之和2(n+1)小于2n 。即2(n+1)≤2n ，化简后，2≤0，矛盾，
所以，G 中至少有1个结点度数大于等于3.
离散数学期末复习
离散数学期末复习 一、选择题 1、下列各选项错误的是 A、??? B、??? C、?∈{?} D、??{?} 2、命题公式(p∧q)→p是 A、矛盾式 B、重言式 C、可满足式 D、等值式 3、如果是R是A上的偏序关系，R-1是R的逆关系，则R∪R-1是 A、等价关系 B、偏序关系 C、全序关系 D、都不是 4、下列句子中那个是假命题？ A、是无理数. B、2 + 5＝8.
C、x+ 5＞3 D、请不要讲话！ 5、下列各选项错误的是？ A、??? B、??{?} C、?∈{?} D、{?}?? 6、命题公式p→（p∨q∨r）是？ A、重言式 B、矛盾式 C、可满足式 D、等值式 7、函数f : N→N, f(x)=x+5,函数f是 A、单射 B、满射 C、双射 D、都不是 8、设D=
D、不连通的 9、关系R1和R2具有反自反性，下面运算后，不能保持自反性的是 A、R1?R2 B、R1-1 C、R1?R2 D、R1-R2 10、连通平面图G有4个结点，3个面，则G有（）条边。 A、7 B、6 C、5 D、4 二、填空题 1、将下面命题符号化。设p:天冷，q:小王穿羽绒服。只要天冷，小王就穿羽绒服.符号化为 2、将下面命题符号化，设p:天冷，q:小王穿羽绒服。因为天冷，所以小王穿羽绒服.符号化为 3、将下面命题符号化，设p:天冷，q:小王穿羽绒服。若小王不穿羽绒服，则天不冷.符号化为 4、将下面命题符号化，设p:天冷，q:小王穿羽绒服。只有天冷，小王才穿羽绒服.符号化为
离散数学期末试题
离散数学考试试题（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 。
离散数学期末试题及答案
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的补元( ). 5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ).
离散数学期末试题及答案完整版
离散数学期末试题及答 案 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的补元( ).
【浙江工商大学】《离散数学》期末考试题(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.整环不一定是域. ( )
离散数学期末考试试题及答案
离散数学试题(Ｂ卷答案１） 一、证明题(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={
离散数学期末试卷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人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？
离散数学期末测验试题(有几套带答案1)
离散数学期末测验试题（有几套带答案1)
————————————————————————————————作者: ————————————————————————————————日期: ?
离散数学试题(A卷及答案） 一、证明题（10分） １)(?P∧(?Q∧Ｒ)）∨(Q∧R）∨(P∧R）?Ｒ 证明：左端?(?P∧?Q∧R)∨（(Q∨Ｐ)∧R)?（(?P∧?Q)∧R))∨((Ｑ∨Ｐ)∧R） ?(?(P∨Q）∧R)∨((Q∨P)∧Ｒ)?(?(P∨Q)∨(Ｑ∨Ｐ))∧R ?(?(P∨Q)∨(Ｐ∨Ｑ))∧R?T∧R(置换）?R 2）?x(Ａ（ｘ)→B(x)）??xＡ(x）→?xB(x) 证明:?x(A(x)→Ｂ(x））??x（?A（x)∨B(x))??x?A(x)∨?xB(x)???xA（x)∨?xB(x)??xA(x)→?xＢ(ｘ） 二、求命题公式(P∨(Q∧Ｒ))→(Ｐ∧Q∧R）的主析取范式和主合取范式(１０分) 证明:(P∨（Ｑ∧Ｒ））→(P∧Q∧R)??(P∨(Ｑ∧Ｒ）)∨（P∧Q∧R)) ?（?P∧（?Q∨?R)）∨(Ｐ∧Q∧Ｒ） ?(?P∧?Ｑ)∨(?P∧?R)）∨(Ｐ∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Ｑ∧?R）∨(?Ｐ∧Q∧?R)）∨(?P∧?Q∧?R)）∨(Ｐ∧Ｑ∧R) ?m0∨ｍ1∨m2∨ｍ７ ?Ｍ3∨M4∨M5∨M6 三、推理证明题(10分) 1）Ｃ∨D， (C∨D)→?E, ?Ｅ→(A∧?B), (A∧?B)→(R ∨S)?R∨S 证明:(1) (C∨D）→?E (２) ?E→（A∧?Ｂ) ?? (3）（C∨D）→（A∧?Ｂ) （４) （Ａ∧?B)→(R∨Ｓ) ?? (5) （C∨D）→（R∨Ｓ) ? (6) C∨Ｄ?? (7) R∨S 2) ?x(P(ｘ)→Q(ｙ）∧R(x)），?xP(x)?Q(y）∧?x（P(x)∧R(x)) 证明（1)?xP(ｘ) (2）P(a) （3)?ｘ(P(x)→Q(y）∧R(x)) (4）P（a)→Q(y)∧R(a) (５)Q(y)∧Ｒ(a) (6)Q(y) （７)R(a） (8)P(a) (9)P(ａ)∧R(a) （10)?x(Ｐ(x)∧R(ｘ)) (11)Q（ｙ)∧?x(P（x）∧R(x)） 五、已知Ａ、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) （１5分) 证明∵x∈A-（Ｂ∪C)?x∈A∧x?（Ｂ∪C)?x∈A∧(x?Ｂ∧ｘ?C）?(x∈A∧x?B)∧（x∈A∧x?C）?x∈（Ａ-B)∧ｘ∈(A－C）?x∈(A－B）∩（A-Ｃ)∴A-(B∪Ｃ）=（A-B)∩(A-C） 六、已知R、S是N上的关系，其定义如下：Ｒ=｛＜x，ｙ>| x，y∈N∧y=x2｝，Ｓ={
离散数学期末考试试题及答案
离散数学试题(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
离散数学本科期末复习题
1. 计算：2400 mod 319、2340 mod 11。 2. 设整数a 和b 不全为0，且a 和b 互素。请证明：ab 和a+b 互素。 3. 设n!的标准素因数分解式是 k k p p p εεεΛ2121 请证明： ∑∞=???? ? ?????=1s s i p n i ε，i=1,2,…,k 4. 300！末尾0的个数是？。 5. 解同余方程组：x≡3(mod 8)，x≡11(mod 20)，x≡1(mod 15)。 6. 求p →(p ∧(q →p))的主析取范式和主合取范式。（真值表法和等值演算法） 7. 求谓词公式?x ?y(P(x,y)?Q(x,y))→?x ?yR(x,y)的前束范式。 8. 证明下面的推理： “每个科研工作者都是努力工作的。每个努力工作而又聪明的人都取得事业的成功。某个人是科研工作者并且聪明。所以，某人事业取得成功。” 9. 设R={(1,2),(1,4),(3,3),(4,1)}是集合A={1,2,3,4}上的关系。 （1） R 是自反的吗？是对称的吗？是传递的吗？ （2） R 的自反对称闭包存在吗？ （3） R 的自反传递闭包存在吗？ （4） R 的对称传递闭包存在吗？ （5） R 的自反对称传递闭包存在吗？ （6） R 的反自反闭包存在吗？ （7） R 的反对称闭包存在吗？ 10. 设A={x|x ∈N ，且x|54}，R={(x,y)|x,y ∈A ，且x|y }。 （1） 列出集合A 和R 中的元素； （2） 给出R 的矩阵表示； （3） 证明(A,R)是偏序集，画出哈斯图； （4） 指出(A,R)中的最大元、最小元、极大元、极小元。 11. 设X={(x,y) | x 和y 是不为零的实数}，E 是X 上的关系：
离散数学期末试卷及答案
一．判断题（共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．自然数集关于数的加法和乘法
列为。 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?{
最新离散数学期末考试试题配答案
精品文档院术师范学广东技模拟试题 科目：离散数学 120 分钟考试时间: 考试形式：闭卷 姓名：学号：系别、班级： 2分，共10分）一．填空题（每小题__________。?x?y?P(x)∨Q(y) 1. 谓词公式的前束范式是 __)xxQ(?xP(x)????????____，，2. 设全集A?_{4,5}B =__则A∩ {2}__,,?E?1,2,3,4,55,A?21,,32,B_____ __ {1,3,4,5}??BA????b,c}} __________，则3. 设__ ， b?,c,b,a,A?Ba???B(A)?)(_____Φ_______。???)(AB()?4. 在代数系统（N，+）中，其单位元是0，仅有_1___ 有逆元。 ne条边，则G有___e+2-n____个面。5．如果连通平面图G有个顶点，二．选择题（每小题2分，共10分） P?(Q?R)等价的公式是（1. 与命题公式） （A）（B）（C）（D）R?P?Q)()?R)R?(QPP?(Q?R?Q)(P??????b?b,?a,aA??a,b,cR?,不具备关系( 2. 设集合上的二元关系,A)性质 （A）(A)传递性(B)反对称性(C)对称性(D)自反性 G??V,E?中,结点总度数与边数的关系是3. 在图( ) ??E?Edeg(v)deg(v)?2deg(v)?Evdeg()?2E(A)(C)(B) (D) iiiiVv?Vv?4. 设D是有n个结点的有向完全图,则图D的边数为( ) n(n?1)n(n?1)n(n?1)/2n(n?1)/2(A)(B)(D)(C) 5. 无向图G是欧拉图,当且仅当( ) (A)G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数 精品文档． 精品文档 (C)G连通且所有结点的度数都是偶数(D) G连通且G的所有结点度数都是奇数。 三．计算题（共43分） p?q?r的主合取范式与主析取范式。（1. 求命题公式6分） 解：主合取方式：p∧q∨r?(p∨q∨r)∧(p∨?q∨r)∧(?p∨q∨r)= ∏0.2.4 主析取范式：p∧q∨r?(p∧q∧r) ∨(p∧q∧?r)∨(?p∧q∧r) ∨(?p∧?q∧r) ∨(p∧?q∧r)=∑1.3.5.6.7 1000????0111?????Md,A?a,b,c,的上的二元关集2. 设合系R关系矩阵为求 ??R0000????1000??)tR(),(RsRr()(),(),(rRsRtR),的关系图。R的关系矩阵，并画出分）10（，
《离散数学》期末考试试题
《离散数学》期末考试试题 一、 填空题（每空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 ∧??∧?)())((。
离散数学--期末复习
v1.0 可编辑可修改 离散数学知识要点总结 第1章命题逻辑 1、会判断一个语句是否为命题（如P31-习题题） 练习：判断下列语句是否为命题。 (1).3+8=13； (2).离散数学是计算机系的一门必修课； (3).太阳系以外的星球上有生物； (4).你打算考硕士研究生吗 (5).9+5≤12 ； (6). 天上有三个月亮。 (7).x+5 > 6； (8).一定要努力学习！(9).2是素数； (10).x+5 > 6； (11).我正在说谎； (12).x=13. (13).这朵花多好看呀！ (14).7能被2整除. (15).我用的计算机CPU主频是 1G吗 (16).蓝色和黄色可以调成绿 色； (17). 雪是黑色的. (18). 明天会下雨吗； (19).我能进来吗 (20).这个男孩真勇敢呀！ (21).蓝色和黄色可以调成绿 色； (22).x≤3； (23)地球饶着太阳转. (24)青年人多么朝气蓬发呀！ (25).5能被2整除. (26).嫦娥一号太棒了！ (27).台湾是中国的一部分； (29) 你下午有会吗若无会，请 到我这儿来！ (30).请不要讲话！ (31) 5是奇数； (32). 3 2> + x 2、注意五个命题联结词的使用，会将命题进行符号化（如，，题的题型）或在判断体现逻辑联结词的逻辑有关系等。练习：将以下命题符号化 (1)如果你不去逛街，那么我也不去逛街。 (2)小李边吃饭边看电视。 (3)林芳学过英语或日语。 (4)张辉与王丽都是三好生. (5)小王住在101室或102室。 (6).2+2≠4当且仅当王红没努力学习离散数学。 (7)4或6是素数. (8).王晓聪明，但是他不用功. (9)如果今天是1号，则明天是5号。(10).小潘不能既跳舞又唱歌。 (11)如果你来了，他就唱歌而且陪你跳舞。 (12).或者雪是黑色的，或者太阳从东方升起。 (13).王晓既用功又聪明。 (14)2 + 2 ≠ 4 当且仅当美国位于非洲。 (15)小李学过英语或法语。 (16）如果石头会说话，那么月亮上就会出现海洋。(17）.如果天气寒冷，小梅就不去游泳。 （18）小红喜欢看书和画画。
离散数学-期末考试卷-A卷
离散数学-期末考试卷-A卷
东莞理工学院城市学院（本科）试卷（A卷） 2013-2014学年第一学期 开课单位：计算机与信息科学系，考试形式：闭卷，允许带入场 科目：离散数学，班级：软工本2012-1、2、3 姓名：学号： 题序一二三四总分 得分 A评 卷人 一、单项选择题（每小题2分，共20分） 在每小题列出的四个备选项中只有一个是符合题目要求的，错选、多选或未选均无分。 1. 下述不是命题的是( ) A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 2. 命题公式P→(P∨Q∨R)是( ) A. 永假的 B. 永真的 C. 可满足的
D. 析取范式 3. 命题公式﹁B→﹁A等价于( ) A. ﹁A∨﹁ B B. ﹁(A∨B) C. ﹁A∧﹁ B D. A→B 4．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）A．?P∧Q B．P∧?Q C．P→?Q D．P∨?Q 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. 设有A={a,b,c}上的关系R={
7. 设A={1,2,3,4,5,6},B={a,b,c,d,e}，以下哪一个关系是从A到B的满射函数( ) A. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>} B. f={<1,e>,<2,d>,<3,c>,<4,b>,<5,a>,<6,e>} C. f={<1,a>,<2,b>,<3,c>,<4,a>,<5,b>,<6,c>} D. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>,<1,b>} 8．设简单图G所有结点的度数之和为10，则G一定有（） A．3条边B．4条边C．5条边 D．6条边 9．下列不．一定是树的是（） A．每对结点之间都有通路的图 B．有n个结点，n-1条边的连通图 C．无回路的连通图D．连通但删去一条边则不连通的图 10．下列各图中既是欧拉图，又是哈密顿图的是（）
离散数学期末考试题
《离散数学》复习题 一、单项选择题（每小题2分，共20分） 1、下列命题中是命题的是（ ） A 、 7>+y x B 、雪是黑色的 C 、严禁吸烟 D 、我正在说谎 2下列命题联结词集合中,哪个不是极小全功能集( )。 A 、{,}刭 B 、{,}刳 C 、{}- D 、{,}佼 3、下列公式中哪个不是简单析取式（ ）。 A 、p B 、p q ∨ C 、()p q ?∨ D 、p q ?∨? 4、设个体域{,}A c d =，公式()()x P x x S x ?∧?在A 中消去量词后应为（ ） A ()()P x S x ∧ B (()())(()( P c P d S c S d ∧∧∨ C ()()P c S d ∧ D ()() () (P c P d S c S d ∧ ∧∨ 5、下列是命题公式p ∧(q ∨┓r)的成真指派的是( ) A.110，111，100 B.110，101，011 C.所有指派 D.无 6、下列命题中（ ）是正确的。 A. 若图G 有n 个顶点，则G 的各顶点的度和为2n; B. 无向树中任意两点之间均相互可达； C. 若有向图G 是弱连通的，则它必定也是单向连通； D. 若无向带权图G 是连通的，则其最小生成树存在且唯一。
7、正整数集合Z +的以下四个划分中，划分块最多的是（ ） A ．1π={{x }︱x ∈Z + } B ．2π= {Z + } C. 3π={12,S S },1S 为素数集，21S Z S + =- D ．3π={12,S S ,3S },i S 为Z +中元素除以3的余数 8、给定下列各图： ⑴G 1=
离散数学期末考试试题(配答案)
广东技术师范学院 模拟试题 科 目：离散数学 考试形式：闭卷 考试时间: 120 分钟 系别、班级： 姓名： 学号： 一．填空题（每小题2分，共10分） 1. 谓词公式)()(x xQ x xP ?→?的前束范式是__ ?x ?y?P(x)∨Q(y) __________。 2. 设全集{}{}{},5,2,3,2,1,5,4,3,2,1===B A E 则A ∩B =__{2}__，=A _{4,5}____， =B A __ {1,3,4,5} _____ 3. 设{}{}b a B c b a A ,,,,==，则=-)()(B A ρρ__ {{c},{a,c},{b,c},{a,b,c}} __________， =-)()(A B ρρ_____Φ_______。 4. 在代数系统（N ，+）中，其单位元是0，仅有 _1___ 有逆元。 5．如果连通平面图G 有n 个顶点，e 条边，则G 有___e+2-n ____个面。 二．选择题（每小题2分，共10分） 1. 与命题公式)(R Q P →→等价的公式是（ ） （A ）R Q P →∨)( （B ）R Q P →∧)( （C ）)(R Q P ∧→ （D ）)(R Q P ∨→ 2. 设集合{}c b a A ,,=,A 上的二元关系{}><><=b b a a R ,,,不具备关系( )性质 （A ） (A)传递性 (B)反对称性 (C)对称性 (D)自反性 3. 在图>= 离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（）离散数学期末练习题-(带答案)复习进程
- 离散数学期末考试题
- 离散数学期末考试题(有几套带答案)
- 【浙江工商大学】《离散数学》期末考试题(B)
- 离散数学期末考试试题(配答案)
- 离散数学期末考试试题(配答案)
- 离散数学期末考试题及答案
- 最新离散数学期末考试试题(配答案)
- 离散数学期末测试卷I及答案
- 《离散数学》期末考试试题
- 离散数学期末考试试题与答案
- 离散数学》期末考试题(A)
- 《离散数学》期末试题及答案
- 离散数学期末试题及答案完整版
- 离散数学期末考试题(附答案和含解析3)
- 离散数学期末考试题
- 离散数学期末试卷(3套附答案)
- 离散数学期末考试试题(有几套带答案)
- 离散数学期末试卷A卷汇总
- 离散数学期末考试试题及答案
- 离散数学期末考试试题及答案