Prolog 学习 Ch1

Facts,Rules and Queries

Posted by R1NG on October 10, 2021 Viewed Times

Prolog 入门: 事实, 规则和查询

和常规的程序设计语言不同, Prolog 是一种被设计为处理 一阶谓词演算 的面向演绎推理的逻辑型语言. 虽然也可被用于设计通用图灵机, 但由于该语言具有文法简答, 表达力丰富等特点, 它常被用于解决数理逻辑, 抽象问题求解, 自然语言理解等问题.

特征和基本构成

Prolog 一名的本意就是 “逻辑编程” (Progamming of Logic). 在给出 事实 (Fact) 和 规则 (Rule) 后, 它就会自行分析其中的逻辑关系, 从而使我们可以通过 查询 (Queries) 完成复杂的逻辑运算.

Prolog 提供了统一的数据结构: (Term). 我们下面简述其定义和具体的从属关系:

定义 (项)

原子 (Atom), (Number), 变量 (Variable) 和 复合项 (Complex Term, i.e. Symbol) 组成.

定义 (原子)

原子 由以下三种字符串组成:

  1. 由大/小写字母, 数字和下划线组成, 并以小写字母为开头的字符串.
  2. 包含在一对单引号中的, 内容任意的字符串, 而单引号包含的内容被称为 原子名.
  3. 特殊字符 组成的字符串.

注意: 在 Prolog 中, 我们定义 “大小写字母” 分别为 A-Z, a-z, “数字“ 定义为 0-9, 下划线 _ 单独分开定义, 其余的符号则称为 特殊符号 (Special Characters). 空格被算作一种特殊的符号, 字符串被定义为一连串不间断的字符.

定义 (变量)

称由大小写字母, 数字和下划线组成, 且以 大写字母 为开头的字符串为 变量.

注意: 单独的下划线 _ 自然也是一种变量. 我们称其为 匿名变量 (Anonymous Variable).

定义 (复合项)

复合项 又称 结构体 (Structures), 由一个 函子 (Functor) 后跟一系列参数构成. 参数放在普通括号中, 用逗号分隔放在函子之后.

注意: 函子后面必须直接跟括号, 在函子和括起参数的括号之间不能有空格. 函子必须是一个原子而不能为变量.

从属关系如下:

(测试一下mermaid, 晚点画图)

graph LR
    

语法和属性

下面简述 Prolog 的命令行操作方式, 基本属性和语法.

命令行交互

我们可以在成功安装并正确配置 Prolog 后从终端通过 swipl 进入 Prolog 运行环境. 在 Prolog 运行环境中, ?- 为命令提示符, 每条命令的结尾都需要加上一个句号 . 表示语句结束. 要退出 Prolog, 需要使用 halt 命令:

20211010231425

基本语法

  1. 变量和常量
    由上一节的介绍可知, 在 Prolog 中以小写字母开头的字符串即为 常量, 而以大写字母开头的就是 变量.

  2. 事实和规则

    我们可以使用 符号 组成一些 事实:

    1
    2
    3
    4
    5
    
     likes(axton, chrome).
     likes(axton, cytusII).
     dislikes(axton, safari).
     dislikes(axton, arcaea).
     experiencedFrontendDeveloper(axton).
    

    此处注意, 关系不具备对称性. 此外, 如果括号中只包含一个参数, 即表示对象拥有该属性.

    规则是用于推理如何从一个推断得到另一个推断的方法.

    下面举一个例子:

    1
    
     senpai(X, Y) :- younger(Y, X), isMajorSame(X, Y), \+ notInTheSameUniversity(X, Y), isMale(X); isFemale(X).
    

    在上述代码中, X, Y 均为大写, 表示这是两个变量. 符号 :- 表示 推理关系, 意为只要推理符号右侧的表达式为 true, 则左侧的表达式为 true.

    由于该条规则取决于多个条件同时为 true,我们需要用逗号隔开条件.

    若需要表示 “某条规则取决于某个条件为 false”, 则需要在条件前加上 \+ 表示否定.

    若需要表示 “某条规则取决于某两个条件中其中一个为true”, 则需要用分号 ; 连接这两个条件.

  3. 查询
    Prolog 允许我们查询已知的事实. 要查询某个关系是否为真, 只需在命令行窗口中键入即可. 此外, 我们还可以使用 listing 列出所有已知的特定关系.

    20211010234809

最后以一个较为复杂的例子结束本章.

20211010235021

考虑对上述地图的着色问题: 假设现在有三种可选颜色, 且地图中相邻区域颜色必须不同, 求可行的上色方案的种数.

首先定义颜色:

1
2
3
color(manchesterPurple)
color(manchesterYellow)
color(manchesterGray)

然后定义着色的限制规则:

1
2
3
4
colorify(A, B, C, D, E) :- 
    color(A), color(B), color(C), color(D), color(E), 
    \+ A=B, \+ A=C, \+ A=D, \+ A=E,
    \+ B=C, \+ C=D, \+ D=E.

注意上述代码段定义了一个对 A, B, C, D, E 五个变量求值的表达式. 该表达式为 true 当且仅当这些在地图上相邻的颜色互异.

将上述两段代码组合为一个脚本, 加载执行, 可见计算机给出了六组解. 注意默认只有第一组解会被直接显示, 如果需要继续展示不同解的话需要手动输入分号 ;.

20211011000206