离散基础及数学 6

1离散数学第八章格与布尔代数回顾半群和独异点的定义及性质半群和独异点的同态与同构积半群群的基本定义与性质置换群和对称群子群与陪集群的同态与同构环与域2/35回顾群的定义群的性质群的基本性质幂运算规则方程存在唯一解消去律元素的阶群的阶Abel群子群的定义子群的判定定理子群的性质生成子群中心C子群的交子群格子群的陪集定义与性质拉格朗日定理3/35回顾循环群定义及性质生成元、n阶循环群、无限循环群置换群定义及性质群的同态与同构群同态映射：单一同态、满同态、群同构映射环的概念与性质域的概念应用：群与网络安全4/35主要内容格的定义及性质格的对偶原理子格分配格、有补格布尔代数5/358.1

格的定义与性质

6/35对偶原理

7/35

8.1

格的定义与性质

8/35格中满足四条运算定律，但等幂律可由吸收律推出，故上述定义只需满足三条运算定律即可。

8.1

格的定义与性质

9/35

8.1

格的定义与性质

10/35

8.1

格的定义与性质

11/35

8.1

格的定义与性质

12/35

8.1

格的定义与性质

13/358.2分配格、有补格与布尔代数

14/358.2分配格、有补格与布尔代数

例8.2.1

图中哪些是分配格，哪些不是分配格？15/358.2分配格、有补格与布尔代数

定义8.2.2若有界格L中，每一个元素都有补元，则称L为有补格。定义8.2.3如果一个格是有补分配格，那么称它为布尔格或布尔代数。16/358.2分配格、有补格与布尔代数

17/358.2分配格、有补格与布尔代数

例8.2.2证明如左图所示的哈塞尔图的格不是一个布尔代数。

18/358.3应用与拓展8.3.1格与数字电路布尔代数在数字电路设计中有重要的应用。在抽象代数中，布尔代数是捕获了集合运算和逻辑运算二者的根本性质的一个代数结构（就是说一组元素和服从定义的公理的在这些元素上运算）。特别是，它处理集合运算交集、并集、补集；和逻辑运算与、或、非。因为真值可以在逻辑电路中表示为二进制数或电平，这种相似性同样扩展到它们，所以布尔代数在电子工程和计算机科学中同在数理逻辑中一样有很多实践应用。在电子工程领域专门化了的布尔代数也叫做逻辑代数，在计算机科学领域专门化了布尔代数也叫做布尔逻辑。19/358.3.1格与数字电路

20/35

21/358.3.1格与数字电路静态分析要在不运行程序的情况下推断程序性质，但程序真实的运行状态空间极其庞大（路径爆炸、循环迭代、递归调用等），因此通常不会直接精确计算，而是选一个抽象域来“近似描述”状态。这个抽象域往往被组织成一个格（lattice）：用偏序⊑表示“信息精确度/包含关系”（更精确的状态包含更少可能性），并设置⊥（不可能状态）和⊤（完全未知）等极值。在AI中，静态分析常用来做两件事：一是作为自动推理/约束验证的基础，帮助规划、漏洞检测、程序验证等任务把“可行/不可行”判断做得更可靠；二是给生成式AI（代码助手、自动修复、Agent）提供安全护栏”。22/358.3.2格与静态分析24/35Meta开源静态分析器Infer:Infer是Meta开源的静态分析工具：输入Java/C/C++/Objective-C代码，它会在不运行程序的前提下报告潜在bug（例如空指针、资源泄漏等）。Infer的静态分析过程大致为：在控制流图上维护一种“抽象程序状态”。这些抽象状态天然能按“信息是否更精确/更强”排成一个偏序；同时在分支合流处需要把不同路径的状态合并（对应格上的join/上界思想），在条件分支处需要把状态收紧（类似meet/过滤/加约束），从而在“抽象状态空间”里推进推理。Infer的经典核心技术之一是分离逻辑+双向溯因：通过推断函数调用所需的前置条件以及不被触及的状态（frame），实现可组合的过程间分析。8.3.2格与静态分析25/35在控制流图上做数据流分析时，遇到分支汇合就用join（⊔）求上确界来合并来自不同路径的抽象信息；遇到条件约束就对抽象状态做“收紧”，常可理解为格上的meet（⊓）或等价的过滤/约束传播。循环和递归会带来“反复更新直到稳定”的过程：分析定义单调的转移函数，在格上迭代寻找不动点；为保证能在有限时间内收敛，工程上常用有限高度格、或引入widening/narrowing等技巧。在上述过程中，格能让分析可以实现“单调传播+迭代到不动点”的方式处理循环或递归：抽象状态沿边传播、遇到回边反复更新，直到达到稳定。最终Infer给出的结论是对真实执行的保守近似：宁可报“可能出错”，也尽量不漏掉确实可能发生的空指针/泄漏路径，这样才能在大规模代码库里持续落地。8.3.2格与静态分析形式概念分析（FCA）是一种用于数据分析和知识发现的数学方法，它通过建立形式上下文（formalcontext）来组织数据，从而揭示数据之间的隐含关系。格与FCA的关系主要体现在如何通过格的结构来组织和推理概念。在FCA中，概念格实际上就是一个格，概念之间的包含关系通过格上的偏序来表示。在分析过程中，FCA利用格的运算（如join、meet）来合并和约束概念，进而发现隐藏在数据中的属性模式或结构层次。概念格为数据的结构化分析提供了一个非常清晰的框架，利用格的性质，FCA能够在多个维度上对数据进行挖掘和总结，揭示出最具意义的关系。26/358.3.3格与形式概念分析在AI中的应用，FCA主要用于知识发现、数据挖掘、可解释机器学习和自动化推理等领域。在知识图谱构建中，FCA被用来从大规模数据集中提取层次化的概念结构，帮助构建更具可解释性的本体。在机器学习中，FCA可以用于特征选择和特征组合的发现，通过概念格识别出最相关的属性组合，从而提升模型的性能和解释性。可视化FCA工具ConceptExplorer:ConceptExplorer是一类用来做FCA的可视化工具：用户把一个“对象–属性”的二元关系表（formalcontext）导入进去，它就能自动生成形式概念（extent=对象集合，intent=属性集合）、构建概念格，并支持你在图上做浏览、筛选、查看上下概念关系、导出结果等操作。27/358.3.3格与形式概念分析以ConceptExplorer为例，格在FCA上的应用为：首先，FCA会把原始数据抽象成一个上下文K=(G,M,I)（对象集G、属性集M、关系I⊆GxM）。ConceptExplorer在导入这张对象-属性表后，会对任意对象子集A⊆G求出A'={m∈M|

g∈A,(g,m)∈I}，对任意属性子集B⊆M

求出B'={g∈G|

m∈B,(g,m)∈I}，进而得到形式概念(A,B)满足A'=B,B'=A。这些概念之间按“包含/蕴含”形成偏序：(A1,B1)≤(A2,B2)

A1⊆A2（等价于B2⊆B1）。ConceptExplorer把这个偏序结构画成概念格，其中“上移”代表对象范围扩大、属性约束变少，“下移”代表对象范围缩小、属性更具体；而上确界/下确界（join/meet）对应FCA中概念的合并与交汇，是“格”结构在FCA里的核心落点。28/358.3.3格与形式概念分析8.4历史人物与事件乔治·布尔（GeorgeBoole）于1815年11月2日出生在英国林肯郡的一个普通家庭。尽管他在贫困环境下长大，但他对知识的渴望和自学能力使他逐渐成为了一位杰出的数学家和逻辑学家。或许在他的时代，布尔的工作并未引起广泛关注，然而他的贡献却深深地影响了数学、逻辑学和计算机科学的发展。通过发展布尔代数，一种基于逻辑运算符的数学体系，布尔为我们构建了现代逻辑思维的基础。这种二值逻辑系统不仅让我们能够评估命题的真假性，更成为了计算机科学和电子工程中的核心概念。28/35布尔在早期的教育中受到了父亲的指导而启发了对知识的探索之心，展现出了非凡的天赋。布尔14岁时就读于林肯镇的一间技校，16岁因家境困窘而缀学。20岁时于林肯镇开办寄宿学校，从事初等教育。边授课边深入地研究当时的数学热点——微分、变分等知识。1844年，布尔凭发表在《伦敦皇家学会学刊》的优秀论文《关于分析的一般方法》荣获英国皇家学会授予数学金质奖章。1847年，布尔出版了他第一本86页的小书《逻辑的数学分析》，建立了逻辑和代数的联系，并由此引进了符号逻辑代数。1849年因在符号逻辑上的贡献而被任命为爱尔兰皇后学院的数学教授。29/358.4历史人物与事件在经历了几年的教授生涯之后，布尔最终著作出版了《思维规律的研究──逻辑与概率的数学理论基础》，开辟了一个全新的数学分支，即包括“布尔代数”和“布尔逻辑”的现代数理逻辑学。布尔在爱尔兰皇后学院任教直至1864年。一天，他冒着暴雨去上课，结果着凉病倒了。他因之犯了急性肺炎，接着又因妻子治疗处理不当，于12月8日不幸病逝，时年49岁。布尔对数学的热情、对学习的专注和教书育人的重视也影响了他的家人，他的子孙也都十分出色，大都成为了学者。其中韩丁、寒春在20世纪40年代受到中国共产党的影响，投身到了建设新中国的事业中，为中国的农业做出许多贡献，被称为“中国人民的好朋友”，“国际友人”。30/358.4历史人物与事件乔治·布尔开创的布尔代数被广泛地应用于数字逻辑电路的分析与设计中。相关产业中，芯片行业芯片是现代经济的命脉，也是从iPhone到吐司机、从数据中心到信用卡等所有电子设备和系统的大脑。半导体是量子计算和人工智能等有望在下个世纪彻底改变生活的创新技术背后的驱动力。从2019年起，美国就已经开始实施对中国的芯片制裁，并频繁更新制裁策略试图打压中国的相关行业发展。华为和中芯国际等中国科技企业尤其受到美国的打压。面对这样的状况，近年来，华为一直在致力于自主研发芯片技术，以减少对外部供应商的依赖并提高自身的竞争力。31/358.4历史人物与事件2020年，华为发布了麒麟9000s芯片，时任美国商务部长雷蒙多在参议院商务委员会的听证会上，表示这可能会对美国的国家安全构成威胁，需要执行更严格的出口管制。而后华为推出的搭载了7纳米麒麟9000s芯片的新款智能手机无疑是对美国商务部制裁有力的回应