群只包含一个二元运算； 环、域等代数结构包含两个二元运算，两个二元运算之间也会有关系。 第七章 其它代数系统 群只包含一个二元运算； 环、域等代数结构包含两个二元运算，两个二元运算之间也会有关系。

1、环 定义7.1： 两个运算分别称为加法和乘法 结合律，无单位元、逆元 -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： 这里是实数 及其加法、乘法 (R,◦)是可换半群

对群，单位元的验证只要对某个元素成立即可 定理7.1： 对群，单位元的验证只要对某个元素成立即可 零元没有逆元

定理7.2： 群一定满足消去律，因此这里的消去律是针对(R,◦)来说的 这里的消去律是排除零元的 零因子：环中，a≠0，b≠0，但a◦b=0，则a为左零因子，b为右零因子 群一定满足消去律，因此这里的消去律是针对(R,◦)来说的 这里的消去律是排除零元的

(S,+)中a的逆元，(S,◦)是半群，无逆元 定义7.4： 定理7.3： (S,+)中a的逆元，(S,◦)是半群，无逆元

定义7.5： 两个运算都 需要考虑

2、理想 定义7.6： 类似于正规子群的条件； 为什么是对运算“◦”：运算“+”是可换的（环的定义）

(I,+,x)的所有理想都是主理想，则(I,+,x)是主理想环

定义7.4: 陪集是定义在群上的，所以考虑的是(D,+)

3、整环 定义7.7： 都是对 (R,◦)来说的 环要求 (R,+)可换， 可换环还要求(R,◦)可换

定理7.5： 定理7.6： 即：对于“◦”的消去律，(D,◦)是半群，本不应该有消去律，这里是因为无零因子

环，即使整环也不能用非零元素除，而域可以 4、域 定义7.8： 2、3点和整环相同 这点和整环不同，整环要求无零因子

注意：其逆定理不成立，即整环不一定是域。 定理7.7： 定理7.8： 注意：其逆定理不成立，即整环不一定是域。 定理7.9： 即：有逆元

多项式环 定义：

(R,+,◦)的零元

定理：

9.1 格的定义与性质 偏序 格 偏序关系：集合L上具有自反性、反对称性和传递性的关系称为集合L上的，记为 ≤ ； 2019/10/23 9.1 格的定义与性质 偏序 偏序关系：集合L上具有自反性、反对称性和传递性的关系称为集合L上的，记为 ≤ ； 偏序集：集合L和偏序关系 ≤ 一起称为偏序集，用（L， ≤ ）来表示； 引入L的子集上的最大下界、最小上界等概念。 格 对于一个偏序集来说，其中的每一对元素不一定都有最大下界或最小上界； 格：每一对元素都有最大下界或最小上界的偏序集。 2019/10/23

格是一个偏序集，其中任意两个元素所构成的子集都有下确界与上确界，也可以称为偏序格。 定义7.9 格是一个偏序集，其中任意两个元素所构成的子集都有下确界与上确界，也可以称为偏序格。 记x,y的上确界为 x ∨ y=lub(x,y)， 下确界为 x ∧ y=glb(x,y) 集合P上的偏序关系≤所构成的偏序集如果是格，可写为(P, ∧, ∨)，若P中元素有限，称为有限格。 2019/10/23

例1. 设n是正整数，Sn是n的正因数的集合，≤为整除关系，则偏序集（Sn，≤）构成格。 证明：对任意的x、y∈Sn，有x∨y是x与y的最小公倍数， x∧y是x与y的最大公约数，且x∨y、x∧y∈Sn，所以（Sn，≤）构成格。 例2. 偏序集（ρ(A)，）是格。 证明：对任意的x、y∈ρ(A)，有： x∨y＝x∪y，x∧y＝x∩y，且x∨y、x∧y∈ρ(A) 所以（ρ(A)，）是格。 2019/10/23

例3. 偏序集（Z，≤）是格。 注意：并不是每个偏序集都是格。 如A＝{2，3，4，6，8，12，36，60}， 证明：对任意的x、y∈Z，有： x∨y＝max(x，y)，x∧y＝min(x，y)， 且它们都是整数，所以（Z，≤）是格。 注意：并不是每个偏序集都是格。 如A＝{2，3，4，6，8，12，36，60}， 对A上的整除关系∨ ，因为8∨12和2 ∨ 3不存在，所以偏序集（A，∨ ）不是格。 2019/10/23

设(P, ∧, ∨)是格，M⊂P且M≠Ø，若(M, ∧, ∨)也构成格，称(M, ∧, ∨)是(P, ∧, ∨)的子格。 说明： 设(P, ∧, ∨)是格，M⊂P且M≠Ø，若(M, ∧, ∨)也构成格，称(M, ∧, ∨)是(P, ∧, ∨)的子格。 (M, ∧, ∨)是(P, ∧, ∨)的子格的充分必要条件是M关于∧, ∨封闭。 2019/10/23

设(P, ∧, ∨)和 (L, ∧, ∨)是两个格，若存在函数f:P→L，使得对任意a,b ∈P，有： 定义7.10： 设(P, ∧, ∨)和 (L, ∧, ∨)是两个格，若存在函数f:P→L，使得对任意a,b ∈P，有： f(a∧b)=f(a) ∧ f(b) f(a∨b)=f(a) ∨ f(b) 则称f为由格P到L的格同态； 如果f是一一对应的，则称它是一个格同构， 或称(P, ∧, ∨)和 (L, ∧, ∨)同构。 2019/10/23

设(P, ∧, ∨) 是格，对任意a,b,c ∈P，有： a ≤a∨b，b≤a∨b a ≤c且b ≤ c ，则a∨b≤c 定理7.10： 设(P, ∧, ∨) 是格，对任意a,b,c ∈P，有： a ≤a∨b，b≤a∨b a ≤c且b ≤ c ，则a∨b≤c a∧b≤a，a∧b≤b c≤a且c≤b，则c≤a∨b 观察上述不等式可以发现：不等式都是有规律地 成对出现，这就是对偶原理。 2019/10/23

格(P, ∧, ∨) 中出现的符号≤、≥、∧、∨分别用≥、≤、∨、∧替换，得到的原式的对偶式。 对偶式： 格(P, ∧, ∨) 中出现的符号≤、≥、∧、∨分别用≥、≤、∨、∧替换，得到的原式的对偶式。 定理7.11（对偶定理） 在格(P, ∧, ∨) 中任何一条定理的对偶式仍是定理。 2019/10/23

定理：设(P, ∧, ∨)是格，则运算∨和∧满足： 交换律：对任意的a、b∈P，有a∨b＝b∨a，a∧b＝b∧a。 结合律：对任意的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。 2019/10/23

因为a∨b和b∨a分别是{a，b}和{b，a}的最小上界， 证明（1） ： 因为a∨b和b∨a分别是{a，b}和{b，a}的最小上界， 因为{a，b}＝{b，a}， 所以a∨b＝b∨a。 由对偶原理，a∧b＝b∧a。 2019/10/23

再由(1)得(a∨b)∨c ≥ a∨(b∨c) 同理可证(a∨b)∨c ≤ a∨(b∨c) 证明（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) 根据偏序关系的反对称性有(a∨b)∨c＝a∨(b∨c)。 由对偶原理有(a∧b)∧c＝a∧(b∧c)。 2019/10/23

(3)显然a ≤ a∨a。又由a ≤ a可得a∨a ≤ a。 根据偏序关系的反对称性有a∨a＝a。 同理可证a∧a＝a。 (4)显然a∨(a∧b) ≤ a，又由a ≥ a和a∧b ≤ a， 可得a∨(a∧b) ≤ a。 根据偏序关系的反对称性有a∨(a∧b)＝a。 同理可证a∧(a∨b)＝a。 2019/10/23

定理7.16 设(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 一个格既有下界又有上界，称为有界格。 2019/10/23

设(P, ∧, ∨)是有界格，则对任意a∈P，有： a∨1=1，a∨0=a；a∧1=a，a∧0=0 定理 7.17 设(P, ∧, ∨)是有界格，则对任意a∈P，有： a∨1=1，a∨0=a；a∧1=a，a∧0=0 其中1和0分别是(P, ∧, ∨)的上界与下界。 说明： 1是(P, ∧, ∨)关于∧的单位元； 0是(P, ∧, ∨)关于∨的单位元； 有限格一定是有界格。 2019/10/23

设(P, ∧, ∨)是有界格，如果对每个a∈P，必有 𝑎 ∈P，且满足：a∨ 𝑎 =1，a∧ 𝑎 =0 定义 7.13 设(P, ∧, ∨)是有界格，如果对每个a∈P，必有 𝑎 ∈P，且满足：a∨ 𝑎 =1，a∧ 𝑎 =0 则称(P, ∧, ∨)是有补格，其中 𝑎 是a的补元素。 说明： 1 =0， 0 =1 。 一个格既是有补格又是分配格，则称为有补分配格。 2019/10/23

设(P, ∧, ∨)是有补分配格，对每个a∈P，它的补元素 𝑎 是唯一的。 定理7.18 设(P, ∧, ∨)是有补分配格，对每个a∈P，它的补元素 𝑎 是唯一的。 定理7.19 设(P, ∧, ∨)是有补分配格，对每个a,b∈P，有： 𝑎∨𝑏 = 𝑎 ∧ 𝑏 𝑎∧𝑏 = 𝑎 ∨ 𝑏 2019/10/23

设（P,+,◦）是代数系统，+和◦是二元运算，如果满足：交换律、结合律和吸收律，则称（P,+,◦）是代数格。 定义7.14 设（P,+,◦）是代数系统，+和◦是二元运算，如果满足：交换律、结合律和吸收律，则称（P,+,◦）是代数格。 定理：一个偏序格必是一个代数格，反之亦然。 2019/10/23

布尔代数 19世纪50年代，英国人乔治.布尔（George Boole） 创造出了一套符号系统，利用符号来表示逻辑中的各种概念。 并且建立了一系列的运算法则，利用代数方法研究逻辑问题，初步奠定了数理逻辑的基础。

定义：一个有补分配格称为布尔代数，可以记为(B,+,◦) 所有可能出现的数只有0和1两个； 基本运算只有“与”、“或”、“非”三种； 在布尔代数中用等式表示命题，把推理过程看作等式的变换。 这种变换只依赖于基本运算的性质。   

布尔代数的性质

逻辑门电路 布尔代数在诞生100多年后，在计算机的发展中找到了它 的用武之地，它为电子数字计算机开关电路设计提供了 最重要的数学方法。 布尔代数在诞生100多年后，在计算机的发展中找到了它 的用武之地，它为电子数字计算机开关电路设计提供了 最重要的数学方法。  1938年，美国数学家、信息论创始人香农(C. Shannon)发 表了著名的论文“继电器和开关电路的符号分析”，首次用 布尔代数进行开关电路分析。 由于布尔代数只有0和1两个值，恰好与二进制数对应， 香农把它运用于以脉冲方式处理信息的继电器开关。并 证明布尔代数的逻辑运算，可以通过继电器电路来实现， 明确地给出了实现加、减、乘、除等运算的电子电路的 设计方法，从而从理论到技术彻底改变了数字电路的设 计方向。      

计算机芯片里使用的逻辑部件，都是由各种布尔 逻辑元件—逻辑门和触发器组成的。 由逻辑元件可以组成各种逻辑网络，这样任何复 杂的逻辑关系都可以由逻辑元件经过相应的组合 来实现。 基于逻辑输入变量，产生逻辑输出结果的电路称 为逻辑门电路 一个门电路由若干个晶体管组成的，但逻辑上仅看作是 一个单元； 一个集成电路由若干个门组成，实现特定逻辑关系的变 换。

三种基本的逻辑门符号：直接对应着其布尔操作（“与”门、“或”门、“非”门）

“异或”门 可以通过基本逻辑门构造出来。

“与非”门 “或非”门

任何逻辑关系都可以仅仅使用“与非”和“或非”两种门电路构成 所以它们称为“全能”门 易生产、造价低

一个逻辑门电路可以有多个输入，至多两个反相输出。

通过逻辑元件构造电路 当电路的输出仅与当前即时输入状态有关时，称为组合逻辑电路； 门电路组合起来可从逻辑上实现表达式的结果。

判断两个线路等价 分配律

电路最小化：降低成本、提高可靠性

根据运算表构造逻辑表达式 输出结果为1的那些组合的逻辑加

一个组合逻辑电路的实例： 半加器，实现两位数字相加并产生 一位进位

利用一个异或门和一个与门实现半加 Sum=𝑥 𝑦 + 𝑥 𝑦=𝑥⊕𝑦 Carry=𝑥𝑦

全加器除了本位和之外，还需要考虑低位来的进位； 全加器真值表：

由真值表直接写出Sum和carry_out表达式…

全加器实现电路 (x⊕y) (x⊕y) carry_in xy

通过半加器构造全加器 x+y+进位 carry_in Sum x carry_out y

用全加器和半加器将两个三位整数相加 x0 s0 进位 y0 s1 x1 进位 y1 s2 x2 c2=s3 y2

把上述全加器连接起来构成串行加法器（波纹进位加法器ripple） 缺点是高位需要等待低位的进位，速度慢

四元数 四元数（Quaternions）是由威廉·卢云·哈密顿（William Rowan Hamilton,1805-1865）在1843年爱尔兰提出的数学概念； 四元数描述刚体的转动； 四元数是复数的不可交换延伸； 如把四元数的集合考虑成多维实数空间的话，四元数就代表着一个四维空间，相对于复数为二维空间。 四元数可用在电脑绘图（及相关的图像分析）上表示三维物件的旋转及方位。

四元数也可以用于控制论、信号处理、姿态控制、物理和轨道力学，都是用来表示旋转和方位。 四元数转换组合比很多矩阵转换组合在数字上更稳定； 四元数可以用于位姿计算和变换，并不断用来解决运动学和动力学的分析和控制问题； 用四元数作为控制信号，不仅容易得到刚体角运动的稳定控制，而且在许多情况下都接近于最优控制。

一个有固定点的刚体通过绕该点的某个轴转过特定角度可达到任何姿态 n 转轴的方向可以表示成一个单位矢量: 则描述该转动的四元数可以表示成: 四元数既反映了转动的方向又反映了转动的幅值.

四元数的表示： λ ----- 标量部分 ---- 矢量部分 包括一个实数单位 1 和三个虚数单位 i, j, k 另一种表示法: λ ----- 标量部分 ---- 矢量部分 包括一个实数单位 1 和三个虚数单位 i, j, k 另一种表示法: , P 代表矢量部分

群旋转 四元数的优点是： 非零四元数的乘法群在R3的实部为零的部分上的共轭作用可以实现转动。 单位四元数（绝对值为1的四元数）若实部为cos(t)，它的共轭作用是一个角度为2t的转动，转轴为虚部的方向。 四元数的优点是： 表达式无奇点（和例如欧拉角之类的表示相比） 比矩阵更简炼（也更快速） 单位四元数的对可以表示四维空间中的一个转动。

四元数的乘法不符合交换律（commutative law）。 四元数是除环（除法环）的一个例子。 除了没有乘法的交换律外，除法环与域是相类的。 乘法的结合律仍旧存在、非零元素仍有唯一的逆元素。 四元数形成一个在实数上的四维结合代数（事实上是除法代数），并包括复数，但不与复数组成结合代数。 四元数（以及实数和复数）都只是有限维的实数结合除法代数。 四元数的不可交换性往往导致一些令人意外的结果，例如四元数的 n-阶多项式能有多于n个不同的根。