第六章邏輯式程序設(shè)計(jì)語(yǔ)言-文庫(kù)吧資料
2025-08-07 13:25本頁(yè)面
【正文】 第一、二式是事實(shí)也是公理，把結(jié)果值作為變?cè)諏憽? 即使是整個(gè)目標(biāo)最后失敗， 也不等于這個(gè)目標(biāo)追求的命題是否定的， 因?yàn)橄抻跀?shù)據(jù)庫(kù)存放的規(guī)則和事實(shí)有限， 它是“ 封閉世界假說(shuō) ”之下的失敗。 因?yàn)樘岢龅膯?wèn)題就是證明過(guò)程的目標(biāo) ,所以查詢也叫目標(biāo) (goal)。 Av) getinput (Sum， N) : ratom (X)， not (eof)， getinput (Sum1， N1)， Sum is Sum1 + X， N is N1＋ 1. getinput (0， 0) : eof. 典型邏輯程序設(shè)計(jì)語(yǔ)言 Prolog ? Prolog要環(huán)境支持 ， 即管理事實(shí)和規(guī)則的數(shù)據(jù)庫(kù) ? Prolog的基本成分是對(duì)象 (常量、變量、結(jié)構(gòu)、表 )、謂詞、運(yùn)算符、函數(shù)、規(guī)則 ? 從 純語(yǔ)法 意義上 Prolog的項(xiàng)什么都可以表示 : ? 項(xiàng) ::=常量 |變量 |結(jié)構(gòu) |(項(xiàng) )|表 后綴算符 ? |項(xiàng) 中綴算符 項(xiàng) |，項(xiàng) 前綴算符 ?從 語(yǔ)義 角度， 以下語(yǔ)法描述提供了處理時(shí)的語(yǔ)義概念 : 程序 → 子句 子句 → ( 事實(shí) | 規(guī)則 | 查詢 ) 事實(shí) → 結(jié)構(gòu) 規(guī)則 → 頭 : 體 頭 → 結(jié)構(gòu) 體 → 目標(biāo) ， 目標(biāo) 目標(biāo) → /* 形如 p或 q(T， … ， )的字面量 */ ?Prolog程序結(jié)構(gòu) Prolog程序由子句組成， 子句模型是 Horn子句。 若 S為空， 則為無(wú)條件 Horn子句， 是一個(gè)斷言 (事實(shí) ) 邏輯程序的風(fēng)格 第一 個(gè)特點(diǎn)是它不描述計(jì)算過(guò)程而是描述證明過(guò)程 第二個(gè)特點(diǎn)是描述性 第三個(gè)特點(diǎn)是大量用表和遞歸實(shí)現(xiàn)重復(fù)操作 例 求平均成績(jī)的邏輯程序，打開(kāi)一分?jǐn)?shù)文件 scores， 讀入分?jǐn)?shù)求和并用的數(shù) N除之得平均成績(jī) average : see(scores)， getinput (Sum， N)， seen (scores)， Av is Sum /N， print (39?！??39。 ? Horn子句實(shí)現(xiàn)超歸結(jié) Horn子句是至多只有一個(gè)非負(fù)謂詞符號(hào)的子句 Horn子句形式示例如下 : ?P∨ ?Q∨ S∨ ?R∨ ?T 其中只有一個(gè)非負(fù)謂詞 S,可作以下演算： 先將 S移向右方 ┠ S∨ ?P∨ ?Q∨ ?R∨ ?T 按德 所謂 合一 是找出型式匹配的兩子句， 將它們合一為歸結(jié)式， 相當(dāng)于代數(shù)中的化簡(jiǎn)。 例：歸結(jié)證明 若有前題 待證命題 取反得新子句 p1 Q∨ ?P ?P∨ ?U p5 P p2 R∨ ?Q p6 U p3 S∨ ?R p4 ?U∨ ?S 取待證命題的反， 得 P∧ U， 它是 ∧ 連接的兩個(gè)子句P、 U， 把它們加到前題子句集， 為 p5， p6。命題得證。用合一算法得出新子句 (歸結(jié)式 )，再加入到子句集。歸結(jié)證明的過(guò)程并稱之歸結(jié)演繹， 其步驟如下 : [1]把前題中所有命題換成子句形式。 為了證明合適公式 F為真， 歸結(jié)法證明 ?F恒假來(lái)代替 F永真。 窮舉完所有路徑馬上遇到組合爆炸問(wèn)題，無(wú)論是深度優(yōu)先還是廣度優(yōu)先，百步演繹可能的路徑數(shù)都是天文數(shù)字。如此下去就形成一個(gè)龐大的樹(shù)行公理集， 每層的結(jié)點(diǎn)表示一個(gè)公理的語(yǔ)句， 其深度和寬度隨問(wèn)題和最初給出的公理而定， 一層一步驟， N層的樹(shù)就是 N步推理。 關(guān)鍵是效率。 所以能滿足該理論的模型往往不止一個(gè)。 公理的謂詞符號(hào)必須派定為域中對(duì)象的性質(zhì)， 函數(shù)派定為對(duì)域中對(duì)象的操作。 因?yàn)樾问较到y(tǒng)只是符號(hào)抽象，借助模型我們可為每個(gè)常量、函數(shù)、謂詞符號(hào)找到真理性的解釋。連接的子句的集合 自動(dòng)定理證明 ? 證明系統(tǒng) 事實(shí)即證明系統(tǒng)中的公理 (axioms) 證明系統(tǒng) (proof system)是應(yīng)用公理演繹出定理 (theorems)的合法演繹規(guī)則的集合 演繹也叫歸約 (deduction)， 是對(duì)證明系統(tǒng)中合法 推理規(guī)則的一次應(yīng)用 演繹從公理導(dǎo)出結(jié)論 (conclusion)， 中間可利用以 這些規(guī)則演繹出的定理 證明 (proof)是個(gè)語(yǔ)句序列， 以每個(gè)語(yǔ)句得到證明而結(jié)束， 即每個(gè)句子要么演繹成公理， 要么演繹成前此導(dǎo)出的定理 一個(gè)證明若有 N個(gè)語(yǔ)句 (命題 )則稱 N步證明 反駁 (refutation)是一個(gè)語(yǔ)句的反向證明。Lv 因此，任一公式均可化為 39。L2?！?39。39。 于是采取反證的方法，全稱量化的謂詞取反 量化謂詞 取反 ?Xodd(X)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1