英文翻譯 自動化

編號：自動化1介紹自動化可能是成功的機械化的關(guān)鍵。在一些情形中，機械化不需要自動化就可以實行。確實，在高度抽象的數(shù)學(xué)區(qū)域，大部分由使用者拼出的復(fù)雜證明組成的機械化推論遠遠超過了那些目前能被自動化解決的范圍。在這一背景下，如果自動化它被全部使用，將指導(dǎo)在容易的可以解決的被緊緊地限定的次問題上。一個機械化的典型例子是我們的拉姆齊定理的形式化。另一方面，在推論相對被限制的地方，自動化能富有成效地在確認類型的證明中被應(yīng)用，但是絕對程度的細節(jié)將使一個非自動化的機械化不可實行。許多人已經(jīng)花費了數(shù)年來發(fā)展全自動系統(tǒng)。比如Vampire[VR]和otter[McC]全自動系統(tǒng)。我們可以和這樣的系統(tǒng)競爭的設(shè)想是愚蠢的。它們的執(zhí)行是一種方式，這種方式超過目前在交互式定理證明器被實行的系統(tǒng)。這些計劃正在進行是為了把這些系統(tǒng)和交互式定理證明器相連。這是極其有價值的工作：如果知道一個一階的陳述是可證明的，這時應(yīng)該期待機器能提供一個證明。在這一節(jié)中，我們簡略說明一些我們已經(jīng)在各種不同的情況應(yīng)用研究的技術(shù)。自然地我們不企圖僅此一次去解決自動化推論的問題。寧可我們把重心集中在問題，而這些問題典型地出現(xiàn)在我們已經(jīng)涉及的研究。我們首先簡略說明我們需要的自動化的引擎功能。我們?nèi)缓竺枋鑫覀儜?yīng)用的技術(shù)，而且他們是如何整合的。我們評估根據(jù)我們的需求性質(zhì)上地產(chǎn)生的引擎，和數(shù)量地有關(guān)于一件相當大的案例研究。這些技術(shù)中的少數(shù)是新奇的，寧可，我們企圖用一種適宜的方式來融合現(xiàn)行的技術(shù)。這些步驟在HOL啟發(fā)定理證明器被發(fā)展，這是我們建立的設(shè)計原型的一輛優(yōu)良車輛的不同方法。2需求我們的自動化的需求是什么?讓我們區(qū)別一下自動化和全自動化的使用，以及交互式自動化的使用，每一種的需求都有非常地不同。也許料想不到地，失敗的自動化證明引擎是基準，是觀念，這觀念是當交互式發(fā)展的復(fù)雜證明使我們花費大多數(shù)時間對"幾乎"的可證明的義務(wù)的時候。因此我們想要證明器給我們完美的反饋作為為什么任務(wù)不能夠被執(zhí)行的原因。這引證強調(diào)一種在自動化和交互式證明之間的重要的不同。在自動校對中，可典型地知道，目標是可證明的(或至少，非常強烈地懷疑，而且在結(jié)束相當多量的時間之前準備等候證明的搜尋)。的確，自動證明器被判斷在他們能實際上證明多少可證明的目標之上。在交互式證明中，"我們花費我們大多數(shù)的時間在幾乎可證明的義務(wù)上"。這是交互式和證明之間的不同。如果我們花費大部份的時間嘗試去證明簡單但不可證實的目標，然后校正的搜尋完全變成比較不重要。這雖不能說是它全部失去重要:：如果一個系統(tǒng)缺乏完整性，這時它將會無法證明一些可證明的目標。什么類型的目標正在被放棄，這是非常必要而且主要去知道的，這是為了知道當一個證明器失敗于證明一個目標時就能理解它是什么意思。這些知識也非常有用，當混合系統(tǒng)為了了解作為整個系統(tǒng)的行為，應(yīng)當首先了解部分的行為。在一個交互式的環(huán)境中，在完全之上所有物可能被偏愛，就我們而言，自動化的最重要方面是簡單化。而這些我們不是意味著去落實簡單(要布多少根線來實現(xiàn)系統(tǒng)?等等)，而是概念上的簡單化。例如，簡單化到處被用于交互式定理求證。如果一組改寫規(guī)則不能融合，這時去了解簡化器的行為，必須了解適用的規(guī)則順序。不用說，對于理解這是一件極端復(fù)雜的事情，而且屬于這些所有物的證明在推測上極端易碎。概念上的簡單化通過聚集和簡易裝置的終端對一個簡化器進行緊密地約束。如果一個使用者要了解系統(tǒng)，概念上的簡單化很重要。如果一個系統(tǒng)的概念簡單，它將會很有希望被簡單的使用。在一個交互式環(huán)境中，我們期待自動化失敗。為了取得進步，我們必須了解一種證明的嘗試為什么失敗，證明器一定會提供反饋?；谙到y(tǒng)的決議能提供反饋，但是他們是毀滅性的(在某種意義上目標轉(zhuǎn)換成一種正常的形式在證明的嘗試之前開始，破壞了最初的邏輯結(jié)構(gòu))，所以反饋很難被了解(論證失敗的點對于最初的目標能看出明顯的不同)。較好的方式是引導(dǎo)在一個盡可能接近的方法證明到一個人類可能如何引導(dǎo)證明。在一些感覺中我們需要證明的系統(tǒng)應(yīng)該是自然的。在這情況下，如果一種證明的嘗試失敗，失敗的部分能時常被作為檢驗直接地返回給使用者。反饋與能見度相關(guān)。時常一個使用者希望檢查失敗的證明，但是只有證明的蹤跡是可得的，它能引起一個概念上的錯誤結(jié)合:使用者把重心集中在結(jié)果，然而蹤跡可能全部是有不同的自然。如果有許多沒有被證明的部分，這時一個使用者不可能檢查它們的全部，但是可能愿意沿著證明走。像約翰哈里森的模式消除的執(zhí)行的自動化方法，時常利用全球化的節(jié)點優(yōu)先尋址的信息在一棵樹里搜尋一個證明。如果全球化的信息不是出現(xiàn)在結(jié)果中使用者有機會接近，它將會難以經(jīng)過通過簡單運用的自動證明器一步一次的自動化證明。當傳導(dǎo)的搜尋正在使用全球化的信息時，自動證明器將不做出它做出的相同決定，因為它只能進入本地的結(jié)果。許多方法現(xiàn)在被交互式定理證明器所使用，就像伊莎貝爾的blast，留下未改變的目標如果它們失敗于證明這目標的話。證明搜尋的自然方法期待在所有的情形中至少能做出一些進步，所以即使目標不是可證明的，它們也能夠有所幫助。比如，安全的步驟(就像在許多系統(tǒng)的∧E)應(yīng)該被實行，簡單化步驟被應(yīng)用等等。自動化也應(yīng)該是穩(wěn)定的。在大量的證明中，一個證明時?；旌辖换ナ胶妥詣拥淖C明。如果被自動化返回的目標容易根本地以目標的微小變化改變，這時關(guān)聯(lián)的交互式證明將被毫無用處的給予，而且一定被改寫。因為這一個理由，被自動化返回的不能解決的次目標應(yīng)該在對于最初的目標的微小改變下穩(wěn)定。如果一個證明能被建立，然后一開始把重心集中在使證明更加可維持的方面，就像魯棒一樣。效率是在蛋糕上的糖衣。完全也是重要的，雖然沒有必要在一階邏輯完全，但是寧可應(yīng)該有一個給定的程序解決的層次問題一個清楚的觀念。無論如何，一些系統(tǒng)的行為理論上理解是重要的，如果它接近簡單的目標。讓我們總結(jié)出這些觀點：?自動化應(yīng)該很簡單：它應(yīng)該在理論上很好地被了解，和在使用中可預(yù)期的。?自動化也應(yīng)該提供反饋，以至于使用者能估定一種證明的嘗試為什么失敗。?一個甚至比較強烈的需求是，自動化是可視的，在可視中通過證明的研究，能直接地檢查自動化的執(zhí)行。?自動化應(yīng)該是自然的，這是為了使證明器和使用者之間的概念差距最小化。舉例來說，自動化應(yīng)該在標準的邏輯系統(tǒng)中執(zhí)行，或者與使用者傳導(dǎo)證明的決策程度相一致。?時常，使用者對一個證明進行優(yōu)化有很多的安全步驟。與自動化在返回前至少做出改進相比，自動化簡單的返回“可證明”與“不可證明”是沒什么用處的。?自動化應(yīng)該是穩(wěn)定的，以至于在自動化的行為中理論上微小的改變不會產(chǎn)生大的變化。這是很重要的，因為交互式的證明包含大量隔行掃描使用者或自動化步驟的環(huán)節(jié)。?自動化也應(yīng)該是魯棒的，在意義上微小的變化不會影響自動化的可證實性。?我們想要自動化對明顯的理論是有效率的。?最后，我們想要自動化是完全精密的。她能很好的定義問題的層次。3目前交互式證明器的自動化目前交互式定理證明器的自動化證明方法不符合先前環(huán)節(jié)的需求。Isabelle/HOL是目前作為被認可的HOL執(zhí)行的代表。主要被使用的技術(shù)是一個描述的證明器blast，和簡化器simp。這些都混合在單個的自動化策略里。Isabelle也包括一個模式消除程序，它和blast使用起來有點相似。Simp被廣泛地使用，但是它并不是一個完全的一階證明方法。然而，它能滿足許多前期環(huán)節(jié)需求的事實解釋了為什么它這么流行，在交互式證明中。blast方法在肯定邏輯和組的簡單問題上運行得很好，但是它很難了解它的特性是什么。它基于一個證明器leanTAP，那對一階邏輯是完全的。另一方面，下列的目標稍微可證明在一階邏輯，但是blast不行。f(ga)=a┝Зy?g(fy)=y它甚至更加的混亂，但它在區(qū)間ga實現(xiàn)的時候，這區(qū)間在結(jié)果本身中發(fā)生，并是存在的證明。更糟的是，當像HOL的類型邏輯被表達的時候，ga是唯一的區(qū)間發(fā)生在可以使用的正確類型結(jié)果中。這一個失敗對于有效地處理等式邏輯是一個描述類型程序失敗的合并統(tǒng)一。因為它是這么的不受限制，所以自動方法幾乎從不被用于交互式證明的中間。而且，它是不穩(wěn)定的，在它產(chǎn)生的子目標中在對目標的較小變化之下可能是野性地不同的，它的提出是無用的除了在緊緊地被控領(lǐng)域。整合一個現(xiàn)代的解決證明器Vampire進入Isabelle將沒有必要糾正這些錯誤。基于解決的方式提供了一點支持對于交互式理論證明器，因為子句形式的減少意味著使用者有很少的可觀性進入證明的搜尋，而且很少知道為什么一個特殊的輔助定理會失效。證明的搜尋是一個本地的向前的綜合的搜尋，與一個全球化的向后的綜合搜尋的典型描述介紹以及Isabelle的策略水平相反。因此，對于使用者，解決是一個不自然的系統(tǒng)。通常從這些系統(tǒng)來的反饋是極差的甚至不存在的。此外，許多步驟應(yīng)該被認為是安全的(應(yīng)用一個終端和聚合的改寫組，運行一個∧E步驟)因為系統(tǒng)被當作一個黑盒子使用，或目標率直地被解決，或者更通常，一點也不解決，而且系統(tǒng)包含的關(guān)于可靠應(yīng)用的步驟被丟失的信息，留給使用者可以手動的應(yīng)用這些步驟。這里的問題是系統(tǒng)無法做出改進那些無法直接證明的目標。我們也作關(guān)于一階理論證明器的以下觀察。這些證明器被設(shè)計去尋找大量的數(shù)量詞實例，尋找可選擇地系數(shù)平等推論。然而在交互式定理證明器里的自動化的失敗沒有失敗于猜測大量的數(shù)量詞實例。4技術(shù)在下面這節(jié)，我們描述我們?nèi)绾谓⒆詣踊?。首先，我們正在嘗試尋找證明，所以我們將會需要(至少)證明的搜尋引擎。然后，我們在很大的程度上愿做用手動的方式的模型證明。除了證明的搜尋之外，在手動證明中其他主要的利用方法是簡單化。我們描述我們怎樣討論簡化器。有條件的簡單化是一種簡單化的形式，它的簡化器采用遞歸的方式企圖解決可能被應(yīng)用的當前目標的改寫選擇。我們討論正采用在這些目標上的簡化器沒有被最好的運行，并建議替代選擇。然后，當使用簡單化的時候，它是一個很好的方法去確定簡單裝置是匯合的和終端的。我們描述完成的執(zhí)行。當使用簡單化的時候，然而，也想利用在改寫一個證明的過程中產(chǎn)生的假設(shè)。確定改寫規(guī)則的組仍然是聚合的和終止的，就應(yīng)該在證明搜尋時提供一些動態(tài)完成的形式。我們討論我們?nèi)绾巫プ×诉@些議題。4.1證明的搜尋在這節(jié)中，我們描述我們證明搜尋的基本系統(tǒng)。這是一個單一的結(jié)論，對向后的證明搜尋是適當?shù)闹庇^系統(tǒng)。我們避開統(tǒng)一的流行的區(qū)間計算。這有一些有趣的結(jié)果當混合證明搜尋時用其他的方法。注意我們只對自動化的一階系統(tǒng)感興趣。4.1.1邏輯系統(tǒng)證明搜尋的二個主要系統(tǒng)是決議和描述。因為一個交互式環(huán)境的自動化，決議太不自然。因為這一原因，描述是更有希望的。我們因此限制我們的注意在基于描述的系統(tǒng)。描述系統(tǒng)典型地藉由否定目標而且尋找矛盾著手進行。我們甚至考慮到這是不自然的。我們因此集中在標準邏輯系統(tǒng)中直接執(zhí)行的描述系統(tǒng)。使用這樣一個系統(tǒng)根據(jù)復(fù)雜的執(zhí)行有重要的意義，因為我們能只是簡單地在HOL目標的水平搜尋使用或多或少標準的策略。這也對自然化有有利條件，因為使用者已經(jīng)熟悉一個如此系統(tǒng)的證明和反饋，因此我們能直接地對使用者呈現(xiàn)失敗的部分，這些使用者沒有翻譯出來自一些其它可能的證明系統(tǒng)的結(jié)果。單一結(jié)論系統(tǒng)對古典的證明是不適宜的，古典的證明被多樣結(jié)論系統(tǒng)更好的支援。然而多樣的結(jié)論系統(tǒng)是不自然的。如果我們對古典的證明感興趣，我們一定承認我們的單一結(jié)論系統(tǒng)有缺點。另一方面，我們相信大規(guī)模的證明結(jié)構(gòu)大概是直觀的：我們典型地集中于一個目標，并且我們的輔助定理服務(wù)作為證明中的中間觀點，和我們的補助定理如證明的中間點服務(wù)，即├A?B→C作為一個補助定理對├┑(A?B)?C不是典型地相等，因此我們期待在證明中達到一個點，這里A?B是可證明的，而不是去做一個可分的拆開。確定地對于我們感興趣的領(lǐng)域，所有的證明本質(zhì)上是直觀的，以及古典的推論被限制到可能被簡單化或其他的限制技術(shù)處理的小區(qū)域。4.1.2引進規(guī)則我們希望做出更多的進步。雖然程序簡述說明上方是完全的，它寧可是一邊的。既然大多數(shù)的證明大量利用輔助定理，對應(yīng)的目標傳輸容易變成相當擁擠。而且，當引進規(guī)定的時候，許多輔助定理自然地被瀏覽，也就是說，趨于使用精煉的結(jié)論C而不愿使用從Г開始向前連接著的結(jié)論。因為這些理由，我們也利用引進規(guī)則àlaPaulson[PNW03]。這些典型不安全，但是如果我們再一次返回，而且輪流其他的防備，完全性就能被保存。這些引進規(guī)則能像輔助定理一樣被執(zhí)行，但是被作記號作為引進規(guī)則。在證明的搜尋時候，這些輔助定理的結(jié)論被相配對抗當前的目標。如果結(jié)論與當前的目標相配，那么目標將被選擇的引進規(guī)則所代替，而且在事件中這些假定不能夠被證明，那么返回將被采用。如果一條引進規(guī)則標明是安全的，這時返回不發(fā)生。注意，這些提高沒有必要來自理論的觀點，而且它的唯一動機是做模型自然形式的證明。如果完全性以特定的方式被考慮，這時候能夠看見完全性的保存。如果這些規(guī)則是行為表現(xiàn)所預(yù)期的，則在簡單化之前需要等式的統(tǒng)一。然而，目前我們用手動的方式來模擬等式統(tǒng)一的使用。完全性失敗對于引用規(guī)則：如果我們以一條規(guī)則作為一條引進規(guī)則，這時我們無法是完全的?不過這不是真實的，而且規(guī)則是安全的，在哪一情況我們都很順利，或不安全的，在哪一情況我們返回。需求的統(tǒng)一意味著我們能避免我們能避免作為增加的假設(shè)而使用的規(guī)則。然而，如果在一些階段我們能以規(guī)則作為一條引進規(guī)則，這里有一個引進規(guī)則被打算使用的環(huán)境，但是沒有連接鏈，然而當一項額外的假定可能有時這里將沒有統(tǒng)一的問題。而且，自從我們沒有使用一個作為標準的輔助定理的規(guī)則，使用完全化的概念將不是很清楚。讓我們定義完全化的生產(chǎn)一個引進規(guī)則去了解是否有一個證明作為一個輔助定理的規(guī)則。這時一個使用規(guī)則的證明作為一條引進規(guī)則。在平等面前，我們應(yīng)該因此使用統(tǒng)一去確定我們的引進規(guī)則能被無論在那里都可能應(yīng)用。既然在每個階段我們有一個有限的場地區(qū)間組，與一個終端和匯合的改寫次序，這樣一個方法能夠可以實行，即使在現(xiàn)階段我們只能用人工模擬這樣的步驟。引進規(guī)則的使用會帶來復(fù)雜化，因為完全化是否適合不清楚。如果引進規(guī)則能作為一個正常的輔助定理使用，這時完全化是可以保留的，因此輔助定理被操作就像它是個正常的肯定邏輯。在一條引進規(guī)則后面的計劃是去平衡證明的搜尋，這會以別的方式主要地在左邊上操作。在規(guī)則├A→B作為幾個輔助定理和作為一個引進規(guī)則之間的差異，是自動化能應(yīng)用→L與一個作為輔助定理的規(guī)則相結(jié)合。因此作為一個引進規(guī)則，我們期望目標最終成為B和它能用A代替這些。4.2等式4.2.1改寫改寫是由用相等的子術(shù)語更換一個術(shù)語的變換過程。例如，我們可能使用輔助定理f(a)=a去改寫Qf(f(a))到Qf(a)然后到Q(a)。在這節(jié)中，我們的各種改寫概念是非正式的。對于更多的信息讀者可以請教優(yōu)秀者。在用辭上的一個注解：一個簡單化的次序是一個改寫被限制的次序，過去一直用來證明一個區(qū)間改寫系統(tǒng)的終止。然而，“簡單化”這個詞時常被非正式地用于提到改寫，而且“簡化組”這個詞時常用來提及改寫的系統(tǒng)規(guī)則。我們下面采用這些非正式的用法。兩個主要的簡單化財富是終止和聚集。沒有聚集，了解簡化器的行為就必須知道改寫被應(yīng)用的次序。這太多而不是使用者所期待的。在一個交互式環(huán)境中終止非常有用，例如，它允許反饋。而且，終止允許簡單化與主要的證明的搜尋相整合。如果我們有聚集和終端，這時每一個區(qū)間有一個獨特正式形式，而且嘗試的等式變得可決定。這是一個極其有用的簡化組的財富。我們的基本策略是熱心地應(yīng)用簡單化，在證明的搜尋每個步驟之后，使用假定去簡化其他的假定和結(jié)論。我們用一個有終止和聚集的簡化器工作。我們檢查終止和聚集的手動使用完成。我們在個體的類型中應(yīng)用簡單化。如果簡化組正在終止和聚合，這時它保存了證明搜尋的完全性。我們也在布爾類型應(yīng)用簡單化，但它不是一階邏輯的一種可能性。例如，我們采用高階對微小范圍的數(shù)量詞改寫。不是太困難而無法爭論而這也保存證明的搜尋完全。經(jīng)常相似改寫的假定在證明期間出現(xiàn)，而且這些可能被簡化組合并。給一項假定x.Px和假定Pt，就可以簡化Pt=，是再一次在布爾類型的簡化，而不是一階的操作。我們不以這一種形式的假定作為改寫：我們的對數(shù)量詞示例的基本途徑經(jīng)由區(qū)間計算，而且使用這些簡單化會破壞這方式的完全。我們使用假定形式x=y(可能數(shù)量化)來改寫。為了保有聚集和終止，我們完成簡化組的生產(chǎn)并動態(tài)的產(chǎn)生改寫。因為完成沒被保證結(jié)束，完成被限制到一個步驟的確定數(shù)字，雖然在我們的應(yīng)用中，完成總是成功。4.2.2條件的簡單化在這節(jié)中，我們描述有條件的簡單化，并且注意到標準的途徑去解決遞歸環(huán)境下簡化器的實施可能沒有被期待。我們建議一些其他的方法，而且討論其他的有條件的簡單化的問題。我們得出結(jié)論，目前有條件的簡單化太復(fù)雜而無法作為"簡單的"技術(shù)計算，并且的確太復(fù)雜而無法以一合理的方式與證明的搜尋相連接。我們建議考慮有條件的改寫就如平常的輔助定理的一樣的替代選擇。簡單化的工作在于對形式a=b的改寫，在目標的任何地方改寫a到b。有條件的簡單化的工作在于對有條件的形式├A→a=b（A是一典型的連接）的改寫。在一個依次的Г├C中，如果我們能證明﹃C,Г的話，我們就能在目標里調(diào)整a到b的改寫。我們應(yīng)該如何嘗試去證明條件A?假如我們正在用簡單化連接一個完全的證明搜尋系統(tǒng)。在這情況下，非常好的(從一個理論上的立場)行為會被由需求獲得，如果A是可證明的，那么它實際上是被證明的。因為對A的證明的搜尋是潛在的沒有終止的，我們這時應(yīng)該妥善地安排一個復(fù)雜的隔行掃描主要證明搜尋的過程，與子證明搜尋企圖去解決有條件的改寫情況。一個如此方式是不適口的不只因為效率的原因。簡單化的好處之一是，不像證明的搜尋，它正在終止。如果當采用有條件的簡單化的時候，我們希望保留這一終止的行為，當企圖證明條件的時候，我們應(yīng)該遵行被涉及的非終止。一個我們應(yīng)該采用的主要證明搜尋是去證明條件，但是限制對特別深度的搜尋。這也是不適口的。為了在一個合理的時間里保持簡單化的運行，這深度應(yīng)當非常小，因為條件的產(chǎn)生是很頻繁的。這些小的深度不能提供更多的條件解決辦法比其他簡單的方法。對于一個小深度的有限制的證明搜尋，這也意味著它的理論限制也能成為實際的限制：任何的有限制的證明搜尋將會是不完全的，但是由于大的深度我們可以有希望的忽略這樣的不完全。小的深度意味著我們可能面臨的條件能被解決的條件，這條件對于使用者是很清晰的，不過被限制的搜尋深度意味著情況沒有被解決。根據(jù)我們的經(jīng)驗，深度必須至少有10個邏輯的步驟(∨E及其他。)，連接中間有效的等式推論(我們想像一個情節(jié)我們有一個有效地處理等式的證明搜尋)。在實驗方面，根據(jù)簡化器的反應(yīng)時間執(zhí)行這些方法變得不實際，在深度4之后。在將來，這些方法對于電腦將變得是可實行的，雖然目前它不能。一個使用有限制的證明搜尋的替代選擇是為了解決從一個條件去確定一個可接受的條件類別，而且接受一些將會有可能是可證明的條件，但是它將會在外部被給的類別上失敗。明顯的選擇是提議的邏輯。然而，有條件的簡單化的問題擴充多深入地超過偶然的失敗證明一種提議有效的條件，如同我們稍后討論一樣，所以這方式不能產(chǎn)生任何很大實際的效益，雖然行為會至少在理論上有好的理解。被采用的HOL，HOL啟發(fā)和Isabelle的目前方式，是在條件上激發(fā)簡單器它自己。這些遞歸的召集是潛在的非終止(有條件的簡單化極端地傾向于成環(huán))，以至于被激發(fā)的遞歸簡化器的時間是限制的。這些深度搜尋的限制當解決條件遭受同樣的問題，這些問題在先前的段落被討論過的。方式在許多方面比上面的很差，因為額外的簡單化所有物有必要了解它的行為，當解決條件時，可能是不清晰的甚至在提議的條件上，讓單獨的情況來涉及述語。對于一個典型的目標，我們只需要簡單化能在一個簡單了解的方法方面有進步。對于條件，我們的需求通常是體檢可能的話，就被解決。簡單化不是完全形式的證明，因此，我們希望，我們的情況將會是以致于那簡單化能經(jīng)常很好地運行。然而，簡單化不能夠證明所有的前置詞條件以至于它的行為甚至在提議的水平是難了解的。在數(shù)量詞推論上，甚至在最基本的水平，失敗是基準。因此，當求證條件時，目前的方法無法足夠地以非終止的問題處理。而且條件的級別可被簡單化解決的很難去描述，而且不是簡單的適合使用者去理解。4.2.3完成完成是一個能確定簡單組是聚合還是終止的程序。聚合與終止是我們要求簡化組具備的兩個主要所有物，所以完成是當采用簡單化時一個有用的工具。我們討論我們的完成使用。在群的公理理論上使用完成的標準例子，源自一組終止和聚合的改寫對于這一個理論構(gòu)成一個標準的改寫系統(tǒng)的規(guī)則，展示了完成是有力的技術(shù)。在我們的工作中，這樣的動力是從不被需要。我們實現(xiàn)了我們發(fā)現(xiàn)的非常有用的基本完成。因為我們的需要是被限制的，我們沒有實現(xiàn)Huet的完全完成程序，雖然在不同的設(shè)定中這是令人想要的。我們放下這些是為了將來的工作。我們的完成程序也允許有條件的完成。當工作在一個鍵入設(shè)定的時候，時常希望在一個給定的類型中提及個體的一個子集。然后介紹一個述語的子類型，而且限制語句只談?wù)撟宇愋偷慕M成。4.2.4動態(tài)的完成我們先前提到了它時常是一個希望以假定作為改寫的例子。清楚地說，假定是動態(tài)的并且在證明的程序中各處改變。雖然我們可能開始就錯在改寫的簡單化規(guī)則的組，如果我們使用假定，它可能很好的作為我們的基本簡化組，增大假定，不再是聚合和終止。如果我們愿保存一個正在共同聚合和終止的簡化組的所有形式，這時我們在證明的過程期間必須運行一些完成形式。我們需要這樣的動態(tài)完成，因為它一定能在證明的過程期間被很好地運行。不幸地是，完成是一個相當昂貴的過程。而且，它大體上非終止的。然而，當看到各種規(guī)則類型被使用的時候，典型地它們是一種非常簡單的形式。舉例來說，我們時常獲得與假定類似的a=b∨a=c，然后著手進行一個可分的除去。產(chǎn)生的目標有假定a=b和a=c，我們愿作為簡單化的規(guī)則來使用它。多數(shù)的這些簡單化規(guī)則是基礎(chǔ)的。在這情況下，完成被保證去結(jié)束，應(yīng)該有一個方法發(fā)生短路的完成程序去得到一個能更快速地運行的相等程序。希望，如果我們能微小地減少完成的一條到另外一條規(guī)則的改寫，這時希望改寫程序相對地充分運用(當然地，這是伊莎貝爾空想的簡單化的情形，而且HOL光簡單化也在某些程度上是充分運用的)，而且執(zhí)行將會是可接受的。有一些文件覆蓋了基本區(qū)間的完成。我們看[GNP+93]。這一個運算法則帶來了一個基本的改寫規(guī)則組，而且在多項式產(chǎn)生一個減少的權(quán)威改寫系統(tǒng)的時間。不幸地是，雖然過程在多項式時間里操作，但是它利用合適的終止。合適的終止在HOL啟發(fā)或Isabelle中沒有被執(zhí)行，而且在及時上可能有一個沒有充分運用的版本相對緩慢是多項式的(即，雖然來自[GNP+93]的運算法則是多項式的在及時上，這里會有一個比例的高常數(shù))。當然，在證明期間做一個增加的變化給等式組，因此，在這某種程度希望有一點提高，但是我們?nèi)匀粦?yīng)該有能夠做更多的感覺?？匆幌挛覀兪褂米鳛楦膶懙募俣?，它是清楚，超過基本的，他們甚至有比較簡單的自然：沒有左手邊的子區(qū)間被用于任何其他的改寫規(guī)則(比如，假定a=b，全然沒有左手邊的一個適當子區(qū)間，而且我們從沒有另一項假定形式a=d同時發(fā)生的情況)。在這個例子中，它足夠為了要維持聚合和終止，用這一條規(guī)則改寫所有其他的簡單化規(guī)則。如果我們需要在線完成這些沒有被滿足的條件，我們會依靠我們的(被限制的時間)完成程序，但是在我們的個案研究中這不發(fā)生。當在基本完成的正確證明的上下文中考慮的時候，這一個結(jié)果是清晰的。然而，在我們的個案研究期間有若干的復(fù)雜情節(jié)，沒有這最佳化，導(dǎo)致我們的證明器花了特別久的時間。4.2.5方程式的統(tǒng)一我們的最高水平的證明搜尋基于列舉區(qū)間上升到一個確定的區(qū)間深度。統(tǒng)一沒有出現(xiàn)在一個這樣的程序中。我們引用引進規(guī)則àlaPaulson進入我們的搜尋程序?，F(xiàn)在由相配對的引進規(guī)則對抗現(xiàn)在的目標規(guī)則的結(jié)論被簡單的完成。引進規(guī)則像其他的輔助定理被對待，作為補充的假定它們合并的進入結(jié)果。不過，他們作為引進規(guī)則被作記號。我們用具體的例子說明它們的從區(qū)間的列舉像其他輔助定理一樣。結(jié)論通過簡化器被改寫。在證明搜尋的每個階段，我們檢查任何引進規(guī)則的結(jié)論是否與目前的目標相配，而且如果因此我們以引進規(guī)則的條件替換目標，返回不安全的引進規(guī)定，這有模擬等式統(tǒng)一的效果。5連接與整合在這節(jié)中我們描述在早先的章節(jié)中被簡述的技術(shù)如何整合進入一個單一戰(zhàn)略，和在這一個戰(zhàn)略和使用者之間的連接。我們的自動化包含一個描述的證明搜尋，藉由對固定的區(qū)間深度的數(shù)量詞實例化，以要求散布到簡單化。這些應(yīng)該如何被整合?如果簡單化正在終止和聚集的，這時應(yīng)用在證明搜尋的每個步驟后的簡單化的明顯策略保存完全。這是在這兩項技術(shù)整合后的必要觀察。策略提供了一個連接給使用者。使用過程中使用者必須敘述一組終止和聚集的改寫規(guī)則和一組引進規(guī)則的過程。事實上，使用者也敘述一組應(yīng)該在證明期間被考慮的輔助定理，而且這些只是被當作先前描述與目標陳述的合并。證明搜尋地進行，與安全的規(guī)則和簡單化熱心地應(yīng)用，以及在不安全規(guī)則上的返回。如果證明是不成功的，失敗部分被返回給使用者幾乎沒有安全規(guī)則，或簡單化的步驟，可能被應(yīng)用。對我們的方式一個缺點是結(jié)果相當大，因為我們正在特定的深度下面用所有的(類型-正確的)區(qū)間例示數(shù)量詞。它將有一點適應(yīng)使用者的連接，以使這些實例化不直接地呈現(xiàn)給使用者，但是在要求上可視的。我們離開這更進一步工作。6評估在這節(jié)中，我們討論我們的證明的過程怎樣相當于根據(jù)在第2節(jié)中被簡述的標準。我們?nèi)缓笥懻撏耆淖h題。我們沒有宣稱有一個正式的證明對完全產(chǎn)生一些問題的類別，但是我們確實討論過程有好的所有物。我們通過設(shè)置我們的技術(shù)產(chǎn)生其他的就像分析一樣的理論證明技術(shù)。然后我們通過給出的成功例子評估實際的過程使用，而且描述過程的感覺。6.1評估生產(chǎn)需求我們的程序與在第2節(jié)提到的標準一起被設(shè)計。我們感到它滿足簡單化的需求。在概念上，我們正在執(zhí)行一個標準直觀的證明搜尋。我們合并安全的和不安全的規(guī)則。我們在邏輯的水平(布爾類型)和領(lǐng)域的特性類型里使用簡單化。我們的簡單化規(guī)則應(yīng)該是聚集和終止的。當改寫不破壞重要的所有物時候，我們確信任何的假定都可以使用。我們只有在限制的它們有很好的行為的例子中使用簡單化以及有條件的簡單化規(guī)則。所有的這些觀念很容易理解的。當使用程序的時候，概念上的簡單化導(dǎo)致簡單化。我們應(yīng)當確定我們的簡化組，我們的引進規(guī)則組，以及與目標相關(guān)的輔助定理。策略在策略水平運行，因此，我們能通過激發(fā)一次一步的策略步進經(jīng)過一個失敗的證明嘗試。既然程序是非破壞力的(在某種意義上我們直接地搜尋使用自然減除的規(guī)則，并非對正常的形式轉(zhuǎn)換)，我們有高水平的可視化進入證明的搜尋。失敗部分典型地立刻被理解。安全步驟的觀念意謂，即使我們無法找到證明，我們回到使用者執(zhí)行得相當多的我們?nèi)〉眠M步的工作。不完全顯示它本身作為一個失敗去猜測大量的數(shù)量詞實例。隨著動態(tài)完成的失敗，不完全也能在證明搜尋期間產(chǎn)生。簡單化導(dǎo)致了穩(wěn)定性。當在它已經(jīng)成功之前，我們會稱的證明器是單調(diào)的，在那增加的輔助定理中，簡單化的規(guī)則，或不安全的規(guī)則不會導(dǎo)致程序的失敗。同樣地證明器是魯棒的，即使對定義有微小的變化等等。我們不會宣稱程序是有效率的。6.2完全我們自動化有一些不完全的來源。FOL的可證明性大體上是無法決定的。我們對區(qū)間集合的子集深度限制。是否有一個證明僅僅涉及到深度限制區(qū)間是現(xiàn)在可決定的，但是我們將會不可避免地失敗于找到我們的限制子集之外包括區(qū)間放置的證明。這是一個不完全的來源。然而，我們可能連續(xù)地增加區(qū)間深度并且這樣來恢復(fù)對可決定性花費的完全。FOL能在方程序的推論[McK75]中置入，所以期待等式推論表明對通常證明搜尋的類似問題。我們的方式是限制我們自己對終止和聚集的改寫規(guī)則組。因此完成可能失敗，或不可能結(jié)束，這是一個不完全的來源。而且，我們采用動態(tài)的完成，能同樣地失敗，雖然在實踐中這不是一個問題。然而，完成能讓使用者大量的進行交互式處理。如果使用者確定，改寫規(guī)則組是聚集和終止的，而且如果動態(tài)的完成在證明搜尋期間總是成功的，這時我們的等式操作將會是完整的。6.3效率目前自動化方法的成功很大停留在統(tǒng)一上，然而我們只有稍微地使用統(tǒng)一，當操作引進規(guī)則時。根據(jù)證明的搜尋，根據(jù)執(zhí)行我們的程序?qū)V泛類似像吉爾曼這樣的前統(tǒng)一程序。舉例來說，下列的目標是可決定的：(xyz.Pxy→Pyz→Pxz)→(xyz.Qxy→Qyz→Qxz)→(xy.Pxy→Pyx)→(xy.Pxy∨Qxy)→(xy.Pxy)∨(xy.Qxy)的確，事實或一個公式的虛偽能在一個只有四種要素的模型中被評估。然而，即使這樣一個的目標是可決定的，甚至于一些現(xiàn)代解決方法基于證明器的努力。不幸的是，我們的程序注定要花非常長的時間。在防御中，這樣的目標很少在交互式定理的證明中被碰到。如果他們被遇見，使用者當然可以用一個交互式的決議證明器去解決他們。除了基本的證明搜尋之外，我們對等式推論給予特別的關(guān)注。我們在完成上對等式結(jié)束的方式，和在各種可變的條件是滿足的。然而，如果保持這些情況，達成平等的方式或許是有效的。現(xiàn)代的決議證明器采用無窮盡的完成，推測的行為將不再比完成一個完全存在的改寫組有效率。6.4實際應(yīng)用因為它概念簡單，證明器是非常容易使用的。從一個定理到下一個定理的典型移動，激發(fā)證明器關(guān)于簡化組和預(yù)先輔助定理組的使用。如果證明沒有被建立，我們會見到失敗部分。這個部分通常是很容易理解的。幾乎總是(在我們的個案研究中，總是)需要增加一個簡化規(guī)則，或一個不是不重要的輔助定理。如果輔助定理沒有已經(jīng)被證明就應(yīng)該取出并證明它。增加必要的規(guī)則，程序被重復(fù)執(zhí)行，通常是成功的。大體上說，我們沒有修整簡單化規(guī)則和輔助定理組到每個定理：這些規(guī)則被利用取決與上下文的內(nèi)容，而且總是一個良好的主意去使用它們?nèi)绻梢缘脑?。相對于這些，太多的規(guī)則能導(dǎo)致執(zhí)行能力的降低，但是通常它正工作在一個給定的理論中，這里輔助定理的數(shù)量相對地被限制。有時候必須用一個巧妙的區(qū)間例示一個數(shù)量詞，但是這些是自然的困難的步驟。在使用者的手段(并非檢查一些失敗的部分的表現(xiàn))下步進的經(jīng)過證明的能力是非常有用的，而且提供很好的可視化，如果一些東西沒有正確工作的話。我們討論完全不是首要重要的，但是清楚地自動化的目標是協(xié)助使用者證明輔助定理。如果自動化能直接證明輔助定理，我們將沒有抱怨的了。在我們的個案研究中我們執(zhí)行許多證明。一個主要的結(jié)果包含超過250條交互式證明的手寫體。這些證明的手寫體不是最初的證明抄寫，所以自動化可以可實現(xiàn)的再造它們。我們的自動化能夠解決每一個輔助定理。我們提供針對證明的一個區(qū)段的統(tǒng)計，它涉及輔助定理theorem_3_nes_Mup，對于其他輔助定理是代表性的。這些輔助定理依次有一個次補助定理theorem_3__Mup_3。在下面的列表中，我們記錄定理名稱，策略手寫體的組成沒有我們的自動化，組成有我們的自動化和花費的時間。當求證theorem_3_nes_Mup時，次輔助定理theorem_3_nes_Mup_3被提供給自動化。當這個次輔助定理被省略，而且主要的輔助定理不需要theorem_3_nes_Mup協(xié)助的時候，我們也記錄發(fā)生的東西。這涉及了證明器在主要的輔助定理的證明期間的再次證明。在這情況下，一個證明被建立，雖然它需要花超過5分鐘的時間。然而，我們相信，這是由于自動化策略的無效率實行，而且我們想要在將來的工作中再實現(xiàn)它。這些補助定理對自動化對個案研究的其他輔助定理的效果是有代表性的。而且，我們已經(jīng)在其他的領(lǐng)域中相對成功的應(yīng)用了這樣的技術(shù)。即使執(zhí)行很差勁，調(diào)和這些證明程序以至于輔助定理能被證明是一個主要的完成。事實上我們可以用一個常用的方法提供程序有很好的理論所有的證據(jù)。定理名稱策略行自動操作的策略行自動操作的時間/秒theorem3_nes_Mup_328166theorem3_nes_Mup12124theorem3_nes_Mup'n/a13057替代選擇我們發(fā)展的自動化被我們在案例研究中遇見的問題所激發(fā)。然而，我們總是能夠完成我們的簡化組的事實應(yīng)該是一件幸運的事情。大體上我們能期待完成舉例失敗對于表達交換性的規(guī)則來說，所以測試兩個區(qū)間經(jīng)過一個權(quán)威的改寫組的等式。這里有一些處理問題的環(huán)境的方法，比如順序改寫交互式的規(guī)則的例子，但是我們想要這個機會考慮替代選擇一般的對等式處理的途徑。到現(xiàn)在為止，我們的證明搜尋限制了被考慮的區(qū)間深度?？雌饋硭坪跸拗频仁酵普摰揭粋€共同的區(qū)間子集是很合理的，而且在這里面采用適合終止限制的子集。這些介紹是過程的不完全。求證s=t使用等式需要的公理，大體上，是任意很大深度的區(qū)間。如果我們限制我們考慮的區(qū)間深度，我們的等式推論將會是不完全的。舉例來說，假設(shè)我們通過轉(zhuǎn)移鏈s=u=v=x=y=t來證明一個等式s=t。這樣的一個證明被展示在圖1。如果我們限制我們考慮到d或更小的區(qū)間深度，圖可能與圖2相似。在這個情況下，等式s=u=v將會被獲得，但是等式x=y和y=t將不會被獲得。如果沒有s=t的證明存在與被限制的共同區(qū)間里，我們將會無法推論得到s=t。因此在任何給出的我們證明搜尋的階段，我們的等式推論將會是不完全的。然而，如果我們連續(xù)地增加我們考慮的區(qū)間深度，我們將重新獲得等式推論的完全性。在這一環(huán)境下，方程式的統(tǒng)一，生產(chǎn)被限制的區(qū)間組，變成可決定的，而且能非常有效率地實現(xiàn)。這個方式的另一個優(yōu)點是給同等級別的代表能在一個使用者特別的習(xí)慣下被選擇。舉例來說，使用者可能選擇同等類型的子句作為代表，或最小的產(chǎn)生一些詞典的路徑命令。這對使結(jié)果保持易讀有幫助。這方式的另一個優(yōu)點是使用者的理解是簡單的，而且我們在證明搜尋的方法密合得很好。聚焦在單個復(fù)雜性上的衡量，比如區(qū)間深度，在一些程序之上，是一個統(tǒng)一的步驟。而且，缺點和方式的不完全經(jīng)由完成在這里是不存在的。我們留下這些替代選擇的執(zhí)行給將來的工作。區(qū)間深度suvxyt區(qū)間圖1:傳遞性的等式證明d區(qū)間深度suvxyt區(qū)間圖2:有深度限制的傳遞性等式證明8結(jié)論我們已經(jīng)呈現(xiàn)我們發(fā)展去抓住一件大的個案研究的自動化。自動化被修整到交互式的使用，自動化以一個證明搜尋引擎和簡單化的整合為基礎(chǔ)，本質(zhì)上依賴于完成。這節(jié)的貢獻是根據(jù)基本的證明搜尋，和它的簡單化整合，在一個交互式假定里解說目前自動化的失敗。我們的技術(shù)沒有走出