符号学习简介

一阶逻辑与逻辑程序(上)

(Press ? for help, n and p for next and previous slide)


戴望州

南京大学人工智能学院
2022年-春季

https://daiwz.net

FOIL的缺点

目标概念:\(triangle(X,Y,Z)\)

  • 正样例:\(triangle(3,4,5), triangle(8,12,7)\)
  • 负样例:\(triangle(1,2,9), triangle(4,5, 10)\)

FOIL的缺点

背景知识

\begin{eqnarray*} larger\_than(X,Y)&\leftarrow &success(Y,X)\\ larger\_than(X,Y)&\leftarrow &success(Y,Z), larger\_than(X,Z)\\ sum(X,Y,Z)&\leftarrow &Z=X+Y \end{eqnarray*}

FOIL的缺点

假设概念:\(triangle(X,Y,Z)\leftarrow larger\_than(X,A)\)

覆盖样例:\(\langle X,Y,Z,A\rangle\)

  • 正样例:\(\langle 3,4,5,4\rangle, \langle 3,4,5,5\rangle, \langle 3,4,5,6\rangle, \ldots\)
  • 负样例:\(\langle 1,2,9,2\rangle, \langle 1,2,9,3\rangle, \langle 1,2,9,4\rangle, \ldots\)

FOIL的缺点

背景知识不能是一阶逻辑公式

\begin{eqnarray*} larger\_than(X,Y) &\leftarrow &success(Y,X)\\ larger\_than(X,Y) &\leftarrow &success(Y,Z), larger\_than(X,Z)\\ sum(X,Y,Z)&\leftarrow &Z=X+Y \end{eqnarray*}

路径图

符号学习简介・一阶逻辑与逻辑程序(上)

  1. 什么是逻辑
  2. 一阶逻辑语言

这算逻辑吗?

L的推理:

  • 所有心脏麻痹的被害人都是罪犯
    • KILLER具有强烈的正义感
  • 被害人姓名、样貌几乎都被公开过
    • KILLER杀人需要知道姓名、样貌
  • 第一起案件在新宿,罪犯在行凶时暴毙
  • 电视只在关东地区直播,假L当场死亡
    • KILLER存在
    • KILLER是日本人

这算逻辑吗?

因果关系不是逻辑

这算逻辑吗?

\[e^{i\pi}+1=0\]

这算逻辑吗?

特定领域的知识不是逻辑

这算逻辑吗?

黄金戒律:己所不欲勿施于人

这算逻辑吗?

道德律令不是逻辑

亚里士多德三段论

\begin{align} \text{快乐} & \text{ 是 } \text{短暂的}\\ \text{永恒} & \text{ 是 } \text{快乐的}\\ \hline \end{align}

亚里士多德三段论

\begin{align} \text{快乐} & \text{ 是 } \text{短暂的}\\ \text{永恒} & \text{ 是 } \text{快乐的}\\ \hline \text{永恒} & \text{ 是 } \text{短暂的} \end{align}

命题逻辑

\(A\) \(B\) \(A\rightarrow B\)

一阶逻辑(谓词逻辑)

\begin{align} \text{快乐} & \text{ 是 } \text{短暂的}\\ \text{永恒} & \text{ 是 } \text{快乐的}\\ \hline \text{永恒} & \text{ 是 } \text{短暂的} \end{align}

一阶逻辑(谓词逻辑)

\begin{align} \forall X(p(X)\rightarrow q(X))&\\ p(c)\\ \hline q(c)& \end{align}

什么是逻辑?

到底什么是逻辑?

什么是逻辑?

逻辑是关于

苏格拉底(Socrates):

  • 辩论是为了寻找
  • 就算被驳倒了也可能有所收获——

我们预设

在一些情况下,我们可以谈论(Truth)

下述预设大概没什么问题

  • 如果我们可以有意义地谈论命题\(A\)和\(B\)是否为真,那么我们也可以有意义地谈论“并非\(A\)”、“\(A\)并且\(B\)”等等是否为真。
  • 如果我们可以谈论,某个人,例如“苏格拉底会死”是否为真,那么我们也可以有意义地谈论“所有人都会死”或“存在一个不会死的人”是否为真。

作为“终极”概念的真概念

对任何概念/性质/集合\(P\)以及对象\(a\),当我们问\(a\)是不是落在概念\(P\)之下,我们可以问\(Pa\)是不是的。

作为“终极”概念的真概念

  • 令\(T=\{\sigma\mid \sigma\text{ 是真的}\}\),考虑句子\(\tau\)说的是\(\neg T\tau\)
  • 问题:\(\tau\)是不是真的?

塔斯基(Tarski):

  • 我们只能谈论特定领域的真:\(\text{Th }\mathfrak{A} = \{\sigma\mid \mathfrak{A}\models\sigma\}\)
  • \(\text{Th }\mathfrak{A}\)不是\(\mathfrak{A}\)中可定义的
  • 日常语言的是不可定义的

很遗憾

我们无法一劳永逸地把握

什么是逻辑

逻辑谈论的只是关于的一些规律

什么是逻辑

逻辑谈论的只是关于的一些普遍性规律

什么是逻辑

“要让我们的推理有规可循,唯一方法是把它做得像数学那样扎扎实实,这样我们一眼就可以看到错误所在,当人们之间产生争议的时候,我们只要说:让我们坐下来算一算(let us calculate),不需要更多的忙乱就可以看到谁是对的。”

——莱布尼茨(The Art of Discovery)

符号学习简介・一阶逻辑与逻辑程序(上)

  1. 什么是逻辑
  2. 一阶逻辑语言

一阶逻辑的语言

符号:

  • 逻辑符号
    • 括号:\((\),\()\)
    • 命题连词:\(\neg\),\(\rightarrow\)
    • 量词:\(\forall\)
    • 变元:\(V_1\),\(V_2\),\(\ldots\)

一阶逻辑的语言

符号:

  • 非逻辑符号(参数符号)
    • (*)常数符号:\(c_1\),\(c_2\),\(\ldots\)
    • (*)函数符号:\(f_1\),\(f_2\),\(\ldots\)
    • (*)谓词符号:\(p_1\),\(p_2\),\(\ldots\)
    • 等词:\(\equiv\)(可有可无)
  • (*)可以没有,也可以有无穷多
  • 存在能行的函数\(g,h:\mathbb{N}\mapsto\mathbb{N}^+\)告诉我们:
    • 每个\(f_i\)是\(g(i)\)-元函数符号
    • 每个\(p_i\)是\(h(i)\)-元函数符号

各种一阶逻辑语言

我们说“给定一个一阶逻辑语言”就是规定各类参数符号的集合。

  • 集合论语言:\(\{\equiv,\in\}\)
  • 初等数论的语言:\(\{\equiv, 0,s,<,+,\cdot\}\)
  • 序关系的语言:\(\{\equiv,R\}\)

各种一阶逻辑语言

我们说“给定一个一阶逻辑语言”就是规定各类参数符号的集合。

  • 集合论语言:\(\{\equiv,\in\}\)
  • 初等数论的语言:\(\{\equiv, 0,s,<,+,\cdot\}\)
  • 序关系的语言:\(\{\equiv,R\}\)

项(term)

给定一个一阶逻辑语言\(\mathcal{L}\),定义\(\mathcal{L}\)中的为:

  • 每个变元\(V_i\)是项
  • 每个\(\mathcal{L}\)中的常数符号是项
  • 如果\(t_1,\ldots,t_n\)是项且\(f\)是\(\mathcal{L}\)中的\(n\)元函数符号,那么\(f(t_i,t_2,\ldots,t_n)\)也是项

例子:初等数论语言\(\{\equiv, 0,s,<,+,\cdot\}\)中的项

  • \(V_3\)
  • \(s(0)\)
  • \(s(V_1)+s(s(0))\)

合式公式(W.F.F.)

给定一个一阶逻辑语言\(\mathcal{L}\),定义\(\mathcal{L}\)中的合式公式(well-formed formula)为:

  • 如果\(t_1, t_2\)是项,那么\(t_1\equiv t_2\)是公式(若\(\mathcal{L}\)中有等词)
  • 如果\(t_1,\ldots,t_n\)是项,且\(p\)是一个\(n\)元谓词符号,那么\(p(t_1,\ldots,t_n)\)是公式
  • 上述公式被称为原子公式(atomic formulae, atoms)
  • 如果\(\alpha,\beta\)是合式公式,那么\((\neg\alpha),(\alpha\rightarrow\beta)\)也是
  • 如果\(\alpha\)是合式公式,\(X\)是变元,那么\(\forall X\alpha\)也是

注意:\(t_1, t_2, \ldots\)、\(\alpha, \beta, \ldots\)、\(X,Y,\ldots\)是元语言中的符号

缩写规定

常见的缩写:

  • \(\alpha\vee \beta=_\mathsf{abbr} \neg\alpha\rightarrow \beta\)
  • \(\alpha\wedge \beta=_\mathsf{abbr} \neg(\alpha\rightarrow \neg\beta)\)
  • \(\alpha\leftrightarrow \beta=_\mathsf{abbr} (\alpha\rightarrow\beta)\wedge(\beta\rightarrow\alpha)\)
  • \(\exists X\alpha=_\mathsf{abbr} \neg\forall X\neg \alpha\)

我们习惯称\(\forall X\)为全称量词,称\(\exists X\)为存在量词

一阶逻辑的例子

鬼的存在性:

  1. 如果存在存在着的鬼,则鬼存在
  2. 存在着的鬼当然存在
  3. 鬼存在

一阶逻辑的例子

一阶算数语言:\(\{0,\equiv, <, s, +, \cdot\}\)

  1. 零不是任何数的后继
  2. 两个数后继相等,当且仅当它们相等
  3. 数学归纳法
  4. \(X\)是素数

自由出现与约束出现

例子

给定\(\{a_i\mid i\in\mathbb{N}\}\)

\[ b=\sum_{i=0}^k a_i \]

自由出现与约束出现

例子

给定\(\{a_i\mid i\in\mathbb{N}\}\)

\[ b=\sum_{\color{#cc9393}{i}=0}^{\color{#8CD0D3}{k}} a_{\color{#cc9393}{i}} \]

自由出现与约束出现

例子

给定\(\{a_i\mid i\in\mathbb{N}\}\)

\[ b=\sum_{\color{#cc9393}{j}=0}^{\color{#8CD0D3}{k}} a_{\color{#cc9393}{j}} \]

自由出现与约束出现

对公式\(\alpha\)递归定义\(X\)在\(\alpha\)中自由出现(free)

  • 当\(\alpha\)是原子公式:\(X\)在\(\alpha\)中自由出现
  • 当\(\alpha=\neg\beta\):\(X\)在\(\beta\)中自由出现
  • 当\(\alpha=\beta\rightarrow\gamma\):\(X\)在\(\beta\)或\(\gamma\)中自由出现
  • 当\(\alpha=\forall Y\beta\):\(X\)在\(\beta\)中自由出现,且\(X\neq Y\)

\(X\)在\(\forall X\alpha\)中的出现称做约束出现(bound)
我们称一个合式公式\(\alpha\)是语句 (sentence),当且仅当没有变元在 \(\alpha\)中自由出现

替换(substitution)

我们定义元语言中的一个表达方式\(\alpha\theta\),其中\(\theta=\{V_1/t_1, V_2/t_2, \ldots\}\)

首先对\(u\)递归定义\(u\theta\),其中\(\theta=\{X/t\}\)

  • 当\(u=Y\): \[ u\theta=\begin{cases} t, &\text{若$X=Y$}\\ Y, &\text{否则} \end{cases} \]
  • 当\(u=f(t_1, \ldots, t_n)\):\(u\theta=f(t_1 \theta,\ldots,t_n \theta)\)

替换(substitution)

例子

  • \(u=V_1, \theta=\{V_1/f(V_1, V_2)\}, u\theta= f(V_1, V_2)\)
  • \(u=V_2, \theta=\{V_1/c\}, u\theta= V_2\)
  • \(u=f(V_1, g(V_2)), \theta=\{V_2/g(c)\}, u\theta= f(V_1, g(g(c)))\)

替换(substitution)

其次对公式\(\alpha\)递归定义\(\alpha\theta\),其中\(\theta=\{X/t\}\)

  • 当\(\alpha=t_1\equiv t_2\):\(\alpha\theta=t_1 \theta\equiv t_2 \theta\)
  • 当\(\alpha=p(t_1,\ldots,t_n)\):\(\alpha\theta=p(t_1 \theta, \ldots, t_n \theta)\)
  • 当\(\alpha=\neg\beta\):\(\alpha\theta=(\neg\beta)\theta = \neg\beta\theta\)
  • 当\(\alpha=\beta\rightarrow \gamma\):\(\alpha\theta=(\beta\rightarrow\gamma)\theta=\beta\theta\rightarrow\gamma\theta\)
  • 当\(\alpha=\forall Y\beta\): \[\alpha\theta=(\forall Y\beta)\theta=\begin{cases} \alpha, &\text{若$X=Y$}\\ \forall Y(\beta\theta), &\text{否则} \end{cases} \]

替换(substitution)

例子

  • \(\alpha=p(V_1, f(V_2))\rightarrow\exists V_2 p(V_1, V_2), \theta=\{V_1/c\}\)
  • \(\alpha=p(V_1, f(V_2))\rightarrow\exists V_2 p(V_1, V_2), \theta=\{V_2/c\}\)
  • \(\alpha=p(V_1, f(V_2))\rightarrow\exists V_2 p(V_1, V_2), \theta=\theta_1\theta_2, \theta_1=\{V_1/V_2\}, \theta_2=\{V_2/V_1\}\)

小结

一阶逻辑部分的小结

  1. 逻辑是什么
  2. 一阶逻辑与命题逻辑的区别