數(shù)理邏輯與代數(shù)系統(tǒng)重點(diǎn)整理

離散數(shù)學(xué)重點(diǎn)整理By迷若煙雨第1章命題邏輯主要內(nèi)容1.1命題與聯(lián)結(jié)詞11.2命題公式與翻譯21.3真值表與等價(jià)公式31.4重言式與蘊(yùn)含式41.5其他聯(lián)結(jié)詞51.6對(duì)偶與范式61.7推理理論7應(yīng)記住的等價(jià)公式（都可以通過真值表驗(yàn)證）1對(duì)合律

PP（雙重否定律）2冪等律 PPPP∧PP3結(jié)合律 (PQ)R

P(QR) (P∧Q)∧

R

P∧(Q∧

R)4交換律 PQQP P∧QQ∧P5分配律 P(Q∧R)

(PQ)∧(P

R) P∧(Q

R)

(P∧Q)(P∧R)6吸收律 P(P∧Q)

P

P∧(PQ)

P7德.摩根律

(PQ)P∧Q

(P∧Q)PQ應(yīng)記住的等價(jià)公式8同一律 P∧TP PFP9零律 PTT P∧FF10否定律 P

P

T P∧

P

F（補(bǔ)余律）補(bǔ)充：11蘊(yùn)含表達(dá)式 PQPQQP12等價(jià)表達(dá)式 PQ(PQ)∧(QP) (PQ)∧(QP)

(P∧Q)(P∧Q)蘊(yùn)涵式證明方法1）直接證法（前件真推導(dǎo)后件真）假定公式的前件為真，若能推導(dǎo)出后件也為真，則條件式是重言式，即蘊(yùn)含式成立。2）間接證法/反證法（后件假推導(dǎo)前件假）假定后件為假，若能推導(dǎo)出前件也為假，則條件式是永真式，即蘊(yùn)含式成立。例3：證明

(PQ)P證1：設(shè)(PQ)為T， 則PQ為F，于是P為T。或設(shè)(PQ)為T， 則(P

Q)為T， 即P∧Q為T，P為T。證2：設(shè)P為F， 則PQ為T， 故(PQ)為F，因此(PQ)P。書第20頁所列各蘊(yùn)含式都可以用這兩種推理方法證明。3）條件式永真法（按定義證）將蘊(yùn)含式改為條件式，利用等價(jià)代換證明該條件式的真值為永真。4）真值表法（以上三種證法都可以用真值表驗(yàn)證）3.最小聯(lián)結(jié)詞組/極小全功能聯(lián)結(jié)詞集合定義：如果A是聯(lián)結(jié)詞完備集，且A中聯(lián)結(jié)詞不能夠相互等價(jià)的表示出來，則稱A為最小聯(lián)結(jié)詞組/極小全功能聯(lián)結(jié)詞集合。那么考慮{?，，}是否最小聯(lián)接詞組？PQ(PQ)(P∧Q)P∧Q(P∧Q)(PQ)

說明∧和可以等價(jià)地相互表示。{,}、{,∧}、{,}、{↓}、{↑}都是最小聯(lián)結(jié)詞組。利用等價(jià)公式求主析取范式的步驟化歸為析取范式；去掉析取范式中所有永假的項(xiàng)（即含形如P∧P的項(xiàng)）；合并相同變?cè)拖嗤先№?xiàng)；對(duì)合取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變?cè)?，即添?PP)式，然后應(yīng)用分配律展開公式。

與主析取范式類似的是主合取范式。注意：大項(xiàng)與小項(xiàng)編碼不同。如M000=PQR,m111=PQR，上例用編碼形式表示如下：主析取范式Am001m110

m111

1,6,7主合取范式AM000∧M010∧M011∧

M100∧M101

0,2,3,4,5利用等價(jià)公式求主合取范式步驟化歸為合取范式；除去合取范式中所有永真的析取項(xiàng)；（即去掉含PP形式的項(xiàng)）合并相同的析取項(xiàng)和相同的變?cè)?；?duì)析取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變?cè)刺砑覲∧P形式的項(xiàng)，然后利用分配律展開公式，并去掉相同的析取項(xiàng)。解：A(PR)∧(QP)(PR)∧(PQ)∧(QP)(PR)∧(PQ)∧(QP)((PR)(Q∧Q))∧((PQ)(R∧R))∧((P

Q)(R∧R))(PRQ)∧(PQR)∧(PQR)∧(PQR)∧(P

QR)∧(PQR)(PRQ)∧(PQR)∧(PQR)∧(PQR)∧(P

QR)M000∧M010∧M100∧M101

∧M0110，2，3，4，5例6：利用等價(jià)公式推導(dǎo)求A(PR)∧(QP)的主合取范式由此可知，由A的主析取范式求主合取范式的步驟為：(1)求出A的主析取范式中沒有包含的小項(xiàng)，即A；(2)求出與(1)中小項(xiàng)的編碼相同的大項(xiàng)；(3)(2)中大項(xiàng)的合取式，即為A的主合取范式。例8：設(shè)A(P∧Q∧R)(P∧Q∧R)(P∧Q∧R)(P∧Q∧R)(P∧Q∧R)7,5,4,3,2由定理3，A的主析取范式為：A0,1,6(P∧Q∧R)(P∧Q∧R)(P∧Q∧R)AA0,1,6

(PQR)∧(PQR)∧(PQR)

即為A的主合取范式。

類似的，由A的主合取范式也可以求出A的主析取范式。3.演繹法由一組前提，利用一些公認(rèn)的推理規(guī)則，根據(jù)已知的等價(jià)或蘊(yùn)含公式，推理得到有效結(jié)論。（1）P規(guī)則（前提引入規(guī)則）：在推導(dǎo)過程中可以隨時(shí)引入前提集合中的任意一個(gè)前提；（2）T規(guī)則（結(jié)論引用規(guī)則）：在推導(dǎo)中，如果有一個(gè)或多個(gè)公式蘊(yùn)含公式S，則公式S可引入推導(dǎo)之中（如PQ,QRPR，這時(shí)PR可引入推導(dǎo)之中）。證：(1) PQ P (消去P,Q為目的) (2) PQ T(1)E16 (為了消去Q,經(jīng)常把PQ變?yōu)镻Q) (3) QS P (4) PS T(2)(3)I13 (5) PR P (6) RP T(5)E18 (7) RS T(4)(6)I13 (8) RS T(7)E16

原式成立。例3：證明(PQ)，(PR)，(QS)SR4.間接證法定義：假設(shè)公式H1,H2,…,Hn中的命題變?cè)獮镻1,P2,…,Pk，對(duì)于P1,P2,…,Pk的一些真值指派，如果能使H1∧H2∧…∧Hn的真值為T，則稱公式H1,H2,…,Hn是相容的。如果對(duì)于P1,P2,…,Pk的每一組真值指派使得H1∧H2∧…∧Hn的真值均為F，則稱公式H1,H2,…,Hn是不相容的。（1）要證明H1,H2,…,HnC，證C與H1,H2,…,Hn是不相容的即可。說明：要證明H1,H2,…,HnC，記SH1,H2,…,Hn，即要證SC，即SC永真，即SC永真，(SC)永假，即C∧S永假。證： (1)(P) P(附加前提) (2)PQ P (3)Q T(1)(2)I11 (4)QR P (5)R T(3)(4)I10 (6)R∧S P (7)R T(6)I1 (8)R∧R(矛盾) T(5)(7)I9例5：證明PQ,QR,R∧SP（2）間接證法的另一種情況是： 要證明H1∧H2∧…∧Hn(RC)，如能證明 H1∧H2∧…∧Hn∧RC即可。這種證明方法稱為CP規(guī)則（記SH1∧H2∧…∧Hn）說明：因?yàn)橐CSRC，即要證S(RC)為重言式，而S(RC)SRC (S∧R)C(S∧R)C，即只需要證S∧RC是重言式，也就是要證S∧RC。因此如果證明了S∧RC，即證明了S(RC)。注意：這種方法，其結(jié)論必須是條件式形式，或經(jīng)轉(zhuǎn)化變?yōu)闂l件式形式。小結(jié)1、證明蘊(yùn)含式PQ的方法（其中P可為一組前提）1）真值表法；2）設(shè)P為T，推出Q為T；3）設(shè)Q為F，推出P為F；4）推導(dǎo)PQ為重言式；（利用等價(jià)公式推導(dǎo)）5）推理規(guī)則的演繹法；6）推理規(guī)則的反證法；7）推理規(guī)則間接證法2）CP規(guī)則，應(yīng)注意其結(jié)論必須是RC的形式。比較上述方法，一般用推理歸則比較好。小結(jié)2、證明等價(jià)式的方法（AB）1）真值表法（適于變?cè)^少的情況）2）證AB為重言式（等價(jià)推導(dǎo)法）3）等價(jià)推導(dǎo)A……B4）把A,B都化為主析（合）取范式，若兩主范式相同，則AB。20謂詞、命題函數(shù)與量詞1謂詞公式與翻譯2變?cè)募s束3謂詞演算的等價(jià)式與蘊(yùn)含式4前束范式5謂詞演算的推理理論6

主要內(nèi)容第二章謂詞邏輯21如果沒有給出個(gè)體域，都應(yīng)該以全總個(gè)體域?yàn)閭€(gè)體域。引入特性謂詞后，使用全稱量詞與存在量詞符號(hào)化的形式是不同的，一般：全稱量詞(x)：作為條件式的前件 例：所有的人都是要呼吸的

M(x):x是人H(x):x要呼吸

(x)(M(x)H(x))存在量詞(x)：作為合取項(xiàng) 例：有些人沒有來上課

M(x):x是人C(x):x沒來上課

(x)(M(x)C(x))

說明在使用量詞時(shí)應(yīng)注意以下幾點(diǎn)：22多個(gè)量詞同時(shí)出現(xiàn)時(shí)，不能隨意顛倒次序。

例：“對(duì)任意的x，存在y，使得x+y=5”，個(gè)體域?yàn)镽

則命題符號(hào)化為：(x)(y)H(x,y) 是個(gè)真命題 而(y)(x)H(x,y)表示“存在y，對(duì)任意的x，都有x+y=5”是個(gè)完全不同的命題，真值為假使一個(gè)命題函數(shù)成為命題，有兩種方法：對(duì)客體變?cè)M(jìn)行指派。

如：P(x):x是素?cái)?shù)，則P(5)為T，P(4)為F對(duì)命題函數(shù)進(jìn)行量化

如：P(x):x是素?cái)?shù)，則(x)P(x)為T，(x)P(x)為F

說明23改名范圍是量詞中的指導(dǎo)變?cè)约霸摿吭~轄域中所出現(xiàn)的該變?cè)?，其余部分不變；所選擇的變?cè)?hào)不能夠和轄域中變?cè)嗤?。?：對(duì)上頁例中需換名的公式換名

1)(x)P(x)Q(x)(y)P(y)Q(x) 2)(x)(P(x,y)Q(x))R(x,y) (z)(P(z,y)Q(z))R(x,y) 3)(x)((PQ(x,y))(x)R(x)) (x)((PQ(x,y))(z)R(z))

同樣，對(duì)公式中的自由變?cè)部梢愿?，稱作代入。2.約束變?cè)膿Q名規(guī)則24在同一個(gè)自由變?cè)霈F(xiàn)之處都要代入;采用的變?cè)?hào)與公式中所有變?cè)拿Q不能夠相同。例3：對(duì)上頁例中需代入的公式進(jìn)行代入

1)(x)P(x)Q(x) (x)P(x)Q(y) 2)(x)(P(x,y)Q(x))R(x,y) (x)(P(x,y)Q(x))R(z,y) 3)(x)((PQ(x,y))(x)R(x))

不需代入，只能使用換名規(guī)則3.自由變?cè)拇胍?guī)則25(x)(A(x)B)

(x)A(x)B

(x)(A(x)B)

(x)A(x)B

(x)(A(x)B)

(x)A(x)B

(x)(A(x)B)

(x)A(x)B

這里僅在有限個(gè)體域上給出證明證：設(shè)E={a1,a2,…,an}(x)(A(x)B)(A(a1)B)(A(a2)B)…(A(an)B) (A(a1)A(a2)…A(an))B (x)A(x)B(x)(A(x)B)(A(a1)B)(A(a2)B)…(A(an)B) (A(a1)A(a2)…A(an))(BB…B) (x)A(x)B3.量詞轄域的擴(kuò)張與收縮26(x)A(x)B

(x)(A(x)B)

(x)A(x)B

(x)(A(x)B)

B(x)A(x)

(x)(BA(x))

B(x)A(x)

(x)(BA(x))證：(x)A(x)B?(x)A(x)B

(x)?A(x)B(x)(?A(x)B) (x)(A(x)B) B(x)A(x)?B(x)A(x)

(x)(?BA(x))

(x)(BA(x))當(dāng)謂詞的變?cè)c量詞的指導(dǎo)變?cè)煌瑫r(shí)，亦能有類似于上述的公式，例如：

(x)(P(x)Q(y))

(x)P(x)Q(y)

(x)(y)(P(x,y)Q(z))

(x)(y)P(x,y)Q(z)27(1)在有限個(gè)體域上證明：證：設(shè)E={a1,a2,…,an}(x)(A(x)B(x))(A(a1)B(a1))(A(a2)B(a2))… (A(an)B(an))(A(a1)A(a2)…A(an))(B(a1)B(a2)…B(an))(x)A(x)(x)B(x)(2)利用(1)的結(jié)論(x)(A(x)B(x))?(?(x)(A(x)B(x))) ?((x)?(A(x)B(x))) ?((x)

(?

A(x)?B(x))) ?((x)?

A(x)

(x)?B(x)) (x)?

?

A(x)(x)?

?B(x)28那么以下說法是否等價(jià)： ”該班全體同學(xué)學(xué)習(xí)好或人品好”

“該班全體同學(xué)學(xué)習(xí)好或全體同學(xué)人品好”？ “該班部分同學(xué)學(xué)習(xí)好且人品好”

”該班部分同學(xué)學(xué)習(xí)好且部分同學(xué)人品好”？即：(x)A(x)(x)B(x)

(x)(A(x)B(x)) (x)(A(x)B(x))

(x)A(x)(x)B(x)

(x)(A(x)B(x))?

(x)A(x)(x)B(x)

(x)(A(x)B(x))?

(x)A(x)(x)B(x)(x)(A(x)B(x))(x)A(x)(x)

B(x)(x)(A(x)B(x))(x)A(x)(x)

B(x)(x)A(x)(x)B(x)

(x)(A(x)B(x))29例：證明(x)A(x)(x)B(x)

(x)(A(x)B(x))

(x)(A(x)B(x))

(x)A(x)(x)B(x)證明：(1)(x)A(x)(x)B(x))

(x)(A(x)B(x))

設(shè)前件(x)A(x)(x)B(x))

為T， 則

(x)A(x)為T或者(x)B(x)為T， 若(x)A(x)為T， 則對(duì)aE，有A(a)為T，于是A(a)B(a)為T，

因?yàn)閍的任意性，就有(x)(A(x)B(x))為T

同理由(x)B(x)為T也可證出(x)(A(x)B(x))為T(2)(x)(A(x)B(x))

(x)A(x)(x)B(x)

由公式1：(x)A(x)(x)B(x))

(x)(A(x)B(x))可得

(x)?A(x)(x)?B(x))

(x)(?A(x)?B(x)) ?(x)A(x)?(x)B(x))

(x)?(A(x)B(x))

?((x)A(x)(x)B(x)))

?(x)(A(x)B(x))

即：(x)(A(x)B(x))

(x)A(x)(x)B(x)30命題演算的推理規(guī)則，如P,T,CP規(guī)則亦可在謂詞演算的推理理論中使用。謂詞邏輯中特有的等價(jià)式見書。謂詞邏輯中特有的蘊(yùn)含式：(x)A(x)(x)B(x)

(x)(A(x)B(x))(x)(A(x)B(x))

(x)A(x)(x)B(x)(x)(A(x)B(x))(x)A(x)(x)

B(x)(x)(A(x)B(x))(x)A(x)(x)

B(x)(x)A(x)(x)B(x)

(x)(A(x)B(x))同時(shí)還需要增加關(guān)于量詞的推理規(guī)則。31(x)P(x)P(c)條件：x是P(x)中自由出現(xiàn)的客體變?cè)?/p>

c為論域中任意的客體常元例1：推證蘇格拉底三段論設(shè)M(x):x是人D(x):x總是要死的s:蘇格拉底 該題就是要證明：(x)(M(x)D(x))，M(s)D(s)

證：(1)(x)(M(x)D(x))P (2)M(s)D(s)US(1) (3)M(s)P (4)D(s)T(2)(3)I1.US規(guī)則（全稱指定/全稱量詞消去規(guī)則）32

P(y)(x)P(x)條件：y在P(y)中自由出現(xiàn)

必須滿足前提P(y)對(duì)論域中每一個(gè)c都有P(y)為真

例：令論域?yàn)閷?shí)數(shù)集，F(xiàn)(x,y)：x>y，考察下列推導(dǎo)：

(1)(x)F(x,y) P (2)(x)(x)F(x,x) UG(1)

顯然得到的結(jié)論不是有效結(jié)論。2.UG規(guī)則（全稱推廣規(guī)則）33

(x)A(x)A(c)

條件：c為論域中使A(x)為真的特定客體常元

c在A(x)中沒有出現(xiàn)過

A(c)(x)A(x)條件：c為論域中使A(x)為真的特定客體常元

取代c的x不能在A(c)中出現(xiàn)過 3.ES規(guī)則（存在指定規(guī)則）4.US規(guī)則（存在推廣規(guī)則）34可以使用命題邏輯中的P,T規(guī)則；若結(jié)論是以條件式形式給出，可用CP規(guī)則；可以使用演繹法和間接證法；推導(dǎo)過程中，對(duì)消去量詞的公式或公式中沒含量詞的子公式，完全可以使用命題邏輯中的基本等價(jià)式和蘊(yùn)含式；5.謂詞邏輯中的綜合推理方法35在推導(dǎo)過程中，如果既要使用US規(guī)則，又要使用ES規(guī)則，通常先使用ES，再使用US；例4：(x)(P(x)Q(x))

(x)P(x)

(x)Q(x)證：采用間接證明方法

(1)((x)P(x)

(x)Q(x))P(附加) (2)(x)P(x)(x)Q(x)T(1)E (3)(x)P(x)(x)Q(x)T(2)E (4)(x)P(x)T(3)I (5)(x)Q(x)T(3)I

(6)P(c)ES(4)首先使用ES,再使用US (7)Q(c)US(5) (8)P(c)Q(c)T(6)(7)I (9)(P(c)Q(c))T(8)E (10)(x)(P(x)Q(x))P (11)P(c)Q(c)US(10) (12)(P(c)Q(c))

(P(c)Q(c))矛盾T(9)(11)36如果一個(gè)常元是用US消去量詞而得，則添加量詞時(shí)，既可用EG，又可用UG；

如果一個(gè)常元是用ES消去量詞而得，則添加量詞時(shí)，只可用EG；例5：(x)(C(x)W(x)R(x))，(x)(C(x)Q(x))

(x)(Q(x)R(x))證：(1)(x)(C(x)Q(x))

P (2)C(a)Q(a)ES(1) (3)(x)(C(x)W(x)R(x))P (4)C(a)W(a)R(a)US(E) (5)

C(a)T(2) (6)W(a)R(a)T(4)(5)I (7)R(a)T(6)I (8)Q(a)T(2)I (9)Q(a)R(a)T(2)(8)I (10)(x)(Q(x)R(x))EG(9)37如果有兩個(gè)含有存在量詞的公式，當(dāng)用ES消去量詞時(shí)，不能選用同樣的常元符號(hào)來取代兩個(gè)公式中的變?cè)?；?：判斷下列論證過程是否有效：

證明(x)P(x)(x)Q(x)(x)(P(x)Q(x)) (1)(x)P(x)(x)Q(x)P

(2)(x)P(x)T(1)I

(3)(x)Q(x)T(1)I

(4)P(c)ES(2)

(5)Q(c) ES(3)

(6)P(c)Q(c)T(4)(5)I

(7)(x)(P(x)Q(x))EG(6)Q(d)38謂詞邏輯中命題的符號(hào)化同一個(gè)命題在不同的個(gè)體域內(nèi)符號(hào)化形式可能不同；未指定個(gè)體域時(shí)，采用全總個(gè)體域。

此時(shí)需引入特性謂詞：

(x)：特性謂詞作為條件式前件引入；

(x)：特性謂詞作為合取項(xiàng)引入。掌握并會(huì)判定公式的類型：永真、永假、可滿足式約束變?cè)c自由變?cè)膿Q名規(guī)則和代入規(guī)則量化命題函數(shù)與命題關(guān)系掌握并記住主要的基本等價(jià)式與蘊(yùn)涵式掌握謂詞邏輯的推理理論

小 結(jié)39第五章代數(shù)結(jié)構(gòu)代數(shù)系統(tǒng)的基本概念1半群與含幺半群（獨(dú)異點(diǎn)）2群（阿貝爾群與循環(huán)群）3子群與陪集4同態(tài)與同構(gòu)5環(huán)與域640

注意若a是b的逆元，則b也是a的逆元，即a與b互為逆元；若b是a的左逆元，則a是b的右逆元；一個(gè)元素左逆元不一定等于它的右逆元；一個(gè)元素可以只有一個(gè)左(右)逆元，沒有右(左)逆元；或者有多個(gè)左逆元，多個(gè)右逆元；或者既沒有左逆元，也沒有右逆元。41<A,*>是代數(shù)系統(tǒng)，*是A上的二元運(yùn)算，那么該運(yùn)算的有些性質(zhì)可以從運(yùn)算表中直接看出。方法如下：1)*有封閉性，當(dāng)且僅當(dāng)運(yùn)算表中的每個(gè)元素都屬于A；2)*有可交換性，當(dāng)且僅當(dāng)運(yùn)算表關(guān)于主對(duì)角線對(duì)稱；3)*有等冪性，當(dāng)且僅當(dāng)運(yùn)算表上的每個(gè)對(duì)角線元素與它所在行（列）的表頭元素相同；4)A中關(guān)于*有零元，當(dāng)且僅當(dāng)該元素所對(duì)應(yīng)的行和列中的元素都與該元素相同；5)A中關(guān)于*有幺元，當(dāng)且僅當(dāng)該元素所對(duì)應(yīng)的行和列依次與運(yùn)算表的行和列一致；6)設(shè)A中有幺元，a和b互逆，當(dāng)且僅當(dāng)位于a所在行，b所在列的對(duì)應(yīng)元素以及b所在行，a所在列的對(duì)應(yīng)元素都是幺元。42例5：設(shè)代數(shù)系統(tǒng)的運(yùn)算表如下，討論其性質(zhì)解：(1)封閉、可交換、等冪、幺元是b、無零元

b-1=ba-1=cc-1=a (2)封閉、不可交換、無等冪性、幺元是a、 無零元，d是左零元、

a-1=ab-1=bc-1=bb-1=c c是d的左逆元，d是c的右逆元，d無逆元*abcaaabbabccbcc*abcdaabcdbbaacccabaddddd(1)(2)43定義1：<S,*>是一個(gè)代數(shù)系統(tǒng)，S為非空集合，*是定義在S上的二元運(yùn)算：*是封閉的代數(shù)系統(tǒng)稱為廣群；*可結(jié)合的廣群稱為半群；含有幺元的半群，稱為獨(dú)異點(diǎn)（含幺半群）；*可交換的（含幺）半群，稱為交換（含幺）半群。例：

<R,->是代數(shù)系統(tǒng)，但不是半群 因?yàn)?在R上封閉，但不可結(jié)合；

<R,?>是半群，而且含有幺元1

所以也是獨(dú)異點(diǎn)，是可交換的獨(dú)異點(diǎn)。44定義1：每個(gè)元素都有逆元的獨(dú)異點(diǎn)，稱為群。定義2：若群還滿足交換律，則稱為交換群（阿貝爾群）。定義3：<G,*>是群，若G是有限集，稱<G,*>是有限群；

G中元素的個(gè)數(shù)稱為該有限群的階數(shù)，記為|G|；

若G無限，則<G,*>稱為無限群。定義4：代數(shù)系統(tǒng)<G，*>中，若存在aG，有a*a=a，則稱a為等冪元。定義5：<G,*>是群，a是G中任意元素，nN，定義元素a的冪為：

a0=e，a1=a，……，

an+1=an*a，

a-n=(a-1)n(其中a-1是a的逆元)

顯然，am*ak=am+k，(am)k=amk（m,kI）1.群的概念45定義6：<G,*>是群，a是G中任意元素，若存在nZ+，使

an=e，則稱元素a的階是有限的，最小的正整數(shù)n稱為元素a的階；若不存在這樣的正整數(shù)n，則稱元素a具有無限階。解：e1=e，∴e的階是1 a2=a*a=b，

a3=a2*a=b*a=e ∴a的階是3

同理，b的階也是3 a3k=e*eabeabeababbeea例：46例1：判斷<I,?>，<R,+>，<P(S),∪>，<P(S),∩>，<P(S),>是否是群？解：<I,?>，幺元是1，只有幺元有逆元，其它元素沒逆元，

∴不是群；<R,+>，幺元是0，x+(-x)=0，每個(gè)元素都有逆元，

∴是群<P(S),∪>和<P(S),∩>不是群，因?yàn)闊o逆元；<P(S),>是群， ∵?A=A=A?∴?是幺元 AP(S)，有AA=?∴A-1=A， 每個(gè)元素都有逆元47例2：集合Zm是模m的同余類組成的同余類集，即

Zm={[0],[1],[2],…,[m-1]}，[i]Zm，[j]Zm，定義運(yùn)算： [i]+m[j]=[(i+j)modm]，

[i]×m[j]=[(i×j)modm]，

判斷當(dāng)m=4時(shí)代數(shù)系統(tǒng)<Zm,+m>,<Zm,×m>是否為群？證明：m=4時(shí)，運(yùn)算表：

封閉、可結(jié)合、 有幺元[0]、 每個(gè)元素都有逆元

[0]-1=[0]

x≠0時(shí)，[x]-1=[4-x]∴<Z4,+4>是群，階數(shù)是4+4[0][1][2][3][0][0][1][2][3][1][1][2][3][0][2][2][3][0][1][3][3][0][1][2]48小結(jié)：

{群}{獨(dú)異點(diǎn)}{半群}{廣群}{代數(shù)系統(tǒng)}

半群在廣群基礎(chǔ)上還要求運(yùn)算可結(jié)合； 獨(dú)異點(diǎn)在半群基礎(chǔ)上要求存在幺元； 群在獨(dú)異點(diǎn)基礎(chǔ)上要求每個(gè)元素都有逆元?！?[0][1][2][3][0][0][0][0][0][1][0][1][2][3][2][0][2][0][2][3][0][3][2][1]

封閉、可結(jié)合、 有幺元[1]、 但元素[0]、[2]沒有逆元 ∴<Z4,×4>不是群492.群的性質(zhì)1)群中無零元。證明：設(shè)<G,*>是群， 若|G|=1，則G的唯一元素是幺元，∴無零元； 若|G|>1，設(shè)<G,*>有幺元e、零元，則≠e xG，x*=*x=≠e∴無逆元 這與<G,*>是群相矛盾，

∴<G,*>中無零元502)<G,*>是群，a,bG，必存在唯一的xG，使得a*x=b證明：

aG，設(shè)a的逆元為a-1 ∵<G,*>是群，∴*在G上是封閉的，∴

a-1*bG

令x=a-1*b，則a*(a-1*b)=(a*a-1)*b=e*b=b

∴

存在x，使得a*x=b

設(shè)另有x1G，使得a*x1=b，則有

x=a-1*b=a-1*(a*x1)=(a-1*a)*x1=

e*x1=x1

∴x=x1

∴

使a*x=b成立的x是唯一的。說明：證明存在性時(shí)，只要找出一個(gè)滿足條件的即可；證明唯一性時(shí)，通常設(shè)另一個(gè)滿足條件的，再證兩個(gè)相等513)<G,*>是群，a,b,cG，若a*b=a*c或b*a=c*a，則b=c（消去律）證明略（兩邊同時(shí)與a-1進(jìn)行*運(yùn)算即可）4)在群<G,*>中，只有幺元e是等冪元證明：∵e*e=e，∴

e是等冪元 設(shè)有另一個(gè)等冪元a，則a*a=a ∵e*a=a=a*a，由消去律，得a=e5)在有限群<G,*>中，每個(gè)元素都具有有限階，且階數(shù)至多是|G|。（利用鴿巢原理證明）52定理2：<G,*>是群，SG且S≠?，若對(duì)a,bS，

有a*b-1S

，則<S,*>是<G,*>的子群。證明：(根據(jù)定義證明)(1)設(shè)e是<G,*>的幺元，對(duì)aS，由已知得：

a*a-1

S，即eS

， ∵aS，SG ∴aG，∴a*e=e*a=a，∴e是<S,*>的幺元；(2)對(duì)aS，∵eS，∴由已知得e*a-1S，即a-1S， ∴S中的任意元素都有逆元；(3)對(duì)a,bS，由(2)知b-1S，由已知得a*(b-1)-1S

即a*bS，∴*在S上封閉；(4)*在s上的結(jié)合性是保持的；∴<S,*>是群，又∵SG且S≠?，∴<S,*>是<G,*>的子群。53定理3：循環(huán)群的子群必為循環(huán)群證明：設(shè)<G,*>為循環(huán)群，<H,*>是其子群，則設(shè)H中g(shù)k的最小正整數(shù)k為m。 對(duì)于H中任意元素gk，令k=qm+r，0r<m，

∴r=k-qm

由封閉性，就有g(shù)r=gk-qm

=gk*(gm)-q

H， 因?yàn)閞<m，而gm是滿足giH的最小正整數(shù)，

從而r=0， 即gr=e，是幺元 所以gk=(gm)q

， 即<H,*>是循環(huán)群。543.拉格朗日定理<H,*>是<G,*>的子群，則

(1)R={<a,b>|aG,bG，且a-1*bH}是G上的一個(gè)等價(jià)關(guān)系，對(duì)于aG，記[a]R={x|xG且<a,x>R}，則[a]R=aH。

(2)若G是有限群，|G|=n，|H|=m，則m/n

即：H的階整除G的階55推論1：素?cái)?shù)階的群只有平凡子群

因?yàn)槿粲蟹瞧椒沧尤?，則該子群的階必定是原群的一個(gè)因子，這與原群的階是質(zhì)數(shù)矛盾。推論2：<G,*>是n階有限群，對(duì)于aG，a的階必是n的因子，且必有an=e（e是<G,*>的幺元）；若n是質(zhì)數(shù)，則<G,*>必是循環(huán)群。證明：(1)設(shè)<H,*>是由a生成的m階循環(huán)子群，則am=e， 再由“拉格朗日定理”m整除n，∴

an=(am)k=ek=e；(2)若n是質(zhì)數(shù)，aG，且a≠e，則a的階必是n，an=e

由上面的證明，知H={a,a2,…,an=e}是G的循環(huán)子群 ∵HG且|H|=n，∴G=H ∴<G,*>必是循環(huán)群思考：質(zhì)數(shù)階群必是交換群，正確嗎？56定理2：f是<A,°>到<B,*>的一個(gè)同態(tài)映射，若<A,°>是半群（獨(dú)異點(diǎn)、群），則在f作用下，同態(tài)象<f(A),*>也是半群（獨(dú)異點(diǎn)、群）。證明：(1)若<A,>是半群，則<f(A),*>也是半群

對(duì)y1,y2f(A)，存在x1,x2A， 使y1=f(x1)、y2=f(x2) y1*y2=f(x1)*f(x2)=f(x1x2) ∵<A,>是半群，∴x1x2A，

∴f(x1x2)f(A)，y1*y2f(A) ∴*在f(A)上封閉；571.環(huán)定義1：設(shè)<R,+,?

>是含兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng)，若：

(1)<R,+>是交換群；

(2)<R,?>是半群；

(3)運(yùn)算?對(duì)+是可分配的；

則稱<R,+,?>是環(huán)。 通常把第一個(gè)運(yùn)算+稱為“加法”；

第二個(gè)運(yùn)算?稱為“乘法”。58例1：以下代數(shù)系統(tǒng)都是環(huán)：<I,+,?>，其中I:整數(shù)集，+、?是加法和乘法<Q,+,?>，其中Q:有理數(shù)集，+、?是加法和乘法<R,+,?>，其中R:實(shí)數(shù)集，+、?是加法和乘法<C,+,?>，其中C:復(fù)數(shù)集，+、?是加法和乘法<R(x),+,?>，其中R(x):系數(shù)是實(shí)數(shù)的多項(xiàng)式集合，

+、?是多項(xiàng)式加法和乘法<Mn,+,?>，其中Mn是I上n×n方陣，

+、?是矩陣加法和矩陣乘法593.特殊環(huán)定義2：<R,+,?>是環(huán)：

(1)若<R,?>是交換半群，則稱<R,+,?

>是交換環(huán)；

(2)若<R,?>是含幺半群，則<R,+,?

>是含幺環(huán)；

(3)若R中存在兩個(gè)非零元素a和b，使a?b=0，則稱a

和b為零因子，而稱<R,+,?

>是含零因子環(huán)；

否則稱<R,+,?

>是無零因子環(huán)。 例如：對(duì)于集合S，<P(S),,>稱作S的子集環(huán)

<P(S),>含幺元，可交換 又如：<I,+,?>是無零因子環(huán)。60例2：代數(shù)系統(tǒng)<Nk,+k,×k>是環(huán)，其中Nk={0,1,…,k-1}，+k和×k是模k加法和乘法運(yùn)算，是否含零因子環(huán)。解：k=5時(shí)，N5={0,1,2,3,4}， a,b≠0，a×5b=(a?b)mod5 ∵a?b≠5m，∴a×5b≠0 ∴<N5,+5,×5>是無零因子環(huán)

k=6時(shí)，N6={0,1,2,3,4,5}， ∵2N6

，3N6

，2×53=(2?3)mod6=0

而2≠0，3≠0∴<N6,+6,×6>是含零因子環(huán)，其中2和3是零因子∴<Nk,+k,×k>要根據(jù)k的具體值來確定是否是含零因子環(huán)61定義3：<R,+,?>是代數(shù)系統(tǒng)，若滿足

(1)<R,+>是阿貝爾群（交換群）

(2)<R,?>是可交換獨(dú)異點(diǎn)，且無零因子

(3)運(yùn)算?對(duì)運(yùn)算+是可分配的

則稱<R,+,?>為整環(huán)。

（即：可交換的含幺元的無零因子環(huán)是整環(huán)）下圖說明了幾種環(huán)之間的繼承關(guān)系：無零因子環(huán)交換環(huán)含幺環(huán)整環(huán)環(huán)62定理1：設(shè)<R,+,?>是環(huán)，則<R,+,?>是無零因子環(huán)的充要條件為其中消去律成立。證明：(1)若無零因子則有消去律 若無零因子并設(shè)c≠0且c

?a=c

?b，則有

c

?a-c

?b=0 ∴c

?

(a-b)=0 ∴a-b=0∴a=b

同理右消去律成立；(2)若消去律成立，則無零因子（反證法） 假設(shè)存在零因子a、b

有a?b=0=a?0，由消去律得b=0， 這與零因子的定義矛盾，∴假設(shè)錯(cuò) ∴若消去律成立，則無零因子634.域定義5：<R,+,?>是代數(shù)系統(tǒng)，若滿足：

(1)<R,+>是阿貝爾群（交換群）

(2)<R-{0},?>是阿貝爾群

(3)運(yùn)算?對(duì)運(yùn)算+是可分配的

則稱<R,+,?>為域。即：<R,+,?>是環(huán)，|R|>1，含幺元，可交換，每個(gè)非零元素有乘法逆元。例：<Q,+,?>是域，<R,+,?>是域；

<I,+,?>不是域， ∵<I-{0},?>不是群，

例如2I-{0}，但<I-{0},?>中2沒有逆元，1/2I-{0}64定理2：域一定是整環(huán)。證明：設(shè)<A,+,?>是域，則<A-{0},?>是阿貝爾群，∴<A,?>中?可交換且含幺元，∴<A,?>是可交換獨(dú)異點(diǎn)，∴只需證<A,?>滿足無零因子條件， 即只需證<A,?>滿足消去律。設(shè)e是乘法幺元，對(duì)于a,b,cA，且a≠0，若有a?b=a?c，則b=e?b=a-1?a?b=a-1?(a?c)=e?c=c∴<A,?>滿足乘法消去律∴<A,+,?>是整環(huán)。65定理3：有限整環(huán)必是域。證明：設(shè)<A,+,?>是有限整環(huán)，則<A,+,?>對(duì)于域的其它條件都滿足，只需證<A-{0},?>中每個(gè)元素都有逆元。對(duì)于a,b,cA，且c≠0，且ab時(shí)，a?cb?c