【高级人工智能】国科大《高级人工智能》符号主义笔记 + 考试记忆版

国科大《高级人工智能》罗老师部分——符号主义笔记

• 罗老师上课很有意思，但是这部分内容还是挺难理解的，需要仔细思考
• 今年考试题目这部分跟往年不一样，老师讲的重点（A搜索+归结原理）也没考😅

文章目录

• 几个概念
• 一、语义 Entailment 蕴含
• • 1.定义
  • 2.命题逻辑：语法与语义
  • 3.命题逻辑中的知识库KB
  • 4.什么是valid和satisfiable
• 二、形式推演 Deduction
• • 1.定义：
  • 2.归结原理（Resolution）
• 三、Inference over Horn and Definite Clauses
• • 1.一些概念
  • 2.肯定式推理Modus Ponens
• 四、一阶谓词逻辑
• • 1.基本形式
  • 2.实例化
  • 3.合一化（理解为某种替代）
  • 4.一阶谓词逻辑的归结原理(重要)
  • 5.逻辑编程：Prolog
• 五、模糊逻辑
• • 1.定义
  • 2.模糊集的表示
• 六、考试题目整理
• • 1.选择题
  • 2.简答题
  • 3.综合应用题

几个概念

• 逻辑：表示信息以便得出结论的形式语言
• 语法：定义语言中的句子
• 语义：定义句子的意思
• 逻辑研究的内容：研究形式化定义的 sentences 之间的关系
• 两个角度：
  • 语义：entailment 蕴含，逻辑推导
  • 语法：inference 演绎，形式推演

    

一、语义 Entailment 蕴含

1.定义

是基于语义的句子(即句法)之间的一种关系

K

B

⊨

α

KB\models\alpha

KB⊨α

知识库KB蕴涵句子

α

\alpha

α，当且仅当

α

\alpha

α在KB为真的所有世界（代指 Model）中为真。

（这个定义要记住）

Model：使sentence为真的assignment（真值指派），即为model

重点：当且仅当

M

(

K

B

)

⊆

M

(

α

)

M(KB)\subseteq M(\alpha)

M(KB)⊆M(α)时，

K

B

⊨

α

KB\models\alpha

KB⊨α（证

⊨

\models

⊨，找Model）

2.命题逻辑：语法与语义

语法（Syntax）：定义语言中的句子；

命题（Proposition）：一个陈述句，要么是对的，要么是错的；

原子命题（Atomic propositions）：最小的命题；

文字（Literals）：原子命题或它们的否定；

语义（Semantics）：每个模型指定每个命题符号的真/假。

注：

⊨

\models

⊨不是命题的合法句子

证明：

语义等价转换

3.命题逻辑中的知识库KB

KB：满足命题逻辑语法的 sentence 的集合；

假设：这组 sentence 中，一共有n个原子命题；

真值指派（truth assignment）：对每个原子命题赋值；

一共有2^n种真值指派，其中：使得KB中的每个sentence都为真的真值指派，就是KB的model；

在此基础上，在命题逻辑中，我们可以明确的定义：

K

B

⊨

α

KB\models\alpha

KB⊨α

• Entailment (

  ⊨

  \models

  ⊨)：逻辑上的概念，刻画两组sentence之间的关系；

• Implication (¬,∧,∨,⟹,⟺)：Proposition（命题）之间的一种运算子，用真值表刻画语义。

4.什么是valid和satisfiable

• 一个句子是valid，如果他在所有模型都是 true
• 一个句子是satisfiable，如果他在存在true的模型

  

  

  几个证明题：

  

  （之前考过）

  

  5.总结：蕴含的三个等价条件：

  

二、形式推演 Deduction

1.定义：

有两种：11条规则 + 1条规则（归结原理）

Inference：可靠性证明+完备性证明（见上图）

2.归结原理（Resolution）

1）合取范式Conjunctive Normal Form (CNF—universal)

目的是将一些列命题用∧和∨连起来，具体步骤如下：

2）归结：

3）证明归结原理的可靠性与完备性：

可靠性（Sound）：If

K

B

⊢

α

KB\vdash\alpha

KB⊢α，that

K

B

⊨

α

KB\models\alpha

KB⊨α

sound的证明方法很简单，只要check一次resolution的过程是正确的(利用真值表)，实际上就是去证明这个子句合取第二个子句可以蕴含下面那个子句。【用真值指派的方法】

完备性：If

K

B

⊨

α

KB\models\alpha

KB⊨α，that

K

B

⊢

α

KB\vdash\alpha

KB⊢α

4）归结原理+A*搜索

• A*搜索：要设计好一个启发式函数，可以通过原问题的松弛问题的解来进行求解
• 初始状态：{KB，!a}
• 目标：goal（goal包含空集）
• 每次的动作：选一个可以归结的原子命题进行归结。
• 启发函数：所有包含a的句子里找一个最短的，假定这个最短的句子是有k个原子命题。现在已经有!a了，那至少也要做k次归结才能归结出空集，那启发函数就是h()=k。这个估计耗散一定小于等于真实耗散，它是可采纳的。
• 例外的情况：KB推不出a，那就不会有包含空集的goal，那就如果找不到可以归结的原子命题，那搜索就停止。

三、Inference over Horn and Definite Clauses

1.一些概念

“负文字”(negative literal)：文字包含否定符号(¬)；否则称为“正文字”(positive literal)。

Definite clause：有且只有一个正文字

Horn clause：最多只有一个正文字

2.肯定式推理Modus Ponens

可靠性证明：If

K

B

⊢

α

KB\vdash\alpha

KB⊢α，that

K

B

⊨

α

KB\models\alpha

KB⊨α

与归结原理一样，用真值表，即证明：

完备性证明：If

K

B

⊨

α

KB\models\alpha

KB⊨α，that

K

B

⊢

α

KB\vdash\alpha

KB⊢α

注：p是包含变量的句子，p-theta就是按theta赋值，所以p也是蕴含p-theta的

四、一阶谓词逻辑

1.基本形式

全称-存在转化：

2.实例化

3.合一化（理解为某种替代）

理解为某种替换（合一的算子）

4.一阶谓词逻辑的归结原理(重要)

1）归结原理（-替换）

2）合取范式

①去掉存在量词及其修饰的变量使每个都使全称量词修饰的变量

②消去biconditionals（

⇔

\Leftrightarrow

⇔）和implications（

⇒

\Rightarrow

⇒）

③把

⌝

\urcorner

┐放到里面去

④标准化变量（有些变量不是同一个object，要用不同的变量表示）

⑤Skolemize：用关于x的函数表示依赖于x的变量

⑥通用的全称量词删掉

⑦展开在析取上的合取

Eg：

3）归结策略

删除策略：删除纯文字、删除重言式

限制策略：支持集策略、单文字子句策略、祖先过滤策略

4）GMP的可靠性证明

5.逻辑编程：Prolog

主要思想：编知识库KB

（1）语法（https://ruanyifeng.com/blog/2019/01/prolog.html）

①friend(X, Y) :- friend(Y,X).

• X和Y都是大写，表示这是两个变量；
• 符号:-表示推理关系，含义是只要右边的表达式friend(Y, X)为true，那么左边的表达式friend(X, Y)也为true。

②onesidelove(X, Y) :- loves(X, Y), + loves(Y,X).

• 如果一条规则取决于多个条件同时为true，则条件之间使用逗号分隔；
• 如果一条规则取决于某个条件为false，则在条件之前加上+表示否定。

（2）有时会推出错误的答案（它的实现不sound），有时正确答案也推不出（不complete）【考过】

五、模糊逻辑

（没讲推理）

• 模糊性：事件发生的程度，而不是是否发生
• 随机性：事情发生的不确定性

1.定义

2.模糊集的表示

为了能够表示出论域中的元素与其隶属度之间的对应关系，扎德引入了一种模糊集的表示方式：先为论域中的每个元素都标上其隶属度，然后再用+号把它们连接起来：

连续论域：

3.模糊关系的运算

模糊关系合成：（类似矩阵乘法）

4.用模糊逻辑表示自然语言

六、考试题目整理

1.选择题

• prolog概念
• “永真”、“永假、”“不可满足”的判断

2.简答题

• 知识表示
• 自动化的知识推理
• 集合运算符交集并集符号 和 逻辑句子连接词中合取和析取符号
• 描述逻辑蕴含

  ⊨

  \models

  ⊨ 和 逻辑连接词蕴含⟹

3.综合应用题

• 设计形式推演规则：任意合取范式作为输入，推出的结论时可靠但不完备的
• Modus Ponens规则证明中间的一部分