人工智能_公式

谓词公式的等价式：

• • • • • • • • • •

(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

P↔Q ⇔ (P→Q)∧(Q→P) P↔Q ⇔ (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

• P↔Q ⇔ (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(Ai)P(B/Ai)全概率公式和Bayes公式 P(Ai|B)ni1,2,,nn P(Aj)P(B/Aj)P(B)P(Ai)P(B|Ai)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(Hi,E)1i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的综合可信度 CF1(H)CF2(H)CF1(H)CF若CF1(H)0 2(H)且CF2(H) 0 CF(H)CF1(H)CF2(H)CH1(H)CF2(H)若CF1(H)0

且CF2(H)0 CF1(H)CF2(H)若CF1(H)

与1minCF1(H),CF2(H)CF2(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) LS与LN的关系O(H |E)LNO(H) ① LS>1且LN<1 ② LS<1且LN>1

③ 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(E)

P(H|S)P(E) P(H)P(H|E)P(E)P(E|S)P(E),若P(E)P(E|S)1

1P(E)结论不确定性的合成