(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的推理:
- 所有心脏麻痹的被害人都是罪犯
- 被害人姓名、样貌几乎都被公开过
- 第一起案件在新宿,罪犯在行凶时暴毙
- 电视只在关东地区直播,假L当场死亡
亚里士多德三段论
\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)\)也是项
合式公式(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\)也是
缩写规定
常见的缩写:
- \(\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\}\)
一阶逻辑部分的小结
- 逻辑是什么
- 一阶逻辑与命题逻辑的区别