2024年3月27日发(作者：湖南高考一卷数学试卷分析)
《离散数学》练习题和参考答案
一、选择或填空（数理逻辑部分）
1、下列哪些公式为永真蕴含式？( )
(1)
Q=>Q→P (2)
Q=>P→Q (3)P=>P→Q (4)
P
(P
Q)=>
P 答：（1），（4）
2、下列公式中哪些是永真式？( )
(1)(┐P
Q)→(Q→
R) (2)P→(Q→Q) (3)(P
Q)→P (4)P→(P
Q) 答：（2），（3），（4）
3、设有下列公式，请问哪几个是永真蕴涵式?( )
(1)P=>P
Q (2) P
Q=>P (3) P
Q=>P
Q
(4)P
(P→Q)=>Q (5)
(P→Q)=>P (6)
P
(P
Q)=>
P 答：（2），（3），（4），（5），（6）
4、公式x((A(x)B(y，x)) z C(y，z))D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z
5、判断下列语句是不是命题。若是，给出命题的真值。( )
北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角
形有4条边。 (5) 前进！ (6) 给我一杯水吧！
答：（1） 是，T （2） 是，F （3） 不是
（4） 是，T （5） 不是 （6） 不是
6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。
答：所有人都不是大学生，有些人不会死
7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。
(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校
(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校
答：（1）
QP
（2）
PQ
（3）
PQ
（4）
PQ
8、设个体域为整数集，则下列公式的意义是( )。
(1) xy(x+y=0) (2) yx(x+y=0)
答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0
9、设全体域D是正整数集合，确定下列命题的真值：
(1) xy (xy=y) ( ) (2) xy(x+y=y) ( )
(3) xy(x+y=x) ( ) (4) xy(y=2x) ( )答：（1） F （2） F （3）F （4）T
10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( )
(1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答：（1）
11、命题“2是偶数或-3是负数”的否定是（ ）。 答：2不是偶数且-3不是负数。
12、永真式的否定是（ ）
(1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答：（2）
13、公式(
P
Q)
(
P
Q)化简为（ ），公式 Q
(P
(P
Q))可化简为（ ）。答：
P ，Q
P
14、谓词公式x(P(x) yR(y))
Q(x)中量词x的辖域是（ ）。答：P(x) yR(y)
15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（ ）。
答：
x(R(x)
Q(x))
（集合论部分）
16、设A={a,{a}}，下列命题错误的是（ ）。
(1) {a}
P(A) (2) {a}
P(A) (3) {{a}}
P(A) (4) {{a}}
P(A) 答：(2)
17、在0（ ）
之间写上正确的符号。
(1) = (2)
(3)
(4)
答：(4)
18、若集合S的基数|S|=5，则S的幂集的基数|P(S)|=（ ）。 答：32
19、设P={x|(x+1)
4且x
R},Q={x|5
x+16且x
R},则下列命题哪个正确（ ）
22
(1) Q
P (2) Q
P (3) P
Q (4) P=Q 答：（3）
20、下列各集合中，哪几个分别相等( )。
(1) A1={a,b} (2) A2={b,a} (3) A3={a,b,a} (4) A4={a,b,c}
(5) A5={x|(x-a)(x-b)(x-c)=0} (6) A6={x|x2-(a+b)x+ab=0}
答：A1=A2=A3=A6， A4=A5
21、若A-B=Ф，则下列哪个结论不可能正确？( )
(1) A=Ф (2) B=Ф (3) A
B (4) B
A
答：（4）
22、判断下列命题哪个为真?( )
(1) A-B=B-A => A=B (2) 空集是任何集合的真子集
(3) 空集只是非空集合的子集 (4) 若A的一个元素属于B，则A=B
答：（1）
23、判断下列命题哪几个为正确？( )
(1) {Ф}∈{Ф,{{Ф}}} (2) {Ф}
{Ф,{{Ф}}} (3) Ф∈{{Ф}}
(4) Ф
{Ф} (5) {a,b}∈{a,b,{a},{b}}
答：（2），（4）
24、判断下列命题哪几个正确？( )
(1) 所有空集都不相等 (2) {Ф}
Ф (4) 若A为非空集，则A
A成立。
答：（2）
25、设A∩B=A∩C，
A
∩B=
A
∩C，则B( )C。
于）
26、判断下列命题哪几个正确？( )
(1) 若A∪B＝A∪C，则B＝C (2) {a,b}={b,a}
(3) P(A∩B)
P(A)∩P(B) （P(S)表示S的幂集）
(4) 若A为非空集，则A
A∪A成立。
27、Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确：
答：=（等
答：（2）
(1) A
B，B
C=> A
C (2) A
B，B
C=> A∈B (3) A∈B，B∈C=> A∈C 答：（1）
（二元关系部分）
28、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求(1)R (2) R-1 。
答：（1）R={<1,1>,<4,2>} (2) R
1
={<1,1>,<2,4>}
29、举出集合A上的既是等价关系又是偏序关系的一个例子。( ) 答：A上
的恒等关系
30、集合A上的等价关系的三个性质是什么？( ) 答：自反性、对称
性和传递性
31、集合A上的偏序关系的三个性质是什么？( )
答：自反性、反对称性和传递性
32、设S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝求(1)R
R (2) R-1 。
答：R
R ={〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉}R-1 =｛〈2,1〉，〈1,2〉，〈3,2〉，〈4,3〉｝
33、设Ａ＝｛1，2，3，4，5，6｝，Ｒ是A上的整除关系，求R= {( )}。
答：R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>,<1,3>,<1,4>,
<1,5>,<1,6>,<2,4>,<2,6>,<3,6>}
34、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=2y｝，求(1)R (2) R-1 。
答：（1）R={<1,1>,<4,2>,<6,3>} (2) R
1
={<1,1>,<2,4>,(36>}
35、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求R和R-1的关系矩阵。
1
0
00
00
000
010
100000
000
000100
答：R的关系矩阵=
000
R
1
的关系矩阵=
000000
36、集合A={1,2,…,10}上的关系R={
A}，则R 的性质为（ ）。
(1) 自反的 (2) 对称的 (3) 传递的，对称的 (4) 传递的
（代数结构部分）
37、设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点
答：2，6
38、设A={3,6,9}，A上的二元运算*定义为：a*b=min{a,b}，则在独异点
答：9，3
（半群与群部分）
39、设〈G,*〉是一个群，则
(1) 若a,b,x∈G，a
x=b，则x=( )；
(2) 若a,b,x∈G，a
x=a
b，则x=( )。 答： （1） a
1
b
b
40、设a是12阶群的生成元， 则a2是( )阶元素，a3是( )阶元素。
。
；
（2）
答：
6,4
41、代数系统
单位元
42、设a是10阶群的生成元， 则a4是( )阶元素，a3是( )阶元素。 答：
5，10
43、群
单位元，1
44、素数阶群一定是( )群, 它的生成元是( )。 答：循环群，任
一非单位元
45、设〈G,*〉是一个群，a,b,c∈G，则
(1) 若c
a=b，则c=( )；(2) 若c
a=b
a，则c=( )。
b
46、 >是 >的子群的充分必要条件是( )。 答： >是群 或 a，b G， a b H，a-1 H 或 a,b G，a b-1 H 47、群＜A,*＞的等幂元有( )个，是( )，零元有( )个。 位元，0 48、在一个群〈G,*〉中，若G中的元素a的阶是k，则a-1的阶是( )。 49、在自然数集N上，下列哪种运算是可结合的？（ ） (1) a*b=a-b (2) a*b=max{a,b} (3) a*b=a+2b (4) a*b=|a-b| 50、任意一个具有2个或以上元的半群，它（ ）。 (1) 不可能是群 (2) 不一定是群 (3) 一定是群 (4) 是交换群 51、6阶有限群的任何子群一定不是（ ）。 (1) 2阶 (2) 3 阶 (3) 4 阶 (4) 6 阶 （格与布尔代数部分） 52、下列哪个偏序集构成有界格（ ） (1) （N, ） (2) （Z, ） (3) （{2,3,4,6,12},|（整除关系）） (4) (P(A), ) 53、有限布尔代数的元素的个数一定等于（ ）。 (1) 偶数 (2) 奇数 (3) 4的倍数 (4) 2的正整数次幂 （图论部分） 54、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图 (2) 树 (3) 平面图 (4) 连通图 55、下面给出的集合中，哪一个是前缀码？( ) (1) {0，10，110，101111} (2) {01，001，000，1} 答：（1） b a 1 (2) 答：1，单 答：k (3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011} 56、一个图的哈密尔顿路是一条通过图中( )的路。 答：所有结点一次 且恰好一次 57、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( )。 答：以v为起点的边的条数， 以v为终点的边的条数 58、设G是一棵树，则G 的生成树有( )棵。 (1) 0 (2) 1 (3) 2 (4) 不能确定 59、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 n(n1) 2 答：, n-1 60、一棵无向树的顶点数n与边数m关系是( )。 答： m=n-1 61、一个图的欧拉回路是一条通过图中( )的回路。 答：所有边一次且恰 好一次 62、有n个结点的树，其结点度数之和是( )。 答： 2n-2 63、下面给出的集合中，哪一个不是前缀码( )。 (1) {a，ab，110，a1b11} (2) {01，001，000，1} (3) {1，2，00，01，0210} (4) {12，11，101，002，0011} 答：(1) 64、n个结点的有向完全图边数是( )，每个结点的度数是( )。 答：n(n-1),2n-2 65、一个无向图有生成树的充分必要条件是( )。 答：它是连通图 66、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 答：（3） 67、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。 答：2 68、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。 答：1，树 69、设G是有n个结点m条边的连通平面图，且有k个面，则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 答：（1） 70、设T是一棵树，则T是一个连通且( )图。 答：无简单回路 71、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 答：（4） 72、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12 答：(4) 73、设图G= 答：有向图 74、任一有向图中，度数为奇数的结点有( )个。 答：偶数 75、具有6 个顶点，12条边的连通简单平面图中，每个面都是由( )条边围成？ (1) 2 (2) 4 (3) 3 (4) 5 答：（3） 76、在有n个顶点的连通图中，其边数（ ）。 (1) 最多有n-1条 (2) 至少有n-1 条 (3) 最多有n条 (4) 至少有n 条 答：（2） 77、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ ）。 (1) 5 (2) 7 (3) 8 (4) 9 答：（4） 78、若一棵完全二元（叉）树有2n-1个顶点，则它（ ）片树叶。 (1) n (2) 2n (3) n-1 (4) 2 答：（1） 79、下列哪一种图不一定是树（ ）。 (1) 无简单回路的连通图 (2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图 答：（3） 80、连通图G是一棵树当且仅当G中（ ）。 (1) 有些边是割边 (2) 每条边都是割边 (3) 所有边都不是割边 (4) 图中存在一条欧拉路径 答：（2） （数理逻辑部分） 二、求下列各公式的主析取范式和主合取范式： 1、(P→Q) R 解：(P→Q) R ( P Q ) R ( P R) (Q R) （析取范式） ( P (Q Q) R) (( P P) Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) ( P Q R) ( P Q R) (P Q R)（主析取范式） ((P→Q) R) ( P Q R) ( P Q R) (P Q R) (P Q R) ( P Q R)（原公式否定的主析取范式） (P→Q) R (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R)（主合取范式） 2、(P R) (Q R) P 解： (P R) (Q R) P（析取范式） (P (Q Q) R) ((P P) Q R) ( P (Q Q) (R R)) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) (主析取范 式) （(P R) (Q R) P） (P Q R) (P Q R）（原公式否定的主析取范式） (P R) (Q R) P ( P Q R) ( P Q R)（主合取范式） 3、( P→Q) (R P) 解：( P→Q) (R P) (P Q) (R P)（合取范式） (P Q (R R)) (P (Q Q)) R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R)（主合取范式） (( P→Q) (R P)) (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R)（原公式否定的主合取范式） ( P→Q) (R P) ( P Q R) (P Q R) (P Q R) (P Q R) (P Q R) （主析取范式） 4、Q→(P R) 解：Q→(P R) Q P R（主合取范式） （Q→(P R)） ( P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R）（原公式否定的主合取范式） Q→(P R) (P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R）（主析取范式） 5、P→(P (Q→P)) 解：P→(P (Q→P)) P (P ( Q P)) P P T (主合取范式) ( P Q) ( P Q) (P Q) (P Q)（主析取范式） 6、 (P→Q) (R P) 解： (P→Q) (R P) ( P Q) (R P) (P Q) (R P)（析取范式） (P Q (R R)) (P ( Q Q) R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R)（主析取范式） ( (P→Q) (R P)) (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R)（原公式否定的主析取范式） (P→Q) (R P) ( P Q R) (P Q R) (P Q R) (P Q R) (P Q R)（主合取范式） 7、P (P→Q) 解：P (P→Q) P ( P Q) (P P) Q T(主合取范式) ( P Q) ( P Q) (P Q) (P Q)（主析取范式） 8、(R→Q) P 解：(R→Q) P ( R Q ) P ( R P) (Q P) （析取范式） ( R (Q Q) P) (( R R) Q P) ( R Q P) ( R Q P) ( R Q P) (R Q P) (P Q R) (P Q R) (P Q R)（主析取范式） ((R→Q) P) ( P Q R) ( P Q R） (P Q R) ( P Q R) ( P Q R)（原公式 否定的主析取范式） (R→Q) P (P Q R) (P Q R) ( P Q R) (P Q R) (P Q R)（主合取范式） 9、P→Q 解：P→Q P Q（主合取范式） ( P (Q Q)) (( P P) Q) ( P Q) ( P Q) ( P Q) (P Q) ( P Q) ( P Q) (P Q)（主析取范式） 10、 P Q 解： P Q （主合取范式） (P ( Q Q)) (( P P) Q） (P Q) (P Q) ( P Q) (P Q） (P Q) (P Q) ( P Q)（主析取范式） 11、P Q 解：P Q（主析取范式） (P (Q Q)) ((P P) Q) (P Q) (P Q) (P Q) ( P Q) (P Q) (P Q) ( P Q)（主合取范式） 12、（P R） Q 解：（P R） Q (P R) Q ( P R) Q ( P Q) ( R Q)（合取范式） ( P Q (R R)) (( P P) Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) ( P Q R) ( P Q R) (P Q R)（主合取范式） （P R） Q ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R) 范式） （P R） Q (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R)（主析取范式） 13、（P Q） R 解：（P Q） R ( P Q) R （原公式否定的主析取 (P Q) R(析取范式) (P Q (R R)) ((P P) (Q Q) R) (P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R)(主析取范式） （P Q） R ( P Q) R (P Q) R(析取范式) (P R) ( Q R)(合取范式) (P (Q Q) R) ((P P) Q R) (P Q R) (P Q R) (P Q R) ( P Q R) (P Q R) (P Q R) ( P Q R)(主合取范式) 14、(P (Q R)) ( P ( Q R)) 解：(P (Q R)) ( P ( Q R)) ( P (Q R)) (P ( Q R)) ( P Q) ( P R) (P Q) (P R)（合取范式） ( P Q (R R)) ( P (Q Q) R) (P Q (R R)) (P (Q Q) R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R)(主合取范式) (P (Q R)) ( P ( Q R)) ( P Q R) (P Q R)(原公式否定的主合取范式) (P (Q R)) ( P ( Q R)) (P Q R) ( P Q R)(主析取范式) 15、P ( P (Q ( Q R))) 解：P ( P (Q ( Q R))) P (P (Q (Q R))) P Q R(主合取范式) (P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) (原公式否定的主合取范式) (P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R) (P Q R)(主析取范式) 16、(P Q) (P R) 解、(P Q) (P R) ( P Q) ( P R) (合取范式) ( P Q (R R) ( P ( Q Q) R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R)(主合取范式) (P Q) (P R) ( P Q) ( P R) P (Q R)(合取范式) ( P (Q Q) (R R)) (( P P) Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) (主析取范式) 三、证明： 1、P→Q， Q R， R， S P=> S 证明： (1) R 前提 (2) Q R 前提 Q （1），（2） P→Q 前提 P （3），（4） S P 前提 (7) S （5），（6） 2、A→(B→C)，C→( D E)， F→(D E),A=>B→F 证明： (1) A 前提 (2) A→(B→C) 前提 (3) B→C （1），（2） (4) B 附加前提 C （3），（4） C→( D E) 前提 D E （5），（6） F→(D E) 前提 F （7），（8） B→F CP 3、P Q， P→R, Q→S => R S 证明： (1) R 附加前提 (2) P→R 前提 (3) P （1），（2） (4) P Q 前提 (5) Q （3），（4） (6) Q→S 前提 (7) S （5），（6） (8) R S CP，（1），（8） 4、(P→Q) (R→S)，(Q→W) (S→X)， (W X)，P→R => P 证明： （1） P 假设前提 （2） P→R 前提 （3） R （1），（2） （4） (P→Q) (R→S) 前提 （5） P→Q （4） （6） R→S （5） （7） Q （1），（5） （8） S （3），（6） （9） (Q→W) (S→X) 前提 （10） Q→W （9） （11） S→X （10） （12） W （7），（10） （13） X （8），（11） （14） W X （12），（13） （15） (W X) 前提 （16） (W X) (W X) （14），（15） 5、(U V)→(M N), U P, P→(Q S)， Q S =>M 证明： (1) Q S 附加前提 P→(Q S) 前提 P （1），（2） U P 前提 U （3），（4） U V （5） (U V)→(M N) 前提 M N (6),(7) M （8） 6、 B D，(E→ F)→ D， E=> B 证明： (1) B 附加前提 (2) B D 前提 (3) D （1），（2） (4) (E→ F)→ D 前提 (5) (E→ F) （3），（4） (6) E F （5） (7) E （6） (8) E 前提 (9) E E （7），（8） 7、P→(Q→R)，R→(Q→S) => P→(Q→S) 证明： （1） P 附加前提 （2） Q 附加前提 （3） P→(Q→R) 前提 （4） Q→R （1），（3） （5） R （2），（4） （6） R→(Q→S) 前提 （7） Q→S （5），（6） （8） S （2），（7） （9） Q→S CP，（2），（8） （10） P→(Q→S) CP，（1），（9） 8、P→ Q， P→R，R→ S =>S→ Q 证明： （1） S 附加前提 （2） R→ S 前提 （3） R （1），（2） （4） P→R 前提 （5） P （3），（4） （6） P→ Q 前提 （7） Q (5），（6） （8） S→ Q CP，（1），（7） 9、P→(Q→R) => (P→Q)→(P→R) 证明： (1) P→Q 附加前提 (2) P 附加前提 (3) Q (1),(2) (4) P→(Q→R) 前提 (5) Q→R (2),(4) (6) R (3),(5) (7) P→R CP,(2),(6) (8) (P→Q) →(P→R) CP,(1),(7) 10、P→( Q→ R)，Q→ P,S→R,P => S 证明： （1） P 前提 （2） P→( Q→ R) 前提 （3） Q→ R (1)，(2) （4） Q→ P 前提 （5） Q (1)，(4) （6） R (3),(5) （7） S→R 前提 （8） S (6)，(7) 11、A，A→B， A→C， B→(D→ C) => D 证明： （1） A 前提 （2） A→B 前提 （3） B (1)，(2) （4） A→C 前提 （5） C (1)，(4) （6） B→(D→ C) 前提 （7） D→ C (3)，(6) （8） D (5)，(7) 12、A→(C B)，B→ A，D→ C => A→ D 证明： （1） A 附加前提 (2) A→(C B) 前提 (3) C B （1），（2） B→ A 前提 B （1），（4） C （3），（5） D→ C 前提 D （6），（7） A→ D CP，（1），（8） 13、(P Q) (R Q) （P R） Q 证明、 (P Q) (R Q) ( P Q) ( R Q) ( P R) Q （P R） Q (P R) Q 14、P (Q P) P (P Q) 证明、 P (Q P) P ( Q P) ( P) ( P Q) P (P Q) 15、（P Q） （P R）， (Q R)，S P S 证明、 (1) （P Q） （P R） 前提 （2） P (Q R) (1) （3） (Q R) 前提 （4） P （2），(3) (5) S P 前提 (6) S (4),(5) 16、P Q，Q R，R S P 证明、 (1) P 附加前提 （2） P （4） Q Q 前提 R 前提 S 前提 （3） Q （1），（2） (5) R （3），（4） (6 ) R （7） R （6） （8） R R （5），（7） 17、用真值表法证明Ｐ Ｑ (Ｐ Ｑ) (Ｑ Ｐ) 证明、 列出两个公式的真值表： P Q P Q （P Q） （Q P） F F T T F T F F T F F F T T T T 由定义可知，这两个公式是等价的。 18、P→Q P→(P Q) 证明、 设P→(P Q)为F，则P为T，P Q为F。所以P为T，Q为F ，从而P→Q也为F。所以P→Q P→(P Q)。 19、用先求主范式的方法证明(P→Q) (P→R) (P→（Q R） 证明、 先求出左右两个公式 的主合取范式 (P→Q) (P→R) ( P Q) ( P R) ( P Q (R R))) ( P (Q Q) R) ( P Q R) ( P Q R) ( P Q R) ( 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 R)) ( P (Q Q) R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) 它们有一样的主合取范式，所以它们等价。 20、(P→Q) 证明、 设(P→Q) (Q R) P (Q R)为T，则P→Q和 (Q R)都为T。即P→Q和 Q R都为T。故P→Q， Q和 R)都为T，即 (Q R) P P→Q为T，Q和R都为F。从而P也为F，即 P为T。从而(P→Q) 21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效? 前提: (1) 若A队得第一，则B队或C队获亚军; 若C队获亚军，则A队不能获冠军; 若D队获亚军，则B队不能获亚军; 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 前提 （2） A （B C）前提 （3） B C （1），（2） （4） C A 前提 （5） C （1），（4） （6） B （3），（5） （7） D B 前提 （8） D （6），（7） 22、用推理规则证明P Q, (Q R),P R不能同时为真。 证明、 (1) P R 前提 (2) P (1) (3) P Q 前提 (4) Q (2),(3) (5) (Q R) 前提 (6) Q R (5) (7) Q (6) (8) Q Q (4),(7) (集合论部分) 四、设Ａ，Ｂ，Ｃ是三个集合，证明： 1、A (B－C)＝(A B)－(A C) 证明： (A B)－(A C)= (A B) AC =(A B) （ A C ） =(A B A ) (A B C )= A B C =A （B C ） =A （B-C） 2、(A－B) (A－C)=A－(B C) 证明： (A-B) (A-C)=(A B ) (A C ) =A ( B C ) =A BC = A-(B C) 3、A B=A C， A B= A C，则C=B 证明： B=B ( A A)=(B A ) (B A) =(C A ) (C A)=C ( A A)=C 4、A B=A (B-A) 证明： A (B-A)=A (B A )=(A B) (A A ) =(A B) U= A B 5、A=B A B= 证明： 设A=B，则A B=（A-B） （B-A）= = 。 设A B= ，则A B=（A-B） （B-A）= 。故A-B= ，B-A= ，从而A B，B A，故A=B。 6、A B = A C，A B=A C，则C=B 证明： B=B (A B)= B (A C)= (B A) (B C) = (A C) (B∩C)= C (A B) = C (A C) =C 7、A B=A C， A B= A C，则C=B 证明： B=B (A A )=(B A) (B A ) =(C A) (C A )=C (A A ) =C 8、A－(B C)＝(A－B)－C 证明： A－(B C)= A BC =A ( B C )=(A B ) C =(A-B) C =(A-B)-C 9、(A－B) (A－C)=A－(B C) 证明： (A-B) (A－C) =(A B ) (A C ) =(A A) ( B C ) =A BC =A－(B C) 10、A-B=B，则A=B= 证明： 因为B=A-B，所以B=B B=（A-B） B= 。从而A=A-B=B= 。 11、A=(A-B) (A-C) A B C= 证明： 因为(A-B) (A-C) =(A B ) (A C ) =A ( B C ) =A BC = A-(B C)，且A=(A-B) (A-C)， 所以A= A-(B C)，故A B C= 。 因为A B C= ，所以A-(B C)=A。而A-(B C)= (A-B) (A-C)， 所以A=(A-B) (A-C)。 12、(A-B) (A-C)= A B C 证明： 因为(A-B) (A-C) =(A B ) (A C ) =A ( B C ) =A BC = A-(B C)，且(A-B) (A-C)= ， 所以 = A-(B C)，故A B C。 因为A B C，所以A-(B C)=A。而A-(B C)= (A-B) (A-C)， 所以A=(A-B) (A-C)。 13、(A-B) (B-A)=A B= 证明： 因为(A-B) (B-A)=A，所以B-A A。但(B-A) A= ，故B-A= 。 即B A，从而B= （否则A-B A，从而与(A-B) (B-A)=A矛盾）。 因为B= ，所以A-B=A且B-A= 。从而(A-B) (B-A)=A。 14、(A-B)-C A-(B-C) 证明： x (A-B)-C，有 x A-B且x C，即 x A，x B且x C。 从而 x A，x B-C，故x A-(B-C)。从而(A-B)-C A-(B-C) 15、P(A) P(B) P(A B) （P(S)表示S的幂集） 证明： S P(A) P(B)，有S P(A)或S P(B)，所以S A或S B。 从而S A B，故S P(A B)。即P(A) P(B) P(A B) 16、P(A) P(B)=P(A B) （P(S)表示S的幂集） 证明： S P(A) P(B)，有S P(A)且S P(B)，所以S A且S B。 从而S A B，故S P(A B)。即P(A) P(B) P(A B)。 S P(A B)，有S A B，所以S A且S B。 从而S P(A)且S P(B)，故S P(A) P(B)。即P(A B) P(A) P(B)。 故P(A B)=P(A) P(B) 17、（A-B） B=（A B）-B当且仅当B= 。 证明： 当B= 时，因为（A-B） B=（A- ） =A，（A B）-B=（A ）- =A，所以（A-B） B=（A B）-B。 用反证法证明。假设B ，则存在b B。因为b B且b A B，所以b （A B）-B。而显然b （A-B） B。 故这与已知（A-B） B=（A B）-B矛盾。 五、证明或解答： （数理逻辑、集合论与二元关系部分） 1、设个体域是自然数，将下列各式翻译成自然语言： (1) x y（xy=1）; (2) x y(xy=1); (3) x y (xy=0); (4) x y（xy=0）; (5) x y (xy=x); (6) x y（xy=x）; (7) x y z (x-y=z) 答： （1）存在自然数x，对任意自然数y满足xy=1; （2）对每个自然数x，存在自然数y满足xy=1; （3）对每个自然数x，存在自然数y满足xy=0; （4）存在自然数x，对任意自然数y满足xy=1; （5）对每个自然数x，存在自然数y满足xy=x; （6）存在自然数x，对任意自然数y满足xy=x; （7）对任意自然数x,y，存在自然数z满足x-y=z。 2、设A(x,y,z): x+y=z, M（x,y,z）: xy=z, L(x,y): x （1）没有小于0的自然数; （2）x （3）若x （4）存在x，对任意y 使得xy=y; （5）对任意x，存在y使x+y=x。 答： （1） x（G(x,0) M（0,0,x）） 或 x L(x,0) （2） x y z ((L(x,y) L(y,z)) L(x,z)) （3） x y ((L(x,y) z(L(z,0) G(xz,yz))) （4） x yM（x,y,y） （5） x yA(x,y,x) 3、列出下列二元关系的所有元素： （1）A={0,1,2}，B={0,2,4}，R={ AB }; （2）A={1,2,3,4,5}，B={1,2}，R={ x+y 4且x A 且y B}; （3）A={1,2,3}，B={-3,-2,-1,0,1}，R={ A 且y B}; 解： (1) R={<0,0>,<0,2>,<2,0>,<2,2>} (2) R={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>}; (3) R={<1,1>,<1,-1>,<2,-2>,<3,-3>}。 4、对任意集合A,B，证明：若A A=B B，则B=B。 证明： 若B= ，则B B= 。从而A A = 。故A= 。从而B=A。 若B ，则B B 。从而A A 。 对 xB , B B。因为A A=B B，则 A A。从而x A。故B A。 同理可证，A B。 故B=A。 5、对任意集合A,B，证明：若A ，A B=A C，则B=C。 证明： 若B= ，则A B= 。从而A C = 。因为A ，所以C= 。即B=C。 若B ，则A B 。从而A C 。 对 xB ,因为A ，所以存在y A, 使 A B。因为A B=A C，则 A C。从而x C。故B C。 同理可证，C B。 故B=C。 6、设A={a,b}, B={c}。求下列集合： (1) A {0,1} B； (2) B2 A； (3) (A B)2; (4) P(A) A。 解： （1） A {0,1} B={ （2） B2 A={ （3） (A B)2={ （4） P(A) A={< ,a>,< ,b>,<{a},a>,<{a},b>,<{b},a>,<{b},b> , 7、设全集U={a,b,c,d,e}, A={a,d}, B={a,b,c}, C={b,d}。求下列各集合： （1）A B C ； （2） ABC ；（3）(A B ) C; （4）P(A)-P(B); （5）(A-B) (B-C); （6）(A B) C; 解 ： (1) A B C ={a}; (2) ABC ={a,b,c,d,e}; (3) （A B ） C={b,d}; (4) P(A)-P(B)={{d},{a,d}}; (5) (A-B) (B-C)={d,c,a}; (6) (A B) C={b,d}。 8、设A,B,C是任意集合，证明或否定下列断言： （1）若A B，且B C，则A C； （2）若A B，且B C，则A C; （3）若A B，且B C，则A C； （4）若A B，且B C，则A C； 证明： (1) 成立。 对 x A, 因为A B，所以x B。又因为B C，所以x C。即A C。 (2) 不成立。反例如下：A={a}, B={a,b},C={a,b,c}。虽然A B，且B C，但A C。 (3) 不成立。反例如下：A={a}, B={{a},b},C={{{a},b},c}。虽然A B，且B C，但A C。 (4) 成立。因为A B, 且B C，所以A C。 9、A上的任一良序关系一定是A上的全序关系。 证明： a，b∈A，则{a,b}是A的一个非空子集。 ≤是A上的良序关系， {a,b}有最小元。若最小元为a，则a≤b；否则 b≤a。从而≤为A上的的全序关系。 10、若R和S都是非空集A上的等价关系，则R S是A上的等价关系。 证明： a∈A，因为R和S都是A上的等价关系，所以xRx且xSx。故xR Sx。从而R S是自反的。 a,b∈A，aR Sb，即aRb且aSb。因为R和S都是A上的等价关系，所以bRa且bSa。故bR Sa。从而R S是对 称的。 a,b,c∈A，aR Sb且bR Sc，即aRb，aSb,bRc且bSc。因为R和S都是A上的等价关系，所以aRc且aSc。故aR Sc。 从而R S是传递的。 故R S是A上的等价关系。 11、设R A×A，则R自反 IA R。 证明： x A， R是自反的， xRx。即 R，故IA R。 x A， IA R， R。即xRx，故R是自反的。 12、设A是集合，R A×A，则R是对称的 R＝R－1。 证明： R ， R是对称的， yRx。即 R，故 R_1 。从而R R-1。 反之 R-1,即 R 。 R是对称的， yRx。即 R， R_1 R。 故R=R-1。 x，y A，若 R ，即 R-1。 R=R-1， R。即yRx，故R是对称的。 13、设A,B,C和D均是集合，R A×B，S B×C，T C×D，则 (1) R (S T)=(R S) (R T)； (2) R (S T) (R S) (R T)； 证明： （1） R (S T)，则由合成关系的定义知 y B，使得 R且 S T。从而 R且 z> S或 R且 T，即 R S或 R T。故 （R S） （R T） 。从而R (S T) （R S） （R T）。 同理可证（R S） （R T） R (S T)。 故R (S T)=（R S） （R T）。 (2) R (S T)，则由合成关系的定义知 y B，使得 R且 S T。从而 R且 z> S且 T，即 R S且 R T。故 （R S） （R T） 。从而R (S T) (R S） （R T）。 14、设〈A,≤〉为偏序集， B A，若B有最大(小)元、上(下)确界，则它们是惟一的。 证明： 设a,b都是B的最大元，则由最大元的定义a b，b a。 是A上的偏序关系， a=b。即B如果有最大元 则它是惟一的。 15、设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质： 1 1 1 2 3 2 3 2 3 解： 000 101 100 ;它是反自反的、反对称的、传递的； （1）R={<2,1>,<3,1>,<2,3>};MR= 011 101 110 ;它是反自反的、对称的； （2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};MR= 011 100 001 ;它既不是自反的、反自反的、也不是对称的、反对称的、传递的。（3）R={<1,2>,<2,1>,<1,3>,<3,3>};MR= 16、设A={1,2,…,10}。下列哪个是A的划分？若是划分，则它们诱导的等价关系是什么？ （1）B={{1,3,6},{2,8,10},{4,5,7}}; （2）C={{1,5,7},{2,4,8,9},{3,5,6,10}}; （3）D={{1,2,7},{3,5,10},{4,6,8},{9}} 解： （1）和（2）都不是A的划分。 （3）是A的划分。其诱导的等价关系是 I A {<1,2>,<2,1>,<1,7>,<7,1>,<2,7>,<7,2>,<3,5>,<5,3>,<3,10>, <10,3>,<10,5>,<5,10>,<4,6>,<6,4>,<4,8>,<8,4>,<6,8>,<8,6>}。 17、R是A={1,2,3,4,5,6}上的等价关系， R=I A {<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>} 求R诱导的划分。 解： R诱导的划分为{{1,5},{2,4},{3,6}}。 18、A上的偏序关系 的Hasse图如下。 下列哪些关系式成立：a b,b a,c e,e f,d f,c f； 分别求出下列集合关于 的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）： (a) A; (b) {b,d}; (c) {b,e}; (d) {b,d,e} a e f b d c 解： (1) b a,c e,d f,c f成立； (2) (a)的极大元为a,e,f,极小元为c;无最大元，c是最小元； 无上界，下界是c;无上确界，下确界是c。 (b)的极大元为b,d,极小元为b,d;无最大元和最小元； 上界是e，下界是c;上确界是e，下确界是c。 (c)的极大元为e,极小元为b;最大元是e，b是最小元； 上界是e，下界是b;上确界是e，下确界是b。 (d)的极大元为e,极小元为b,d;最大元是e，无最小元； 上界是e，下界是c;上确界是e，下确界是c。 （半群与群部分） 19、求循环群C12={e,a,a2,…,a11}中H={e,a4,a8}的所有右陪集。 解： 因为|C12|=12，|H|=3，所以H 的不同右陪集有4 个：H，{a,a5,a9},{a2,a6,a10},{a3,a7,a11}。 20、求下列置换的运算： 解： 1234 1234 1234 2431 4321 1342 （1）= 123456 123456 123456 452631 452631 452631 （2）= 123456 123456 123456 452631 635124 123456 == 32 21、试求出8阶循环群的所有生成元和所有子群。 解： 设G是8阶循环群，a是它的生成元。则G={e,a,a2,..,a7}。由于ak是G的生成元的充分必要条件是k与8互素，故 a,a3,a5,a7是G的所有生成元。 因为循环群的子群也是循环群，且子群的阶数是G 的阶数的因子，故G的子群只能是1 阶的、2阶的、4 阶的或8阶 的。因为|e|=1,|a|=|a3|=|a5|=8,|a2|=|a6|=8, |a4|=2,且G 的子群的生成元是该子群中a的最小正幂，故G的所有 子群除两个平凡子群外，还有{e,a4},{e,a2,a4,a6}。 22、I上的二元运算*定义为： a,b I，a*b=a+b-2。试问 故1n=n-2(n-1)=2-n。从而对任一个k I,k=2-(2-k)=12-k，故1是的生成元。又因为1和3 关于*互为逆元，故3 也 是 23、设 G。令H={x G|a·x=x·a}。试证：H 是G 的子群。 证明： c，d H，则对 c，d HK，c·a=a·c,d·a=a·d。故(c·d) ·a=c·(d·a)=c·(a·d)=(c·a) ·d=(a·c) ·d=a·(c·d)。 从而c·d H。 由于c·a=a·c,且·满足消去律，所以a ·c-1=c-1·a。故c-1 H。 从而H 是G的子群。 24、证明：偶数阶群中阶为2 的元素的个数一定是奇数。 证明： 设 为2 的元素。故偶数阶群中阶为2 的元素一定是奇数个。 25、证明：有限群中阶大于2的元素的个数一定是偶数。 证明： 设 a G，有|a|=|a-1|。且当a 阶大于2时， a a-1。故阶数大于2 的元素成对出现，从而其 个数必为偶数。 26、试求 解： 0是 27、设 G，a e，且a4·b=b·a5。试证a·b b·a。 证明： 用反证法证明。 假设a·b=b·a。则a4·b= a3·（a·b）= a3·(b·a)=(a5·b)·a =(a2·(a·b))·a=（a2·（b·a））·a=((a2·b)·a)·a=(a·(a·b))·(a·a) =(a·(b·a))·a2=((a·b)·a)·a2 =((b·a)·a)·a2=(b·a2)·a2 =b·(a2·a2)=b·a4。 因为a4·b= b·a5，所以b·a5= b·a4。由消去律得，a=e。 这与已知矛盾。 28、I上的二元运算*定义为： a,b I，a*b=a+b-2。试证： 证明： （1） a,b,c I，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4, a*(b*c) =a+(b*c)-2=a+(b+c-2)-2=a+b+c-4。故(a*b)*c= a*(b*c)，从而*满足结合律。 （2）记e=2。对 a I，a*2=a+2-2=a=2+a-2=2*a.。故e=2是I关于运算*的单位元。 （3）对 a I，因为a*（4-a）=a+4-a-2=2=e=4-a+a-2=(4-a)*a。故4-a是a关于运算*的逆元。 综上所述， 29、设 S。令Sa={ai | i I+ }。试证 证明： b，c Sa，则存在k,l I+，使得b=ak,c=al。从而b·c=ak·al=ak+l。因为k+l I+，所以b·c Sa，即Sa关于 运算·封闭。故 30、单位元有惟一逆元。 证明： 设 >是一个群，e是关于运算 的单位元。 若e1,e2都是e的逆元，即e1*e=e且e2*e=e。 因为e是关于运算 的单位元，所以e1=e1*e=e=e2*e=e2。 即单位元有惟一逆元。 31、设e和0是关于A上二元运算*的单位元和零元，如果|A|>1，则e 0。 证明： 用反证法证明。假设e=0。 对A的任一元素a，因为e和0是A上关于二元运算*的单位元和零元， 则a=a*e=a*0=0。即A的所有元素都等于0,这与已知条件|A|>1矛盾。 从而假设错误。即e 0。 32、证明在元素不少于两个的群中不存在零元。 证明：（用反证法证明） 设在素不少于两个的群 >中存在零元 。对 a G, 由零元的定义有 a* = 。 >是群， 关于*消去律成立。 a=e。即G中只有一个元素，这与|G| 2矛盾。故在元素不少于两 个的群中不存在零元。 33、证明在一个群中单位元是惟一的。 证明： 设e1,e2都是群〈G,*〉的单位元。 则e1=e1*e2=e2。 所以单位元是惟一的。 34、设a是一个群〈G，*〉的生成元，则a-1也是它的生成元。 证明： x G，因为a是〈G，*〉的生成元，所以存在整数k，使得x=a k 。 故x=((a) k1 ) 1 =((a 1 )) k1 =(a 1 ) k 。从而a-1也是〈G，*〉的生成元。 35、在一个偶数阶群中一定存在一个2阶元素。 证明： 群中的每一个元素的阶均不为0 且单位元是其中惟一的阶为1的元素。因为任一阶大于2 的元素和它的逆元的阶相等。 且当一个元素的阶大于2 时，其逆元和它本身不相等。故阶大于2 的元素是成对的。从而阶为1的元素与阶大于2 的 元素个数之和是奇数。 因为该群的阶是偶数，从而它一定有阶为2 的元素。 36、代数系统 证明： 设e是该群的单位元。若a是 因为a*e=a，所以a*a=a*e。由于运算*满足消去律，所以a=e。 即G除单位元以外无其它等幂元。 37、设 >是一个群，则对于a,b∈G，必有唯一的x∈G，使得a x=b。 证明： 因为a-1*b∈G，且a*(a-1*b)=(a*a-1)*b=e*b=b，所以对于a,b∈G，必有x∈G，使得a x=b。 若x1,x2都满足要求。即a x1=b且a x2=b。故a x1=a x2。 由于*满足消去律，故x1=x2。 从而对于a,b∈G，必有唯一的x∈G，使得a x=b。 38、设半群 a,b S，（a·b）2=a2·b2。 证明： a,b S，（a·b）2=(a·b)·(a·b)=((a·b)·a)·b =(a·(a·b))·b=((a·a)·b)·b=(a·a)·(b·b)=a2·b2; a,b S，因为（a·b）2=a2·b2，所以(a·b)·(a·b)=(a·a)·(b·b)。故a·((b·a)·b)=a·(a·(b·b))。 由于·满足消去律，所以(b·a)·b=a·(b·b)，即(b·a)·b=(a·b)·b。从而a·b=b·a。故·满足交换律。 39、设群 证明： 对任一a G，由已知可得a*a=e，即a-1=a。 对任一a,b G，因为a*b=(a*b)-1=b-1*a-1=b*a，所以运算*满足交换律。 从而＜G,*＞是交换群。 40、设*是集合A上可结合的二元运算，且 a,b A,若a*b=b*a，则a=b。试证明： （1） a A,a*a=a，即a是等幂元； （2） a,b A,a*b*a=a; （3） a,b,c A,a*b*c=a*c。 证明： （1） a A,记b=a*a。因为*是可结合的，故有b*a=(a*a)*a=a*(a*a)=a*b。由已知条件可得a=a*a。 （2） a,b A,因为由（1），a*(a*b*a)=(a*a)*(b*a)=a*(b*a), (a*b*a)*a=(a*b)*(a*a)=(a*b)*a=a*(b*a)。 故a*(a*b*a)=(a*b*a)*a，从而a*b*a=a。 （3） a,b,c A,（a*b*c）*（a*c）=（（a*b*c）*a）*c=(a*(b*c)*a)*c 且(a*c)*(a*b*c)=a*(c*(a*b*c))=a*(c*(a*b)*c))。 由（2）可知a*(b*c)*a=a且c*(a*b)*c=c， 故（a*b*c）*（a*c）=(a*(b*c)*a)*c=a*c 且(a*c)*(a*b*c)= a*(c*(a*b)*c))= a*c， 即（a*b*c）*（a*c）=(a*c)*(a*b*c)。 从而由已知条件知，a*b*c=a*c。 41、设 G,a a-1。证明：f是G的自同构 G是交换群。 证明： 设f 是G的自同构。对 a，b G，a·b=(b-1·a-1)-1=(f(b) ·f(a))-1=(f(b·a))-1=((b·a)-1)-1=b·a。故 运算·满足交换律 ，即G是可交换群。 因为当a b时，a-1 b-1，即f(a) f(b)，故f是G到G中的一个单一函数。又对 a G，有f(a-1)=(a-1)-1=a。 故f是G到G上的满函数。从而f是G到G上的自同构。 对 a，b G，因为G是可交换群，故f(a·b)=(a·b)-1=(b·a)-1=a-1·b-1=f(a)·f(b)。故f满足同态方程。 从而f是G 的自同构。 42、若群 证明： 由已知可知，G关于H 有两个不同的左陪集H，H1和两个不同的右陪集H，H2。因为H H1= 且H H1=G，H H2= 且H H2=G，故H1=G-H=H2。 对 a G，若a H，则aH=H,Ha=H。否则因为a G-H，故aH H,Ha H。从而aH=Ha=G-H。故H是G的不变子群。 43、设H和K都 是G的不变子群。证明：H K也是G 的不变子群。 证明： 因为H和K都 是G的不变子群，所以H K是G 的子群。对 a G，h H K，有a·h·a-1 a·H·a-1，·h·a-1 a·K·a-1。 因为H和K都 是G的不变子群，所以a·h·a-1 H且a·h·a-1 K。从而a·h·a-1 H K。故H K是G 的不变 子群。 44、设群G的中心为C（G）={a G| x G,a·x=x·a}。证明C（G）是G的不变子群。 证明： 先证C（G）是G的子群。 a,b C（G），对 x G,有a·x=x·a ，b·x=x·b。故（a·b）·x= a·(b·x)= a·(x·b)=(a·x)·b=(x·a)·b=x·(a·b), a-1·x=x·a-1。从而a·b，a-1 C（G）。 故C（G）是G 的子群。 再证C（G）是G的不变子群。 h C(G)，对 a G，记b=a·h·a-1。下证b C(G)。因为h C(G)，所以b=(a·h) ·a-1=（h·a）·a-1=h·(a·a-1)=h C(G)。 故C（G）是G的不变子群。 45、设 证明： 若G是平凡群，则结论显然成立。 否则设 G且a e,记H=（a）(由a生成的G的子群)。显然H {e}，且G没有非平凡子群， 故H=G。从而G一定是循环群，且a是G 的生成元。 若n是合数，则存在大于1 的整数k,m，使得n=mk。记H={e,ak,(ak)2,…,(ak)m-1}，易证H是G 的子群，但1<|H|=m 故H是G 的非平凡子群。这与已知矛盾。从而n是质数。 故G是质数阶的循环群。 综上所述，G是平凡群或质数阶的循环群。 46、设H和K都是G 的有限子群，且|H|与|K|互质。试证：H K={e}。 证明： 用反证法证明。 若H K {e}。则H K是一个元素个数大于1的有限集。 先证H K也是G的子群，从而也是H和K的子群。 a,b H K,则a,b H且a,b K。因为H和K都 是G的子群，故 a·b,a-1 H且a·b,a-1 K。从而a·b H K,a-1 H K。故H K是G的子群，从而也是H和K的子群。 由拉格朗日定理可知，|H K|是|H|和|K|的因子，这与已知矛盾。 47、素数阶循环群的每个非单位元都是生成元。 证明： 设 对G中任一非单位元a。设a的阶为k,则k 1。 由拉格朗日定理，k是p的正整因子。因为p是素数，故k=p。即a的阶就是p，即群G的阶。故a是G的生成元。 48、若 >是可交换独异点，T为S中所有等幂元的集合，则 >是 >的子独异点。 证明： e e=e， e T，即T是S的非空子集。 a,b T, >是可交换独异点, (a b) (a b)=((a b) a) b =(a (b a)) b=（a (a b)） b =((a a) b) b=(a a) (b b) =a b,即a b T。 故 >是 >的子独异点。 n 49、设 >是群，且a∈G的阶为n，k∈I，则|ak|＝ (k,n) ，其中(k,n)为k和n的最大公因子。 证明： nk 记p= (k,n) ,q= (k,n) ,｜ak｜＝m。由n和p的定义，显然有(ak)p=e。故m p且m|p。 又由于akm=e，所以由定理5.2.5知，n|km。即p|qm。但p和q 互质，故p|m。 n 由于p和m都是正整数，所以p=m。即｜ak｜＝ (k,n) 。 50、设 >是有限群，|G|＝n，则 a∈G，|a| n。 证明： a G，由封闭性及|G|=n可知a,a2,…,an,an+1中必有相同的元素，不妨设为ak=am,k 而|a| m-k n。 51、设G＝(a)，若G为无限群，则G只有两个生成元a和a-1； 证明： b G＝(a)，则 n I,使b=an。故b=(a-n)-1=(a-1)-n,从而a-1也是G的生成元。 若c是G的生成元，则 k,m I，分别满足c=ak和a=cm。从而c= (cm)k= cmk。若km 1，则由消去律可知c的阶是 有限的，这与|G|无限矛盾。从而km=1，即k=1,m=1或k=-1,m=-1。故c=a或c=a-1。 从而G只有两个生成元a和a-1。 52、设G＝(a)，{e} H G，am是H中a 的最小正幂，则 （1） H＝(am)； （2） 若G为无限群，则H也是无限群； 证明： （1） b H, k I, 使得b=ak。令k=mq+r, 0 r 则ar=ak-mq=ak a-mq=b (am)-q。 因为b,amH, 且H G，所以ar H。 由于0 r 从而b=(am)q。故am是H的生成元。 （2）因为{e} H，故H的生成元为am （m 0）。因为G是无限群，所以a的阶是无限的，从而am的阶也是无限的， 故H也是无限群。 53、设G＝(a)，|G|＝n，则对于n 的每一正因子d，有且仅有一个d阶子群。因此n阶循环群的子群的个数恰为 n的 正因子数。 证明： n 对n 的每一正因子d，令k= d ,b=ak, H={e,b,b2,…,bd-1}。 因为|a|=n,所以bd=(ak)d=akd=an=e且|b|=d。 从而H中的元素是两两不同的，易证H G。 故|H|=d。所以是G的一个d阶子群。 n 设H1是G的任一d阶子群。则由定理5.4.4知，H1＝(am)，其中am是H1中a 的最小正幂，且|H|= m 。因为|H|=d， n 所以m= d =k，即H=H1。从而H是G的惟一d阶子群。 设H是G的惟一的d阶子群。若d=1 ,则结论显然成立。否则H＝(am)，其中am是H中a 的最小正幂。由定理5.4.4 n 知，d= m 。故d是n的一个正因子。 54、设h是从群 （1） h(e1)=e2； （2） a G1，h(a-1)=h(a)-1； （3） 若H G1，则h(H) G2； （4） 若h为单一同态，则 a G1，|h(a)|=|a|。 证明： (1) 因为h(e1) h(e1)=h(e1 e1)= h(e1)= e2 h(e1),所以h(e1)=e2。 (2) a∈G1，h(a) h(a-1)=h(a a-1)= h(e1)= e2, h(a-1) h(a)=h(a-1 a)= h(e1)= e2,故h(a-1)=h(a)-1。 (3) c,d∈h(H), a,b∈H，使得c=h(a),d=h(b)。故c d=h(a) h(b) =h(a >到 >的群同态，G 1 和G2的单位元分别为e1和e2，则 b)。因为H G，所以a b ∈H ，故c d∈h(H)。又c-1=(h(a))-1=h(a-1)且a-1∈H，故c-1∈h(H)。由定理 5.3.2知h(H) G2。 (4) 若|a|=n,则an=e1。故(h(a))n=h(an)=h(e1)=e2。从而h(a)的阶也有限，且|h(a)| n。 设|h(a)|=m,则h(am)= (h(a))m= h(e1)=e2。因为h是单一同态，所以am=e1。即|a| m。 故|h(a)|=|a|。 若a的阶是无限的，则类似于上述证明过程可以得出，h(a)的阶也是无限的。 故结论成立。 55、有限群G的每个元素的阶均能整除G的阶。 证明： 设|G|=n， a G，则|a|=m。令H={e,a,a2,…,am-1}。 则H是G的子群且|H|=m。由Lagrange定理知|H|能整除|G|，故a的阶能整除G的阶。 56、证明：在同构意义下，只有两个四阶群，且都是循环群。 证明： 在4阶群 G中，由Lagrange定理知，G中的元素的阶只能是1，2或4。阶为1 的元素恰有一个，就是单位元e. 若G有一个4阶元素，不妨设为a，则G=（a）,即G是循环群 ，从而是可交换群。 若G没有4阶元素，则除单位元e外，G的其余3个阶均为2。不妨记为a,b,c。因为a,b,c的阶均为2，故 a-1=a,b-1=b,c-1=c。从而a b a, a b b, a b e,故a b=c。同理可得a c=c a=b, c b=b c=a, b a=c。 57、在一个群 证明： 因为| a |=k，所以ak=e。即（a-1）k=(ak)-1=e。 从而a-1的阶是有限的，且|a-1| k。 同理可证，a的阶小于等于|a-1|。 故a-1的阶也是k。 58、在一个群 B=G，则A=G或B=G。 证明： 用反证法证明。 若A G且B G，则有a A,a B且b B,b A。因为A，B都是G的子群，故a,b G，从而a*b G。 因为a A,所以a 1 A。若a*b A,则b= a 1 *(a*b) A，这与a B矛盾。从而a*b A。 同理可证a*b B。 综合可得a*b A B=G，这与已知矛盾。从而假设错误，得证A=G或B=G。 59、设e是奇数阶交换群 证明： 设G=<{e,a 1 ,a 2 ,…,a 2n },*>，n为正整数。 因为G的阶数为奇数2n+1，所以由拉格朗日定理知G中不存在2 阶元素，即除了单位元e以外，G的所有元素的阶都 大于2。故对G中的任一非单位元a，它的逆元a 1 不是它本身，且G中不同的元素有不同的逆元。 由此可见，G中的2n个非单位元构成互为逆元的n对元素。因为G 是交换群，故G的所有元素之积可变成单位元和n 对互为逆元的元素之积的积，从而结果为e。 60、设S=Q Q，Q为有理数集合，*为S上的二元运算：对任意(a,b)，(c,d) S,有 (a,b)*(c,d)=(ac,ad+b), 求出S关于二元运算*的单位元，以及当a 0时，(a,b)关于*的逆元。 解： 设S关于*的单位元为(a,b)。根据*和单位元的定义，对 (x,y) S,有 (a,b)*(x,y)=(ax,ay+b)=(x,y), (x,y)*(a,b)=(ax,xb+y)=(x,y)。 即ax=x,ay+b=y,xb+y=y对 x,y Q都成立。解得a=1,b=0。 所以S关于*的单位元为(1,0)。 当a 0时，设(a,b)关于*的逆元为(c,d)。根据逆元的定义，有 (a,b)*(c,d)= (ac,ad+b)=(1,0) (c,d)*(a,b)= (ac,cb+d)=(1,0) 1b 即ac=1,ad+b=0,cb+d=0。解得c= a ,d=- a 。 1b 所以(a,b)关于*的逆元为( a ,- a )。 61、设 则R是G上的等价关系。 证明： a∈G，因为H、K是G的子群，所以e∈H且e∈K。令h=k=e,则a=e*a*a=h*e*k,从而aRa。即R是自反的。 a,b∈G，若aRb，则存在 h∈H，k∈K, 使得b=h*a*k。因为H、K是G的子群，所以h-1∈H且k-1∈K。故a=h-1*a*k-1, 从而bRa。即R是对称的。 a,b,c∈G，若aRb,bRc,则存在 h,g∈H，k,l∈K, 使得b=h*a*k，c=g*b*l。所以c=g*b*l=g*(h*a*k)*l=(g*h)*a*(k*l)。 因为H、K是G的子群，所以g*h∈H且k*l∈K。从而aRc。即R是传递的。 综上所述，R是G上的等价关系。 62、设H是G的子群，则下列条件等价： （1） H是G的不变子群； （2） a∈G，a H a-1 H； （3） a∈G，a-1 H a H； （4） a∈G， h∈G，a h a-1 H。 证明： (1) (2) a∈G，则对h∈H,令h1=a h a-1，因为a h a H且H a=a H，所以 h2∈H，使得a h=h2 a。 故h1=（h2 a） a-1=h2 H。故 a H a-1 H。 (2) (3) a∈G，对h∈H,令h1=a-1 h a，则（h1）-1= a h-1 a-1。因为h-1∈H，所以（h1）-1= a h-1 a-1 ∈a H a-1。由（2）可知（h1）-1∈H,从而h1 H。故a-1 H a H 。 (3) (4) 类似于（2） (3)的证明。 (4) (1) a∈G，对 b∈a H，则 h∈H，使得b=a h。故b=(a h) (a-1 a)=(a h a-1) a。由于a h a-1 ∈H，所以b∈H a。即a H H a。 反之对 b∈H a，则 h∈H，使得b=h a。故b=(a a-1) (h a)=a (a-1 h a)=a (a-1 h (a-1)-1)。由于 a-1 h (a-1)-1∈H，所以b∈a H。即H a a H。 即H a=a H。从而H是G的不变子群。 63、在半群 a,b G，方程a*x=b 和y*a=b都有惟一解，则 证明： 任意取定a G，记方程a*x=a的惟一解为eR。即a*eR=a。 下证eR为关于运算*的右单位元。 对 b G，记方程y*a=b的惟一解为y。 运算*满足结合律。 b*eR=(y*a)*eR=y*(a*eR)=y*a=b。 类似地，记方程y*a=a的唯一解为eL。即eL*a=a。 下证eL为关于运算*的左单位元。 对 b G，记方程a*x=b的惟一解为x。 运算*满足结合律。 eL*b=eL*(a*x)=(eL*a)*x=a*x=b。 从而在半群 现证G中每个元素关于运算*存在逆元。 对 b G，记c为方程b*x=e的惟一解。下证c为b关于运算的逆元。记d=c*b。 则b*d=(b*c)*b=e*b=b。 b*e=b,且方程b*x=b有惟一解， d=e。 b*c=c*b=e。从而c为b关于运算的逆元。 综上所述， 64、设 的子群的充分必要条件是HK=KH。 证明： HK是G的子群。 c HK，则c-1 HK，故存在a H,b K ,使得c-1=a·b。因为c=（a·b）-1=b-1·a-1。因为H 和K都是G 的子群，所以a-1 H,b-1 K ，即c KH。从而HK KH。 c KH，则存在a H,b K ,使得c=b·a。因 为c=（a-1·b-1）-1。因为H和K都是G 的子群，所以a-1 H,b-1 K ，即a-1·b-1 HK。因为HK是G的子群，所 以c=（a-1·b-1）-1 HK。从而KH HK。 故HK=KH。 HK=KH。对 c，d HK，有a1,a2 H,b1,b2 K ,使得c=a1·b1 ,d=a2·b2。则 c·d=( a1·b1)·(a2·b2)=(( a1·b1)·a2)·b2=( a1·(b1·a2))·b2。因为b1·a2 KH=KH，所以存在a3 H,b3 K , 使得b1·a2 =a3·b3。从而c·d=( a1·（b1·a2）·b2=(a1·（a3·b3）)·b2=(a1·a3)·(b3·b2)。因为H和K都是 G的子群，故a1·a3 H, b3·b2 K。从而c·d HK。 又c-1=(a1·b1)-1=b-11·a-11。因为H和K都是G的子群，故a-11 H, b-11 K。从而c-1 KH。因为HK=KH，所以 c-1 HK。 综上所述，HK是G的子群。 65、设H和K都 是G的不变子群。证明：HK也是G 的不变子群。 证明： 先证HK是G 的子群。 对 a HK，有hH，k K，使得a=h·k。因为a=h·k=(h·k·h-1)·h，且K是G 的不变子群，所以h·k·h-1K。 故a KH。从而HK KH。 同理可证，KH HK。 故HK=KH。从而HK是G的子群。 下证HK是G的不变子群。 对 a G，b HK，有hH，k K，使得b=h·k。故a·b·a-1=a·(h·k)·a-1=(a·h·a-1)·(a·k·a-1)。因为H 和K都是G的不变子群，所以a·h·a-1 H且a·k·a-1 K。从而a·b·a-1 HK。故HK是G 的不变子群。 66、设 G。若a*b=c*b*a,a*c=c*a,b*c=c*b，且a,b的阶分别为m,n，则c的阶整除m与n的最大 公因子(m,n)。 证明： 设c的阶为k。在a*b=c*b*a两边同时右乘b a*b=(c*b*a)*b =(c*b)*a*b =(c*b)*a*b 3 2n2 n3 nn1 n1 ，再由a*b=c*b*a得 n2 n3 =(c*b)*(a*b)*b 2 n2 =(c*b)*(c*b*a)*b 2 =(c*b)*(a*b)*b =…=(c*b)*a, n n3 =(c*b)*(c*b*a)*b 再由b*c=c*b及b 的阶为n得 a=a*b= (c*b)*a=(c*b)*a=c*a, 所以c=e。故由元素阶的定义有k|n。 由a*b=c*b*a,a*c=c*a,b*c=c*b得a*b=b*a*c，两边同时左乘a a*b=a = a = a m2 m3 mm1 m1 n nnnnn ，再由a*b=b*a*c得 *(b*a*c)= a 2 m2 * (a*b)*(a*c)= a 2 m2 *(b*a*c)*(a*c) 2 *b*(a*c)= a 3 m3 *(a*b)*(a*c)= a m m3 *(b*a*c)*(a*c) *b*(a*c)=…=b*(a*c), 再由a*c=c*a及a 的阶为m得 b= a*b= b*(a*c)=b* a * c=b*c, 所以c=e。故由元素阶的定义有k|m。 由此可见，k是m和n的公因子，从而能整除m和n的最大公因子(m,n)。 （格与布尔代数） 67、当n分别是24，36，110时， 解： 因为|S24|=8，|S36|=9，|S110|=8，故 是布尔代数，其原子集为{2,5,11}。 68、设L是有界格，且|L|>1。证明：0 1。 证明： m mmmmm 用反证法证明。 设0=1。则任取a L，则由于L是有界格，故a 1且0 a。即0 a 1。因为0=1且 是L上的偏序关系，所以a=0。 这与已知|L|>1矛盾。 69、设(L,≤)是格，若a,b,c L，a≤b≤c，则 a b=b⊙c , (a⊙b) (b⊙c)=(a b)⊙(a c) 证明： 因为a b c，所以a b=a，a b=b=b，且b=b c，以c=b c。从而a b=b c。 (a b) (b c)=a (b c)=a (a b)=(a a) b=a b=b， (a b) (a c)=(b c) (a c)=b (c (a c))=b c=b。 70、在布尔代数中，证明恒等式a ( a b)=a b 证明： a ( a b)=(a a ) (a b)=1 (a b)=a b 71、设 >是格，a1,a2,…,an L。试证：a1 a2 … an= a1 a2 … an当且仅当a1=a2=…=an。 证明： 显然是成立的。 对任一k=1,2,..,n，a1 a2 … an ak，ak a1 a2 … an。 因为a1 a2 … an= a1 a2 … an，且 是L上的偏序关系，故ak=a1 a2 … an。从而a1=a2=…=an。 72、在布尔代数中，证明恒等式(a c) ( a b) (b c)=(a c) ( a b) 证明： ((a c) ( a b)) (b c)=((a c) (b c)) (( a b) (b c)) =(a b c) ( a b c)=(a a ) b c=1 b c=b c, 故 b c (a c) ( a b)，从而 (a c) ( a b) (b c)=(a c) ( a b)。 73、在布尔代数中，证明恒等式(a b) ( a c) ( b 证明： (a b) ( a c) ( b =(a b) ( (ab) c)=(a b) c c)=(a b) (( a b ) c) c)=(a b) c。 74、设 >是格，a,b,c,d L。试证：若a b且c d，则 a c b d 证明： 因为a b，c d，所以a=a b,c=c d。从而 (a c) (b d)=((a c) b) d=(b (a c)) d=((b a) c) d =a (c d)=a c， 所以a c b d。 75、当n分别是10,45时，画出 解： 10 45 15 9 5 2 5 3 1 1 76、在布尔代数中，证明恒等式 (a b ) (b c ) (c a )=( a b) ( b c) ( c a) 证明： (a b ) (b c ) (c a ) =(a b c) (a b a ) (a c a ) (a c c) ( b b c) ( b c c) ( b c a ) ( b b a )=(a b c) ( b c a )， ( a b) ( b c) ( c a) =( a b c ) ( a b a) ( a c c ) ( a c a) (b b c ) (b b a) (b c c ) (b c a)=(a b c) ( a b c )， 故(a b ) (b c ) (c a )=( a b) ( b c) ( c a)。 77、设 L，且a≤b，记 I[a,b]={x L|a≤x≤b} 则 证明： x,y I[a,b],a≤x≤b且a≤y≤b。由定理6.1.1有a≤x y≤b且a≤x y≤b。从而x y I[a,b]且x y I[a,b]。 故I[a,b] 关于 和 是封闭的，从而 78、设A＝{a,b,c}，求 >的子格（P(A)表示A的幂集）。 解： P(A)={ ,{a},{b},{c},{a,b},{a,c},{b,c},A}。在P(A)的所有非空子集中，只要它关于 和 是封闭的，则它就是 >的子格。 显然 >和<{ }, >是 >的子格。 <{ ,{a}}, >、<{ ,{b}}, >、<{ ,{c}}, >、<{ ,{a,b}}, >、<{ ,{a,c}}, >、<{ ,{b,c}}, >、 <{ ,A}, >、<{ ,{c},{a,c},{b,c},A }， >等都是 >的子格。 79、证明：在同构意义下，4阶格只有2个。 证明： 若≤是L上的全序关系，则它一定是良序关系(因为任一有限的全序集一定是良序集)。若设L={a,b,c,d}，则L的四个 元素满足：a≤b≤c≤d。 若≤不是L上的全序关系，则L中一定存在两个元素（不妨设为b,c），b≤c和c≤b都不成立。因此b 不可能相等，也不可能是b和c。不妨记a=b ≤b,a≤c,a≤d,b≤d,c≤d。 d d c b c b a a 80、设 >是有界格， 是A上的全序关系。若|A|＞2，则 a A-{0,1}，a无补元。 证明： 用反证法证明。 若 a A-{0,1}，a有补元a\'。即a a\'=1，a 则a= a c和b c既 c,d=b c。故 a\'=0。因为 是A上的全序关系，所以a a\'或a\' a。若a a\'， a\'=0。若a\' a，则a= a a\'=1。无论如何，这与a 0,a1 矛盾。 , >是模格 a,b,c L，有 81、格 a (b (a c))=(a b) (a c) 证明： a,b,c L，记d= a c。所以a d,从而 a (b (a c))= a (b d)= (a b) d=(a b) (a c)。 c= (a b) （a c）= a (b (a c))= a (b c)。 , >是分配格， a,b,c L。若(a b)＝(a c)且(a b)＝(a c)，则b＝c。 a,b,c L，若a c，则c= a c。所以 (a b) 82、设 证明： 由吸收律、分配律和交换律有 b=b (a b)＝b (a c)=（b a） （b c） (b c)=c (a b)= c (a c)＝c。 =(a c) 83、证明：在有补分配格中，每个元素的补元一定惟一。 证明： 设 >是一个有补分配格。 a L,设b和c都是a 的补元，即 a b=1,a c=1,a b=0,a c=0。 由吸收律、分配律和交换律有 b= b 0＝b (a c= c 0=c (a c)=(b a) (b c)=1 (b c)=b c, b)＝(c a) (c b)=1 (c b)=c b。 故b=c。从而每个元素的补元是惟一的。 84、设 , >是格，则L是分配格当且仅当 a,b,c L，有 (a b) c a (b c) 证明： 设L是分配格。对 a,b,c L，有 (a b) c=(a c) (b c) 因为a c a，故(a c) (b c) a (b c)。从而 (a b) c a (b c) 对 a,b,c L，因为a c a,a c c,a a b,b c c,b c b,b a b,所以a c a b，a c c，b c c,b c a b， 从而(a c) (b c) (a b) c。 又由已知有 (a b) c=((b a) c) c (b (a c)) c=((a c) b) c (a c) (b c)。 故(a b) c=((a c) b) c (a c) (b c)。 从而L是分配格。 85、设 ,⊙,′,0,1>是一布尔代数，则 a+b=(a⊙b′) (a′⊙b)。 证明： a,b S， ＜S, ,⊙,′,0,1>是一布尔代数， a+b=(a⊙b′) (a′⊙b)= (b⊙a′) (b′⊙a)=b+a。 运算+满足交换律。 a,b,c S，(a+b)+c=((a⊙b′) (a′⊙b))+c =(((a⊙b′) (a′⊙b))⊙c′) (((a⊙b′) (a′⊙b))′⊙c) =(a⊙b′⊙c′) (a′⊙b⊙c′) ((a′ b)⊙(a b′)⊙c) =(a⊙b′⊙c′) (a′⊙b⊙c′) (((a′⊙b′) (b⊙a))) ⊙c) =(a⊙b′⊙c′) (a′⊙b⊙c′) (a′⊙b′⊙c) (a⊙b⊙c) a+(b+c)=(c+b)+a =(c⊙b′⊙a′) (c′⊙b⊙a′) (c′⊙b′⊙a) (c⊙b⊙a) =(a⊙b′⊙c′) (a′⊙b⊙c′) (a′⊙b′⊙c) (a⊙b⊙c) =(a+b)+c 运算+满足结合律。 a S， ＜S, ,⊙,′,0,1>是一布尔代数， a+0=(a⊙0′) (a′⊙0)= (a⊙1) 0=a。 0关于运算+的单位元。 a S， ＜S, ,⊙,′,0,1>是一布尔代数， a+a=(a⊙a′) (a′⊙a)=0 0=0。 a是a关于运算+的逆元。 综上所述， 86、设 ,⊙,′,0,1>是一布尔代数，则 R={ b=b}是S上的偏序关系。 证明： a S， 满足等幂律， a a=a，故aRa。即R是自反的。 a,b S，若aRb且bRa, 满足交换律， b=a b=b a=a。即R是反对称的。 a,b,c S，若aRb且bRc, 满足结合律， c=c b=c （b a） =(c b) a=c a,故aRc。即R是反对称的。 综上所述，R={ b=b}是S上的偏序关系。 87、设 ,⊙,′,0,1>是一布尔代数，则关系 ={ 证明： a S，因为⊙满足等幂律，所以a⊙a=a，故a a。即 是自反的。 a,b S，若a b且b a,因为⊙满足交换律，所以a=a⊙b=b⊙a=b。即 是反对称的。 a,b,c S，若a b且b c,因为⊙满足结合律，因为a=a⊙b=a⊙(b⊙c)=(a⊙b)⊙c=a⊙c,故a c。即 是反对称的。 综上所述， ={ （图论部分） 88、证明在有n个结点的树中，其结点度数之和是2n-2。 证明： 设T= 由欧拉握手定理，树中所有结点的度数之和等于2|E|. 从而结点度数之和是2n-2。 88、任一图中度数为奇数的结点是偶数个。 证明： 设G=〈V,E〉是任一图。设|V|=n。 由欧拉握手定理可得 vV deg(v)=2|E|可得，图中所有结点度数之和是偶数。显然所有偶数度结点的度数之和仍为偶 数，从而所有奇数度结点的度数之和也是偶数。因此，图中度数为奇数的结点一定为偶数个。 89、连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗？若是对的请证明之，否则请举例说明。 证明： 不对。 反例如下：若G 本身是一棵树时，则G的每一条边都不可能是G的任一棵生成树（实际上只有惟一一棵）的弦。 90、设T= 证明： （用反证法证明）设|V|=n。 因为T=〈V,E〉是一棵树，所以|E|=n-1。 由欧拉握手定理可得 vV deg(v)=2|E|=2n-2。 假设T中最多只有1片树叶，则 vV deg(v) 2(n-1)+1>2n-2。 得出矛盾。 91、画一个使它分别满足： 有欧拉回路和哈密尔顿回路； 有欧拉回路，但无条哈密尔顿回路； 无欧拉回路，但有哈密尔顿回路； 既无欧拉回路，又无哈密尔顿回路。 解 92、设无向图G= 解： 设G中度数小于3的顶点有k个，由欧拉握手定理 24= vV deg(v) 知，度数小于3 的顶点度数之和为6。故当其余的顶点度数都为2时，G的顶点最少。即G中至少有9个顶点。 93、设图G= 证明： 由已知可知，G中k+1度顶点为n-nk个。再由欧拉握手定理可知 2m= vV deg(v) =knk+(k+1)(n-nk)=(k+1)n+-nk 故nk=(k+1)-2m。 94、设G= 证明： (用反证法证明） 设|V|=n，则|E|=n-1。 由欧拉握手定理可得 vV deg(v)=2|E|=2n-2。 因为G连通，所以 v V，deg(v) 1。假设G中没有1片树叶，则 vV deg(v) 2n>2n-2。 得出矛盾。 95、若n阶连通图中恰有n-1 条边，则图中至少有一个结点度数为1。 证明： （用反证法证明）设G= 由欧拉握手定理可得 vV deg(v)=2|E|=2n-2。 因为G是连通图，所以G中任一结点的度数都大于等于1。 假设G中不存在度数为1 的结点，则G中任一结点的度数都大于等于2.故 vV deg(v) 2(n-1)+1>2n-2, 得出矛盾。 96、若G有n个结点，m条边，f个面，且每个面至少由k(k 3)条边围成，则 m k(ｎ－2)／(ｋ－2)。 证明： 设连通简单无向平面图G=〈V,E,F〉，则|V|=n,|E|=m,|F|=p。 由已知对任一f F, deg(f) k。 由公式 fF deg(f)=2|E|可得，2|E| k|F|。 2 再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+ k |E| 2。 即k(n-2) (k-2)m。 所以m k(ｎ－2)／(ｋ－2)。 97、设G= 3，面数为k,则k 2n-4。 证明： 记|E|=m。因为G= fF deg(f)=2|E|可得 3k 2m 再由欧拉公式|V|-|E|+|F|=2有 m=n+k-2 3 及 2 k n+k-2 故 k 2n-4。 98、证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点。 证明： 若结点个数小于等于3时，结论显然成立。 当结点多于3 个时，用反证法证明。 记|V|=n,|E|=m,|F|=k。 假设图中所有结点的度数都大于等于5。 由欧拉握手定理得 vV deg(v)=2|E|得 5n 2m。 又因为G=〈V,E,F〉是一个连通简单无向平面图， 所以对每个面f,deg(f) 3。 由公式 fF deg(f)=2|E|可得，2m 3k。 221 再由欧拉公式|V|-|E|+|F|=2可得2 5 m-m+ 3 m= 15 m 从而30 m,这与已知矛盾。 99、在一个连通简单无向平面图G=〈V，E，F〉中若|V| 3，则 |E| 3|V|－6。 证明： |V| 3，且G=〈V，E，F〉是一个连通简单无向平面图， d(f) 3， f F。 由公式 fF deg (f)=2|E|可得，2|E| 3|F|。 2 再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+ 3 |E| 2。 |E| 3|V|－6。 100、给定连通简单平面图G= F, d(f)=3。 证明： 因为|V|=6 3，且G=〈V,E,F〉是一个连通简单无向平面图， 所以对任一f F，deg(f) 3。 由欧拉公式|V|-|E|+|F|=2可得|F|=8。 再由公式 fF deg(f)=2|E|， fF deg(f)=24。 因为对任一f F，deg(f) 3，故要使上述等式成立， 对任一f F，deg(f)=3。 101、设G= V，有d(u)+d(v) n，则G是连通图。 证明： 用反证法证明。 若G 不连通，则它可分成两个独立的子图G 1 和G 2 ，其中|V(G 1 )|+|V(G 2 )|-2=n ，且G 1 中的任一个顶点至多只和G 1 中 的顶点邻接，而G 2 中的任一顶点至多只和G 2 中的顶点邻接。任取u V(G 1 ),v V(G 2 ),则 d(u) |V(G 1 )|-1, d(v) |V(G 2 )|-1。 故d(u)+d(v) (|V(G 1 )|-1)+(|V(G 2 )|-1) |V(G 1 )|+|V(G 2 )|-2 =n-2 故G是连通图。 102、一次会议有20人参加，其中每个人都在其中有不下10个朋友。这20人围成一圆桌入席。有没有可能使任意相 邻而坐的两个人都是朋友？为什么？ 证明： 可以。 将每个人对应成相应的顶点，若两人是朋友，则对应的两个顶点间连上一条无向边，作出一个简单无向图。由已知， 图中每个顶点的度数都大于等于10。即图中任两个不相邻的顶点的度数大于等于20，即顶点数。故这个图是一个哈密 尔顿图，从而存在哈密尔顿回路。任取一条哈密尔顿回路，按回路经过的顶点的次序安排对应的人的座位，就可满足 要求。 103、证明在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。 证明： 将每个人对应成相应的顶点，若两人是朋友，则对应的两个顶点间连上一条无向边，作出一个简单无向图。则原命题 相当于在该无向图中一定存在两个顶点的度数相等。 设该简单无向图中有n个顶点，则图中n个顶点的度数只能为0，1，2，…，n-1。若图中有两个或两个以上的顶点度 数为0，则结论显然成立。否则所有顶点的度数都大于等于1。现用反证法证明该无向图中一定存在两个顶点的度数相 等。 设该简单无向图中n个顶点中任何一对顶点的度数都不相等，即这n个顶点的度数两两不同。但每个顶点的度数只能 是1,2,…,n-1这n-1个数中的某一种，这显然产生了矛盾。 因此该无向图中一定存在两个顶点的度数相等。从而在任何两个或两个以上人的组内，存在两个人在组内有相同个数 的朋友。 104、设有如下有向图G= （1）求G的邻接矩阵；（2）G中v1到v4的长度为4 的通路有多少条？（3）G中经过v1的长度为3 的回路有多少条？ （4）G中长度不超过4 的通路有多少条？其中有多少条通路？ 解： 1 1 0 0 A= 3 2 0 0 A3= 110 2 1010 0001 010 0 ，A2= 242 5 3131 0001 010 0 ，A4= 121 111 010 001 374 243 010 001 G中v1到v4的长度为4 的通路有4条； G中经过v1的长度为3 的回路有3条； （4） G中长度不超过4 的通路有72条，其中有19条回路。 v1 v4 v2 v3 题104图 105、求下列无向图中每个顶点的度数；求下列有向图中每个顶点的出度、入度和度。 解： a d e c b f 在这个无向图中d(a)=3,d(b)=6, d(c)=4, d(d)=3, d(e)=0, d(f)=0。 c b a 在这个有向图中d(a)=3,d(b)=4, d(c)=3, d(a)=2, d(a)=1, d(b)=2 , d(b)=2,d(c)=1, d(a)=2。 a d e c b f 题106图 106、求下列无向图的子图、生成子图、由边集诱导的子图和由顶点集诱导的子图。 解： c b 它的一个子图 d a e c b f 它的一个生成子图 d a c b 由边集{(a,b),(a,c),(a,d),(b,d)}诱导出的子图 d a b f 由顶点集{a,b,d,f}诱导出的子图 107、求下列赋权图顶点间的距离。 d a e 4 3 5 7 1 c b 14 f 解： d(a,b)=3, d(a,c)=3, d(a,d)= , d(a,e)=8, d(a,f)=16, d(b,c)=1, d(b,d)= , d(b,e)=6, d(b,f)=13, d(c,d)= , d(c,e)=5, d(c,f)=12, d(d,e)= , d(d,f)= , d(e,f)=7, 108、求下列赋权图中v1到其他顶点的距离。 v2 10 v4 3 v1 2 2 6 4 3 4 v6 v3 2 v5 解： S l(v2) l(v3) l(v4) l(v5) l(v6) t l(t) {v1} 3 4 v2 3 {v1,v2} 4 13 v3 4 {v1, v2, v3} 7 6 v5 6 {v1,v2, v3, v5} 7 10 v4 7 {v1,v2, v3, v5, v4} 9 v6 9 {v1,v2, v3, v5, v4, v6} 故v1到v2, v3, v4, v5, v6的距离分别是3，4，7，6，9。 109、求下图的可达矩阵。 d a e b c 解： 该图的邻接矩阵为 1 1 0 0 0 A= 则 1 0 0 1 1 0 0 0 0 0 00 00 00 01 10 A2= 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 00 00 00 01 10 2 2 1 1 0 0 = 1 1 2 0 0 1 0 0 00 00 00 10 0 0 01 33 1 00 31 2 00 1 0 2 0 0 0 00 01 A3= 00 0 10 6 43 00 4 51 00 3 1 0 0 0 2 0 0 10 A4= 0 00 01 故图的可达矩阵为 111 00 111 00 11 0 00 1 0 0 11 P = 000 11 110、求下列图的生成树。 解： 下面是它的两棵生成树： 111、在一个有n个顶点的G= V。若存在一条从u到v的一条通路，则必有一条从u到v的长度不超过 n-1的通路。 证明： 设v0e1v1e2…el vl是从u=v0到v=vl的长为l的通路。 若l n-1，则结论显然成立。 否则因为l+1>n，故v0，v1，…，vl中必有一个顶点是重复出现的。不妨设vi=vj(0 i l)，则新通路v0e1v1e2… viej+1vl+1ej+2vj+2…elvl是一条从u 到v的通路，且此通路长度比原通路长度至少少1。 若新通路的长度 n-1，则结论得证。否则对新通路重复上述过程，必可以得到一条从u到v的长为n-1的通路。 112、设简单平面图G中顶点数n=7，边数m=15。证明：G是连通的。 证明： 设G具有k个连通分支G1，G2，…，Gk。设Gi的顶点数为ni，边数为mi，i=1,2,…,k。 先证每个连通分支的顶点数都大于1。否则说明G中有孤立结点。由于G是简单图，从而要使G的边数是15，则G只 有两个连通分支，其中一个是由孤立结点导出的，另一个是K6。但K6不是平面图，故要每个连通分支的顶点数都大于 1。 同理可证，每个连通分支的顶点数都大于2。 由此可得，G的每个连通分支至少有3 个顶点。从而 mi 3ni-6 即m= m i1 k i (3n i1 k i 6) =3n-6k 从而15 21-6k，即k 1。从而k=1，故G是连通图。 113、已知一棵无向树中有2个2度顶点、1个3度顶点、3个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？ 解： 设它有k个1度顶点，则由欧拉握手定理 vV deg(v)=2|E| 可得 2|E|=k+4+3+12=k+19。再由于它是一棵树，故 |E|=k+2+1+3-1=k+5 从而2(k+5)=k+19, k=9。故它有9个1度顶点。 114、有向图G是强连通的 G中有一回路，它至少通过每个顶点一次。 证明： 设G= V，则u和v相互可达，即从u到v有路径P 1 ，从v到u有路径P 1 。故从P 1 和 P 2 首尾相接可得到一条经过u和v的回路C 1 。 若C 1 经过G中所有顶点至少一次，则C 1 就是满足结论要求的回路。否则若C 1 没有经过顶点w，则类似地我们可得到一 条经过u和w的回路C 2 。从C 1 和C 2 我们可得到一条经过更多顶点的回路C 3 （先从u经过P 1 到v,再从v经过C 2 回 到v,再从v经过P 2 回到u）。 对C 3 重复上述过程，直到得到一条经过所有顶点的回路为止。 若G中存在一条经过G中所有顶点至少一次的回路，则G中任意两个顶点是相互可达的，从而G是强连通 的。 115、一个有向图是单向连通图 它有一条经过所有结点的路。 证明： 设G= V，则u可达v或v可达u。不妨设u可达v，即从u到v有路径P 1 。 若P 1 经过G中所有顶点至少一次，则P 1 就是满足结论要求的路径。否则若P 1 没有经过顶点w，则如果v经过路径T 可达w, 连接P 1 和T我们可得一条经过P 1 经过的所有顶点及w的更长的路径P 2 ；否则若w经过路径S可达u，连接S 和P 1 我们也可得一条经过w及P 1 经过的所有顶点的更长的路径P 2 ；再否则我们一定可以找到P 1 经过的两个相邻顶点 t和s，t到s有边，t经过路径T 1 可达w，w经过路径T 2 可达s（否则就与u可达w，w可达v矛盾），我们构造这样 一条路径P 2 ：从u出发经过P 1 到达t,t经过路径T 1 到达w，再从w出发经过路径T 2 到达s，然后从s出发经过P 1 到 达v。这是一条经过w及P 1 所经过的所有顶点的更长的路径。 P 1 P 1 u v u v T S w w P u t s v T 1 T 2 w 对P 2 重复上述过程，直到得到一条经过所有顶点的路径为止。 若G中存在一条经过G中所有顶点至少一次的路径，则G中任意两个顶点中至少有一个可达另一个，从而G是单向 连通的。
更多推荐
顶点,下列,元素,证明,度数,存在
发布评论