離散數(shù)學試題及答案

《離散數(shù)學試題及答案》由會員分享，可在線閱讀，更多相關《離散數(shù)學試題及答案（17頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、離散數(shù)學試題及答案一、填空題1設集合 A,B，其中 A1,2,3, B= 1,2,則 A - B _3 _;(A) -(B) _ 3 ，1 ，3 ，2,3,1,2,3_ .2.設有限集合 A, |A| = n,則 |(A×A)| = _ 2(n2)_.3.設集合 A = a, b, B = 1, 2,則從 A 到 B 的所有映射是 _A1 = (a,1), (b,1), A2 =(a,2), (b,2), A3 = (a,1), (b,2), A4 = (a,2), (b,1),_ _, 其中雙射的是 _A3, A4 _.4.已知命題公式 G (PQ) R，則 G的主析取范式是 _P

2、 Q R (m5) _.5. 設 G是完全二叉樹， G 有 7 個點，其中 4 個葉點，則 G的總度數(shù)為 _12_，分枝點數(shù)為_3_.6 設A、 B 為兩個集合, A= 1,2,4, B = 3,4,則從_1,2,3,4_;AB _ 1,2_ .AB _4 _; AB7. 設 R 是集合 A 上的等價關系，則 R所具有的關系的三個特性是 _自反性 _,_對稱性 _, _ 傳遞性 _.8.設命題公式G (P(QR) ，則使公式G為真的解釋有 _（ 1,0,0） _，_(1,0,1)_,_ (1,1,0)_.9.設集合 A1,2,3,4,A 上的關系 R = (1,4),(2,3),(3,2),R

3、 = (2,1),(3,2),(4,3),則RR =_11_,(1,3),(2,2),(3,1)_,RR =_ (2,4), (3,3), (4,2)1221R2=_ (2,2), (3,3)_.110.設有限集 A, B ，|A| = m, |B| = n,則| |(AB)| = _ 2(m*n) _.11設 A,B,R 是三個集合，其中 R 是實數(shù)集， A = x |-1 x 1, xR, B = x | 0 x < 2, xR,則 A-B = _x | -1 x < 0, x R_ , B-A = _x | 1 < x < 2, x R_ ,A B = _ x |

4、 0 x13.設集合 A2, 3, 4, 5, 61, xR_ , .，R 是 A 上的整除，則R 以集合形式 ( 列舉法 ) 記為 _(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)_.14.設一階邏輯公式G =xP(x)xQ(x) ，則G的前束范式是_yx(P(y)Q(x) _ _.15. 設 G是具有 8 個頂點的樹，則 G中增加 _21_條邊才能把 G變成完全圖。16.設謂詞的定義域為 a,b,將表達式xR(x)xS(x)中量詞消除，寫成與之對應的命題公式是 _(R(a) R(b) (S(a) S(b) _.17.設集合 A

5、1, 2, 3, 4， A 上的二元關系 R (1,1),(1,2),(2,3), S(1,3),(2,3),(3,2)。則 RS_(1, 3),(2, 2)_,R2 _(1, 1),(1, 2),(1, 3)_.二、選擇題1設集合 A=2,a,3,4， B = a,3,4,1， E 為全集，則下列命題正確的是 ( C )。(A)2A(B)aA(C)aBE (D)a,1,3,4B.2設集合 A=1,2,3,A上的關系 R (1,1),(2,2),(2,3),(3,2),(3,3)，則 R 不具備(D ).(A) 自反性(B) 傳遞性(C) 對稱性(D) 反對稱性3設半序集 (A, ) 關系的哈

6、斯圖如下所示，若A 的子集 B=2,3,4,5,則元素 6為B的( B) 。65(A) 下界(B) 上界(C) 最小上界34(D)以上答案都2不對14 下列語句中， ( B ) 是命題。(A) 請把門關上(B)地球外的星球上也有人(C)x + 5 > 6 (D)下午有會嗎？5設 I 是如下一個解釋：Da,b,P(a, a) P(a,b) P(b,a) P(b,b)1010則在解釋 I 下取真值為 1的公式是 (D ).(A) x yP(x,y) (B)x yP(x,y)(C)xP(x,x)(D)x yP(x,y).6.若供選擇答案中的數(shù)值表示一個簡單圖中各個頂點的度，能畫出圖的是( C)

7、.(A)(1,2,2,3,4,5)(B)(1,2,3,4,5,5)(C)(1,1,1,2,3)(D)(2,3,3,4,5,6).7.設 G、 H 是一階邏輯公式，P 是一個謂詞， GxP(x), HxP(x), 則一階邏輯公式GH是( C ).(A) 恒真的(B)恒假的(C) 可滿足的(D) 前束范式 .8設命題公式G(PQ)， H P (QP)，則 G與 H的關系是 (A ) 。(A)G H(B)HG(C)G H (D)以上都不是 .9設 A, B 為集合，當 (D ) 時 ABB.(A)A B(B)AB(C)B A(D)A B .10設集合 A = 1,2,3,4, A上的關系R (1,1

8、),(2,3),(2,4),(3,4),則 R具有(B ) 。(A) 自反性(B) 傳遞性(C) 對稱性(D)以上答案都不對11下列關于集合的表示中正確的為(B )。(A)aa,b,c(B)aa,b,c (C)a,b,c(D)a,ba,b,c12 命題xG(x) 取真值 1 的充分必要條件是(A ).(A) 對任意 x， G(x) 都取真值1.(B)有一個 x 0，使 G(x0) 取真值 1.(C) 有某些 x，使 G(x 0 ) 取真值 1. (D) 以上答案都不對 .13.設 G是連通平面圖，有5 個頂點， 6 個面，則G的邊數(shù)是 ( A ).(A)9 條 (B)5條(C) 6條 (D)

9、11條 .14.設 G是 5 個頂點的完全圖，則從G中刪去 (A ) 條邊可以得到樹 .(A)6(B)5(C)10(D)4.0111115. 設圖 G的相鄰矩陣為10100，則 G的頂點數(shù)與邊數(shù)分別為 ( D ).110111010110110(A)4, 5( B)5, 6(C)4, 10(D)5, 8.三、計算證明題1. 設集合 A1, 2, 3, 4, 6, 8, 9, 12， R 為整除關系。(1) 畫出半序集 (A,R) 的哈斯圖；128694231(2) 寫出 A 的子集 B = 3,6,9,12 的上界，下界，最小上界，最大下界；B 無上界，也無最小上界。下界1, 3;最大下界是3

10、.(3) 寫出 A 的最大元，最小元，極大元，極小元。A 無最大元，最小元是1，極大元 8, 12, 90+;極小元是 1.2.設集合 A 1, 2, 3, 4，A 上的關系R (x,y) | x, yA 且 xy,求(1) 畫出 R 的關系圖；1423(2) 寫出 R 的關系矩陣 .10001100M R110111113. 設 R 是實數(shù)集合，,是 R上的三個映射，(x) = x+3,(x) = 2x,(x) x/4,試求復合映射?，?,? ,? ，? ? .(1)?(x)(x)+3 2x+3 2x+3.(2)?(x)(x)+3 (x+3)+3 x+6,(3)?(x)(x)+3 x/4+3

11、,(4)?(x)(x)/4 2x/4 = x/2,(5)?(?) ?+3 2x/4+3 x/2+3.4. 設 I 是如下一個解釋： D = 2, 3,abf(2)f(3)P(2,P(2,P(3,P(3,2)3)2)3)32320011試求 (1)P( a, f (a) P( b,f (b);(,( )(,f( )P a faP bb=P(3,f (3) P(2,f (2)= P(3, 2) P(2,3)= 1 0= 0.(2)xy P ( y, x).xy P ( y,x) =x ( P (2,x) P (3,x)= ( P (2, 2)P (3, 2) ( P (2, 3)P (3, 3)=

12、 (0 1) (0 1)= 1 1= 1.5.設集合 A 1, 2, 4, 6, 8, 12， R 為 A 上整除關系。(1) 畫出半序集 (A,R) 的哈斯圖；8124621(2) 寫出 A 的最大元，最小元，極大元，極小元；無最大元，最小元1，極大元 8, 12;極小元是1.(3) 寫出 A 的子集 B = 4, 6, 8, 12的上界，下界，最小上界，最大下界.B 無上界，無最小上界。下界1, 2;最大下界2.6.設命題公式G =(P Q)(Q (P R),求 G 的主析取范式。7. (9 分 ) 設一階邏輯公式： G = (xP( x) yQ( y) xR( x) ，把 G化成前束范式

13、 .G = (xP( x) yQ( y) xR( x)=(xP( x) yQ( y) xR( x)= (xP( x) yQ( y) xR( x)= (xP( x) yQ( y) zR( z)=xyz(P( x) Q( y) R( z)9.設 R是集合 A = a,b, c, d.R是 A 上的二元關系 , R = (a,b),(b,a),(b,c),(c,d),(1) 求出 r(R), s(R), t(R)；r(R) R I A (a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d),s(R) R R 1 (a,b), (b,a), (b,

14、c), (c,b) (c,d), (d,c),t(R) R R2 R3 R4 (a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)；(2) 畫出 r(R), s(R), t(R)的關系圖 .adadadbcbcbcr(R)s(R)t(R)11. 通過求主析取范式判斷下列命題公式是否等價：(1) G = (PQ) (PQR)(2) H = (P(Q R) (Q(PR)G (PQ)(PQR) (P Q R)(P QR) ( P Q R) m6 m7 m3 (3, 6, 7)H = (P (QR) (Q(PR)(P Q) (QR) (PQR) (

15、P Q R)(P QR) ( P Q R)(P QR)( PQR) (P Q R)( PQR)(P Q R) m6 m3 m7 (3, 6, 7)G,H 的主析取范式相同，所以G = H.13.設 R和 S 是集合 A a, b, c, d 上的關系， 其中 R ( a, a),(a, c),( b, c),( c, d),S ( a,b),( b,c),( b,d),( d,d).(1) 試寫出 R和 S 的關系矩陣；1010010000100011M R001M S0000000000001 111(2) 計算 R?S, RS, R , S ?R .R?S ( a,b),( c,d),R

16、S ( a,a),( a,b),( a,c),( b,c),( b, d),( c, d),( d, d),R 1 ( a,a),(c,a),(c,b),( d,c),S 1?R 1 (b,a),(d,c).四、證明題1.利用形式演繹法證明： P Q,R S,PR 蘊涵 Q S。證明： PQ,RS,P R 蘊涵 QS(1)PRP(2) RP Q(1)(3)PQP(4) RQ Q(2)(3)(5) QR Q(4)(6)RSP(7) QS Q(5)(6)(8) Q SQ(7)2. 設 A,B 為任意集合，證明：(A-B)-C = A-(B C).證明： (A-B)-C = (A B) C= A (

17、BC)= A (BC)= A-(B C)3. ( 本題 10 分) 利用形式演繹法證明：A B,CB, C D蘊涵 A D。證明： A B,CB, C D蘊涵 A D(1) AD(附加 )(2) ABP(3) BQ(1)(2)(4)CBP(5) B CQ(4)(6) CQ(3)(5)(7) C DP(8)DQ(6)(7)(9)A DD(1)(8)所以 AB,C B, C D蘊涵 AD.4. ( 本題 10 分 )A, B 為兩個任意集合，求證：A (AB) = (AB)B .證明： A (A B)= A (AB) A (A B) (AA)(AB) (AB) (A B) A B而 (A B)B=

18、 (A B)B= (A B)(BB)= (A B)= A B所以： A (AB) = (A B)B.離散數(shù)學試題（ A 卷及答案）一、（ 10 分）某項工作需要派A、 B、 C和 D 4 個人中的 2 個人去完成，按下面3 個條件，有幾種派法？如何派？(1) 若 A去，則 C和 D中要去 1 個人；(2) B 和 C不能都去；(3) 若 C去，則 D留下。解設A： A 去工作；B： B 去工作；C： C 去工作；D： D 去工作。則根據(jù)題意應有：ACD，( BC)，CD必須同時成立。因此( ACD)(BC)(CA( CA( CD)D) (D)(C D)C D) ( (BBC) (C) (CBD

19、)D) C (CD)(A( CB D C) (BA B C)(CD) ( DA BC) (D) ( CADCD)C)(CD CD) (C DBC) (CDBD)(CDC) (C DCD)FF(AC) FF( CDB) FF(CDB) F(CD) F(AC) (BCD) (CDB) (CD)(AC) (BCD) (CD)T故有三種派法：B D， A C， A D。二、（ 15 分）在謂詞邏輯中構(gòu)造下面推理的證明：某學術(shù)會議的每個成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。解：論域：所有人的集合。S ( x ) ： x 是專家；W ( x ) ： x 是工人；Y ( x )

20、 ： x 是青年人；則推理化形式為：x ( S ( x ) W ( x ) ，x Y ( x )x ( S ( x ) Y ( x )下面給出證明：(1)x Y ( x )P(2)Y ( c)T(1)， ES(3)x ( S ( x ) W ( x )P(4)S ( c ) W ( c )T(3)， US(5)S ( c )T(4)，I(6)S ( c ) Y ( c)T(2)(5)， I(7)x ( S ( x ) Y ( x )T(6)， EG三、（ 10 分）設 A、 B 和 C是三個集合，則AB證明： ABx( x Ax B) x( x Bx(BA)。A)x( xA x B) x( x

21、BxA)x( x A xB) x( xB x A)x( x A xB) x( x AxB)(x( x A xB) x( x A xB)(x( x A xB) x( x BxA)(BA)。四、（ 15 分）設 A 1 ，2，3，4，5 ，R是 A 上的二元關系，且R <2 ，1>，<2，5>，<2， 4>，<3， 4>， <4， 4>， <5， 2> ，求 r ( R) 、 s( R) 和 t ( R) 。解 r ( R) R I A <2 ， 1>， <2， 5>， <2， 4>，<

22、;3， 4>， <4， 4>， <5， 2>， <1， 1>，<2， 2>，<3， 3>， <4， 4>， <5， 5>s( R) R R 1 <2 ，1>， <2， 5>，<2，4>， <3， 4>， <4， 4>，<5， 2>， <1， 2>，<4，2>， <4，3>R2 <2 ， 2>， <2， 4>，<3， 4>，<4， 4>，<5， 1

23、>， <5， 5>，<5， 4>R3 <2 ， 1>， <2， 5>，<2， 4>，<3， 4>，<4， 4>， <5， 2>，<5， 4>R4 <2 ， 2>， <2， 4>，<3， 4>，<4， 4>，<5， 1>， <5， 5>，<5， 4> R2t ( R) i， 1>， <2， 5>， <2， 4>， <3， 4>，<4， 4>， &l

24、t;5， 2>， <2， 2>， <5，R<2i 11>， <5，4>， <5， 5> 。五、（10 分）R是非空集合 A 上的二元關系， 若 R是對稱的， 則 r ( R) 和 t ( R) 是對稱的。證明 對任意的 x、y A，若 xr ( R) y，則由 r ( R) R I A 得， xRy 或 xI Ay。因 R 與 I A對稱，所以有yRx 或 yI Ax，于是 yr ( R) x。所以 r ( R) 是對稱的。n下證對任意正整數(shù)n， R 對稱。因 R對稱，則有 xR2 yz( xRz zRy)z( zRx yRz)yR2

25、x，所以 R2 對稱。若 Rn 對稱，則x Rn 1y(Rnz)(Rnx)yRn 1x，所以 Rn 1對稱。因此，對任z xzRyz zyRz意正整數(shù) n， Rn 對稱。對任意的x、 y A，若 xt ( R) y，則存在 m使得 xRmy，于是有 yRmx，即有 yt ( R) x。因此，t ( R) 是對稱的。六、（ 10 分）若 f ： A B 是雙射，則 f 1： B A 是雙射。證明 因為 f ： A B 是雙射，則 f 1 是 B 到 A 的函數(shù)。下證 f 1 是雙射。對任意 x A，必存在 yB 使 f ( x) y，從而 f 1( y) x，所以 f 1 是滿射。對任意的 y1

26、、 y2 B，若 f 1( y1) f 1( y2) x，則 f ( x) y1 ， f ( x) y2。因為 f ： AB是函數(shù)，則 y1 y2。所以 f 1 是單射。綜上可得， f 1： BA 是雙射。七、（ 10 分）設 < ，*> 是一個半群，如果S是有限集，則必存在 ，使得*。Sa Sa aa證明 因為 <S， *> 是一個半群，對任意的b S，由 * 的封閉性可知， b2 b* b S， b3 b2* b S， ， bn S， 。因為 S 是有限集，所以必存在 j i ，使得 bi b j 。令 p j i，則 b j b p * b j 。所以對 q i

27、，有 bq b p * bq 。因為 p 1，所以總可找到 k 1，使得 kp i 。對于 bkp S，有 bkp bp * bkp b p *(b p * bkp ) bkp * bkp 。令 a bkp ，則 a S 且 a* a a。八、（ 20 分）（ 1）若 G是連通的平面圖，且G的每個面的次數(shù)至少為l ( l 3) ，則 G的邊數(shù) m與結(jié)點數(shù) n 有如下關系：m l( n 2) 。l2r證明設 G有 r 個面，則 2md ( f i ) lr 。由歐拉公式得， n m r 2。于是， mi1l( n 2) 。l 2（ 2）設平面圖 G <V， E， F>是自對偶圖，則

28、| E | 2(| V| 1) 。證明設 G* <V* ，E*> 是連通平面圖G <V， E， F>的對偶圖，則G*G，于是|F|V*| V|，將其代入歐拉公式|V|E|F|2得，|E| 2(|V|1) 。離散數(shù)學試題（ B 卷及答案）一、（ 10 分）證明 (PQ) ( P R) (Q S) SR證明因為 SRR S，所以，即要證 ( PQ) ( P R) ( Q S)R S。(1)R附加前提(2)PRP(3)P(1)(2)，IT(4)PQP(5)QT(3)(4)，I(6)QSP(7)ST(5)(6)，I(8)R SCP(9)SRT(8) ，E二、（15 分）根據(jù)推理

29、理論證明：每個考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。設 P( e) ：e 是考生， Q( e) ：e 將有所作為， A( e) ：e 是勤奮的， B(e) ：e 是聰明的，個體域：人的集合，則命題可符號化為：x( P( x) ( A( x) B( x) ，x( A( x)Q( x) ，x( P( x) Q( x)x( P( x) B( x) 。(1)x( P( x)Q( x)P(2)x(P( x) Q( x)T(1)， E(3)x( P( x) Q( x)T(2)， E(4)P( a) Q( a)T(3) ，ES(5)()(4)

30、 ，IP aT(6)Q( a)T(4) ，I(7)( () () ()Px P xA xB x(8)P( a)( A( a) B( a)T(7) ， US(9)A( a) B( a)T(8)(5)，I(10) x( A( x)Q( x)P(11) A( a)Q( a)T(10) ，US(12)A( a)T(11)(6) ， I(13)B( a)T(12)(9)，I(14)P( a) B( a)T(5)(13)，I(15)x( P( x) B( x)T(14) ， EG三、（10 分）某班有 25 名學生，其中 14 人會打籃球， 12 人會打排球， 6 人會打籃球和排球， 5 人會打籃球和網(wǎng)球

31、，還有 2 人會打這三種球。而 6 個會打網(wǎng)球的人都會打另外一種球，求不會打這三種球的人數(shù)。解設 A、B、C分別表示會打排球、網(wǎng)球和籃球的學生集合。則：| A| 12，| B| 6，| C| 14，| AC| 6，| BC| 5， | ABC| 2，|( AC) B| 6。因為 |( AC) B| ( AB) ( BC)| |( AB)| |( BC)| | ABC| |( AB)| 526，所以 |( AB)| 3。于是 | ABC| 12614 6 53220， | AB C | 25205。故，不會打這三種球的共5 人。四、（10 分）設 A 、A 和 A 是全集 U的子集，則形如3(

32、A為 A 或 Ai) 的集合稱為由 A 、A123iii1i1A 和 A 產(chǎn)生的小項。試證由A 、A 和 A 所產(chǎn)生的所有非空小項的集合構(gòu)成全集U的一個劃分。23123證明小項共 8 個，設有 r個非空小項 s1 、s2、 、 sr ( r 8) 。對任意的 aU，則 a Ai 或 a Ai，兩者必有一個成立，取i為包含元素a的i 或 Ai ，則AAa3r，于是rr，所以r。A，即有 sUs。又顯然有ssiiiiii 1i 1i 1i1i1任取兩個非空小項s 和 s ，若 s s ，則必存在某個 A 和 Ai 分別出現(xiàn)在sp 和q 中，于是sppqpqis sq。綜上可知， s1， s2， ，

33、 sr 是 U的一個劃分。五、（15 分）設 R是 A 上的二元關系，則：R是傳遞的R* RR。證明 (5)若R是傳遞的，則 <，> *()，由R是傳遞的得，xy R Rz xRz zSy xRccSyxRy即有 <x， y>R，所以 R* RR。反之，若 R* RR，則對任意的x、y、zA，如果 xRz 且 zRy，則 <x， y>R*R，于是有 <x，y>R，即有 xRy，所以 R是傳遞的。六、（15 分）若 G為連通平面圖，則n m r 2，其中， n、 m、r 分別為 G的結(jié)點數(shù)、邊數(shù)和面數(shù)。證明對 G的邊數(shù) m作歸納法。當 m 0 時，

34、由于 G是連通圖，所以G為平凡圖，此時n 1， r 1，結(jié)論自然成立。假設對邊數(shù)小于m的連通平面圖結(jié)論成立。下面考慮連通平面圖G的邊數(shù)為 m的情況。設 e 是 G的一條邊，從G中刪去 e 后得到的圖記為G，并設其結(jié)點數(shù)、邊數(shù)和面數(shù)分別為n、 m和 r。對 e 分為下列情況來討論：若 e 為割邊，則 G有兩個連通分支G 和 G。G 的結(jié)點數(shù)、邊數(shù)和面數(shù)分別為n 、m和 r。12iiii顯然 n1 n2 nn，m1m2mm1，r 1r 2 r 1 r 1。由歸納假設有 n1m1 r 12，n mr 2，從而 ( n n ) ( mm) ( rr ) 4， n ( m 1) ( r 1) 4，即 n

35、mr 2。222121212若e不為割邊，則n ，m 1，r 1，由歸納假設有nmr 2，從nmr而 n( m 1) r 12，即 nmr 2。由數(shù)學歸納法知，結(jié)論成立。七、（10 分）設函數(shù) g：AB，f ：BC，則：(1) f og 是 A 到 C的函數(shù)；(2) 對任意的 xA，有 f og( x) f ( g( x) 。證明(1)對任意的 xA，因為 g： A B 是函數(shù)，則存在yB 使 <x，y> g。對于 y B，因f ： BC是函數(shù)，則存在 z C使<y，z>f 。根據(jù)復合關系的定義，由 <x，y>g 和<y，z>f 得<x，z

36、> g* f ，即 <x， z>f og。所以 Df ogA。對任意的 xA，若存在 y1、y2 C，使得 <x，y1>、<x， y2 > f og g* f ，則存在 t 1 使得 <x，t 1> g 且<t 1 ， y1>f ，存在 t 2 使得 <x，t 2>g 且<t 2 ，y2>f 。因為 g：AB 是函數(shù)，則 t 1 t 2 。又因 f ：BC是函數(shù)，則 y1 y2 。所以 A 中的每個元素對應 C中惟一的元素。綜上可知， f og 是 A 到 C的函數(shù)。(2) 對任意的 xA，由 g：AB

37、是函數(shù)，有 <x，g( x)> g 且 g( x) B，又由 f ：BC是函數(shù)，得 <g( x) ，f ( g( x)> f ，于是 <x，f ( g( x)> g* f f og。又因 f og 是 A 到 C的函數(shù)，則可寫為 f og( x) f ( g( x) 。八、（15 分）設 < ，*>是 < ，*>的子群，定義<，>|、且1* ，則R是GHGRa b a b Ga b H中的一個等價關系，且 a R aH。證明對于任意 ，必有 1G使得1* ，所以<，>。a Gaa a e Ha a R若<

38、a，b>R，則 a1* b H。因為 H是 G的子群，故 ( a1 *b) 1b 1* aH。所以 <b，a> R。若<a，b>R，<b，c>R，則 a1* bH，b1* cH。因為 H是 G的子群，所以 ( a1 *b)*( b 1* c) a1 * cH，故 <a， c> R。綜上可得， R是 G中的一個等價關系。對于任意的 b a R，有 <a，b> R，a1* b H，則存在 hH使得 a 1 * bh，b a* h，于是 b aH， aRaH。對任意的 b aH，存在 h H使得 b a* h，a 1* b hH，<a，b> R，故 aH a R。所以， aR 。aH