剩余布尔代数

在数学中，剩余布尔代数是其格结构是布尔代数的剩余格。例子包括幺半群乘法选取为合取的布尔代数，在串接运算之下的给定字母表 Σ 的所有形式语言的集合，在关系复合运算之下的给定集合 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. 幂集 $2^{X^{2}}$ 如平常那样通过 ∩、∪ 和相对于 X² 的补集运算成为布尔代数，并通过关系复合运算成为幺半群。幺半群单位元 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^{${\breve {}}$}，而在例子 3 中两侧在 x 包含空字的时候都是 I 否则都是 0。在例子 2 情况中 x^{${\breve {\ }}{\breve {\ }}$} = x。对于例子 3 是不可能的因为 x▷I 几乎没有保留关于 x 的任何信息。所以在例子 2 中我们用 x^{${\breve {}}$} 代换 x▷I = x^{${\breve {}}$} = I◁x 中的 x 并消去得到

x^{${\breve {}}$}▷I = x = I◁x^{${\breve {}}$}。

x^{${\breve {\ }}{\breve {\ }}$} = x 可以从这两个方程证明。塔斯基的关系代数概念可以定义有满足这两个等式的一个运算 x^{${\breve {}}$} 的剩余布尔代数。

上面的消去步骤对于例子 3 是不可能的，因此它不是关系代数，x^{${\breve {}}$} 唯一确定为 x▷I。

逆反的这个公理化的推论包括 x^{${\breve {\ }}{\breve {\ }}$} = x、 ¬(x^{${\breve {\ }}$}) = (¬x)^{${\breve {\ }}$}、(x∨y)^{${\breve {}}$} = x^{${\breve {}}$}∨y^{${\breve {}}$} 和 (x·y)^{${\breve {}}$} = y^{${\breve {}}$}·x^{${\breve {}}$}。

引用

• 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.