离散数学课件代数系统

《离散数学课件代数系统》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章代数系统(抽象代数)以前学过许多代数：初等代数、高等代数(线性代数)、集合代数、命题代数、等等它们研究的对象分别是整数、有理数、实数、矩阵、集合、命题等等，以及这些对象上的各种运算。这一章我们将代数的研究引导到更高的层次，即抛开具体对象去研究代数——抽象代数。就专业知识而言，计算机学科中要培养学生三个能力：理论抽象设计理论：就是计算机科学中各种理论课。抽象：要把实际问题抽象成数学模型(数学系统)。设计：系统设计、程序设计。确定数学模型，需要了解有哪些代数结构(系统)。另外，抽象代数可以培养学生的抽

2、象逻辑思维能力。本章所讨论的理论，在计算机的编译理论、程序理论、语义理论、编码理论、计算理论、逻辑设计理论、数据库理论等都有应用。本章主要讨论：代数结构(系统)的概念，运算的性质、代数结构(系统)的同构、半群、独异点、群、环、域等。6-1代数结构(系统)的概念所谓代数结构(系统)，无非是有一个运算对象的集合，和若干个运算，构成的系统。一.n元运算如何定义运算，先看几个我们熟悉的例子：取相反数运算“-”、集合的补运算“~”以及N上的“+”II可见运算“-”、“~”、“+”就是个映射。-0。1。2。-1。-2。

3、......。0。-1。-2。1。2......P(E)P(E)~{a}。{b}。{a,b}。Φ。。{a}。{b}。{a,b}。ΦN2N+<0,0>。<0,1>。<0,2>。<1,0>。<1,1>。.........。0。1。2。3<1,2>。1.定义：设X是个集合，f:XnY是个映射，则称f是X上的n元运算。(Xn=X×X×...×X--n个X的笛卡尔积)，如果YX，则称运算f在X上是封闭的。f:XY是个一元运算。前面的-、~是一元运算。f:X2Y是个二元运算。+×÷∧∨∪∩是二元运算。思考题：下

4、面说法是否正确？减法－是N上封闭的二元运算。除法÷是整数I上的二元运算。除法÷是实数R上的二元运算。我们主要讨论二元运算。通常用、、、、、、+等表示抽象的二元运算。如果用“”表示二元运算f时，通常将f()=z写成xy=z。n个2.二元运算的运算表有时用一个表来表示二元运算的运算规律。例如令E={a,b}，P(E)上的∩运算表如图所示。再如令X={S,R,A,L}其中S表示开始时的位置；R表示“向右转”；A表示“向后转”；L表示“向左转”；“”表示转动的复合运算；其运算表如图

5、所示。从运算表除了可以看清运算的规律外，可以很容易地看出运算的性质。SRALSSRALRRALSAALSRLLSRA∩ΦΦ{a}{a}{a}{a}{a}{b}{b}{b}{b}{b}{a,b}{a,b}{a,b}ΦΦΦΦΦΦΦΦΦ上表头元素左表头元素运算二.代数系统的概念1.代数系统的定义：X是非空集合，X上的m个运算f1,f2,…,fm构成代数系统U,记作U=(m≥1)注意：这m个运算f1,f2,…fm的元数可能不同,比如f1是一元运算，f2是二元运算,…,fm是k元运算。例

6、如，2.有限代数系统：U=是个代数系统，如果X是个有限集合，则称U是个有限代数系统。3.同类型代数系统：给定两个代数系统U=，V=如对应的运算fi和gi的元数相同(i=1,2,3,…,m),则称U与V是同类型代数系统。例如与<{T,F}，,∧,∨>、与6-2二元运算的性质下面着重讨论一般二元运算的性质：一.封闭性设是X上的二元运算，如果对任何

7、x,y∈X,均有xy∈X,则称在X上封闭。例如在N上加法+和乘法×封闭，而减法不封闭。从运算表可以很容易看出运算是否封闭。二.交换性设是X上的二元运算，如果对任何x,y∈X，均有xy=yx，则称是可交换的。大家都知道：加法、乘法、交、并、对称差等运算均是可交换。从运算表看交换性：是以主对角线为对称的表。三.幂等元、幂等性设是X上的二元运算，如果有a∈X，aa=a，则称a是幂等元。如果对任何x∈X,都有xx=x，则称有幂等性.从运算表看幂等元、幂等性：看主对角线的元素与上表头(或左表头)元

8、素相同。请看上述∩的运算表∩有幂等性。∩ΦΦ{a}{a}{a}{a}{a}{b}{b}{b}{b}{b}{a,b}{a,b}{a,b}ΦΦΦΦΦΦΦΦΦSRALSSRALRRALSAALSRLLSRA四.幺元(单位元、恒等元)设是X上的二元运算，如果有eL∈X，使得对任何x∈X，有eLx=x，则称eL是相对的左幺元。如果有eR∈X，使得对任何x∈X，有xeR=x，则称eR是相对的右幺元。如果eL=eR