离散数学第七章

第七章其它代数系统群只包含一个二元运算；环、域等代数结构包含两个二元运算，两个二元运算之间也会有关系。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为右零因子定义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,◦)可换(R,+)是群，因此无零元，因此不会定义零因子定理7.5：定理7.6：即：对于“◦〞的消去律，(D,◦)是半群，本不应该有消去律，这里是因为无零因子4、域定义7.8：这点和整环不同，整环要求无零因子环，即使整环也不能用非零元素除，而域可以2、3点和整环相同定理7.7：定理7.8：注意：其逆定理不成立，即整环不一定是域。定理7.9：即：有逆元多项式环定义：(R,+,◦)的零元定理：2023/12/319.1格的定义与性质偏序偏序关系：集合L上具有自反性、反对称性和传递性的关系称为集合L上的，记为≤；偏序集：集合L和偏序关系≤一起称为偏序集，用〔L，≤〕来表示；引入L的子集上的最大下界、最小上界等概念。格对于一个偏序集来说，其中的每一对元素不一定都有最大下界或最小上界；格：每一对元素都有最大下界或最小上界的偏序集。2023/12/31定义7.9格是一个偏序集，其中任意两个元素所构成的子集都有下确界与上确界，也可以称为偏序格。 记x,y的上确界为x∨y=lub(x,y)， 下确界为x∧y=glb(x,y)集合P上的偏序关系≤所构成的偏序集如果是格，可写为(P,∧,∨)，假设P中元素有限，称为有限格。2023/12/31例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)，〕是格。2023/12/31例3.偏序集〔Z，≤〕是格。证明：对任意的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，∨〕不是格。2023/12/31

2023/12/31定义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,∧,∨)同构。2023/12/31定理7.10：设(P,∧,∨)是格，对任意a,b,c∈P，有：a≤a∨b，b≤a∨ba≤c且b≤c，那么a∨b≤ca∧b≤a，a∧b≤bc≤a且c≤b，那么c≤a∨b观察上述不等式可以发现：不等式都是有规律地成对出现，这就是对偶原理。2023/12/31对偶式： 格(P,∧,∨)中出现的符号≤、≥、∧、∨分别用≥、≤、∨、∧替换，得到的原式的对偶式。定理7.11〔对偶定理〕 在格(P,∧,∨)中任何一条定理的对偶式仍是定理。2023/12/31定理：设(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。2023/12/31证明〔1〕：因为a∨b和b∨a分别是{a，b}和{b，a}的最小上界，因为{a，b}＝{b，a}，所以a∨b＝b∨a。由对偶原理，a∧b＝b∧a。2023/12/31证明〔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)。2023/12/31(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。2023/12/31定理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一个格既有下界又有上界，称为有界格。2023/12/31定理7.17设(P,∧,∨)是有界格，那么对任意a∈P，有：a∨1=1，a∨0=a；a∧1=a，a∧0=0其中1和0分别是(P,∧,∨)的上界与下界。说明：1是(P,∧,∨)关于∧的单位元；0是(P,∧,∨)关于∨的单位元；有限格一定是有界格。2023/12/31

2023/12/31

2023/12/31定义7.14设〔P,+,◦〕是代数系统，+和◦是二元运算，如果满足：交换律、结合律和吸收律，那么称〔P,+,◦〕是代数格。定理：一个偏序格必是一个代数格，反之亦然。19世纪50年代，英国人乔治.布尔〔GeorgeBoole〕创造出了一套符号系统，利用符号来表示逻辑中的各种概念。并且建立了一系列的运算法那么，利用代数方法研究逻辑问题，初步奠定了数理逻辑的根底。布尔代数定义：一个有补分配格称为布尔代数，可以记为(B,+,◦)

所有可能出现的数只有0和1两个；根本运算只有“与〞、“或〞、“非〞三种；在布尔代数中用等式表示命题，把推理过程看作等式的变换。这种变换只依赖于根本运算的性质。

布尔代数的性质布尔代数在诞生100多年后，在计算机的开展中找到了它的用武之地，它为电子数字计算机开关电路设计提供了最重要的数学方法。

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

45逻辑门电路计算机芯片里使用的逻辑部件，都是由各种布尔逻辑元件—逻辑门和触发器组成的。由逻辑元件可以组成各种逻辑网络，这样任何复杂的逻辑关系都可以由逻辑元件经过相应的组合来实现。基于逻辑输入变量，产生逻辑输出结果的电路称为逻辑门电路一个门电路由假设干个晶体管组成的，但逻辑上仅看作是一个单元；一个集成电路由假设干个门组成，实现特定逻辑关系的变换。46三种根本的逻辑门符号：直接对应着其布尔操作〔“与〞门、“或〞门、“非〞门〕47“异或〞门可以通过根本逻辑门构造出来。48“与非〞门“或非〞门49任何逻辑关系都可以仅仅使用“与非〞和“或非〞两种门电路构成所以它们称为“全能〞门易生产、造价低5051一个逻辑门电路可以有多个输入，至多两个反相输出。当电路的输出仅与当前即时输入状态有关时，称为组合逻辑电路；门电路组合起来可从逻辑上实现表达式的结果。52通过逻辑元件构造电路判断两个线路等价分配律电路最小化：降低本钱、提高可靠性根据运算表构造逻辑表达式输出结果为1的那些组合的逻辑加55一个组合逻辑电路的实例：半加器，实现两位数字相加并产生一位进位56利用一个异或门和一个与门实现半加57

全加器除了本位和之外，还需要考虑低位来的进位；全加器真值表：58由真值表直接写出Sum和carry_out表达式…59全加器实现电路60(x⊕y)carry_in(x⊕y)xy通过半加器构造全加器carry_inxycarry_outSumx+y+进位用全加器和半加器将两个三位整数相加x0y0x1y1x2y2s0s1s2c2=s3进位进位把上述全加器连接起来构成串行加法器〔波纹进位加法器ripple〕63缺点是高位需要等待低位的进位，速度慢

四元数四元数〔Quaternions〕是由威廉·卢云·哈密顿〔WilliamRowanHamilton,1805-1865〕在1843年爱尔兰提出的数学概念；四元数描述刚体的转动；四元数是复数的不可交换延伸；如把四元数的集合考虑成多维实数空间的话，四元数就代表着一个四维空间，相对于复数为二维空间。四元数可用在电脑绘图〔及相关的图像分析〕上表示三维物件的旋转及方位。四元数也可以用于控制论、信号处理、姿态控制、物理和轨道力学，都是用来表示旋转和方位。四元数转换组合比很多矩阵转换组合在数字上更稳定；四元数可以用于位姿计算和变换，并不断用来解决运动学和动力学的分析和控制问题；用四元数作为控制信号，不仅容易得到刚体角运动的稳定控制，而且在许多情况下都接近于最优控制。n一个有固定点的刚体通过绕该点的某个轴转过特定角度可到达任何姿态转轴的方向可以表示成一个单位矢量:那么描述该转动的四元数可以表示成:四元数既反映了转动的方向又反映了转动的幅值.67四元数的表示：λ-----标量局部----矢量部分包括一个实数单位1

和三个虚数单位i,j,k

另一种表示法:,P

代表矢量部分群旋转非零四元数的乘法群在R3的实部为零的局部上的共轭作用可以实现转动。单位四元数〔绝对值为1的四元数〕假设实部为cos(t)，它的共轭作用是一个角度为2t的转动，转轴为虚部的方向。四元数的优点是：表达式