Kleene代数

**克萊尼代數**（名稱源自於美國數學家邏輯學家 史蒂芬・科爾・克萊尼）在數學中是下列兩個事物之一:

* 帶有滿足德・摩根定律和不等式 _x_∧−_x_ ≤ _y_∨−_y_ 的對合 (補) 運算的有界分配格。所以所有布爾代數都是 Kleene 代數，但是多數 Kleene 代數不是布爾代數。如同布爾代數有關於經典命題邏輯，Kleene 代數有關於 Kleene 的三值邏輯。
* 推廣來源自正則表達式的運算的代數結構。本文餘下部分採用這種 Kleene 代數的概念。

## 定義

在文獻中給出了 Kleene 代數和相關結構的各種不等價的定義。總攬可見 [1]。下面給出當代最常用的定義。

Kleene 代數是帶有分別寫為 _a_ + _b_、_ab_ 和 _a_\* 的，兩個二元運算 + : _A_ × _A_ → _A_ 和・ : _A_ × _A_ → _A_，和一個函數 \* : _A_ → _A_ 的集合 _A_，所以滿足下列公理。

* + 和・的結合律: _a_ + (_b_ + _c_) = (_a_ + _b_) + _c_ 和 _a_(_bc_) = (_ab_)_c_ 對於 _A_ 中所有的 _a_, _b_, _c_。
* + 的交換律: _a_ + _b_ = _b_ + _a_ 對於 _A_ 中所有的 _a_, _b_。
* 分配律: _a_(_b_ + _c_) = (_ab_) + (_ac_) 和 (_b_ + _c_)_a_ = (_ba_) + (_ca_) 對於 _A_ 中所有的 _a_, _b_, _c_。
* + 和・的單位元：對於 _A_ 中所有的 _a_ 存在一個 _A_ 中元素 0 使得: _a_ + 0 = 0 + _a_ = _a_。 對於 _A_ 中所有的 _a_ 存在一個 _A_ 中元素 1 使得: _a_1 = 1_a_ = _a_。
* _a_0 = 0_a_ = 0 對於 _A_ 中所有的 _a_。

上述公理定義了一個半環。我們進一步要求:

* + 是等冪的: _a_ + _a_ = _a_ 對於 _A_ 中所有的 _a_。

現在可以定義在 _A_ 上的偏序 ≤，通過設定 _a_ ≤ _b_ 若且唯若 _a_ + _b_ = _b_ (或等價的: _a_ ≤ _b_ 若且唯若 _A_ 存在一個 _x_ 使得 _a_ + _x_ = _b_)。通過這個次序我們可以公式化關於運算 \* 的最後兩個公理:

* 1 + _a_(_a_\*) ≤ _a_\* 對於 _A_ 中所有的 _a_。
* 1 + (_a_\*)_a_ ≤ _a_\* 對於 _A_ 中所有的 _a_。
* 如果 _a_ 和 _x_ 在 _A_ 中使得 _ax_ ≤ _x_，則 _a_\*_x_ ≤ _x_。
* 如果 _a_ 和 _x_ 在 _A_ 中使得 _xa_ ≤ _x_，則 _x_(_a_\*) ≤ _x_。

在直覺上，我們應當把 _a_ + _b_ 當作 "並" 或 _a_ 和 _b_ 的 "最小上界"，和把 _ab_ 當作某種單調性的乘法，在 _a_ ≤ _b_ 蘊涵 _ax_ ≤ _bx_ 的意義上。星號背後的想法是 _a_\* = 1 + _a_ + _aa_ + _aaa_ + ... 從編程理論的觀點，你還可以把 + 解釋所謂 "選擇"，把・解釋為 "順序"，把 \* 解釋為 "重複"。

## 例子

設 Σ 是有限集合 ("字母表") 並設 _A_ 是在 Σ 上所有正則表達式的集合。我們認為兩個正則表達式是相等的，如果它們描述同樣的語言。則 _A_ 形成一個 Kleene 代數。事實上，這是自由 Kleene 代數，在正則表達式上的任何等式都從 Kleene 代數的公理得出，並且因此在所有 Kleene 代數中都是有效的意義上。

再次設 Σ 是字母表。設 _A_ 是在 Σ 上所有正則語言的集合 (或在 Σ 上所有上下文無關語言的集合；或在 Σ 上所有遞歸語言的集合；或在 Σ 上所有語言的集合)。則 _A_ 的兩個元素的併集 (寫為 +) 和串接 (寫為・) 再次屬於 _A_，並且 Kleene 星號運算也適用於 _A_ 的任何元素。我們獲得了 0 為空集而 1 為只包含空字符串的集合的 Kleene 代數 _A_。

設 _M_ 是帶有單位元 _e_ 的么半群，並設 _A_ 是 _M_ 的所有子集的集合。對於兩個這樣的子集 _S_ 和 _T_，設 _S_ + _T_ 是 _S_ 和 _T_ 的併集並設 _ST_ = {_st_ : _s_ ∈ _S_ ∧ _t_ ∈ _T_}。_S_\* 被定義為 _S_ 生成的 _M_ 的子么半群，它可以被描述為 {_e_} ∪ _S_ ∪ _SS_ ∪ _SSS_ ∪ ... 則 _A_ 形成 0 為空集而 1 為 {_e_} 的 Kleene 代數。對任何小範疇都可以進行類似的構造。

假設 _M_ 是一個集合而 _A_ 是在 _M_ 上所有二元關係的集合。採用 + 為並，・為複合，\* 為自反傳遞凸包 (hull)，我們就得到了 Kleene 代數。

帶有運算 ∨ 和 ∧ 的所有布爾代數成為 Kleene 代數，如果我們對 + 使用 ∨，對・使用 ∧，並對所有 _a_ 設立 _a_\* = 1。

在計算權重有向圖中的最短路徑的時候一個非常不同的 Kleene 代數是有用的：設 _A_ 是擴展的實數軸，採用 _a_ + _b_ 為 _a_ 和 _b_ 的最小者，而 _ab_ 是 _a_ 和 _b_ 的普通和 (帶有 +∞ 和 -∞ 的和並定義為 +∞)。_a_\* 被定義對非負 _a_ 為實數零對負 _a_ 為 -∞。這是帶有零元素 +∞ 和一元素是實數零的 Kleene 代數。

## 性質

零是最小元素: 0 ≤ _a_ 對於 _A_ 中所有的 _a_。 

_a_ + _b_ 的和是 _a_ 和 _b_ 的最小上界：我們有 _a_ ≤ _a_ + _b_ 和 _b_ ≤ _a_ + _b_ 並且如果 _x_ 是 _A_ 的一個元素有著 _a_ ≤ _x_ 和 _b_ ≤ _x_，則 _a_ + _b_ ≤ _x_。類似的，_a_1 + ... + _a_n 是元素 _a_1, ..., _a_n 的最小上界。

乘法和加法是單調性的：如果 _a_ ≤ _b_，則 _a_ + _x_ ≤ _b_ + _x_、_ax_ ≤ _bx_ 和 _xa_ ≤ _xb_ 對於 _A_ 中所有的 _x_。 

關於 \* 運算，我們有 0\* = 1 和 1\* = 1，\* 是單調性的 (_a_ ≤ _b_ 蘊涵 _a_\* ≤ _b_\*)，而 _a_n ≤ _a_\* 對於所有自然數 _n_。進一步的，(_a_\*)(_a_\*) = _a_\*、(_a_\*)\* = _a_\* 和 _a_ ≤ _b_\* 若且唯若 _a_\* ≤ _b_\*。

如果 _A_ 是 Kleene 代數而 _n_ 是自然數，則你可以認為集合 Mn(_A_) 由帶有 _A_ 中條目的所有 _n_×_n_ 矩陣構成。使用普通的矩陣加法和乘法概念，你可以定義一個唯一的 \*- 運算，所以 Mn(_A_) 成為一個 Kleene 代數。

## 歷史

Kleene 代數不是 Kleene 定義的；他介入了正則表達式並尋求一個完備的公理集合來允許在正則表達式上的所有等式的推導。首先約翰・何頓・康威在**正則代數**的名義下研究了這個問題。Dexter Kozen 最先證明了 Kleene 代數的公理解決了這個問題。

## 參見

## 引用