剩余布尔代数
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在数学中,剩余布尔代数是其格结构是布尔代数的剩余格。例子包括幺半群乘法选取为合取的布尔代数,在串接运算之下的给定字母表 Σ 的所有形式语言的集合,在关系复合运算之下的给定集合 X 上所有二元关系的集合,和更一般的在关系复合之下的任何等价类的幂集。最初的应用是作为关系代数中二元关系例子的有限公理化推广,但是存在不是关系代数的有趣的剩余布尔代数的例子,比如语言例子。
定义
剩余布尔代数是代数结构 (L, ∧, ∨, ¬, 0, 1, ·, I, \, /) 使得
- (i) (L, ∧, ∨, ·, I, \, /) 是剩余格,而
- (ii) (L, ∧, ∨, ¬, 0, 1) 是布尔代数。
更适合关系代数应用的一个等价标识(signature)是 (L, ∧, ∨, ¬, 0, 1, ·, I, ▷, ◁),这里的一元运算 x\ 和 x▷ 是可用如下德·摩根定律的方式相互转换的:
- x\y = ¬(x▷¬y), x▷y = ¬(x\¬y),
和对偶的为 /y 和 ◁y 使用:
- x/y = ¬(¬x◁y), x◁y = ¬(¬x/y),
而在剩余格中的剩余公理因而(替代 z 为 ¬z)改写为
- (x▷z)∧y = 0 ⇔ (x·y)∧z = 0 ⇔ (z◁y)∧x = 0
这个德·摩根对偶重公式化在下面关于共轭的段落中详细讨论。
因为剩余格和布尔代数都可以用有限多等式定义,剩余布尔代数也是如此,因此它们形成了可有限公理化的一个簇。
例子
1. 任何布尔代数带有幺半群乘法 · 选取为合取而两个剩余选取为实质蕴涵 x→y。在也有可能替代合取作为幺半群乘法的余下 15 个二元布尔运算中,只有五个满足单调性要求,它们是 x·y = 0, x·y = 1, x·y = x, x·y = y, 和 x·y = x∨y。设置 y = z = 0 于剩余公理 y ≤ x\z ⇔ x·y ≤ z 中,得到 0 ≤ x\0 ⇔ x·0 ≤ 0,通过选取 x = 1 它在 x·y = 1、x·y = x 或 x·y = x∨y 的时候失败。z/y 的对偶自变量排除了 x·y = y。这就只留下了 x·y = 0 (与 x 和 y 无关的常量二元运算),它在剩余都被选取为常量运算 x/y = x\y = 1 的时候满足几乎所有公理。它不能满足的公理是 x·I = x = I·x,因为 I 缺乏一个合适的值。所以合取是作为剩余布尔代数的幺半群乘法的唯一二元布尔运算。
2. 幂集 如平常那样通过 ∩、∪ 和相对于 X2 的补集运算成为布尔代数,并通过关系复合运算成为幺半群。幺半群单位元 I 是恒等关系 {(x,x)|x ∈ X}。右剩余 R\S 定义为 x(R\S)y 当且仅当对于所有 X 中的 z,zRx 蕴涵 zSy。对偶的左剩余 S/R 定义为 y(S/R)x 当且仅当对于所有 X 中 z ,xRz 蕴涵 ySz。
3. 幂集 2Σ* 如例子 2 那样成为布尔代数,但是幺半群选取为语言串接。这里的集合 Σ 被用做字母表而 Σ* 指示在字母表上的所有有限(包括空串)的字的集合。语言 L 和 M 的串接 LM 构成自所有字 uv 使得 u ∈ L 并且 v ∈ M。幺半群单位元是只由空字 ε 构成的语言 {ε}。右剩余 M\L 构成自所有在 Σ 上的字 w 使得 Mw ⊆ L。左剩余 L/M 除了 wM 替代了 Mw 之外同右剩余一样。
共轭
剩余的德·摩根对偶 ▷ 和 ◁ 如下这样引出。在剩余格之中,布尔代数是有补运算 ¬ 的特殊情况。这允许了如下三个不等式的可供替代的表达式
- y ≤ x\z ⇔ x·y ≤ z ⇔ x ≤ z/y
在使用不相交的两个剩余的公理化中,使用了等价的 x ≤ y ⇔ x∧¬y = 0。 简写 x∧y = 0 为 x # y 来表达它们的不相交,并把在公理中的 z 代换为 ¬z ,通过一点布尔运算处理它们变成了
- ¬(x\¬z) # y ⇔ x·y # z ⇔ ¬(¬z/y) # x
现在 ¬(x\¬z) 让我们想起了德·摩根对偶性,假设 x\ 被认为是一元运算 f,定义为 f(y) = x\y,它有一个德·摩根对偶 ¬f(¬y),这类似于 ∀xφ(x) = ¬∃x¬φ(x)。这个对偶就指示为 x▷,我们定义 x▷z 为 ¬(x\¬z)。类似的我们定义另一个运算 z◁y 为 ¬(¬z/y)。通过类比 x\ 作为关联于运算 x· 的剩余运算,我们称呼 x▷ 为 x· 的共轭运算或简称共轭。类似的,◁y 是 ·y 的共轭。不同于剩余的是,共轭是在两个运算之间的等价关系: 如果 f 是 g 的共轭则 g 也是 f 的共轭,就是说,f 的共轭的共轭是 f。共轭的另一个好处是没有必要谈论右和左共轭,这个区别现在继承自 x· 和 ·x 之间的不同,它们有各自的共轭 x▷ 和 ◁x。(但是在 x\ 被选取为对 x· 的剩余运算的时候这个优点同样出现在剩余上。)
所有这些(与布尔代数和幺半群公理一起)生成了下列剩余布尔代数的等价公理化。
- x▷z # y ⇔ x·y # z ⇔ z◁y # x
使用这个表示保持了这个公理化可以表达为有限多等式的情况。
逆反
在例子 2 和 3 中可以证明 x▷I = I◁x。在例子 2 中两侧都等于 x 的逆反 x,而在例子 3 中两侧在 x 包含空字的时候都是 I 否则都是 0。在例子 2 情况中 x = x。对于例子 3 是不可能的因为 x▷I 几乎没有保留关于 x 的任何信息。所以在例子 2 中我们用 x 代换 x▷I = x = I◁x 中的 x 并消去得到
- x▷I = x = I◁x。
x = x 可以从这两个方程证明。塔斯基的关系代数概念可以定义有满足这两个等式的一个运算 x 的剩余布尔代数。
上面的消去步骤对于例子 3 是不可能的,因此它不是关系代数,x 唯一确定为 x▷I。
逆反的这个公理化的推论包括 x = x、 ¬(x) = (¬x)、(x∨y) = x∨y 和 (x·y) = y·x。
引用
- Bjarni Jónsson and Constantine Tsinakis, Relation algebras as residuated Boolean algebras, Algebra Universalis, 30 (1993) 469-478.
- Peter Jipsen, Computer aided investigations of relation algebras, Ph.D. Thesis, Vanderbilt University, May 1992.