符号学习简介
一阶逻辑与逻辑程序（上）
(Press ? for help, n and p for next and previous slide)
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*}
路径图
符号学习简介・一阶逻辑与逻辑程序（上）
- 什么是逻辑
- 一阶逻辑语言
这算逻辑吗？
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）
符号学习简介・一阶逻辑与逻辑程序（上）
- 什么是逻辑
- 一阶逻辑语言
一阶逻辑的语言
符号：
- 逻辑符号
- 括号：\((\)，\()\)
- 命题连词：\(\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\)为存在量词
一阶逻辑的例子
鬼的存在性：
- 如果存在存在着的鬼，则鬼存在
- 存在着的鬼当然存在
- 鬼存在
一阶逻辑的例子
一阶算数语言：\(\{0,\equiv, <, s, +, \cdot\}\)
- 零不是任何数的后继
- 两个数后继相等，当且仅当它们相等
- 数学归纳法
- \(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\}\)
小结
一阶逻辑部分的小结
- 逻辑是什么
- 一阶逻辑与命题逻辑的区别