代數(shù)等式理論的自動定理證明計算機科學導論第一講

1、代數(shù)等式理論的自動定理證明代數(shù)等式理論的自動定理證明計算機科學導論第一講計算機科學導論第一講計算機科學技術(shù)學院計算機科學技術(shù)學院陳意云陳意 http:/ 程程 內(nèi)內(nèi) 容容 課程內(nèi)容課程內(nèi)容圍繞學科理論體系中的模型理論圍繞學科理論體系中的模型理論, 程序理論和計算理論程序理論和計算理論1. 模型理論關(guān)心的問題模型理論關(guān)心的問題 給定模型給定模型M，哪些問題可以由模型，哪些問題可以由模型M解決；如何解決；如何比較模型的表達能力比較模型的表達能力2. 程序理論關(guān)心的問題程序理論關(guān)心的問題 給定模型給定模型M，如何用模型，如何用模型M解決問題解決問題 包括程序設計范型、程

2、序設計語言、程序設計、包括程序設計范型、程序設計語言、程序設計、形式語義、類型論、程序驗證、程序分析等形式語義、類型論、程序驗證、程序分析等3. 計算理論關(guān)心的問題計算理論關(guān)心的問題給定模型給定模型M和一類問題和一類問題, 解決該類問題需多少資源解決該類問題需多少資源本次講座基于中學的等式本次講座基于中學的等式推理推理, ,與這些內(nèi)容關(guān)系不大與這些內(nèi)容關(guān)系不大2課課 程程 內(nèi)內(nèi) 容容 本講座內(nèi)容本講座內(nèi)容 以以代數(shù)等式理論中的定理證明為例，介紹怎樣從代數(shù)等式理論中的定理證明為例，介紹怎樣從中學生熟知的等式演算中學生熟知的等式演算方法方法，構(gòu)造構(gòu)造等式等式定理定理的的自自動證明動證明系統(tǒng)，即將問

3、題變?yōu)橄到y(tǒng)，即將問題變?yōu)榭捎糜嬎銠C求解可用計算機求解 有助于理解計算思維的含義有助于理解計算思維的含義計算思維（譯文）計算思維（譯文） 運用計算機科學的基礎(chǔ)概念進行問題求解、系統(tǒng)運用計算機科學的基礎(chǔ)概念進行問題求解、系統(tǒng)設計、以及人類行為理解等涵蓋計算機科學之廣度設計、以及人類行為理解等涵蓋計算機科學之廣度的一系列思維活動的一系列思維活動3講講 座座 提提 綱綱 基本知識基本知識 代數(shù)項、代數(shù)等式、演繹推理規(guī)則、代數(shù)等式理代數(shù)項、代數(shù)等式、演繹推理規(guī)則、代數(shù)等式理論、等式定理證明方法論、等式定理證明方法 項重寫系統(tǒng)項重寫系統(tǒng) 終止性、良基關(guān)系、合流性、局部合流性、關(guān)鍵終止性、良基關(guān)系、合流性、

4、局部合流性、關(guān)鍵對對 良基歸納法良基歸納法 僅舉例說明僅舉例說明 Knuth-Bendix完備化過程完備化過程 也僅舉例說明也僅舉例說明4基基 本本 知知 識識 代數(shù)項和代數(shù)等式（僅涉及一個類型）代數(shù)項和代數(shù)等式（僅涉及一個類型） 代數(shù)項代數(shù)項例：自然數(shù)類型例：自然數(shù)類型nat 0, 1, 2, : nat常量常量 x, y : nat變量變量 +, f : nat nat nat 二元函數(shù)二元函數(shù) S : nat nat一元的后繼函數(shù)一元的后繼函數(shù) 0, x, x + 1, x + S(y)和和f(100, y) 都是代數(shù)項都是代數(shù)項 代數(shù)等式代數(shù)等式例：例： x + 0 = x，x + S

5、(y) = S(x + y) x + y = z + 55基基 本本 知知 識識 代數(shù)項和代數(shù)等式（代數(shù)項和代數(shù)等式（涉及多個類型涉及多個類型） 例：定義有限表：同類數(shù)據(jù)的有限序列的集合例：定義有限表：同類數(shù)據(jù)的有限序列的集合 6, 17, 50, 28, 188, 92, 30, 67, 15 18.8, 9.2, 50, 77, 8.6, 5.5, 40.0 a, b, c, d, e, f, , z（非數(shù)值數(shù)據(jù)）（非數(shù)值數(shù)據(jù)） 上述數(shù)據(jù)涉及兩個類型上述數(shù)據(jù)涉及兩個類型 序列中元素的類型序列中元素的類型 數(shù)值或非數(shù)值類型數(shù)值或非數(shù)值類型 這些序列所屬的類型，稱為表（這些序列所屬的類型，稱為

6、表（list）類型）類型 非數(shù)值類型非數(shù)值類型 中學所學的代數(shù)概念在此已經(jīng)擴展中學所學的代數(shù)概念在此已經(jīng)擴展6基基 本本 知知 識識 代數(shù)項和代數(shù)等式（代數(shù)項和代數(shù)等式（涉及多個類型涉及多個類型） 代數(shù)項（表代數(shù)項（表類型類型list ，表元類型，表元類型atom） x : atom,l : list 變量變量 nil : list 零元構(gòu)造函數(shù)零元構(gòu)造函數(shù) (常量常量) cons : atom list list 構(gòu)造函數(shù)構(gòu)造函數(shù) first : list atom，rest : list list 觀察函數(shù)觀察函數(shù) nil, cons(x, l), rest(cons(x, nil), r

7、est(cons(x, l), cons(first(l), rest(l)都是代數(shù)項。用都是代數(shù)項。用T 表示項集表示項集 代數(shù)等式代數(shù)等式(方括號列出等式中出現(xiàn)的變量及類型方括號列出等式中出現(xiàn)的變量及類型) first(cons(x, l) = x x : atom, l : list rest(cons(x, l) = l x : atom, l : list7基基 本本 知知 識識 等式證明等式證明例：基于一組等式（公式、公理）：例：基于一組等式（公式、公理）：x + 0 = x 和和 x + S(y) = S(x + y) 怎么證明等式：怎么證明等式：x + S(S(y) = S(S

8、(x + y) ?需要有推理規(guī)則需要有推理規(guī)則8 等式證明的演繹推理規(guī)則等式證明的演繹推理規(guī)則自反公理：自反公理：M M 對稱規(guī)則：對稱規(guī)則：傳遞規(guī)則：傳遞規(guī)則：加變量規(guī)則：加變量規(guī)則：等價代換規(guī)則：等價代換規(guī)則：M = N N = M M = N N = P M = P M = N M = N , x : s M = N , x : s P = Q P/x M = Q/x N 基基 本本 知知 識識x不在不在 中中P , Q 是類型是類型s的項的項9 等式推理的例子等式推理的例子等價代換規(guī)則：等價代換規(guī)則：等式公理：等式公理：x + 0 = x和和x + S(y) = S(x + y)證明等

9、式：證明等式： x + S(S(y) = S(S(x + y)證證明明: x + S(S(y) 根據(jù)根據(jù)x + S(z) = S(x + z)，S(y) = S(y)= S(x + S(y)使用等價代換規(guī)則得到第一個等式使用等價代換規(guī)則得到第一個等式 S(x + S(y) 根據(jù)根據(jù)S(z) = S(z)，x + S(y) = S(x + y)= S(S(x + y) 使用等價代換規(guī)則得到第二個等式使用等價代換規(guī)則得到第二個等式x + S(S(y) = S(S(x + y) 根據(jù)根據(jù)傳遞規(guī)則和上面兩等式傳遞規(guī)則和上面兩等式M = N , x : s P = Q P/x M = Q/x N 基基

10、本本 知知 識識10 等式推理的例子等式推理的例子等價代換規(guī)則：等價代換規(guī)則：等式公理：等式公理：x + 0 = x和和x + S(y) = S(x + y)證明等式：證明等式： x + S(S(y) = S(S(x + y)證明證明: x + S(S(y)= S(x + S(y) 我們的證明演算習慣見左邊我們的證明演算習慣見左邊= S(S(x + y) 它是基于剛才所介紹的演繹推理的它是基于剛才所介紹的演繹推理的若希望計算機來自動推理，嚴格的推理規(guī)則是必若希望計算機來自動推理，嚴格的推理規(guī)則是必須提供的須提供的M = N , x : s P = Q P/x M = Q/x N 基基 本本 知

11、知 識識11基基 本本 知知 識識 代數(shù)等式理論（代數(shù)等式理論（algebraic equation theory）在在項集項集T 上上從一組等式從一組等式E（公理）能推出的公理）能推出的所有等式的集合稱為一個等式理論（通俗的解釋）所有等式的集合稱為一個等式理論（通俗的解釋） 代數(shù)等式理論的定理證明代數(shù)等式理論的定理證明判斷等式判斷等式 M = N 是否在某個代數(shù)等式理論中是否在某個代數(shù)等式理論中 常用證明方法常用證明方法 把把M和和N分別化簡分別化簡, 若它們的最簡形式一樣則相等若它們的最簡形式一樣則相等 分別證明分別證明M和和N都等于都等于L 證明證明M N等于等于0 還有其他方法還有其他

12、方法12基基 本本 知知 識識 哪種證明方法最適合于計算機自動證明？哪種證明方法最適合于計算機自動證明？ 把把M和和N分別化簡分別化簡, 若它們的最簡形式一樣則相等若它們的最簡形式一樣則相等 若基于等式若基于等式E，通過等式證明，把，通過等式證明，把M和和N化簡到化簡到最簡形式，則這種方式相對簡單，便于自動證明最簡形式，則這種方式相對簡單，便于自動證明 并且采用適合于計算機使用的單向并且采用適合于計算機使用的單向重寫規(guī)則重寫規(guī)則 分別證明分別證明M和和N都等于都等于L 自動選擇自動選擇L是非常困難的是非常困難的 證明證明M N等于等于0 不適用于非數(shù)值類型的項，例如先前給出的不適用于非數(shù)值類型

13、的項，例如先前給出的atom類型的表類型的表13項項 重重 寫寫 系系 統(tǒng)統(tǒng) 自動證明要解決的問題自動證明要解決的問題 項集項集T 上上等式集等式集E中的等式要定向為單向項重寫中的等式要定向為單向項重寫規(guī)則規(guī)則, 構(gòu)成構(gòu)成重寫規(guī)則集重寫規(guī)則集R, 以方便計算機對項化簡以方便計算機對項化簡若若E是：是：x + 0 = x，x + S(y) = S(x + y) x 0 = 0，x S(y) = x y + x定向成如下的項重寫系統(tǒng)定向成如下的項重寫系統(tǒng)Rx + 0 x，x + S(y) S(x + y)x 0 0，x S(y) x y + x 記號記號M N：用一條規(guī)則可將項：用一條規(guī)則可將項M

14、歸約成歸約成N 若規(guī)則若規(guī)則LR R，含，含z一次出現(xiàn)的項一次出現(xiàn)的項T，以及使得以及使得SL/zT T的代換的代換S，則，則SL/zT SR/zT “”既用于既用于規(guī)則，也用規(guī)則，也用于項的歸約于項的歸約14項項 重重 寫寫 系系 統(tǒng)統(tǒng) 自動證明要解決的問題自動證明要解決的問題 項集項集T 上上等式集等式集E中的等式要定向為單向項重寫中的等式要定向為單向項重寫規(guī)則規(guī)則, 構(gòu)成重寫規(guī)則集構(gòu)成重寫規(guī)則集R, 以方便計算機對項化簡以方便計算機對項化簡若若E是：是：x + 0 = x，x + S(y) = S(x + y) x 0 = 0，x S(y) = x y + x定向成如下的項重寫系統(tǒng)定向成

15、如下的項重寫系統(tǒng)Rx + 0 x，x + S(y) S(x + y)x 0 0，x S(y) x y + x 記號記號M N：用一條規(guī)則可將項：用一條規(guī)則可將項M歸約成歸約成N 例：例：x + S(S(y)“”既用于既用于規(guī)則，也用規(guī)則，也用于項的歸約于項的歸約15項項 重重 寫寫 系系 統(tǒng)統(tǒng) 自動證明要解決的問題自動證明要解決的問題 項集項集T 上上等式集等式集E中的等式要定向為單向項重寫中的等式要定向為單向項重寫規(guī)則規(guī)則, 構(gòu)成重寫規(guī)則集構(gòu)成重寫規(guī)則集R, 以方便計算機對項化簡以方便計算機對項化簡若若E是：是：x + 0 = x，x + S(y) = S(x + y) x 0 = 0，x

16、S(y) = x y + x定向成如下的項重寫系統(tǒng)定向成如下的項重寫系統(tǒng)Rx + 0 x，x + S(y) S(x + y)x 0 0，x S(y) x y + x 記號記號M N：用一條規(guī)則可將項：用一條規(guī)則可將項M歸約成歸約成N 例：例：x + S(S(y) S(x + S(y) S(x + S(y)/zz S(S(x + y)/zz16代換代換S：xx yS(y)項項 重重 寫寫 系系 統(tǒng)統(tǒng) 自動證明要解決的問題自動證明要解決的問題 項集項集T 上上等式集等式集E中的等式要定向為單向項重寫中的等式要定向為單向項重寫規(guī)則規(guī)則, 構(gòu)成重寫規(guī)則集構(gòu)成重寫規(guī)則集R, 以方便計算機對項化簡以方便計

17、算機對項化簡若若E是：是：x + 0 = x，x + S(y) = S(x + y) x 0 = 0，x S(y) = x y + x定向成如下的項重寫系統(tǒng)定向成如下的項重寫系統(tǒng)Rx + 0 x，x + S(y) S(x + y)x 0 0，x S(y) x y + x 記號記號M N：用一條規(guī)則可將項：用一條規(guī)則可將項M歸約成歸約成N 例：例：x + S(S(y) S(x + S(y) S(S(x + y) 子項能與第子項能與第2條規(guī)則的左部匹配條規(guī)則的左部匹配17項項 重重 寫寫 系系 統(tǒng)統(tǒng) 自動證明要解決的問題自動證明要解決的問題 問題問題1：如何從：如何從E得到得到R，保證項的化簡能保

18、證項的化簡能終止終止例：若有規(guī)則例：若有規(guī)則 x + y = y + x，不管怎么定向都有，不管怎么定向都有 a + b b + a a + b 問題問題2：如何從：如何從E得到得到R，保證對項采用不同化簡，保證對項采用不同化簡策略所得最簡項是唯一的（策略所得最簡項是唯一的（合流性合流性） E： = S( ), Eq(x, x) = true, Eq(x, S(x) = falseR： S( ), Eq(x, x) true, Eq(x, S(x) false18項項 重重 寫寫 系系 統(tǒng)統(tǒng) 自動證明要解決的問題自動證明要解決的問題 問題問題1：如何從：如何從E得到得到R，保證項的化簡能保證項

19、的化簡能終止終止例：若有規(guī)則例：若有規(guī)則 x + y = y + x，不管怎么定向都有，不管怎么定向都有 a + b b + a a + b 問題問題2：如何從：如何從E得到得到R，保證對項采用不同化簡，保證對項采用不同化簡策略所得最簡項是唯一的（策略所得最簡項是唯一的（合流性合流性）R： S( ), Eq(x, x) true, Eq(x, S(x) false則有：則有： Eq( , ) true Eq( , ) Eq( , S( ) false 問題問題3：如何從：如何從E得到得到R, ,使得使得E和和R確定同樣的代確定同樣的代數(shù)理論，即在數(shù)理論，即在E中能證則在中能證則在R中也能證（中

20、也能證（完備性完備性）19項項 重重 寫寫 系系 統(tǒng)統(tǒng) 問題一：終止性問題一：終止性1. 終止性終止性 項集項集T 上的上的R不存在無窮歸約序列不存在無窮歸約序列M0M1M2 , 即即: 任何項都能歸約到范式任何項都能歸約到范式(不能再歸約的項不能再歸約的項)2. 有時很難對等式定向，以得到終止的重寫系統(tǒng)有時很難對等式定向，以得到終止的重寫系統(tǒng)例如：對由三角函數(shù)公式構(gòu)成的等式系統(tǒng)例如：對由三角函數(shù)公式構(gòu)成的等式系統(tǒng) 和角公式和角公式: sin( + ) = sin cos + cos sin , 差角公式差角公式: sin( ) = sin cos cos sin , 積化和差積化和差: si

21、n cos = (sin( + )+sin()/2, 和差化積和差化積: sin +sin = 2sin( + )/2)cos()/2), 20項項 重重 寫寫 系系 統(tǒng)統(tǒng) 問題一：問題一：終止性終止性3. 定義：良基關(guān)系（良基：定義：良基關(guān)系（良基：well-founded）集合集合A上的二元關(guān)系上的二元關(guān)系 是是良基的良基的，若不存在，若不存在A上元上元素的無窮遞減序列素的無窮遞減序列a0 a1 a2 （a b iff b a）例：自然數(shù)上的例：自然數(shù)上的1, 有有 x 規(guī)則規(guī)則2： x, y 1, 有有2(x+y+1) = 2x2y2 2x2y22x24項項 重重 寫寫 系系 統(tǒng)統(tǒng) 問題

22、二：合流性問題二：合流性1. 記號記號 MN：M經(jīng)若干步經(jīng)若干步(含含0步步)重寫后得到重寫后得到N NM：若有：若有MN M N：若存在：若存在P，使得，使得MP且且NP2. 定義定義 令令R是項集是項集T 上的上的重寫系統(tǒng)重寫系統(tǒng), ,若若N M P 蘊涵蘊涵N P，則，則R是是合流合流的的3. 定義定義 令令R是項集是項集T 上的上的重寫系統(tǒng)重寫系統(tǒng), ,若若N M P 蘊涵蘊涵N P，則，則R是是局部局部合流合流的的 局部合流關(guān)系嚴格弱于合流關(guān)系局部合流關(guān)系嚴格弱于合流關(guān)系 先考慮局部合流的判定方法，然后再考慮合流的先考慮局部合流的判定方法，然后再考慮合流的判定方法判定方法25項項 重

23、重 寫寫 系系 統(tǒng)統(tǒng) 插曲插曲在介紹局部合流性之前，先介紹代數(shù)項的樹形表示在介紹局部合流性之前，先介紹代數(shù)項的樹形表示代數(shù)項代數(shù)項cons(first(cons(x, l), rest(cons(y, l)的樹形的樹形表示表示 倒長的樹：根在上，葉在下倒長的樹：根在上，葉在下 每棵子樹代表一個子項，整個樹每棵子樹代表一個子項，整個樹代表完整的代數(shù)項代表完整的代數(shù)項26consconsconsrestfirstyllx項項 重重 寫寫 系系 統(tǒng)統(tǒng) 局部合流性的判定（問題二的子問題）局部合流性的判定（問題二的子問題）1. 討論所選用的例子討論所選用的例子函數(shù)：函數(shù)：nil : listcons :

24、 atom list list first : list atom，rest : list list cond : bool list list list等式：等式： first(cons(x, l) = x, rest(cons(x, l) = l, cons(first(l), rest(l) = l, 下面的討論針對如下兩條重寫規(guī)則：下面的討論針對如下兩條重寫規(guī)則：rest(cons(x, l) lcons(first(l ), rest(l ) l 27項項 重重 寫寫 系系 統(tǒng)統(tǒng) 局部合流性的判定（問題二的子問題）局部合流性的判定（問題二的子問題） (1) 無重疊的歸約無重疊的歸約

25、歸約規(guī)則：歸約規(guī)則： rest(cons(x, l) l （規(guī)則（規(guī)則LR） cons(first(l ), rest(l ) l （規(guī)則（規(guī)則LR ） 待歸約項：待歸約項：cond (B, rest(cons s l), cons(first(l), rest(l) ) 方式方式1: 原式原式 cond(B, l, cons(first(l), rest(l) ) cond(B, l, l) 方式方式2: 原式原式 cond (B, rest(cons s l), l) cond(B, l, l) 特點：特點：M中無重疊子項的歸約相互不受影響中無重疊子項的歸約相互不受影響28項項 重重 寫寫

26、 系系 統(tǒng)統(tǒng) 局部合流性的判定局部合流性的判定 (1) 無重疊的歸約無重疊的歸約圖示：圖示： LR 和和LR 是規(guī)則是規(guī)則 圖中圖中SL和和SR分別表示分別表示 代換代換S作用于作用于L的的 結(jié)果結(jié)果 S : T T 代換代換S的最主要部分的最主要部分是把變量映射到項是把變量映射到項MSLSL MSLSR MSRSR SL MSR29cond (B, rest(cons s l), cons(first(l), rest(l)項項 重重 寫寫 系系 統(tǒng)統(tǒng) 局部合流性的判定（問題二的子問題）局部合流性的判定（問題二的子問題） (2) 平凡的重疊平凡的重疊 歸約規(guī)則：歸約規(guī)則：rest(cons(

27、x, l) l（規(guī)則（規(guī)則LR） cons(first(l ), rest(l ) l （規(guī)則（規(guī)則LR ） 待歸約項：待歸約項： rest(cons(x, cons(first(l), rest(l) 方式方式1: 原式原式 cons(first(l), rest(l) l 方式方式2: 原式原式 rest(cons(x, l) l30項項 重重 寫寫 系系 統(tǒng)統(tǒng) 局部合流性的判定（問題二的子問題）局部合流性的判定（問題二的子問題） (2) 平凡的重疊平凡的重疊 歸約規(guī)則：歸約規(guī)則：rest(cons(x, l) l（規(guī)則（規(guī)則LR） cons(first(l ), rest(l ) l （

28、規(guī)則（規(guī)則LR ） 待歸約項：待歸約項： rest(cons(x, cons(first(l), rest(l) 特點：特點：SL 是是SL的子項的子項，且，且S把把L中的某變量中的某變量(這里是這里是l)用用由由SL 構(gòu)成的項代換構(gòu)成的項代換 不同的第不同的第1步歸約不會影響局部合流，但合流所步歸約不會影響局部合流，但合流所需歸約步數(shù)可能不一樣（取決于需歸約步數(shù)可能不一樣（取決于R中有幾個中有幾個l）31項項 重重 寫寫 系系 統(tǒng)統(tǒng) 局部合流性的判定局部合流性的判定 (2) 平凡的重疊平凡的重疊 圖示：圖示： SL 是是SL的子項的子項，且，且S把把L中的某變量中的某變量x用有用有SL 構(gòu)成

29、的項代換構(gòu)成的項代換 不同的第不同的第1步歸約步歸約不會影響局部合流，不會影響局部合流，但合流所需歸約但合流所需歸約步數(shù)可能不一樣步數(shù)可能不一樣SLSL SLSR SRSL SL SRSR SR 32rest(cons(x, cons(first(l), rest(l)項項 重重 寫寫 系系 統(tǒng)統(tǒng) 局部合流性的判定（問題二的子問題）局部合流性的判定（問題二的子問題）(3) 非平凡的重疊非平凡的重疊 歸約規(guī)則：歸約規(guī)則：rest(cons(x, l) l（規(guī)則（規(guī)則LR） cons(first(l ), rest(l ) l （規(guī)則（規(guī)則LR ） 待歸約項：待歸約項：rest(cons(firs

30、t(l), rest(l) 方式方式1: 原式原式 rest(l)（用規(guī)則（用規(guī)則LR） 方式方式2: 原式原式 rest(l)（用規(guī)則（用規(guī)則LR ） 該例比較特殊，都一步歸約就到范式該例比較特殊，都一步歸約就到范式33項項 重重 寫寫 系系 統(tǒng)統(tǒng) 局部合流性的判定（問題二的子問題）局部合流性的判定（問題二的子問題）(3) 非平凡的重疊非平凡的重疊 歸約規(guī)則：歸約規(guī)則：rest(cons(x, l) l（規(guī)則（規(guī)則LR） cons(first(l ), rest(l ) l （規(guī)則（規(guī)則LR ） 待歸約項：待歸約項：rest(cons(first(l), rest(l) 特點：特點：SL 在

31、在SL的非變量位置的非變量位置LR 或或LR 的使用都可能使的使用都可能使對方在原定位置對方在原定位置 不能使用，故不能保證局部合流不能使用，故不能保證局部合流34項項 重重 寫寫 系系 統(tǒng)統(tǒng) 局部合流性的判定局部合流性的判定(3) 非平凡的重疊非平凡的重疊 圖示：圖示： SL 在在SL的非變量位置的非變量位置 LR或或LR 的使用的使用都可能使都可能使對方在原定對方在原定位置不能使用，故不位置不能使用，故不能保證局部合流能保證局部合流SLSL SLSR SR? 35rest(cons(first(l), rest(l)項項 重重 寫寫 系系 統(tǒng)統(tǒng) 局部合流性的判定局部合流性的判定 若所有含非

32、平凡重疊的項都能局部合流若所有含非平凡重疊的項都能局部合流, 則則R也能也能 把對所有含非平凡重疊的項的檢查縮小為對有限把對所有含非平凡重疊的項的檢查縮小為對有限的重寫規(guī)則集的檢查的重寫規(guī)則集的檢查 若由若由R的重寫規(guī)則確定的所有關(guān)鍵對的重寫規(guī)則確定的所有關(guān)鍵對(critical pair)都能歸約到同一個項，則都能歸約到同一個項，則所有項的非平凡重所有項的非平凡重疊都能局部合流疊都能局部合流（課堂上不介紹（課堂上不介紹） 例：重寫規(guī)則例：重寫規(guī)則rest(cons(x, l) l，和，和 cons(first(l ), rest(l ) l 會形成兩個關(guān)鍵對會形成兩個關(guān)鍵對36項項 重重 寫

33、寫 系系 統(tǒng)統(tǒng)第第1個關(guān)鍵對：個關(guān)鍵對：（課堂上不介紹）（課堂上不介紹） 選適當?shù)拇鷵Q，使得兩規(guī)則代換后綠色選適當?shù)拇鷵Q，使得兩規(guī)則代換后綠色部分一樣部分一樣cons(first(l ), rest(l ) l rest(cons(x, l) l 第第1條規(guī)則中的條規(guī)則中的l 用用cons(x, l)代換后代換后, 其左部是項：其左部是項：cons(first(cons(x, l), (rest(cons(x, l) 用這兩條規(guī)則化簡上述項可得第用這兩條規(guī)則化簡上述項可得第1個關(guān)鍵對：個關(guān)鍵對： cons(x, l), cons(first(cons(x, l), l) 歸約關(guān)鍵對：歸約關(guān)鍵對

34、：cons(x, l)已經(jīng)是范式已經(jīng)是范式 cons(first(cons(x, l), l) cons(x, l) 第第1個關(guān)鍵對能歸約到同一個項個關(guān)鍵對能歸約到同一個項37項項 重重 寫寫 系系 統(tǒng)統(tǒng)第第2個關(guān)鍵對：個關(guān)鍵對：（課堂上不介紹）（課堂上不介紹） 選適當?shù)拇鷵Q，使得兩規(guī)則代換后綠色選適當?shù)拇鷵Q，使得兩規(guī)則代換后綠色部分一樣部分一樣 cons(first(l ), rest(l ) l rest(cons(x, l) l 第第2條規(guī)則中的條規(guī)則中的x和和l分別代換成分別代換成first(l )和和rest(l )后后,其左部是項：其左部是項：rest(cons(first(l )

35、, rest(l ) 用這兩條規(guī)則化簡上述項可得第用這兩條規(guī)則化簡上述項可得第2個關(guān)鍵對：個關(guān)鍵對： rest(l ), rest(l ) 顯然，第顯然，第2個關(guān)鍵對也能歸約到同一個項個關(guān)鍵對也能歸約到同一個項38項項 重重 寫寫 系系 統(tǒng)統(tǒng) 局部合流性的判定局部合流性的判定 定理定理 一個重寫系統(tǒng)一個重寫系統(tǒng)R是局部合流的，當且僅當對是局部合流的，當且僅當對每個關(guān)鍵對每個關(guān)鍵對 M, N 有有M N 如果如果一個有限的重寫系統(tǒng)一個有限的重寫系統(tǒng)R是終止的，那么該定是終止的，那么該定理就給出一個算法，可用于判定理就給出一個算法，可用于判定R是否局部合流是否局部合流39項項 重重 寫寫 系系 統(tǒng)

36、統(tǒng) 局部合流、終止和合流之間的聯(lián)系局部合流、終止和合流之間的聯(lián)系定理定理 令令R是終止的重寫系統(tǒng)，那么是終止的重寫系統(tǒng)，那么R是合流的當是合流的當且僅當它是局部合流的且僅當它是局部合流的 合流蘊含局部合流（這是顯然的）合流蘊含局部合流（這是顯然的） 反方向蘊含的證明需要使用良基歸納法反方向蘊含的證明需要使用良基歸納法40良良 基基 歸歸 納納 法法 良基歸納法良基歸納法用一個簡單例子說明它比自然數(shù)歸納法更一般用一個簡單例子說明它比自然數(shù)歸納法更一般證明：對任何自然數(shù)的有限集合，每次刪除一個元證明：對任何自然數(shù)的有限集合，每次刪除一個元 素，最終會到達空集素，最終會到達空集 1. 若忽略集合中元

37、素的個性，只關(guān)心集合中元素若忽略集合中元素的個性，只關(guān)心集合中元素的個數(shù)，則可以用自然數(shù)歸納法的個數(shù)，則可以用自然數(shù)歸納法 2. 若關(guān)注元素個性（雖無必要）若關(guān)注元素個性（雖無必要） ：集合之間的歸約：集合之間的歸約規(guī)則規(guī)則: x1, , xnx2, , xn其中其中x1是左邊集合的任意元素是左邊集合的任意元素 3.良基關(guān)系：良基關(guān)系：A B則則A B410, 1, 21, 20, 20, 1012良良 基基 歸歸 納納 法法 良基歸納法良基歸納法需要證明：任何自然數(shù)的有限集合可歸約到空集需要證明：任何自然數(shù)的有限集合可歸約到空集1. 對所有的歸約路徑進行歸納對所有的歸約路徑進行歸納2. 良基

38、歸納證明良基歸納證明歸納基礎(chǔ)：歸納基礎(chǔ)：經(jīng)經(jīng)0步歸約到步歸約到歸納假設：對所有的歸納假設：對所有的s s1, s s2, s sn, s1, s2, , sn都能歸約都能歸約到到歸納證明：證明歸納證明：證明s能歸約到能歸約到420, 1, 21, 20, 20, 1012良良 基基 歸歸 納納 法法 良基歸納法良基歸納法（課堂上不介紹）（課堂上不介紹）令令 是集合是集合A上的一個良基關(guān)系，令上的一個良基關(guān)系，令P是是A上的某上的某個性質(zhì)。若每當所有的個性質(zhì)。若每當所有的P(b) (b a)為真則為真則P(a)為真為真(即即 a.( b.(b a P(b) P(a) )，那么，對所有的那么，對所

39、有的a A，P(a)為真為真證明步驟：證明步驟： 歸納基礎(chǔ)歸納基礎(chǔ): 對任意不存在對任意不存在b使得使得b a的的a，證明，證明P(a) 在不存在在不存在b使得使得b a的情況下，的情況下， b.(b a P(b) P(a)等價于等價于 true P(a)等價于等價于 P(a)43良良 基基 歸歸 納納 法法 良基歸納法良基歸納法（課堂上不介紹）（課堂上不介紹）令令 是集合是集合A上的一個良基關(guān)系，令上的一個良基關(guān)系，令P是是A上的某上的某個性質(zhì)。若每當所有的個性質(zhì)。若每當所有的P(b) (b a)為真則為真則P(a)為真為真(即即 a.( b.(b a P(b) P(a) )，那么，對所有的

40、那么，對所有的a A，P(a)為真為真證明步驟：證明步驟： 歸納基礎(chǔ)歸納基礎(chǔ): 對任意不存在對任意不存在b使得使得b a的的a，證明，證明P(a) 歸納步驟：對任意存在歸納步驟：對任意存在b使得使得b a的的a， b.(b a P(b) P(a)在此得出歸納假設：在此得出歸納假設： 假定對所有假定對所有b a的的b，P(b)為真，然后證明：為真，然后證明： 歸納證明：證明歸納證明：證明P(a)為真為真44良良 基基 歸歸 納納 法法 用良基歸納法證明合流性用良基歸納法證明合流性證明：若有證明：若有M N和和 M P，則，則N P若若MN, 則規(guī)定則規(guī)定N M。因系統(tǒng)終止因系統(tǒng)終止, 故故 是良

41、基的是良基的歸納基礎(chǔ)：歸納基礎(chǔ)： 若不存在若不存在N使得使得N M，即即M是范式，顯然是范式，顯然M具有具有要證明的性質(zhì)要證明的性質(zhì) 因為因為M只能只能0步歸約到步歸約到M本身，圖上的本身，圖上的N和和P都只都只能是能是MMNP45(M)(M)M良良 基基 歸歸 納納 法法 用良基歸納法證明合流性用良基歸納法證明合流性證明：若有證明：若有M N和和 M P，則，則N P若若MN, 則規(guī)定則規(guī)定N M。因系統(tǒng)終止因系統(tǒng)終止, 故故 是良基的是良基的歸納步驟：歸納步驟：假定假定M N1 N并且并且M P1 P(1) 根據(jù)局部合流性，根據(jù)局部合流性，存在存在Q，使得，使得N1 Q P1MN1P1NP

42、46良良 基基 歸歸 納納 法法 用良基歸納法證明合流性用良基歸納法證明合流性證明：若有證明：若有M N和和 M P，則，則N P若若MN, 則規(guī)定則規(guī)定N M。因系統(tǒng)終止因系統(tǒng)終止, 故故 是良基的是良基的歸納步驟：歸納步驟： 假定假定M N1 N并且并且M P1 P(1) 根據(jù)局部合流性，根據(jù)局部合流性，存在存在Q，使得，使得N1 Q P1MN1P1QNP47良良 基基 歸歸 納納 法法 用良基歸納法證明合流性用良基歸納法證明合流性證明：若有證明：若有M N和和 M P，則，則N P若若MN, 則規(guī)定則規(guī)定N M。因系統(tǒng)終止因系統(tǒng)終止, 故故 是良基的是良基的歸納步驟：歸納步驟： 假定假定

43、M N1 N并且并且M P1 P(2) 由歸納假設，由歸納假設，存在存在R， 使得使得N R QMN1P1QNP48良良 基基 歸歸 納納 法法 用良基歸納法證明合流性用良基歸納法證明合流性證明：若有證明：若有M N和和 M P，則，則N P若若MN, 則規(guī)定則規(guī)定N M。因系統(tǒng)終止因系統(tǒng)終止, 故故 是良基的是良基的歸納步驟：歸納步驟： 假定假定M N1 N并且并且M P1 P(2) 由歸納假設，由歸納假設，存在存在R， 使得使得N R QMN1P1QNRP49良良 基基 歸歸 納納 法法 用良基歸納法證明合流性用良基歸納法證明合流性證明：若有證明：若有M N和和 M P，則，則N P若若M

44、N, 則規(guī)定則規(guī)定N M。因系統(tǒng)終止因系統(tǒng)終止, 故故 是良基的是良基的歸納步驟：歸納步驟： 假定假定M N1 N并且并且M P1 P(3) 再由歸納假設，再由歸納假設，存在存在S， 使得使得R S PMN1P1QNRP50良良 基基 歸歸 納納 法法 用良基歸納法證明合流性用良基歸納法證明合流性證明：若有證明：若有M N和和 M P，則，則N P若若MN, 則規(guī)定則規(guī)定N M。因系統(tǒng)終止因系統(tǒng)終止, 故故 是良基的是良基的歸納步驟：歸納步驟： 假定假定M N1 N并且并且M P1 P(3) 再由歸納假設，再由歸納假設，存在存在S， 使得使得R S P(4) N P得證得證MN1P1QNRSP

45、51Knuth-Bendix完備化過程完備化過程 問題三：完備性問題三：完備性回顧回顧 最適合于計算機自動證明代數(shù)等式最適合于計算機自動證明代數(shù)等式M=N的方式：的方式： 把把M和和N分別化簡分別化簡, 若它們的最簡形式一樣則相等若它們的最簡形式一樣則相等 由定向代數(shù)等式系統(tǒng)由定向代數(shù)等式系統(tǒng)E來得到等價的重寫系統(tǒng)來得到等價的重寫系統(tǒng)R，需解決三個問題：終止性、合流性和完備性需解決三個問題：終止性、合流性和完備性完備性：從完備性：從E可可得到得到R，E和和R確定同樣的代數(shù)理論確定同樣的代數(shù)理論 概要介紹概要介紹Knuth-Bendix完備化過程完備化過程 給出一個完備化過程不終止的例子。由此可

46、知，給出一個完備化過程不終止的例子。由此可知，并非對任何并非對任何E都都可以得到與之有同樣代數(shù)理論的可以得到與之有同樣代數(shù)理論的R52Knuth-Bendix完備化過程完備化過程 Knuth-Bendix完備化過程的目的完備化過程的目的完備化過程的目的完備化過程的目的 為一個代數(shù)等式系統(tǒng)為一個代數(shù)等式系統(tǒng)E，構(gòu)造一個確定同樣代數(shù)，構(gòu)造一個確定同樣代數(shù)理論的終止且合流的重寫系統(tǒng)理論的終止且合流的重寫系統(tǒng)R53Knuth-Bendix完備化過程完備化過程 Knuth-Bendix完備化過程簡介完備化過程簡介1. 把把E定向成一個終止的重寫系統(tǒng)定向成一個終止的重寫系統(tǒng)R（若定向失敗，則完備化過程失敗

47、）（若定向失敗，則完備化過程失敗）2. 檢查檢查R的局部合流性并進行完備化的局部合流性并進行完備化for(R的每個關(guān)鍵對的每個關(guān)鍵對 M, N ) if (不具備不具備M N) 把把MN或或NM加入加入R（原因稍后解釋）（原因稍后解釋） （若定向失敗，則完備化過程失?。ㄈ舳ㄏ蚴。瑒t完備化過程失?。?(過程可能因過程可能因R不斷地被加入規(guī)則而不終止不斷地被加入規(guī)則而不終止)3. 最終的最終的R為所求為所求54Knuth-Bendix完備化過程完備化過程 例：完備化過程不終止例：完備化過程不終止作為輸入的等式系統(tǒng)作為輸入的等式系統(tǒng)E如下如下f(x) f(y) = f(x + y)(x + y)

48、 + z = x + (y + z)1. 先定向成一個終止的重寫系統(tǒng)先定向成一個終止的重寫系統(tǒng)R f(x) f(y) f(x + y) (x + y) + z x + (y + z)2. 檢查局部合流性并進行完備化檢查局部合流性并進行完備化55Knuth-Bendix完備化過程完備化過程 例：完備化過程不終止例：完備化過程不終止作為輸入的等式系統(tǒng)作為輸入的等式系統(tǒng)E如下如下f(x) f(y) = f(x + y)(x + y) + z = x + (y + z)1. 先定向成一個終止的重寫系統(tǒng)先定向成一個終止的重寫系統(tǒng)R f(x) f(y) f(x + y) (x + y) + z x + (

49、y + z)2. 檢查局部合流性并進行完備化檢查局部合流性并進行完備化(1) 把兩條規(guī)則左部的綠色部分進行合一，把兩條規(guī)則左部的綠色部分進行合一，產(chǎn)生產(chǎn)生一一個個臨界臨界對對 f(x + y) + z, f(x) + (f(y) + z) 臨界對的兩個項都已最簡，這個臨界對不能合流臨界對的兩個項都已最簡，這個臨界對不能合流 因第因第2條規(guī)則左部的合條規(guī)則左部的合一結(jié)果：一結(jié)果： (f(x) f(y) + z 56Knuth-Bendix完備化過程完備化過程 例：完備化過程不終止例：完備化過程不終止作為輸入的等式系統(tǒng)作為輸入的等式系統(tǒng)E如下如下f(x) f(y) = f(x + y)(x + y

50、) + z = x + (y + z)1. 先定向成一個終止的重寫系統(tǒng)先定向成一個終止的重寫系統(tǒng)R f(x) f(y) f(x + y) (x + y) + z x + (y + z)2. 檢查局部合流性并進行完備化檢查局部合流性并進行完備化(1) 把兩條規(guī)則左部的綠色部分進行合一，把兩條規(guī)則左部的綠色部分進行合一，產(chǎn)生產(chǎn)生一一個個臨界臨界對對 f(x + y) + z, f(x) + (f(y) + z) (2) 增加增加重寫規(guī)則重寫規(guī)則f(x + y) + z f(x) + (f(y) + z) 因第因第2條規(guī)則左部的合條規(guī)則左部的合一結(jié)果：一結(jié)果： (f(x) f(y) + z 57Kn

51、uth-Bendix完備化過程完備化過程 例：完備化過程不終止例：完備化過程不終止解釋：增加規(guī)則解釋：增加規(guī)則f(x + y) + z f(x) + (f(y) + z)的原因的原因 在在E中可證中可證f(x + y) + z和和f(x) + (f(y) + z)相等相等等式等式：f(x) f(y) = f(x + y)和和(x + y) + z = x + (y + z) 證明：證明：f(x + y) + z = f(x) f(y) + z = f(x) + (f(y) + z) 在未加上述重寫規(guī)則在未加上述重寫規(guī)則R中證明不了中證明不了, 即即R不不完備完備： 在在R中能證的等式在中能證的

52、等式在E中中能證，但存在能證，但存在E中中能證而能證而在在R中不能證的等式中不能證的等式 向向R中加規(guī)則是為了完備性中加規(guī)則是為了完備性58Knuth-Bendix完備化過程完備化過程 例（續(xù)）例（續(xù)）1. 先定向成一個終止的重寫系統(tǒng)先定向成一個終止的重寫系統(tǒng)R f(x) f(y) f(x + y) (x + y) + z x + (y + z)2. 檢查局部合流性并進行完備化檢查局部合流性并進行完備化(1) 產(chǎn)生一個臨界對產(chǎn)生一個臨界對 f(x + y) + z, f(x) + (f(y) + z) (2) 增加重寫規(guī)則增加重寫規(guī)則f(x + y) + z f(x) + (f(y) + z)(3) R擴大為：擴大為： f(x) f(y) f (x + y) (x + y) + z x + (y + z) f(x + y) + z f(x) + (f(y) + z)59Knuth-Bendix完備化過程完備化過程 例（續(xù)）例（續(xù)）1. 先定向成一個終止的重寫系統(tǒng)先定向成一個終止的重寫系統(tǒng)R