人工智能逻辑

约 2207 个字 5 张图片 预计阅读时间 6 分钟

任课教师：廖备水

课后作业

• HW1
• HW2
• HW3
• HW4

i cannot read these

Lec1: Introduction

推理形式

1. 演绎推理
   • “保真”：若前提为真，则结论必为真
     • 这也是其有效性的描述：演绎论证是有效的当且仅当它是保真的

     • 论证形式

       豆子&袋子的例子可看作演绎推理的一个实例
       演绎论证的形式即用字母表示。
       一个论证形式是有效的当且仅当对该论证形式中的变项所做的任一解释都满足保真性。
   • 从一般原理到特殊情况（类似集合中不断取子集）
2. 非单调推理
   • 对于任何命题，若依据某个知识库中的知识均可以明确判断其真假时，知识库中知识是完备的
   • 在上面的演绎推理中，每条命题都蕴含着知识，如果其知识不完备或不确定，则无法直接套用，得到正确结论。
     • 不确定性：缺少准确的知识得到完全可靠的结论
     • 不完备性：缺失部分信息
   • 为了解决这种问题，可以在演绎推理中添加正常性假设（基于假设的演绎推理）
     • 鸟会飞，除非证明它不正常
     • Tweety是鸟（可以被“证明Tweety不正常”推翻）
     • 所以Tweety会飞
   • 假设会被新信息推翻，从而结论也会被推翻
   • 称这种结论可被推翻的推理为非单调推理
   • 可以把包含例外的知识表示为可废止规则，可看作“常识”，可能有例外。
     • 一般情况下，如果A则B（B可被反面证据推翻）
3. 归纳推理
   • 从特定事例观察推断出一般规律
   • 用归纳强度刻画归纳论证的好坏
4. 溯因推理
   • 观察现象寻找合理解释
5. 关于论证的推理
   • 论辩图怎么画

AIL的主要研究方向

what is this

Lec2: 知识的表示与推理

知识表示语言

• 表示：用一个集合的元素来表示一个集合的元素
  • 一种表示知识的语言由初始符号列表和语法规则组成
• 公式表示：\(\{\neg, \land, \lor, (, )\}\)
• 有向图表示：\(G = \{V, E\}\)

用特定符号语言描述的公式或结构，由我们对公式/结构中的元素所做的不同解释，可表示现实世界中的不同知识。

推理

• 符号级推理：形式上的计算
  • 一阶逻辑中最基本的规则是肯定前件式（MP规则）：\(a \rightarrow b, a \vdash b\)，\(\vdash\) 表示形式可推演关系。
• 知识级推理：推理的前提与结论在语义上的映射关系
  • 在经典演绎推理中表现为语义蕴涵关系：若 \(a \models b\)，则当前提 \(a\) 为真，结论 \(b\) 为真
  • 在论证推理中，不一定是语义蕴含，需要建立的是从论证图到可接受的论证集合的映射关系

推理系统的特性

• 系统内特性：一个逻辑系统内部各个成分具有的特定性质，如演绎系统中，包括有效的语义蕴涵模式、正确的推理形式等。
• 系统元特性：
  • 完备性：给定前提集合 \(\Gamma\)，若其语义蕴含（\(\models\)）公式 \(A\)，那么从形式上可以从 \(\Gamma\) 推出 \(A\)（\(\vdash\)）。
  • 可靠性：给定前提集合 \(\Gamma\)，若其可从形式推出（\(\vdash\)）公式 \(A\)，那么其语义蕴含（\(\models\)）公式 \(A\)。

Lec3: 命题逻辑

命题公式

1. 命题符号（就是用个字母表示的命题）是公式（原子公式）。
2. 若 \(A\) 是公式，则 \(\neg A, (A \land B), (A \lor B), (A \rightarrow B), (A \leftrightarrow B)\) 也是公式。
3. 有限次使用 1 和 2 的规则，得到的都是公式。

联结词：\(\neg, \land, \lor, \rightarrow, \leftrightarrow\)

真假赋值：对命题符号赋予真假值（即一个函数，定义域是命题符号集合，值域是 \(\{0, 1\}\)（感觉就是命题的真假））

逻辑推论

给定一组命题公式集合 \(\Phi\) 和一个命题公式 \(\phi\)，则 \(\phi\) 是 \(\Phi\) 的逻辑推论，当且仅当 \(\forall v, \Phi^v = 1 \Rightarrow \phi^v = 1\)，记作 \(\Phi \models \phi\)。

类似蕴涵式，如果 \(\Phi^v = 0\)，则 \(\phi^v\)的取值无所谓

\(\Phi\) 是空集合时，\(\models \phi\) 当且仅当 \(\phi\) 是永真式。（此时也称 \(\phi\) 具有有效性）

推论

• \(ϕ\) 是可满足的 当且仅当 \(¬ϕ\) 不是有效的；
• \(ϕ\) 是有效的 当且仅当 \(¬ϕ\) 不是可满足的。
  • 这两个很显然，可以构想一个真值表
• 即可以通过检验一个公式的可满足性来判断这个公式的有效性。

逻辑推论

若 \(\Phi \models \phi\) 且 \(\phi \models \Phi\)，则称 \(\Phi\) 和 \(\phi\) 是等价的，记作 \(\Phi \equiv(|=|) \phi\)。

常见的语义等价

• \(p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)\)
• \(p \rightarrow q \equiv \neg p \lor q\)
• 德摩根定律：\(\neg (p \land q) \equiv \neg p \lor \neg q\)，\(\neg (p \lor q) \equiv \neg p \land \neg q\)

定理

给定 \(\phi \equiv \psi\)，则 \(\phi\) 是 \(\varphi\) 的一部分。把 \(\varphi\) 中的 \(\phi\) 替换为 \(\psi\) 得到 \(\varphi'\)，则 \(\varphi \equiv \varphi'\)

• 范式：见离散笔记
  • 合取取交，析取取并
  • 注意范式的每个子式只包含原子命题（的否定）的析取/合取，例如 \(\neg (\neg p)\) 什么都不是

消解推演系统

通过形式推演（之前的推理过程）

合取起来的子式记为集合的元素（放在大括号里），析取的子式放在中括号里。

\([p, q]\) 与 \([\neg p, r]\) 消解得到 \([q, r]\)，类比即 \(p \lor \neg p \equiv 1\)

消解推演系统

消解推演系统是可靠的，但不完备。消解可看作取交

proof

霍恩子句

对于消解系统而言，对于公式的的一些子类，对其可满足性的判断又更加有效的方法。

霍恩子句：子句 \(L_1 \land L_2 \land \cdots \land L_n\) 中如果至多包含一个正文字，那么这个子句就是霍恩子句。

• 四种形式：
  • \(p \leftarrow q_1, q_2, \cdots, q_n (n \neq 0)\)
  • \(p \leftarrow (n = 0)\)
  • \(\leftarrow q_1, q_2, \cdots, q_n (n \neq 0)\)
  • \([空]\)

SAT

实现可满足性的推理引擎称为 SAT（Satisfiability）求解器：在给定一个公式的前提下，寻找一个真值赋值，使得公式为真。（即寻找真值表中某一行，使目标公式为真）

该算法是 NP 完全的

经典算法：DPLL

例

设 \(\Phi = \{[p,q, \neg r], [\neg p, \neg q], [r], [p, \neg q]\}, \Sigma = {p,q,r}\)。SAT 算法的执行过程：

• 单位传播规则：令 \(r \rightarrow 1\)，得到简化的字句集合 \(\{[p,q], [\neg p, \neg q], [p, \neg q]\}\)
• 分裂规则
  • \(p \rightarrow 0\)，得到简化：\(\{[q], [\neg q]\}\)，令 \(q \rightarrow 1\) 得到空子句，公式不成立，回溯
  • \(p \rightarrow 1\)，得到简化：\(\{[\neg q]\}\)，令 \(\neg q \rightarrow 0\)，即可满足

Lec 4: 一阶逻辑

不同于 Lec 3 中的公式，为了描述更日常的命题，需要引入对象、论域、函词、谓词、量词等概念。个体常元和个体变元统称项。例如，“张三的哥哥是学生”可以表示为 \(F(g(ZS))\)，其中 \(F\) 表示“...是学生”，\(g\) 表示“是...的哥哥”。

Definitions

• 论域：所有被讨论对象的集合。
• 个体：域中的元素，即被讨论的对象。
• 常元：用于表示确定对象的符号。
• 变元：用于表示给定论域上的任意一个对象的符号。
• 函词：给定一个论域，从一组个体到一个个体的映射关系。
• 项：
  1. 个体常元和个体变元是项。
  2. 如果 \(t_1, t_2, ... t_n\)是项，\(f\) 是 n 元函词，那么 \(f(t1, t2, \cdots, t_n)\) 是项。
  3. 有限次使用(1)(2)生成的是项。
• 谓词：描述个体之间的关系。谓词包含着可放置讨论对象的位置，即 空位。 空位的数量称为谓词的元数。用一元谓词表示的关系称为个体的性质。

一阶语言

• \(F(t_1, t_2, \cdots, t_n)\) 是原子公式，其中 \(F\) 是 n 元关系符号，\(t_1, t_2, \cdots, t_n\) 是项。
• 如果 \(t_1,t_2\) 是项，那么 \((t_1 \equiv t_2)\) 是原子公式。
• 如果 \(\phi\) 和 \(\Phi\) 是公式，且 \(x\) 是出现于 \(\phi\) 中的自由变元，则 \((\neg \phi), (\phi \land \Phi), (\phi \lor \Phi), (\phi \rightarrow \Phi), (\forall x \phi), (\exists x \phi)\) 都是公式。
• 有限次使用上述三条规则生成的都是公式。

代换

代换 \(\theta\) 是一个有限的对子集合 \(\{x_1/t_1, x_2/t_2, \cdots, x_n/t_n\}\)，其中 \(x_i\) 是变元，\(t_i\) 是项。代换 \(\theta\) 作用于公式 \(\phi\)，得到 \(\phi\theta\)，是将 \(\phi\) 中的所有自由变元 \(x_i\) 替换为 \(t_i\) 得到的公式。

语义

评论