知识表示

一阶谓词逻辑

命题

非真即假，陈述句，唯一的真值。

如果满足上述条件而暂时无法确定真值也算，明天是晴天、存在外星人都是命题。

谓词

$$P(x_1,x_2,...,x_n)$$

$P$是谓词名（表示一种定性），$x_1,x_2,...,x_n$是个体。谓词中包含的个体数就是谓词的元数。

例：

老张是老师：$Teacher(Zhang)$ 或 $Is-a(Zhang,Teacher)$;

5>3：$Greater(5,3)$;

小李的妹妹与小张的哥哥结婚：$Married(Sister(Li),Brother(Zhang))$

其中$Sister(Li),Brother(Zhang)$ 是函数，这种可以递归调用，比如小李的祖父$father(father(Li))$.

谓词公式

连接词

$\wedge$，合取；

$\vee$，析取；

$\mathrm{\neg }$，非；

$\to$，蕴涵（$P\to Q$：若$P$则$Q$）只有前真后假整体才为假；

$\leftrightarrow$，等价（$P\leftrightarrow Q$：$P$当且仅当$Q$​）。

例：

如果Jones造了一个传感器，且这个传感器不能用，那么他要么晚上修理要么第二天把它交给工程师：

$$\begin{array}{c}Produces(Jones,Sensor)\wedge \mathrm{\neg }Works(Sensor)\to Fix(Jones,Sensor,Evening)\\ \vee Give(Sensor,Engineer,Next-day)\end{array}$$

量词

$\mathrm{\forall }$，全称；

$\mathrm{\exists }$，存在。

例：

某个工程师可以操作车床：

$$(\mathrm{\exists }x)[Engineer(x)\to Operates(x,Lathe)]$$

每个雇员都有一个经理：

$$(\mathrm{\forall }x)(\mathrm{\exists }y)[Employee(x)\to Manager(y,x)]$$

有一个人是所有雇员的经理：

$$(\mathrm{\exists }y)(\mathrm{\forall }x)[Employee(x)\to Manager(y,x)]$$

每个人都有喜欢的人：

$$(\mathrm{\forall }x)(\mathrm{\exists }y)Love(x,y)$$

有的人被所有人喜欢：

$$(\mathrm{\exists }x)(\mathrm{\forall }y)Love(y,x)$$

兼爱：

$$(\mathrm{\exists }x)(\mathrm{\forall }y)Love(x,y)$$

理想社会：

$$(\mathrm{\forall }x)(\mathrm{\forall }y)Love(x,y)$$

谓词公式

上边几种符号有限组合就是谓词公式。

优先级从高到低：

$$\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow$$

量词辖域

$$\mathrm{\exists }x(P(x,y)\to Q(x,y))\vee R(x,y)$$

$(P(x,y)\to Q(x,y))$是量词$\mathrm{\exists }x$的辖域，里面的x受$\mathrm{\exists }x$约束，$R(x,y)$中的$x$不受约束，是自由变元。

换名规则

自由变元随便换（不能用约束变元的名），约束变元统一换：

$$(\mathrm{\forall }x)P(x,y)isequalto(\mathrm{\forall }z)P(z,t)$$

谓词公式的性质

解释

一个解释就是命题公式中所有变元的一组真值。一个解释能给公式确定唯一一个真值。

永真性

任何解释下公式都为真就是永真。

可满足性

至少一个解释下为真就是可满足。

不可满足性

任何一个解释下都不为真就是不可满足，即永假。

等价性（等价式）

交换律

$$P\vee Q\iff Q\vee P$$

结合律

$$(P\vee Q)\vee R\iff P\vee (Q\vee R)$$

分配律

$$P\vee (Q\wedge R)\iff (P\vee Q)\wedge (P\vee R)$$

De Morgen律

$$\mathrm{\neg }(P\vee Q)\iff \mathrm{\neg }P\wedge \mathrm{\neg }Q$$

拆括号内部全取反，与或互换。

双重否定律

$$\mathrm{\neg }\mathrm{\neg }P\iff P$$

吸收律

$$\begin{gathered} P\vee (P\wedge Q)\iff P \\ P\wedge (P\vee Q)\iff P \end{gathered}$$

补余（否定）律

$$\begin{gathered} P\vee \mathrm{\neg }P\iff T \\ P\wedge \mathrm{\neg }P\iff F \end{gathered}$$

连接词 化归律

$$P\to Q\iff \mathrm{\neg }P\vee Q$$

用来处理箭头

逆否律

$$P\to Q\iff \mathrm{\neg }Q\to \mathrm{\neg }P$$

量词转换律

$$\begin{gathered} \mathrm{\neg }(\mathrm{\exists }x)P\iff (\mathrm{\forall }x)(\mathrm{\neg }P) \\ \mathrm{\neg }(\mathrm{\forall }x)P\iff (\mathrm{\exists }x)(\mathrm{\neg }P) \end{gathered}$$

不存在$x$满足$P$ 和 任意$x$都不满足$P$。

量词分配律

$$(\mathrm{\forall }x)(P\wedge Q)\iff (\mathrm{\forall }x)P\wedge (\mathrm{\forall }x)Q$$

谓词公式的永真蕴涵

如果$P\to Q$永真，则公式$P$永真蕴涵$Q$，记作$P\Rightarrow Q$，$Q$为$P$的逻辑结论，$P$为$Q$的前提。

假言推理

$$P,P\to Q\Rightarrow Q$$

由$P$为真和$P\to Q$为真，可以推出$Q$​为真。

拒取式

$$\mathrm{\neg }Q,P\to Q\Rightarrow \mathrm{\neg }P$$

假言三段论

$$P\to Q,Q\to R\Rightarrow P\to R$$

构造性两难

$$P\vee Q,P\to R,Q\to R\Rightarrow R$$

全称固化

$$(\mathrm{\forall }x)P(x)\Rightarrow P(y)$$

$y$代表任一个体。

存在固化

$$(\mathrm{\exists }x)P(x)\Rightarrow P(y)$$

$y$是个体域中某一个使$P(y)$为真的个体。

反证法

$$\begin{gathered} P_1,P_2,...P_n\Rightarrow Q\mathrm{当}\mathrm{且}\mathrm{仅}\mathrm{当} \\ (P_1\wedge P_2\wedge ...\wedge P_n)\wedge \mathrm{\neg }Q\mathrm{永}\mathrm{假} \end{gathered}$$

后半部分的意思就是前边那些P都满足时Q不可能是假的。

置换与合一

在基于谓词的推理过程中，会出现谓词名相同但其个体不同的情况，此时不能直接进行匹配的，需要先进行置换。在推理过程中，寻找项与项之间的置换，使不同谓词表达式一致的过程叫做合一的过程。

置换

置换是用置换项替换变量。置换项可以是常量、函数或变量。

定义

置换是形如$\{t_1/x_1,t_2/x_2,...,t_n/x_n\}$的有限集合，其中$t_1,t_2,...,t_n$是置换项，$x_1,x_2,...,x_n$是互不相同的变元，$t_i/x_i$表示用$t_i$替换$x_i$​。

例：

$\{g(a)/x,f(x)/y\}$是置换。

$\{g(y)/x,f(x)/y\}$不是置换。用$g(y)$替换$x$，再用$f(g(y))$置换$y$​，循环置换。

规则

只能用常量、函数或变量置换变量，不能用变量置换常量和函数，不能用常量和函数置换不同的常量和函数。

$x_i$不能出现在$t_i$中，如$g(x)/x$​不是置换。

不能循环置换，如$\{y/x,x/y\}$不是一个置换。

合一

定义

设公式集$F=\{F_1,F_2,...,F_n\}$，若存在一个置换$\theta$，使得$F_1\theta =F_2\theta =...=F_n\theta$，则$\theta$是$F$的一个合一，$F_1,F_2,...,F_n$是可合一的。

例：

$$F=\{P(x,y,f(y)),P(a,g(x),z)\}$$

则它的一个合一是$\lambda =\{a/x,g(a)/y,f(g(a))/z\}$。

因为：

对于$P(x,y,f(y))$，用$\lambda$置换完之后是$P(a,g(a),f(g(a)))=P(a,g(a),z)$；

对于$P(a,g(x),z)$，置换之后$P(a,g(a),z)$，跟上面一样。

一般来说一个公式集的合一不唯一。

最一般合一

定义

设$\sigma$是公式集$F$的一个合一，如果对$F$的任一合一$\theta$都存在一个置换$\lambda$，使得$\theta =\sigma \cdot \lambda$，则称$\sigma$是一个最一般合一。

一个公式集的任一合一都可由最一般合一和一个置换的合成置换得到。

最一般合一是唯一的。

例：

$F=\{P(x),P(f(y))\}$，则$\sigma =\{f(y)/x\}$是它的一个合一，$\theta =\{f(a)/x,a/y\}$也是它的一个合一。

引入置换$\lambda =\{a/y\}$，$\sigma$与$\lambda$的合成置换$\sigma \cdot \lambda =\{f(a)/x,a/y\}=\theta$​

最一般合一的求法

$$W=\{P(a,x,f(g(y))),P(z,f(z),f(u))\}$$

求$W$的最一般合一置换，其实就是要找到一个置换$\sigma$使得$E_1\cdot \sigma =E_2\cdot \sigma$.

步骤：

先找出第一个不一致集$\{a,z\}$，用常量换变量构造第一个置换${\sigma }_1=\{a/z\}$​

$$W_1=W\cdot {\sigma }_1=\{P(a,x,f(g(y))),P(a,f(a),f(u))\}$$

之后找第二个不一致集$\{x,f(a)\}$，用常量换变量构造第二个置换${\sigma }_2=\{f(a)/x\}$

$$W_2=W\cdot {\sigma }_2=\{P(a,f(a),f(g(y))),P(a,f(a),f(u))\}$$

最后一个不一致集$\{g(y),u\}$，用常量换变量构造第三个置换${\sigma }_3=\{u/g(y)\}$

$$\begin{gathered} W_2=W\cdot {\sigma }_2=\{P(a,f(a),f(u)),P(a,f(a),f(u))\} \\ =\{P(a,f(a),f(u))\} \end{gathered}$$

则$W$的最一般合一置换为

$$\sigma =\{{\sigma }_1,{\sigma }_2,{\sigma }_3\}=\{a/z,f(a)/x,u/g(y)\}$$

产生式

产生式

确定性规则知识

$$\begin{gathered} IFPTHENQ \\ P\to Q \end{gathered}$$

不确定性规则知识

$$\begin{gathered} IFPTHENQ(\mathrm{置}\mathrm{信}\mathrm{度}) \\ P\to Q(\mathrm{置}\mathrm{信}\mathrm{度}) \end{gathered}$$

确定性事实性知识

$$\begin{gathered} (\mathrm{对}\mathrm{象}，\mathrm{属}\mathrm{性}，\mathrm{值}) \\ (\mathrm{关}\mathrm{系}，\mathrm{对}\mathrm{象}1，\mathrm{对}\mathrm{象}2) \end{gathered}$$

例：

老李40岁：$(Li,Age,40)$;

老李和老王是朋友：$(Friend,Li,Wang)$.

不确定性事实性知识

$$\begin{gathered} (\mathrm{对}\mathrm{象}，\mathrm{属}\mathrm{性}，\mathrm{值}，\mathrm{置}\mathrm{信}\mathrm{度}) \\ (\mathrm{关}\mathrm{系}，\mathrm{对}\mathrm{象}1，\mathrm{对}\mathrm{象}2，\mathrm{置}\mathrm{信}\mathrm{度}) \end{gathered}$$

例：

老李很有可能40岁：$(Li,Age,40,0.9)$;

老李和老王不太会是朋友：$(Friend,Li,Wang,0.1)$.

蕴含式与产生式

产生式可以表示不确定知识，并且包括操作、规则、变换、算子、函数等，这些蕴含式都做不到。

产生式系统

规则库

r1: IF 该三角形有两边相等 THEN 该三角形是等腰三角形
r2: IF 该三角形两边相等 AND  第三边也相等 THEN 该三角形是等边三角形
r3: IF 该三角形有一个钝角 THEN 该三角形是钝角三角形
r4: IF 该三角形有一个直角 THEN 该三角形是直角三角形
r5: IF 该三角形不存在钝角或直角 THEN 该三角形是锐角三角形
r6: IF 该三角形是等腰三角形 AND 有一个钝角 THEN 该三角形是等腰钝角三角形
r7: IF 该三角形是等腰三角形 AND 不存在钝角或直角 THEN 该三角形是等腰锐角三角形
r8: IF 该三角形是等腰三角形 AND 有一个直角 THEN 该三角形是等腰直角三角形

推理机构工作过程

$$\mathrm{该}\mathrm{三}\mathrm{角}\mathrm{形}\mathrm{只}\mathrm{有}\mathrm{两}\mathrm{边}\mathrm{相}\mathrm{等}，\mathrm{有}\mathrm{一}\mathrm{个}\mathrm{直}\mathrm{角}$$

取出r1，符合

此时

$$\mathrm{该}\mathrm{三}\mathrm{角}\mathrm{形}\mathrm{只}\mathrm{有}\mathrm{两}\mathrm{边}\mathrm{相}\mathrm{等},\mathrm{是}\mathrm{等}\mathrm{腰}\mathrm{三}\mathrm{角}\mathrm{形}$$

之后的条目均不符合，直到：取出r8，符合

$$\mathrm{该}\mathrm{三}\mathrm{角}\mathrm{形}\mathrm{只}\mathrm{有}\mathrm{两}\mathrm{边}\mathrm{相}\mathrm{等},\mathrm{是}\mathrm{等}\mathrm{腰}\mathrm{三}\mathrm{角}\mathrm{形},\mathrm{是}\mathrm{直}\mathrm{角}\mathrm{等}\mathrm{腰}\mathrm{三}\mathrm{角}\mathrm{形}$$

特点：

自然性、模块性、有效性、清晰性；效率不高、不能表示有结构的知识。

框架表示法

框架表示法类似面向对象，通过属性组合来描述一件事。

例如产生式规则：如果头疼且发烧就是感冒，框架表示为：

框架名: <诊断1>
	前提：条件1 头疼
	     条件2 发烧
	结论：感冒

特点：

结构性、继承性、自然性。