代数结构:5、格与布尔代数

16.1 偏序与格

偏序集:设P是集合,P上的二元关系“≤”满足以下三个条件,则称“≤”是P上的偏序关系(或部分序关系)

(1)自反性:a≤a,∀a∈P;

(2)反对称性:∀a,b∈P,若a≤b且b≤a,则a=b;

(3)传递性:∀a,b,c∈P,若a≤b且b≤c,则a≤c;

定义1 格

​ 设 ( L , ⪯ ) (L,\preceq) (L,)为偏序集,如果任意的$a,b\in L 有最小上界与最大下界时,称 有最小上界与最大下界时,称 有最小上界与最大下界时,称L 为 ‘ 格 ‘ ,以 为`格`,以 ,以a\lor b = lub(a,b) ( l e a s t u p p e r b o n d ) 表示 (least upper bond)表示 (leastupperbond)表示a,b 的最小上界, 的最小上界, 的最小上界,a\land b =glb(a,b) ( g r e a t e s t l o w e r b o n d ) 表示 (greatest lower bond)表示 greatestlowerbond)表示a,b$的最大下界。

定义2 覆盖

( L , ⪯ ) (L,\preceq) (L,)为格,如果 a ⪯ b , a ≠ b a\preceq b,a\neq b ab,a=b(记为 a ≺ b a\prec b ab),且不存在 u ∈ L − { a , b } u\in L-\{a,b\} uL{a,b},使 a ≺ u ≺ b a\prec u \prec b aub,则称 a a a覆盖 b b b.

:若 a ≺ b a\prec b ab,如果有 c 1 , ⋯   , c k ∈ L , k ≥ 1 c_1,\cdots,c_k \in L,k\ge 1 c1,,ckL,k1 ,使 c i + 1 c_{i+1} ci+1覆盖 c i ( u i = 1 , 2 , ⋯   , k − 1 ) c_i(ui=1,2,\cdots,k-1) ci(ui=1,2,,k1),且
a = c 1 ≺ c 2 ≺ ⋯ ≺ c k = b a=c_1\prec c_2\prec\cdots\prec c_k = b a=c1c2ck=b
​ 则称 c 1 , ⋯   , c k c_1,\cdots,c_k c1,,ck为连接 a , b a,b a,b的链,如果L中的任意两个元素总有连接它们的链,则称 L L L是离散的。

​ 有限的离散全序集的哈斯图由一条链组成

定义3 完全格

( L ; ≺ ) (L;\prec) (L;)为偏序集,当$\forall A\subseteq L 有最大下界、最小上界时, 有最大下界、最小上界时, 有最大下界、最小上界时,L 显然是格,称为 ‘ 完全格 ‘ , 显然是格,称为`完全格`, 显然是格,称为完全格L 自身的最小上界是整个格 自身的最小上界是整个格 自身的最小上界是整个格L 的最大元,记为 1 ; 的最大元,记为1; 的最大元,记为1L 自身的最小下界为整个格 自身的最小下界为整个格 自身的最小下界为整个格L 的最小元记为 0. 子集 的最小元记为0.子集 的最小元记为0.子集A$可以是有限的,也可以是无限的。

定理1 格的关系运算

( L , ⪯ ) (L,\preceq) (L,)为格,则对任意 a , b ∈ L a,b\in L a,bL

  1. a ≺ a ∨ b , a ∧ b ≺ a a\prec a\lor b ,a\land b \prec a aab,aba
  2. a ⪯ b ⟺ a ∨ b = b a\preceq b \Longleftrightarrow a\lor b =b abab=b
  3. a ⪯ b ⟺ a ∧ b = a a\preceq b \Longleftrightarrow a\land b = a abab=a

画个哈斯图是显然的,或者注意到按照定义,我们有 a ∨ b = l u b ( a , b ) , a ∧ b = g l b ( a , b ) a\lor b=lub(a,b),a\land b = glb(a,b) ab=lub(a,b),ab=glb(a,b),且若 a ⪯ b a\preceq b ab,则 l u b ( a , b ) = b lub(a,b)=b lub(a,b)=b就容易得到了

定理2 格的运算律

  1. 幂等律: a ∧ a = a , a ∨ a = a a\land a = a, a\lor a = a aa=a,aa=a
  2. 交换律: a ∨ b = b ∨ a , a ∧ b = b ∧ a a\lor b=b\lor a,a\land b=b\land a ab=ba,ab=ba
  3. 结合律: a ∨ ( b ∨ c ) = ( a ∨ b ) ∨ c , a ∧ ( b ∧ c ) = ( a ∧ b ) ∧ c a\lor(b\lor c)=(a\lor b )\lor c,a\land(b\land c)=(a\land b)\land c a(bc)=(ab)c,a(bc)=(ab)c
  4. 吸收律: a ∨ ( a ∧ b ) = a , a ∧ ( a ∨ b ) = a a\lor(a\land b)=a,a\land(a\lor b)= a a(ab)=a,a(ab)=a

P211

那么我们可以将 [ L ; ∧ , ∨ ] [L;\land,\lor] [L;,]视为代数系统

引理 1 代数系统L中的等价关系

​ 在 [ L ; ∨ , ∧ ] [L;\lor,\land] [L;,]中二元关系 ∨ , ∧ \lor,\land ,满足上述4条运算律,则 ∀ a , b ∈ L , a ∧ b = a ⟺ a ∨ b = b \forall a,b\in L ,a\land b= a\Longleftrightarrow a\lor b=b a,bL,ab=aab=b

KaTeX parse error: Undefined control sequence: \and at position 38: …row a\lor b =(a\̲a̲n̲d̲ ̲b )\lor b =b(最后一步是吸收律)

a ∨ b = b ⇒ a ∧ b = a ∧ ( a ∨ b ) = a a\lor b =b\Rightarrow a\land b = a\land(a\lor b )=a ab=bab=a(ab)=a

引理2 通过L构造偏序集

​ 在 [ L ; ∧ , ∨ ] [L;\land,\lor] [L;,]中, ∧ , ∨ \land,\lor ,满足4条运算规律,定义关系 ⪯ \preceq 如下: ∀ a , b ∈ L , a ⪯ b \forall a,b \in L ,a\preceq b a,bL,ab,当且仅当 a ∨ b = b a\lor b =b ab=b.则 ( L ; ⪯ ) (L;\preceq) (L;)为偏序集

证明自反性,反对称性,传递性 P211

定理3 引理2中的偏序集是格

证明 a ∨ b = l u b ( a , b ) , a ∧ b = g l b ( a , b ) a\lor b = lub(a,b),a\land b = glb(a,b) ab=lub(a,b),ab=glb(a,b) P211

定义4 格的另一种定义方式

[ L ; ∨ , ∧ ] [L;\lor,\land] [L;,]是一代数系统, ∨ , ∧ \lor,\land ,是定义在 L L L上的二元运算,当其满足 L 1 L_1 L1 L 4 L_4 L4时,称 L L L为格,并称 ∧ \land 为积(交), ∨ \lor 为和(或并)

定理4 保序性

​ 格 [ L ; ∨ , ∧ ] , ∀ a , b , c ∈ L [L;\lor,\land],\forall a,b,c\in L [L;,],a,b,cL,当 b ⪯ c b\preceq c bc时有 a ∧ b ⪯ a ∧ c a\land b \preceq a\land c abac a ∨ b ⪯ a ∨ c a\lor b\preceq a\lor c abac

定义5 子格

[ L ; ∨ , ∧ ] [L;\lor,\land] [L;,]为格, T ≠ ∅ , T ⊆ L T\neq\varnothing,T\subseteq L T=,TL, T T T关于 ∨ , ∧ \lor,\land ,封闭(即 a , b ∈ T , a ∨ b ∈ T , a ∧ b ∈ T a,b\in T,a\lor b \in T,a\land b \in T a,bT,abT,abT)时,称 T T T L L L的子格

​ 注意,当 T T T L L L的子格时, T T T一定是格,但当 T ⊆ L T\subseteq L TL, T T T关于 L L L中的偏序关系 ⪯ \preceq 为格时, T T T不一定是 L L L的子格,因为 T T T中的运算关系可能不同

​ 例如,一个群 G G G的子群全体 S ( G ) S(G) S(G)关于 ⊆ \subseteq 关系所构成的格不是 G G G的幂集关于 ⊆ \subseteq 关系所构成的格的子格,因为子群的并不一定是子群

定义6 格的同态与同构

​ 设 [ L ; ∨ , ∧ ] [L;\lor,\land] [L;,] [ S ; + , ∘ ] [S;+,\circ] [S;+,]为两个格,如果存在映射 φ : L → S , ∀ a , b ∈ L \varphi:L\rightarrow S,\forall a,b\in L φ:LSa,bL,有
φ ( a ∧ b ) = φ ( a ) ∘ φ ( b ) φ ( a ∨ b ) = φ ( a ) + φ ( b ) \varphi(a\land b )=\varphi(a)\circ\varphi(b)\\ \varphi(a\lor b)=\varphi(a)+\varphi(b) φ(ab)=φ(a)φ(b)φ(ab)=φ(a)+φ(b)
​ 则称 φ \varphi φ L L L S S S的同态映射,当 φ ( L ) = S \varphi(L)=S φ(L)=S时(满射),则说两个格同态,当 φ \varphi φ是一一对应(双射),说同构。如果 L = S L=S L=S,则称为自同态和自同构。

定理 5 同态映射是保序的

​ 若 φ \varphi φ是格 L , S L,S L,S间的同态映射,则 φ \varphi φ是同态映射,即 ∀ a , b ∈ L \forall a,b\in L a,bL,若 a ⪯ b a\preceq b ab,则 φ ( a ) ⪯ φ ( b ) \varphi(a)\preceq\varphi(b) φ(a)φ(b)注意不是当且仅当

定理6 同构映射的保序性

a ⪯ b ⟺ φ ( a ) ⪯ φ ( b ) a\preceq b \Longleftrightarrow \varphi(a)\preceq\varphi(b) abφ(a)φ(b)

定理7 对偶原理

  1. P P P是对任意偏序集都为真的一个命题, P ′ P' P是将 P P P中所有 ⪯ , ⪰ \preceq,\succeq ,对换得到的对偶命题,则 P ′ P' P对任意偏序集也为真
  2. P P P是从格 [ B ; ∨ , ∧ ] [B;\lor,\land] [B;,]推出的命题, P ′ P' P是将 P P P ∨ \lor ∧ \land 对换得到的对偶命题,则 P ′ P' P对格 [ B ; ∧ , ∨ ] [B;\land,\lor] [B;,]也为真

偏序反转后,自然从P得到了P‘

16.2 有补格及分配格

定义7 有界格

​ 一个具有最大元1和最小元0的格 [ L ; ∨ , ∧ ] [L;\lor,\land] [L;,]称为有界格

定理8 最大元和最小元的性质

​ 有界格中, ∀ a ∈ L : a ∨ 1 = 1 , a ∧ 0 = 0 , a ∧ 1 = a , a ∨ 0 = a \forall a\in L:a\lor 1 =1,a\land 0 =0,a\land 1 =a,a\lor 0 =a aL:a1=1,a0=0,a1=a,a0=a

定义8 有补格

[ L ; ∨ , ∧ ] [L;\lor,\land] [L;,]为有界格,$\forall a \in L , 若 ,若 ,\exist b\in L , 有 ,有 ,a\lor b =1,a\land b =0 ,则称 ,则称 ,则称b 为 为 a 的 ‘ 补元 ‘ , 记 的`补元`,记 补元,b 为 为 a’ . 若 .若 .L 中的每个元有补元,称 中的每个元有补元,称 中的每个元有补元,称L$为有补格

我们可以发现,对任意格成立分配不等式,即格 [ L ; ∨ , ∧ ] [L;\lor,\land] [L;,]中任意 a , b , c ∈ L a,b,c\in L a,b,cL,有:

  1. a ∨ ( b ∧ c ) ⪯ ( a ∨ b ) ∧ ( a ∨ c ) a\lor (b\land c)\preceq (a\lor b)\land(a\lor c) a(bc)(ab)(ac)
  2. KaTeX parse error: Undefined control sequence: \and at position 34: …and c)\preceq a\̲a̲n̲d̲(b\lor c)

怎么说了,这个不等关系很容易记反,就画哈斯图吧

定义9 分配格

我们可以发现,对任意格成立分配不等式,即格 [ L ; ∨ , ∧ ] [L;\lor,\land] [L;,]中任意 a , b , c ∈ L a,b,c\in L a,b,cL,有:

  1. a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c ) a\lor (b\land c)= (a\lor b)\land(a\lor c) a(bc)=(ab)(ac)
  2. KaTeX parse error: Undefined control sequence: \and at position 28: …or(a\land c)= a\̲a̲n̲d̲(b\lor c)

则称格L为分配格

两个典型的非分配格

在这里插入图片描述

​ 只要哈斯图中含有这种子结构,就可以判断它不是分配格

定理9 分配格的判断

[ L ; ∨ , ∧ ] [L;\lor,\land] [L;,]为任意格,则下述条件等价

  1. ∀ a , b , c ∈ L , a ∧ ( b ∨ c ) = ( a ∧ b ) ∨ ( a ∧ c ) \forall a,b,c\in L,a\land(b\lor c)=(a\land b)\lor(a\land c) a,b,cL,a(bc)=(ab)(ac)
  2. ∀ a , b , c ∈ L , a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c ) \forall a,b,c\in L,a\lor(b\land c)=(a\lor b)\land(a\lor c) a,b,cL,a(bc)=(ab)(ac)
  3. ∀ a , b , c ∈ L , ( a ∧ b ) ∨ ( b ∧ c ) ∨ ( c ∧ a ) = ( a ∨ b ) ∧ ( b ∨ c ) ∧ ( c ∨ a ) \forall a,b,c\in L,(a\land b)\lor (b\land c)\lor(c\land a)=(a\lor b)\land(b\lor c)\land(c\lor a) a,b,cL,(ab)(bc)(ca)=(ab)(bc)(ca)
  4. 不含 M 5 M_5 M5 N 5 N_5 N5同构的子格

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/617755.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【刷题篇】滑动窗口(二)

文章目录 1、水果成篮2、找到字符串中所有字母异位词3、串联所有单词的子串4、最小覆盖子串 1、水果成篮 你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。 你想要尽可能多…

景源畅信:抖音小店的商品怎么同步到橱窗?

在数字营销的海洋中,抖音小店与橱窗的同步操作无疑是商家们关注的焦点。这不仅能增加商品的曝光度,还能提高交易的可能性。那么,如何将抖音小店的商品同步到橱窗呢? 一、核心步骤解析 要实现商品从抖音小店同步到橱窗,你需要确保…

程序员工作中常见问题,你遇到过几个?

在赛博朋克2077玩后感中,我提到,即便是在严谨的机制下,依然可能出现让人匪夷所思或是贻笑大方的问题。 那么今天,就以后端程序员的视角,盘点下从设计开发到上线的常见问题,看看大家中过几个。 01 设计与开…

栈和队列讲解

文章目录 栈栈的实现栈的初始化压栈出栈获取栈顶元素获取栈内有效元素个数检查是否为空销毁栈栈的使用 栈全部代码队列的初始化队尾入队列队头出队列获取队列头部元素获取队列队尾元素获取队列中有效元素个数检测队列是否为空,如果为空返回非零结果,如果…

Java设计模式-工厂

Java设计模式中,工厂模式主要包括普通工厂模式以及抽象工厂模式,普通工厂模式是用于制造输出不同类型的对象,抽象工厂模式是用于制造输出不同类型的普通工厂,本文主要描述工厂模式的基本用法。 如上所示,使用普通工厂模…

HCIP(BGP综合实验)--8

一:实验要求 二:实现过程 (一)配置IP地址: AR1: [AR1]int g0/0/0 [AR1-GigabitEthernet0/0/0]ip add 12.1.1.1 24 [AR1-GigabitEthernet0/0/0]int l0 [AR1-LoopBack0]ip add 172.16.0.1 32 [AR1-LoopBack0]int l1 […

C++异常详解

文章目录 前言一、回顾C语言二、异常的概念三、异常的使用1.异常的抛出和捕获2.异常的重新捕获 三.异常安全与异常规范1.异常安全2.异常规范 四.自定义异常体系五.C标准库的异常体系六.异常优缺点练习题总结 前言 在本篇文章中,我们将会详细介绍一下有关C异常的讲解…

Redis数据结构扩容源码分析

1 Redis数据结构 redis的数据存储在dict.中,其数据结构为(c源码) ypedef struct dict { dictType *type; //理解为面向对象思想,为支持不同的数据类型对应dictType抽象方法,不同的数据类型可以不同实现 void *privdata; //也可不同的数据类…

C++中vector的简单实现

文章目录 一、主要任务1. 查看文档的网站的链接2.内部模拟的函数 二、本人的模拟实现过程1. 所需模拟实现的函数a.构造、拷贝构造b. reverse()扩容c.insert()、push_back()插入数据d. erase()、pop_back()删除数据e. swap()交换f. begin()、end()非const与const迭代器g. 完善构…

【ARM 嵌入式 C 入门及渐进 16.1 -- C 代码实现CRC32校验函数】

请阅读【嵌入式开发学习必备专栏】 文章目录 CRC32校验函数CRC32 表与函数CRC32 测试函数测试结果 对比测试结果 CRC32校验函数 在C语言中,实现CRC32计算的函数需要一个CRC算法的实现。以下是一个使用查表法实现CRC32的简单例子。这种方法通过预先计算好的CRC表来快…

六级翻译笔记

理解加表达 除了专有名词不能自己理解翻译,其它都可以 时态一般唯一 题目里出现有翻译为 客观存在: there be 单词结尾加er和ee的区别:er是主动,ee是被动 中文句子没有被动,也可以英文翻译为被动 中文的状语可以不是…

python代码实现TF-IDF

1、TF-IDF解释 TF-IDF(Term frequency–inverse document frequency),中文翻译就是词频 - 逆文档频率,是一种用来计算关键词的传统方法。 TF(Term Frequency):TF 的意思就是词频,是…

图片批量管理迈入智能新时代:一键输入关键词,自动生成并保存惊艳图片,轻松开启创意之旅!

在数字化时代,图片已成为我们表达创意、记录生活、传递信息的重要工具。然而,随着图片数量的不断增加,如何高效、便捷地管理这些图片,却成为了一个令人头疼的问题。 第一步,进入首助编辑高手主页面,在上方…

Vagrant + docker搭建Jenkins 部署环境

有人问,为什么要用Jenkins?我说下我以前开发的痛点,在一些中小型企业,每次开发一个项目完成后,需要打包部署,可能没有专门的运维人员,只能开发人员去把项目打成一个war包,可能这个项…

(动画详解)LeetCode面试题 02.04.分割链表

💖💖💖欢迎来到我的博客,我是anmory💖💖💖 又和大家见面了 欢迎来到动画详解LeetCode系列 用通俗易懂的动画的动画使leetcode算法题可视化 先来自我推荐一波 个人网站欢迎访问以及捐款 推荐阅读…

3D 生成重建010-SyncDreamer从单视图生成一致性的多视图

3D 生成重建010-SyncDreamer从单视图生成一致性的多视图 文章目录 0论文工作1论文方法2 效果 0论文工作 在zero123中,首先探索了给2d图像扩散模型注3d空间感知能力。可以将原图输入模型,通过相机位置的相对偏移生成对应的新视图。 这篇论文就是在zero1…

PAD如何实现在用RJ45上网的同时还能保证PAD的续航?|边充电边上网

在数字化时代,手机已经成为我们生活、工作的得力助手。当提及手机边上网边充电时,或许您会想:“这不是常态吗?”但今天,我们要探讨的是一个更为特殊而重要的场景——有线网络直连手机。对于那些需要稳定网络连接、不能…

51输出周期为40ms的方波(C+汇编)

题目 已知Fosc12MHz,T1工作于方式1, ①:实现20ms延时,求定时器初值TH0?TL0?写出具体的计算过程。 ②:利用汇编或C语言编程实现输出周期为40ms的方波。 周期为40ms的方波,半周期就…

weblogic 反序列化 CVE-2018-2628

这个漏洞因为java版本问题一直下载不了ysoserial反序列化工具,没办法生成payload。这里记录一下漏洞原理。 一、漏洞简介 Weblogic Server中的RMI 通信使用T3协议在Weblogic Server和其它Java程序(客户端或者其它Weblogic Server实例)之间传…

四川景源畅信:小白做抖音电商怎么样?

在数字时代,抖音已成为一个不可忽视的电商平台。对于初入行的小白来说,涉足抖音电商似乎既充满机遇又伴随着挑战。要判断小白做抖音电商的可行性,我们不妨从几个关键方面进行深入探讨。 一、市场趋势与流量获取 抖音作为新媒体的代表之一&…