. . . . . .
.
.. ..
.
.
Introduction to Answer Set Programming (ASP):
Logic Programming and Non-Monotonic Reasoning
Jianmin Ji and Guoqiang Jin
{jizheng,abxeeled}@mail.ustc.edu.cn
Multi-Agent Systems Lab.
School of Computer Science and Technology
University of Science and Technology of China
August 17, 2010
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 1 / 21
. . . . . .
.. Outline
.
. .1 关于暑期讨论班
.
. .2 逻辑程序
.
. .3 稳定模型
.
. .4 相关阅读材料
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 2 / 21
. . . . . .
关于暑期讨论班
.. Outline
.
. .1 关于暑期讨论班
.
. .2 逻辑程序
.
. .3 稳定模型
.
. .4 相关阅读材料
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 3 / 21
. . . . . .
关于暑期讨论班
.. 机器人智能决策讨论班 (2010年暑假)
主要内容：
Answer Set Programming (ASP)基础：历史背景，语法，语义，基
本性质。
ASP求解：计算原理，多种求解器介绍，使用和比较。
ASP编程：使用 ASP来求解问题，Home组仿真平台的熟悉以及编
程。
自然语言理解，以及自然语言理解在 Home机器人决策中的应用。
行动推理的理论以及相关的实验。
方式：
报告：隔一天一次专题报告。见
http://wrighteagle.org/cn/seminar/theory_10.php
文献阅读：在报告之前和之后，有一些文献需要阅读。
讨论：每次报告后有一段时间集体讨论或回答问题。
实验：主要是 Home组的仿真平台。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 4 / 21
http://wrighteagle.org/cn/seminar/theory_10.php
. . . . . .
关于暑期讨论班
.. 机器人智能决策讨论班 (2010年暑假)
主要内容：
Answer Set Programming (ASP)基础：历史背景，语法，语义，基
本性质。
ASP求解：计算原理，多种求解器介绍，使用和比较。
ASP编程：使用 ASP来求解问题，Home组仿真平台的熟悉以及编
程。
自然语言理解，以及自然语言理解在 Home机器人决策中的应用。
行动推理的理论以及相关的实验。
方式：
报告：隔一天一次专题报告。见
http://wrighteagle.org/cn/seminar/theory_10.php
文献阅读：在报告之前和之后，有一些文献需要阅读。
讨论：每次报告后有一段时间集体讨论或回答问题。
实验：主要是 Home组的仿真平台。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 4 / 21
http://wrighteagle.org/cn/seminar/theory_10.php
. . . . . .
关于暑期讨论班
.. ASP基础与应用讨论班 (2010年暑假) con’t
期望效果
了解 ASP理论基础。
掌握 ASP编程技术，可以用来求解实际问题。
了解行动推理或自然语言理解的大致框架。
了解并实验 Home机器人中使用的 ASP智能决策技术。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 5 / 21
. . . . . .
逻辑程序
.. Outline
.
. .1 关于暑期讨论班
.
. .2 逻辑程序
.
. .3 稳定模型
.
. .4 相关阅读材料
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 6 / 21
. . . . . .
逻辑程序
.. 逻辑程序
Answer Set Programming (ASP)是逻辑程序 (Logic
Programming)中的一种。
逻辑程序的基本观点：Algorithm = Logic + Control
只需用逻辑程序将问题的逻辑部分 (问题是什么)描述清楚，程序自
动求解。
在逻辑程序中引入 ‘not’，从而处理非单调推理。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 7 / 21
. . . . . .
逻辑程序
.. 逻辑程序
Answer Set Programming (ASP)是逻辑程序 (Logic
Programming)中的一种。
逻辑程序的基本观点：Algorithm = Logic + Control
只需用逻辑程序将问题的逻辑部分 (问题是什么)描述清楚，程序自
动求解。
在逻辑程序中引入 ‘not’，从而处理非单调推理。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 7 / 21
. . . . . .
逻辑程序
.. 逻辑程序
Answer Set Programming (ASP)是逻辑程序 (Logic
Programming)中的一种。
逻辑程序的基本观点：Algorithm = Logic + Control
只需用逻辑程序将问题的逻辑部分 (问题是什么)描述清楚，程序自
动求解。
在逻辑程序中引入 ‘not’，从而处理非单调推理。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 7 / 21
. . . . . .
逻辑程序
.. 逻辑程序
Answer Set Programming (ASP)是逻辑程序 (Logic
Programming)中的一种。
逻辑程序的基本观点：Algorithm = Logic + Control
只需用逻辑程序将问题的逻辑部分 (问题是什么)描述清楚，程序自
动求解。
在逻辑程序中引入 ‘not’，从而处理非单调推理。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 7 / 21
. . . . . .
逻辑程序
.. 逻辑程序的语法
在逻辑程序中 (正程序)，所有“语句”都表示成“规则”的形式：
A← A1, A2, . . . , Am.
其中 A是一个原子，称为该规则的“头”， Ai 也是原子，合称为该
规则的“体”。
n = 0的规则称为“事实”，没有体，只有头，往往省略反箭头←.
文字的析取称为一个“子句”。不严格的说，一条规则
A← A1, A2, . . . , Am 代表一个子句 A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am。
仅有一个正文字的子句，称为 Horn子句。每条逻辑程序 (正程序)
的规则对应一个 Horn子句。
默认子句中出现的所有个体变元都被全称量化。因此，子
句 A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am 实际上是全称闭式：
∀x1, x2, . . . , xn : A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am
的简写，其中 x1, x2, . . ., xn 是子句中出现的所有个体变元。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 8 / 21
. . . . . .
逻辑程序
.. 逻辑程序的语法
在逻辑程序中 (正程序)，所有“语句”都表示成“规则”的形式：
A← A1, A2, . . . , Am.
其中 A是一个原子，称为该规则的“头”， Ai 也是原子，合称为该
规则的“体”。
n = 0的规则称为“事实”，没有体，只有头，往往省略反箭头←.
文字的析取称为一个“子句”。不严格的说，一条规则
A← A1, A2, . . . , Am 代表一个子句 A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am。
仅有一个正文字的子句，称为 Horn子句。每条逻辑程序 (正程序)
的规则对应一个 Horn子句。
默认子句中出现的所有个体变元都被全称量化。因此，子
句 A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am 实际上是全称闭式：
∀x1, x2, . . . , xn : A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am
的简写，其中 x1, x2, . . ., xn 是子句中出现的所有个体变元。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 8 / 21
. . . . . .
逻辑程序
.. 逻辑程序的语法
在逻辑程序中 (正程序)，所有“语句”都表示成“规则”的形式：
A← A1, A2, . . . , Am.
其中 A是一个原子，称为该规则的“头”， Ai 也是原子，合称为该
规则的“体”。
n = 0的规则称为“事实”，没有体，只有头，往往省略反箭头←.
文字的析取称为一个“子句”。不严格的说，一条规则
A← A1, A2, . . . , Am 代表一个子句 A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am。
仅有一个正文字的子句，称为 Horn子句。每条逻辑程序 (正程序)
的规则对应一个 Horn子句。
默认子句中出现的所有个体变元都被全称量化。因此，子
句 A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am 实际上是全称闭式：
∀x1, x2, . . . , xn : A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am
的简写，其中 x1, x2, . . ., xn 是子句中出现的所有个体变元。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 8 / 21
. . . . . .
逻辑程序
.. 逻辑程序的语法
在逻辑程序中 (正程序)，所有“语句”都表示成“规则”的形式：
A← A1, A2, . . . , Am.
其中 A是一个原子，称为该规则的“头”， Ai 也是原子，合称为该
规则的“体”。
n = 0的规则称为“事实”，没有体，只有头，往往省略反箭头←.
文字的析取称为一个“子句”。不严格的说，一条规则
A← A1, A2, . . . , Am 代表一个子句 A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am。
仅有一个正文字的子句，称为 Horn子句。每条逻辑程序 (正程序)
的规则对应一个 Horn子句。
默认子句中出现的所有个体变元都被全称量化。因此，子
句 A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am 实际上是全称闭式：
∀x1, x2, . . . , xn : A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am
的简写，其中 x1, x2, . . ., xn 是子句中出现的所有个体变元。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 8 / 21
. . . . . .
逻辑程序
.. 逻辑程序的语法
在逻辑程序中 (正程序)，所有“语句”都表示成“规则”的形式：
A← A1, A2, . . . , Am.
其中 A是一个原子，称为该规则的“头”， Ai 也是原子，合称为该
规则的“体”。
n = 0的规则称为“事实”，没有体，只有头，往往省略反箭头←.
文字的析取称为一个“子句”。不严格的说，一条规则
A← A1, A2, . . . , Am 代表一个子句 A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am。
仅有一个正文字的子句，称为 Horn子句。每条逻辑程序 (正程序)
的规则对应一个 Horn子句。
默认子句中出现的所有个体变元都被全称量化。因此，子
句 A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am 实际上是全称闭式：
∀x1, x2, . . . , xn : A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am
的简写，其中 x1, x2, . . ., xn 是子句中出现的所有个体变元。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 8 / 21
. . . . . .
逻辑程序
.. Herbrand基
任给程序 P, P的一个“常项”(ground term)是一个由 P中出现的
个体常元和函数符号复合而成的项。
P的所有常项的集合称为 P的 Herbrand域 (Herbrand Universe)，
记为 U(P)。
例如： P1 = { p(1)., q(2)., q(x)← p(x). }，则 U(P1) = { 1, 2 }。
P的一个“常原子”是一个由 P的常项和 P中出现的谓词符号组成
的原子。
P的所有常原子的集合称为 P的 Herbrand基 (Herbrand Base)，
记为 B(P)。例如， B(P1) = { p(1), p(2), q(1), q(2) }.
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 9 / 21
. . . . . .
逻辑程序
.. Herbrand基
任给程序 P, P的一个“常项”(ground term)是一个由 P中出现的
个体常元和函数符号复合而成的项。
P的所有常项的集合称为 P的 Herbrand域 (Herbrand Universe)，
记为 U(P)。
例如： P1 = { p(1)., q(2)., q(x)← p(x). }，则 U(P1) = { 1, 2 }。
P的一个“常原子”是一个由 P的常项和 P中出现的谓词符号组成
的原子。
P的所有常原子的集合称为 P的 Herbrand基 (Herbrand Base)，
记为 B(P)。例如， B(P1) = { p(1), p(2), q(1), q(2) }.
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 9 / 21
. . . . . .
逻辑程序
.. Herbrand基
任给程序 P, P的一个“常项”(ground term)是一个由 P中出现的
个体常元和函数符号复合而成的项。
P的所有常项的集合称为 P的 Herbrand域 (Herbrand Universe)，
记为 U(P)。
例如： P1 = { p(1)., q(2)., q(x)← p(x). }，则 U(P1) = { 1, 2 }。
P的一个“常原子”是一个由 P的常项和 P中出现的谓词符号组成
的原子。
P的所有常原子的集合称为 P的 Herbrand基 (Herbrand Base)，
记为 B(P)。例如， B(P1) = { p(1), p(2), q(1), q(2) }.
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 9 / 21
. . . . . .
逻辑程序
.. Herbrand基
任给程序 P, P的一个“常项”(ground term)是一个由 P中出现的
个体常元和函数符号复合而成的项。
P的所有常项的集合称为 P的 Herbrand域 (Herbrand Universe)，
记为 U(P)。
例如： P1 = { p(1)., q(2)., q(x)← p(x). }，则 U(P1) = { 1, 2 }。
P的一个“常原子”是一个由 P的常项和 P中出现的谓词符号组成
的原子。
P的所有常原子的集合称为 P的 Herbrand基 (Herbrand Base)，
记为 B(P)。例如， B(P1) = { p(1), p(2), q(1), q(2) }.
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 9 / 21
. . . . . .
逻辑程序
.. Herbrand基
任给程序 P, P的一个“常项”(ground term)是一个由 P中出现的
个体常元和函数符号复合而成的项。
P的所有常项的集合称为 P的 Herbrand域 (Herbrand Universe)，
记为 U(P)。
例如： P1 = { p(1)., q(2)., q(x)← p(x). }，则 U(P1) = { 1, 2 }。
P的一个“常原子”是一个由 P的常项和 P中出现的谓词符号组成
的原子。
P的所有常原子的集合称为 P的 Herbrand基 (Herbrand Base)，
记为 B(P)。例如， B(P1) = { p(1), p(2), q(1), q(2) }.
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 9 / 21
. . . . . .
逻辑程序
.. 逻辑程序的常例 (grounding)
任给一个规则 R， R的一个“常例”(ground instance)是通过下述
操作产生的不含个体变元的规则：对 R中出现的每一个体变元 x，
处处同时带入一个常项。
例如， P1 中第三条规则有两个常例:
q(1)← p(1).
q(2)← p(2).
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 10 / 21
. . . . . .
逻辑程序
.. 逻辑程序的常例 (grounding)
任给一个规则 R， R的一个“常例”(ground instance)是通过下述
操作产生的不含个体变元的规则：对 R中出现的每一个体变元 x，
处处同时带入一个常项。
例如， P1 中第三条规则有两个常例:
q(1)← p(1).
q(2)← p(2).
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 10 / 21
. . . . . .
逻辑程序
.. 逻辑程序的 Herbrand解释
逻辑程序的语义与经典语义不同，建立在 Herbrand解释之上。
一阶逻辑语义：一个解释 I由一个论域 D以及一个从项和公式
到 D上函数和关系的映射 V构成。给定 I，任何公式都可被映射为
真或者假。
任给程序 P， P的任何一个 Herbrand解释 IH 的论域取为 U(P)，
即 P的 Herbrand域。 IH 的解释函数 VH 将 P的任意常项和常原子
映射为它们自身。
P的一个 Herbrand解释还包含一个由 P的若干常原子组成的“指
派”集合M(P) ⊆ B(P)。一个常原子 p在指派M(P)下为真，当且
仅当 p ∈M(P)。
任何规则 R在一个 Herbrand解释 IH 下的真值根据M(P)如下：
…1 IH(R) = t，当且仅当对 R的所有常例 R∗ 有 IH(R∗) = t；
…2 若 A← A1, A2, . . . , Am 是一个规则的常例，则
IH(A← A1, A2, . . . , Am) =df IH(A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am),
当且仅当， IH(A) = t或者存在 Ai 使得 IH(¬Ai) = t，
当且仅当， A ∈M(P)或者存在 Ai ̸∈M(P)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 11 / 21
. . . . . .
逻辑程序
.. 逻辑程序的 Herbrand解释
逻辑程序的语义与经典语义不同，建立在 Herbrand解释之上。
一阶逻辑语义：一个解释 I由一个论域 D以及一个从项和公式
到 D上函数和关系的映射 V构成。给定 I，任何公式都可被映射为
真或者假。
任给程序 P， P的任何一个 Herbrand解释 IH 的论域取为 U(P)，
即 P的 Herbrand域。 IH 的解释函数 VH 将 P的任意常项和常原子
映射为它们自身。
P的一个 Herbrand解释还包含一个由 P的若干常原子组成的“指
派”集合M(P) ⊆ B(P)。一个常原子 p在指派M(P)下为真，当且
仅当 p ∈M(P)。
任何规则 R在一个 Herbrand解释 IH 下的真值根据M(P)如下：
…1 IH(R) = t，当且仅当对 R的所有常例 R∗ 有 IH(R∗) = t；
…2 若 A← A1, A2, . . . , Am 是一个规则的常例，则
IH(A← A1, A2, . . . , Am) =df IH(A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am),
当且仅当， IH(A) = t或者存在 Ai 使得 IH(¬Ai) = t，
当且仅当， A ∈M(P)或者存在 Ai ̸∈M(P)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 11 / 21
. . . . . .
逻辑程序
.. 逻辑程序的 Herbrand解释
逻辑程序的语义与经典语义不同，建立在 Herbrand解释之上。
一阶逻辑语义：一个解释 I由一个论域 D以及一个从项和公式
到 D上函数和关系的映射 V构成。给定 I，任何公式都可被映射为
真或者假。
任给程序 P， P的任何一个 Herbrand解释 IH 的论域取为 U(P)，
即 P的 Herbrand域。 IH 的解释函数 VH 将 P的任意常项和常原子
映射为它们自身。
P的一个 Herbrand解释还包含一个由 P的若干常原子组成的“指
派”集合M(P) ⊆ B(P)。一个常原子 p在指派M(P)下为真，当且
仅当 p ∈M(P)。
任何规则 R在一个 Herbrand解释 IH 下的真值根据M(P)如下：
…1 IH(R) = t，当且仅当对 R的所有常例 R∗ 有 IH(R∗) = t；
…2 若 A← A1, A2, . . . , Am 是一个规则的常例，则
IH(A← A1, A2, . . . , Am) =df IH(A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am),
当且仅当， IH(A) = t或者存在 Ai 使得 IH(¬Ai) = t，
当且仅当， A ∈M(P)或者存在 Ai ̸∈M(P)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 11 / 21
. . . . . .
逻辑程序
.. 逻辑程序的 Herbrand解释
逻辑程序的语义与经典语义不同，建立在 Herbrand解释之上。
一阶逻辑语义：一个解释 I由一个论域 D以及一个从项和公式
到 D上函数和关系的映射 V构成。给定 I，任何公式都可被映射为
真或者假。
任给程序 P， P的任何一个 Herbrand解释 IH 的论域取为 U(P)，
即 P的 Herbrand域。 IH 的解释函数 VH 将 P的任意常项和常原子
映射为它们自身。
P的一个 Herbrand解释还包含一个由 P的若干常原子组成的“指
派”集合M(P) ⊆ B(P)。一个常原子 p在指派M(P)下为真，当且
仅当 p ∈M(P)。
任何规则 R在一个 Herbrand解释 IH 下的真值根据M(P)如下：
…1 IH(R) = t，当且仅当对 R的所有常例 R∗ 有 IH(R∗) = t；
…2 若 A← A1, A2, . . . , Am 是一个规则的常例，则
IH(A← A1, A2, . . . , Am) =df IH(A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am),
当且仅当， IH(A) = t或者存在 Ai 使得 IH(¬Ai) = t，
当且仅当， A ∈M(P)或者存在 Ai ̸∈M(P)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 11 / 21
. . . . . .
逻辑程序
.. 逻辑程序的 Herbrand解释
逻辑程序的语义与经典语义不同，建立在 Herbrand解释之上。
一阶逻辑语义：一个解释 I由一个论域 D以及一个从项和公式
到 D上函数和关系的映射 V构成。给定 I，任何公式都可被映射为
真或者假。
任给程序 P， P的任何一个 Herbrand解释 IH 的论域取为 U(P)，
即 P的 Herbrand域。 IH 的解释函数 VH 将 P的任意常项和常原子
映射为它们自身。
P的一个 Herbrand解释还包含一个由 P的若干常原子组成的“指
派”集合M(P) ⊆ B(P)。一个常原子 p在指派M(P)下为真，当且
仅当 p ∈M(P)。
任何规则 R在一个 Herbrand解释 IH 下的真值根据M(P)如下：
…1 IH(R) = t，当且仅当对 R的所有常例 R∗ 有 IH(R∗) = t；
…2 若 A← A1, A2, . . . , Am 是一个规则的常例，则
IH(A← A1, A2, . . . , Am) =df IH(A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am),
当且仅当， IH(A) = t或者存在 Ai 使得 IH(¬Ai) = t，
当且仅当， A ∈M(P)或者存在 Ai ̸∈M(P)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 11 / 21
. . . . . .
逻辑程序
.. 逻辑程序的 Herbrand解释
逻辑程序的语义与经典语义不同，建立在 Herbrand解释之上。
一阶逻辑语义：一个解释 I由一个论域 D以及一个从项和公式
到 D上函数和关系的映射 V构成。给定 I，任何公式都可被映射为
真或者假。
任给程序 P， P的任何一个 Herbrand解释 IH 的论域取为 U(P)，
即 P的 Herbrand域。 IH 的解释函数 VH 将 P的任意常项和常原子
映射为它们自身。
P的一个 Herbrand解释还包含一个由 P的若干常原子组成的“指
派”集合M(P) ⊆ B(P)。一个常原子 p在指派M(P)下为真，当且
仅当 p ∈M(P)。
任何规则 R在一个 Herbrand解释 IH 下的真值根据M(P)如下：
…1 IH(R) = t，当且仅当对 R的所有常例 R∗ 有 IH(R∗) = t；
…2 若 A← A1, A2, . . . , Am 是一个规则的常例，则
IH(A← A1, A2, . . . , Am) =df IH(A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am),
当且仅当， IH(A) = t或者存在 Ai 使得 IH(¬Ai) = t，
当且仅当， A ∈M(P)或者存在 Ai ̸∈M(P)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 11 / 21
. . . . . .
逻辑程序
.. 逻辑程序的 Herbrand解释
逻辑程序的语义与经典语义不同，建立在 Herbrand解释之上。
一阶逻辑语义：一个解释 I由一个论域 D以及一个从项和公式
到 D上函数和关系的映射 V构成。给定 I，任何公式都可被映射为
真或者假。
任给程序 P， P的任何一个 Herbrand解释 IH 的论域取为 U(P)，
即 P的 Herbrand域。 IH 的解释函数 VH 将 P的任意常项和常原子
映射为它们自身。
P的一个 Herbrand解释还包含一个由 P的若干常原子组成的“指
派”集合M(P) ⊆ B(P)。一个常原子 p在指派M(P)下为真，当且
仅当 p ∈M(P)。
任何规则 R在一个 Herbrand解释 IH 下的真值根据M(P)如下：
…1 IH(R) = t，当且仅当对 R的所有常例 R∗ 有 IH(R∗) = t；
…2 若 A← A1, A2, . . . , Am 是一个规则的常例，则
IH(A← A1, A2, . . . , Am) =df IH(A ∨ ¬A1 ∨ ¬A2 ∨ · · · ∨ ¬Am),
当且仅当， IH(A) = t或者存在 Ai 使得 IH(¬Ai) = t，
当且仅当， A ∈M(P)或者存在 Ai ̸∈M(P)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 11 / 21
. . . . . .
逻辑程序
.. 逻辑程序的 Herbrand模型
一个 Herbrand解释称为一个规则的 Herbrand模型，如果该规则在
该解释下为真。
一个 Herbrand解释称为一个程序的 Herbrand模型，如果该程序的
所有规则在该解释下为真。
严格说，一个程序 P的一个 Herbrand解释是一个三元
组 IH = ⟨U(P), VH, M(P)⟩。但 U(P)和 VH 对任何 P都是“固定
的”，所以通常用指派集合M(P) ⊆ B(P)代表一个 Herbrand模型，
简记为M。
例如， P1 = { p(1)., q(2)., q(x)← p(x). }有两个 Herbrand模型:
{ p(1), q(1), q(2) }和 { p(1), p(2), q(1), q(2) }。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 12 / 21
. . . . . .
逻辑程序
.. 逻辑程序的 Herbrand模型
一个 Herbrand解释称为一个规则的 Herbrand模型，如果该规则在
该解释下为真。
一个 Herbrand解释称为一个程序的 Herbrand模型，如果该程序的
所有规则在该解释下为真。
严格说，一个程序 P的一个 Herbrand解释是一个三元
组 IH = ⟨U(P), VH, M(P)⟩。但 U(P)和 VH 对任何 P都是“固定
的”，所以通常用指派集合M(P) ⊆ B(P)代表一个 Herbrand模型，
简记为M。
例如， P1 = { p(1)., q(2)., q(x)← p(x). }有两个 Herbrand模型:
{ p(1), q(1), q(2) }和 { p(1), p(2), q(1), q(2) }。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 12 / 21
. . . . . .
逻辑程序
.. 逻辑程序的 Herbrand模型
一个 Herbrand解释称为一个规则的 Herbrand模型，如果该规则在
该解释下为真。
一个 Herbrand解释称为一个程序的 Herbrand模型，如果该程序的
所有规则在该解释下为真。
严格说，一个程序 P的一个 Herbrand解释是一个三元
组 IH = ⟨U(P), VH, M(P)⟩。但 U(P)和 VH 对任何 P都是“固定
的”，所以通常用指派集合M(P) ⊆ B(P)代表一个 Herbrand模型，
简记为M。
例如， P1 = { p(1)., q(2)., q(x)← p(x). }有两个 Herbrand模型:
{ p(1), q(1), q(2) }和 { p(1), p(2), q(1), q(2) }。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 12 / 21
. . . . . .
逻辑程序
.. 逻辑程序的 Herbrand模型
一个 Herbrand解释称为一个规则的 Herbrand模型，如果该规则在
该解释下为真。
一个 Herbrand解释称为一个程序的 Herbrand模型，如果该程序的
所有规则在该解释下为真。
严格说，一个程序 P的一个 Herbrand解释是一个三元
组 IH = ⟨U(P), VH, M(P)⟩。但 U(P)和 VH 对任何 P都是“固定
的”，所以通常用指派集合M(P) ⊆ B(P)代表一个 Herbrand模型，
简记为M。
例如， P1 = { p(1)., q(2)., q(x)← p(x). }有两个 Herbrand模型:
{ p(1), q(1), q(2) }和 { p(1), p(2), q(1), q(2) }。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 12 / 21
. . . . . .
逻辑程序
.. 正程序 Herbrand模型性质
.
Proposition 1
..
.. ..
.
.任何正程序都有 Herbrand模型。
.
Theorem 1..
.. ..
.
.
正程序的任意两个 Herbrand模型的交集也是该程序的一个 Herbrand模
型。
.
Proposition 2
..
.. ..
.
.任何正程序有唯一的极小（最小）Herbrand模型。记为 AS(P)。
.
Proposition 3
..
.. ..
.
.两个逻辑程序 P1, P2，如果 P1 ⊆ P2，则 AS(P1) ⊆ AS(P2)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 13 / 21
. . . . . .
逻辑程序
.. 正程序 Herbrand模型性质
.
Proposition 1
..
.. ..
.
.任何正程序都有 Herbrand模型。
.
Theorem 1..
.. ..
.
.
正程序的任意两个 Herbrand模型的交集也是该程序的一个 Herbrand模
型。
.
Proposition 2
..
.. ..
.
.任何正程序有唯一的极小（最小）Herbrand模型。记为 AS(P)。
.
Proposition 3
..
.. ..
.
.两个逻辑程序 P1, P2，如果 P1 ⊆ P2，则 AS(P1) ⊆ AS(P2)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 13 / 21
. . . . . .
逻辑程序
.. 正程序 Herbrand模型性质
.
Proposition 1
..
.. ..
.
.任何正程序都有 Herbrand模型。
.
Theorem 1..
.. ..
.
.
正程序的任意两个 Herbrand模型的交集也是该程序的一个 Herbrand模
型。
.
Proposition 2
..
.. ..
.
.任何正程序有唯一的极小（最小）Herbrand模型。记为 AS(P)。
.
Proposition 3
..
.. ..
.
.两个逻辑程序 P1, P2，如果 P1 ⊆ P2，则 AS(P1) ⊆ AS(P2)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 13 / 21
. . . . . .
逻辑程序
.. 正程序 Herbrand模型性质
.
Proposition 1
..
.. ..
.
.任何正程序都有 Herbrand模型。
.
Theorem 1..
.. ..
.
.
正程序的任意两个 Herbrand模型的交集也是该程序的一个 Herbrand模
型。
.
Proposition 2
..
.. ..
.
.任何正程序有唯一的极小（最小）Herbrand模型。记为 AS(P)。
.
Proposition 3
..
.. ..
.
.两个逻辑程序 P1, P2，如果 P1 ⊆ P2，则 AS(P1) ⊆ AS(P2)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 13 / 21
. . . . . .
稳定模型
.. Outline
.
. .1 关于暑期讨论班
.
. .2 逻辑程序
.
. .3 稳定模型
.
. .4 相关阅读材料
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 14 / 21
. . . . . .
稳定模型
.. 逻辑程序中引入 ‘not’
逻辑程序中规则定义为如下形式：
A← A1, . . . , Am, not Am+1, . . . , not An.
引入 ‘not’，从而引入非单调的表达能力。
‘not’表示“推不出”，逻辑程序下的推出 (推不出)关系。
对于正程序有唯一的极小 Herbrand模型，对于一般逻辑程序极
小 Herbrand模型不是唯一的。(哪些才是合理的？)
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 15 / 21
. . . . . .
稳定模型
.. 逻辑程序中引入 ‘not’
逻辑程序中规则定义为如下形式：
A← A1, . . . , Am, not Am+1, . . . , not An.
引入 ‘not’，从而引入非单调的表达能力。
‘not’表示“推不出”，逻辑程序下的推出 (推不出)关系。
对于正程序有唯一的极小 Herbrand模型，对于一般逻辑程序极
小 Herbrand模型不是唯一的。(哪些才是合理的？)
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 15 / 21
. . . . . .
稳定模型
.. 逻辑程序中引入 ‘not’
逻辑程序中规则定义为如下形式：
A← A1, . . . , Am, not Am+1, . . . , not An.
引入 ‘not’，从而引入非单调的表达能力。
‘not’表示“推不出”，逻辑程序下的推出 (推不出)关系。
对于正程序有唯一的极小 Herbrand模型，对于一般逻辑程序极
小 Herbrand模型不是唯一的。(哪些才是合理的？)
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 15 / 21
. . . . . .
稳定模型
.. 逻辑程序中引入 ‘not’
逻辑程序中规则定义为如下形式：
A← A1, . . . , Am, not Am+1, . . . , not An.
引入 ‘not’，从而引入非单调的表达能力。
‘not’表示“推不出”，逻辑程序下的推出 (推不出)关系。
对于正程序有唯一的极小 Herbrand模型，对于一般逻辑程序极
小 Herbrand模型不是唯一的。(哪些才是合理的？)
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 15 / 21
. . . . . .
稳定模型
.. 稳定模型语义 (Stable Model Semantics)
The stable model semantics for logic programming
[Gelfond & Lifschitz 1988].
Assumption = Minimal Knowledge.
对于含 ‘not’的规则，我们不得不预先合理的假定一些知
识 (assumption)。所谓的合理在这里解释为：与最后推导出的知
识 (minimal knowledge)一致。
对于任意原子的集合 S， PS 定义为 P中按下列方式处理得到的程
序：
…1 如果规则体中有 not a，并且 a ∈ S，则删除这条规则；
…2 删除剩余的含 not 文字。
S是 P的稳定模型 iff S是 PS 的极小模型。
S = AS(PS)
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 16 / 21
. . . . . .
稳定模型
.. 稳定模型语义 (Stable Model Semantics)
The stable model semantics for logic programming
[Gelfond & Lifschitz 1988].
Assumption = Minimal Knowledge.
对于含 ‘not’的规则，我们不得不预先合理的假定一些知
识 (assumption)。所谓的合理在这里解释为：与最后推导出的知
识 (minimal knowledge)一致。
对于任意原子的集合 S， PS 定义为 P中按下列方式处理得到的程
序：
…1 如果规则体中有 not a，并且 a ∈ S，则删除这条规则；
…2 删除剩余的含 not 文字。
S是 P的稳定模型 iff S是 PS 的极小模型。
S = AS(PS)
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 16 / 21
. . . . . .
稳定模型
.. 稳定模型语义 (Stable Model Semantics)
The stable model semantics for logic programming
[Gelfond & Lifschitz 1988].
Assumption = Minimal Knowledge.
对于含 ‘not’的规则，我们不得不预先合理的假定一些知
识 (assumption)。所谓的合理在这里解释为：与最后推导出的知
识 (minimal knowledge)一致。
对于任意原子的集合 S， PS 定义为 P中按下列方式处理得到的程
序：
…1 如果规则体中有 not a，并且 a ∈ S，则删除这条规则；
…2 删除剩余的含 not 文字。
S是 P的稳定模型 iff S是 PS 的极小模型。
S = AS(PS)
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 16 / 21
. . . . . .
稳定模型
.. 稳定模型语义 (Stable Model Semantics)
The stable model semantics for logic programming
[Gelfond & Lifschitz 1988].
Assumption = Minimal Knowledge.
对于含 ‘not’的规则，我们不得不预先合理的假定一些知
识 (assumption)。所谓的合理在这里解释为：与最后推导出的知
识 (minimal knowledge)一致。
对于任意原子的集合 S， PS 定义为 P中按下列方式处理得到的程
序：
…1 如果规则体中有 not a，并且 a ∈ S，则删除这条规则；
…2 删除剩余的含 not 文字。
S是 P的稳定模型 iff S是 PS 的极小模型。
S = AS(PS)
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 16 / 21
. . . . . .
稳定模型
.. 稳定模型语义 (Stable Model Semantics)
The stable model semantics for logic programming
[Gelfond & Lifschitz 1988].
Assumption = Minimal Knowledge.
对于含 ‘not’的规则，我们不得不预先合理的假定一些知
识 (assumption)。所谓的合理在这里解释为：与最后推导出的知
识 (minimal knowledge)一致。
对于任意原子的集合 S， PS 定义为 P中按下列方式处理得到的程
序：
…1 如果规则体中有 not a，并且 a ∈ S，则删除这条规则；
…2 删除剩余的含 not 文字。
S是 P的稳定模型 iff S是 PS 的极小模型。
S = AS(PS)
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 16 / 21
. . . . . .
稳定模型
.. 稳定模型语义 (Stable Model Semantics)
The stable model semantics for logic programming
[Gelfond & Lifschitz 1988].
Assumption = Minimal Knowledge.
对于含 ‘not’的规则，我们不得不预先合理的假定一些知
识 (assumption)。所谓的合理在这里解释为：与最后推导出的知
识 (minimal knowledge)一致。
对于任意原子的集合 S， PS 定义为 P中按下列方式处理得到的程
序：
…1 如果规则体中有 not a，并且 a ∈ S，则删除这条规则；
…2 删除剩余的含 not 文字。
S是 P的稳定模型 iff S是 PS 的极小模型。
S = AS(PS)
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 16 / 21
. . . . . .
稳定模型
.. Stable Model性质
.
Theorem 2..
.. ..
.
.S是程序 P的 Herbrand模型当且仅当 S是 P
S 的 Herbrand模型。
.
Theorem 3..
.. ..
.
.程序 P的任何一个稳定模型都是 P的一个极小 Herbrand模型。
正程序有唯一的稳定模型，即该程序的极小模型；
有些程序没有稳定模型，例如 { p← not p. }；
有些程序有多个稳定模型，例如 { p← not q. q← not p. };
有些程序只有空集作为稳定模型，例如 { p← p. }；
一个程序的稳定模型彼此互不为子集。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 17 / 21
. . . . . .
稳定模型
.. Stable Model性质
.
Theorem 2..
.. ..
.
.S是程序 P的 Herbrand模型当且仅当 S是 P
S 的 Herbrand模型。
.
Theorem 3..
.. ..
.
.程序 P的任何一个稳定模型都是 P的一个极小 Herbrand模型。
正程序有唯一的稳定模型，即该程序的极小模型；
有些程序没有稳定模型，例如 { p← not p. }；
有些程序有多个稳定模型，例如 { p← not q. q← not p. };
有些程序只有空集作为稳定模型，例如 { p← p. }；
一个程序的稳定模型彼此互不为子集。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 17 / 21
. . . . . .
稳定模型
.. Stable Model性质
.
Theorem 2..
.. ..
.
.S是程序 P的 Herbrand模型当且仅当 S是 P
S 的 Herbrand模型。
.
Theorem 3..
.. ..
.
.程序 P的任何一个稳定模型都是 P的一个极小 Herbrand模型。
正程序有唯一的稳定模型，即该程序的极小模型；
有些程序没有稳定模型，例如 { p← not p. }；
有些程序有多个稳定模型，例如 { p← not q. q← not p. };
有些程序只有空集作为稳定模型，例如 { p← p. }；
一个程序的稳定模型彼此互不为子集。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 17 / 21
. . . . . .
稳定模型
.. Stable Model性质
.
Theorem 2..
.. ..
.
.S是程序 P的 Herbrand模型当且仅当 S是 P
S 的 Herbrand模型。
.
Theorem 3..
.. ..
.
.程序 P的任何一个稳定模型都是 P的一个极小 Herbrand模型。
正程序有唯一的稳定模型，即该程序的极小模型；
有些程序没有稳定模型，例如 { p← not p. }；
有些程序有多个稳定模型，例如 { p← not q. q← not p. };
有些程序只有空集作为稳定模型，例如 { p← p. }；
一个程序的稳定模型彼此互不为子集。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 17 / 21
. . . . . .
稳定模型
.. Stable Model性质
.
Theorem 2..
.. ..
.
.S是程序 P的 Herbrand模型当且仅当 S是 P
S 的 Herbrand模型。
.
Theorem 3..
.. ..
.
.程序 P的任何一个稳定模型都是 P的一个极小 Herbrand模型。
正程序有唯一的稳定模型，即该程序的极小模型；
有些程序没有稳定模型，例如 { p← not p. }；
有些程序有多个稳定模型，例如 { p← not q. q← not p. };
有些程序只有空集作为稳定模型，例如 { p← p. }；
一个程序的稳定模型彼此互不为子集。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 17 / 21
. . . . . .
稳定模型
.. Stable Model性质
.
Theorem 2..
.. ..
.
.S是程序 P的 Herbrand模型当且仅当 S是 P
S 的 Herbrand模型。
.
Theorem 3..
.. ..
.
.程序 P的任何一个稳定模型都是 P的一个极小 Herbrand模型。
正程序有唯一的稳定模型，即该程序的极小模型；
有些程序没有稳定模型，例如 { p← not p. }；
有些程序有多个稳定模型，例如 { p← not q. q← not p. };
有些程序只有空集作为稳定模型，例如 { p← p. }；
一个程序的稳定模型彼此互不为子集。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 17 / 21
. . . . . .
稳定模型
.. Stable Model性质
.
Theorem 2..
.. ..
.
.S是程序 P的 Herbrand模型当且仅当 S是 P
S 的 Herbrand模型。
.
Theorem 3..
.. ..
.
.程序 P的任何一个稳定模型都是 P的一个极小 Herbrand模型。
正程序有唯一的稳定模型，即该程序的极小模型；
有些程序没有稳定模型，例如 { p← not p. }；
有些程序有多个稳定模型，例如 { p← not q. q← not p. };
有些程序只有空集作为稳定模型，例如 { p← p. }；
一个程序的稳定模型彼此互不为子集。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 17 / 21
. . . . . .
稳定模型
.. 稳定模型语义举例
企鹅与鸟的例子:
.
Example 4
..
.. ..
.
.
fly(X)← bird(X), not nfly(X). /*通常，鸟会飞 */
bird(X)← penguin(X). /*企鹅是鸟 */
nfly(X)← penguin(X), not fly(X). /*通常，企鹅不会飞 */
penguin(tweety). /* tweety是企鹅 */
tweety会不会飞？
此程序的所有稳定模型为：
{ bird(tweety), penguin(tweety), fly(tweety) },
{ bird(tweety), penguin(tweety), nfly(tweety) }.
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 18 / 21
. . . . . .
稳定模型
.. 稳定模型语义举例
企鹅与鸟的例子:
.
Example 4
..
.. ..
.
.
fly(X)← bird(X), not nfly(X). /*通常，鸟会飞 */
bird(X)← penguin(X). /*企鹅是鸟 */
nfly(X)← penguin(X), not fly(X). /*通常，企鹅不会飞 */
penguin(tweety). /* tweety是企鹅 */
tweety会不会飞？
此程序的所有稳定模型为：
{ bird(tweety), penguin(tweety), fly(tweety) },
{ bird(tweety), penguin(tweety), nfly(tweety) }.
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 18 / 21
. . . . . .
稳定模型
.. 稳定模型语义举例
企鹅与鸟的例子:
.
Example 4
..
.. ..
.
.
fly(X)← bird(X), not nfly(X). /*通常，鸟会飞 */
bird(X)← penguin(X). /*企鹅是鸟 */
nfly(X)← penguin(X), not fly(X). /*通常，企鹅不会飞 */
penguin(tweety). /* tweety是企鹅 */
tweety会不会飞？
此程序的所有稳定模型为：
{ bird(tweety), penguin(tweety), fly(tweety) },
{ bird(tweety), penguin(tweety), nfly(tweety) }.
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 18 / 21
. . . . . .
稳定模型
.. 稳定模型语义举例
企鹅与鸟的例子:
.
Example 4
..
.. ..
.
.
fly(X)← bird(X), not nfly(X). /*通常，鸟会飞 */
bird(X)← penguin(X). /*企鹅是鸟 */
nfly(X)← penguin(X), not fly(X). /*通常，企鹅不会飞 */
penguin(tweety). /* tweety是企鹅 */
tweety会不会飞？
此程序的所有稳定模型为：
{ bird(tweety), penguin(tweety), fly(tweety) },
{ bird(tweety), penguin(tweety), nfly(tweety) }.
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 18 / 21
. . . . . .
稳定模型
.. 经典否定
前面的介绍中，没有涉及经典否定 ¬。在程序中其实可以加入经典
否定:
L← L1, . . . , Lm, not Lm+1, . . . , not Ln.
其中， L和 Li 是文字，即原子或原子的否定 (¬)。
对于含经典否定的正逻辑程序，仍然可以定义极小 Herbrand模型，
只不过此时 Herbrand解释对应为文字的集合。
程序的 Herbrand模型是一致的（不同时存在 p和 ¬p）或者是文字
的全体集合 Lit。在此约束下，逻辑程序保持前面介绍的各种性质。
程序的 Answer set为一个文字集 S，满足 S = AS(PS)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 19 / 21
. . . . . .
稳定模型
.. 经典否定
前面的介绍中，没有涉及经典否定 ¬。在程序中其实可以加入经典
否定:
L← L1, . . . , Lm, not Lm+1, . . . , not Ln.
其中， L和 Li 是文字，即原子或原子的否定 (¬)。
对于含经典否定的正逻辑程序，仍然可以定义极小 Herbrand模型，
只不过此时 Herbrand解释对应为文字的集合。
程序的 Herbrand模型是一致的（不同时存在 p和 ¬p）或者是文字
的全体集合 Lit。在此约束下，逻辑程序保持前面介绍的各种性质。
程序的 Answer set为一个文字集 S，满足 S = AS(PS)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 19 / 21
. . . . . .
稳定模型
.. 经典否定
前面的介绍中，没有涉及经典否定 ¬。在程序中其实可以加入经典
否定:
L← L1, . . . , Lm, not Lm+1, . . . , not Ln.
其中， L和 Li 是文字，即原子或原子的否定 (¬)。
对于含经典否定的正逻辑程序，仍然可以定义极小 Herbrand模型，
只不过此时 Herbrand解释对应为文字的集合。
程序的 Herbrand模型是一致的（不同时存在 p和 ¬p）或者是文字
的全体集合 Lit。在此约束下，逻辑程序保持前面介绍的各种性质。
程序的 Answer set为一个文字集 S，满足 S = AS(PS)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 19 / 21
. . . . . .
稳定模型
.. 经典否定
前面的介绍中，没有涉及经典否定 ¬。在程序中其实可以加入经典
否定:
L← L1, . . . , Lm, not Lm+1, . . . , not Ln.
其中， L和 Li 是文字，即原子或原子的否定 (¬)。
对于含经典否定的正逻辑程序，仍然可以定义极小 Herbrand模型，
只不过此时 Herbrand解释对应为文字的集合。
程序的 Herbrand模型是一致的（不同时存在 p和 ¬p）或者是文字
的全体集合 Lit。在此约束下，逻辑程序保持前面介绍的各种性质。
程序的 Answer set为一个文字集 S，满足 S = AS(PS)。
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 19 / 21
. . . . . .
相关阅读材料
.. Outline
.
. .1 关于暑期讨论班
.
. .2 逻辑程序
.
. .3 稳定模型
.
. .4 相关阅读材料
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 20 / 21
. . . . . .
相关阅读材料
.. 下一阶段阅读文献
Gelfond, M. and Lifschitz, V.
The Stable Model Semantics For Logic Programming.
In Proceedings of the Fifth International Conference on Logic
Programming (ICLP-88), pages 1070–1080, 1988.
Gelfond, M. and Lifschitz, V.
Classical Negation in Logic Programs and Disjunctive Databases.
New Generation Computing 9:365–385, 1991.
Jianmin Ji and Guoqiang Jin (USTC) Introduction to ASP August 17, 2010 21 / 21
关于暑期讨论班
逻辑程序
稳定模型
相关阅读材料