離散數(shù)學(xué)第七章

第七章其它代數(shù)系統(tǒng)群只包含一個二元運算；環(huán)、域等代數(shù)結(jié)構(gòu)包含兩個二元運算，兩個二元運算之間也會有關(guān)系。1、環(huán)定義7.1：結(jié)合律，無單位元、逆元-b為(R,+)中b的逆元兩個運算分別稱為加法和乘法算24點一個小題目5、5、5、1，通過簡單四那么運算，算出24思考5×5-1=24，多出來一個5，怎么辦？利用分配律5×5-1=5×5-5×1/5=5×(5-1/5)=24例：例：定義7.2：定義7.3：這里是實數(shù)及其加法、乘法(R,?)是可換半群定理7.1：零元沒有逆元對群，單位元的驗證只要對某個元素成立即可定理7.2：群一定滿足消去律，因此這里的消去律是針對(R,?)來說的這里的消去律是排除零元的零因子：環(huán)中，a≠0，b≠0，但a?b=0，那么a為左零因子，b為右零因子定義7.4：定理7.3：(S,+)中a的逆元，(S,?)是半群，無逆元定義7.5：兩個運算都需要考慮類似于正規(guī)子群的條件；為什么是對運算“?〞：運算“+〞是可換的〔環(huán)的定義〕2、理想定義7.6：(I,+,x)的所有理想都是主理想，那么(I,+,x)是主理想環(huán)定義7.4:陪集是定義在群上的，所以考慮的是(D,+)3、整環(huán)定義7.7：都是對(R,?)來說的環(huán)要求(R,+)可換，可換環(huán)還要求(R,?)可換(R,+)是群，因此無零元，因此不會定義零因子定理7.5：定理7.6：即：對于“?〞的消去律，(D,?)是半群，本不應(yīng)該有消去律，這里是因為無零因子4、域定義7.8：這點和整環(huán)不同，整環(huán)要求無零因子環(huán)，即使整環(huán)也不能用非零元素除，而域可以2、3點和整環(huán)相同定理7.7：定理7.8：注意：其逆定理不成立，即整環(huán)不一定是域。定理7.9：即：有逆元多項式環(huán)定義：(R,+,?)的零元定理：2023/12/319.1格的定義與性質(zhì)偏序偏序關(guān)系：集合L上具有自反性、反對稱性和傳遞性的關(guān)系稱為集合L上的，記為≤；偏序集：集合L和偏序關(guān)系≤一起稱為偏序集，用〔L，≤〕來表示；引入L的子集上的最大下界、最小上界等概念。格對于一個偏序集來說，其中的每一對元素不一定都有最大下界或最小上界；格：每一對元素都有最大下界或最小上界的偏序集。2023/12/31定義7.9格是一個偏序集，其中任意兩個元素所構(gòu)成的子集都有下確界與上確界，也可以稱為偏序格。 記x,y的上確界為x∨y=lub(x,y)， 下確界為x∧y=glb(x,y)集合P上的偏序關(guān)系≤所構(gòu)成的偏序集如果是格，可寫為(P,∧,∨)，假設(shè)P中元素有限，稱為有限格。2023/12/31例1.設(shè)n是正整數(shù)，Sn是n的正因數(shù)的集合，≤為整除關(guān)系，那么偏序集〔Sn，≤〕構(gòu)成格。證明：對任意的x、y∈Sn，有x∨y是x與y的最小公倍數(shù)，x∧y是x與y的最大公約數(shù)，且x∨y、x∧y∈Sn，所以〔Sn，≤〕構(gòu)成格。例2.偏序集〔ρ(A)，〕是格。證明：對任意的x、y∈ρ(A)，有：x∨y＝x∪y，x∧y＝x∩y，且x∨y、x∧y∈ρ(A)所以〔ρ(A)，〕是格。2023/12/31例3.偏序集〔Z，≤〕是格。證明：對任意的x、y∈Z，有： x∨y＝max(x，y)，x∧y＝min(x，y)， 且它們都是整數(shù)，所以〔Z，≤〕是格。注意：并不是每個偏序集都是格。 如A＝{2，3，4，6，8，12，36，60}， 對A上的整除關(guān)系∨，因為8∨12和2∨3不存在，所以偏序集〔A，∨〕不是格。2023/12/31

2023/12/31定義7.10：設(shè)(P,∧,∨)和(L,∧,∨)是兩個格，假設(shè)存在函數(shù)f:P→L，使得對任意a,b∈P，有： f(a∧b)=f(a)∧f(b) f(a∨b)=f(a)∨f(b)那么稱f為由格P到L的格同態(tài)；如果f是一一對應(yīng)的，那么稱它是一個格同構(gòu)， 或稱(P,∧,∨)和(L,∧,∨)同構(gòu)。2023/12/31定理7.10：設(shè)(P,∧,∨)是格，對任意a,b,c∈P，有：a≤a∨b，b≤a∨ba≤c且b≤c，那么a∨b≤ca∧b≤a，a∧b≤bc≤a且c≤b，那么c≤a∨b觀察上述不等式可以發(fā)現(xiàn)：不等式都是有規(guī)律地成對出現(xiàn)，這就是對偶原理。2023/12/31對偶式： 格(P,∧,∨)中出現(xiàn)的符號≤、≥、∧、∨分別用≥、≤、∨、∧替換，得到的原式的對偶式。定理7.11〔對偶定理〕 在格(P,∧,∨)中任何一條定理的對偶式仍是定理。2023/12/31定理：設(shè)(P,∧,∨)是格，那么運算∨和∧滿足：交換律：對任意的a、b∈P，有a∨b＝b∨a，a∧b＝b∧a。結(jié)合律：對任意的a、b、c∈P，有(a∨b)∨c＝a∨(b∨c)，(a∧b)∧c＝a∧(b∧c)。冪等律：對任意的a∈P，有a∨a＝a，a∧a＝a。吸收律：對任意的a、b∈P，有a∨(a∧b)＝a，a∧(a∨b)＝a。2023/12/31證明〔1〕：因為a∨b和b∨a分別是{a，b}和{b，a}的最小上界，因為{a，b}＝{b，a}，所以a∨b＝b∨a。由對偶原理，a∧b＝b∧a。2023/12/31證明〔2〕：由上確界的定義有(a∨b)∨c≥a∨b≥a(1)(a∨b)∨c≥a∨b≥b(2)(a∨b)∨c≥c(3)由(2)和(3)有(a∨b)∨c≥b∨c再由(1)得(a∨b)∨c≥a∨(b∨c)同理可證(a∨b)∨c≤a∨(b∨c)根據(jù)偏序關(guān)系的反對稱性有(a∨b)∨c＝a∨(b∨c)。由對偶原理有(a∧b)∧c＝a∧(b∧c)。2023/12/31(3)顯然a≤a∨a。又由a≤a可得a∨a≤a。根據(jù)偏序關(guān)系的反對稱性有a∨a＝a。同理可證a∧a＝a。(4)顯然a∨(a∧b)≤

a，又由a≥a和a∧b≤a，可得a∨(a∧b)≤

a。根據(jù)偏序關(guān)系的反對稱性有a∨(a∧b)＝a。同理可證a∧(a∨b)＝a。2023/12/31定理7.16設(shè)(P,∧,∨)是格，那么對a、b∈P，有： a∧b=a當且僅當a∨b=b定義7.11如果格(P,∧,∨)滿足分配律，那么稱(P,∧,∨)是分配格。對任意的a、b、c∈P，有 a∧(b∨c)=(a∧b)∨(a∧c)， a∨(b∧c)=(a∨b)∧(a∨c).定義7.12一個格既有下界又有上界，稱為有界格。2023/12/31定理7.17設(shè)(P,∧,∨)是有界格，那么對任意a∈P，有：a∨1=1，a∨0=a；a∧1=a，a∧0=0其中1和0分別是(P,∧,∨)的上界與下界。說明：1是(P,∧,∨)關(guān)于∧的單位元；0是(P,∧,∨)關(guān)于∨的單位元；有限格一定是有界格。2023/12/31

2023/12/31

2023/12/31定義7.14設(shè)〔P,+,?〕是代數(shù)系統(tǒng)，+和?是二元運算，如果滿足：交換律、結(jié)合律和吸收律，那么稱〔P,+,?〕是代數(shù)格。定理：一個偏序格必是一個代數(shù)格，反之亦然。19世紀50年代，英國人喬治.布爾〔GeorgeBoole〕創(chuàng)造出了一套符號系統(tǒng)，利用符號來表示邏輯中的各種概念。并且建立了一系列的運算法那么，利用代數(shù)方法研究邏輯問題，初步奠定了數(shù)理邏輯的根底。布爾代數(shù)定義：一個有補分配格稱為布爾代數(shù)，可以記為(B,+,?)

所有可能出現(xiàn)的數(shù)只有0和1兩個；根本運算只有“與〞、“或〞、“非〞三種；在布爾代數(shù)中用等式表示命題，把推理過程看作等式的變換。這種變換只依賴于根本運算的性質(zhì)。

布爾代數(shù)的性質(zhì)布爾代數(shù)在誕生100多年后，在計算機的開展中找到了它的用武之地，它為電子數(shù)字計算機開關(guān)電路設(shè)計提供了最重要的數(shù)學(xué)方法。

1938年，美國數(shù)學(xué)家、信息論創(chuàng)始人香農(nóng)(C.Shannon)發(fā)表了著名的論文“繼電器和開關(guān)電路的符號分析〞，首次用布爾代數(shù)進行開關(guān)電路分析。由于布爾代數(shù)只有0和1兩個值，恰好與二進制數(shù)對應(yīng)，香農(nóng)把它運用于以脈沖方式處理信息的繼電器開關(guān)。并證明布爾代數(shù)的邏輯運算，可以通過繼電器電路來實現(xiàn)，明確地給出了實現(xiàn)加、減、乘、除等運算的電子電路的設(shè)計方法，從而從理論到技術(shù)徹底改變了數(shù)字電路的設(shè)計方向。

45邏輯門電路計算機芯片里使用的邏輯部件，都是由各種布爾邏輯元件—邏輯門和觸發(fā)器組成的。由邏輯元件可以組成各種邏輯網(wǎng)絡(luò)，這樣任何復(fù)雜的邏輯關(guān)系都可以由邏輯元件經(jīng)過相應(yīng)的組合來實現(xiàn)?；谶壿嬢斎胱兞浚a(chǎn)生邏輯輸出結(jié)果的電路稱為邏輯門電路一個門電路由假設(shè)干個晶體管組成的，但邏輯上僅看作是一個單元；一個集成電路由假設(shè)干個門組成，實現(xiàn)特定邏輯關(guān)系的變換。46三種根本的邏輯門符號：直接對應(yīng)著其布爾操作〔“與〞門、“或〞門、“非〞門〕47“異或〞門可以通過根本邏輯門構(gòu)造出來。48“與非〞門“或非〞門49任何邏輯關(guān)系都可以僅僅使用“與非〞和“或非〞兩種門電路構(gòu)成所以它們稱為“全能〞門易生產(chǎn)、造價低5051一個邏輯門電路可以有多個輸入，至多兩個反相輸出。當電路的輸出僅與當前即時輸入狀態(tài)有關(guān)時，稱為組合邏輯電路；門電路組合起來可從邏輯上實現(xiàn)表達式的結(jié)果。52通過邏輯元件構(gòu)造電路判斷兩個線路等價分配律電路最小化：降低本錢、提高可靠性根據(jù)運算表構(gòu)造邏輯表達式輸出結(jié)果為1的那些組合的邏輯加55一個組合邏輯電路的實例：半加器，實現(xiàn)兩位數(shù)字相加并產(chǎn)生一位進位56利用一個異或門和一個與門實現(xiàn)半加57

全加器除了本位和之外，還需要考慮低位來的進位；全加器真值表：58由真值表直接寫出Sum和carry_out表達式…59全加器實現(xiàn)電路60(x⊕y)carry_in(x⊕y)xy通過半加器構(gòu)造全加器carry_inxycarry_outSumx+y+進位用全加器和半加器將兩個三位整數(shù)相加x0y0x1y1x2y2s0s1s2c2=s3進位進位把上述全加器連接起來構(gòu)成串行加法器〔波紋進位加法器ripple〕63缺點是高位需要等待低位的進位，速度慢

四元數(shù)四元數(shù)〔Quaternions〕是由威廉·盧云·哈密頓〔WilliamRowanHamilton,1805-1865〕在1843年愛爾蘭提出的數(shù)學(xué)概念；四元數(shù)描述剛體的轉(zhuǎn)動；四元數(shù)是復(fù)數(shù)的不可交換延伸；如把四元數(shù)的集合考慮成多維實數(shù)空間的話，四元數(shù)就代表著一個四維空間，相對于復(fù)數(shù)為二維空間。四元數(shù)可用在電腦繪圖〔及相關(guān)的圖像分析〕上表示三維物件的旋轉(zhuǎn)及方位。四元數(shù)也可以用于控制論、信號處理、姿態(tài)控制、物理和軌道力學(xué)，都是用來表示旋轉(zhuǎn)和方位。四元數(shù)轉(zhuǎn)換組合比很多矩陣轉(zhuǎn)換組合在數(shù)字上更穩(wěn)定；四元數(shù)可以用于位姿計算和變換，并不斷用來解決運動學(xué)和動力學(xué)的分析和控制問題；用四元數(shù)作為控制信號，不僅容易得到剛體角運動的穩(wěn)定控制，而且在許多情況下都接近于最優(yōu)控制。n一個有固定點的剛體通過繞該點的某個軸轉(zhuǎn)過特定角度可到達任何姿態(tài)轉(zhuǎn)軸的方向可以表示成一個單位矢量:那么描述該轉(zhuǎn)動的四元數(shù)可以表示成:四元數(shù)既反映了轉(zhuǎn)動的方向又反映了轉(zhuǎn)動的幅值.67四元數(shù)的表示：λ-----標量局部----矢量部分包括一個實數(shù)單位1

和三個虛數(shù)單位i,j,k

另一種表示法:,P

代表矢量部分群旋轉(zhuǎn)非零四元數(shù)的乘法群在R3的實部為零的局部上的共軛作用可以實現(xiàn)轉(zhuǎn)動。單位四元數(shù)〔絕對值為1的四元數(shù)〕假設(shè)實部為cos(t)，它的共軛作用是一個角度為2t的轉(zhuǎn)動，轉(zhuǎn)軸為虛部的方向。四元數(shù)的優(yōu)點是：表達式