淮海工学院2011-2012-2离散数学期末复习题答案(1)

淮海工学院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、?R?a,a??R?a,b????R?b,a??R?b,b?? 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、 设集合A?{0,?}，?为空集， ?(A)为A的幂集，则下列为假命题的是（ B ） A、???(A) B、0??(A) C、{?}??(A) D、{0}??(A) 13、 设集合A?{0,?}，?为空集， ?(A)为A的幂集，则下列为假命题的是（ B ） A、???(A) B、{0}??(A) C、{?}??(A) D、{{0}}??(A) 14、非空集合X上的空关系?不具备的性质是（ A ）

A、自反性 B、反自反性 C、对称性 D、传递性

10、设A?{1,2,3}上的关系R的关系图如下，则R不具备的性质为（ A ）

????

A、自反性 B、反自反性 C、反对称性 D、传递性 15、A?{1,2,3,4}上的关系R???1,3?,?1,4?,?2,3,??2,4,?3?,4??只不具备（ C ）

A、 反自反性 B、 反对称性 C、对称性 D、传递性

16、设R为A?{1,2,3}上的关系，其关系图如下，则下列为真命题的是（ C ）

A、R对称，但不反对称 B、R反对称，但不对称 C、R对称，又反对称 D、R不对称，也不反对称

17、设R为A?{1,2,3,4}上的关系，其关系图如下，则下列为假命题的是（ C ）

A、R不自反，也不反自反 B、R不对称，也不反对称 C、R传递 D、R不传递

18、设A?{ 1, 2, 3 }，则A上不同等价关系的个数为（ C ） A、3 B、4 C、5 D、6 19、设A?{ 1, 2, 3, 4 }，则A上不同等价关系的个数为（ C ）

A、13 B、14 C、15 D、16

20、设R、Z分别为实数集、整数集，则下列函数为满射而非单射的是（ C ） A、f:R?R,C、f:R?Z,A、f:R?R,C、f:R?R,f(x)?(x?6)2

f(x)?[x] D、f:R?R,f(x)?x6?6x

f(x)?x?6 B、f:R?R,21、设R、非负实数集、正整数集，下列函数为单射而非满射的是（ B ） R、Z?分别为实数集、

f(x)??x2?7x?1 B、f:Z??R,f(x)?lnx；

f(x)?7x?1

f(x)?x D、f:R?R,22、设X?3,Y?4，则从X到Y可以生成不同的单射个数为（ B ）． A、12 B、24 C、64 D、81 23、设X?3,Y?2，则从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、a?b?max{a,b}D、a?b?a?2b

26、设Nk为前k?2个自然数集，?k表示模k加法，对代数系统A?Nk,?k，有（ A ） A、0是么元，无零元 B、1是么元，无零元 C、无么元，0是零元 D、无么元，无么元 27、设Nk为前k?2个自然数集，?k表示模k乘法，对代数系统A?Nk, ?k，有（ B ）A、1是么元，无零元 B、1是么元，0是零元 C、无么元，0是零元 D、无零元，无么元 28、设非空有限集S的幂集为?(S)，对代数系统A?29、设非空有限集S的幂集为?(S)，对代数系统A??(S),?，有（ B ）

A、?是么元，S是零元 B、?是零元，S是么元 C、唯一等幂元 D、无等幂元

?(S),?，有（ A ）

A、?是么元，S是零元 B、?是零元，S是么元 C、唯一等幂元 D、无等幂元

30、设Z是由所有整数组成的集合，对于下列*运算，代数系统为独异点的是（ B ） A、a*b=ab 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的顶点集V?{v1,v2,?,vn}，邻接矩阵A?(aij)n?n，则d eg(?)vi?（ D ）A、aii B、

n?ai?1ii C、

?aj?1nij D、

?aj?1nji

37、设有向线图G的顶点集V?{v1,v2,?,vn}，邻接矩阵A?(aij)n?n，则d eg(?)vi?（ C ）A、aii B、

?ai?1nii C、

?aj?1nij D、

?aj?1nji

38、在有n个结点的简单无向图中，其边数（ C ） A、 最多有n-1条 B、至少有n-1条 C、最多有

n(n?1)n(n?1)条 D、至少有条 2239、在有n个结点的简单有向图中，其边数（ C ）

A、 最多有n-1条 B、至少有n-1条 C、最多有n(n?1)条 D、至少有n(n?1)条 40、在有n个结点的连通图中，其边数（ B ）

A、 最多有n-1条 B、至少有n-1条 C、最多有n条 D、至少有n条 41、设A?{?,{1},{1,3},{1,2,3}}，则A上包含关系“?”的哈斯图为（ C ）

42、集合A?{ 1, 2, 3,4 }上的偏序关系图为

则它的哈斯图为（ A ）

43、下列哪一种图不一定是树（ C ）

A、无简单回路的连通图 B、 有n个顶点n-1条边的连通图 C、每对顶点间都有通路的图 D、连通但删去一条边便不连通的图

44、设G是有5个结点的无向完全图，则从G中删去（ C ）条边可以得到树 A、 4 B、5 C、6 D、10

二、填充题（每题4分）

1、当赋予极小项足标相同的指派时，该极小项的真值为1，当赋予极大项足标相同的指派时，该极大项的真值为0.

2、任意两个不同极小项的合取式的真值为0，而全体极小项的析取式的真值为1. 3、任意两个不同极大项的析取式的真值为1，而全体极大项的合取式的真值为0. 4、n个命题变元可构造包括F的不同的主析取范式类别为2.

5、n个命题变元可构造包括T的不同的主合取范式类别为2.

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)的基数为212、A??(B)的基数为m2，?(A)?B的基数为n2，?(A)??(B)的基数为2nmm?nmn2n2n，

．

1 ,2,3,4,6,8,12,24} 13、设A?{，“?”为A上整除关系，则偏序集?A,??的极小元为1，最小元为1，极大元为24、最大元为24． 14、设A?{ 2,3,4,6,8,12 }，“?”为A上整除关系，则偏序集?A,??的极小元为2,3，

最小元为无，极大元为8,12，最大元为无，既非极小元也非极大元的是4,6． 15、设X?m,Y?n，则从X到Y有2有n! 种不同的双射．

17、设A={2,4,6}，A上*为：a*b=max{a,b}，则在代数系统中，么元是2，零元为6． 18、设A={3,6,9}，A上*为：a*b=min{a,b}，则在代数系统中，么元是9，零元为3 ． 19、设〈G,*〉是一个群，则

(1) 若a,b,x∈G，a?x=b，则x= a?b；(2) 若a,b,x∈G，a?x=a?b，则x= b． 20、群的等幂元是么元，有1个，零元有0个．

21、设a是12阶群的生成元， 则a是6阶元素，a是4阶元素． 22、设a是10阶群的生成元， 则a是5阶元素，a是10阶元素． 23、在一个群〈G,*〉中，若G中的元素a的阶是k，则a的阶是k． 24、n阶无向完全图Kn 的边数是

?14323mn 种不同的二元关系，有n 种不同的函数．

nm

16、在一个有n个元素的集合上，可以有2 种不同的二元关系，有n 种不同的函数，

n2?1n(n?1)，每个结点的度数是n?1． 2?0?1?25、设有向图G = < V，E >，V?{v1,v2,v3,v4}的邻接矩阵A??1??1则v1的入度deg(v1)= 3 ，v4的出度deg(v4)=1 ．

??101001001??1?， 0??0?26、设无向图G有18条边且每个顶点的度数都是3，则图G有12个顶点． 27、一棵无向树的顶点数为n，则其边数为n-1 ，其结点度数之和是2n-2. 28、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在2片树叶.

三、问答题（每题6分）

1、若个体域D?{?1,3,6}，S(x)：x?3，Q(x)：x?5,a：3，P:5?3， 则谓词公式?x(S(x)?Q(a))?P为真吗？为什么？

答：为真；

?x(S(x)?Q(a))?P?((S(?1)?Q(a))?(S(3)?Q(a))?(S(6)?Q(a)))?1

?((0?0)?(0?0)?(1?0))?1?(1?1?0)?1?1.

2、谓词公式?x?yP(x,y)??y?xP(x,y)为真吗？为什么？ 答：不为真；设个体域D：实数域，P(x,y)：x?y?0， 则?x?yP(x,y)??y?xP(x,y)?1?0?0.

3、设A??1,2,3?，问A上存在一个既不是自反又不是反自反的关系吗？为什么？

答：存在；如R???1,1?,?1,2??．

4、设A??1,2,3?，问A上存在一个既不是对称又不是反对称的关系吗？为什么？ 答：存在；如R???1,2?,?1,3?,?2,1??．

5、设A??1,2,3?，问A上存在一个既是对称又是反对称的关系吗？为什么？ 答：存在；如R???1,1?,?2,2?,?3,3??．

34}，B?{2，4，7，10,12}，从A到B的关系 6、设A?{2，，R?{?a,b?a?A,b?B,且a整除b}，试给出R的关系图和关系矩阵，并说明此

关系R及其逆关系R是否为函数？为什么？

解：R?{?2,2?,?2,4?,?2,10?,?2,12?,?3,12?,?4,4?,?4,12?}，则R的关系图为： R的关系矩阵为

A 2 3 4 B 2 4 7 10 ?1?11011??? MR?00001 ????01001??关系R不是A到B的函数，

因为元素2，4的象不唯一

12 ?1逆关系R也不是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，总有f(0,x)?x，则f是满射；

对于?1,2?,?2,1??Z?Z,，有f(1,2)?3?f(2,1)，而?1,2???2,1?，则f非单射；

f(x,x)?2x,f(x,?x)?0．

8、设Z为整数集合，“?”定义为：a?b=ab，问其在Z上封闭吗？可交换吗？可结合吗？ 答：①取a＝2，b＝-1，a?b=2-1?Z，其在Z上不封闭；

②取a＝2，b＝1时，a?b=ab=2，b?a=ba=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上可结合．

10、设无向图G?V,E有12条边，已知有6个3度顶点，其余顶点的度数均小于3，问G中至少有多少个顶点？

答：设G中度数小于3的顶点有k个，则由欧拉定理

?deg(v)?24知，

v?V度数小于3 的顶点度数之和为6，故当其余的顶点度数都为2时，G的顶点最少， 即G中至少有9个顶点.

11、n取怎样的值，无向完全图Kn有一条欧拉回路? 答： n为奇数，?v∈V，deg(v)=n-1为偶数， 所以，当n是大于或等于3的奇数时，Kn有欧拉回路.

12、判断下列无向图是否存在欧拉路径？是否为欧拉图？说明理由.

EAFBDC

答：d(A)=2, d(B) =d(C)= d(D)=4 d(E) =d(F)=3 只有两个奇数度的结点, 有欧拉路径，如EDBEFCABCDF ； 由于每个结点的次数不均为偶数，所以不是欧拉图.

13、判断下列图是否为欧拉图？说明理由，是否存在哈密尔顿回路？ ? ? ?

? ?

答：一个无向图D是欧拉图?D是连通的，且所有顶点的度等于偶数，

所以是欧拉图，但无哈密尔顿回路．

14、判断下列图是否存在欧拉路径？是否为欧拉图？说明理由. ABDC

答：一个有向图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

主析取范式A??(2) ；主合取范式A??(0,1,3). 2、对命题公式 A?(p?q)?r，要求 （1）用0或1填补其真值表的空格处；（2）求该命题公式的主析取范式与主合取范式. 解：

p q p?q A r 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

主析取范式A??(1,3,4,7) ；主合取范式A??(0,2,5,6).

a a b c b b c a c c a b 3、设代数系统，其中A=?a,b,c?，?是A上的二元运算，由下列表给出，试列表分别

讨论交换性、幂等性、么元和逆元． ? a b c 解：

交换律 有 幂等律 无 么元 a 逆元 a –1= a, b –1= c, c –1= b 4、设代数系统，其中A=?a,b,c?，?是A上的二元运算，由下列表给出，试列表分别讨论交换性、幂等性、么元和逆元． ? a b c a a a a b b b b c c c c 解：

交换律 有 幂等律 无 么元 a 逆元 a –1= a, b –1= b

五、计算问答题（每题10分）

1、集合A?{1,2,3,4}上的关系

R?{?1,1?,?1,3?,?2,2?,?3,3?,?3,1?,?3,4?,?4,3?,?4,4?}，写出关系矩阵MR，画出关系图并讨论R的五种性质．

?1010????0100?解：R的关系矩阵为MR?? ，R的关系图为 ?1011???0011???因MR对角元皆为1，故R是自反的，不是反自反的；因MR为对称矩阵，故R是对称的； 因?1,3?,?3,1??R，故R不是反对称的；

又因?1,3?,?3,4??R，但?1,4??R，故R无传递性． 2、设R是集合A?{1,2,3,4}上的二元关系，

R?{?1,1?,?1,2?,?1,3?,?3,1?,?3,2?,?3,3?,?4,1?,?4,2?,?4,3?}， 写出关系矩阵MR，画出关系图并讨论R的五种性质．

?1110???0000?，R的关系图为 解：R的关系矩阵为MR???1110???1110??因MR对角元不全为1，也不全为0，故R不是自反的，也不是反自反的；

因MR为非对称矩阵，故R是反对称的，不是对称的；因R?R，故R是传递的． 3、有向图G如图9.27所示， ⑴ 求G的邻接矩阵；

⑵ 根据邻接矩阵求各结点的出度和入度；

⑶ 求G中长度为3的路的总数，其中有多少条回路； ⑷ 求G的可达性矩阵．

2?0?1解：⑴MR=??0??0＋

110??000?； ?101?000?4?4－

＋

－

⑵deg(v1)=2，deg(v1)=1，deg(v2)=1，deg(v2)=2，

＋－＋－

deg(v3)=2，deg(v3)=1，deg(v4)=0，deg(v4)=1；

?1?0⑶ A2=??1??0101??1??110?1 ，A3=??0000???000?4?4?0110??101? ，

110??000?4?4长度为3的路有8条，其中回路3条；

?3?2⑷ C3=A0+A1+A2+A3=??1??0

332021201??1??1?1 P=??11???1?4?4?0111??111?．

111??001?4、有向图D??V,E?，其中结点集V?{v1,v2,v3,v4}，有向边集E可表示为：

E?{?v1,v2?,?v2,v3?,?v3,v1?,?v3,v2?,?v3,v4?,?v4,v1?,?v4,v2?} （1） 求D的邻接矩阵A；（2）求D的可达性矩阵P；

（3）说明v2到v3长度为4的路径有几条？（4）v2到其它各顶点长度为3的路径有几条？

?0?0解：（1）A???1??1?00?11（2）A2???12??01101101001011R4?A?A2?A3?A40?0?? ； 1??0?0??1101??1210??1210??1221?1??，A4???，A3??? ?1221??3422?0??????11110?2311?????1111??2421??1111??3542?? ； ?，P?????1111??6954?????11114632????（3）v2到v3长度为4的路径有2条 ； （4）v2到其它各顶点长度为3的路径有2条． 5、有向图D??V,E?，其中结点集V?{v1,v2,v3,v4}，

有向边集E?{?v1,v2?,?v1,v3?,?v1,v4?,?v2,v1?,?v4,v2?,?v4,v3?} （1）求D的邻接矩阵A；（2）求D的可达性矩阵P；

（3）说明D中经过v1长度为3的回路有几条？ （4）说明D中v1到v3长度为4的路径有几条？ （5）说明D中v1到v3所有的路径有几条？

?0?1解：（1） A???0??0?11?012（2）A???00??10111?000?? ； 000??110?10??1?111?3?，A???000???00??0111??1?1110?4?，A???0000???111??1210121011?1??， 0??0?111?111??； 000??111?（3）D中经过v1长度为3的回路有1条；（4）D中v1到v3长度为4的路径有2条；

（5）D中v1到v3所有的路径有5条.

?3?3R4?A?A2?A3?A4???0??2530353033??1?12??，P???00???1??1四、证明计算题（每题10分）

1、设A?{1,2,3,4}，在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?{?a,b??a,b??A?A,a?b?2}?{?1,3?,?2,4?},

A?A/R?{[?1,1?]R,[?1,2?]R,[?2,1?]R,[?1,3?]R,[?3,1?]R,[?1,4?]R,[?4,1?]R}．

d?b?c， 2、设A?{1,2,3,4}，在A?A上定义R:??a,b?,?c,d???R? 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，

e，???a,b?,?e,f???R,即R传递； 有 a?f?b? 综上得出，R是A?A上的等价关系，

且[?2,4?]R?{?a,b??a,b??A?A,2a?b}?{?1,2?,?2,4?},

A?A/R?{[?1,1?]R,[?1,2?]R,[?2,1?]R[?1,3?]R,[?3,1?]R,[?1,4?]R,[?4,1?]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)，所以*是可结合运算；

在中，对于任何实数a，都有0*a=a*0=0+a+0·a=a 故0是中的么元，是独异点；

对中任何实数a，都有(?1)*a=a*(?1)=(?1)+a+(?1)·a=?1， ?1是中的零元． 4、某无向连通图G中有10条边，二个2度顶点，二个3度顶点，一个4度顶点，其余顶点的度数都是1，求G的顶点个数，并证明G为树.

解：设G中度数为1的顶点个数为x

由握手定理知x?2?2?2?3?4?2?10 解得x?6

于是G中的顶点个数为x?2?2?1?11

因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) (拒取式)

T(3)，(6) (合取式) (7) (p?q)?(q?p)

(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)．

P 证明：⑴?xR(x)

T⑴（US） ⑵R(c)

P ⑶?x(G(x)??R(x))

T⑶（US） ⑷G(c)??R(c)

T⑵，⑷（拒取式） ⑸?G(c)

P ⑹?x(F(x)?G(x))

T⑹（US） ⑺F(c)?G(c)

T⑸，⑺（析取三段论） ⑻F(c)

T⑻（UG）⑼?xF(x) ．

4、用逻辑推理规则证明：?xF(x)??y(F(y)?G(y)?R(y)),?xF(x)??xR(x)．

P 证明：⑴?xF(x)

T⑴（ES） ⑵F(c)

P ⑶?xF(x)??y(F(y)?G(y)?R(y))

T⑴，⑶（假言推理） ⑷?y(F(y)?G(y)?R(y))

T⑷（US） ⑸F(c)?G(c)?R(c)

T⑵（加法式） ⑹F(c)?G(c)

T⑸，⑹（假言推理） ⑺R(c)

T⑺（EG）⑻?xR(x) ．

5、用逻辑推理规则证明： ?x(P(x)?Q(x))??xP(x)??xQ(x).

P（附加前提） 证明：⑴?xP(x)

T⑴（ES） ⑵P(a)

P ⑶?x(P(x)?Q(x))

T⑶（US） ⑷P(a)?Q(a)

T⑵，⑷（假言推理） T⑸（EG） ⑹?xQ(x)

CP． ⑺?xP(x)??xQ(x)

6、设R为集合A上的二元关系，如果R是反自反的和可传递的，则R一定是反对称的． 证明：假设R不是反对称的，则 ??x,y??R,?y,x??R,x?y 由R的传递性知， ?x,x??R ，此与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上的偏序关系．

⑸Q(a)

9、设R是S上的等价关系，证明：R是S上的等价关系．

?1证明：（1）因R在S上的自反性，有IS?R，则IS?IS?R?1，有R在S上自反；

?1?1（2）因R在S上的对称性，有R?1?R，则(R?1)?1?R?R?1，有R?1在S上对称；

?12?（3）因R在S上的传递性，有R?R，则(R?1)2?R，有R在S上可传递； ?R?R12则R'2?(R'?R)?(R'?(S'?S'))?R?(S'?S')?R'，有R'在S'上是对称的； 综上所述，可证R是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*(由于0是么元，所以a的逆元是

?111?1)=(a +1)(?1+1)?1=0 a?1a?11?1；综上证明，是群． a?112、是个群，u∈G，定义G中的运算“?”为a?b=a*u*b，对任意a，b∈G， 求证：也是个群．

-1

证明：1）?a，b∈G，a?b=a*u*b∈G，运算是封闭的；

-1-1-1-1

2）?a，b，c∈G，（a?b）?c=（a*u*b）*u*c=a*u*（b*u*c）=a?（b?c），运算可结合；

-1

3）?a∈G，设E为?的单位元，则a?E=a*u*E=a，得E=u，存在么元u；

-1-1-1-1

4）?a∈G，a?x=a*u*x=E，x=u*a*u，则x?a=u*a*u*u*a=u=E，各元素都有逆元； 所以也是个群．

13、设图G=，|V|=n，|E|=m，k度顶点有nk个，且各顶点或是k度点或是k+1度点，证明：nk= (k+1)n -2m.

证明：由已知可知，G中k+1度顶点为n-nk个。再由欧拉握手定理可知

2m=

-1

?deg(v)=kn+(k+1)(n-n)=(k+1)n-n，n= (k+1)n -2m.

kkkkv?V14、设G=?V,E?是图，|V|=n，|E|=m，证明：?(G)≤

2m≤?(G) . nnn证明：根据最小度的定义，?v?V，deg(v)≥?(G)，所以，2m=?deg(v)≥???G?=n?(G)

i?1i?1即 n?(G) ≤2m，整理后得，?(G)≤

2m n另一方面，根据最大度的定义，?v?V，deg(v)≤?(G)，与前面推理类似的可得，2m≤n?(G) 整理后得，?(G)≥

2m2m，,所以， ?(G)≤≤?(G) . nn15、设图G有n个结点，n＋1条边，证明：G中至少有1个结点度数大于等于3. 证明：用反证法，设G=?V,E?，?v∈V，deg(v)≤2，

所有结点的度数之和2(n+1)小于2n。即2(n+1)≤2n，化简后，2≤0，矛盾， 所以，G中至少有1个结点度数大于等于3.

本文来源：https://www.bwwdw.com/article/9j2r.html