剩余布尔代数
维基百科，自由的百科全书
在数学中，剩余布尔代数是其格结构是布尔代数的剩余格。例子包括幺半群乘法选取为合取的布尔代数，在串接运算之下的给定字母表 Σ 的所有形式语言的集合，在关系复合运算之下的给定集合 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.
