第三章确定性推理(运算问题，与作业题难度相当)
谓词公式的等价式：
•
•
•
•
•
•
•
•
•
• (1) 双重否定率 ¬ ¬ P ⇔ P (2) 交换率 (P∨Q) ⇔ (Q∨P) ， ( P∧Q) ⇔ ( Q∧P) (3) 结合率 (P∨Q) ∨R ⇔ P ∨(Q∨R) (P∧Q) ∧R ⇔ P ∧(Q∧R) (4) 分配率 P ∨(Q∧R) ⇔ (P∨Q) ∧(P∨R) P ∧(Q∨R) ⇔ (P∧Q) ∨(P∧R) (5) 摩根定律 ¬ (P∨Q) ⇔ P ∧Q ¬ (P∧Q) ⇔ P ∨Q (6) 吸收率 P ∨(P∧Q) ⇔ P P ∧(P∨Q) ⇔ P
(7) 补余率 P ∨P ⇔ T, P ∧P ⇔ F
(8) 连词化归率 P →Q ⇔ ¬P ∨Q
PQ ⇔ (P→Q) ∧(Q→P)
PQ ⇔ (P∧Q) ∨(Q∧P)
(9) 量词转换率 ¬ (∃x)P ⇔ (∀x)( ¬ P)
¬ (∀x)P ⇔ (∃x) (¬ P)
(10) 量词分配率 (∀x) (P∧Q) ⇔ (∀x)P ∧(∀x)Q
(∃x) (P∨Q) ⇔ (∃x)P ∨(∃x)Q
常用的永真蕴含式如下：
(1) 化简式 P ∧Q ⇒ P ， P ∧Q ⇒ Q
(2) 附加式 P ⇒ P ∨Q ， Q ⇒ P ∨Q
(3) 析取三段论 ﹁ P, P ∨Q ⇒ Q
(4) 假言推理 P, P →Q ⇒ Q
(5) 拒取式 ¬Q, P →Q ⇒ P
(6) 假言三段论 P →Q, Q →R ⇒P →R
(7) 二难推理 P ∨Q, P →R, Q →R ⇒ R
(8) 全称固化 (∀x)P(x) ⇒ P(y)
其中，y 是个体域中的任一个体，依此可消去谓词公式中的全称量词。
(9) 存在固化 (∃x)P(x) ⇒ P(y)
其中，y 是个体域中某一个可以使P(y)为真的个体，依此可消去谓词公式中的存在量词。
子句集的化简
(1) 消去连接词“→”和“”
• P →Q ⇔﹁ P ∨Q
• PQ ⇔ (P∧Q) ∨(﹁P ∧﹁Q)
(2) 减少否定符号的辖域
• ﹁(﹁P) ⇔ P
• ﹁(P∧Q) ⇔﹁P ∨﹁Q
• ﹁(P∨Q) ⇔﹁P ∧﹁Q
• ﹁ (∀x)P(x) ⇔ (∃x) ﹁P(x)
• ﹁ (∃x)P(x) ⇔ (∀x) ￢P(x) • • • • • • • • • • • • • • • • • • • •
(3) 对变元标准化（将y 变为z ）
(4) 化为前束范式(所有量词都移到公式的左边)
(5) 消去存在量词(用Skolem 函数f(x1，x2 ,…, xn)替换)
(6) 化为Skolem 标准形(等价关系P ∨(Q∧R) ⇔ (P∨Q) ∧(P∨R))
(7) 消去全称量词(省掉全称量词)
(8) 消去合取词(去掉∧得到子句集)
(9) 更换变量名称（x 换为y ）
第六章不确定性推理公式（计算都要）
P (A i ) ⨯P (B /A i ) 全概率公式和Bayes 公式 P (A i |B ) =i =1, 2, , n n P (A j ) ⨯P (B /A j ) ∑P (B ) =∑P (A i ) ⨯P (B |A i ) j =1 i =1一、CF 模型
CF(H, E)=MB(H, E)-MD(H, E)
⎧1, 信任增长度 若P (H ) =1⎪MB (H , E ) =⎨max{P (H |E ), P (H )}-P (H ) , 否则⎪1-P (H ) ⎩
⎧1, 不信任增长度 若P (H ) =0⎪MD (H , E ) =min{P (H |E ), P (E )}-P (H ) ⎨ , 否则⎪-P (H ) ⎩
可信度
当MB(H, E)>0时，MD(H, E)=0
当MD(H, E)>0时，MB(H, E)=0
0≤MB (H , E ) ≤1, 0≤MD (H , E ) ≤1, -1≤CF (H , E ) ≤1
P (⌝H |E ) -P (⌝H ) (1-P (H |E )) -(1-P (H )) = MD (⌝H , E ) =-P (⌝H ) -(1-P (H )) -P (H |E ) +P (H ) -(P (H |E ) -P (H )) ==-(1-P (H )) -(1-P (H ))
P (H |E ) -P (H ) ==MB (H , E ) (信任增长度) 1-P (H )
CF(H,E)+CF(﹁H,E)=(MB(H,E)-MD(H,E))+(MB(﹁H,E)-MD(﹁H,E))
=(MB(H,E)-0)+(0-MD(﹁H,E)) (由互斥性)
=MB(H,E)-MD(﹁H,E)=0
它说明：(1)对H 的信任增长度等于对非H 的不信任增长度；(2)对H 的可信度
与非H 的可信度之和等于0；(3)可信度不是概率，不满足P(H)+P(﹁H)=1 和 0≤P(H),P(﹁H) ≤ 1
n
∑CF (H i , E ) ≤1
i =1合取CF(E)=min{CF(E1), CF(E2), … ,CF(En)}
析取CF(E)=max{CF(E1), CF(E2), … ,CF(En)}
不确定性的更新公式CF(H)=CF(H, E)×max{0, CF(E)}
E1与E2对H 的综合可信度
⎧CF 1(H ) +CF 2(H ) -CF 1(H ) ⨯CF 若CF 1(H ) ≥0 ⎪2(H )
且CF 2(H ) ≥ ⎪0
CF (H ) =⎪⎨CF 1(H ) +CF 2(H ) +CH 1(H ) ⨯CF 2(H ) 若CF 1(H )
⎪与
⎩1-min CF 1(H ) , CF 2(H ) CF 2(H ) 异号
二、主观Bayes 方法
IF E THEN (LS, LN) H
(LS, LN)用来表示该知识的知识强度，LS(充分性度量) 和LN(必要性度量) P (E |
LS =H )
P (E |⌝H )
LN =P (⌝E |H ) 1-P (E |H
P (⌝E |⌝H ) =)
1-P (E |⌝H )
P (H |E ) =P (E |H ) ⨯P (H )
P (E )
P (⌝H |E ) =P (E |⌝H ) ⨯P (⌝H )
P (E )
P (H |E ) P (E |
P (⌝H |E ) =H )
P (E |⌝H ) ⨯P (H )
P (⌝H )
P (X ) P (X )
O (X ) =1-P (X ) 或O (X ) =P (⌝X )
O (H |E ) =P (E |H )
P (E |⌝H ) ⨯O (H )
O (H |E ) =LS ⨯O (H )
同理可得到关于LN 的公式：
P (H |⌝E ) P (⌝E |H ) P (H )
P (⌝H |⌝E ) =P (⌝E |⌝H ) ⨯P (⌝H )
O (H |⌝E ) =LN ⨯O (H )
① LS>1且LN
② LS1
③ LS=LN=1
⎧当E 为假时
概率与几率之间的关系 O (E ) =P (E ) =⎪0
⎨∝当E 为真时
1-P (E ) ⎪⎩(0, ∝) 当E 非真也非假时 (6.1)(6. 2) (6.3)(6.4)
组合证据不确定性的计算
E=E1 AND E2 AND … AND En
已知在当前观察S 下，每个单一证据Ei 有概率P (E1|S), P(E2|S), … ,P(En|S)，则 P(E|S)=min{ P(E1|S), P(E2|S), … ,P(En|S)}
E=E1 OR E2 OR … OR En
已知在当前观察S 下，每个单一证据Ei 有概率P(E1|S), P(E2|S), … ,P(En|S)，则 P(E|S)=max{ P(E1|S), P(E2|S), … ,P(En|S)}
不确定性的更新
1. 证据肯定为真时，P(E)=P(E|S)=1
H 的先验几率更新为后验几率的公式为：O(H|E)=LS×O(H)
P (H |E ) =LS ⨯P (H )
(LS -1) ⨯P (H ) +1(6.5)
2. 当证据E 肯定为假时，P(E)=P(E|S)=0，P(﹁E)=1
H 的先验几率更新为后验几率的公式为：O(H|﹁E)=LN×O(H)
P (H |⌝E ) =LN ⨯P (H )
(LN -1) ⨯P (H ) +1(6.6)
3. 当证据既非真假时
P(H|E)=P(H|E)×P(E|S)+P(H|﹁E) ×P(﹁E|S) (6.7)
(1)P(E|S)=1；P(﹁E|S)=0
LS ⨯
P (H |S ) =P (H |E ) =P (H )
(LS -1) ⨯P (H ) +1
(2)P(E|S)=0；P(﹁E|S)=1
P (H |S ) =P (H |⌝E ) =LN ⨯P (H )
(LN -1) ⨯P (H ) +1
(3)P(E|S)=P(E)；E 与S 无关
P (H |S ) =P (H |E ) ⨯P (E |S ) +P (H |⌝E ) ⨯P (⌝E |S )
=P (H |E ) ⨯P (E ) +P (H |⌝E ) ⨯P (⌝E ) =P (H )
(4) P(E/S)为其它值
⎧
⎪P (H |⌝E ) +P (H ) -P (H |⌝E ) ⨯P (E |S ), 若0≤P (E |S )
⎪P (H ) +P (H |E ) -P (E ) ⨯[P (E |S ) -P (E ) ], 若P (E ) ≤P (E |S ) ≤1 ⎪⎩1-P (E )
结论不确定性的合成
第三章确定性推理(运算问题，与作业题难度相当)
谓词公式的等价式：
•
•
•
•
•
•
•
•
•
• (1) 双重否定率 ¬ ¬ P ⇔ P (2) 交换率 (P∨Q) ⇔ (Q∨P) ， ( P∧Q) ⇔ ( Q∧P) (3) 结合率 (P∨Q) ∨R ⇔ P ∨(Q∨R) (P∧Q) ∧R ⇔ P ∧(Q∧R) (4) 分配率 P ∨(Q∧R) ⇔ (P∨Q) ∧(P∨R) P ∧(Q∨R) ⇔ (P∧Q) ∨(P∧R) (5) 摩根定律 ¬ (P∨Q) ⇔ P ∧Q ¬ (P∧Q) ⇔ P ∨Q (6) 吸收率 P ∨(P∧Q) ⇔ P P ∧(P∨Q) ⇔ P
(7) 补余率 P ∨P ⇔ T, P ∧P ⇔ F
(8) 连词化归率 P →Q ⇔ ¬P ∨Q
PQ ⇔ (P→Q) ∧(Q→P)
PQ ⇔ (P∧Q) ∨(Q∧P)
(9) 量词转换率 ¬ (∃x)P ⇔ (∀x)( ¬ P)
¬ (∀x)P ⇔ (∃x) (¬ P)
(10) 量词分配率 (∀x) (P∧Q) ⇔ (∀x)P ∧(∀x)Q
(∃x) (P∨Q) ⇔ (∃x)P ∨(∃x)Q
常用的永真蕴含式如下：
(1) 化简式 P ∧Q ⇒ P ， P ∧Q ⇒ Q
(2) 附加式 P ⇒ P ∨Q ， Q ⇒ P ∨Q
(3) 析取三段论 ﹁ P, P ∨Q ⇒ Q
(4) 假言推理 P, P →Q ⇒ Q
(5) 拒取式 ¬Q, P →Q ⇒ P
(6) 假言三段论 P →Q, Q →R ⇒P →R
(7) 二难推理 P ∨Q, P →R, Q →R ⇒ R
(8) 全称固化 (∀x)P(x) ⇒ P(y)
其中，y 是个体域中的任一个体，依此可消去谓词公式中的全称量词。
(9) 存在固化 (∃x)P(x) ⇒ P(y)
其中，y 是个体域中某一个可以使P(y)为真的个体，依此可消去谓词公式中的存在量词。
子句集的化简
(1) 消去连接词“→”和“”
• P →Q ⇔﹁ P ∨Q
• PQ ⇔ (P∧Q) ∨(﹁P ∧﹁Q)
(2) 减少否定符号的辖域
• ﹁(﹁P) ⇔ P
• ﹁(P∧Q) ⇔﹁P ∨﹁Q
• ﹁(P∨Q) ⇔﹁P ∧﹁Q
• ﹁ (∀x)P(x) ⇔ (∃x) ﹁P(x)
• ﹁ (∃x)P(x) ⇔ (∀x) ￢P(x) • • • • • • • • • • • • • • • • • • • •
(3) 对变元标准化（将y 变为z ）
(4) 化为前束范式(所有量词都移到公式的左边)
(5) 消去存在量词(用Skolem 函数f(x1，x2 ,…, xn)替换)
(6) 化为Skolem 标准形(等价关系P ∨(Q∧R) ⇔ (P∨Q) ∧(P∨R))
(7) 消去全称量词(省掉全称量词)
(8) 消去合取词(去掉∧得到子句集)
(9) 更换变量名称（x 换为y ）
第六章不确定性推理公式（计算都要）
P (A i ) ⨯P (B /A i ) 全概率公式和Bayes 公式 P (A i |B ) =i =1, 2, , n n P (A j ) ⨯P (B /A j ) ∑P (B ) =∑P (A i ) ⨯P (B |A i ) j =1 i =1一、CF 模型
CF(H, E)=MB(H, E)-MD(H, E)
⎧1, 信任增长度 若P (H ) =1⎪MB (H , E ) =⎨max{P (H |E ), P (H )}-P (H ) , 否则⎪1-P (H ) ⎩
⎧1, 不信任增长度 若P (H ) =0⎪MD (H , E ) =min{P (H |E ), P (E )}-P (H ) ⎨ , 否则⎪-P (H ) ⎩
可信度
当MB(H, E)>0时，MD(H, E)=0
当MD(H, E)>0时，MB(H, E)=0
0≤MB (H , E ) ≤1, 0≤MD (H , E ) ≤1, -1≤CF (H , E ) ≤1
P (⌝H |E ) -P (⌝H ) (1-P (H |E )) -(1-P (H )) = MD (⌝H , E ) =-P (⌝H ) -(1-P (H )) -P (H |E ) +P (H ) -(P (H |E ) -P (H )) ==-(1-P (H )) -(1-P (H ))
P (H |E ) -P (H ) ==MB (H , E ) (信任增长度) 1-P (H )
CF(H,E)+CF(﹁H,E)=(MB(H,E)-MD(H,E))+(MB(﹁H,E)-MD(﹁H,E))
=(MB(H,E)-0)+(0-MD(﹁H,E)) (由互斥性)
=MB(H,E)-MD(﹁H,E)=0
它说明：(1)对H 的信任增长度等于对非H 的不信任增长度；(2)对H 的可信度
与非H 的可信度之和等于0；(3)可信度不是概率，不满足P(H)+P(﹁H)=1 和 0≤P(H),P(﹁H) ≤ 1
n
∑CF (H i , E ) ≤1
i =1合取CF(E)=min{CF(E1), CF(E2), … ,CF(En)}
析取CF(E)=max{CF(E1), CF(E2), … ,CF(En)}
不确定性的更新公式CF(H)=CF(H, E)×max{0, CF(E)}
E1与E2对H 的综合可信度
⎧CF 1(H ) +CF 2(H ) -CF 1(H ) ⨯CF 若CF 1(H ) ≥0 ⎪2(H )
且CF 2(H ) ≥ ⎪0
CF (H ) =⎪⎨CF 1(H ) +CF 2(H ) +CH 1(H ) ⨯CF 2(H ) 若CF 1(H )
⎪与
⎩1-min CF 1(H ) , CF 2(H ) CF 2(H ) 异号
二、主观Bayes 方法
IF E THEN (LS, LN) H
(LS, LN)用来表示该知识的知识强度，LS(充分性度量) 和LN(必要性度量) P (E |
LS =H )
P (E |⌝H )
LN =P (⌝E |H ) 1-P (E |H
P (⌝E |⌝H ) =)
1-P (E |⌝H )
P (H |E ) =P (E |H ) ⨯P (H )
P (E )
P (⌝H |E ) =P (E |⌝H ) ⨯P (⌝H )
P (E )
P (H |E ) P (E |
P (⌝H |E ) =H )
P (E |⌝H ) ⨯P (H )
P (⌝H )
P (X ) P (X )
O (X ) =1-P (X ) 或O (X ) =P (⌝X )
O (H |E ) =P (E |H )
P (E |⌝H ) ⨯O (H )
O (H |E ) =LS ⨯O (H )
同理可得到关于LN 的公式：
P (H |⌝E ) P (⌝E |H ) P (H )
P (⌝H |⌝E ) =P (⌝E |⌝H ) ⨯P (⌝H )
O (H |⌝E ) =LN ⨯O (H )
① LS>1且LN
② LS1
③ LS=LN=1
⎧当E 为假时
概率与几率之间的关系 O (E ) =P (E ) =⎪0
⎨∝当E 为真时
1-P (E ) ⎪⎩(0, ∝) 当E 非真也非假时 (6.1)(6. 2) (6.3)(6.4)
组合证据不确定性的计算
E=E1 AND E2 AND … AND En
已知在当前观察S 下，每个单一证据Ei 有概率P (E1|S), P(E2|S), … ,P(En|S)，则 P(E|S)=min{ P(E1|S), P(E2|S), … ,P(En|S)}
E=E1 OR E2 OR … OR En
已知在当前观察S 下，每个单一证据Ei 有概率P(E1|S), P(E2|S), … ,P(En|S)，则 P(E|S)=max{ P(E1|S), P(E2|S), … ,P(En|S)}
不确定性的更新
1. 证据肯定为真时，P(E)=P(E|S)=1
H 的先验几率更新为后验几率的公式为：O(H|E)=LS×O(H)
P (H |E ) =LS ⨯P (H )
(LS -1) ⨯P (H ) +1(6.5)
2. 当证据E 肯定为假时，P(E)=P(E|S)=0，P(﹁E)=1
H 的先验几率更新为后验几率的公式为：O(H|﹁E)=LN×O(H)
P (H |⌝E ) =LN ⨯P (H )
(LN -1) ⨯P (H ) +1(6.6)
3. 当证据既非真假时
P(H|E)=P(H|E)×P(E|S)+P(H|﹁E) ×P(﹁E|S) (6.7)
(1)P(E|S)=1；P(﹁E|S)=0
LS ⨯
P (H |S ) =P (H |E ) =P (H )
(LS -1) ⨯P (H ) +1
(2)P(E|S)=0；P(﹁E|S)=1
P (H |S ) =P (H |⌝E ) =LN ⨯P (H )
(LN -1) ⨯P (H ) +1
(3)P(E|S)=P(E)；E 与S 无关
P (H |S ) =P (H |E ) ⨯P (E |S ) +P (H |⌝E ) ⨯P (⌝E |S )
=P (H |E ) ⨯P (E ) +P (H |⌝E ) ⨯P (⌝E ) =P (H )
(4) P(E/S)为其它值
⎧
⎪P (H |⌝E ) +P (H ) -P (H |⌝E ) ⨯P (E |S ), 若0≤P (E |S )
⎪P (H ) +P (H |E ) -P (E ) ⨯[P (E |S ) -P (E ) ], 若P (E ) ≤P (E |S ) ≤1 ⎪⎩1-P (E )
结论不确定性的合成