离散数学课本定义和定理

1、第1章集合1.1集合的基本概念1 .集合、元（元素）、有限集、无限集、空集2 .表示集合的方法：列举法、描述法3 .定义1.1.1 （子集）：给定集合A和B,如果集合A的任何一个元都是集合 B中的元，则称 集合A包含于B或B包含A,记为人匚0或"24,并称A为B的一个子集。如果集合A和B满足4U©,但B中有元不属于 A,则称集合A真包含于B,记为八U 8 , 并且称A为B的一个真子集。4 .定义1.1.2 （哥集）：给定集合A,以A的所有子集为元构成的一个集合，这个集合称为A的募集，记为#5）或2"1.2 集合的运算定义1.2.1 （并集）：设A和B是两个集合，则

2、包含A和B的所有元，但不包含其他元的集合， 称为A和B的并集，记为MUB.定义1.2.2 （交集）：A和B是两个集合，包含A和B的所有公共元，但不包含其他元的集合， 称为A和B的交集，记为定义1.2.3 （不相交）：A和B是两个集合，如果它们满足yin/? = 0,则称集合A和B是不相 交的。定义1.2.4 （差集）：A和B是两个集合，属于 A而不属于B的所有元构成集合，称为 A和B 的差集，记为小-0.定义1.2.5 （补集）：若A是空间E的集合，则E中所有不属于A的元构成的集合称为 A的补集，记为公.定义1.2.6 （对称差）：A和B是两个集合，则定义 A和B的对称差力R为1.3 包含排斥

3、原理定理1.3.1设八1，4为有限集，其元素个数分别为1人1，mi则I而同同+图定理1.3.2设勺/人为有限集，其元素个数分别为,则内显得闻向手|引+ Mai -两二肉两an Ml + kh n a3定理1.3.3设公为有限集,则M】U/U.MrJ =fly j - y H：ni+y |4介a0%|+“,+（-1严1n A2 n _重要例题P11例1.3.1第2章二元关系2.1 关系定义2.1.1 （序偶）:若工和y是两个元，将它们按前后顺序排列，记为,则成为一个序偶。派 对于序偶£的和当且仅当工=口并且¥ = %时，才称 任了和（会切相等，记为 （x,y） = （外力定义

4、2.1.2 （有序方元组）：若,卬勺/是个元，将它们按前后顺序排列，记为与&*/），则成为一个 有序，元组（简称口元组）。定义2.1.3 （直接积）:M和占是两个集合，则所有序偶（.%，）的集合，称为和的直接积（或笛卡尔积），记为八鬣". 定义2.1.4 （直接积）:设并小2,是也个集合，E #" = 12.，/1,则所有H元组J的集合，称为匹心儿的笛卡尔积（或直接积），记为dK/x “X（.定义2.1.5 （二元关系）若和的是两个集合，则力X8的任何子集都定义了一个二元关系，称为 MX仃上的二元 关系。如果力=8,则称为八上的二元关系。定义2.1.5 （恒等关系）

5、：设（是，上的二元关系，I = &刈"三题，则称勺是X上的恒等关系。定义2.1.7 （定义域、值域）：若S是一个二元关系，则称D=国存在Vrf妇工y） E 为S的定义域。R（5）=61存在答使住M £ 5为，的值域。定义2.1.8 （自反）：设R是集合上|加的关系，若对于 任何rEX,都有了心:I即国外E H则称发 关系是自反的。定义2.1.9 （反自反）：设A是集合上|不|的关系，若对于任何"EX,都满足即月对 任何.tE*都不成立，则称关系R是反自反的。定义2.1.10 （对称）：设K是集合上X的关系，若对于任何用VE&只要工Ky,就有VKh,

6、那么 称关系£是对称的。定义2.1.11 （反对称）：设R是集合上的关系，若对于任何,只要HR并且网比时, 就有K = y,那么称关系胃是对称的。定义2.1.11 （传递）设R是集合上的关系，若对于任何KyEX,只要并且yRz时，就 有短匕,则称关系a是传递的。定理2.1.1设A是集合上|¥的关系，若A是反自反的和传递的，则 R是反对称的。2.2 关系矩阵和关系图定义无定理无2.3 关系的运算定义2.3.1 （连接）：设氏为* XF上的关系，5为FXZ|上的关系，则定义关系R" = （。厘| 存在 乂 使优丁）e Ril（y e s称为关系R和5的连接或复合，有时

7、也记为|R，5|.定义2.3.2 (逆关系)：设|犬为¥乂产上的关系，则定义R的逆关系为i为V xX上的关系:.定理2.3.1设R和$都是XXV上的二元关系，则下列各式成立(1) (hT11 = h kUS二 5 n5) ' = w lns 1(4)1 = (K " g$)A-s 1定理2.3.2设代为XX Y上的关系,S为Fxz上的关系，则1(投"»t=55'2.4闭包运算定义2.4.1 (自反闭包)：设R是集合彳上的二元关系，如果是包含R的最小自反关系，则 称%是关系R的自反闭包，记为广(町|.定义2.4.2 (对称闭包)：设火是集合

8、犬上的二元关系，如果是包含A的最小对称关系，则 称“I是关系E的对称闭包，记为MR)I.定义2.4.3 (传递闭包)：设K是集合犬上的二元关系，如果"1是包含用的最小传递关系，则 称“也关系A的传递闭包，记为:或卜.定理2.4.1设#是集合仪上的二元关系，则(1)A是自反的，当且仅当r(K) = H.(2)田是对称的，当且仅当KR)=用(3)A是传递的，当且仅当t四 = &定理2.4.2设#是集合以上的二元关系，则r5) = "UJ.“ 'L恒等关系”定理2.4.3设#是集合X上的二元关系，则£( = HUN 1.“逆关系”定理2.4.4设及是集合

9、融上的二元关系,则R = "U R U /? U附.“ :u京集，定理2.4.5设X是一个八元集，八'是X上的二元关系，则存在一个正整数 取使得h' = k u w2 u /e3 u 炉2.5 等价关系和相容关系定义2.5.1 (覆盖、划分)：F是一个集合，氏£5工=1?)如果5 1%='则称。是S的一个覆盖。如果U1,4； = 5并且4H（1J = 1.2”nri*j）,则称以是6的一个划分，k中的元称为F的划分块。定义2.5.2 （等价关系）：设夫是X上的一个关系，如果K具有自反性、对称性和传递性三个性 质，则称A是一个等价关系。设“是等价关系，

10、若卜的，成立，则称H等价于H定义253（等价类）：设及是以上的一个等价关系，则对任何工W*,令四月=WWE*”.斓丹，称工k为二关于A的等价类，简称为W的等价类，克也可以简记为划.定义2.5.4 （同余）：对于整数 兄6和正整数m,有关系式：a =+ rL（0 < < m）b - mk2 + 上（0 < r2 <如果1 =，则称Q力对于模愠同余的，记作 码b（modm）定义2.5.5 （商集）：设A是X上的一个等价关系，由4引出的等价类组成的集合|Uh|hE*）|称 为集合上由关系W产生的商集，记为x/R.“等价类的集合”定理2.5.1 若是*上的一个等价关系，则由 改

11、可以产生唯一的一个对 X的划分。“商集” 定义2.5.6 （相容关系）：设R是K上的一个关系，如果A是自反的和对称的，则称 胃是一个相 容关系。相容关系可以记为所有的等价关系都是相容关系，但相容关系却不一定是等价关系。定义2.5.7 （最大相容块）：设/是一个集合，|引是定义在*上的相容关系。如果/中的 任何两个元都有关系 七，而M一小的每一个元都不能和 中所有元具有关系卜司，则称力是Y的 一个最大相容块。2.6 偏序关系定义2.6.1 （偏序关系）：R是定义在集合A上的一个关系，如果它具有自反性、反对称性和传递性，则称R是*上的一个偏序关系，简称为一个偏序，记为 KL更一般地讲，若x是一个

12、集合，在不上定义了一个偏序 4 ,则我们用符号来表示它，并称是一个偏序集。 定义2.6.2 （全序/链）：）是一个偏序集，对任何 归后弁，如果万岑引或iYk这两者中至 少有一个必须成立，则称（尤式）是一个全序集或链，而称I引是火上的一个全序或线性序。定义2.6.3（盖住）:W ）是一个偏序集，EX,若工人并且不存在2 E/使，< ?并且胃< ¥ , 则称盖住X. “紧挨着”定义2.6.4 （最小元、最大元）：PC 4）是一个偏序集，如果 田中存在有元产，对任何都满 足丫。,则称y是的最小元。如果x中存在有元,，对任何都满足mW %,则称*是 （XW）的最大元。定义2.6.

13、5 （极小元、极大元）：代W）是一个偏序集，如果yEX|,而乂中不存在元箕，使上<Y, 则称是伏，W ）的极小元。如果？ EX,而中不存在元M,使EC 4,则称1是（X,W）的极大元。定义2.6.6 （上界、下界、上确界、下确界）：是一个偏序集,再匚,尤丁,如果对于 所有的a 4都有a W '则称工是才的一个上界。如果对于所有的u E A,都有y 4肛则称y是！的 一个下界。如果人是人的一个上界，对于 人的任一上界z,都有其百则称是1的最小上界（上 确界）.如果V是的一个上界，对于孙的任一上界卬,都有wWy,则称丫是rI的最大下界（下确 界）.定义2.6.5 （良序集）：设彼,&

14、lt;）是一个偏序集，对于偏序I电如果X的每个非空子集都具有 最小元，则称是一个良序集，而称1式是尺上的一个良序。每个良序集都是全序集。第3章函数和运算3.1 函数定义3.1.1（映射、象）：关系/定义在上,如果对于每一个，e*,都有唯一的一个|ytr, 使伊沙）则称是从以到y的一个函数（或映射），记为六¥一丫1称为函数|川的变元，X称为变元，t在1/下的值（或象），记为戏 注意：（1） 定义域Mf二月 而不是见f）匚*（2） 每一个E有唯一的卜匕 使K，）E/.多值函数不符合定义值域R匚以定义3.1.2 （受限、扩展）：若，是从促到Y的一个函数，AQX,则/ n（/X门也是一个函数

15、， 它定义于乳到匕 我们称它是在1上的受限。如果/是函数g的一个受限，则称d是/的一个扩 展。定义3.1.3 （映上、映内、一对一、对应 ）：若/：»*¥,则/的值域二丫时，称函数/是映上的（或满射）。如果f的值域K仁H时，则称函数f是映内的。如果4典W *占*七,则有/（/）工八/）,则称/是一对一的（单射）（即，aj=r卜。时，有匕=勺）.如果f映上的，又是一对一的，则称 ，是对应的（或双射）。定义3.1.4 （复合运算）：若/：*T匕g,TZ|,则定义J和必的复合运算fug为：= 与幻|存在y e匕使y =代用,且/=gW）即f °g（x） = g（/（灯）

16、.注：逆函数若要存在需要满足以下条件：（1）函数/是映上的（2）函数/必须是一对一的定义3.1.5 （恒等函数）函数0 =13,冷国毛町称为恒等函数。定理3.1.1匕。于一&则b = f 1的充分必要条件是g"/=。，并且/ ”9 = 43.2运算定义3.2.1 （二目运算）：若夫是一个集合，/是从W X4至”的一个映射（函数），则称/为一个二目运算。一般地，若J是从川*到X的一个映射（也是正整数），则称/是一个月目运算。运算的封闭：运算的结果总是集合 X中的一个元，因此这个定义保证了运算的施行，这种情况又称为集合X对于该种运算是封闭的。定义3.2.2 （可交换）：若了渭乂

17、XtX是一个运算,对于任何芭都有，0加=/UK）, 则称运算1/是可交换的（或者说，/服从交换律）.定义3.2.3 （可结合）：若/次X 是一个运算，对于任何Z E * ,都有 /（用力团=f&JS）,则称运算1是可结合的（或者说，/服从结合律）.定义3.2.4 （可分配）:若火 乂犬*是一个运算，"*父是一个运算，对于任何工泮E X , 都有 心田"）=,则称运算对于运算自是可分配的（或者说，/I对于M服从 分配律）定义3.2.5 （左单位元、右单位元）：设图是不上的一个运算，如果X中存在有一个元句，对于任何有勺*则称中是运算*的左单位元；如果X中存在有一个元对于

18、任何HEM,有=则称凡是运算*的右单位元。定理3.2.1若,是，上的一个运算，/和吃分别是它的左、右单位元，则ef = cr = c并且值是 唯一的（因此，称为运算*的单位元）.定义3.2.6 （左零元、右零元）：设”是犬上的一个运算，如果X中存在有一个元0）,对于任何xex,有力尸=。1,则称6是运算*的左零元；如果X中存在有一个元 耳，对于任何xex,有则称&是运算的右零元.定义3.2.7 （等哥）：若,是X上的一个运算，aeX,对于运算* ,有= 则称元口对于 运算学是等哥的。定义3.2.8 （左逆元、右逆元）：若*是X上的一个运算，它具有单位元E ,对于任何一个HER, 如果存

19、在有元勺W*,使二则称卜1是口的左逆元；如果存在有元卜*工,使"*勺=。，则称。是口的右逆元；定理3.2.3 若*是/上的一个运算，它具有单位元 4,并且是可结合的，则当元口可逆时，它的左、右逆元相等，并且唯一的（此时称之为期的逆元，并且记为a '）.定义3.2.9 （可消去）：若是X上的一个运算，对于任何如果元口满足：&*工=靠*¥则工=见或工*” = y * 口贝版=y ,则称元口对于运算,是可消去的。第4章无限集合4.1 基数定义4.1.1 （等势）:若工和0是两个集合，如果在 力和之间可以建立 1?丁丁对应关 系，则称集合和“等势，并记为定理4.1.

20、1令口是由若干个集合为元所组成的集合，则。上定义的等势关系是一个等价关系。定义4.1.2 （有限集、无限集）：若八是一个集合，它和某个自然数集 =用等势，则称金是一有限集，不是有限集的集合称为无限集。定理4.1.2有限集的任何子集都是有限集定理4.1.3有限集不与其任何真子集等势定理4.1.4自然数集N = 0J2）是无限集4.2 可列集定义4.2.1 （可列集）：若只是一个集合，它和所有自然数的集合 M等势，则称，1是一个可列集。可列集的基数用符号 表示。定理4.2.1若人是一个集合，/可列的充分必要条件是可以将它的元排列为的序列形式。定理4.2.2任何无限集必包含有可列子集。定理4.2.3

21、可列集的子集是有限集或可列集（记为：定理4.2.4若八是可列集，。是有限集，并且小0 R=0 ,则U B是可列集（记为：诙+丸=M ）.定理4.2.5若其和仃都是可列集，并且= %则是可列集（记为：% + %=%）推论4.2.1设儿1 = 12，都是可列集，则4 = 14是可列集（记为：七%）二%）定理4.2.6设4Q = L2.，。都是可列集，并且""乙=矶"词=1Z），则56是可列集（记为：Kn Ko = KU）推论4.2.1设网u=12出都是可列集，则4 lA是可列集.定理4.2.7所有有理数的集合是可列集。4.3 不可列集定理4.3.1区间（0，L：中所有

22、实数构成的集合是不可列的。定义4.3.1 （连续基数）：开区间（04）中所有数组成集合的基数记为 N ,具有基数K的集合称 为连续统，：称为连续基数。推论：集合81的基数也是N.定理4.3.2所有实数的集合是不可列的，它的基数是立定理4.3.3对于任何数 叫 若口瓦 则区间（口戊力以及;0卬）,04）都具有连 续基数定理4.3.4 一个无限集八和一个可列集作并集时，并集的基数等于集力的基数。推论4.3.2 一个无限集/和一个有限集的并集，其基数等于集小的基数。4.4 基数的比较定义4.4.1 （比 网）设集合R的基数是q二夕如果从与白的真子集等势，而八和V不等势，则称 a的基数小于区的基数，记

23、为4定理4.4.1: 48是两个集合，若人与廿的某一子集等势，冏与八的某一子集等势，则aB.定理4.4.2:儿8是任意两个集合，4的基数为巴g的基数为# ,则下列三个关系： a = pra仇a 0中必有一个且只有个成立。定理4.4.3:若打是有限集力的基数，则底飞6.定理4.4.4:若X是无限集合，则Ko - CardW定理4.4.5:若“1奄一”/是可列个互不相交的集合，它们的基数都是M,则1勺的基数是N （记为：辱X= +*定理4.4.6:可列集的募集，其基数是 K （记为：2 = N）定理4.4.7：若用是一个集合，取二p（d）|是八的募集，则 皿A） * Card.此定理说明：不存在最

24、大的基数。补充：炉乩炉芭第5章形式语言5.1 文法和语言定义5.1.1 （产生式）：一个产生式或重写规则是一个有序对 O,通常写成J-扎其中，“是 一个符号，而工是一个符号的非空有限串，”是这个产生式的左部，而人是产生式的右部.产生 式将简称为规则。定义5.1.2 （非终极符号、字母表、终极符号、开始符号）：一个文法。是一个四元组（心/口）.其中，,耳是元语言的语法类或变元的集合，它生成语言的串，这些语法类或变元成为非终极符号，1%是符号的非空有穷集合，称为字母表，117T的符号称为 终极符号.5或打之一,是词汇表的一个识别元素，称为开始符号.是产生式的集合。定义5.1.3 （直接产生、直接推

25、导，直接规约 ）：设G是一个文法，如果X = 而G中有规则Uth,就称串U直接产生串W,或称中是P直接推导出来的，或 即直接规约到，记 为 定义5.1.4 （产生、规约到、推导）：设G是一个文法，如果存在产生式序列内/2PnE°）,使得'产22r而匕=。就说产生卬1 （廓规约到H,或M是H的推导），记为 k + w .定义5.1.5 （句型）：令G是一个文法，如果串支可从开始符号S推导出来，即如果5=*工，则闻 称为一个句型。补充： 若£ =依，则2/ = Arafbfoa.abtbafbbtuaaf.，其 中人是 空串，丁 =如也叫她如她emu,（不含空串）5.2

26、 文法的类型定义5.2.1 （0-型文法）：在工上的0-型文法由以下组成：（1） 不在工中的不同符号的非空集合 也称为变量表，它包含一个纲符号 刈,5称为开始变量。（2） 产生式的有限集合。由G产生的所有字集称为由6产生的语言。定义5.2.2 （0-型语言）：在工上可由某一 0-型文法产生的字集称为 0-型语言。定义5.2.3 （ 1-型文法）：如果在0-型文法中，对于P中的每个产生式sta,要求IM W |0| ,则 这文法称为1-型文法或上下文敏感文法.定义5.2.4 （2-型文法）：设文法仃=匕”,对于P中的每一个产生式Rf?旬山勺河且（有的人要求 H 则此文法叫2-型文法或前后文无关文

27、法。定义5.2.5 （3-型文法）：设G =为一文法,又设P中的每一个产生式都是或Stci|,其中儿和©都是变量，而口为终极符号，而此文法为 3-型文法或正规文法。第1章代数系统1.1代数系统的实例和一般性质定义1.1.1 （代数系统）：若X#是序偶，又是一个非空集合，”是定义在上的某些运算的 非空集合，则称 5,5是一个代数系统,或称代数。代数系统的类型：（1）代数系统 体仃卜的%）的类型是 四g/J,其中仃一%”代表1,2，,m目运算 符。（2） 俨勺心6），分别为0,1,2目运算符，则（无。1，吗内）的类型为K。3.1.2 同态和同构定义1.2.1 （同态象、同态映射）：亿明）

28、和传出）是两个同类型的代数系统， 映射卡出和 的也构成一一对应.如果对于任意H目运算/6力，及其对应的运算叼E外,当。盟，.与£* 时,都有© 16rl弧次，J =叮出刈必。"（%）则称代数（匕。力是，闭）的同态象，称y是 从%）到化）的一个同态映射。定义1.2.2 （同态象、同态映射）：若%。）和1（匕*是两个同类型的代数系统， 。和*都是二 目运算，映射9；XtF.如果对于任何用yEX,都有“© ,则称忆"）是的一个同态象，称M是从（。）到（匕）的一个同态映射。注：如果化就是以），则映射9是从X到它自身。当上述条件仍然满足时，我们就称）是（

29、*” ）的一个自同态映射。定义1.2.3 （同构、同构映射、自同构映射 ）：如果和（匕*是同态的，映射不仅 是同态映射，而且是 丁丁对应 的，则称（匕*）和区”同构，称d是从阳力到亿的一个同 构映射。如果匕. 就是%“）,则称©是（X” ）上的一个自同构映射定义1.2.4 （同余关系）：设是一个代数系统，是？上的一个等价关系，如果存在工.勺片两日当时，'F）L成立，则称是侬川上的一个同余关系。定理1.2.1：设是Z上的一个等价关系，如果存在同态映射tE *,使得当。£7时，工1巧当且仅当9（/）=。卜。，则是（Z,。）上的同余关系。1.3 商代数与积代数定义131（

30、子代数）：设亿叮是一个代数系统，入口胃在运算。|下封闭的，则称亿1，“是 的一个子代数。定义1.3.2 （直接积）：设7到匕串）是两个同类型的代数系统，如果对任意的叫勺£彳和力定义运算殖于胃X士佑必也帆必）=彷"去当* %）,称化乂匕的是（Z,。）和匕”的直接积，称）和优”为（ZXY,到的因子。第2章半群和群2.1 半群和有幺半群定义2.1.1 （半群、有幺半群）：S是一个非空集合，如果5中定义了一个二目运算 ，对于任 何相力,。£5,都有9 与y = *3仃，则称（S,）是一个半群.如果半群（5, ）中具有单位元 外 使得对任何ME5,都有又=货己=比则称（5，

31、力是一个有幺半群。（1） £是一个由有限个符号组成的集合，其中的元称为字母。 表示所有的字构成的集合，七”表示非空串组成的集合。（2）自由半群：半群的各元相互间没有任何关系。“）说明：半群是一个定义了二目运算， 并且服从结合律的代数系统。有幺半群则是具有单位元的半群。2.2 群和循环群定义2.2.1 （群）：在代数系统 Q中，如果二目运算I*满足（1）对于任何 h也cwq有。（2）。中存在单位元e,对任何OWG,有。2 =（3）对于任何QEG,存在有逆元说】£；,使江*b 1 = a则称他，*）是一个群。注：对于群 *）来说，单位元e是唯一的，每个元d的逆元口 一：也是唯一

32、的。“存在逆元的有幺半群叫做群”定义2.2.2 （阶数）：若 n是一个群，当G是有限集时，则称a中元的个数为群的阶数， 记为 .定理2.2.1若国，*是一个群，则:孙厂|二厂屋:其中孙即工*¥.定义2.2.3 （哥）:*，是一个群，xEGl,则记卜个N的积北串一上为F ,犬r称为N哥，（工）记为工, x表示单位元e。定理2.2.2 （指数律）：若m和月是整数，则工"二二婷）定理2.2.3若盯="，则/，" 二 V铲定义2.2.4 （次数）：若）是一个群，x 6,使/ = e = x0的最小正整数n ,称为元m的次数。定理2.2.4若* ）是一个群，归E行

33、，X的次数为n ,则/ = ex/ 1都是G中不同的元。定义2.2.5 （循环群、生成元）：由一个单独元素口的一切哥所组成的群称为循环群，Ci称为这个群的生成元。定理2.2.5在阶数为内的循环群，由生成元M所产生的元必次数为%即/是生成元的充分必要条件是r和芭互质。定理2.2.6若，,和打不是互质的，则.的次数是“凡其中的f是H和H的最小公倍数。定义2.2.6 （阿贝尔群）：如果群邑，）中的元对于运算*满足交换律，则称这个群是一个阿 贝尔群。“满足交换律的群叫做阿贝尔群”循环群是一个阿贝尔群。定理2.2.7若和仍,*）都是有限的阿贝尔群，定义+仅*2）=（%，的由1 *瓦）则储X丛+ 是一个阿

34、贝尔群。最简单的一个阿贝尔群是14群（的/时目为按位加2.3 二面体群、置换群二面体群是从图形的变换中到处，这些图形都是比较正规的图形。定理2.3.1必二bl" 一更一般地讲，ah-batl'r定义2.3.1 （置换）：若S是一个非空的有限集合， 则S上任何一个到它自身的一一对应的映射， 都称为3上的置换。定理2.3.2两个置换的乘积仍是一个置换，并且置换的乘积服从结合律。S的恒等映射也是一个置换称为单位置换。S上所有置换的集合，对于置换乘法构成一个群，这个群称为对称群，记为 :?是S中元的个数。定义2.3.2 （”阶置换群）若S是非空有限集合，仃是S上的打个置换所构成的群，

35、则称 仃是一个 M阶置换群。定理2.3.3任何一个（曾阶）群都同构于一个（孔阶）置换群。2.4 子群、群的同态定义2.4.1 （子群）：（&*）是一个群，.匚G,如果（1）单位元K £ $（2）若则。的逆元n" E5（3）若&bES|,则则称”是但J）的一个子群。定理2.4.1是一个群，5匚3,）是一个子群的充分必要条件是：若口力ES,则定义2.4.2 （同态象、群同态映射 ）：和伴,* 是群，.若对任何0b E G ,有 09 * b） = ff（a）心 g®群的同态映射具有下列性质：（1）将单位元映射为单位元（2）将逆元映射为逆元 对运算封闭，

36、即对任何。力丘3,有。功定理2.4.2若值*）和四*）是群，g：GT,是一个群同态映射，则。将伍* 的子群映射为网” 的子群。定义2.4.3（同态核）：若箪Gt"是一个群同态映射，口是的单位元，则G中所有满足= %的元值的集合，称为同态核，记为 KerS”定理2.4.3同态核是一个子群。定理2.4.3若是群G）的子群，则也定义了。上的一个划分（因而也定义了 G上一个等 价关系）.群子集：假定A3都是群（6 *）|中的元构成的集合（称之为群子集），定义AB = abaeA,beBi特别地，当八是一元集时，我们简记 他为他，则如=5 帅EZ?定理2.4.5若（儿事）是群（氏的子群都是群

37、道的子群，则依乱）是一个群的充分必要条件是2.5 陪集、正规子群、商群定义2.5.1 （左陪集）：若是群的子群，对于口EG,称M=S*h|hE川称为用的一 个左陪集.定理2.5.1若UL7是群（也串）的子群，则山的所有左陪集构成6的一个划分。定理2.5.2 （拉格朗日定理）每个左陪集的元和口中的元都是一样多。推论2.5.1子群中元的个数一定是群中元的个数的因子。定义2.5.2（正规子群）：若比*）是群（足,）的子群，对于任彳01。4都满足。开="&,则称（凡*）是群旧厂的一个正规子群.一个阿贝尔群的任何子群都是正规子群。当，是群（也的正规子群时，对于关于6的陪集.定义运算I

38、'为b" =考虑所有同关于g的陪集组成的集合mm。£用和运算.构成的系统（加，7为一个群。这个群称为作关于的商群，记为GL定理2.5.3若9：Gt是从群 * ）到群（” ）的映上的同态映射，则核N是正规子群，商群G/N 同构于' .群同态基本定理：商群G/N是由陪集£山叮构成的群，也是同余类的集SN构成的群，所以它 同构于象代数，即 GN同构于H.如果群没有真正的正规子群，则该群为 单群。正规群的任何子群都是正规子群。第3章格和布尔代数3.1格定义3.1.1 （格）：（LW）表示一个偏序集，如果对于 山中的任何两个元a和h ,在L中都存在一个元是它

39、们的上确界，存在一个元是它们的下确界，则称是一个格。对于中的元。力，它们的上确界常常记为也田卜,它们的下确界常常记为口*台,前者又称为a和 .匕析取或和（或H +力，后者又称为口和b的合取或积（。八方或仇力或心）。定理3.1.1若£, < >是一个格，则对于任何 心力E L ,有（1）« < b的充分必要条件是tt* = a|.（2）。玉5的充分必要条件是 我田b= 5.定理3.1.2 （保序性）若（LE）是一个格，则对于任何&现cel,当bd时，有 a*b<a* cfab <口上（引理 3.1.1 若是一个格，|口也。瓦口 则定理3.

40、1.3 （分配不等式）：若出0是一个格，则对于任何口力.出3 * L）< （。匕）* （附。）a * （bfficj > （a * 与日（口 * c）定理3.1.4 （模数不等式）若（L < >是一个格，则对于任何afb,c EL<C的充分必要条件是a®（t + c） *c|定理3.1.5若see是一个代数系统，由和*是5上的二目运算，它服从交换律、结合律和 吸收律.则母电*，是一个格.定义3.1.2 （子格）甩舟）是一个格，5 口,当且仅当5对于运算出和是封闭的，运算结 果和在£中相同时，则称代数系统 舟,*）是工的一个子格。定义3.1.3

41、（直接积）若3曲）和母 忆A是两个格，则 仕乂£+）称为这两个格的直接积，其中的运算+和，定义为：对于任何的他力1M优加力s 乂 s,的%卜他力分二口1 *叼/1 A %）（向力1） + 町也）=口仲叼由V/定义3.1.4 （同态映射）设a曲,*）和£匕A）是两个格，gT5.如果对任何,有虱口 *b） = gA gb）小通垃=目V g（b）则称g是©到 *A）的一个同态映射.特别地，当g是一个一一对应时，称 b是一个 同构映射，并且称格 L串.*）和 九A）同构的。如果g：L一2是格）上一个同态映射，则称©是一个自同态映射.如果是一个同构映 射，则称目是

42、一个自同构映射.定义3.1.5 （完备）：对于一个格，如果它的每一个非空子集在格中都具有一个上确界和下 确界，则这个格称为完备的。显然每个有限的格都是完备的。对于一个格，它的上确界和下确界如果存在，我们称它们为这个格的边界，并分别记为1和0,因此有时这种格称为 有界格。定义3.1.6（补元）：出限3。1）是一个有界格，aeL如果存在元bEL，使U *%=0且岫8 = 1 , 则称8为仃的补元。定义3.1.7 （补格）：（工舟，*凡1中的每个元都至少具有一个补元，则称这个格是一个补格。定义3.1.8 （分配格）：他我*）是一个格，如果对任何 岫E L ,有a * （匕缶匚）=（<（- c）

43、。=（岫b） * （a®c）则称缶>是一一个分配格。定理3.1.6任何两个分配格的直接积是分配格。定理3.1.7若L曲，是一个分配格，则对于任何。力E2,如果R*b = U *匚，并且限Bh也C,则推论3.1.2如果一个格是分配格，同时又是补格，则它的每一个元都具有唯一的一个补元。3.2 布尔代数定义3.2.1 （布尔代数）一个既是补格，又是分配格的格，称为布尔代数。定义3.2.2 （对偶命题）如果（比/,八:0,1）是一个布尔代数，R是关于B中变元的一个命题,它可以由口中变元元通过运算 V ,八1。来表示.如果对P的表示式进行下列代换：V代换为| A ; A代换为| V； 1

44、代换0； 0代换为1 ,则这样代换后也将得到一个命题 ,它成 为命题F的对偶命题，简称为对偶。定理3.2.1 （对偶原理）如果?是一个命题，它在任何一个布尔代数中都成立，并且可以由运算Y，A一仇1来表示，则对它的对偶命题 也在任何一个布尔代数中成立。定理3.2.1* （对偶原理）如果P是一个命题，它在任何一个布尔代数中都成立，并且可以由运算WA二。和关系|，之来表示，则将P中的运算V代换为A ；|八|代换为V ； 0代换为1, I代换0； M换为之，之换为宣，所得到的对偶命题也在任何一个布尔代数中成立。定理3.2.2若0和%是两个布尔代数，入出是一个同态映射，则月在h中的同态象可见是% 的一个

45、子布尔代数。aI定义323（基元）：出，）是一个布尔代数，支684工0,如果0中不存在元，,使？*：口 则称“是3的一个基元。如果对于任何 bEBrbt °都存在有基元，则称这个布尔代数是基 元的。定理3.2.3若（乱丫/，01）是一个布尔代数，UW。*。,则下列命题是等价的。（1） n是一个基元（2）对于所有的,£纥若工0口,则工=0或1 = 口（3）对于所有的卜以'一1仇。出时推论3.2.1若*和力是不同的基元，uAh=O定理3.2.4伊A,。口）是一个基元的布尔代数，力是其基元的集合，对任一 卜已优令 双外=“*£,则%心声,并且作为基元的析取式，这

46、个表达式是唯一的。定理3.2.5若（昆fk）是一个非空有限的布尔代数，M是它的所有基元构成的集合，则（/八/二。）同构飙用05：0川推论3.2.2 一个有限的布尔代数具有2,个元，其中的内是它的基元的个数。推论3.2.3对于任意正整数 通具有2"个元的布尔代数是同构的。3.3 其他代数系统定义（环）3.3.1若代数系统（凡+ , ）满足下列条件：（1） R对于二目运算|+是一个可交换的加法群。（2）长对于二目运算卜| （即乘法）是封闭的。（3）乘法结合律成立，即对 K中任何三个元口力和£有a （d - c） = （ur b） c（4）分配律成立，即对 长中任何元U力和匕有a

47、（bc） = ab + a*cf £? + c） « = b « + c a|则称（凡+ ,7是一个环。定义3.3.2 （交换环）一个环A中的任何两个元 电h,如果都满足Q , 8 = b ,口，则称R是一个交换 环。定义3.3.3 （逆元、零元）一个环冗中如果存在有元/使得对R中任何一个元都有 ,aae = 4，则称e是R的一个单位元。定义3.3.4 （逆元、零元）在一个有单位元的环里， 如果口和8是环中的元，满足。= 1, 则称8是门的逆元。对任意口£风若。，江=支内=0,则称0是用的零元。环的零元通常用0表示。定义3.3.7 （域）：一个可交换的除

48、环称为一个域。定义3.3.8 （子环）：一个环汗的一个子集区本身对R的代数运算也构成一个环，则称 $为R的子 环。定义3.3.9 （理想子环，理想）：若'是环A的一个非空子集，满足（1）aeiu-be I aehrERra.ar EI则称/是R的一个理想子环，简称理想。第4章群码1.1 通信模型和错误校正的基本概念1.2 二进制编码定义4.2.1 （海明距离）设zyw夕次与，之间的海明距离是与由v的权I*缶W,用矶苞y表示。定理4.2.1设DZ £ B”,则（1） =（2）（3） ”*,y） = 0当且仅当然¥"（醐）定义4.2.2 （码字）：码字是卜I元

49、组的码的最小距离，是该码中所有码字之间的海明距离的最小值。定理4.2.2当且仅当一个编码的任意两个码字之间的最小距离至少* + 1时，能够检查出M个或至少k个错误的所有组合。定理4.2.3当且仅当任意两个码字之间的距离至少是2k + l时，这中编码就能够纠正 上个或 少于打个错误的组合。定义423（群码）设（即,和出曲）是群，函数仃仍18",使得«即）=岫）出£*是#"的子群，则称E是编码函数.“暧。是群码。定理4.2.4 一个群码的非零码字的最小权等于它的最小距离。定 义 4.2.4 设/ =匐对C=/",其 中% = u通比I £

50、 f g m;l </ S m定义4.2.5 （布尔矩阵）：设“二西二岛Lxn是布尔矩阵，布尔矩阵的积|F«D *fi = /fJm乂卜是布尔矩阵，其中 fj = % + di2d2i + + 4r41.定理4.2.5设m和也是非负整数，且m<ri,r=m-m,并设“是HXF布尔矩阵，则函数力MhI加=超* t!,x E日”是从群川到川的同态映射。推论4.2.1设m和T1是非负整数，且m廿二汽一叫并设是nxr布尔矩阵，函数 心4九3 =1* "K E耳"使得N = 小E Hb *H = 0是正规子群。定理4.2.6设工二当冷Vm/勺E” ,则当且仅当某

51、b E 二为.推论4.2.1 看仪然似咖E，严是必的一个子群。1.3 解码和错误校正定义4.3.1 （解码函数）：若比是映上函数，如果“苞）二占6"二使得当传送通道没有 噪声时，占=片，则称J是与己对应的（氏用；解码函数。定义4.3.2述级校正）设。是一个（叫世；编码函数，4是与。对应的解码函数，如果 工二式。）是 正确传送或具有人级错误，则称（巳是上级校正。定理4.3.1假设已是筋典；编码函数，d是对应的最大似然译码函数，则:上出）能够校正化级错误，当且仅当士的最小距离至少是2A + 1.定义4.3.3 （陪集头）的左陪集中，具有最小权的元素称为陪集头。定理4.3.2如果范&

52、;，和/"定义如前，则是映上的。定理4.3.3设上和V是出的元素，则r和处于N的同一左陪集，当且仅当加幻二介（丁），即当且仅当它们有相同的并发错。第1章命题演算1.4 命题和逻辑连接词定义1.1.1 (命题)：如果有一个陈述语句，它可以取值：“真”或“假”，并且只能取其中一个值，这样的陈述语句就成为一个命题。5中基本逻辑连接词：(1)：否定词：“非(2) A :合取词：“力并且修”(3) V :析取词：“乂或者，(4) t：蕴涵词：“若。则等值词：“力等值于夕,1.2合式公式能成为命题的式子称为合式公式，简记为叩。定义1.2.1 (合式公式)：(1) 一个命题变元是 wff.(2)若

53、P是一个W",则干是一个权".(3)若p和Q是附"，则:PAQ)"P¥QMIJQ)和;J'Q)都是坪"1.1 只限于有限次使用(1) (2) (3)所得到的符号串。定义1.2.2 (部分合式公式)如果0和“都是用制，B是J的一部分，则称是1的部分合式公式或子公式，部分合式公式简记为结论：在小刀都是且是符号串尸的一个组成部分时。如果用 区代换P中全部的八,所得到 的是Q.当且仅当Q是*"时，?是用/.判断符号串p是否是w".的算法：(1)空公式不是W/丹(2)对P中的叩/P用命题变元代换，得到新的符号串P(3

54、)检查?是否还能作进一步代换，以消除逻辑连接词.如何能则转(2)(4)检查最后的符号串 是否是简单的命题变元，如果是，则原来的P是：'"，否则不是。重要例题1.2.71.3 真值表、永真式定义1.3.1 (永真式、重言式、有效)对于一个卬"的命题变元无论作何指派，所得到的值永为n即命题永远是真命题，则称该卬"为永真式或重言式，并称它是有效的。定义1.3.2 (永假公式、不可满足公式 )对于一个卬/了的命题变元无论作何指派，所得到的值永为用即命题永远是假命题，则称该 卬/为永假公式或不可满足公式。定义1.3.3 (可满足公式)不是永真式的卬"称为非

55、永真公式。 不是永假公式的麻/f称为可 满足公式。定理1.3.1永真公式的合取式或析取式仍然是永真公式。定理1.3.2在一个永真公式中，对某个变元用同一个 置换，其结果仍然为永真公式。定理1.3.3若八和区都是W/O3的充要条件是是一个永真式。定理1.3.4 一个W"的永真式、永假性、非永真性和可满足性是可判定的。1.4 命题演算的等价关系定理1.4.1 (代换定理)若J是一个W/儿儿是它的一个电通"产"在将用中各处出现的小中的一个或若干个代换 片时，如果得到的卬"为8，则"=B.1.5 逻辑连接词的可省略性如果能找到一个更小的逻辑连接词的集合

56、，用它们也能完成上述五个连接词的全部功能，则我们把这种连接词的集合称为连接词的功能完全集。功能完全集：f V、fA、r、T、国T：读为“与非" （2） T读为“或非”MoPTPoPTPP V Qo（PTP）T（QTQ）q（P1P）1（Q】Q）1.6 范式定义1.6.1 （初等积）：命题变元和它们的否定的合取式称为初等积。定义1.6.2 （初等和）：命题变元和它们的否定的析取式称为初等和。定义1.6.3（析取范式）：如果一个出”具有形式41nzi J"八仙"）而每个川都是初等积，则它称为析取范式。定义1.6.4 （合取范式）：如果一个出”具有形式*1 A/*八3W

57、1；而每个网都是初等和，则它称为合取范式。定义1.6.5 （最小项）：在初等积中，每个命题变元和它的否定不能同时出现，但两者中必须出现一个，而且只能出现一次，这样的初等积称为最小项。定义1.6.6 （标准析取范式）：对于一个Wff,仅由它的最小项的析取组成的等价公式称为 它的标准析取范式。定理1.6.1在真值表中，一个原"的真值为的指派所对应的最小项的析取式，即为此郎/丹的标准析取范式。“真值为的并集，变元取正”定义1.6.7 （最大项）：在初等和中，每个命题变元和它的否定不能同时出现，但两者中必须出现一个，而且只能出现一次，这样的初等和称为最大项。定义1.6.8 （标准合取范式）：对于一个W/丹，仅由它的最大项的合取组成的等价公式称为它的标准合取范式。定理1.6.2 一个W"的真值为F的指派所对应的最大项的合取式，即为此的标准合取范式。“真值为的交集，变元取反”1.7 推理和证明方法定义1.7.1 （逻辑前提、有效结论）：44久和小都是时。如果对于A/ A-A 4r取彳g 1的任何代入，/I也一定取值1,则称是才的逻辑前提，力是山4的有效结论，并记为尸4定理1.7.1