离散数学期末复习题

离散数学期末复习题

一、选择题

1、永真式的否定是（2） (2) 永假式

2、设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，则下列真命题为(1) (1)P?Q?R

3、设P：我听课，Q：我看小说，则命题R“我不能一边听课，一边看小说”的符号化为⑵ ⑵P??Q(3)

提示：R??(P?Q)?P??Q 4、下列表达式错误的有⑷ ⑷P?(?P?Q)?P?Q 5、下列表达式正确的有⑷ ⑷?(P?Q)??Q

6、下列联接词运算不可交换的是(3) (3)?

6、设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y，则命题“有的人喜欢所有的花”的逻辑符号化为⑷ ⑷?x(M(x)??y(F(y)?H(x,y))

7、设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些

老

师”的逻辑符号化为⑵

⑵?x(L(x)??y(J(y)?A(x,y)))

8、谓词公式?x(P(x)??yR(y))?Q(x)中的 x是⑶ ⑶既是自由变元又是约束变元 9、下列表达式错误的有⑴

⑴?x(A(x)?B(x))??xA(x)??xB(x) 10、下列推导错在⑶

①?x?y(x?y) P

②?y(z?y) ③(z?Cz) ④?x(x?x) ⑶④

11、下列推理步骤错在⑶

①?x?yF(x,y)

②?yF(z,y) ③F(z,c) ④?xF(x,c) ⑤?y?xF(x,y) ⑶③→④

US① ES② UG③

P US① ES② UG③ EG④

12、设个体域为{a,b}，则?x?yR?x,y?去掉量词后，可表示为⑷

⑷?R?a,a??R?a,b????R?b,a??R?b,b??

提示：原式??yR?a,y???yR?b,y??R?a,a??R?a,b??R?b,a??R?b,b? 二、填充题

1、一个命题含有n个原子命题，则对其所有可能赋值有2 种。

- 1 -

n????2、n个命题变元可产生2个互不等价的极小项，其中，任意两个不同极小项的合取式为矛盾式（永假式），而全体极小项的析取式为重言式（永真式），n个命题变元可构造包括F的不同的主析取范式类别为2。

3、n个命题变元可产生2个互不等价的极大项，其中，任意两个不同极大项的析取式为重言式（永真式），而全体极小项的合取式为矛盾式（永假式），n个命题变元可构造包括T的不同的主合取范式类别为2。

5、公式?(P?Q)?(P??(Q??S))的对偶公式为?(P?Q)?(P??(Q??S))。 6、设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的逻辑符号可化为S?P?Q?R 。 7、P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为?P?Q； “虽然你努力了，但还是失败了”的翻译为P?Q。

8、令A(x)：x会叫，B(x)：x是狗，C(x)：x会咬人，则命题“会叫的狗未必会咬人” 的符号化为?x(A(x)?B(x)??C(x))。

9、设P(x)：x是大象，Q(x)：x是老鼠，R(x,y)：x比y重，则命题“大象比老鼠重”的符号化为?x?y(P(x)?Q(y)?R(x,y))。

10、令A（x）:x是自然数，B（x,y）：x 小于y，则命题“存在最小的自然数” 的符号化为?x(A(x)??y(A(y)??B(y,x)。

三、计算题

1、用真值表方法判断下列公式的类型，并求（3）的主析取范式与主合取范式

（1）（P?Q）?（?P∨Q）； （2）?（P?Q）∧Q； （3）（P?Q）∧?R；

解 （1）、（2）和（3）的真值表如表1、表2和表3所示：

表1 P Q P?Q ?P∨Q （P?Q）?（P∨Q） 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 表2 P Q P?Q ?（P?Q） ?（P?Q）∧Q 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 表3 P Q R P?Q ?R （P?Q）∧?R 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 0 由上述真值表可知，（1）为永真式，（2）为永假式，（3）为可满足式。

- 2 -

2nnn2n（3）的主析取范式为：?(0,2,6)；其主合取范式为?(1,3,4,5,7)。

2、给定解释I：D={2，3}，L（x,y）为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求谓词合式公式?y?xL(x,y)的真值。

解：?y?xL(x,y)??y(L(2,y)?L(3,y))?(L(2,2)?L(3,2))?(L(2,3)?L(3,3))

?(1?0)?(0?1)?0?0?0。

3、个体域为{1，2}，求?x?y（x+y=4）的真值。 解：?x?y（x+y=4）??x（（x+1=4）∨（x+2=4））

?（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+2=4）） ?（0∨0）∧（0∨1）?0∧1?0。

四、证明题

1、证明下列逻辑恒等式：

（1）Ｐ?Ｑ? (Ｐ?Ｑ)?(Ｑ?Ｐ) 证明、用真值表法证明

P Q P?Q （P?Q）?（Q?P）

F F T T

F T F F

T F F F

T T T T

由定义可知，这两个公式是等价的。 （2）P?(Q?P)??P?(P??Q)

证明、P?(Q?P)??P?(?Q?P) ?P?(?P??Q)

?P?(?P??Q) ?P?(P??Q) ??P?(P??Q)

（3） (P?Q)?(R?Q)?((P?R)?Q)

证明 ： 左?((?P?Q)?(?R?Q))?((?P??R)?Q)

?(?(P?R)?Q)?(P?R?Q)?右

（4）求证：?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) （5）求证：?x(P(x)?Q(x))∧?xP(x)??x(P(x)∧Q(x))

证明：左??x((P(x)?Q(x)∧P(x))??x((?P(x)∨Q(x))∧P(x))??x(P(x)∧Q(x)) ?右 （6）求证：?x?y(P(x)?Q(y))? ?xP(x)??yQ(y) 证明：?x?y(P(x)?Q(y))??x?y(?P(x)∨Q(y))

??x(?P(x)∨?yQ(y))??x?P(x)∨?yQ(y)???xP(x)∨?yQ(y)??xP(x)??yQ(y)

?证明：左??x?(F?x???G?x?)???x?F?x???G?x????(?xF?x???x?G?x?) ????xF?x????xG?x??????xG?x???xF?x???右

（7）求证：?x?F?x??G?x????xG?x???xF?x? 2、用推理规则证明下列各结论是各前提的有效结论： （1）P→Q，?Q?R，?R，?S?P=>?S 证明：(1) ?R P

(2) ?Q?R P

(3) ?Q T（1），（2）(析取三段论) (4) P→Q P (5) ?P T（3），（4）(拒取式) (6) ?S?P P (7) ?S T（5），（6）(析取三段论)

- 3 -

???

（2）A→(B→C)，C→(?D?E)，?F→(D??E),A=>B→F 证明： (1) A P (2) A→(B→C) P (3) B→C T（1），（2）(假言推理)

(4) B P（附加前提） (5) C T（3），（4）(假言推理) (6) C→(?D?E) 前提 (7) ?D?E T（5），（6）(假言推理) (8) ?F→(D??E) 前提 (9) F T（7），（8）(拒取式) (10) B→F CP

（3）(P→Q)?(R→S)，(Q→W)?(S→X)，?(W?X)，P→R => ?P 证明：（1） P P （假设前提）

（2） P→R P

（3） R T（1），（2）(假言推理) （4） (P→Q)?(R→S) P

（5） P→Q T（4）(化简律) （6） R→S T（4）(化简律) （7） Q T （1），（5）(假言推理) （8） S T（3），（6）(假言推理) （9） (Q→W)?(S→X) P

（10） Q→W T（9）(化简律) （11） S→X T（9）(化简律) （12） W T（7），（10）(假言推理) （13） X T（8），（11）(假言推理) （14） W?X T（12），（13）(合取引入) （15） ?(W?X) P

（16） ?(W?X)?(W?X) T（14），（15）(合取引入) 由（16）得出矛盾式，故?P为原前提的有效结论

（4）?x(P(x)?Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x))

证明(1)?xP(x) P

(2)P(a) T(1)，ES (3)?x(P(x)?Q(y)∧R(x)) P

(4)P(a)?Q(y)∧R(a) T(3)，US

(5)Q(y)∧R(a) T(2)(4) (假言推理) (6)Q(y) T(5) (化简律) (7)R(a) T(5) (化简律)

(8)P(a)∧R(a) T(2)(7) (合取引入) (9)?x(P(x)∧R(x)) T(8)，EG

(10)Q(y)∧?x(P(x)∧R(x)) T(6)(9) (合取引入) （5）(?x)(P(x)?Q(x))?(?x)P(x)?(?x)Q(x) 证明：①?xP(x) P（ 附加前提）

②P(e)

T①ES ③(?x)(P(x)?Q(x)) P ④P(e)?Q(e) T③US

⑤Q(e) T②④(假言推理) ⑥(?x)Q(x)

T⑤EG

- 4 -

⑦(?x)P(x)?(?x)Q(x)

CP

（6）?xP(x)??x(P(x)?Q(x)?R(x)),?xP(x),?xQ(x)??x?y(P(x)?R(y)) 证明：⑴?xP(x)??x(P(x)?Q(x)?R(x))

P ⑵?xP(x)

P

⑶?x(P(x)?Q(x)?R(x)) T⑴⑵(假言推理) ⑷P(e) T⑵ES ⑸?xQ(x) P ⑹Q(d)

T⑸ES ⑺P(d)?Q(d)?R(d) T⑶US ⑻Q(d)?P(d) T⑹（附加律） ⑼R(d) T⑺⑻(假言推理) ⑽P(e)?R(d) T⑷⑼(合取引入) ⑾(?y)(P(e)?R(y)) T⑽EG ⑿(?x)(?y)(P(x)?R(y))

T⑾EG

（7）??x??P(x)?Q(x)????x?P(x)??xQ(x)

证明：（1）??(?x)p(x)?(?x)Q(x)? P（假设前提） （2）??x??P(x)??x?Q(x) T （1） （3）??x??P(x) T（2）(化简律) （4）?P(e) T（3）ES （5）??x??P(x)?Q(x)? P （6）??x???P(x)?Q(x)? T （5） （7）?P(e)?Q(e) T（6）US

（8）Q?e? T (4). (7) (假言推理)

(9) ??x??Q?x? T (2) (化简律) (10)?Q?e? T(9)US

(11)?Q?e??Q?e? T (8) (10) (合取引入) 由（11）得出矛盾式，故??x?P(x)??xQ(x)为原前提的有效结论

- 5 -

五、将下列命题形式化，并证明结论的有效性：

1、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效? 前提: (1) 若A队得第一，则B队或C队获亚军;

(2) 若C队获亚军，则A队不能获冠军; (3) 若D队获亚军，则B队不能获亚军; (4) A 队获第一;

结论: (5) D队不是亚军。

证明、设A：A队得第一;B: B队获亚军;C: C队获亚军;D: D队获亚军; 则前提符号化为A?（B?C），C??A，D??B，A；结论符号化为 ?D。 本题即证明 A?（B?C），C??A，D??B，A??D。 （1） A P （2） A?（B?C） P

（3） B?C T（1），（2）(假言推理) （4） C??A P

（5） ?C T（1），（4）(拒取式) （6） B T（3），（5）(析取三段论) （7） D??B P

（8） ?D T（6），（7）(拒取式) 故该结论有效

2、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好。

解 设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生的集合，则命题可符号化为：?P??x?A(x)，?xA(x)?Q?Q?P。

(1)?P??x?A(x) P (2)?P???xA(x) T(1) (3)?xA(x)?P T(2) (4)?xA(x)?Q P (5)(?xA(x)?Q)∧(Q??xA(x)) T(4)

(6)Q??xA(x) T(5) (化简律)

(7)Q?P T(6)(3) （假言三段论） 3、所有有理数都是实数，某些有理数是整数。因此，某些实数是整数。 解：设Q(x)：x是有理数，R(x)：x是实数，Z(x)：x是整数。

命题形式化：?x(Q(x)?R(x)),?x(Q(x)?Z(x))? ?x(R(x)?Z(x))。

证明：（1）?x(Q(x)?Z(x)) P (2) Q(a)?Z(a) T(1) ES (3) Q(a) T(2) (化简律) (4) ?x(Q(x)?R(x)) P (5) Q(a)?R(a) T(4)US

(6) R(a) T(3)(5) (假言推理) (7) Z(a) T(2) (化简律) (8) R(a)?Z(a) T(6)(7) (合取引入) (9) ?x(R(x)?Z(x)) T (8) EG

集合、关系、函数的重要知识

一、关系的集合运算法则

设R,R1,R2,R3?A?A，则有 1.(R)

?1?1?1?R，??1??，(IA)?1?IA，(A?A)?1?A?A，(R1?R2)?1?R2?R1?1

- 6 -

?1?1?12.(R1?R2)?1?R1?1?R2，(R1?R2)?1?R1?1?R2，(R1?R2)?1?R1?1?R2

3.R1?(R2?R3)?(R1?R2)?R3

4.R1?(R2?R3)?(R1?R2)?(R1?R3)，R1?(R2?R3)?(R1?R2)?(R1?R3) 二、关系特性的判断方法 自反性 非（反）自反性 定义 ?x?A ?x?A 对称性 若x,y?R非（反）对称性 若x,y?R 传递性 若x,y?R 且y,z?R 则x,z?R ?x,x?R?x,x?R 则y,x?R 且x?y 则y,x?R 集合IA?R IA?R?? R?1?R 运算 关系主对角线主对角线元对称矩阵 矩阵 元素全为1 素全为0 关系图中各顶图中各顶点若两顶点间图 点都有环 都无环 有边，必为双 向边 三、关系特性在各种运算下的遗传变异问题 设R,R1,R2?A?A，则有

R?R?1?IA R?R?R2?R 若aij?1，且i?j，若aij?1，ajk?1 则aji?0 若两顶点间有边，必为单向边 则aik?1 若两顶点通过中间点相联，则两顶点间必有直达边 四、函数的性质

设函数f:B?C，g:A?B，

若f,g是单射，则f?g:A?C也是单射； 若f,g是满射，则f?g:A?C也是满射； 若f,g是双射，则f?g:A?C也是双射； 若f?g:A?C是单射，则g是单射； 若f?g:A?C是满射，则f是满射；

若f?g:A?C是双射，则f是满射，g是单射

集合、关系、函数的重要习题

一、选择题

1、下列为真命题的是（B）

A、a?{{a}} B、{a}?{{a}} C、{a}?{{a}} D、{a}?{{a}} 2、下列结果错误的是（B）

- 7 -

A、??{?}?{?} B、??{?}?{?} C、{?}???{?} D、{?}???{?} 3、非空集合X上的空关系?不具备的性质是（A）

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

4、设R为S={1，2，3}上的关系，其关系图如下，则下列为真命题的是（C）

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

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

A、R不自反，也不反自反 B、R不对称，也不反对称 C、R传递 D、R不传递 6、设R，S是集合A上的关系，则下列断言正确的是（A）

A、若R,S自反，则R?S自反 B、若R,S对称，则R?S对称； C、若R,S反自反，则R?S反自反 D、若R,S反对称，则R?S反对称 7、设Z为整数集，下面哪个序偶不够成偏序集（A）

A、?Z,??(?：小于关系) B、?Z,??(?：小于等于关系)

(?：等于关系) D、?Z,?(：整除关系)

8、设A={?，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（C ）

C、?Z,??

9、集合A={1，2，3，4}上的偏序关系图为

则它的哈斯图为（A）

10、下列关系中能构成函数的是（B）

2A、{?x,y?|(x,y?N)?(x?y?10)}；B、{?x,y?|(x,y?R)?(y?x)}；

C、{?x,y?|(x,y?R)?(y?x)}； D、{?x,y?|(x,y?Z)?(x?ymod3)} 11、下列函数是双射的为（A ）

A、f : Z?E , f (x) = 2x B、f : N?N?N, f (n) =

- 8 -

2C、f : R?Z , f (x) = 1 D、f : Z?N, f (x) = | x | （注：Z—整数集，E—偶数集， N—自然数集，R—实数集） 12、下面函数为单射而非满射的是（B）

A、f:R?R,f(x)??x2?2x?1 B、f:Z??R,f(x)?lnx； C、f:R?Z,f(x)?[x] D、f:R?R,f(x)?2x?1 13、下列命题正确的有（C ）

A、若g?f是双射，则f,g都是单射 B、若g?f是双射，则f,g都是满射 C、若g?f是双射，则f是单射, g是满射 D、若g?f是双射，则f是满射, g是单射 二、填充题

1、设M?{x1?x?12,x被2整除，x?Z}，N?{x1?x?12,x被3整除，x?Z}， 则 M?N?{6，12} ，M?N?{2，4，8，10} ，M?N?{2，3，4，8，9，10} 2、集合A?{{?,2},{2}}的幂集?(A)={?,{{?,2}},{{2}},{{?,2},{2}}} 3、?(?(?))?{?,{?}}， ?(?({?}))?{?,{?},{{?}},{?,{?}}} 4、设A??a,b?，则?(A)?A?

???,a?,??,b?,?{a},a?,?{a},b?,?{b},a?,?{b},b?,?A,a?,?A,b?? 5、设关系A={<1,2>,<2 , 4 >,<3 , 3 >} 与 B={<1,3>,<2,4>,<4,2>}, 则A?B= {< 1 , 4 > , < 2 , 2 > }，(A?B)?1?{ < 4 , 2 > } 6、设集合A={1，2，3，4，5}上偏序关系的Hass图为

则集合A上的最大元为1，最小元为无，极大元为1，极小元为4,5，lub为1，glb为无； 其子集B={2，3，4}上的最大元为无，最小元为4，；极大元为2,3，极小元为4 ，lub为1，glb为4

7、偏序集?A,R??的哈斯图为

则R?= {,,,,,,,,,}?IA 8、 设A={1，2，3，4}，S={{1}，{2，3}，{4}}，为A的一个分划，则由S导出的等价关系 R={< 1 , 1 > , < 2 , 2> , < 2, 3 > , < 3 , 2 > , < 3 , 3 > < 4 , 4 > } 9、设|X|=m，|Y|=n，则从X到Y有2mn 种不同的关系，有n 种不同的函数

n2nm10、在一个有n个元素的集合上，可以有2 种不同的关系，有n 种不同的函数，有n! 种 不同的双射

11、设 f，g是自然数集N上的函数?x?N,则f?g(x)?2x?1，g?f(x)?2(x?1)

三、问答、计算、证明题

1、设R是X＝{1，2，3，4}上的二元关系，

R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}

(1)画出R的关系图． (2)写出R的关系矩阵．

(3)说明R是否是自反、反自反、对称、传递的？

- 9 -

f(x)?x?1,g(x)?2x，

解 (1)R的关系图如图所示： (2) R的关系矩阵为：

?1??0M(R)??1??1?101110110??0? ?0?0??(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；

由于对角线上存在非0元，R不是反自反的； 由于矩阵不对称，R不是对称的；

从关系图看出，若两顶点通过中间点相联，则两顶点间必有直达边，所以R是传递的． 2、设X为集合，A＝?(X)－{?}－{X}，且A≠?，若|X|＝n，问

(1)偏序集是否有最大元？ (2)偏序集是否有最小元？

(3)偏序集中极大元和极小元的一般形式是什么？并说明理由。

解：考察?(X)的哈斯图，最底层的顶点是空集，记作第0层，由底向上，第一层是单元集，第二层是二元集，?，由|X|＝n，则第n－1层是X的n－1元子集，第n层是X．

偏序集与偏序集相比，恰好缺少第0层和第n层． A≠?，则偏序集不存在最大元和最小元

因此的极小元就是X的所有单元集，即{x}，x∈X； 而极大元恰好是比X少一个元素，即X－{x}，x∈X． 3、 R?{?1,1?,?1,3?,?2,2?,?3,3?,?3,1?,?3,4?,?4,3?,?4,4?}是集合

A?{1,2,3,4}上的关系，写出关系矩阵MR，画出关系图，问R是A上的等价关系吗？

解：

?1??0MR??1??0?010010110??0? R的关系图为 ?1?1??

R是自反、对称的，但不传递，故不是等价关系．

4、求S={1，2，3，4，5}上的等价关系R，使其诱导划分{{1，2}，{3}，{4，5}}， 画出关系图．

解：R1={1,2}×{1,2}={<1,1>,<1,2>,<2,1>,<2,2>} R2={3}×{3}={<3,3>}

R3={4,5}×{4,5}={<4,4>,<4,5>,<5,4>,<5,5>} R=R1?R2?R3

={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>}．

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

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

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

A B

?12 3 2 4 - 10 -

（2）偶数阶群中阶为2 的元素的个数一定是奇数。

-1-1

证明：（1）设是有限群，则?a?G，有|a|=|a|。且当a 阶大于2时，a?a。故阶数大于2 的元素成对出现，从而其个数必为偶数。 证明：（2）设是偶数阶群，则由于群的元素中阶为1 的只有一个单位元，阶大于2 的元素是偶数个，剩下元素中都是阶为2 的元素。故偶数阶群中阶为2 的元素一定是奇数个。

－1

9、设是由g生成的循环群，则若G为无限循环群，则G只有两个生成元g和g。 证明：因为g是群的生成元，所以对任意的a∈G，存在i∈Z使得a＝g。又a＝(g?1)?i，

－1

所以g也是群的生成元。

－1

再证G只有g和g这两个生成元。假设h也是G的生成元，对G的元素g，存在整数s，使得g＝hs。对于h来说，由g是G的生成元，存在整数t，使得h＝gt。于是，g＝hs＝gst。由G中的消去律得gst?1＝e。因为G是无限群，必有st－1＝0。

－1

从而有s＝t＝1或s＝t＝－1，即h＝g或h＝g。

-1

10、是个群，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，各元素都有逆元。 所以也是个群。

-1

11、设是群，作f:G?G,a?a。证明：f是G的自同构?G是交换群。 证明： ? 设f 是G的自同构。

-1-1-1-1-1-1-1

对?a，b?G，a·b=(b·a)=(f(b) ·f(a))=(f(b·a))=((b·a))=b·a。 故运算·满足交换律 ，即G是可交换群。

i?因为当a?b时，a-1?b-1，即f(a)?f(b)，故f是G到G中的一个单射。

-1-1-1

又对?a?G，有f(a)=(a)=a。故f是G到G上的满射。从而f是G到G上的双射。

-1-1-1-1

对?a，b?G，因为G是可交换群，则 f(a·b)=(a·b)=(b·a)=a·b=f(a)·f(b)。

故f是G 的自同构。

图论部分

一、选择题：

1．欧拉回路是（B）

A. 路径 B. 简单回路 C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路 2．哈密尔顿回路是（C）

A. 路径 B. 简单回路 C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路 3．设G是简单有向图，可达矩阵P(G)刻划下列关系中的是（C） A、点与边 B、边与点 C、点与点 D、边与边

4．下列哪一种图不一定是树（C）。

A.无简单回路的连通图 B. 有n个顶点n-1条边的连通图 C. 每对顶点间都有通路的图 D. 连通但删去一条边便不连通的图 5.下列哪个不是两个图同构的必要条件

A. 结点数目相等B. 边数相等C. 度数相同的结点数目相同D. 两个图都是平面图 6．在有n个结点的连通图中，其边数（B）

A. 最多有n-1条 B. 至少有n-1条 C. 最多有n条 D. 至少有n条 7．下列图为树的是（C）。 A、G1??{a,b,c,d},{?a,a?,?a,b?,?c,d?}? B、G2??{a,b,c,d},{?a,b?,?b,d?,?c,d?}?

- 16 -

C、

G3??{a,b,c,d},{?a,b?,?a,d?,?c,a?}?

D、G4??{a,b,c,d},{?a,b?,?a,c?,?d,d?}? 二、填充题：

1、n阶无向完全图Kn 的边数是(

n(n?1))，每个结点的度数是(n-1)。 22、n个结点的有向完全图边数是(n(n-1))，每个结点的度数是(2n-2)。

?0??13、设有向图G = < V，E >，V?{v1,v2,v3,v4}的邻接矩阵A??1??1?101001001??1?， ?0?0??则v1的入度deg?(v1)= 3 ，v4的出度deg?(v4)=1 ，从v2到v4的长度为2的路有 1 条。

4、一棵无向树的顶点数为n，则其边数为n-1 ，其结点度数之和是2n-2。 5、一个无向图有生成树的充分必要条件是(它是连通图)。

6、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在(2)片树叶。

7、任何连通无向图G至少有(1)棵生成树，当且仅当G 是(树)，G的生成树只有一棵。 8、设T是一棵树，则T是一个连通且(无简单回路)的图。

9、设无向图G有18条边且每个顶点的度数都是3，则图G有(12)个顶点。 10、任一有向图中，度数为奇数的结点有(偶数)个。

11、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（9）。 三、问答题

1、设无向图G=，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？

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

?deg(v)知，度数小于3 的顶点度

v?V数之和为6。故当其余的顶点度数都为2时，G的顶点最少。即G中至少有9个顶点。 2、判断下列图是否为欧拉图？说明理由，存在是否哈密尔顿回路。 解：一个无向图D是欧拉图? D是连通的，且所有顶点的度等于偶数。 所以是欧拉图，但无哈密尔顿回路。

? ? ?

? ?

四、计算题

1、有向图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）说明v1到v3长度为4的路径有几条？ （4）说明v1到其它各顶点长度为3的路径有几条？

?0?1解：（1）A???0??0100110011?0?? 0??0? - 17 -

?3553??1111??3332??1111?234?，P??? （2）R4?A?A?A?A???0000??0000?????23311111????（3）v1到v3长度为4的路径有2条，（4）v1到其它各顶点长度为3的路径有3条.

2、设有如下有向图G=， （1）求G的邻接矩阵；（2）G中v1到v4的长度为4 的通路有多少条？（3）G中经过v1的长度为3 的回路有多少条？（4）G中长度不超过4 的通路有多少条？其中有多少条通路？

?v1 ?v4

?v2 ? v3 ?1?1解：（1）A=??0??0100011010??2?10??，A2=??01???0??0110021101??3

?21??，A3=??00???1??0

2

1004301

2??5

?31??，A4=??01???0??0

3

2007410

4?3?? 0??1?

（2）G中v1到v4的长度为4 的通路有4条； （3）G中经过v1的长度为3 的回路有3条；

（4）G中长度不超过4 的通路有72条，其中有19条回路。 五、证明题

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

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

2m=

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

k

k

k

k

v?V2、设G=是n个顶点的无向图(n>2)，若对任意u,v?V，有d(u)+d(v)? n-2，则G是连通图。

证明：用反证法证明。

若G 不连通，则它可分成两个独立的子图G1和G2，其中

|V(G1)|+|V(G2)|?n ，且G1中的任一个顶点至多只和G1中的顶点邻接，而G2中的任一顶点至多只和G2中的顶点邻接。任取u?V(G1),v?V(G2),则 d(u)?|V(G1)|-1, d(v)?|V(G2)|-1。

故d(u)+d(v) ?(|V(G1)|-1)+(|V(G2)|-1)?|V(G1)|+|V(G2)|-2 =n-2，这与已知矛盾。故G是连通图。

- 18 -

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