知识表示

Chromatic Vizier...About 18 min

知识表示

把有关信息关联在一起所形成的信息结构称为知识。把有关信息关联在一起所形成的信息结构称为知识。

知识的性质

相对正确性：1＋1＝10 在不同的进制下有不同的正确性；

不确定性：知识并不总是只有“真”和“假”两种状态。以下原因导致了这条性质：

① 随机性：我有八成的把握打中目标。

② 模糊性：高个子适合于打篮球。

③ 不完全性：莲花清瘟对新冠病毒有一定功效。

④ 经验性：土干了就给花浇水。

可表示与可利用性

知识表示的分类

分类方式	分类
形成	知识由概念、命题、公理、定理、规则和方法组成
层次	表层知识、深层知识
确定性程度	确定性知识、不确定性知识
等级	元知识、非元知识
作用	陈述性知识、过程性知识

过程性知识表示

过程性知识一般是表示如何做的知识，是有关系统变化、问题求解过程的操作、演算和行为的知识。这种知识一般隐含在面向过程程序中，机器无法从程序的编码中抽取出知识。

这种知识的描述表示控制规则和控制结构的知识，给出一些客观规律，告诉怎么做。

例如矩阵求逆程序，程序中描述了矩阵的逆和求解方法的知识。

陈述式知识表示

描述系统的状态、环境和条件，以及问题的概念、定义和事实。

一阶谓词逻辑

命题

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

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

谓词

P (x_{1}, x_{2}, . . ., x_{n})

$P$ 是谓词名（表示一种定性）， $x_{1}, x_{2}, . . ., x_{n}$ 是个体。谓词中包含的个体数就是谓词的元数。

例：

老张是老师： $T e a c h e r (Z h a n g)$ 或 $I s - a (Z h a n g, T e a c h e r)$ ;

5>3： $G r e a t e r (5, 3)$ ;

小李的妹妹与小张的哥哥结婚： $M a r r i e d (S i s t e r (L i), B r o t h e r (Z h a n g))$

其中 $S i s t e r (L i), B r o t h e r (Z h a n g)$ 是函数，这种可以递归调用，比如小李的祖父 $f a t h e r (f a t h e r (L i))$ .

谓词公式

连接词

$\land$ ，合取；

$\lor$ ，析取；

$\neg$ ，非；

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

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

例：

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

\begin{matrix} P r o d u c e s (J o n e s, S e n s o r) \land \neg W o r k s (S e n s o r) \to F i x (J o n e s, S e n s o r, E v e n i n g) \\ \lor G i v e (S e n s o r, E n g i n e e r, N e x t - d a y) \end{matrix}

量词

$\forall$ ，全称；

$\exists$ ，存在。

例：

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

(\exists x) [E n g i n e e r (x) \to O p e r a t e s (x, L a t h e)]

每个雇员都有一个经理：

(\forall x) (\exists y) [E m p l o y e e (x) \to M a n a g e r (y, x)]

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

(\exists y) (\forall x) [E m p l o y e e (x) \to M a n a g e r (y, x)]

每个人都有喜欢的人：

(\forall x) (\exists y) L o v e (x, y)

有的人被所有人喜欢：

(\exists x) (\forall y) L o v e (y, x)

兼爱：

(\exists x) (\forall y) L o v e (x, y)

理想社会：

(\forall x) (\forall y) L o v e (x, y)

谓词公式

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

优先级从高到低：

\neg, \land, \lor, \to, \leftrightarrow

量词辖域

\exists x (P (x, y) \to Q (x, y)) \lor R (x, y)

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

换名规则

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

(\forall x) P (x, y) i s e q u a l t o (\forall z) P (z, t)

谓词公式的性质

解释

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

永真性

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

可满足性

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

不可满足性

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

等价性（等价式）

交换律

P \lor Q \Leftrightarrow Q \lor P

结合律

(P \lor Q) \lor R \Leftrightarrow P \lor (Q \lor R)

分配律

P \lor (Q \land R) \Leftrightarrow (P \lor Q) \land (P \lor R)

De Morgen律

\neg (P \lor Q) \Leftrightarrow \neg P \land \neg Q

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

双重否定律

\neg \neg P \Leftrightarrow P

吸收律

P \lor (P \land Q) \Leftrightarrow P P \land (P \lor Q) \Leftrightarrow P

补余（否定）律

P \lor \neg P \Leftrightarrow T P \land \neg P \Leftrightarrow F

连接词化归律

P \to Q \Leftrightarrow \neg P \lor Q

用来处理箭头

逆否律

P \to Q \Leftrightarrow \neg Q \to \neg P

量词转换律

\neg (\exists x) P \Leftrightarrow (\forall x) (\neg P) \neg (\forall x) P \Leftrightarrow (\exists x) (\neg P)

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

量词分配律

(\forall x) (P \land Q) \Leftrightarrow (\forall x) P \land (\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$ 为真。

拒取式

\neg Q, P \to Q \Rightarrow \neg P

假言三段论

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

构造性两难

P \lor Q, P \to R, Q \to R \Rightarrow R

全称固化

(\forall x) P (x) \Rightarrow P (y)

$y$ 代表任一个体。

存在固化

(\exists x) P (x) \Rightarrow P (y)

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

反证法

P_{1}, P_{2}, . . . P_{n} \Rightarrow Q 当 且 仅 当 (P_{1} \land P_{2} \land . . . \land P_{n}) \land \neg Q 永 假

后半部分的意思就是前边那些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}}$ ，若存在一个置换 $θ$ ，使得 $F_{1} θ = F_{2} θ = . . . = F_{n} θ$ ，则 $θ$ 是 $F$ 的一个合一， $F_{1}, F_{2}, . . ., F_{n}$ 是可合一的。

例：

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

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

因为：

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

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

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

最一般合一

定义

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

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

最一般合一是唯一的。

例：

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

引入置换 $λ = {a / y}$ ， $σ$ 与 $λ$ 的合成置换 $σ \cdot λ = {f (a) / x, a / y} = θ$

最一般合一的求法

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

求 $W$ 的最一般合一置换，其实就是要找到一个置换 $σ$ 使得 $E_{1} \cdot σ = E_{2} \cdot σ$ .

步骤：

先找出第一个不一致集 ${a, z}$ ，用常量换变量构造第一个置换 $σ_{1} = {a / z}$

W_{1} = W \cdot σ_{1} = {P (a, x, f (g (y))), P (a, f (a), f (u))}

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

W_{2} = W \cdot σ_{2} = {P (a, f (a), f (g (y))), P (a, f (a), f (u))}

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

W_{2} = W \cdot σ_{2} = {P (a, f (a), f (u)), P (a, f (a), f (u))} = {P (a, f (a), f (u))}

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

σ = {σ_{1}, σ_{2}, σ_{3}} = {a / z, f (a) / x, u / g (y)}

产生式

确定性规则知识

I F P T H E N Q P \to Q

不确定性规则知识

I F P T H E N Q (置 信 度) P \to Q (置 信 度)

确定性事实性知识

(对 象 ， 属 性 ， 值) (关 系 ， 对 象 1 ， 对 象 2)

例：

老李40岁： $(L i, A g e, 40)$ ;

老李和老王是朋友： $(F r i e n d, L i, W a n g)$ .

不确定性事实性知识

(对 象 ， 属 性 ， 值 ， 置 信 度) (关 系 ， 对 象 1 ， 对 象 2 ， 置 信 度)

例：

老李很有可能40岁： $(L i, A g e, 40, 0.9)$ ;

老李和老王不太会是朋友： $(F r i e n d, L i, W a n g, 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 该三角形是等腰直角三角形

推理机构工作过程

该 三 角 形 只 有 两 边 相 等 ， 有 一 个 直 角

取出r1，符合

此时

该 三 角 形 只 有 两 边 相 等, 是 等 腰 三 角 形

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

该 三 角 形 只 有 两 边 相 等, 是 等 腰 三 角 形, 是 直 角 等 腰 三 角 形

特点：

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

框架表示法

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

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

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

结构

一个框架由若干个“槽”组成，一个槽又可划分为若干个“侧面”。一个槽用于描述所论对象某一方面的属性，一个侧面用于描述相应属性的一个方面。

<框架名>
槽名1:		侧面名1	    值1,值2,…,值p1
			 侧面名2		 值1,值2,…,值p2
			 …
			 侧面名m1	      值1,值2,…,值pm1
槽名2:		侧面名1		值1,值2,…,值q1
			 侧面名2		 值1,值2,…,值q2
			 …
			 侧面名m2	      值1,值2,…,值qm2
…
槽名n:		侧面名1		值1,值2,…,值r1
			 侧面名2		 值1,值2,…,值r2
			 …
			 侧面名mn	     值1,值2,…,值rmn
约束:		    约束条件1
			 约束条件2
			 …
			 约束条件n

例如：

框架名：<教师>
		姓名：单位(姓、名)
		年龄：单位(岁)
		性别：范围(男、女)
			   缺省：男
		职称：范围(教授、副教授、讲师、助教)
			   缺省：讲师
		部门：单位(系，教研室)
		住址：<住址框架>
		工资：<工资框架>
		开始工作时间：单位(年、月)
		截止时间：单位(年、月)
			  缺省：现在