H-逻辑智能体II-人工智能(AI).ppt

1、命题逻辑及其推理APropostional logic 或 (命题符号的合取) 命题符号 E.g., C (B A) (C D B) 分离规则 Modus Ponens (应用于Horn范式 ): 对于霍恩知识库KB是完备的 1, ,n,1 n 对由Horn子句构成的Horn知识库的推理可以通过前向链和反向链进行,前向链,思想: 应用那些其前提能在KB中得到满足的规则以得到新的结论 将产生的新结论加入到KB中，直到查询的得到解答,对于Horn知识库KB，前向链推理是可靠且完备的,前向链算法,前向链例子,前向链例子,前向链例子,前向链例子,前向链例子,前向链例子,前向链例子,前向链例子,思想:

2、由查询 q 往回走 : 要由BC（反向链，Backward Chaining）证明q, 检查 q 是否已知，或 由BC证明结论为q的规则的前提是否都得到了满足,反向链,反向链例子,反向链例子,反向链例子,反向链例子,反向链例子,反向链例子,反向链例子,反向链例子,反向链例子,反向链例子,FC 是数据驱动（data-driven）, 自动的，无意识的处理 例如, 目标识别, 路径决策 可能会做学多与目标无关的工作 BC 是目标驱动（goal-driven）, 适于问题求解 例如, 钥匙在哪？ BC的复杂度远小于KB的大小,前向链 vs. 反向链,合取范式 Conjunctive Normal F

3、orm (CNF) 文字析取式的合取形式 （conjunction of disjunctions of literals clauses） E.g., (A B) (B C D) 归结 推理规则 (针对CNF): l1 lk, m1 mn l1 li-1 li+1 lk m1 mj-1 mj+1 . mn 式中 li 和 mj 为互补文字. E.g., P2,2 P3,1, P2,2 P3,1 针对命题逻辑的归结是可靠和完备的推理过程,归结,B1,1 (P1,2 P2,1) 消去 , ( )( ) : (B1,1 (P1,2 P2,1) (P1,2 P2,1) B1,1) 2. 消去 , :

4、 (B1,1 P1,2 P2,1) (P1,2 P2,1) B1,1) 3. 将移入括号内，使其直接作用于文字（摩根率）: (B1,1 P1,2 P2,1) (P1,2 P2,1) B1,1) 4. 应用分配率，得到CNF， （( ） （ )） : (B1,1 P1,2 P2,1) (P1,2 B1,1) (P2,1 B1,1),转换为合取范式CNF,使用归谬法证明，即证明KB是不可满足的,归结算法,有知识库KB = (B1,1 (P1,2 P2,1) B1,1 = P1,2（即方格1,2无陷阱） 欲证明KB 采用归谬法，即证明KB不可能成立 (不可满足） 则KB将转换为CNF，然后运用归结，

5、若归结出空子句，即KB不可满足,归结证明例子,Efficient propositional inference,Two families of efficient algorithms for propositional inference: Complete backtracking search algorithms DPLL algorithm (Davis, Putnam, Logemann, Loveland) Incomplete local search algorithms WalkSAT algorithm,Practical Propositional Theorem P

6、roving,Problem to solve is in CNF Is Marvin a Martian? M = true?Given: Marvin is green G=true Marvin is little L=true (little and green) implies Martian (L G) = M (L G) M L G M Proof by contradictionAre there true/false values for G, L, and M that are consistent with knowledge base and Marvin not be

7、ing a Martian? G L (L G M) M = false?,Searching for variable values,Want to find values such that: G L (L G M) M = false Randomly consider all true/false assignments to variables until we exhaust them all or find match (model checking) (G, L, M) = (t, f, f) no = (f, t, f) no = (f, f, f) no = (t, t,

8、f) no Alternatively,Encoding Wumpus in propositional logic,4x4 Wumpus World The “physics” of the game At least one wumpus on board A most one wumpus on board (for any two squares, one is free) n(n-1)/2 rules like: W1,1 V W1,2 No instant death: P1,1 W1,1 Total of 155 sentences containing 64 distinct

9、symbols,KB contains physics sentences for every single square For every time t and every location x,y, Lx,y FacingRightt Forward Ltx+1,y Rapid proliferation of clauses,Expressiveness limitation of propositional logic,t,t,Summary,Logical agents apply inference to a knowledge base to derive new inform

10、ation and make decisions Basic concepts of logic: syntax: formal structure of sentences semantics: truth of sentences wrt models entailment: necessary truth of one sentence given another inference: deriving sentences from other sentences soundness: derivations produce only entailed sentences completeness: derivations can produce all entailed sentences Wumpus world requires the ability to represent partial and negated information, reason by cases, etc. Resolution is complete for propositional logicForward, backward chaining are linear-time, complete