剩余布尔代数

数学中,剩余布尔代数是其格结构是布尔代数剩余格。例子包括幺半群乘法选取为合取的布尔代数,在串接运算之下的给定字母表 Σ 的所有形式语言的集合,在关系复合运算之下的给定集合 X 上所有二元关系的集合,和更一般的在关系复合之下的任何等价类的幂集。最初的应用是作为关系代数中二元关系例子的有限公理化推广,但是存在不是关系代数的有趣的剩余布尔代数的例子,比如语言例子。

定义

编辑

剩余布尔代数是代数结构 (L, ∧, ∨, ¬, 0, 1, ·, I, \, /) 使得

(i) (L, ∧, ∨, ·, I, \, /) 是剩余格,而
(ii) (L, ∧, ∨, ¬, 0, 1) 是布尔代数。

更适合关系代数应用的一个等价标识(signature)是 (L, ∧, ∨, ¬, 0, 1, ·, I, ▷, ◁),这里的一元运算 x\ 和 x▷ 是可用如下德·摩根定律的方式相互转换的:

x\y = ¬(x▷¬y),   xy = ¬(xy),

和对偶的为 /y 和 ◁y 使用:

x/y = ¬(¬xy),   xy = ¬(¬x/y),

而在剩余格中的剩余公理因而(替代 z 为 ¬z)改写为

(xz)∧y = 0 ⇔ (x·y)∧z = 0 ⇔ (zy)∧x = 0

这个德·摩根对偶重公式化在下面关于共轭的段落中详细讨论。

因为剩余格和布尔代数都可以用有限多等式定义,剩余布尔代数也是如此,因此它们形成了可有限公理化的一个

例子

编辑

1. 任何布尔代数带有幺半群乘法 · 选取为合取而两个剩余选取为实质蕴涵 xy。在也有可能替代合取作为幺半群乘法的余下 15 个二元布尔运算中,只有五个满足单调性要求,它们是 x·y = 0, x·y = 1, x·y = x, x·y = y, 和 x·y = xy。设置 y = z = 0 于剩余公理 yx\zx·yz 中,得到 0 ≤ x\0 ⇔ x·0 ≤ 0,通过选取 x = 1 它在 x·y = 1、x·y = xx·y = xy 的时候失败。z/y 的对偶自变量排除了 x·y = y。这就只留下了 x·y = 0 (与 xy 无关的常量二元运算),它在剩余都被选取为常量运算 x/y = x\y = 1 的时候满足几乎所有公理。它不能满足的公理是 x·I = x = I·x,因为 I 缺乏一个合适的值。所以合取是作为剩余布尔代数的幺半群乘法的唯一二元布尔运算。

2. 幂集   如平常那样通过 ∩、∪ 和相对于 X2 的补集运算成为布尔代数,并通过关系复合运算成为幺半群。幺半群单位元 I 是恒等关系 {(x,x)|xX}。右剩余 R\S 定义为 x(R\S)y 当且仅当对于所有 X 中的 zzRx 蕴涵 zSy。对偶的左剩余 S/R 定义为 y(S/R)x 当且仅当对于所有 XzxRz 蕴涵 ySz

3. 幂集 2Σ* 如例子 2 那样成为布尔代数,但是幺半群选取为语言串接。这里的集合 Σ 被用做字母表而 Σ* 指示在字母表上的所有有限(包括空串)的字的集合。语言 LM 的串接 LM 构成自所有字 uv 使得 uL 并且 vM。幺半群单位元是只由空字 ε 构成的语言 {ε}。右剩余 M\L 构成自所有在 Σ 上的字 w 使得 MwL。左剩余 L/M 除了 wM 替代了 Mw 之外同右剩余一样。

共轭

编辑

剩余的德·摩根对偶 ▷ 和 ◁ 如下这样引出。在剩余格之中,布尔代数是有补运算 ¬ 的特殊情况。这允许了如下三个不等式的可供替代的表达式

yx\zx·yzxz/y

在使用不相交的两个剩余的公理化中,使用了等价的 xyx∧¬y = 0。 简写 xy = 0 为 x # y 来表达它们的不相交,并把在公理中的 z 代换为 ¬z ,通过一点布尔运算处理它们变成了

¬(xz) # yx·y # z ⇔ ¬(¬z/y) # x

现在 ¬(xz) 让我们想起了德·摩根对偶性,假设 x\ 被认为是一元运算 f,定义为 f(y) = x\y,它有一个德·摩根对偶 ¬fy),这类似于 ∀xφ(x) = ¬∃x¬φ(x)。这个对偶就指示为 x▷,我们定义 xz 为 ¬(xz)。类似的我们定义另一个运算 zy 为 ¬(¬z/y)。通过类比 x\ 作为关联于运算 x· 的剩余运算,我们称呼 x▷ 为 x· 的共轭运算或简称共轭。类似的,◁y 是 ·y 的共轭。不同于剩余的是,共轭是在两个运算之间的等价关系: 如果 fg 的共轭则 g 也是 f 的共轭,就是说,f 的共轭的共轭是 f。共轭的另一个好处是没有必要谈论右和左共轭,这个区别现在继承自 x· 和 ·x 之间的不同,它们有各自的共轭 x▷ 和 ◁x。(但是在 x\ 被选取为对 x· 的剩余运算的时候这个优点同样出现在剩余上。)

所有这些(与布尔代数和幺半群公理一起)生成了下列剩余布尔代数的等价公理化。

xz # yx·y # zzy # x

使用这个表示保持了这个公理化可以表达为有限多等式的情况。

逆反

编辑

在例子 2 和 3 中可以证明 xI = Ix。在例子 2 中两侧都等于 x 的逆反 x ,而在例子 3 中两侧在 x 包含空字的时候都是 I 否则都是 0。在例子 2 情况中 x  = x。对于例子 3 是不可能的因为 xI 几乎没有保留关于 x 的任何信息。所以在例子 2 中我们用 x  代换 xI = x  = Ix 中的 x 并消去得到

x I = x = Ix 

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

上面的消去步骤对于例子 3 是不可能的,因此它不是关系代数,x  唯一确定为 xI

逆反的这个公理化的推论包括 x  = x、 ¬(x ) = (¬x) 、(xy)  = 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.