查看“︁剩余布尔代数”︁的源代码

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

==定义==
'''剩余布尔代数'''是代数结构 (''L'', ∧, ∨, ¬, 0, 1, ·, '''I''', \, /) 使得
: (i) (''L'', &and;, &or;, ·, '''I''', \, /) 是[[剩余格]]，而
:(ii) (''L'', &and;, &or;, &not;, 0, 1) 是布尔代数。  

更适合[[关系代数 (抽象代数)|关系代数]]应用的一个等价标识(signature)是 (''L'', ∧, ∨, ¬, 0, 1, ·, '''I''', ▷, ◁)，这里的一元运算 ''x''\ 和 ''x''▷ 是可用如下[[德·摩根定律]]的方式相互转换的：
:''x''\''y'' = &not;(''x''&#9655;&not;''y''), &nbsp; ''x''&#9655;''y'' = &not;(''x''\&not;''y'')，
和对偶的为 /''y'' 和 ◁''y'' 使用：
: ''x''/''y'' = &not;(&not;''x''&#9665;''y''), &nbsp; ''x''&#9665;''y'' = &not;(&not;''x''/''y''),

而在[[剩余格]]中的剩余公理因而(替代 ''z'' 为 ¬''z'')改写为
:(''x''&#9655;''z'')&and;''y'' = 0 &hArr; (''x''·''y'')&and;''z'' = 0 &hArr; (''z''&#9665;''y'')&and;''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. 幂集 <math>2^{X^2}</math> 如平常那样通过 ∩、∪ 和相对于 ''X''<sup>2</sup> 的补集运算成为布尔代数，并通过关系复合运算成为幺半群。幺半群单位元 '''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<sup>Σ*</sup> 如例子 2 那样成为布尔代数，但是幺半群选取为语言串接。这里的集合 Σ 被用做字母表而 Σ* 指示在字母表上的所有有限(包括空串)的字的集合。语言 ''L'' 和 ''M'' 的串接 ''LM'' 构成自所有字 ''uv'' 使得 ''u'' ∈ ''L'' 并且 ''v'' ∈ ''M''。幺半群单位元是只由空字 ε 构成的语言 {ε}。右剩余 ''M''\''L'' 构成自所有在 Σ 上的字 ''w'' 使得 ''Mw'' ⊆ ''L''。左剩余 ''L''/''M'' 除了 ''wM'' 替代了 ''Mw'' 之外同右剩余一样。

==共轭==

剩余的德·摩根对偶 ▷ 和 ◁ 如下这样引出。在剩余格之中，布尔代数是有补运算 ¬ 的特殊情况。这允许了如下三个不等式的可供替代的表达式
:''y'' &le; ''x''\''z'' &hArr; ''x''·''y'' &le; ''z'' &hArr; ''x'' &le; ''z''/''y''

在使用不相交的两个剩余的公理化中，使用了等价的 ''x'' ≤ ''y'' ⇔ ''x''∧¬''y'' = 0。  简写 ''x''∧''y'' = 0 为 ''x'' # ''y'' 来表达它们的不相交，并把在公理中的 ''z'' 代换为 ¬''z'' ，通过一点布尔运算处理它们变成了
:&not;(''x''\&not;''z'') # ''y'' &hArr; ''x''·''y'' # ''z'' &hArr; &not;(&not;''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''&#9655;''z'' # ''y'' &hArr; ''x''·''y'' # ''z'' &hArr; ''z''&#9665;''y'' # ''x''

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

==逆反==

在例子 2 和 3 中可以证明 ''x''▷'''I''' = '''I'''◁''x''。在例子 2 中两侧都等于 ''x'' 的逆反 ''x''<sup><math>\breve{ }</math></sup>，而在例子 3 中两侧在 ''x'' 包含空字的时候都是 '''I''' 否则都是 0。在例子 2 情况中 ''x''<sup><math>\breve{\ }\breve{\ }</math></sup> = ''x''。对于例子 3 是不可能的因为 ''x''▷'''I''' 几乎没有保留关于 ''x'' 的任何信息。所以在例子 2 中我们用 ''x''<sup><math>\breve{ }</math></sup> 代换 ''x''▷'''I''' = ''x''<sup><math>\breve{ }</math></sup> = '''I'''◁''x'' 中的 ''x'' 并消去得到
:''x''<sup><math>\breve{ }</math></sup>&#9655;'''I''' = ''x'' =  '''I'''&#9665;''x''<sup><math>\breve{ }</math></sup>。

''x''<sup><math>\breve{\ }\breve{\ }</math></sup> = ''x'' 可以从这两个方程证明。[[Alfred Tarski|塔斯基]]的'''[[关系代数 (抽象代数)|关系代数]]'''概念可以定义有满足这两个等式的一个运算 ''x''<sup><math>\breve{ }</math></sup> 的剩余布尔代数。

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

逆反的这个公理化的推论包括 ''x''<sup><math>\breve{\ }\breve{\ }</math></sup> = ''x''、 ¬(''x''<sup><math>\breve{\ }</math></sup>) = (¬''x'')<sup><math>\breve{\ }</math></sup>、(''x''∨''y'')<sup><math>\breve{ }</math></sup> = ''x''<sup><math>\breve{ }</math></sup>∨''y''<sup><math>\breve{ }</math></sup> 和 (''x''·''y'')<sup><math>\breve{ }</math></sup> = ''y''<sup><math>\breve{ }</math></sup>·''x''<sup><math>\breve{ }</math></sup>。

== 引用 ==
* 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.

[[Category:布尔代数|S]]
[[Category:格理论|S]]
[[Category:代数逻辑|S]]