莊伯金 ,1,復習,莊伯金 ,2,答疑安排,答疑時間：周一上午、周二上午、周四下午、周一-周五中午 答疑地點：教二214 課件下載地址：,莊伯金 ,3,命題邏輯,命題邏輯的基本概念 常見聯(lián)結(jié)詞 命題邏輯等值演算 命題邏輯的推理,莊伯金 ,4,命題的基本概念,命題的定義 能判斷真假的陳述句 命題的兩個關(guān)鍵要素 必須是陳述句 能明確地判斷真假 命題的真值 判斷為正確的命題，其真值為真（1）； 判斷為錯誤的命題，其真值為假（0）。,莊伯金 ,5,復合命題及聯(lián)結(jié),復合命題：由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。 常見聯(lián)結(jié)詞 否定聯(lián)結(jié)詞 合取聯(lián)結(jié)詞 析取聯(lián)結(jié)詞 蘊涵聯(lián)結(jié)詞 等價聯(lián)結(jié)詞,莊伯金 ,6,基本復合命題真值表,莊伯金 ,7,公式的賦值,定義 設(shè)A為一命題公式，p1, p2, , pn, 為所有在A中出現(xiàn)的命題變項。給p1, p2, , pn指定一組真值，稱其為A的一個賦值或解釋。 若指定的一組賦值使A的真值為真，則稱這組值為A的成真賦值。 若指定的一組賦值使A的真值為假，則稱這組值為A的成假賦值。 將一個命題公式在所有賦值下的情況列成表，稱為這個公式的真值表。 n個命題變項共有2n組賦值。,莊伯金 ,8,重言式（永真式）： 所有的賦值都是A的成真賦值。 矛盾式（永假式）： 所有的賦值都是A的成假賦值。 可滿足式： 至少存在一組賦值使A為真。,莊伯金 ,9,基本等值規(guī)律(1),雙重否定律 AA 等冪律 AAA AAA 交換律 ABBA ABBA 結(jié)合律 A(BC)(AB)C A(BC)(AB)C,莊伯金 ,10,基本等值規(guī)律(2),分配律 A(BC)(AB)(AC) A(BC)(AB)(AC) 德.摩根律 (AB)AB (AB)AB 吸收律 A(AB)A A(AB)A,莊伯金 ,11,基本等值規(guī)律(3),零律 A11 A00 同一律 A0A A1A 排中律 AA1 矛盾律 AA0,莊伯金 ,12,基本等值規(guī)律(4),蘊涵等值式 ABAB 等價等值式 AB(AB)(BA) (AB)(BA) 假言易位 ABBA 等價否定等值式 ABAB 歸謬論 (AB)(AB)A,莊伯金 ,13,范式的概念,命題公式的規(guī)范表示方法 析取范式:由有限個簡單合取式構(gòu)成的析取式 合取范式:由有限個簡單析取式構(gòu)成的合取式 文字：命題變項及其否定式統(tǒng)稱文字 簡單析取式 僅有有限個文字構(gòu)成的析取式 簡單合取式 僅有有限個文字構(gòu)成的合取式 定理： 一個簡單析取式是重言式當且僅當它同時含某個命題變項及其否定式 一個簡單合取式是矛盾式當且僅當它同時含某個命題變項及其否定式,莊伯金 ,14,范式存在定理,定理：任一命題公式都存在與之等值的析取范式（合取范式）。 求范式的步驟 利用蘊涵等值式和等價等值式消去聯(lián)結(jié)詞 、。 用雙重否定律消去否定聯(lián)結(jié)詞，利用德.摩根律將否定聯(lián)結(jié)詞內(nèi)移。 利用分配律求析取范式或合取范式。,莊伯金 ,15,極小項與極大項,極小項的定義 在含n個命題變項的簡單合取式中，如果每個變項與其否定式不同時存在，但兩者之一恰出現(xiàn)1次，且第i個命題變項或否定式出現(xiàn)在從左起的第i位上。 每個極小項僅有一個成真賦值 每個極小項的成真賦值均不相同 極大項的定義 在含n個命題變項的簡單析取式中，如果每個變項與其否定式不同時存在，但兩者之一恰出現(xiàn)1次，且第i個命題變項或否定式出現(xiàn)在從左起的第i位上。 每個極大項僅有一個成假賦值 每個極大項的成假賦值均不相同 n個命題變項共可形成2n個極小項和2n個極大項。,莊伯金 ,16,主析取范式與主合取范式,主析取范式的定義 若A的命題公式由若干個極小項進行析取構(gòu)成，則稱該析取范式為A的主析取范式 從主析取范式中很容易得到成真賦值 主合取范式的定義 若A的命題公式由若干個極大項進行合取構(gòu)成，則稱該合取范式為A的主合取范式 從主合取范式中很容易得到成假賦值 定理：任何命題公式都存在與之等值的主析?。ê先。┓妒?，且唯一。,莊伯金 ,17,主析取范式的求解方法(1),用等值演算求得析取范式 依次掃描析取范式中的每個簡單合取式B 若B為極小項，則繼續(xù)掃描下一個 若B不為極小項，將不含的命題變項p及其否定式p用等值變換添入BB(pp) (Bp)(Bp) 消去重復出現(xiàn)的命題變項、極小項和矛盾式。,莊伯金 ,18,主析取范式的求解方法(2),根據(jù)公式構(gòu)造真值表 寫出每個公式成真賦值對應的極小項 將極小項進行析取，即得主析取范式,莊伯金 ,19,主合取范式的求解方法(1),用等值演算求得合取范式 依次掃描合取范式中的每個簡單析取式B 若B為極大項，則繼續(xù)掃描下一個 若B不為極大項，將不含的命題變項p及其否定式p用等值變換添入BB (pp) (Bp)(Bp) 消去重復出現(xiàn)的命題變項、極大項和重言式。,莊伯金 ,20,主合取范式的求解方法(2),根據(jù)公式構(gòu)造真值表 寫出每個公式成假賦值對應的極大項 將極大項進行合取，即得主合取范式,莊伯金 ,21,推理的形式結(jié)構(gòu),設(shè)兩命題公式A、B，若AB為重言式，則稱A蘊涵B，記為AB。 設(shè)A1、A2、.、An、B為命題公式，若A1A2. An B，則稱B為A1、A2、.、An的邏輯結(jié)論或有效結(jié)論，也稱B可由一組前提A1、A2、.、An邏輯推出。記為A1，A2，.，AnB。 正確推理的本質(zhì)是A1A2. AnB為重言式。 當A1A2. An為假時，不論B是真是假， A1A2. AnB均為真。所以B為有效結(jié)論并不意味B為真。,莊伯金 ,22,推理的基本方法,簡單證明法： 證明A1A2. AnB是重言式，即A1A2. AnB1。 真值表法 等值演算法 主析取范式法 例：若a能被4整除，則a能被2整除。因為a能被2整除，所以a能被4整除。,莊伯金 ,23,推理的基本方法(2),直接構(gòu)造證明法 由給定的一組前提出發(fā)，利用推理規(guī)則逐步演算得到結(jié)論。 常用推理規(guī)則 前提引入規(guī)則：在證明過程的任何步驟都可以將前提引入使用 結(jié)論引入規(guī)則：在推理中，若已證出結(jié)論B，則B可以引入到以后的推理中作為前提使用 置換規(guī)則：命題公式中任何子公式都可以用等值公式置換 化簡規(guī)則： AB A， AB B 附加規(guī)則： AAB,莊伯金 ,24,常用推理規(guī)則,假言推理規(guī)則：AB，AB 拒取式規(guī)則：AB，BA 析取三段論：AB，AB 假言三段推理：AB，BCAC 等價三段論：AB，BCAC 構(gòu)造性二難規(guī)則：AB，CD，ACBD 破壞性二難規(guī)則： AB，CD，BDAC 合取引入規(guī)則：A，BAB,莊伯金 ,25,推理的基本方法(3),間接構(gòu)造證明法 附加前提證明法 A1A2. AnBC A1A2. AnB C 歸謬法 A1A2. AnB A1A2. AnB 0,莊伯金 ,26,謂詞邏輯,謂詞邏輯 謂詞公式 謂詞的解釋 謂詞邏輯等值式、范式,多媒體中心 莊伯金 ,27,謂詞邏輯,簡單命題之間的內(nèi)在聯(lián)系需要通過進一步分析原子命題中主、謂等之間的關(guān)系。 個體：可以獨立存在的客觀實體稱為個體。 謂詞：刻畫個體具有的性質(zhì)或個體之間關(guān)系的詞。 量詞：表示個體常項或變項之間數(shù)量關(guān)系的詞。 全稱量詞：一切的、所有的、每一個、任意的、都.。符號化為“”。表示個體域里的所有個體關(guān)系。 存在量詞：存在、有一個、有的、至少有一個.。符號化為“”。表示個體域里有的個體關(guān)系。,多媒體中心 莊伯金 ,28,量詞,量詞需要注意個體域的問題。在不同的個體域內(nèi)，命題的真值可能不同。 例：存在x，使得x+3=2。 個體域為自然數(shù) 個體域為整數(shù) 特性謂詞：將某類個體從個體域中區(qū)分出來的謂詞。 M(x)：x是人； F(x)：x是魚； Z(x)：x是整數(shù)。,多媒體中心 莊伯金 ,29,命題符號化,明確命題個體域，分別找出個體常項、個體變項、量詞和謂詞； 按照命題的意思用邏輯聯(lián)結(jié)詞將其組合； 注意： 引入特性謂詞時，全稱量詞的特性謂詞作為命題的前提引入，而存在量詞的特性謂詞作為命題的合取項引入； 多個量詞同時出現(xiàn)，需要注意量詞的順序不能隨意顛倒。,多媒體中心 莊伯金 ,30,合式公式和變項轄域,定義 (1)原子公式是合式公式； (2)若A是合式公式，則(A)也是合式公式 (3)若A，B是合式公式，則(AB)，(AB)，(AB)，(AB)也是合式公式； (4)若A是合式公式，則xA，xA也是合式公式； (5)只有有限次的應用(1)-(4)得到的符號串才是合式公式。 定義： xF，xF中，x稱為指導變項，F(xiàn)稱為相應量詞的轄域。轄域中x的所有出現(xiàn)稱為約束出現(xiàn)，x稱為約束變項，F(xiàn)中不是約束出現(xiàn)的其他變項稱為自由變項。,多媒體中心 莊伯金 ,31,謂詞公式的解釋,定義：為使公式成為真值確定的命題而指定的有關(guān)規(guī)定，稱為謂詞公式的一個解釋。 解釋I的組成 特定的個體域D D中一部分特定元素 D上每個函數(shù)變項所取得的具體函數(shù) D上每個謂詞變項所取的具體謂詞,多媒體中心 莊伯金 ,32,謂詞公式的分類,謂詞公式的分類： 如果A在任何解釋下都為真，則稱A為永真式（邏輯有效式）。 如果A在任何解釋下都為假，則稱A為永假式（矛盾式）。 若至少存在一組A的解釋使A為真，則稱A為可滿足式。 代換實例：設(shè)A0是含命題變項p1,p2,.,pn的命題公式，A1,A2,.,An是n個謂詞公式。用Ai代換A0中的每一個pi，所得的公式A稱為A0的代換實例。 定理： 命題公式中的重言式的代換實例在謂詞公式中為邏輯有效式； 命題公式中的矛盾式的代換實例是謂詞公式中仍為矛盾式。,多媒體中心 莊伯金 ,33,謂詞邏輯等值式,等值式的定義：設(shè)謂詞邏輯中任意兩個公式A和B，若AB是是邏輯有效式，則稱A與B為等值式。記作AB。 原命題等值式的代換實例都是等值式。 消去量詞等值式：設(shè)個體域Da1,a2,.,an xA(x)A(a1)A(a2).A(an) xA(x)A(a1)A(a2).A(an) 量詞否定等值式 xA(x) xA(x) xA(x) xA(x),多媒體中心 莊伯金 ,34,謂詞邏輯等值式,量詞轄域擴張和伸縮等值式 x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x) x(BA(x)BxA(x),多媒體中心 莊伯金 ,35,謂詞邏輯等值式,量詞分配等值式 x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)xA(x)xB(x) 量詞交換等值式 xyA(x,y) yxA(x,y) xyA(x,y) yxA(x,y),多媒體中心 莊伯金 ,36,前束范式,定義：設(shè)A為謂詞邏輯公式，若A具有形式Q1x1Q2x2.QnxnB，其中Qi 為或 ，B為不含量詞的公式。 存在定理：任何謂詞邏輯公式都存在與之等值的前束范式。,莊伯金 ,37,集合,集合的基本概念 集合之間的關(guān)系 集合的基本運算 集合中元素的計數(shù),莊伯金 ,38,集合的基本概念,集合的描述：一些可確定的可分辨事物構(gòu)成的整體。 集合常用大寫字母來表示。 元素：屬于集合的特定的事物。常用小寫字母表示。,莊伯金 ,39,集合間的關(guān)系(1),子集：設(shè)A、B為集合，如果B中的每個元素都是A中的元素，則稱B為A的子集。亦稱為B包含于A，或A包含B，記作BA或AB。即有BAx(xB xA) 相等：設(shè)A、B為集合，如果AB且BA，則稱A與B相等，記作AB。即有：ABABBA 真子集：設(shè)A、B為集合，若BA且BA，則稱B為A的真子集，記作BA。即有BAx(xB xA)x(xAxB)。,莊伯金 ,40,集合,定義：不含任何元素的集合叫做空集，記作。 定理：空集是任意集合的子集。 推論：空集是唯一的。 推論：任意非空集合至少有兩個子集。 定義：設(shè)A為集合，把A的全體子集構(gòu)成的集合叫做A的冪集，記作P(A)。 定義：在一個具體問題中，如果所涉及的集合都是某個集合的子集，則稱這個集合為全集，記作E。在文氏圖中，用矩形框表示。,莊伯金 ,41,集合的基本運算,并運算：設(shè)A、B是任意兩個集合，所有屬于A或者屬于B的元素組成的集合，稱為A與B的并集，記作AB。 ABx|xAxB。 交運算：設(shè)A、B是任意兩個集合，由A與B的公共元素組成的集合，稱為A與B的交集，記為AB。 ABx|xAxB。 相對補集：設(shè)A、B是任意兩集合，屬于A而不屬于B的元素組成的集合，稱為B對于A的補集，也叫B對于A的相對補集，記作A-B。 A-B=x|xAxB。,莊伯金 ,42,集合的基本運算,絕對補集：設(shè)A是集合，A對于全集E的相對補集，稱為A的絕對補集，記作A。 A = E-A = x|xExA = x|xA。 對稱差集：設(shè)A、B是任意兩集合，所有屬于A或?qū)儆贐，但又不同時屬于A和B的元素組成的集合稱為A與B的對稱差集合，記作AB。 AB= x|(xAxB)xAB AB=(AB)-(AB)= (A-B)(B-A),莊伯金 ,43,集合的運算律(1),冪等律 AA=A AA=A 交換律 AB=BA AB=BA 結(jié)合律 (AB)C=A(BC) (AB)C=A(BC),莊伯金 ,44,集合的運算律(2),同一律 A=A AE=A 零律 AE=E A= 分配律 A(BC)=(AB)(AC) A(BC)= (AB)(AC),莊伯金 ,45,集合的運算律(3),吸收律 A(AB)=A A(AB)=A 雙重否定律 (B)=B 排中律 A(A)=E 矛盾律 A(A)=,莊伯金 ,46,集合的運算律(3),德.摩根律 (AB)=(A)(B) (AB)=(A)(B) A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C) 差分運算律 A-B=A(B)=A-(AB) (A-B)B= A(B-C)=(AB)-(AC),莊伯金 ,47,集合的運算律(4),對稱差運算律 AB=BA A=A AA= (AB)C=A(BC),莊伯金 ,48,集合中元素的計數(shù),基數(shù)：集合A中元素的個數(shù)，記作|A|或card A。 有窮集：基數(shù)是有限的集合； 無窮集：基數(shù)是無限的集合。 有窮集的基數(shù)可以通過文氏圖進行計算得出。 先將集合中對應的性質(zhì)確定文氏圖中相應集合 將已知集合的基數(shù)填入相應的區(qū)域 逐步求得其他區(qū)域的基數(shù),莊伯金 ,49,容斥原理,定理：設(shè)有窮集合A、B，基數(shù)分別為|A|和|B|，則有|AB|=|A|+|B|-|AB|。 定理：設(shè)A1,A2,.,An為n個有窮集合，其中，集合Ai的基數(shù)為|Ai|，則有：,莊伯金 ,50,容斥原理(2),設(shè)S為有窮集合，P1,P2,.,Pn是n條性質(zhì)，令Ai表示S中具有性質(zhì)Pi的元素構(gòu)成的集合，則S中不具有性質(zhì)P1,P2,.,Pn的元素個數(shù)是：,莊伯金 ,51,關(guān)系,二元關(guān)系的基本概念 關(guān)系的運算 關(guān)系的性質(zhì) 關(guān)系的閉包 等價關(guān)系與偏序關(guān)系 函數(shù)的概念與性質(zhì),莊伯金 ,52,有序?qū)εc笛卡兒積的概念,定義(有序?qū)?：由兩個元素x和y，按一定順序排列成的二元組。稱為有序?qū)蛐蚺?，記作?x為第一元素，y為第二元素； 有順序的要求：當xy時，； =x=uy=v。 定義(笛卡兒積)：設(shè)A,B為集合，用A中的元素為第一元素，B中的元素為第二元素構(gòu)成有序?qū)Φ募?，稱為A和B的笛卡兒積，記作AB。 AB=|xAyB,莊伯金 ,53,二元關(guān)系的概念,定義(二元關(guān)系)：如果一個集合滿足以下條件之一：(1)集合非空，且它的元素都是有序?qū)Γ?2)集合是空集，則稱該集合為一個二元關(guān)系(簡稱關(guān)系)，記作R。 二元關(guān)系是集合 二元關(guān)系是有序?qū)Φ募?若R，可記為xRy。 定義：設(shè)A和B為集合，AB的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系；若AB，則叫做A上的二元關(guān)系。,莊伯金 ,54,二元關(guān)系的域,定義域：R中所有有序?qū)Φ牡谝辉貥?gòu)成的集合稱為R的定義域，記作domR。 值域：R中所有有序?qū)Φ牡诙貥?gòu)成的集合稱為R的值域，記作ranR。 域：R的定義域和值域的并集稱為R的域，記作fldR。 例：R=,莊伯金 ,55,關(guān)系的表示方法,集合表達式 關(guān)系矩陣 關(guān)系圖,莊伯金 ,56,關(guān)系的運算,逆關(guān)系：設(shè)R為二元關(guān)系，R的逆關(guān)系(簡稱R的逆) 記作R-1，其中R-1=|R。 右復合：設(shè)F和G為二元關(guān)系，G對F的右復合記作FG，其中FG=|t(FG)。 左復合：設(shè)F和G為二元關(guān)系，G對F的左復合記作FG，其中FG=|t(GF)。,莊伯金 ,57,關(guān)系的運算,限制：設(shè)R為二元關(guān)系，A為集合，R在A上的限制記作RA，其中RA=|RxA。 RA的值域稱為A在R下的像，記作RA，其中RA=ran(RA)。 冪：設(shè)R為A上的關(guān)系，n為自然數(shù)，則R的n次冪定義為： R0=|xA=IA Rn+1=RnR 基本的集合運算,莊伯金 ,58,關(guān)系的性質(zhì),自反性：若x(xA(x,x)R)，則稱R在A上具有自反性； 反自反性：若x(xA(x,x)R)，則稱R在A上具有反自反性； 對稱性：若xy(x,yA(x,y)R(y,x)R)，則稱R是A上的對稱關(guān)系； 反對稱性：若xy(x,yA(x,y)R(y,x)R x=y)，則稱R是A上的反對稱關(guān)系； 傳遞性：xyz(x,y,zA(x,y)R(y,z)R(x,z)R)，則稱R是A上的傳遞關(guān)系。,莊伯金 ,59,五種性質(zhì)成立的充要條件,定理：設(shè)R為A上的二元關(guān)系，則 R在A上自反當且僅當IAR； R在A上反自反當且僅當RIA=； R在A上對稱當且僅當R=R-1； R在A上反對稱當且僅當RR-1IA； R在A上傳遞當且僅當RRR,莊伯金 ,60,關(guān)系的閉包,定義：設(shè)R是A上的關(guān)系，R的自反（對稱或傳遞）閉包是A上的關(guān)系R，并滿足 R是自反的（對稱的或傳遞的）； RR； 對A上任何一個包含R的自反（對稱或傳遞）關(guān)系R，RR； R的自反閉包記作r(R)，對稱閉包記作s(R)，傳遞閉包記作t(R)。,莊伯金 ,61,閉包的構(gòu)造,定理：設(shè)R為A上的關(guān)系，則有 r(R)=RIA； s(R)=RR-1 t(R)=RR2R3.,莊伯金 ,62,等價關(guān)系與等價類,定義：設(shè)R為非空集合A上的關(guān)系，如果R滿足自反性、對稱性和傳遞性，則稱R為A上的一個等價關(guān)系。若R，則稱x等價于y。 設(shè)R為非空集合A上的等價關(guān)系，xA，令xR=y|yAR，稱xR為x關(guān)于R的等價類，簡稱為x的等價類，簡記為x。 定理：設(shè)R為A上的等價關(guān)系，則 xA，x非空； x,yA，若R，則xy=； x,yA，若R，則x=y； x=A。,莊伯金 ,63,商集與集合的劃分,定義：設(shè)R為非空集合A上的等價關(guān)系，以R的所有等價類為元素的集合稱為A關(guān)于R的商集，記作A/R，即A/R=x|xA。 定義：設(shè)A為非空集合，若A的子集族滿足： ； xy(x,y xyxy=)； =A。 則稱為A的一個劃分，稱中的元素為A的劃分塊。 商集A/R是A的一個劃分。,商集與集合的劃分,定理：對于集合A的任何一個劃分，存在A上的一個等價關(guān)系R，使得該劃分為A關(guān)于R的商集A/R。反之亦然。,莊伯金 ,64,莊伯金 ,65,偏序關(guān)系,定義：設(shè)R為非空集合A上的一個關(guān)系，若R具有自反性、反對稱性和傳遞性，則稱R為A上的偏序關(guān)系，記作。如果，則稱x小于或等于y。 定義：設(shè)R為非空集合A上的偏序關(guān)系，定義 x,yA，xyxyxy； x,yA，x與y可比xyyx。 定義：集合A和A上的偏序關(guān)系一起叫做偏序集，記作(A,)。 定義：設(shè)R為非空集合A上的偏序關(guān)系，如果x,yA，x與y都是可比的，則稱R為A上的全序關(guān)系（或線序關(guān)系）。,莊伯金 ,66,偏序圖的表示,哈斯圖 排序：若xy，將x放在y的下方； 連線：x,yA，如果xy，且不存在z，使得xzy，則將x和y連線。,莊伯金 ,67,偏序集中的特殊元素,定義：設(shè)(A,)為偏序集，BA，yB， 若x(xByx)，則稱y為B的最小元； 若x(xBxy)，則稱y為B的最大元； 若x(xBxyx=y)，則稱y為B的極小元； 若x(xByxx=y)，則稱y為B的極大元。 定義：設(shè)(A,)為偏序集， BA，yA， 若x(xBxy)，則稱y為B的上界； 若x(xByx)，則稱y為B的下界； 令C=y|y為B的上界，則C的最小元為B的上確界； 令D=y|y為B的下界，則D的最大元為B的下確界。,莊伯金 ,68,代數(shù)系統(tǒng),二元運算 代數(shù)常數(shù) 代數(shù)系統(tǒng),莊伯金 ,69,二元運算,定義：設(shè)集合A，函數(shù)F:AAA稱為A上的二元運算，簡稱為二元運算。 A上的任意兩個元素都可以進行二元運算，且結(jié)果唯一； 運算的結(jié)果還在A內(nèi)，即運算在A上封閉。 可以用, *, 等符號表示二元運算，稱為算符。 交換律：設(shè)為集合A上的二元運算，如果對于任意的元素x,yA，都有xy=yx成立，則稱運算在A上可交換。 結(jié)合律：設(shè)為集合A上的二元運算，如果對于任意的元素x,y,zA，都有(xy)z= x(yz)成立，則稱運算在A上可結(jié)合。,莊伯金 ,70,二元運算的性質(zhì),分配律：設(shè)和*為集合A上的兩個二元運算，如果對于任意的x,y,zA，都有x*(yz)=(x*y)(x*z)和(xy)*z=(x*z)(y*z)成立，則稱運算*對可分配。 冪等律：設(shè)為A上的二元運算，如果對于任意的xA，都有xx=x，則稱運算滿足冪等律。 吸收律：設(shè)和*為集合A上兩個可交換的二元運算，如果對于任意的x,yA，都有x(x*y)=x和x*(xy)=x成立，則稱*和滿足吸收律。,莊伯金 ,71,單位元,左單位元：設(shè)為A上的二元運算，元素elA，如果對任意的xA，都有elx=x，則稱el為運算的左單位元或左幺元。 右單位元：設(shè)為A上的二元運算，元素erA，如果對任意的xA，都有xer=x，則稱er為運算的右單位元或右幺元。 單位元：設(shè)為A上的二元運算，元素eA，如果e既為的左單位元又為的右單位元，則稱e為的單位元或幺元。 定理：設(shè)為A上的二元運算，且運算存在左單位元el和右單位元er ，則運算存在單位元e，且e唯一。,莊伯金 ,72,零元,左零元：設(shè)為A上的二元運算，元素lA，如果對任意的xA，都有l(wèi)x=l，則稱l為運算的左零元。 右零元：設(shè)為A上的二元運算，元素rA，如果對任意的xA，都有xr=r，則稱r為運算的右零元。 零元：設(shè)為A上的二元運算，元素A，如果既是左零元，又是右零元，則稱為運算的零元。 定理：設(shè)為A上的二元運算，且運算存在左零元l和右零元r ，則運算存在零元，且唯一。,莊伯金 ,73,逆元,左逆元：設(shè)為A上的二元運算，e為的幺元，對于元素mA，如果存在ylA，滿足ylm=e，則稱yl為m的左逆元。 右逆元：設(shè)為A上的二元運算，e為的幺元，對于元素mA，如果存在yrA，滿足myr =e，則稱yr為m的右逆元。 逆元：設(shè)為A上的二元運算，對于元素mA，如果y既是m的左逆元又是m的右逆元，則稱y是m的逆元。 定理：設(shè)為A上的可結(jié)合二元運算，A中存在幺元e且每個元素都有左逆元，則在A中，每個元素的左逆元也是該元素的右逆元，且每個元素的逆元唯一。,莊伯金 ,74,代數(shù)系統(tǒng)與子代數(shù)系統(tǒng),定義：由非空集合A以及A上的運算*1,*2,.,*n所組成的系統(tǒng)稱為一個代數(shù)系統(tǒng)，記作。 定義：設(shè)有代數(shù)系統(tǒng)，B是A的非空子集。如果A上的每個運算都在B上是封閉的，且A與B含有相同的代數(shù)常數(shù)，則稱代數(shù)系統(tǒng)為代數(shù)系統(tǒng)的子代數(shù)系統(tǒng)，或稱代數(shù)B為代數(shù)A的子代數(shù)。 最大的子代數(shù)：代數(shù)系統(tǒng)本身 最小的子代數(shù)：B為代數(shù)系統(tǒng)中所有代數(shù)常數(shù)構(gòu)成的集合，且滿足A上每個運算在B上封閉。 若BA，則代數(shù)B為代數(shù)A的真子代數(shù)。,莊伯金 ,75,積代數(shù),定義：設(shè)V1=和V2=為兩個代數(shù)系統(tǒng)，其中*和為二元運算，任意的,AB，AB上的二元運算定義為=，代數(shù)系統(tǒng)稱為V1和V2的積代數(shù)或直積，記為V1V2。,莊伯金 ,76,同態(tài)與同構(gòu),定義：設(shè)兩代數(shù)系統(tǒng)V1=和V2=，如果存在映射f:AB，對任意的x,yA，有f(x*y)=f(x)f(y)，則稱f是V1到V2的同態(tài)映射，簡稱同態(tài)，記為。 若f為滿射，則稱f為滿同態(tài)； 若f為單射，則稱f為單一同態(tài)； 若f為雙射，則稱f為同構(gòu)，記作。 同態(tài)的本質(zhì)是映射與運算可交換順序。 定義：設(shè)為代數(shù)系統(tǒng)，f為到的同態(tài)，則稱f為自同態(tài)；f是到的同構(gòu)，則稱f為自同構(gòu)。,莊伯金 ,77,同態(tài)的性質(zhì),定理：設(shè)映射f:AB是代數(shù)系統(tǒng)到的一個同態(tài)，則是的一個子代數(shù)，并稱它為f作用下的同態(tài)象。 定理：給定代數(shù)系統(tǒng)和，其中*和為二元運算。設(shè)f:AB為到的滿同態(tài)，則 如果*是可交換的或可結(jié)合的運算，則也是可交換或可結(jié)合的運算； 如果中具有單位元e，則具有單位元f(e)。 對運算*，如果每一個A中元素x都有逆元x-1，則對運算，每一個B中元素f(x)，都有逆元f(x-1)。,莊伯金 ,78,代數(shù)結(jié)構(gòu),半群的概念與性質(zhì) 群的概念與性質(zhì) 環(huán)和域的概念,莊伯金 ,79,半群的概念,定義：設(shè)代數(shù)系統(tǒng)V=，為A上的二元運算，若滿足結(jié)合律，則稱V為半群。 半群由一個集合與一個二元運算組成； 滿足結(jié)合律； 若半群滿足交換律，則稱為可交換半群。 定義：設(shè)V=為半群，若該半群中的二元運算含有幺元e，則稱V為含幺半群或幺群或獨異點。記作 若含幺半群滿足交換律，則稱為交換幺群。 定義： 為幺群，若存在一個元素gA，使得對任意的aA，都有a=gn成立，則稱為循環(huán)幺群，并且稱g是A的一個生成元。 定理：循環(huán)幺群是可交換幺群。,莊伯金 ,80,群的定義,定義：設(shè)是代數(shù)系統(tǒng)，為二元運算。如果可結(jié)合，存在單位元eG，且對G中任何元素x，都有x-1G，則稱G為群。 若群G是有窮集，則稱G為有限群，否則稱為無限群。群G的基數(shù)稱為群G的階； 只含單位元的群稱為平凡群； 若群G中