1、编号 题目 答案 题型 分值 大纲 难度区分度1 用先求主范式的方法证明(PQ)(PR) (P（Q R）答：先求出左右两个公式 的主合取范式(PQ) (PR) ( P Q) ( P R) ( P Q (R R) ( P (Q Q) R)( P Q R) ( P Q R) ( P Q R) ( PQ 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)它们有一样的
2、主合取范式，所以它们等价。证明题10 2.3；2.43 32 给定连通简单平面图G=，且 |V|=6, |E|=12, 则对于任意 f F, d(f)=3。答：因为|V|=6 3，且 G=V,E,F是一个连通简单无向平面图，所以对任一 f F，deg(f) 3。由欧拉公式|V|-|E|+|F|=2 可得 |F|=8。证明题10 6.4 3 3再由公式 deg(f)=2|E|， deg(f)=24。Ff Ff因为对任一 f F，deg(f) 3，故要使上述等式成立， 对任一 f F，deg(f)=3。3 证明对于连通无向简单平面图，当边数 e30 时，必存在度数 4 的顶点。答：若结点个数小于等
3、于 3 时，结论显然成立。当结点多于 3 个时，用反证法证明。记|V|=n,|E|=m,|F|=k。假设图中所有结点的度数都大于等于 5。由欧拉握手定理得 deg(v)=2|E|得 5n 2m。Vv 又因为 G=V,E,F是一个连通简单无向平面图，所以对每个面 f,deg(f) 3。由公式 deg(f)=2|E|可得，2m 3k。Ff再由欧拉公式|V|-|E|+|F|=2 可得 2 m-m+ m=53m15从而 30 m,这与已知矛盾。 证明题 10 6.4 3 34 在一个连通简单无向平面图 答： |V| 3，且 G=V，E，F是一个连通简单无 证明题10 6.4 3 3G=V，E，F中若|
4、V| 3，则 |E| 3|V|6。向平面图， d(f) 3， f F。由公式 deg (f)=2|E|可得，2|E| 3|F|。Ff 再由欧拉公式|V|-|E|+|F|=2 可得|V|-|E|+ |E| 2。3|E| 3|V|6。5 设 G=是连通的简单平面图，|V|=n 3，面数 为 k,则 k 2n-4。答：记|E|=m。因为 G=是连通的简单平面图，故每个面的度数都不小于 3。从而由公式 deg(f)=2|E|Ff可得 3k 2m再由欧拉公式|V|-|E|+|F|=2 有m=n+k-2及 k n+k-223故 k 2n-4。证明题10 6.4 3 36 在半群中，若对a,b G，方程 a
5、*x=b 和y*a=b 都有惟一解，则是一个群。答：任意取定 a G，记方程 a*x=a 的惟一解为 eR。即a*eR=a。下证 eR为关于运算*的右单位元。对 b G，记 方程 y*a=b 的惟一解为 y。是半群， 运算*满足结合律。证明题 10 8.3 4 4b*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。从而在半群 中, 关于运算 *存在单位元，记为
6、 e。现证 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 关于运算的逆元。综上所述，是一个群。7 设是一个群，H、K 是其子群。 答： aG，因为 H、K 是 G 的子群，所以 eH 且 eK。 证明题10 4.4 3 3定义 G 上的关系 R：对任意a,bG，aRb 存在 hH,kK, 使得 b=h*a*k，则 R 是 G 上的等价关系。令 h=k=e,则 a=e*a*a=h
7、*e*k,从而 aRa。即 R 是自反的。a,bG，若 aRb，则存在 hH，kK, 使得 b=h*a*k。因为 H、K 是 G 的子群，所以 h-1H 且 k-1K。故 a=h-1*a*k-1,从而 bRa。即 R 是对称的。a,b,cG，若 aRb,bRc,则 存在 h,gH，k,lK, 使得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*hH 且 k*lK。从而 aRc。即 R 是传递的。综上所述，R 是 G 上的等价关系。8 设 h 是从群到 的群同态，G 和 G2 的单位元分 别为 e1
8、和 e2，则（1）h(e1)=e2；（2） a G1，h(a-1)=h(a)-1；（3）若 H G1，则 h(H) G2；答：(1) 因为 h(e1) h(e1)=h(e1 e1)= h(e1)= e2 h(e1),所以 h(e1)=e2。(2) aG1，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,dh(H), a,bH，使得 c=h(a),d=h(b)。故c d=h(a) h(b)=h(a b)。因为 H G，所以 a b H ，故c dh(H)。又 c-1=(h(
9、a)-1=h(a-1)且 a-1H，故 c-1h(H)。由证明题10 8.2；8.35 5（4） 若 h 为单一同态，则a G1，|h(a)|=|a|。定理 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)的阶也是无限的。故结论成立。9 设*是集合 A 上可结合的二元运算
10、，且 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*
11、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)。证明题10 8.1 2 2由（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。10 I 上的二元运算*定义为：a,b I，a*b=a+b-2。试证：为群。答：（1） a,b,c I，(a*b)*c=(a*b)+c-
12、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 关于运算*的逆元。综上所述，为群。证明题10 8.3 4 411 R 是集合 X 上的一个自反关系，求证：R 是对称和传递的，当且仅当 和在 R 中有在 R 中。答：“ ” 若 Xcb, Rc
13、,a c,bb,ac,ac,bbc, 到的同态映射，证明是 的一个子群。其中 C=)(|1xgfx且 1、 答：证 ，有 ，又Cba, )(),(bgfaf)(,)( 11gff )(b af( aabfab(*)(*) 111 )1b 是 的子群。证明题 10 8.2；8.3 4 413 设 R 是 A 上一个二元关系， ),(),(|, RbccaAcbaS 且有对 于 某 一 个试证明若 R 是 A 上一个等价关系，则 S 也是A 上的一个等价关系。答：（1） S 自反的，由 R 自反， ，),(),(Raa,（2） S 对称的证明题10 4.4 3 3传 递对 称定 义RSabbcRc
14、SaA , ),()(,S 传递的 定 义传 递SScaRcbRceebddbAca , ),()( ),(),(,由（1） 、 （2） 、 （3）得；S 是等价关系。14 1）用反证法证明。RSQRP)()()(2）用 CP 规则证明 )()(),( P答：1 证明： P（附加前提）)(R TES PQP TE PS TEP TE TI)()(RS TIP 证明题 10 2.4 5 5 PRP TE TE)( TIF2、证明 P（附加前提）P P)(RQ TI P)(S TIQ TE CP)(SP15 设 ，是半群， e 是左幺元且，使得 ，则Ax,x*是群。答：（1） cbaAcba则若 *,cbea:,*)()*( )*()(:即 使事 实 上 (2) e 是之幺元。事实上：由于 e 是左幺元，现证 e 是右幺元。证明题10 8.1；8.34 4
