离散数学大概（二）
2018-06-03 本文已影响96人
乘瓠散人
- 设S为集合，函数f: SxS->S称为S上的二元运算，简称为二元运算。验证一个运算是否为集合S上的二元运算主要考虑两点：
- S中任何两个元素都可以进行这种运算，且运算结果是唯一的。
- S中任何两个元素的运算结果都属于S，即S对该运算是封闭的。
如自然数集上的加法和乘法是N上的二元运算，但减法和除法不是。
设S为集合，函数f: S->S称为S上的一个一元运算，简称一元运算。如求一个数的相反数。
- 单位元（幺元）
在自然数集N上，0是加法运算的单位元，1是乘法运算的单位元。 - 零元
在自然数集N上，0是乘法运算的零元，加法运算没有零元。 - 逆元
在整数集合Z上，加法的单位元是0，对于任何整数x，它的加法逆元都存在，是它的相反数-x. 如果x的逆元存在，则称x是可逆的。
对于给定的集合和二元运算来说，逆元和单位元、零元不同，如果单位元或零元存在，一定是唯一的（与运算有关），而逆元能否存在与元素有关，有的元素有逆元，有的元素无逆元，不同的元素对应着不同的逆元。 - 代数系统
非空集合S和S上k个一元或二元运算f1,f2,...fk组成的系统称为一个代数系统，简称代数，记作<S,f1,f2,...,fk> - 同类型的代数系统
如果两个代数系统中运算的个数和对应的元数相同，且代数常数的个数也相同，则称这两个代数系统具有相同的构成成分，也称它们是同类型的代数系统。 - 特殊的代数系统
代数系统V=<S,○>，其中○是一个可结合的二元运算，就代表了一类特殊的代数系统——半群。
代数系统V=<S,○,✲>，其中○和✲是二元运算，并满足交换律、结合律、幂等律和吸收律，就代表了另一类特殊的代数系统——格。 - 子代数
对于任何代数系统，其子代数一定存在。最大的子代数就是V本身，如果令V中所有的代数常数构成的集合是B，且B对V中所有的运算都是封闭的，则B就构成了V的最小子代数。这种最大和最小的子代数称为V的平凡子代数。 - 同态
设V1=<A,○>和V2=<B,*>是同类型的代数系统，f: A->B, 且任意x,y属于A，有 f(x○y) = f(x) * f(y)
则称f是V1到V2的同态映射，简称同态。
根据同态映射的性质可以分为单同态，满同态，同构。f 如果是满射，则称为满同态；如果是单射，则称为单同态；如果是双射，则称为同构。 - 半群和群都是具有一个二元运算的代数系统
设V=<S,○>是代数系统，其中○是一个可结合的二元运算，则称V为半群；
设V=<S,○>是半群，e属于S，e是关于○运算的单位元，则称V是幺半群，也叫做独异点；
设V=<S,○>是独异点，若任意a属于S，a的逆元也属于S，则称V是群，通常记作G. - 平凡群和阿贝尔群
- 若群G是有穷集，则称G是有限群，否则称为无限群。群G的基数称为群G的阶。
- 只含单位元的群称为平凡群。eg.<{0} , +>
- 若群G中的二元运算是可交换的，则称G为交换群或阿贝尔(Abel)群。
- k阶元
设G是群，a属于G，使得等式a^k=e成立的最小正整数k称为a的阶（周期），记作|a|=k，这时也称a为k阶元。若不存在这样的正整数k，则称a为无限阶元 - G为群，则G满足消去律。
- 子群：群的子代数
设G是群，H是G的非空子集，如果H关于G中的运算构成群，则称H为G的子群。
任何群G都存在子群，G和{e}都是G的子群，称为平凡子群。 - 群的中心
设G是群，C是与G中所有元素都可交换的元素构成的集合，称C为G的中心。
对于阿贝尔群，因为G中的所有元素都可以互相交换，G的中心就是G；但是对于某些非交换群，它的中心是{e}. - 循环群
设G是群，a属于G，令H={a^k | k为整数}，即a的所有幂构成的集合，则H是G的子群，称为由a生成的子群，记作<a>.
若存在a属于G，使得G=<a>，则称G为循环群，称a为G的生成元。循环群G根据生成元a的阶数可以分为两类：n阶循环群和无限循环群。 - 设G=<a>是循环群
- 若G是无限循环群，则G只有两个生成元，即a和a^(-1)
- 若G是n阶循环群，则G含有Φ(n)（欧拉函数）个生成元，对于任何小于n且与n互素的自然数r，a^r是G的生成元。
- 环是具有两个二元运算的代数系统。
设<R，+，·>是代数系统，+和·是二元运算，如果满足以下条件：
- <R,+>构成交换群
- <R,·>构成半群
- ·运算关于+运算适合分配律
则称<R，+，·>是一个环
- 格与布尔代数是具有两个二元运算的代数系统
- 设<S, ≤ >是偏序集，如果任意x,y属于S，{x, y}都有最小上界和最大下界，则称S关于偏序≤构成一个格。
格中运算符∧表示最大下界，∨表示最小上界。 - 格的对偶原理：设 f 是含有格中元素以及符号=, ≤, ≥, ∨, ∧等的命题。若 f 对一切格为真，则 f 的对偶命题 f* 也对一切格为真。
- 设<S, ✲, ○>是代数系统，✲和○是二元运算，并且满足交换律、结合律和吸收律，则<S, ✲, ○>构成一个格。
- 设<L, ∧, ∨>是格，S是L的非空子集，若S关于L中的运算∧和∨仍构成格，则称S是L的子格。
- 设<L, ∧, ∨>是格，若任意a,b,c属于L,有
a∧(b∨c) = (a∧b)∨(a∧c)
a∨(b∧c) = (a∨b)∧(a∨c)
成立，则称L为分配格。 - 定理：若L是格，则L是分配格当且仅当L中不含有与钻石格或五角格同构的子格
推论：小于五元的格都是分配格；任何一条链都是分配格； - 设L是格，若L存在全下界（记作0）和全上界（记作1），则称L是有界格，并将L记为<L, ∧, ∧, 0, 1>.
- 设<L, ∧, ∧, 0, 1>是有界格，a属于L, 若存在b属于L, 使得
a∧b=0 和 a∨b=1
则称a和b互为补元。 - 设<L, ∧, ∧, 0, 1>是有界格，若任意a属于L, 在L中都有a的补元存在，则称L是有补格
- 如果一个格是有补分配格，则称它为布尔格或布尔代数
