北航研究生课程_程序语言的设计原理教程_第12章.pptVIP

第12章 逻辑式程序设计语言 12.1谓词演算 谓词演算的等价变换 [1]以∧，∨， ?消除→、=符号 [2]化为前束范式,消除最外的?符号,否定符号内移?(?XP(X)┠ ?X(? p(X)) [3]用斯柯林变换消去存在量词 ?X(a ( X) ∧ b(X) ∨?Y c (X，Y)) ┠ ?X(a (X) ∧ b(X) ∨ c (X， g(X))) [4] 消除前束范式的全称量词 ┠ a(X) ∧ b(X) ∨ c (X，g(X)) 12.2 自动定理证明 12.3 逻辑程序的风格 12.4 典型逻辑程序设计语言Prolog Prolog要环境支持 ，即管理事实和规则的数据库 Prolog的基本成分是对象(常量、变量、结构、表)、谓词、运算符、函数、规则 从纯语法意义上Prolog的项什么都可以表示: 项::=常量|变量|结构|(项)|表后缀算符 |项中缀算符项|，项前缀算符 12.5 Prolog评价 Prolog提供一种证明风格的声明式程序设计， 推理清晰， 概括能力强， 程序和数据没有明显分离。 Prolog程序具有自文档性 由于非过程性，它也成为潜在的并行程序设计语言的候选者 它的效率仍不及传统过程语言。由于它的声明性质， 程序员在优化算法时作用有限 复杂的大型系统一开始很难按照证明系统开发， 程序不大运算量惊人 ， 而Prolog本身也只有局部量， 天生来也不是大型软件开发的工具。 因此， Prolog只能作为逻辑程序设计的独枝存在， 解决大型应用多范型语言是个出路 例 快速分类的Prolog代码 r1 split(_，[ ]，[ ]，[ ] ). r2 split (Pivot，[Head | Tail]，[Head | Sm]，Lg):- Head Pivot，split (Pivot，Tail，Sm，Lg). r3 split (Pivot，[Head | Tail]，Sm [Head | Lg]):- Pivot Head，split (Pivot，Tail，Sm，Lg). r4 quicksort ([ ]，[ ]). r5 quicksort ([Head [ ] ]，Head). r6 quicksort ([Pivot | Unsorted] AllSorted):- split (Pivot，Unsorted，Small，Large), quicksort (Small，SmSorted)， quicksort (Large，Lgsorted), append (SmSorted，[Pivot | LgSorted]，AllSorted). (3)逻辑和控制分离 Prolog无通常意义的控制结构，也就是该程序动作次序（显然也有）和计算的子句逻辑没有必然的关系。例如:把上例中r4,r5,r6写在r1,r2,r3前面并不影响本程序的执行结果。 cut和not谓词 因为Prolog的归结模型只能完整地证明正命题， 是否有解无法判定 如果明知再作没有意义，可人为截断cut (1) 安全cut 非形式解释cut， 它如同一篱笆， 由程序员任意置放在规则之中， 以停止无意义的回溯。 例 安全cut示例：求1到N的整数之和 r1 sum_to(N，1):-N=1，！. r2 sum_to (N，R):-N1 is N-1，sum_to(N1，R1)， R is R1 + N. 当有查询: ?-sum_to(1，X) //匹配r1 X=1; //打‘;’号由于有！不致无限查