離散數(shù)學(xué) 第09章 代數(shù)系統(tǒng).ppt

代數(shù)結(jié)構(gòu)主講 艾施榮 2 第三篇 代數(shù)結(jié)構(gòu)目錄 第八章半群 語言和自動機(jī)8 1半群和語言8 2語言和文法8 3有限狀態(tài)機(jī)8 4有限狀態(tài)自動機(jī)8 5語言與自動機(jī)的關(guān)系實(shí)驗(yàn)八 設(shè)計(jì)輸出狀態(tài)自動機(jī)第八章習(xí)題第九章代數(shù)系統(tǒng)9 1代數(shù)系統(tǒng)的概念9 2代數(shù)系統(tǒng)的運(yùn)算及其性質(zhì)9 3群與子群9 4同態(tài)與同構(gòu)9 5交換群與循環(huán)群置換群 9 6子群與群的陪集分解9 7環(huán)與域?qū)嶒?yàn)九 代數(shù)系統(tǒng)的基本運(yùn)算第九章習(xí)題第十章格與布爾代數(shù)10 1格的概念10 2分配格 有補(bǔ)格與布爾代數(shù)10 3分配格10 4有補(bǔ)格10 5布爾代數(shù)與布爾表達(dá)式10 6數(shù)字電路與最小化實(shí)驗(yàn)十 代數(shù)系統(tǒng)綜合課程設(shè)計(jì)第十章習(xí)題 3 第九章 代數(shù)系統(tǒng) 主要內(nèi)容 構(gòu)成代數(shù)系統(tǒng)的基本成分 二元運(yùn)算性質(zhì)和特異元素 同類型的與同種的代數(shù)系統(tǒng) 群的定義 實(shí)例與術(shù)語 群的基本性質(zhì) 子群的判別定理 陪集的定義及其性質(zhì) 子群與群的陪集分解 環(huán)與域 教學(xué)要求 理解代數(shù)系統(tǒng) 群 環(huán)與域的概念 理解同態(tài)與同構(gòu) 交換群與循環(huán)群置換群的區(qū)別 理解子群與群的陪集分解 重點(diǎn) 代數(shù)系統(tǒng) 群的定義與性質(zhì) 子群 陪集與拉格朗日定理 正規(guī)子群與商群 群的同態(tài)與同構(gòu) 循環(huán)群與置換群難點(diǎn) 代數(shù)系統(tǒng)的運(yùn)算及其性質(zhì) 陪集 群的同態(tài)與同構(gòu)等概念的理解 實(shí)踐活動 代數(shù)系統(tǒng)的基本運(yùn)算 4 9 1代數(shù)系統(tǒng)的概念 在計(jì)算機(jī)科學(xué)中 常用代數(shù)系統(tǒng)去描述機(jī)器可計(jì)算函數(shù) 研究運(yùn)算的復(fù)雜性 分析程序設(shè)計(jì)語言的語義等 由非空集合和該集合上的一個(gè)或多個(gè)運(yùn)算所組合的系統(tǒng) 常稱為代數(shù)系統(tǒng) 有時(shí)簡稱為代數(shù) 在研究代數(shù)系統(tǒng)之前 首先考察一個(gè)非空集合上運(yùn)算的概念 如將有理數(shù)集合Q上的每一個(gè)數(shù)a的映射成它的整數(shù)部分 a 或者將Q上的每一個(gè)數(shù)a映射成它的相反數(shù) a 這兩個(gè)映射可以稱為集合Q上的一元運(yùn)算 而在集合Q上 對任意兩個(gè)數(shù)所進(jìn)行的普通加法和乘法都是集合Q上的二元運(yùn)算 也可以看作是將Q中的每兩個(gè)數(shù)映射成一個(gè)數(shù) 至于對集合Q上的任意三個(gè)數(shù)x x2 x3 代數(shù)式x12 x22 x32和x1 x2 x3分別給出了Q上的兩個(gè)三元運(yùn)算 它們分別將Q中三個(gè)數(shù)映射成Q中的一個(gè)數(shù) 上述這些例子有一個(gè)共同的特征 那就是其運(yùn)算的結(jié)果都是在原來的集合中 稱那些具有這種特征的運(yùn)算是封閉的 簡稱閉運(yùn)算 相反地 沒有這種特征的運(yùn)算就是不封閉的 5 6 7 8 9 10 11 12 9 2代數(shù)系統(tǒng)的運(yùn)算及其性質(zhì) 13 14 15 對于滿足結(jié)合律的二元運(yùn)算 在一個(gè)只有該種運(yùn)算的表達(dá)式中 可以去掉標(biāo)記運(yùn)算順序的括號 例如 實(shí)數(shù)集上的加法運(yùn)算是可結(jié)合的 所以表達(dá)式 x y u v 可簡寫為x y u v 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 9 3群與子群 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 9 4同態(tài)與同構(gòu) 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 9 5交換群與循環(huán)群 置換群 81 9 5 1交換群 82 83 84 85 86 87 9 5 2循環(huán)群 88 89 90 91 92 9 5 3置換群 93 94 95 96 97 98 99 100 101 9 6子群與群的陪集分解 102 103 104 105 106 107 108 109 110 111 112