【正文】 (x,y,z): x+y=z, M（ x,y,z） : xy=z, L(x,y): xy, G(x,y): xy， 28 個體域為自然數(shù)。將下列命題符號化： （ 1）沒有小于 0的自然數(shù) 。 （ 2） xz是 xy且 yz的必要條件 。 （ 3）若 xy，則存在某些 z，使 z0, xzyz。 （ 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) 列出下列二元關(guān)系的所有元素： （ 1） A={0,1,2}， B={0,2,4}， R={x,y|x,y BA?? }。 （ 2） A={1,2,3,4,5}， B={1,2}， R={x,y|2? x+y? 4且 x A? 且 y?B}。 （ 3） A={1,2,3}， B={3,2,1,0,1}， R={x,y||x|=|y|且 x 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}。 對任意集合 A,B， 證明：若 A?A=B?B，則 B=B。 證明： 若 B=? ，則 B?B=? 。從而 A?A =? 。故 A=? 。從而 B=A。 若 B ?? ，則 B?B ?? 。從而 A?A ?? 。 對 Bx?? , x,x?B?B。因為 A?A=B?B，則 x,x ??A A。從而 x?A。故 B? A。 同理可證， A? B。 故 B=A。 對任意集合 A,B， 證明：若 A ?? ， A?B=A?C，則 B=C。 29 證明： 若 B=? ，則 A?B=? 。從而 A?C =? 。因為 A ?? ，所以 C=? 。即 B=C。 若 B ?? ，則 A?B ?? 。從而 A?C ?? 。 對 Bx?? ,因為 A ?? ，所以存在 y?A, 使 y,x ??A B。因為 A?B=A?C，則y,x ??A C。從而 x?C。故 B? C。 同理可證， C? B。 故 B=C。 設(shè) 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={a,0,c,a,1,c,b,0,c,b,1,c}。 （ 2） B2?A={c,c,a,c,c,b}。 （ 3） (A?B)2={a,c,a,c,a,c,b,c,b,c,a,c,b,c,b,c}。 （ 4） P(A)?A={? ,a,? ,b,{a},a,{a},b,,a,,b ,A,a,A,b}。 設(shè)全集 U={a,b,c,d,e}, A={a,d}, B={a,b,c}, C={b,d}。求下列各集合： （ 1） A? B? C ； （ 2） CBA ?? ；（ 3） (A? B )? C。 （ 4） P(A)P(B)。 （ 5） (AB)? (BC)。 （ 6） (A? B)? C。 解 ： (1) A? B? C ={a}。 (2) CBA ?? ={a,b,c,d,e}。 (3) （ A? B ） ? C={b,d}。 (4) P(A)P(B)={nhcuj7d3,{a,d}}。 (5) (AB)? (BC)={d,c,a}。 (6) (A? B) ? C={b,d}。 設(shè) 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； 30 證明： (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。 A上的任一良序 關(guān)系一定是 A上的 全序關(guān)系。 證明： ? a， b∈ A，則 {a,b}是 A的一個非空子集。 ?≤是 A上的良序關(guān)系， ?{a,b}有最小元。若最小元為 a，則 a≤ b；否則 b≤ a。從而≤為 A上的的 全序關(guān)系。 若 R和 S都是非 空集 A上的 等價關(guān)系，則 R? S 是 A上的 等價關(guān)系。 證明： ? a∈ A，因為 R和 S都是 A上的 等價關(guān)系， 所以 xRx且 xSx。故 xR? Sx。從而R? S是自反的。 ? a,b∈ A， aR? Sb，即 aRb 且 aSb。 因為 R和 S都是 A上的 等價關(guān)系， 所以 bRa且 bSa。故 bR? Sa。從而 R? S是對稱的。 ? a,b,c∈ A， aR? Sb 且 bR? Sc，即 aRb， aSb,bRc 且 bSc。 因為 R 和 S 都是 A上的 等價關(guān)系， 所以 aRc且 aSc。故 aR? Sc。從而 R? S是傳遞的。 故 R? S是 A上的 等價關(guān)系。 1 設(shè) R? A A，則 R自反 ? IA? R。 證明： ? ? x?A， ?R 是自反的， ?xRx。即 x,x?R，故 IA? R。 ? ? x?A， ?IA? R， ?x,x?R。即 xRx，故 R是自反的。 1設(shè) A是集合， R? A A，則 R是對稱的 ? R＝ R－ 1。 證明： ? ? x,y?R ， ?R是對稱的， ?yRx。即 y,x?R，故 x,y?R_1 。從而 R? R1。 反之 ? y,x?R1,即 x,y?R 。 ?R是對稱的， ?yRx。即 y,x?R， R_1? R。 31 故 R=R1。 ? ? x， y?A，若 x,y?R ，即 y,x?R1。 ? R=R1， ?y,x?R。即 yRx，故R是對稱的。 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。從而 x， y?R且 y， z?S 或 x， y?R且 y， z?T，即 x， z?R? S或 x， z?R? T。故 x， z?（ 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) ? x， z?R? (S? T)，則由合成關(guān)系的定義知 ? y?B，使得 x， y?R且 y，z?S? T。從而 x， y?R且 y， z?S且 y， z?T，即 x， z?R? S 且 x， z?R? T。故 x， z?（ R? S） ? （ R? T） 。從而 R? (S? T)? (R? S） ? （ R? T）。 1 設(shè)〈 A,≤〉為偏序集， ?? B? A，若 B有最大 (小 )元、上 (下 )確界，則它們是惟一的。 證明： 設(shè) a,b都是 B 的最大元，則由最大元的定義 a? b， b? a。 ?? 是 A上的偏序關(guān)系， ?a=b。即 B 如果有最大元則它是惟一的。 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}。MR=??????????001101000 。它是反自反的、反對稱的、傳遞的； 32 （ 2） R={1,2,2,1,1,3,3,1,2,3,3,2}。MR=??????????011101110 。它是反自反的、對稱的； （ 3） R={1,2,2,1,1,3,3,3}。MR=??????????100001110 。它既不是自反的、反自反的、也不是對稱的、反對稱的、傳遞的。 1 設(shè) A={1,2,… ,10}。下 列哪個是 A的劃分？若是劃分，則它們誘導(dǎo)的等價關(guān)系是什么？ （ 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的劃分。其誘導(dǎo)的等價關(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}。 1 R是 A={1,2,3,4,5,6}上的等價關(guān)系， R=IA ? {1,5,5,1,2,4,4,2,3,6,6,3} 求 R誘導(dǎo)的劃分。 解： R誘導(dǎo)的劃分為 {{1,5},{2,4},{3,6}}。 1 A上的偏序關(guān)系 ? 的 Hasse圖如下。 （ 1） 下列哪些關(guān)系式成立： a? b,b? a,c? e,e? f,d? f,c? f； （ 2） 分別求出下列集合關(guān)于 ? 的極大（?。┰⒆畲螅ㄐ。┰?、上（下 ）界及上（下）確界（若存在的話）： (a) A。 (b) {b,d}。 (c) {b,e}。 (d) {b,d,e} 33 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。 （半群與群部分） 1 求循環(huán)群 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}。 求下列置換的運算： 解： （ 1） ???????? 14334221? ???????? 14233241= ???????? 24433211 （ 2） 3163564235241 ????????= ???????? 163564235241 ? 2163564235241 ???????? = ???????? 163564235241 ? ???????? 462514533261 = ???????? 665544332211 34 2 試求出 8階循環(huán)群的所有生成元和所有子群。 解： 設(shè) G 是 8 階循環(huán)群， a 是它的生成元。則 G={e,a,a2,..,a7}。由于 ak是 G 的生成元的充分必要條件是 k與 8互素，故 a,a3,a5,a7是 G的所有生成元。 因為循 環(huán)群的子群也是循環(huán)群，且子群的階數(shù)是 G 的階數(shù)的因子，故 G的子群只能是 1 階的、 2 階的、 4