離散數(shù)學復習 1

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

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

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

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

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

6、An ?(C?D)等價于A1?A2?…An ?C ?D (5)反證法或歸謬法 假設A1,A2,,…為1時， B不為1即為0，也即?B為1，則可以推出矛盾的結論。,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 因為A為1時， A?B 為1 2)A

8、?B?A 因為A?B為1時，A為1且B為１。 3)(A?B)?A?B 左=1時右=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 ?到?轉換再(3). 析取三段論,5、Robinson證明法：機器證明法，歸結法 若p?q，?p?r為真，則q?r為真。 用反證法證明，即假設q?r為假。 (1) q?r為0 (假設) (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)可知),這是矛盾！故“假設q?r為假”錯！，只能為真。證畢,(1)對對碰！(2)P必須變元q,r可為公式(3)前提為析取式的合取(4)可用于反證法與順證法。,十一、習題

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

12、 F(x)表示x男人是壞蛋 , ?xF(x) x值域為男人集 L(x,y)表示x人與y人是同事, ?x?yL(x,y) x,y值域為“計通院的老師集”。 5、量詞 ? Exist “存在有”、 “某些”、 “一部分”、 F(x)表示x男人是壞蛋 , ? xF(x) x值域為男人集 L(x,y)表示x人與y人是同事, ? x ? yL(x,y) x,y值域為“湖南大學的職工集”。 6、掌握對簡單語句的符

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

14、t1,t2,…, tn)是原子公式。,7、合法的謂詞公式項的定義：個體常元與變元及其函數(shù)式為項。原子公式： 設R(x1,x2,…,xn)是n元謂詞，t1,t2,…,tn是項，則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、合法的謂詞公式項的定義：個體常元與變元及其函數(shù)式為項。原子公式： 設R(x1,x2,…,xn)是n元謂詞，t1,t2,…,tn是項，則R(t1,t2,…, tn)是原子公式。合式謂詞公式： (?A)、A?B, A?B, A?B , A?B 、?xA、?xA量詞指導變元：?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)的含義是什么？ 將這些問題確定后，表達式?x(F(x)?G(x))的真值就確定了，這就是公式的解釋。 dom(x)=D1=全總個體域 F(x)表示x是人，G(x)表示x是黃種人。 ?x(F(x)?G(x))：所有的人都是黃種

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

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

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

20、沒有x有某些特性=所有的沒有這個特性4、無關項自由進去轄域 設公式A(x)含自由出現(xiàn)的個體變項x，B不含x ?xA(x)?B? ?x(A(x)?B) ?xA(x)?B? ?x(A(x)?B),5、量詞分配: ? 對?, ?對? 設公式A(x),B(x)含自由出現(xiàn)的個體變項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ī)則：指導變元與約束變元同換 將某量詞的指導變元與轄域中同名約束變元，換成不在公式中出現(xiàn)的變元，則與原公式等值。8、代替規(guī)則：某個公式中自由變元全換掉則仍與公式等值。,十五、一階邏輯的推理理論1、定義 若在各種解釋下A1?A2?A3…?An?B只能為真,則稱為前提A1,A2,…,An可推出結論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是任意個體 全稱量詞的推廣 A(x0)

24、? ?xA(x) x0前面某全稱指定 存在量詞的指定 ?xA(x)?A(c) c為某個特定的個體 存在量詞的推廣 A(c) ??xA(x) c為某個特定的個體,例題 ?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時為真)(5) G(c)為真 ( (2),(4)分離)(6) ?xG(x)為真 ((5)存在推廣) 通過指定將量詞去掉,通過代換實例使用命題邏輯的方法. 通過推廣加上量詞,對于存在只有一個實例,對推廣全稱,一定要注意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：任何邏輯公式可轉換為前束范式。 ?? ?? ?? ?? 命邏代換 約變/自變換名 擴張 例：?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)),十六、習題五 1、確定謂詞公式的值：常量、取值范圍、謂詞 2、符號化 3、自然推理： 四鐵律 分離原則、逆否、條件式來回用十七、集合論 1、定義 枚舉法: 教學樓={復臨,中樓,東樓,北樓,前進樓} 描述法:偶數(shù)集={除以2余為0的所有整數(shù)} 2、子集A?B:A中的每個元素都是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個 ,即2|A|個,3、有窮集的計數(shù)1)、|A|=集合A的元素數(shù)2)、例題：會英=13、日=5、德=10、法=9，同時會英日有2人，會德、法、英中任意二種有4人，會日語的既不懂法也不懂德，只會1種和3種人？,令同時會三種語言為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| 因為公共部分算了兩次！例1：A1={藍球隊}=10，A2={足球隊}=13，雙重身球員3人，請問這二個球隊總共多少人？解：|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ù)個集合相交-偶數(shù)集合相交,A1,A2,十八、習題六 1、60人看雜志、25個學生、1~300整數(shù)、120的素數(shù)(不是2、3、5、7、11的倍數(shù)、不是1)、

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

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

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

34、R1故為可傳遞！,六、關系的閉包：加點序偶使之成某種類型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.任何兩點最多n-1步達 =M+M2+M3+...+Mn-1.例A={a,b,c,d}, R={,,,, }t(R)=R?R2?R3,R2={,,,,,,}R3={,,,,,,} ?{,,,,

36、}={,,,,,,,,}t(R)={,,,, , , , , , , , , , , , ,,,,,},七、等價關系與劃分 自反、對稱、可傳遞的關系稱為等價關系。 例 A={1,2,3,4,5,6,7,8}R={,,,,,,,,,,,,,,,,,,,,,} 等價類{1,4,7},{2,5,8},{3,6}彼此不相交，并集=A，稱為A的劃分。,,,,,,,,,,,,,,,,,,,,,,七、等價關系與劃分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的劃分，倒用以上工作會得到一個劃分！如A1={1,2,3},A2={4,5,6},A3={7,8}，則： R'=A1?A1?A2?A2 ? A3?A3 ={,,, ,,, , ,, ,,,,,,, ,,,,,} 可驗證R'是對稱、自反、可傳遞的等價關系。,八

38、、偏序關系 1)自反、反對稱、可傳遞的關系。廣義的“小于等于”關系，記為?。 2)當??時，寫成x?y，主要為了直觀。 3)當??但x?y時，記成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的子集。 偏序,八、偏序關系 2)當??時，寫成x?y，主要為了直觀。 4)?x,y?A x與y可比是指??或??。 6)偏序集：集合A與定義其上偏序關系。 7)蓋住:x?A,y?A,x:x?y,x?A,y?A}, {1}蓋住?, {2}蓋住?,但{1,2}并不蓋住?.,八、偏序關系 7)蓋住:x?A,y?A,x:x?y,x?A,y?

40、A}, {1}蓋住?, {2}蓋住?,但{1,2}并不蓋住?.去掉自反線可傳遞線得到覆蓋關系哈斯圖,八、偏序關系 7)蓋住:x?A,y?A,x,剔可傳遞生、自反,八、偏序關系-最大元/最小元 8)最大元:設是偏序集，B?A, y0?B, 若?x?B,均有?R，則y0是B的最大元。 y0與B每個元素x有關系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} 最大有,八、偏序關系-極大元/極小元 8)最大元:設是偏序集，B?A, y0?B, 若?x?B,均有?R，則y0是B的最大元。 y0與B每個元素x有關系R即可比，且比其大。 9)極大元: 不存在x,使之與y0可比且?R，,極大元{a,f,h},極小 元{a,b,c,g},極大元{8,6,9,7},極小元{1},二運算的定義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)), 很幸運！這些運算都可利用，它們所在領域的運算符來定義，還有很多運算，只能給出其運算的結果，如x?y=(xy) mod 5 x,y?{0,1,2,3,4},三、運算的性質 1、交換律 設?是集合S上

43、的二元運算，若?x,y?S都有x?y=y ?x， 則稱?在S上是可交換的， 或者說運算?在S上滿足交換律。 若運算表是對稱的，則滿足交換律。x?y=(xy) mod 5 x,y?{0,1,2,3,4},三、運算的性質 2、結合律 設?是集合S上的二元運算，若?x,y,z?S都有(x?y)?z=x?(y?z)， 則稱?在S上是可結合的,或者說運算?在S上滿足結合律。 如：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) 當運算滿足結合律時，常將決定運算次序的園括號去掉，如(x+y)+z=x+y+z。 普通的加、乘、集合的并、交、邏輯的與、邏輯或、矩陣的加、乘滿足結合律。,三、運算的性質 3、冪等律 設?是集合S上的二元運算，若?x?S都有x?x=x， 則稱?在S上是冪等的,或者說運算?在S上滿足冪等律。 如：x?

45、P(A) x+x=(x?x)=x , x?x=(x?x)=x 邏輯的與、邏輯或滿足結合律。 有些運算不滿足冪等律，但是集合S中的某些元素滿足！ 如普通加法不滿足冪等，但0滿足0+0=0, 普通乘法不滿足冪等，但1滿足1?1=1。 普通矩陣的乘法不冪等，但單位矩陣滿足！,三、運算的性質 4、分配律 設?與*是集合S上的二種運算，若?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) 邏輯的與、邏輯或滿足結合律。 有些運算不滿足冪等律，但是集合S中的某些元素滿足！ 如普通加法不滿足冪等，但0滿足0+0=0, 普通乘法不滿足冪等，但1滿足1?1=1

47、。 普通矩陣的乘法不冪等，但單位矩陣滿足！,三、運算的性質 5、吸收律 設?與*是集合S上的二種可交換的二元運算，若?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小結： 交換律、結合律、冪

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

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

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

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

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

53、R=yR。 唯一性：若x有兩個逆元y1、y2。 y1=y1?e=y1?(x?y2)=(y1?x)?y2=e?y2=y2.,六、代數(shù)系統(tǒng)同構與同態(tài) 如果判斷類似呢？同構或同態(tài)檢測！ 定義1：設有兩個代數(shù)系統(tǒng),，若能在集合A與B之間構造映射f，滿足如下要求： (1)?y?B均?x?A，使得y=f(x) (1)滿射(2)1-1 (2)當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)設V=是封閉代數(shù)系統(tǒng)，稱為廣群。(1)設V=是封閉、可結合,則為半群。(2)設V=是封閉、可結合、有單位元e，則V為幺群，也叫獨異點。(3)V=是封閉、可結合、有單位元e、每a?S，有逆元a-1?S則稱為群G。Group例題1： 正整數(shù)集上的加法 x+y+z=(x+y)+z=x+(y+z) 可結合 x+0=x+0=x

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

56、次?運算,是群,a?G如：在中13表示1進行3次+運算=1+1+1=3如: 在中13表示1進行3次?運算=1?1 ? 1=1如：,其中Z3={[0],[1],[2]}, [0]n=[0]n個3k型數(shù)加仍是3k型(3k1+3k2...+3kp)%3=0[1]n=n個3k+1型數(shù)加(3k1+1+3k2+1+...+3kp+1)%3=n%3[2]n=n個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：設G為群，則G的冪運算滿足： ?a?G,(a-1)-1=a 驗證a是a-1的逆元,(a-1)-1為a-1的逆元?a,b?G,(ab)-1=b-1a-1 驗證b-1a-1是ab的逆元?a?G,(an)am=an+m,n,m?z 由冪的定義?a?G,(an)m=anm,n,m?z an進行m次運算

58、證明： (1) a-1是a的逆元，而逆元是相互的，故a也是a-1的逆元，同時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的逆元 而逆元唯一，故兩個逆元相等，即(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：設G為群且|G|>1，則G中沒有零元。證明：假設有零元?, 由剛才定理可知??e 由零元的定義可知，?x?G有x??=??x=? 所以x??=??x?e， 故零元?不可能有單位元，這

60、與群中每個元素有逆元矛盾！ 所以“假設有零元?”是錯的，即群中沒有零元。,定理3：設為群，對于a, b?G， 必存在唯一的 x?G，使得a ? x = b。群中方程有解！ 證明：設 a 的逆元是a?1 ，可驗證 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：設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：設為群，a?G,|a|=r，設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ù) 又如： 對于任何群其本身是其子群，因為G?G 是的子群。因為是群,{e} ?G 平凡子群!,(1)子群判斷定理一：設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群即交換群 定義：設是群,其運算?是可交換的,則稱為交換群.例題:是交換群。解： 封閉性：?x,y?{0,1,2,3},則z=x+4y=(x+y)mod 4肯定在0~3之間，故z?{0,1,2,3}。 可結合：?x,y,z?{0,1,2,3} ,x+4y+4z=(x+y+z)mod 4，由于(x+y+z) mod 4可結合，故+4是可結合的。 單位元：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、