離散證明題集錦

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

2、 B當(dāng)且僅當(dāng)A? B是個重言式。（前面已證）證明：若A B,則對于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ī)則）。證明：因?yàn)閷ψ冊娜我唤M指派，A1與B1真值相同，故以B1取代A1后，公式B與公式A相對于變元的任一指派的真值也必相 同，所以A Bo證明下列命題公式(可以利用基本等價式)Q-(PV(PAQ) Q-P(PAQ)V(PAi Q) P(P-Q)-(

3、Q VR) PVQV RPA QVQ PVQ解：1.原式Q-(PVP) A (PVQ) Q-PA(PVQ)Q-P2 .原式(PAQ) VP) A(PAQ) VI Q) (PVP) A (PVQ) A(PVn Q) A(QVi Q)PA (PVQ) A(PVn Q) PAP P3 .原式( J PVQ) V(QVR) (PA Q) V(QVR) (PVQVR) A(QVi QVR) PVQVR (零率)4 .原式(PA Q) VQ (PVQ) A(n QVQ) PVQ (運(yùn)算次級優(yōu)先級:,A, V,例：求證：(P -Q) V I (P -Q)為永真式。解：原式 J PVQ) V (PAi Q)(

4、 PVQVP) A J PVQ5 Q)T例：求證QA(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和Q-P是重言式，即P? Q為重言 例 已知A是B的充分條件，B是C的必要條件，C是D的必要條件, D是B的必要條件，問：(1) A是D的什么條件？B是D的什么條件？解 已知A B, C B, D C, B D,故有A B, B D,所以A D,即A是D的充分條件DC, C B,所以D B,又因?yàn)锽 D,

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

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

7、所以推理不正確.還可用其他方法判斷之例 證明下列前提是不相容的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 SPP(1)； I1S(1); I2P QPQ,(4)； I8(6)S RPR(3),(6)； I8(8)(9) R (5),(8); I9(10)

8、RA R(7),(9)例 張三說李四在說謊，李四說王五在說謊，王五說張三、李四都在說謊。問誰說真話，誰說假話？解 設(shè)A:張三說真話；B:李四說真話；C:王五說真話依題意有A B, B C, C A A Bo(A B)A (B C)A(C A A B)(A B) A ( B A) A (B C) A ( C B) A (C ( AA B) A(AA B) C)(AABA C) A (A V B) A C) A ( A A BA C) V (A A C) V(BA C)AABA C即：李四說真話，張三和王五說假話。例1.9.3:求證：S是前提 W, W7 Q,i QR和RS的有 效結(jié)論。證明：1(

9、1) W 一 I Q P2(2) 1 Q-R P1,2 W R T,(1)(2)I113(4) W P1,2,3 (5) R T,(3)(4)I84(6) R S P1,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) S P(2) R

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

11、;結(jié)論：S Q證明(1) S CP(2) RSP(3) SR(2), E(4) R (1),(3), I(5) P R P(6) R P (5), E(4), (6), IPV Q P(9) P Q (8), E(10) Q (7),(9), I(11) S Q (1), (10), CP(CP規(guī)則這部分因?yàn)楹孟穸嗔艘粋€條件，所以用起來可能會比較簡 單)例1.9.5:證明R-S可從前提P-(Q-S), I RVP和Q推出。 證明：(CP規(guī)則，因?yàn)榻Y(jié)論R-S為條件式)1(1) RVP P2(2) RP(附加前提)1,2(3) P T,(1)(2)I103(4) P-(Q-S)P1,2,3 (5)

12、 Q-ST, (3,4)I84(6) Q P1,2,3,4 (7) ST,(5)(6)I81,3,4(8) R-S CP,(2)(7)例1.9.4:證明從前提P-Q, (QVR)可演繹出1P.證明：(反證法)1(1) P P (附加前提)2(2) PQ P1,2 Q T,(1)(2)I83(4) (QVR) P3(5) QA RT, (4)E53(6)i Q (5)I11,2,3 (7) Q An Q T,(3)(6)例 如果春暖花開，燕子就會飛回北方。如果燕子飛回北方，則冰雪 融化。所以，如果冰雪沒有融化，則沒有春暖花開。”證明這些語句構(gòu)成一個正確的推理。證：令P:春暖花開。Q:燕子飛回北方

13、。R:冰雪融化。則上述問題轉(zhuǎn)化成證明：P Q, QRR P利用CP規(guī)則，將 R作為附加前提,推導(dǎo) P,從而推導(dǎo)出R P。編號公式依據(jù)(1)Q RP(2)RP(附加前提)(3)Q,(2)； I9(4)P Q(5)P,(4)； I9課堂練習(xí):(1) 基本等價公式的轉(zhuǎn)換方法驗(yàn)證下列推斷是否有效。(1)P Q, RAS, Q RAS;(2) P Q, Q R, R PPVQVR;(3)P, Q R, RVS QS;(4) QA R, RAP, QPV Q。2.用推理規(guī)則證明下述論斷的正確性。(1)P, P (Q (RAS)QS;P (Q R), R (QS)P(QS);P(Q R) (Q (R S)

14、(P (Q S);(4) (P Q) (RVS),(QP)VR,R P Q。3. A, B, C, D四人中要派兩個人出差，按下述三個條件有幾種派法？如何派？若A去，則C和D中要去一人。(2)B和C不能都去。(3)C去則D要留下。4. A, B, C, D四人參加考試后，有人問它們，誰的成績最好。A說不 是我"，B說 是D"，C說 是B"，D說 不是我"。四人的回答只有 一人符合實(shí)際，問是誰的成績最好？只有一人成績最好的是誰？5. 判斷下列推理是否正確：(1)如果我是小孩，我會喜歡熊貓。我不是小孩，所以我不喜歡熊貓。(2)如果太陽從西邊出來，那么地球停止

15、轉(zhuǎn)動。太陽從西邊出來了，所以地球停止了轉(zhuǎn)動。二.謂詞邏輯例試用量詞、謂詞表示下列命題：所有大學(xué)生都熱愛祖國； 每個自然數(shù)都是實(shí)數(shù)；一些大學(xué)生有遠(yuǎn)大理想；有的自然數(shù)是素數(shù)。解 令S(x): x是大學(xué)生，L(x): x熱愛祖國，則所有大學(xué)生都熱愛祖國(x)(S(x)- L (x) 令N(x): x是自然數(shù)，R(x): x是實(shí)數(shù)，則每個自然數(shù)都是實(shí)數(shù)(x)(N(x)-R(x)全稱量詞(x)后跟條件式。令S(x): x是大學(xué)生，I(x): x有遠(yuǎn)大理想，則一些大學(xué)生有遠(yuǎn)大理想(x)(S(x) A I (x)令N(x): x是自然數(shù)，P(x): x是素數(shù)。則有的自然數(shù)是素數(shù)(x)(N(x)AP(x)存在

16、量詞(x)后跟合取式。例 令f(x):x小于88, g(x):x是奇數(shù)，(x) (f(x) A g(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)(P(x)f Q(x,y)AR (x,y)中的約束變元改名。下面哪個正確？(注意到此公式中，約束變元只有x),1) ( y)(P(

17、y) -Q (y,y)AR(x,y)2) ( z)(P(z) -Q (x,y)AR (x,y)3) ( z)(P(z) -Q (z,y)AR (x,y)例：將公式(x)(P(y)-Q(x,y)AR (x,y)中的自由變元代入。(注意到此公式中y為自由變元，x既是約束出現(xiàn)，也是自由出現(xiàn)。) 我們以y為例，試判斷下面哪個正確？1) ( x)(P(z) -Q (x,z)AR (x,y)2) ( x)(P(x) -Q (x,z)AR (x,x)3) ( x)(P(z) -Q (x,z)AR (x,z)例 在公式(x) (Q(x) - R(x, y)V(z) P(x, z)中，x既為約束出現(xiàn)，又為自由出

18、現(xiàn)，下面用兩種方法，使變元x在公式中只呈一種形式出現(xiàn)解用約束變元的改名規(guī)則得：(u) (Q(u) - R(u, y) V( z) P(x, z);或用自由變元得代入規(guī)則得(x )(Q(x) - R(x, y) V( z) P(u, z)。(重做前一例題，將自由出現(xiàn)的 x進(jìn)行代入)重做例：將公式(x)(P(y)-Q(x,y)AR (x,y)中的自由變元代入。注意到此公式中y為自由變元，x既是約束出現(xiàn)，也是自由出現(xiàn)。這次，我們將自由出現(xiàn)的x代入,得：(x)(P(y) -Q (x,y)AR(z,y)例 試證明下面蘇格拉底論證：所有人都是要死的，蘇格拉底是人，因此，蘇格拉底是要死的。證明：令M(x):

19、x是人，D(x):x是要死的，s:蘇格拉底，原題可符號化為：(x)(M(x)-D(x), M(s)卜 D(s)推證如下：1(x)(M(x)-D(x)P1M(s)-D(s)UI,(1)3(3)M(s)P1,3(4)D(s)T,(2),(3),I例 證明(x)A(x) ( x)B(x) ( x)(A(x)B(x)證明：反證法(x) (A(x)B(x)P(附加前提)(x) (A(x)B(x)T, (1), E(A(a)B(a)T, (2), ES(4) A(a) A B(a)T, (3), I A(a)T, (4), I(6) B(a)T, (4), I(7) ( x) A(x)T, (5), EG

20、(8)( x) A(x) ( x) B(x)P前提T, (7)(8), IT, US(6)(10)矛盾(9) ( x) B(x)(10) B(a)(11) B(a)A B(a)三.集合例在一個住著一些人家的僻靜孤島上，島上只有一個理發(fā)師a, a給 且只給島上所有不能自己理發(fā)的人理發(fā)。問誰給 a理發(fā)？解：設(shè)S = x | x是不能自己理發(fā)的人。 若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

21、同時成立。這是著名的羅素悖論paradox。例令 A=1,2,3,4, B=4,5,5,6,則UA=1,2U3=1,2,3,U B=5 U 5,6=5,6,AA=1,2A3二,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)aQ 則稱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 AX B。而?3,2? R, ?5,2? R, ?5,4? R。例 設(shè) A = 1,

22、2, 3, 4, 5, 6, B = a, b, c, d,關(guān)系 R = ?2, a? ?2, b? ?3, b? ?4, d?石,d?,貝Udm(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?,2?,3?1,4p,則RUS=?1,1?2,2?,?3,3?, ?1,2?,3?,?1,43RAS=?1,ipR-S=?2,2?3,3?S-R=?1,2?1,3?,4?R'=?1,2?1,3?,

23、4?, R,1?,23?,?2,4? ?3,1?3,2?3,4?要注意的是，作為關(guān)系，補(bǔ)運(yùn)算是對全域關(guān)系而言的，并不是對全集 U而言的。例 設(shè)A和B分別是學(xué)校的所有學(xué)生和所有課程的集合。假設(shè) R由 所有有序?qū)?？a,b?fi成，其中a是選修課程b的學(xué)生。S由所有有序?qū)??a,b?勾成，其中課程b是a的必修課。什么是關(guān)系RUS,RAS,R S, R-S 和 S-R ?解：關(guān)系RUS由所有的有序?qū)Γ縜,b磔成，其中a是一個學(xué)生，他或 者選修了課程b,或者課程b是他的必修課。RAS是所有有序?qū)?？a,b? 的集合，其中a是一個學(xué)生，他選修了課程 b并且課程b也是a的 必修課。R S由所有有序?qū)Γ縜,b理

24、成，其中學(xué)生a已經(jīng)選修了課程 b,但課程b不是a的必修課，或者課程b是a的必修課，但a沒有 選修它。R-S是所有有序?qū),b?l勺集合，其中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? Q d? ?c, b?。求 R*S 和 S*R。解：R*S = ?a, d? ?a, c?;S*R = 寬,d?h顯然 R*S豐S*R從本例可知復(fù)合關(guān)系不滿足交換律。兄弟關(guān)系和父子關(guān)系的復(fù)合是 叔侄關(guān)系例設(shè)

25、 A = a, b, c, d, e, f ,R =?a, b? ?d, c? ?c, d?,?d, e? ?e, f?。求 Rn (n =1, 2, 3, 4,)。解：R1 = R;R2 = R*R = ?a, c? ?b, d?,覺，e? ?d, f?;R3 = R2*R = ?a, d? ?d, e? ?c, f?;R4 = R3*R = ?a, e?, ?b, fp；R5 = R4*R = ?a, f?;R6 = R5*R =;R7 =:Rn =(n >5 )。例設(shè) A = a, b, c, d, 1,2, 3, 4, A 上的關(guān)系R = ?a,2?,?b,2?, ?b, 3?,

26、?d,4?,則RT = ?2,a?2b? ?3, b?,?4,d?。例設(shè)A = a, b, c, B = 0, 1,有A到B的關(guān)系R = ?a, 0? ?b, 0? ?c, 13, S = ?a, 1? Q 1? ?c, 1?則 RT=?0, a?,?0, b?, ?1,c?, ST=?1, a?, b?, c?RUS = ?a, 0?, ?b, 0?, ?c, 1?, ?a, 1? Q 1?;(RUS) - 1 = RTUST=?0, a? ?0, b? ?1, c? ?1, a? ?1, b?;RAS = ?c, 1?;(RAS) - 1 = RTAST= ?1, c?;R - S = ?

27、a, 0?, ?d, 0?;(R - S) - 1 = RT - S1 = ?0, a?, ?0,b3;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 10 10 1MR=例S = a, b, c, S上的關(guān)系R1 = ?a, a? ?d,b? ?c, c?d,c?R2 = ?a, b?, ?d, a?R3 = ?b

28、, b?覺，c?R1是自反的，R2不是自反的，R3也不是自反的。R1不是非自反的，R2是非自反的，R3也不是非自反的例 設(shè)A = 2,3,5,7, R = ?x, y?|(x-y)/2是整數(shù),驗(yàn)證R在A上是自反和對稱的。證：因?yàn)閷τ谌我鈞6A, (x-x)/2=0，即?x, y?6 R,故R是自反的。又設(shè)x,y6A,如果？x, y?6 R,即(x-y)/2是整數(shù)，則(y-x)/2是整數(shù), 即征x?6 R,故R是對稱的。事實(shí)上，關(guān)系 R= ?2, 2?, ?3, 3?, ?5, 5?, 27,7? ?3, 5?, ?5, 3?, 23,7? ?7, 3?, ?5, 7?, ?7, 5?例設(shè) X

29、= 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,因?yàn)椋?, 2?6R3, 2 1?6 R3,但？1, 1?R3,故 R3 不是傳遞的。注意：R2是傳遞的。例在集合S = a, b, c, d上的關(guān)系R= Q 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,

30、d? R且？d, c? R,所以R不是反對稱的；Q c? R,覺,d? R,但 Q 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= 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)系，則2和3是A的極小元，6和8是A

31、的極大元。1 .我們先看極小元，從最大的數(shù)8開始，因?yàn)?W8（即4整除 8）,故8不是極小元，那么4是不是極小元呢？因?yàn)?W4, 所以4也不是極小元，那么2是不是極小元呢？由于 A 中沒有任何其它元素x,滿足xW2,故2是A的極小元。同理，3也是A的極小元。4不是，因?yàn)?W4。2 .對于極大元，我們從最小的數(shù)2開始，因?yàn)?W4（即2整除 4）,故2不是極大元，那么4是不是極大元呢？因?yàn)?<8, 所以4也不是極大元，那么8是不是極大元呢？由于 A 中沒有任何其它元素x,滿足8Wx,故8是A的極大元。同理，6也是A的極大元。4不是，因?yàn)?<8O從本例可知，極小元和極大元不是唯一的。例若

32、A = 2, 3, 4, 6, 8,偏序關(guān)系是整除關(guān)系，則A中既沒有最小元， 也沒有最大元。因?yàn)?不能整除A中所有元素（如2不能整除3）,所以2不是A的最小元，顯然其余元素也不是。同理， 8也不能被A中所 有元素所整除，所以8不是A的最大元。實(shí)際上，A中所有元素的（最 大）公約數(shù)和（最小）公倍數(shù)均不屬于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ù)（這部分不是重點(diǎn)，了解就行）六.代數(shù)結(jié)構(gòu)本章是重點(diǎn)，主要內(nèi)容是掌握各種代數(shù)結(jié)

33、構(gòu)的性質(zhì)及使用。按照課本的劃分同時包括群環(huán)和格和布爾代數(shù)。例 12.3.6 給定 <S, U, n >,其中 S= , A, B, C, U和 A是一 般的集合運(yùn)算；又有<T,>,這里T = 1, 2, 5, 10,且對于a, b6T 有 a b = lcma, b（最小公倍數(shù)），a b = gcda, b（最大 公約數(shù)），表12.3.3至表12.3.6給出四個運(yùn)算表。試說明<S, A, U> 二 <，>.解：令 f TS: f( )=1, f(A)=2, f(B)=5, f(C)=10。顯然，f 是從 S到T的雙射。經(jīng)驗(yàn)證，對任意 x1, x2 S,又有f(x1 Ux2)=f(x1) f(x2)f(x1 Ax2)=f(x1) f(x2)故s, n, u 與，是同構(gòu)的。表 1233U 0 A B C表 1234r 0 A B c0 0 A B CABCA A C CB C B CC C C C表