[科普中国]-剩余布尔代数

在数学中，剩余布尔代数是其格结构是布尔代数的剩余格。

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

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

(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. 幂集{\displaystyle 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之外同右剩余一样。

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

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.

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

本词条内容贡献者为:

胡建平 - 副教授 - 西北工业大学