離散證明題集錦

1、離散證明題集錦一.命題邏輯例：給出(PAQ)? ( PV Q)的真值表解:P Q (PAQ) ? ( PV Q)001 0 1 1 1 1011 0 1 1 1 0步驟 一般說來，n個命題變元組成的命題公式共有 2n種真值指派。定理1:任何兩個重言式的合取或析取，仍然是重言式。證明：設(shè)A、B為兩個重言式，則AA B和AV B的真值分別等 于 TA T 和 TV T。定理2:對一個重言式的同一分量都用任何一個命題公式置換，所得命題公式仍為一個重言式。(即代入規(guī)則)證明：由于重言式的真值與分量的真值指派無關(guān)， 故對同一分 量以任何一個命題公式置換后，重言式的真值不變。定理3:設(shè)A、B是兩個命題公式

2、，A B當(dāng)且僅當(dāng)A? B日ZE個重言式。（前面已證）證明：若A B,則又t于A、B所包含的分量的任意指派，A B 均取相同的真值，即A?B是一個重言式；若A? B是一個重言式，即 對于分量的任意指派，A B均取相同的真值，即A B定理1:設(shè)A1是命題公式A的子公式，若A1 B1,則若將A中的A1用B1來替換，得到公式B ,則B與A等價，即A B.（替換規(guī)則）。證明：因為對變元的任一組指派，A1與B1真值相同，故以B1取代A1后，公式B與公式A相對于變元的任一指派的真值也必相 同，所以A Bo證明下列命題公式(可以利用基本等價式)Q7(PV(PAQ) CH P(P AQ)V(PA Q) P(P-

3、Q)-(QV R) PV QV RP A QV Q PV Q解：1.原式 QH (PVP) A(PVQ)8 PA (PVQ)Q P2 .原式 (PA Q V P) A (P A Q) V1 Q) (PVP) A (PVQ) A(PVi Q) A(QVi Q) PA (PVQ) A(PV Q) PA P P3 .原式 J PVQ V(QVR) (PA Q) V(QVR) (PVQVR) A (Q V QV R) PV QV R (零率)4 .原式(PA Q VQ (PV Q A QV Q) PV Q (運算次序優(yōu)先級：1,A, V, -,?)例：求證：(P -Q) V I (P -Q)為永真式。

4、解：原式 J PV Q V (PA Q) ( PV QV P) A J PV Q V Q T例：求證IQ (P Q) I P證法1 ：前件真推導(dǎo)后件真證法2:后件假推導(dǎo)前件假證法3:定義定理：設(shè)P、Q為任意兩個命題公式，P Q的充分必要條件是P Q 且Q P。證明：若P Q則P? Q為重言式，即P-Q和Q-P是重言式； 若有P Q且Q P,則P Q和CH P是重言式，即P? Q為重言式例 已知A是B的充分條件，B是C的必要條件，C是D的必要條件，D是B的必要條件，問:(1) A是D的什么條件(2) B是D的什么條件解 已知A B, C B, D C, B D,故有(1) AB, B D,所以A

5、 D,即A是D的充分條件(2) DC, C B,所以D B,又因為B D,所以B D,即B是D的充要條件。定理：如果A B,則A* B*。證明：設(shè)P1,P2,Pn是出現(xiàn)在命題公式 A B中的原子變元， 因為 A B,即：A(P1,P2,下門)？ B(P1,P2,下門)是一個重言式。 故有：A( P1, P2Pn)? BP1,i P2Pn)是一個重言 式。即 A(I P1,i P2Pn) B(1 P1,i P2Pn)1 A* B* ,即 A* B*例判斷下面各推理是否正確.(1)如果天氣涼快，小王就不去游泳.天氣涼快，所以小王沒去游 泳.(2)如果我上街，我一定去新華書店.我沒上街.所以我沒去新

6、華 書店.解：解上述類型的推理問題，應(yīng)先將命題符號化，然后寫出前提、結(jié)論和推理的形式結(jié)構(gòu)，最后進行判斷.(1)P :天氣涼快；Q :小王去游泳.前提：P- Q, P.結(jié)論： Q.推理的形式結(jié)構(gòu)為(P 一 Q)AP)- Q. (*)判斷(*)是否為重言式.真值表法真值表的最后一列全為1,因而(*)是重言式.所以推理正確.等價演算法(P Q)AP)- Q 1.主析取范式法(P 一 Q)AP)- Qm0 V m1V m2V m3由，同樣能判斷推理正確.(2)P :我上街；Q :我去新華書店.前提：P-Q,P.結(jié)論： Q.推理的形式結(jié)構(gòu)為(P-Q)A P) 一 Q. (*)(P -Q)A P)- Qm

7、OV m2V m3可見(*)不是重言式，所以推理不正確.還可用其他方法判斷之例 證明下列前提是不相容的。1 .若A因病缺了許多課，那么他中學(xué)考試失敗。2 .若A中學(xué)考試失敗，則他沒有知識。3 .若A讀了許多書，則他有知識。4 . A因病缺了許多課，而且讀了許多書。證明符號化題目：P：因病缺了許多課，Q：中學(xué)考試失敗，R：有知識，S：讀了許多書。問題要證明前提P Q, Q R, S R, PAS是不相容的。下面我們用另外一種形式的格式證明（即后面講的“構(gòu)造證明”的格式）：編號公式依據(jù)PA SP(2)P(1)； I1(3)S(1); I2(4)P QPQ,(4)； I8(6)S RPR(3),(6

8、)； I8Q RP(9)R(5),(8); I9(10)RAR(7),(9)例 張三說李四在說謊，李四說王五在說謊，王五說張三、李四都在說謊。問誰說真話，誰說假話解 設(shè)A:張三說真話；B:李四說真話；C:王五說真話依題意有A B, B C, CAA Bo(A B)A(B C)A(CAAB)(A B)A( B A)A(B C)A( C B) A (C ( AAB) A (AA B) C)(AA BA C) A (A V B) A C) A (AABA C) V (AAC)V(BA C)AA BA C即：李四說真話，張三和王五說假話。例1.9.3 :求證：S是前提 W W Q, CHR和RHS的有

9、效結(jié)論。證明：1(1)W Q P2(2) CH R P1,2(3) W R T,(1)(2)I113(4) W P1,2,3(5) R T,(3)(4)I84(6)FH SP1,2,3,4(7) S T,(5)(6)I8(這部分的T, I8等是另外一本書的內(nèi)容，所以不用管，只要會 推就行)例前提：如果馬會飛或羊吃草，則母雞就會是飛鳥；如果母雞 是飛鳥，那么烤熟的鴨子還會跑；烤熟的鴨子不會跑。結(jié)論：羊不吃 草。解符號化上述語句，P:馬會飛，Q:羊吃草，R:母雞是飛鳥，S: 烤熟的鴨子還會跑， S：烤熟的鴨子不會跑， Q:羊不吃草。前提集合PVQ R, R S, S,結(jié)論C :Q。(1) SP(2

10、) R S P(3) R(1),(2),I9(4) PV Q R P(5) (PVQ)(3),(4),I9(6) PAQ(5),E5(7) Q(6),I 2例 如果我的考試通過，那么我很快樂。如果我快樂，那么陽光 很好?，F(xiàn)在是凌晨一點，天很暖和。試給出結(jié)論。解 設(shè)P:我的考試通過，Q:我很快樂，R:陽光很好，S:天很 暖和。把“凌晨一點”理解為陽光不好。前提為：P Q, Q R,RA So編號公式依據(jù)(1)P Q P(2)Q R P(3)P R (1),(2); I11(4)RA S P(5)R(4) ; I1(6)P(3),(5); I9結(jié)論：P,我的考試沒通過。例 前提：PV Q, P R

11、, RS;結(jié)論：SQ證明(1)SCP(2)R SP(3)S R(2), ER(1),(3), I(6)RP(5), EP(4), (6), IPVQ P(9)PQ(8), E(10)Q(7), (9), I(11)SQ，(10), CPP RP（CP規(guī)則這部分因為好像多了一個條件，所以用起來可能會比較簡單）例1.9.5 :證明R- S可從前提 6 （Q-S）, 1 RV P和Q推出證明：（CP規(guī)則，因為結(jié)論FHS為條件式）1(1) RV P P2(2) RP(附加前提)1,2(3) P T,(1)(2)I1036 (QS)P1,2,3 (5)CH ST, (3,4)184(6) Q P1,2,

12、3,4(7) S T,(5)(6)I81,3,4R- SCP,(2)(7)例1.9.4 :證明從前提 f Q, (QVR)可演繹出1P.證明：(反證法)1(1) P P (附加前提)2(2)6 QP1,2 Q T,(1)(2)I83(4)(QV R)P3(5)QA RT, (4)E53(6)1Q(5)I11,2,3(7)QA Q T,(3)(6)例 “如果春暖花開，燕子就會飛回北方。如果燕子飛回北方， 則冰雪融化。所以，如果冰雪沒有融化，則沒有春暖花開?！弊C明 這些語句構(gòu)成一個正確的推理。證：令P:春暖花開。Q:燕子飛回 北方。R:冰雪融化。則上述問題轉(zhuǎn)化成證明：P Q, Q R R P利用C

13、P規(guī)則，將R作為附加前提，推導(dǎo) P,從而推導(dǎo)出RP。編號 公式依據(jù)(1) QR PP(附加前提)(3) Q (1),(2)； I9(4) PQ前提(5) P ,(4)； I9課堂練習(xí)：1.用基本等價公式的轉(zhuǎn)換方法驗證下列推斷是否有效PQ, RA S,QR AS;(2) P Q, Q R,R P P VQV R;(3)P , Q R, RVSQ S;29(4)QA R, RA P, Q2.用推理規(guī)則證明下述論斷的正確性。(1)P , P (Q (R AS)S;P (Q R) , R (QS)(Q(3)P (QR) (Q(RS)(P(Q S);(P Q)(RVS), (QP) VR,R P Q。3

14、. A, B, C, D四人中要派兩個人出差，按下述三個條件有幾種派法如何派(1)若A去，則C和D中要去一人。(2)B和C不能都去。(3)C去則D要留下。4 . A, B, C, D四人參加考試后，有人問它們，誰的成績最好。A說“不是我”，B說“是D”，C說“是B”，D說“不是我”。四 人的回答只有一人符合實際，問是誰的成績最好只有一人成績最好的 是誰5 .判斷下列推理是否正確：(1)如果我是小孩，我會喜歡熊貓。我不是小孩，所以我不喜歡 熊貓。(2)如果太陽從西邊出來，那么地球停止轉(zhuǎn)動。太陽從西邊出來 了，所以地球停止了轉(zhuǎn)動。二.謂詞邏輯例 試用量詞、謂詞表不下列命題：所有大學(xué)生都熱愛祖國；每

15、個自然數(shù)都是實數(shù)；一些大學(xué)生有遠大理想；有的自然數(shù)是素數(shù)。解 令S(x): x是大學(xué)生，L(x)： x熱愛祖國，則所有大學(xué)生都熱愛祖國(x)( S(x) -L( x)令Nx)： x是自然數(shù)，Rx)： x是實數(shù)，則每個自然數(shù)都是實數(shù)( x)(Nx)-Rx)全稱量詞(x)后跟條件式。令S(x) ： x是大學(xué)生，I(x)： x有遠大理想，則一些大學(xué)生有遠大理想 ( x)( S(x) A I (x)令N(x) ： x是自然數(shù)，P(x) ： x是素數(shù)。則有的自然數(shù)是素數(shù)(x)( N(x) AP(x)存在量詞(x)后跟合取式。例 令f(x):x 小于88, g(x):x 是奇數(shù)，(x) (f(x) Ag(

16、x)。個體變元x是約束變元。這已經(jīng)不是一個命題函數(shù)，而是一個命題。它相當(dāng)于說“存在有小于88的奇數(shù)”，這是一個真命題例令f(y)： y是辣椒，g(y)： y 是紅的，(y) (f(y)-g(y)。個體變元y是約束變元。這也不是一個命題函數(shù)，而是一個命題。對于其中的個體變元不需要再作代入，它的含義是確定的，它斷定“一切辣椒都是紅的”，這當(dāng)然是一個假命題。例：將公式(x)( Rx)-Qx,y) AR (x,y )中的約束變元改名。下面哪個正確(注意到此公式中，約束變元只有x),1) ( y)( Ry) -Q (y,y) ar(x,y)2) ( z)( P(z) -Q (x,y) AR (x,y)3

17、)( z)(Rz)-Q (z,y)AR (x,y)例：將公式(x)( P( y) - Q x,y) AR (x,y)中的自由變元代入。(注意到此公式中y為自由變元，x既是約束出現(xiàn)，也是自由出現(xiàn)。)我們以y為例，試判斷下面哪個正確1) (x)(Rz)-Q(x,z)AR(x,y)2) (x)(Rx)-Q(x,z)AR(x,x)3) (x)(Rz)-Q(x,z)AR(x,z)例 在公式(x) (Q(x)- R(x, y) V ( z) P(x, z) 中，x 既 為約束出現(xiàn)，又為自由出現(xiàn)，下面用兩種方法，使變元x在公式中只 呈一種形式出現(xiàn)解用約束變元的改名規(guī)則得：(u) (Q(u)- R(u, y)

18、 V( z) P(x, z);或用自由變元得代入規(guī)則得：(x )(Q(x)- R(x, y) V( z) P(u, z)。(重做前一例題，將自由出現(xiàn)的 x進行代入)重做例：將公式(x)( Ry)-Qx,y) AR(x,y)中的自由變元代 入。注意到此公式中y為自由變元，x既是約束出現(xiàn)，也是自由出現(xiàn)。 這次，我們將自由出現(xiàn)的 x代入，得：(x)( P(y) -Q (x,y ) AR (z,y)例試證明下面蘇格拉底論證：所有人都是要死的，蘇格拉底是人，因此，蘇格拉底是要死的。證明：令M(x)： x是人，D(x)： x是要死的，s:蘇格拉底，原題 可符號化為：(x)( Mx)-D(x) , Ms)卜

19、 D(s)推證如下：1(1)(x)(Mx)-Rx)P1(2)Ms)-Rs)UI,(1)3 (3)Ms)P1,3(4)D(s)T,(2),(3),I例證明(x)A(x)證明：反證法(x) (A(x)( x) (A(x)(x)B(x) (B(x)B(x)x)(A(x)B(x)P(附加前提)T, (1), E(4) A(a) A B(a)(5) A(a)(6) B(a)(7) (x)A(x)(8) (x)A(x)(9) (x)B(x)(10) B(a)(11) B(a) A B(a)(A(a)B(a)T, (2), EST, (3), IT, (4), IT, (4), IT, (5), EG(x)

20、 B(x)P 前提T,(8), IT, US(6)(10)矛盾三.集合例在一個住著一些人家的僻靜孤島上，島上只有一個理發(fā)師a,a給且只給島上所有不能自己理發(fā)的人理發(fā)。問誰給a理發(fā)解：設(shè)S = x | x 是不能自己理發(fā)的人。(1)若a S,則a給自己a理發(fā)。又由題意知，a只給不能自己 理發(fā)的人理發(fā)，所以a是不能自己理發(fā)的人，即a S,矛盾。(2)若a S,則a是不能自己理發(fā)的人。又由題意知，a只給 集合S中的人理發(fā)，所以a要給a理發(fā)，即a S ,矛盾。無論如何，都有a S和a S同時成立。這是著名的羅素悖論paradox。例令 A=1,2,3,4,B=4,5,5,6,則UA=1,2 U 3 =

21、1,2,3,U B=5 U 5,6=5,6,n A=1,2 n 3=,n B=5 n 5,6=5四.關(guān)系例設(shè) A = 1, 3, 5, B = 2, 4, 6, 8,定義 A 到 B的二元關(guān)系R: ? a, b ? R當(dāng)且僅當(dāng)a? b,則稱R為A到B的 “小于”關(guān)系。R= ? 1,2? ,? 1,4? , ? 1,6? ,? 1,8? , ? 3,4? , ?3,6? ,? 3,8? ,? 5,6? , ? 5,8? 是A到B的一個關(guān)系，顯然R AXB。而？ 3,2? R, ? 5,2? R, ? 5,4?R。例 設(shè) A = 1,2, 3, 4, 5, 6, B = a, b, c, d,關(guān)系

22、 R = ? 2, a? , ? 2, b? , ? 3, b? , ? 4, d? , ? 6, d? , 則dm(R) = 2, 3, 4, 6,rn(R) = a, b, d,fl(R)=2,3,4,6,a,b,d。例設(shè) A = 1, 2, 3, B=1, 2, 3, 4,從 A到 B上的關(guān)系 R=?1,1 ? , ? 2,2? ,? 3,3? ,S=? 1,1 ? , ? 1,2? ,? 1,3? , ? 1,4? ,則RU S=? 1,1 ? , ? 2,2? ,? 3,3? , ? 1,2? , ? 1,3? ,? 1,4? RA S=? 1,1 ? R-S=? 2,2? ,? 3

23、,3? S-R=? 1,2? ,? 1,3? ,? 1,4? R'= ? 1,2? ,? 1,3? , ? 1,4? ,? 2,1 ? ,? 2,3? ,? 2,4?,? 3,1? ,? 3,2? , ? 3,4? 要注意的是，作為關(guān)系，補運算是對全域關(guān)系而言的，并不是 對全集U而言的。例 設(shè)A和B分別是學(xué)校的所有學(xué)生和所有課程的集合。假設(shè) R 由所有有序?qū)Γ?a,b?組成，其中a是選修課程b的學(xué)生。S由所有 有序?qū)Γ?a,b?構(gòu)成，其中課程b是a的必修課。什么是關(guān)系 RU S, RA S, R S, R-S 和 S-R解：關(guān)系RU S由所有的有序?qū)Γ?a,b?組成，其中a是一個學(xué)生，

24、 他或者選修了課程b,或者課程b是他的必修課。RA S是所有有序?qū)?? a,b?的集合，其中a是一個學(xué)生，他選修了課程 b并且課程b也 是a的必修課。R S由所有有序?qū)Γ?a,b?組成，其中學(xué)生a已經(jīng) 選修了課程b,但課程b不是a的必修課，或者課程b是a的必修課， 但a沒有選修它。R-S是所有有序?qū)Γ?a,b?的集合，其中a已經(jīng)選 修了課程b但課程b不是a的必修課。S-R是所有有序?qū)Γ?a,b?的 集合，其中課程b是a的必修課，但a沒有選它。例設(shè)A = a, b, c, d, A上的關(guān)系R = ? a, a ? ,? a, b ? ,? b, d ? ,S = ? a, d ? ,? b, c

25、 ? ,? b, d ? ,? c, b?。求 R*S 和 S*R。解：R*S = ? a, d ? , ? a, c ? ;S*R = ? c, d ? 顯然R*S豐S*R從本例可知復(fù)合關(guān)系不滿足交換律。兄弟關(guān)系和父子關(guān)系的復(fù)合是例設(shè) A = a, b, c, d, e, f ,R =? a, b ? , ? b, c ?f? 。求 Rn (n =1, 2, 3, 4,解：R1 = R;R2 = R*R =? a, c ?f? ；R3 = R2*R =? a, d ?R4 = R3*R =? a, e ?R5 = R4*R = ? a, fR6 = R5*R =;R7 =;Rn =( n &

26、gt;5 )。叔侄關(guān)系? c, d ? ,? d, e ? , ? e,)。> b, d ? ,? c, e ? ,? d,? b, e ? , ? c, f ? ;? b, f ? ；例設(shè) A = a, b, c, d, 1, 2, 3, 4, A上的關(guān)系R = ? a, 2 ? ,? b, 2 ? , ? b, 3 ? , ? d, 4 ? ,則R- 1 = ?2, a?,?2, b?,?3, b?, ?4, d?。例設(shè)A = a, b, c, B = 0, 1,有A到B的關(guān)系R = ? a, 0? , ? b, 0? , ? c, 1? , S = ? a, 1? , ? b, 1

27、? , ? c, 1 ? 則 R- 1=? 0, a? , ? 0, b? , ? 1,c? , S- 1=? 1, a? ,? 1, b? , ? 1, c ? RUS = ? a, 0 ? ,? b, 0 ? ,? c, 1 ? , ? a, 1 ?,? b, 1 ? ；(RUS) - 1 = R - 1US- 1= ? 0, a? ,? 0, b? ,? 1, c? ,? 1, a? ,? 1, b ? ；RA S = ? c, 1 ? ;(RAS) - 1 = R - 1AS- 1= ? 1, c ? ;R S = ? a, 0 ? ,? b, 0?;(R - S) - 1 = R1

28、- S - 1 = ? 0, a ? , ? 0, b?;dm R- 1 = rn R = 0, 1;rn(S - 1)= dm(S) = a, b, c例設(shè) A = 2, 3, 4, B = 2, 3, 4, 5, 6,定義 A 到 B 的二元關(guān)系R:aRb當(dāng)且僅當(dāng)a整除b。R=? 2, 2? , ? 2, 4? , ? 2, 6? , ? 3, 3? , ? 3, 6?4, 4 ? 2 3 4 5 62 1 0 1 0 1MR= 3 0 1 0 0 14 0 0 1 0 0例 S = a, b, c, S 上的關(guān)系R1 = ?a,a?,?b,b?,? c, c ? , ? b, c ?R2

29、 = ?a,b?,?b,a?R3 = ?b,b?,?c,c?R1 是自反的 , R2 不是自反的, R3 也不是自反的。R1 不是非自反的, R2 是非自反的, R3 也不是非自反的。例 設(shè) A= 2,3,5,7 , R= ? x, y ? |(x-y)/2是整數(shù),驗證 R在A上是自反和對稱的。證：因為對于任意 x6A, (x-x)/2 =0,即？ x, y ? 6R,故R是自反的。又設(shè) x,y 6 A,如果？ x, y? 6 R,即(x-y)/2是整數(shù)，則(y-x)/2是整數(shù)，即？ y, x ? 6 R故R是對稱的。事實上，關(guān)系 R= ? 2, 2 ? , ? 3, 3 ? , ? 5, 5

30、 ? , ? 7, 7 ?,?3, 5?, ?5, 3?, ?3, 7?, ?7, 3?, ?5, 7?, ?7, 5?例 設(shè) X= 1,2,3 , R1=? 1, 2 ? , ? 2, 2 ? , R2 = ? 1, 2? , R3 = ? 1,2 ? , ? 2, 3 ? , ? 1, 3 ? , ? 2, 1 ? , R1,R2,R3 都是傳遞關(guān)系嗎證：根據(jù)傳遞的定義，R1和R2是傳遞的。但對于R3,因為？ 1, 2?6 R3, ? 2, 1 ? 6 R3,但？ 1, 1 ?R3,故 R3不是傳遞的。注意：R2是傳遞的。例在集合S = a, b, c, d 上的關(guān)系R= ? b, c ?

31、 , ? c, c ? , ? c, d ? , ? d, c ? ,判斷 R 的性質(zhì)。解R不是自反的；? c, c ?R,所以R不是非自反的；? b, c ? R,但？ c, b ? R,所以R不是對稱的；? c, c ?R,所以R不是非對稱的；c d,但？ c, d ? R且？ d, c ? R,所以R不是反對稱 的；? b, c? R, ? c, d? R,但？ b, d ? R,所以 R不是可 傳遞的。例 A = 1,2, 3, 4, 5, 6,7, R是A上的模3同余關(guān)系。顯然R是A上的等價關(guān)系，A中各元素關(guān)于R的等價類分別是1R = 1,4, 7, 4 R= 1,4, 7, 7 R

32、= 1,4, 72 R = 2, 5,5 R = 2, 5,3 R = 3, 6,6 R = 3, 6,可以看出，彼此等價的元素其等價類是相同的，所以不同的 等價類僅有3個，它們是1 R, 2 R 和3 R。例 若A = 2, 3, 4, 6, 8,偏序關(guān)系是整除關(guān)系，4 3是A的極小元，6和8是A的極大元。1 .我們先看極小元，從最大的數(shù)8開始，因為4< 8（即4整除8）,故8不是極小元，那么4是不是極小元呢 因為2W 4,所以4也不是極小元，那么2是不是極小元呢 由于A中沒有任何其它元素x,滿足xw 2,故2是A的極 小元。同理，3也是A的極小元。4不是，因為2W4。2 .對于極大元

33、，我們從最小的數(shù) 2開始，因為2< 4（即2整除4）,故2不是極大元，那么4是不是極大元呢 因為4W8,所以4也不是極大元，那么8是不是極大元呢 由于A中沒有任何其它元素x,滿足8W x,故8是A的極 大元。同理，6也是A的極大元。4不是，因為4<8O從本例可知，極小元和極大元不是唯一的。例若A = 2, 3, 4, 6, 8,偏序關(guān)系是整除關(guān)系，則 A中既沒有最小元，也沒有最大元。因為2不能整除A中所有元素（如2不能整除3）, 所以2不是A的最小元，顯然其余元素也不是。同理，8也不能被A中所有元素所整除，所以8不是A的最大元。實際上，A中所有元素 的（最大）公約數(shù)和（最?。┕稊?shù)

34、均不屬于A,所以A中既沒有最小元, 也沒有最大元。又如B = 2, 4, 6, 8,偏序關(guān)系是整除關(guān)系，則B的最小元是2,沒有最大元。又如C=2, 4, 8,偏序關(guān)系是整除關(guān)系， 則C的最小兀是2,最大兀是8。五.函數(shù)與基數(shù)（這部分不是重點，了解就行）六.代數(shù)結(jié)構(gòu)本章是重點，主要內(nèi)容是掌握各種代數(shù)結(jié)構(gòu)的性質(zhì)及使用。按照課本的劃分同時包括群環(huán)和格和布爾代數(shù)。例 12.3.6 給定 <S, U, n >,其中 S= , A, B, Q, U和 A 是一般的集合運算；又有<T, >，這里T = 1,2, 5, 10, 且對于 a, b£T有 a b = lcma, b（最小公倍數(shù)），a b = gcda, b（最大公約數(shù)），表至表給出四個運算表。試說明<S, n , U ><T,解：令 f TS: f( )=1, f(A)=2, f(B)=5, f(Q=10。顯然，f是從S到T的雙射。經(jīng)驗證，對任意 x1, x2 S,又有f (x1 U x2)=f (x1)f (x2)f(x1x2)=f(x1)f(x2)故& n, u 與丁，是同構(gòu)的表 1233J 0 A B C表 1234n 0 A