離散數(shù)學(xué)復(fù)習(xí) 1

1、復(fù)習(xí),廖波,一、命題 可以確定其值的陳述語句。非陳述、悖論不可二、聯(lián)結(jié)詞：能給出真值表 否定?、合取?、析取?、條件?、雙條件? ? ?的等價(jià)式、異或、不可兼或、可兼或三、合式公式的定義(1)命題變元、常量是合法 (2)若A是合式公式，則? A合式(3)若A、B合則A?B、A?B、A?B、A?B合式(4)有限次使用(2)~(3)得到的式子都是合法的。學(xué)會判斷一個(gè)公式是否合法。,四、真值表 先確定公

2、式中命題變元即自由變元清單 可以分步給出每部分的公式的真值 也可以直接將各部分的值寫在運(yùn)算符的下方 證明兩個(gè)公式等值、求主析取范式、主合取范式、設(shè)計(jì)電路、重言式或永真式、矛盾式或永假式、可滿足式五、習(xí)題一 命題符號化第6題、14題、16、17、18、19、20、21、22、23、,六、等值式 1、定義：對于命題變元的每組值真值完全相同 2、p?q(1個(gè))、 p?q(3個(gè)) 3、分配律(正用/逆用)、德摩

3、、原=逆否 4、雙否、冪等、交換、結(jié)合、A?0 、A?1、 A?0、A?1、A??A、 A??A 5、局部等值變換后，整體仍等值。例題某次研討會及習(xí)題，寫出表達(dá)式再等值變換七、主析取范式與主合取范式 1、先給出真值表 2、公式=主析取=小項(xiàng)的析取=大項(xiàng)的合取 3、小項(xiàng)對應(yīng)真值表中取值為1之行 mo1=?p?q 大項(xiàng)………………………0之行 M01= p??q 4、先給出真值表再給出公式，設(shè)計(jì)題,八、析取范

4、式與合取范式 1、定義：主范式是每一項(xiàng)中每個(gè)變元均出現(xiàn)，范式則不一定。九、習(xí)題二 1、掌握用真值表證明公式等值 2、學(xué)會用真值表求主析取、主合取范式 3、掌握設(shè)計(jì)題第27題 4、某科研所派人出國、29、30題 變元不多時(shí)，可給出真值表主析取式范式 并且將明顯不成立的取值組去掉 變元多時(shí)先等值變換再求析取范式 也可用歸結(jié)法Robinson方法“對對碰”。,

5、十、推理的定義 1、定義：若A1，A2，……為真時(shí)公式B為真，則稱{A1, A2, …, An}可推出B，記為{A1,A2,,…}?B。 2、證明方法： (1)真值表法：A1?A2?…An?B為永真。 (2)利用范式：將??轉(zhuǎn)換為???，將?進(jìn)行到底，順、逆用分配律，得到公式的范式，判斷是否為永真。 (3)自然推理：從A1,A2,…An 為真出發(fā)，推理判斷B是否為1。 (4)附加條件法： A1?A2?…

6、An ?(C?D)等價(jià)于A1?A2?…An ?C ?D (5)反證法或歸謬法 假設(shè)A1,A2,,…為1時(shí)， B不為1即為0，也即?B為1，則可以推出矛盾的結(jié)論。,3、常用的等值式 p?q?(?p?q) ? ?q ? ?p p?q ? ?p?q 逆用 p?q ? (p?q)?(q?p) ? (?p?q) ? (p? ? q) ?(p?q) ? (?p??q) 主析取范式

7、 ?(p?q) ? ?p??q 順、逆用 ?(p?q) ? ?p??q 順、逆用 p?(q?r) ? (p?q) ?(p ? r) 順、逆用 p?(q?r) ? (p?q)?(p ? r) 順、逆用 p?(p?q) ?p p?(p?q) ?p 吸收律 多吃少 0?B?B，1?B ?1 0?B?0，1?B ?B,4、推理定律 1)A?A?B 因?yàn)锳為1時(shí)， A?B 為1 2)A

8、?B?A 因?yàn)锳?B為1時(shí)，A為1且B為１。 3)(A?B)?A?B 左=1時(shí)右=1，假言推理或分離原則 4)(A?B)?(B?C)?(A?C) 附加條件再(3) 傳遞律 可以不記，但要會推 5)(A?B)?(C?D)?(A?C)?(B?D) ?到?附加再(3) (A?B)?(?A?B)?B 歸謬法或反證法? B為1 6)(A?B)?(C?D)?(?B??D)?(?A??C)附加逆反再 7)(A?B

9、)??B??A 逆否再(3)。 拒取式 8)(A?B)??B?A ?到?轉(zhuǎn)換再(3). 析取三段論,5、Robinson證明法：機(jī)器證明法，歸結(jié)法 若p?q，?p?r為真，則q?r為真。 用反證法證明，即假設(shè)q?r為假。 (1) q?r為0 (假設(shè)) (2) q為0，r為0 (析取的定義) (3) p?q為1 (已知) (4) p?0為1 ((2)代入(3))

10、 (5) p為1 (由(4)及?的定義) (6) ?p?r為1 (已知) (7) ?p?0為1 ((2)代入(6)) (8) ?p為1 (由(7)及?的定義) (9) p? ?p為1 (由(5)與(8)可知),這是矛盾！故“假設(shè)q?r為假”錯(cuò)！，只能為真。證畢,(1)對對碰！(2)P必須變元q,r可為公式(3)前提為析取式的合取(4)可用于反證法與順證法。,十一、習(xí)題

11、三 1、游泳題、看電影給出真值表主析取式范式 2、如果小趙去小李也去等問題：推理方式 3、自然推理：分離原則、逆否、條件式來回用,十二、謂詞的符號即一階邏輯命題的符號化 1、個(gè)體常項(xiàng) 獨(dú)立存在的個(gè)體，如“楊圣洪” 2、個(gè)體變元 表示某個(gè)范圍(個(gè)體域)任意對象。 3、謂詞 大寫字母表示F，G，H 刻畫一個(gè)對象的性質(zhì)或多個(gè)對象之間的關(guān)系。 4、量詞 ? All “所有的”、 “全部”、 “一切”、……

12、 F(x)表示x男人是壞蛋 , ?xF(x) x值域?yàn)槟腥思?L(x,y)表示x人與y人是同事, ?x?yL(x,y) x,y值域?yàn)椤坝?jì)通院的老師集”。 5、量詞 ? Exist “存在有”、 “某些”、 “一部分”、 F(x)表示x男人是壞蛋 , ? xF(x) x值域?yàn)槟腥思?L(x,y)表示x人與y人是同事, ? x ? yL(x,y) x,y值域?yàn)椤昂洗髮W(xué)的職工集”。 6、掌握對簡單語句的符

13、號化,7、合法的謂詞公式非邏輯符號:個(gè)體常元、函數(shù)符號、謂詞符號邏輯符號:個(gè)體變元、量詞符號、聯(lián)結(jié)詞、逗號、括號。項(xiàng)的定義：個(gè)體常元與變元及其函數(shù)式為項(xiàng)。(1)個(gè)體常元和個(gè)體變元是項(xiàng)。(2)若?(x1,x2,…, xn)是n元函數(shù),t1,t2,…tn是n個(gè)項(xiàng)，則?(t1,t2,…, tn)是項(xiàng)。(3)有限次使用(2)得到的表達(dá)式是項(xiàng)。原子公式： 設(shè)R(x1,x2,…,xn)是n元謂詞，t1,t2,…,tn是項(xiàng)，則R(

14、t1,t2,…, tn)是原子公式。,7、合法的謂詞公式項(xiàng)的定義：個(gè)體常元與變元及其函數(shù)式為項(xiàng)。原子公式： 設(shè)R(x1,x2,…,xn)是n元謂詞，t1,t2,…,tn是項(xiàng)，則R(t1,t2,…, tn)是原子公式。合式謂詞公式： (1)原子公式是合式公式； (2)若A是合式公式，則(?A)也是合式公式； (3)若A,B合式，則A?B, A?B, A?B , A?B 合式 (4)若A合式，則?xA、? xA合式 (

15、5)有限次使用(2)~(4)得到的式子是合式。,7、合法的謂詞公式項(xiàng)的定義：個(gè)體常元與變元及其函數(shù)式為項(xiàng)。原子公式： 設(shè)R(x1,x2,…,xn)是n元謂詞，t1,t2,…,tn是項(xiàng)，則R(t1,t2,…, tn)是原子公式。合式謂詞公式： (?A)、A?B, A?B, A?B , A?B 、?xA、?xA量詞指導(dǎo)變元：?xA和?xA中的x量詞轄域：?xA和?xA中的A為量詞?/?轄域變元的約束出現(xiàn)：在?x和?x的轄域A中

16、，x的所有出現(xiàn)都稱為約束出現(xiàn)。變元的自由出現(xiàn)：不是約束出現(xiàn)的變元。,8、合法的謂詞公式的解釋例4.7：?x(F(x)?G(x)) 其中x的取值范圍是什么？ F(x)的含義是什么？G(x)的含義是什么？ 將這些問題確定后，表達(dá)式?x(F(x)?G(x))的真值就確定了，這就是公式的解釋。 dom(x)=D1=全總個(gè)體域 F(x)表示x是人，G(x)表示x是黃種人。 ?x(F(x)?G(x))：所有的人都是黃種

17、人，值為F. dom(x)=D2=實(shí)數(shù)集R F(x)表示x是自然數(shù)，G(x)表示x是整數(shù)。 ?x(F(x)?G(x))：所有的自然數(shù)都是整數(shù)，值為T.,9、謂詞公式的類型永真式(邏輯有效式):在任何解釋下均為真。永假式(矛盾式):在任何解釋下均為假?？蓾M足式:至少存在一種解釋下為真。10、代換實(shí)例： 設(shè)A0是含命題變元p1,p2,...,pn的命題公式，A1,A2,...,An是n個(gè)謂詞公式(其中個(gè)體常元/變元/函

18、數(shù)/謂詞公式都未確定含義)，用Ai處處代替A0中pi的出現(xiàn)，所得公式A稱為A0的代換實(shí)例。 定理：命題重言式的代換實(shí)例都是永真式， 矛盾式的代換實(shí)例都是矛盾式。,十三、習(xí)題四 1、符號化 2、確定謂詞公式的值：常量、取值范圍、謂詞 3、自然推理：分離原則、逆否、條件式來回用十四、一階邏輯等值 1、定義： 二個(gè)謂詞公式等值是指對于謂詞的每種解釋下真值相同。 即A?B在每種解釋下都是永真式！,2、消去量詞等

19、值式 設(shè)個(gè)體域?yàn)橛邢藜疍={a1,a2,...,an},則有 ?xA(x) ?A(a1)?A(a2)?… ?A(an) ?xA(x) ?A(a1)?A(a2) ?… ?A(an)3、量詞否定等值式-對于量詞的德摩律 設(shè)公式A(x)含自由出現(xiàn)的個(gè)體變項(xiàng)x,則 (1) ??xA(x) ??x?A(x) 不是所有的個(gè)體有某性=有些個(gè)體沒有該特性 (2) ??xA(x) ? ? x?A(x)

20、沒有x有某些特性=所有的沒有這個(gè)特性4、無關(guān)項(xiàng)自由進(jìn)去轄域 設(shè)公式A(x)含自由出現(xiàn)的個(gè)體變項(xiàng)x，B不含x ?xA(x)?B? ?x(A(x)?B) ?xA(x)?B? ?x(A(x)?B),5、量詞分配: ? 對?, ?對? 設(shè)公式A(x),B(x)含自由出現(xiàn)的個(gè)體變項(xiàng)x，則： ?x(A(x)?B(x)) ??xA(x)??xB(x) ?x(A(x)?B(x)) ??xA(x)??xB(x) 但是

21、: ? 對?, ?對?不可分配 ?x(A(x)?B(x)) ??xA(x) ??xB(x) (*) 1?0 ?x(A(x)?B(x)) ??xA(x) ??xB(x) (**) 0?16、置換規(guī)則 若A1?B1，則將某公式?(A1,A2,...,An)中的A全部換成B后得到?(B1,A2,...,An)，仍然等值即 ?(A1,A2,...,An)= ?(B1,A2,...,An) 局

22、部等值變換后整體仍然相等。?x(A(x)?B(x))?G(x)?(?xA(x)??xB(x))?G(x),7、換名規(guī)則：指導(dǎo)變元與約束變元同換 將某量詞的指導(dǎo)變元與轄域中同名約束變元，換成不在公式中出現(xiàn)的變元，則與原公式等值。8、代替規(guī)則：某個(gè)公式中自由變元全換掉則仍與公式等值。,十五、一階邏輯的推理理論1、定義 若在各種解釋下A1?A2?A3…?An?B只能為真,則稱為前提A1,A2,…,An可推出結(jié)論B。2、常見的謂詞推理

23、式 (1)命題邏輯的推理式，代換得到的謂詞推理式 如p?q?p, ?xF(x)??yF(y)??xF(x)p?q,p?q, ?xF(x) ? ?yF(y), ?xF(x) ??yF(y)(2)特有的謂詞推理式?xA(x)??xB(x)??x(A(x)?B(x))?x(A(x)?B(x))??xA(x)??xB(x)(3)四條鐵律： 全稱量詞的指定 ?xA(x)?A(x0) x0是任意個(gè)體 全稱量詞的推廣 A(x0)

24、? ?xA(x) x0前面某全稱指定 存在量詞的指定 ?xA(x)?A(c) c為某個(gè)特定的個(gè)體 存在量詞的推廣 A(c) ??xA(x) c為某個(gè)特定的個(gè)體,例題 ?x(F(x)?G(x)),?xF(x)??xG(x)證明:(1)?xF(x)為真 (前提)(2) F(c)為真 (存在指定,至少存在c使F(c)為真)(3) ?x(F(x)?G(x))為真 (前提)(4) F(c)?G(c)為真 (全稱指定,尤其x

25、=c時(shí)為真)(5) G(c)為真 ( (2),(4)分離)(6) ?xG(x)為真 ((5)存在推廣) 通過指定將量詞去掉,通過代換實(shí)例使用命題邏輯的方法. 通過推廣加上量詞,對于存在只有一個(gè)實(shí)例,對推廣全稱,一定要注意x是全稱指定的.,3、一階邏輯前束范式 定義：形如Q1x1Q2x2…QkxkB的公式為前束范式，其中Qi為?或?，B中不含有數(shù)量詞。 如 ?x?y(F(x)?G(y)?H(x,y)) 是前

26、束范式 ?x(F(x)??y(G(y)?H(x,y))不是！因B有量詞 定理1：任何邏輯公式可轉(zhuǎn)換為前束范式。 ?? ?? ?? ?? 命邏代換 約變/自變換名 擴(kuò)張 例：?xF(x)???xG(x) ??xF(x)??x?G(x)? ?x(F(x)??G(x)) 量詞在前,B中無量?xF(x)???xG(x) ? ?xF(x)???yG(y) ??xF(x)??y?G(y)??x?y(F(x)

27、??G(y)),十六、習(xí)題五 1、確定謂詞公式的值：常量、取值范圍、謂詞 2、符號化 3、自然推理： 四鐵律 分離原則、逆否、條件式來回用十七、集合論 1、定義 枚舉法: 教學(xué)樓={復(fù)臨,中樓,東樓,北樓,前進(jìn)樓} 描述法:偶數(shù)集={除以2余為0的所有整數(shù)} 2、子集A?B:A中的每個(gè)元素都是B的元素 冪集P(A)={A的所有子集的集合}=2A. 如A={1,2,3}

28、A000={},A001={3},A010={2},A011={2,3}, A100={1},A101={1,3},A110={1,2},A111={1,2,3} 其有23個(gè) ,即2|A|個(gè),3、有窮集的計(jì)數(shù)1)、|A|=集合A的元素?cái)?shù)2)、例題：會英=13、日=5、德=10、法=9，同時(shí)會英日有2人，會德、法、英中任意二種有4人，會日語的既不懂法也不懂德，只會1種和3種人？,令同時(shí)會三種語言為x人，只會英為y1,只會法

29、為y2,只會德語y3 y1+2+4-x+x+4-x=12 y2+4-x+4-x+x=9 y3+2(4-x)+x=10 y1+y2+y3+3+2+3(4-x)+x=24,4、包含排斥原理4.1 |A1?A2|=|A1|+|A2|-|A1?A2| 因?yàn)楣膊糠炙懔藘纱危±?：A1={藍(lán)球隊(duì)}=10，A2={足球隊(duì)}=13，雙重身球員3人，請問這二個(gè)球隊(duì)總共多少人？解：|A1?A2|=|A1|+|A2|-|A

30、1?A2|=10+13-3=20人4.2 |A1?A2 ? … ? |=?|Ai|-?|Ai?Aj| +?|Ai?Aj?Ak|-?|Ai?Aj?Ak?AL|….+(-1)n-1| A1?A2?… ? An|加奇數(shù)個(gè)集合相交-偶數(shù)集合相交,A1,A2,十八、習(xí)題六 1、60人看雜志、25個(gè)學(xué)生、1~300整數(shù)、120的素?cái)?shù)(不是2、3、5、7、11的倍數(shù)、不是1)、

31、 2、符號化 3、自然推理： 四鐵律 分離原則、逆否、條件式來回用十九、關(guān)系1、有序?qū)?： 有秩序的二個(gè)元素排在一塊稱為有序?qū)?形如 2、笛卡爾積/直積A?B 形如A?B={|a?A，b?B},3、關(guān)系 ： 將笛卡爾積中前后兩個(gè)元素之間存在某種關(guān)系的序偶檢出來,便得到一個(gè)關(guān)系. A?B={1,2,3}?{a,b,c}={,,, ,,,,,} R1={前后兩個(gè)元素的序號一樣} ={,,

32、},三、關(guān)系 A?B={1,2,3}?{a,b,c}={,,, ,,,,,} R1={前后兩個(gè)元素的序號一樣} ={,,}用如下形式的關(guān)系矩陣表示,A={1,2,3}, F?AxA,G?AxA A上的關(guān)系F={,} G={,,},五、關(guān)系的分類 ：圖、關(guān)系矩陣、序偶 自反關(guān)系:若?x?A,都有?R 反自反關(guān)系:若?x?A有?R 對稱關(guān)系:若?R有?R 反對稱關(guān)系:若?R,?R?x=y 若?R

33、且x?y??R則反對稱 定義等價(jià) 如:A={1,2,3} R1={,} 對稱 R2={,,,} 反對稱 R3={,,} 因?R1不對稱,因與成對出現(xiàn),而不是反對稱,五、關(guān)系的性質(zhì)與分類 傳遞關(guān)系:若?R,?R??R 表示從結(jié)點(diǎn)x出發(fā),連續(xù)2跳后達(dá)到結(jié)點(diǎn)的z所成序偶仍在R中。 而連續(xù)2跳所達(dá)關(guān)系即為R?R,仍在R中即要求R?R?R。 如A={1,2,3} R1={,} 可傳遞的，OKR1?R1=R1?

34、R1故為可傳遞！,六、關(guān)系的閉包：加點(diǎn)序偶使之成某種類型1、R自反閉包r(R)的定義： (1)r(R)自反; (2)R?r(R); (3)R?R',R'自反?r(R)?R' 最小性 恰好增加到變成自反為止。 2、R對稱閉包s(R)的定義： (1)s(R)對稱; (2)R?s(R); (3)R?R‘,R’對稱?s(R)?R‘ 最小性3、R傳

35、遞閉包t(R)的定義： (1)t(R)傳遞; (2)R?t(R); (3)R?R',R'傳遞?t(R)?R' 最小性,t(R)=R?R2 ?R3... ?Rn-1.任何兩點(diǎn)最多n-1步達(dá) =M+M2+M3+...+Mn-1.例A={a,b,c,d}, R={,,,, }t(R)=R?R2?R3,R2={,,,,,,}R3={,,,,,,} ?{,,,,

36、}={,,,,,,,,}t(R)={,,,, , , , , , , , , , , , ,,,,,},七、等價(jià)關(guān)系與劃分 自反、對稱、可傳遞的關(guān)系稱為等價(jià)關(guān)系。 例 A={1,2,3,4,5,6,7,8}R={,,,,,,,,,,,,,,,,,,,,,} 等價(jià)類{1,4,7},{2,5,8},{3,6}彼此不相交，并集=A，稱為A的劃分。,,,,,,,,,,,,,,,,,,,,,,七、等價(jià)關(guān)系與劃分R= {1,4,

37、7}x{1,4,7}?{2,5,8}x{2,5,8}? {3,6}x{3,6}得到劃分 {1,4,7}, {2,5,8},{3,6}. 若有A的劃分，倒用以上工作會得到一個(gè)劃分！如A1={1,2,3},A2={4,5,6},A3={7,8}，則： R'=A1?A1?A2?A2 ? A3?A3 ={,,, ,,, , ,, ,,,,,,, ,,,,,} 可驗(yàn)證R'是對稱、自反、可傳遞的等價(jià)關(guān)系。,八

38、、偏序關(guān)系 1)自反、反對稱、可傳遞的關(guān)系。廣義的“小于等于”關(guān)系，記為?。 2)當(dāng)??時(shí)，寫成x?y，主要為了直觀。 3)當(dāng)??但x?y時(shí)，記成x??或??。 5)全序(線序): ?x,y?A ，x與y都可比。如 A={1,2,3,4,5,6} R={:x?y} 狹義? B={1,2},A={?,{1,2}} R={:x?y,x?A,y?A},即x與y是B的子集。全序 B={1,2},A={?,

39、{1},{2},{1,2}} R={:x?y,x?A,y?A},即x與y是B的子集。 偏序,八、偏序關(guān)系 2)當(dāng)??時(shí)，寫成x?y，主要為了直觀。 4)?x,y?A x與y可比是指??或??。 6)偏序集：集合A與定義其上偏序關(guān)系。 7)蓋住:x?A,y?A,x:x?y,x?A,y?A}, {1}蓋住?, {2}蓋住?,但{1,2}并不蓋住?.,八、偏序關(guān)系 7)蓋住:x?A,y?A,x:x?y,x?A,y?

40、A}, {1}蓋住?, {2}蓋住?,但{1,2}并不蓋住?.去掉自反線可傳遞線得到覆蓋關(guān)系哈斯圖,八、偏序關(guān)系 7)蓋住:x?A,y?A,x,剔可傳遞生、自反,八、偏序關(guān)系-最大元/最小元 8)最大元:設(shè)是偏序集，B?A, y0?B, 若?x?B,均有?R，則y0是B的最大元。 y0與B每個(gè)元素x有關(guān)系R即可比，且比其大。,B={a,b,c,d,e,f,g,h} 最大最小無,B={1~8} 有最小,B={1,2,4,8

41、} 有最大與最小,B={b,c,d,e,f} 最大有,八、偏序關(guān)系-極大元/極小元 8)最大元:設(shè)是偏序集，B?A, y0?B, 若?x?B,均有?R，則y0是B的最大元。 y0與B每個(gè)元素x有關(guān)系R即可比，且比其大。 9)極大元: 不存在x,使之與y0可比且?R，,極大元{a,f,h},極小 元{a,b,c,g},極大元{8,6,9,7},極小元{1},二運(yùn)算的定義x?P(A), y?P(A) x+y =x?y,

42、x?y=x?yx?Boolean, y?Boolean x+y =x?y, x?y=x?yx+y =(x(i,j)+y(i,j)), x-y =(x(i,j)-y(i,j)), x?y=(x(i,j) ? y(i,j)), 很幸運(yùn)！這些運(yùn)算都可利用，它們所在領(lǐng)域的運(yùn)算符來定義，還有很多運(yùn)算，只能給出其運(yùn)算的結(jié)果，如x?y=(xy) mod 5 x,y?{0,1,2,3,4},三、運(yùn)算的性質(zhì) 1、交換律 設(shè)?是集合S上

43、的二元運(yùn)算，若?x,y?S都有x?y=y ?x， 則稱?在S上是可交換的， 或者說運(yùn)算?在S上滿足交換律。 若運(yùn)算表是對稱的，則滿足交換律。x?y=(xy) mod 5 x,y?{0,1,2,3,4},三、運(yùn)算的性質(zhì) 2、結(jié)合律 設(shè)?是集合S上的二元運(yùn)算，若?x,y,z?S都有(x?y)?z=x?(y?z)， 則稱?在S上是可結(jié)合的,或者說運(yùn)算?在S上滿足結(jié)合律。 如：x,y,z?P(A) (x+y)+z

44、=(x?y)?z=x?(y?z)=x+(y+z) (x?y)?z=(x?y)?z=x?(y?z)=x?(y?z) 當(dāng)運(yùn)算滿足結(jié)合律時(shí)，常將決定運(yùn)算次序的園括號去掉，如(x+y)+z=x+y+z。 普通的加、乘、集合的并、交、邏輯的與、邏輯或、矩陣的加、乘滿足結(jié)合律。,三、運(yùn)算的性質(zhì) 3、冪等律 設(shè)?是集合S上的二元運(yùn)算，若?x?S都有x?x=x， 則稱?在S上是冪等的,或者說運(yùn)算?在S上滿足冪等律。 如：x?

45、P(A) x+x=(x?x)=x , x?x=(x?x)=x 邏輯的與、邏輯或滿足結(jié)合律。 有些運(yùn)算不滿足冪等律，但是集合S中的某些元素滿足！ 如普通加法不滿足冪等，但0滿足0+0=0, 普通乘法不滿足冪等，但1滿足1?1=1。 普通矩陣的乘法不冪等，但單位矩陣滿足！,三、運(yùn)算的性質(zhì) 4、分配律 設(shè)?與*是集合S上的二種運(yùn)算，若?x,y,z?S都有 x*(y?z)=(x*y)?(x*z

46、)， (y?z)*x=(y*x)?(z*x) 則稱*對?是可分配的。 如： ?x,y,z?P(A), ?對?可分配， x?(y?z)=(x?y)?(x?z) ?對?也可分配， x ?(y?z)=(x?y)?(x ? z) 邏輯的與、邏輯或滿足結(jié)合律。 有些運(yùn)算不滿足冪等律，但是集合S中的某些元素滿足！ 如普通加法不滿足冪等，但0滿足0+0=0, 普通乘法不滿足冪等，但1滿足1?1=1

47、。 普通矩陣的乘法不冪等，但單位矩陣滿足！,三、運(yùn)算的性質(zhì) 5、吸收律 設(shè)?與*是集合S上的二種可交換的二元運(yùn)算，若?x,y?S都有 x*(x?y)=x ， x?(x*y)=x則稱*與?是滿足吸收律。 如： ?x,y,z?P(A), x?(x?y)=x， x ?(x?y)=x 又如： ?x,y,z命題變元 x? (x?y)=x， x ? (x ? y)=x小結(jié)： 交換律、結(jié)合律、冪

48、等律、分配律、吸收律是普通的加與乘、集合的并與交、命題變元的與或等運(yùn)算的規(guī)律的總結(jié)、推廣！,四、集合S中滿足某運(yùn)算的特殊元素 1、單位元 設(shè)?是集合S上的二元運(yùn)算，如果集合S中的某元素eL，對?x?S都有 eL?x=x 則稱之為左單位元。 設(shè)?是集合S上的二元運(yùn)算，如果集合S中的某元素eR，對?x?S都有 x?eR=x 則稱之為右單位元。 如果S中某個(gè)元素既是左單位元，又是右單位元，則為單位元。 如：??A= A

49、??=A 0+x=x+0=x 1*x=x*1=x,四、集合S中滿足某運(yùn)算的特殊元素 1、單位元 對?x?S都有 eL?x=x 則稱之為左單位元。 對?x?S都有 x?eR=x 則稱之為右單位元。 定理:設(shè)?是S上的二元運(yùn)算,若存在左單位元eL與右單位元eR,則eL=eR=e且唯一 證明： ?x?S都有eL?x=x? eL?eR=eR ?x?S都有 x?eR=x ?eL?eR=eL

50、由以上二式可知eR=eL，即兩個(gè)單位元的值相等，不妨將其值記為e ，則e既是左單位元，又是右單位元，故由單位元定義可知,e是單位元。如： ??A= A??=A 0+x=x+0=x 1*x=x*1=x,四、集合S中滿足某運(yùn)算的特殊元素 1、單位元 對?x?S都有 eL?x=x 則稱之為左單位元。 對?x?S都有 x?eR=x 則稱之為右單位元。 2、零元 對?x?S都有 ?L?x= ?L 則稱之為左零元。

51、對?x?S都有 x? ?R = ?R 則稱之為右零元。 定理：設(shè)?是S上的二元運(yùn)算,若存在零元?與單位元e,且集合S中至少有2個(gè)元素，則??e 。 證明：假設(shè)?=e ， 由單位元定義可知，?x?S都有x?e=x， 由假設(shè)可知?=e ， 故x??=x ….. (1) 。 由零元的定義可知，?x?S都有??x=?…..(2) 由(1)(2)可知x=?，又由假設(shè)可知?=e ，故x= ?=e 故S中只有1個(gè)元素！

52、矛盾！假設(shè)錯(cuò)！,四、集合S中滿足某運(yùn)算的特殊元素 3、逆元 并不是所有元素有逆元！ 某x?S若有yL?S,使得yL?x=e，左逆元。 某x?S若有yR?S,使得x?yR=e，右逆元。 則y既是x的左逆元又是右逆元，則為x的逆元。 定理：設(shè)運(yùn)算?滿足結(jié)合律且存在單位元，某元素x，若存在左逆元yL與右逆元yR,則yL=yR并且唯一。 證明：yL=yL?e=yL?(x?yR)=(yL?x)?yR=e?y

53、R=yR。 唯一性：若x有兩個(gè)逆元y1、y2。 y1=y1?e=y1?(x?y2)=(y1?x)?y2=e?y2=y2.,六、代數(shù)系統(tǒng)同構(gòu)與同態(tài) 如果判斷類似呢？同構(gòu)或同態(tài)檢測！ 定義1：設(shè)有兩個(gè)代數(shù)系統(tǒng),，若能在集合A與B之間構(gòu)造映射f，滿足如下要求： (1)?y?B均?x?A，使得y=f(x) (1)滿射(2)1-1 (2)當(dāng)x1,x2?A, x1?x2有f(x1),f(x2)?B, f(x1)?f(

54、x2) (3) ?x1,x2?A有f(x1?x2)=f(x1) *f(x2),一、群的定義(0)設(shè)V=是封閉代數(shù)系統(tǒng)，稱為廣群。(1)設(shè)V=是封閉、可結(jié)合,則為半群。(2)設(shè)V=是封閉、可結(jié)合、有單位元e，則V為幺群，也叫獨(dú)異點(diǎn)。(3)V=是封閉、可結(jié)合、有單位元e、每a?S，有逆元a-1?S則稱為群G。Group例題1： 正整數(shù)集上的加法 x+y+z=(x+y)+z=x+(y+z) 可結(jié)合 x+0=x+0=x

55、 單位元為0 x+(-x)=0 x的逆元為相反數(shù)。 故是群。,二、群的性質(zhì)有限群：指群的元素集G有限，|G|有限。如：,無窮群， 有限群， Klein四元群是有限群平凡群：只有單位元e的代數(shù)系統(tǒng)。如： ,交換群：若群中的運(yùn)算可交換，Abel群。如： ,無窮群， 有限群， Klein四元群是有限群,二、群的性質(zhì)n次冪：,理解:an表示a進(jìn)行n

56、次?運(yùn)算,是群,a?G如：在中13表示1進(jìn)行3次+運(yùn)算=1+1+1=3如: 在中13表示1進(jìn)行3次?運(yùn)算=1?1 ? 1=1如：,其中Z3={[0],[1],[2]}, [0]n=[0]n個(gè)3k型數(shù)加仍是3k型(3k1+3k2...+3kp)%3=0[1]n=n個(gè)3k+1型數(shù)加(3k1+1+3k2+1+...+3kp+1)%3=n%3[2]n=n個(gè)3k+2型數(shù)加(3k1+2+3k2+2...+3kp+2)%3=2n%3[1

57、]+[2]=(3k+1+3m+2)%3=3%3=[0] 互逆([1]-4)=([1]-1)4=[2]4=2n%3=[2],定理1：設(shè)G為群，則G的冪運(yùn)算滿足： ?a?G,(a-1)-1=a 驗(yàn)證a是a-1的逆元,(a-1)-1為a-1的逆元?a,b?G,(ab)-1=b-1a-1 驗(yàn)證b-1a-1是ab的逆元?a?G,(an)am=an+m,n,m?z 由冪的定義?a?G,(an)m=anm,n,m?z an進(jìn)行m次運(yùn)算

58、證明： (1) a-1是a的逆元，而逆元是相互的，故a也是a-1的逆元，同時(shí)a-1的逆元記為(a-1)-1，故a=(a-1)-1。 (2) (ab)-1是ab的逆元， 而ab(b-1a-1)=abb-1a-1=aea-1=aa-1=e， (b-1a-1)ab=b-1a-1ab=b-1eb=b-1b=e 根據(jù)逆元的定義，b-1a-1也是ab的逆元 而逆元唯一，故兩個(gè)逆元相等，即(ab)-1

59、=b-1a-1(3) anam=an-1aam=an-1am+1=an-2aam+1=...a0am+n=am+n(4) (an)m=anananan...an=anm 指數(shù)相加和為(n+…+n)=nm,定理2：設(shè)G為群且|G|>1，則G中沒有零元。證明：假設(shè)有零元?, 由剛才定理可知??e 由零元的定義可知，?x?G有x??=??x=? 所以x??=??x?e， 故零元?不可能有單位元，這

60、與群中每個(gè)元素有逆元矛盾！ 所以“假設(shè)有零元?”是錯(cuò)的，即群中沒有零元。,定理3：設(shè)為群，對于a, b?G， 必存在唯一的 x?G，使得a ? x = b。群中方程有解！ 證明：設(shè) a 的逆元是a?1 ，可驗(yàn)證 x = a?1 ? b是其解！ 則 a ? x = a ? (a?1 ? b) = (a ? a?1) ? b = e ? b

61、 = b 若另有一解 x1，滿足 a ? x1= b 則a?1 ? (a ?x1)= a?1 ? b 即 x1 = a?1 ? b 故x1=x，即解唯一！,定理4：設(shè)G為群，則G的滿足消去律： ?a,b,c?G,若ab=ac，則b=c?a,b,c?G,若ba=ca,則b=c， 證明： (1) b=eb=a-1ab=a-1ac=ec=c (2) b=be=baa-1=caa-1=ce=

62、c定理5：設(shè)為群，a?G,|a|=r，設(shè)k整數(shù)(1) ak=e?r|k ar=e(2) |a-1|=|a|, 證明:(1) e=ak?r|k。用r去除k得余數(shù)i,則0?i<r,即k=mr+i e=ak=amr+i=amr.ai=(ar)mai=emai=ai 由于r是使得at=e的最小整數(shù)，若0<i<r則矛盾，故i=0 故k=mr即r|k r|k?e=ak， r|k?k=m

63、r ?ak=amr=(ar)m=em=e,三、子群：G是群的元素集，??H?G,若代數(shù)系統(tǒng)是群，則稱為的子群，也簡稱H是G的子群，記為H?G. 若H?G則稱H是G的真子群，記為H是的子群！ 是的子群 是的子群 是的子群，n是自然數(shù) 又如： 對于任何群其本身是其子群，因?yàn)镚?G 是的子群。因?yàn)槭侨?{e} ?G 平凡子群!,(1)子群判斷定理一：設(shè)G為群, ??H?G, H是G的子群? (i)?

64、a,b?H,有a?b?H(封閉) (ii) ?a?H,有a-1?H(逆元)(2)子群判斷定理二:G為群, ??H?G, H是G的子群? ?a,b?H,有a?b-1?H(3)子群判斷定理三:G為群, ??H?G,|H|有限,H是子群??a,b?H,有a?b?H(只要封閉即可)證明:左?右顯然!右?左:由Th1只需要證逆元存在即可. ?b?H(i)若b=e?H, 而母群G中e?e=e可知e-1=e,而e?H故e-

65、1?H.(ii)若b?e,由封閉性?b2=b?b?H即b2?H,故b3=b2?b?H?S={b,b2,b3,…,bk,…}?H?|S|?|H|,而|H|有限?S有限,bi肯定與bj相等!否則無窮了!?bi=bj(i>j)?bj?bi-j=bj?e,根據(jù)G中消去律?bi-j=e,而 b?e?i-j>1?bi-j-1b=bbi-j-1=e ?bi-j-1是b的逆元，即b-1=bi-j-1,而bi-j-1?S?H，故b

66、i-j-1?H，即b-1?H,四、Abel群即交換群 定義：設(shè)是群,其運(yùn)算?是可交換的,則稱為交換群.例題:是交換群。解： 封閉性：?x,y?{0,1,2,3},則z=x+4y=(x+y)mod 4肯定在0~3之間，故z?{0,1,2,3}。 可結(jié)合：?x,y,z?{0,1,2,3} ,x+4y+4z=(x+y+z)mod 4，由于(x+y+z) mod 4可結(jié)合，故+4是可結(jié)合的。 單位元：x+4e=e+4x=x,

67、故e=0. 逆元：0+40 =0,1+43=0,2+42=0， 故0-1=0,1-1=3,3-1=1,2-1=2 交換：x+4y=(x+y)mod 4 y+4x=(y+x)mod 4

68、

69、

70、

71、