電腦代數與符號計算

標準形(canonical form)

同一個想法可以披上許多偽裝:1/2、2/4、3/6 是同一個數;x + x 與 2x 是同一個表達式;(x + 1)(x - 1) 與 x^2 - 1 是同一個多項式。若電腦要認出兩個東西相等,先把每一個改寫成一個大家同意的標準形狀,會幫上大忙。標準形正是如此:為每個值選定一個唯一的代表,使得兩個物件相等,當且僅當它們的標準形逐字元完全相同。

其定義性質是唯一性:標準形把一個等價類裡的每個成員都映到同一個代表。對分數而言,標準形是分母為正的最簡分數,所以 2/4、3/6、1/2 全都變成 1/2。對多項式而言,標準形可能是「展開、各項依次數遞減排序」,所以 (x + 1)^2 與 x^2 + 2x + 1 都變成字串 x^2 + 2x + 1。關鍵在於,標準形使相等性檢驗變得無足輕重——直接比較表示法即可。它較弱的表親「正規形」只保證任何等於零的東西被改寫成字面上的 0(足以檢驗是否為零,但不足以給每個值一個唯一的外觀);這兩個詞常被寬鬆地混用,但在理論上區別很重要。

標準形是讓電腦代數系統可靠地化簡、偵測重複、判定相等的安靜機制。它們不只限於代數:史密斯正規形與埃爾米特正規形是整數矩陣的標準形狀,用於精確線性代數。誠實的限制令人清醒:對於足夠豐富的表達式類別(混雜指數、對數、根式),根本不存在可計算的標準形,因為相等性的判定一般而言是不可判定的。那個不可能性就是零等價問題,也正是自動化簡永遠無法完美的原因。

(x + 1)^2 與 x^2 + 2x + 1 是同一個多項式嗎?把兩者都化為標準形「完全展開、各項依次數遞減」:第一個展開成 x^2 + 2x + 1,第二個本就如此。兩個標準形逐位元組完全相同,於是系統回報相等——無需猜測。

一旦兩者都化為標準形,相等性就是字面上的字串比較。

標準形與正規形常被混為一談,但有別:標準形給每個值一個唯一代表;正規形只保證零被送到 0。而對一般表達式,標準形可能根本不存在,這正是零等價問題。

又稱
normal formcanonical representation正規形標準型