【正文】 由于 ak是 G 的生成元的充分必要條件是 k與 8互素，故 a,a3,a5,a7是 G的所有生成元。 解： 設(shè) G 是 8 階循環(huán)群， a 是它的生成元。 解： 因?yàn)?|C12|=12 ， |H|=3 ， 所 以 H 的 不 同 右 陪 集 有 4 個(gè)： H ，{a,a5,a9},{a2,a6,a10},{a3,a7,a11}。上確界是 e，下確界是 c。 (d)的極大元為 e,極小元為 b,d。最大元是 e， b是最小元； 上界是 e，下界是 b。上確界是 e，下確界是 c。 (b)的極大元為 b,d,極小元為 b,d。無最大元， c是最小元； 無上界，下界是 c。 (c) {b,e}。 （ 1） 下列哪些關(guān)系式成立： a? b,b? a,c? e,e? f,d? f,c? f； （ 2） 分別求出下列集合關(guān)于 ? 的極大（?。┰?、最大（?。┰?、上（下 ）界及上（下）確界（若存在的話）： (a) A。 解： R誘導(dǎo)的劃分為 {{1,5},{2,4},{3,6}}。其誘導(dǎo)的等價(jià)關(guān)系是 IA ? {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}。 （ 3） D={{1,2,7},{3,5,10},{4,6,8},{9}} 解： （ 1）和（ 2）都不是 A的劃分。下 列哪個(gè)是 A的劃分？若是劃分，則它們誘導(dǎo)的等價(jià)關(guān)系是什么？ （ 1） B={{1,3,6},{2,8,10},{4,5,7}}。它既不是自反的、反自反的、也不是對(duì)稱的、反對(duì)稱的、傳遞的。它是反自反的、對(duì)稱的； （ 3） R={1,2,2,1,1,3,3,3}。它是反自反的、反對(duì)稱的、傳遞的； 32 （ 2） R={1,2,2,1,1,3,3,1,2,3,3,2}。 1 設(shè) A={1,2,3},寫出下列圖示關(guān)系的關(guān)系矩陣，并討論它們的性質(zhì)： 1 1 1 2 3 2 3 2 3 解 ： （ 1） R={2,1,3,1,2,3}。 ?? 是 A上的偏序關(guān)系， ?a=b。 1 設(shè)〈 A,≤〉為偏序集， ?? B? A，若 B有最大 (小 )元、上 (下 )確界，則它們是惟一的。故 x， z?（ R? S） ? （ R? T） 。 (2) ? x， z?R? (S? T)，則由合成關(guān)系的定義知 ? y?B，使得 x， y?R且 y，z?S? T。 同理可證（ R? S） ? （ R? T） ? R? (S? T)。故 x， z?（ R? S） ?（ R? T） 。 1 設(shè) 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） ? x， z?R? (S? T)，則由合成關(guān)系的定義知 ? y?B，使得 x， y?R 且y， z?S? T。 ? R=R1， ?y,x?R。 31 故 R=R1。 ?R是對(duì)稱的， ?yRx。從而 R? R1。 證明： ? ? x,y?R ， ?R是對(duì)稱的， ?yRx。即 xRx，故 R是自反的。即 x,x?R，故 IA? R。 1 設(shè) R? A A，則 R自反 ? IA? R。從而 R? S是傳遞的。 因?yàn)?R 和 S 都是 A上的 等價(jià)關(guān)系， 所以 aRc且 aSc。從而 R? S是對(duì)稱的。 因?yàn)?R和 S都是 A上的 等價(jià)關(guān)系， 所以 bRa且 bSa。從而R? S是自反的。 證明： ? a∈ A，因?yàn)?R和 S都是 A上的 等價(jià)關(guān)系， 所以 xRx且 xSx。從而≤為 A上的的 全序關(guān)系。 ?≤是 A上的良序關(guān)系， ?{a,b}有最小元。 A上的任一良序 關(guān)系一定是 A上的 全序關(guān)系。 (4) 成立。反例如下： A={a}, B={{a},b},C={{{a},b},c}。雖然 A? B，且 B? C，但 A?C。 (2) 不成立。又因?yàn)?B? C，所以 x?C。 （ 3）若 A?B，且 B?C，則 A?C； （ 4）若 A?B，且 B? C，則 A?C； 30 證明： (1) 成立。 (6) (A? B) ? C={b,d}。 (4) P(A)P(B)={nhcuj7d3,{a,d}}。 (2) CBA ?? ={a,b,c,d,e}。 （ 6） (A? B)? C。 （ 4） P(A)P(B)。 設(shè)全集 U={a,b,c,d,e}, A={a,d}, B={a,b,c}, C={b,d}。 （ 3） (A?B)2={a,c,a,c,a,c,b,c,b,c,a,c,b,c,b,c}。 解： （ 1） A?{0,1}?B={a,0,c,a,1,c,b,0,c,b,1,c}。求下列集合： (1) A?{0,1}?B； (2) B2?A； (3) (A?B)2。 故 B=C。故 B? C。因?yàn)?A?B=A?C，則y,x ??A C。從而 A?C ?? 。即 B=C。從而 A?C =? 。 對(duì)任意集合 A,B， 證明：若 A ?? ， A?B=A?C，則 B=C。 同理可證， A? B。從而 x?A。 對(duì) Bx?? , x,x?B?B。 若 B ?? ，則 B?B ?? 。故 A=? 。 證明： 若 B=? ，則 B?B=? 。 (3) R={1,1,1,1,2,2,3,3}。 （ 3） A={1,2,3}， B={3,2,1,0,1}， R={x,y||x|=|y|且 x A? 且 y?B}。 答： （ 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) 列出下列二元關(guān)系的所有元素： （ 1） A={0,1,2}， B={0,2,4}， R={x,y|x,y BA?? }。 （ 4）存在 x，對(duì)任意 y 使得 xy=y。 （ 2） xz是 xy且 yz的必要條件 。 設(shè) A(x,y,z): x+y=z, M（ x,y,z） : xy=z, L(x,y): xy, G(x,y): xy， 28 個(gè)體域?yàn)樽匀粩?shù)。 （ 6）存在自然數(shù) x，對(duì)任意自然數(shù) y滿足 xy=x。 （ 4）存在自然數(shù) x，對(duì)任意自然數(shù) y滿足 xy=1。 （ 2）對(duì)每個(gè)自然數(shù) x，存在自然數(shù) y滿足 xy=1。 (6) ? x? y（ xy=x） 。 (4) ? x? y（ xy=0） 。 (2) ? x? y(xy=1)。故這與已知（ AB） ? B=（ A? B） B 矛盾。因?yàn)?b?B 且 b? A? B，所以b?（ A? B） B。 ? 用反證法證明。 故 P(A? B)=P(A)? P(B) 1 （ AB） ? B=（ A? B） B當(dāng)且僅當(dāng) B=? 。 從而 S?P(A)且 S?P(B)，故 S?P(A)? P(B)。即 P(A)? P(B)? P(A? B)。即 P(A)? P(B)? P(A? B) 1 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。從而 (AB)C? A(BC) 1 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。 1 (AB)C? A(BC) 證明： ? x?(AB)C， 有 ?x AB且 x?C，即 ?x A， x?B且 x?C。 ? 因?yàn)?B=? ，所以 AB=A且 BA=? 。但 (BA)? A=? ，故 BA=? 。而 A(B? C)= (AB)? (AC)， 所以 A=(AB)? (AC)。 1 (AB)? (AC)=? ? A? B? C 證明： ? 因?yàn)?(AB)? (AC) =(A? B )? (A? C ) =A? (B ? C ) =A? CB? = A(B? C)，且 (AB)? (AC)=? ， 所以 ? = A(B? C)，故 A? B? C。 ? 因?yàn)?A? B? C=? ，所以 A(B? C)=A。從而 A=AB=B=? 。故 AB=? ， BA=? ，從而 A? B， B? A，故 A=B。 證明、 (1) P? R 前提 (2) P (1) (3) P?Q 前提 (4) Q (2),(3) (5) ? (Q? R) 前提 24 (6) ? Q ?? R (5) (7) ? Q (6) (8) ? Q? Q (4),(7) (集合論部分 ) 四、設(shè)Ａ，Ｂ，Ｃ是三個(gè)集合，證明： A? (B－ C)＝ (A? B)－ (A? C) 證明： (A? B)－ (A? C)= (A? B) ? CA? =(A? B) ? （ A ? C ） =(A? B? A )? (A? B? C )= A? B? C =A? （ B? C ） =A? （ BC） (A－ B)? (A－ C)=A－ (B? C) 證明： (AB)? (AC)=(A? B )? (A? C ) =A? (B ? C ) =A? CB? = A(B? C) 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 A? B=A? (BA) 證明： A? (BA)=A? (B? A )=(A? B)? (A? A ) =(A? B)? U= A? B A=B ? A? B=? 證明： ?設(shè) A=B，則 A? B=（ AB） ? （ BA） =? ? ? =? 。 本題即證明 A?（ B? C）， C? ? A， D? ? B， A? ? D。D: D 隊(duì)獲亞軍 。B: B 隊(duì)獲亞軍 。 結(jié)論 : (5) D隊(duì)不是亞軍。 (3) 若 D隊(duì)獲亞軍，則 B隊(duì)不能獲亞軍 。從而 (P→ Q)? ? (Q? R) ? ? P 2 為慶祝九七香港回歸祖國，四支足球隊(duì)進(jìn)行比賽，已知情況如下，問結(jié)論是否有效 ? 前提 : (1) 若 A隊(duì)得 第一，則 B隊(duì)或 C隊(duì)獲亞軍 。 23 故 P→ Q， ? Q和 ? R)都為 T，即 P→ Q為 T， Q 和 R 都為 F。 (P→ Q)? ? (Q? R) ? ? P 證明、 設(shè) (P→ Q)? ? (Q? R)為 T，則 P→ Q和 ? (Q? R)都為 T。所以 P→ Q? P→ (P? Q)。 1 P→ Q?P→ (P? Q) 證明、 設(shè) P→ (P? Q)為 F，則 P 為 T， P? Q 為 F。 (1) 無簡單回路的連通圖 (2) 有 n個(gè)頂點(diǎn) n1條邊的連通圖 (3) 每對(duì)頂點(diǎn)間都有通路的圖 (4) 連通但刪去一條邊便不連通的圖 答：（ 3） 80、連通圖 G是一棵樹當(dāng)且僅當(dāng) G中（ ）。 (1) 5 (2) 7 (3) 8 (4) 9 答：（ 4） 7若一棵完全二元（叉）樹有 2n1個(gè)頂點(diǎn)，則它（ ）片樹葉。 答：偶數(shù) 7具有 6 個(gè)頂點(diǎn)， 12條邊的連通簡單平面圖中，每個(gè)面都是由 ( )條邊圍成？ (1) 2 (2) 4 (3) 3 (4) 5 答：（ 3） 10 7在有 n個(gè)頂點(diǎn)的連通圖中，其邊數(shù)（ ）。 (1) 10 (2) 4 (3) 8 (4) 16 答：（ 4） 7設(shè)無向圖 G有 18條 邊且每個(gè)頂點(diǎn)的度數(shù)都是 3，則圖 G有 ( )個(gè)頂點(diǎn)。 答：（ 1） 70、設(shè) T是一棵樹，則 T是一個(gè)連通且 ( )圖。 答： 2 6任何連通無向圖 G至少有 ( )棵生成樹，當(dāng)且僅