人工智能课件讲义

u 谓词公式的谓词公式的skolemskolem标准型标准型u 谓词公式的子句集谓词公式的子句集u Robinson Robinson归结原理归结原理u 一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理u 应用归结原理进行定理证明应用归结原理进行定理证明u 应用归结原理进行问题求解应用归结原理进行问题求解u 谓词公式的谓词公式的skolemskolem标准型标准型u 谓词公式的子句集谓词公式的子句集u Robinson Robinson归结原理归结原理u 一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理u 应用归结原理进行定理证明应用归结原理进行定理证明u 应用归结原理进行问题求解应用归结原理进行问题求解 从前束型范式中从前束型范式中消去全部存在量词消去全部存在量词所得到的公所得到的公式，称为式，称为SkolemSkolem范式，或范式，或Skolem标准型。标准型。Skolem标准型的一般形式为：标准型的一般形式为：L SKOLEM SKOLEM范式（教材范式（教材103103页）页）公式的首标公式的首标（不出现存在量词）（不出现存在量词）命题演算公式命题演算公式消去存在量词（参见消去存在量词（参见P102）f(x)代替代替y5【SKOLEM范式的获取步骤范式的获取步骤】（教材（教材102页）页）1.1.消去谓词公式消去谓词公式G G中的蕴涵（中的蕴涵（）和等价（）和等价（）符）符号；号；2.2.减少否定符号（减少否定符号（）的辖域，使否定符号最多只）的辖域，使否定符号最多只作用到一个谓词上；作用到一个谓词上；3.3.重新命名变元，使所有的变元的名字均不同，并重新命名变元，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。且自由变元及约束变元亦不同。4.4.消去存在量词（消去存在量词（）。将该量词约束的变量用任意）。将该量词约束的变量用任意常量常量(a,b等等)或任意变量的函数或任意变量的函数(f(x),g(y)等等)代代替。替。如果存在量词左边没有任何全称量词，则只将其改写为个如果存在量词左边没有任何全称量词，则只将其改写为个体常量；体常量；如果存在量词的左边有全称量词，消去时该变量改写为全如果存在量词的左边有全称量词，消去时该变量改写为全称量词的函数。称量词的函数。5.5.把把全称量词全称量词全部移到公式的全部移到公式的左边左边，并使每个量词，并使每个量词的辖域包括这个量词后面公式的整个部分；的辖域包括这个量词后面公式的整个部分；6.6.母式化为母式化为合取范式合取范式。至此所得的公式就是谓词公式至此所得的公式就是谓词公式G G的的skolemskolem标准型。标准型。例：将下式化为例：将下式化为SkolemSkolem标准形。标准形。解：解：消去消去符号符号 ，得：得：深入到量词内部（深入到量词内部（E13E13），得：），得：【SKOLEM范式的获取实例】全称量词左移，利用分配律，得：全称量词左移，利用分配律，得：变量易名，存在量词左移，直至所有的量词移到变量易名，存在量词左移，直至所有的量词移到 前面，得：前面，得：消去存在量词，略去全称量词，得消去存在量词，略去全称量词，得SkolemSkolem标准形标准形 ：例：将下式化为Skolem标准形。u 谓词公式的谓词公式的skolemskolem标准型标准型u 谓词公式的子句集谓词公式的子句集u Robinson Robinson归结原理归结原理u 一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理u 应用归结原理进行定理证明应用归结原理进行定理证明u 应用归结原理进行问题求解应用归结原理进行问题求解14L 子句与子句集（教材子句与子句集（教材P102P102）原子公式：原子公式：不含任何连接词的谓词公式。不含任何连接词的谓词公式。文文 字：字：原子或原子的否定。原子或原子的否定。子子 句：句：由一些文字组成的由一些文字组成的析取式析取式。空空 子子 句：句：不包含任何文字的子句，表示为不包含任何文字的子句，表示为NILNIL。空子句。空子句是永假的。是永假的。子子 句句 集：集：由子句构成的集合。由子句构成的集合。15【子句集子句集S S的求取的求取】由于由于Skolem Skolem 标准型的母式已准型的母式已为合取式，从而母式的每合取式，从而母式的每一个合取一个合取项都是一个子句。都是一个子句。子句集的求取方法子句集的求取方法为：将将谓词公式公式G G化化为 Skolem Skolem 标准型；准型；消去消去Skolem Skolem 标准型前面的全称量准型前面的全称量词；用用“，”取代取代“”，并表示，并表示为成集合形式。成集合形式。16【实例】【参见教材参见教材102-103102-103页例页例5.75.7】定理定理1 1：G G是不可满足的是不可满足的 S S是不可满足的是不可满足的（教材（教材P104P104）【子句集子句集S S与谓词公式与谓词公式G G的关系的关系】证明一个公式的不可满足性，转化为证明其证明一个公式的不可满足性，转化为证明其子句集子句集S S的不可满足性。的不可满足性。u 谓词公式的谓词公式的skolemskolem标准型标准型u 谓词公式的子句集谓词公式的子句集u Robinson Robinson归结原理归结原理u 一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理u 应用归结原理进行定理证明应用归结原理进行定理证明u 应用归结原理进行问题求解应用归结原理进行问题求解L ROBINSON ROBINSON归结原理（消解原理）归结原理（消解原理）检查子句集检查子句集S S中是否有中是否有空子句空子句：u 若有，则表明若有，则表明S S是不可满足的；是不可满足的；u 若没有，就在子句集中选择合适的子句对若没有，就在子句集中选择合适的子句对其进行归结推理，如果能推出空子句，就说其进行归结推理，如果能推出空子句，就说明子句集是明子句集是S S是不可满足的。是不可满足的。【归结推理过程归结推理过程】对子句集对子句集S S中的各个子句间使用归结推理规则；中的各个子句间使用归结推理规则；将归结所得的归结式放入子句集将归结所得的归结式放入子句集S S中，得到新子句中，得到新子句集集S S；检查子句集检查子句集S S中是否有空子句（中是否有空子句（NILNIL），若有，），若有，则停止推理；否则，转步骤则停止推理；否则，转步骤；置置S=SS=S，转步骤，转步骤。按照上述推理，在推理过程中，当子句集按照上述推理，在推理过程中，当子句集S S中中出现空子句，即证明出现空子句，即证明S S是不可满足的。是不可满足的。重点哦！重点哦！【例题5.11】P105 证明子句集证明子句集PP乛乛Q,Q,乛乛P,QP,Q是不可满足的。是不可满足的。证：证：(1)P(1)P乛乛Q Q.已知已知(2)(2)乛乛P P .已知已知(3)Q (3)Q .已知已知(4)(4)乛乛Q Q .由由(1),(2)(1),(2)归结归结(5)NIL (5)NIL .由由(3),(4)(3),(4)归结归结由于由于S S中出现空子句，所以中出现空子句，所以S S是不可满足的。是不可满足的。【例题5.12】P105 用归结原理证明用归结原理证明R R是是P,(PQ)R,(SU)Q,UP,(PQ)R,(SU)Q,U的逻辑结果。的逻辑结果。【提示提示】要证明要证明PQPQ是永真的，考虑反证法，先否是永真的，考虑反证法，先否定逻辑结论定逻辑结论Q Q，再由否定后的逻辑结论，再由否定后的逻辑结论Q Q及前提及前提条件条件P P出发推出矛盾，即证明原问题。出发推出矛盾，即证明原问题。为证明为证明PQPQ，实际实际上只需证明，实际实际上只需证明P P Q Q的的不可满足性。不可满足性。证：证：由已知前提条件和否定逻辑结论可得到子句集由已知前提条件和否定逻辑结论可得到子句集S S：S=S=P,P,乛乛PP乛乛QR,QR,乛乛SQ,SQ,乛乛UQ,U,UQ,U,乛乛R R 然后对该子句集施行归结，归结过程用下面的然后对该子句集施行归结，归结过程用下面的归结演绎树表示。归结演绎树表示。由于最后推出了空子句，所以子句集由于最后推出了空子句，所以子句集S S不可满足。不可满足。即命题公式即命题公式 P(P(乛乛PP乛乛R)(R)(乛乛SQ)SQ)(乛乛UQ)UUQ)U乛乛R R不可满足，从而不可满足，从而R R是题设前提的是题设前提的逻辑结果。逻辑结果。24u 谓词公式的谓词公式的skolemskolem标准型标准型u 谓词公式的子句集谓词公式的子句集u Robinson Robinson归结原理归结原理u 一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理u 应用归结原理进行定理证明应用归结原理进行定理证明u 应用归结原理进行问题求解应用归结原理进行问题求解L 一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理(P106)(P106)在一阶谓词逻辑中，因为谓词逻辑中的子句含在一阶谓词逻辑中，因为谓词逻辑中的子句含有个体变元，所以不能直接消去互补文字进行子有个体变元，所以不能直接消去互补文字进行子句归结，而是要首先使用句归结，而是要首先使用置换和合一置换和合一的思想，对的思想，对子句中的某些变元进行合一置换，对置换后的新子句中的某些变元进行合一置换，对置换后的新子句再次使用归结。子句再次使用归结。例如：例如：假设有如下两个子句：假设有如下两个子句：C1=P(x)Q(x)C2=乛乛P(a)R(y)直接比较，似乎两者中不含互补文字，但如果我们用直接比较，似乎两者中不含互补文字，但如果我们用a替替换换C1中的中的x，则得到，则得到 C1=P(a)Q(a)C2=乛乛P(a)R(y)于是根据命题逻辑中的消解原理，得于是根据命题逻辑中的消解原理，得C1和和C2的消解式的消解式 C3=Q(a)R(y)所以，要在谓词逻辑中应用消解原理，则一般需要对所以，要在谓词逻辑中应用消解原理，则一般需要对个体变元作适当的替换。个体变元作适当的替换。置换可以简单理解为：在一个谓词公式中用置置换可以简单理解为：在一个谓词公式中用置换项去置换变量。换项去置换变量。1.置换（教材P106）2.合一（P107，定义9）设有公式集设有公式集 ，若存在一个置换，若存在一个置换 可使可使则称则称 是是E E 的合一置换。同时称的合一置换。同时称E E1 1,E E2 2,E En n是可合一的。是可合一的。3.最一般合一（P107，定义10）设设 是谓词公式集是谓词公式集E E 的一个合一置换，如果对的一个合一置换，如果对E E 的任的任意一个合一置换意一个合一置换 都存在一个置换都存在一个置换 ，使得，使得 ，则称，则称 是一个最一般是一个最一般(或最简单或最简单)合一合一(most general(most general unifierunifier，简记为，简记为MGU)MGU)。谓词公式集的最一般合一置换谓词公式集的最一般合一置换并不是唯一的。并不是唯一的。置置k=0,Sk=0,Sk k=S=S，k k=;=;若若S Sk k只只含含有有一一个个谓谓词词公公式式，则则算算法法停停止止，k k就就是要求的最一般合一是要求的最一般合一;求求S Sk k的差异集的差异集D Dk k;若若D Dk k中存在元素中存在元素x xk k和和t tk k，其中，其中x xk k是变元，是变元，t tk k是项是项且且x xk k不在不在t tk k中出现，则置中出现，则置S Sk+1k+1=S=Sk kt tk k/x/xk k,k+1k+1=k kt tk k/x/xk k，k=k+1k=k+1，然后转，然后转;算法停止，算法停止，S S的最一般合一不存在。的最一般合一不存在。最一般合一置换的求取算法最一般合一置换的求取算法（P107-108P107-108）【P108,例5.16】1.求求公公式式集集S=P(a,x,f(g(y),P(z,h(z,u),f(u)的的最最一一般合一。般合一。解：解：k=0：S0=S,0=,S0不不是是单单元元素素集集，求求得得D0=a,z，其其中中z是变元，且不在是变元，且不在a中出现，所以有中出现，所以有 1=0a/z=a/z=a/z S1=S0a/z=P(a,x,f(g(y),P(a,h(a,u),f(u)k=1:S1不是单元素集，求得不是单元素集，求得D1=x,h(a,u)，2=1h(a,u)/x=a/zh(a,u)/x=a/z,h(a,u)/x S2=S1h(a,u)/x=P(a,h(a,u),f(g(y),P(a,h(a,u),f(u)k=2:S2不是单元素集，不是单元素集，D2=g(y),u，3=2g(y)/u=a/z,h(a,g(y)/x,g(y)/uS3=S2g(y)/u=P(a,h(a,g(y),f(g(y),P(a,h(a,g(y),f(g(y)=P(a,h(a,g(y),f(g(y)k=3:S3已是单元素集，所以已是单元素集，所以3就是就是S的最一般合一。的最一般合一。2.判定判定S=P(x,x),P(y,f(y)是否可合一？是否可合一？解：解：k=0:S0=S,0=,S0不是单元素集，不是单元素集，D0=x,y1=0y/x=y/xS1=S0y/x=P(y,y),P(y,f(y)k=1:S1不不是是单单元元素素集集，D1=y,f(y)，由由于于变变元元y在在项项f(y)中出现中出现，所以算法停止，所以算法停止，S不存在最一般合一。不存在最一般合一。【P108,例例5.17】u 谓词公式的谓词公式的skolemskolem标准型标准型u 谓词公式的子句集谓词公式的子句集u Robinson Robinson归结原理归结原理u 一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理u 应用归结原理进行定理证明应用归结原理进行定理证明u 应用归结原理进行问题求解应用归结原理进行问题求解L 利用归结原理进行定理证明利用归结原理进行定理证明归结原理指出了证明子句集不可满足性的方法。归结原理指出了证明子句集不可满足性的方法。设要被证明的定理用谓词公式表示为设要被证明的定理用谓词公式表示为应用归结原理进行定理证明的步骤如下：应用归结原理进行定理证明的步骤如下：首先否定结论，并将否定后的结论谓词公式首先否定结论，并将否定后的结论谓词公式B与前提条与前提条件公式集组成如下形式的谓词公式：件公式集组成如下形式的谓词公式：求谓词公式求谓词公式G的子句集的子句集S；应用归结原理，证明子句集应用归结原理，证明子句集S的不可满足性，从而证明谓的不可满足性，从而证明谓词公式词公式G的不可满足性。的不可满足性。反证法重重点点哦哦！【例例5.21】(P110)求证求证G G是是A A1 1和和A A2 2的逻辑结果。的逻辑结果。A A1 1:x(P(x)(Q(x)R(x):x(P(x)(Q(x)R(x)A A2 2:x(P(x)S(x):x(P(x)S(x)G:x(S(x)R(x)G:x(S(x)R(x)证：我们用反证法，即证明证：我们用反证法，即证明A1A2A1A2乛乛G G不可满足。不可满足。2 首先求得子句集首先求得子句集S S：(1)(1)乛乛P(x)Q(x)P(x)Q(x)(2)(2)乛乛P(y)R(y)P(y)R(y)(3)P(a)(3)P(a)(4)S(a)(4)S(a)(5)(5)乛乛S(z)S(z)乛乛R(z)(R(z)(乛乛G)G)2然后应用消解原理得然后应用消解原理得:(6)R(a)(6)R(a)(2),(3),(2),(3),1 1=a/ya/y(7)(7)乛乛R(a)R(a)(4),(5),(4),(5),2 2=a/za/z(8)NIL (8)NIL (6),(7)(6),(7)所以所以S S是不可满足的，从而是不可满足的，从而G G是是A A1 1和和A A2 2的逻辑结果。的逻辑结果。(A1)(A2)S【例例5.22】(P110)设已知：设已知：(1)(1)能阅读者是识字的；能阅读者是识字的；(2)(2)海豚不识字；海豚不识字；(3)(3)有些海豚是很聪明的。有些海豚是很聪明的。试证明：有些聪明者并不能阅读。试证明：有些聪明者并不能阅读。证：证：首先，定义如下谓词：首先，定义如下谓词：R(x)R(x)：x x能阅读。能阅读。L(x)L(x)：x x识字。识字。I(x)I(x)：x x是聪明的。是聪明的。D(x)D(x)：x x是海豚。是海豚。然后把上述各语句翻译为谓词公式：然后把上述各语句翻译为谓词公式：(1)x(R(x)L(x)(1)x(R(x)L(x)(2)x(D(x)(2)x(D(x)乛乛L(x)L(x)已知条件已知条件(3)x(D(x)I(x)(3)x(D(x)I(x)(4)x(I(x)(4)x(I(x)乛乛R(x)R(x)需证结论需证结论 求题设与结论的否定子句集，得求题设与结论的否定子句集，得(1)(1)乛乛R(x)L(x)R(x)L(x)(2)(2)乛乛D(y)D(y)乛乛L(y)L(y)(3)D(a)(3)D(a)(4)I(a)(4)I(a)(5)(5)乛乛I(z)R(z)I(z)R(z)归结得：归结得：(6)R(a)(5)(6)R(a)(5)，(4)(4)，a/za/z(7)L(a)(6)(7)L(a)(6)，(1)(1)，a/xa/x(8)(8)乛乛D(a)(7),(2),a/yD(a)(7),(2),a/y(9)NIL (8),(3)(9)NIL (8),(3)这个归结过程的演绎树如图。这个归结过程的演绎树如图。u 谓词公式的谓词公式的skolemskolem标准型标准型u 谓词公式的子句集谓词公式的子句集u Robinson Robinson归结原理归结原理u 一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理u 应用归结原理进行定理证明应用归结原理进行定理证明u 应用归结原理进行问题求解应用归结原理进行问题求解L 利用归结原理进行问题求解（利用归结原理进行问题求解（P111P111）归结原理除了能用于对已知结果的证明外，归结原理除了能用于对已知结果的证明外，还能用于对未知结果的求解，即能求出问题的答还能用于对未知结果的求解，即能求出问题的答案来。案来。【问题求解的基本步骤问题求解的基本步骤】把已知条件用谓词公式表示，并化成相应的子句把已知条件用谓词公式表示，并化成相应的子句集集S1；把待求解的问题也用谓词公式表示，然后将其把待求解的问题也用谓词公式表示，然后将其否否定定，并与谓词，并与谓词ANSWER构成构成析取式析取式G1；把把G1化为子句集化为子句集S2，并把子句集，并把子句集S2与与S1合并构成合并构成新子句集新子句集S；对子句集对子句集S应用谓词归结原理进行归结，在归结应用谓词归结原理进行归结，在归结过程中通过合一置换，改变过程中通过合一置换，改变ANSWER中的变元；中的变元；如果得到归结式如果得到归结式ANSWER，则问题的答案就在，则问题的答案就在ANSWER谓词中。谓词中。重重点点哦哦！【例例5.23 】(P111)已知已知:(1)(1)如如果果x x和和y y是是同同班班同同学学，则则x x的的老老师师也也是是y y的的老师。老师。(2)(2)王先生是小李的老师。王先生是小李的老师。(3)(3)小李和小张是同班同学。小李和小张是同班同学。问：小张的老师是谁？问：小张的老师是谁？解解:设设谓谓词词T(x,y)T(x,y)表表示示x x是是y y的的老老师师，C(x,y)C(x,y)表表示示x x与与y y是同班同学，则是同班同学，则 已知可表示成如下的谓词公式：已知可表示成如下的谓词公式：F F1 1:x y z(C(x,y)T(z,x)T(z,y):x y z(C(x,y)T(z,x)T(z,y)F F2 2:T(Wang,Li):T(Wang,Li)F F3 3:C(Li,Zhang):C(Li,Zhang)将它们化成子句集为将它们化成子句集为 S1=S1=C(x,y)C(x,y)T(z,x)T(z,x)T(z,y),T(Wang,Li),T(z,y),T(Wang,Li),C(Li,Zhang C(Li,Zhang）把问题用谓词公式表示，把问题用谓词公式表示，并将其否定与谓词并将其否定与谓词ANSWERANSWER作析取：作析取：设小张的老师是设小张的老师是u u，则有，则有T(u,Zhang)T(u,Zhang)G1:G1:T(u,Zhang)ANSWER(u)T(u,Zhang)ANSWER(u)将析取式将析取式G1G1化成子句集化成子句集S2,S2,并将并将S1S1与与S2S2合并为新子句集合并为新子句集S S：S2=S2=T(u,Zhang)ANSWER(u)T(u,Zhang)ANSWER(u)S=S1S2 S=S1S2 =C(x,y)C(x,y)T(z,x)T(z,y),T(z,x)T(z,y),.(a).(a)T(Wang,Li),T(Wang,Li),.(b).(b)C(Li,Zhang),C(Li,Zhang),.(c).(c)T(u,Zhang)ANSWER(u)T(u,Zhang)ANSWER(u).(d).(d)应用归结原理进行归结：应用归结原理进行归结：(e)C(Li,y)T(Wang,y)aC(Li,y)T(Wang,y)a与与b b归结，（归结，（Li/x,Wang/z)Li/x,Wang/z)(f)(f)T(z,Li)ANSWER(u)dT(z,Li)ANSWER(u)d与与e e归结，（归结，（Wang/u,Zhang/y)Wang/u,Zhang/y)(g)ANSWER(Wang)b(g)ANSWER(Wang)b与与f f归结归结 得到归结式得到归结式ANSWERANSWER（WangWang），答案即在其中：），答案即在其中：u=Wangu=Wang，即小张的老师是王先生。，即小张的老师是王先生。【例例5.24 】(P112)设有如下关系设有如下关系:(1)(1)如如果果x x是是y y的的父父亲亲，y y又又是是z z的的父父亲亲，则则x x是是z z的祖父。的祖父。(2)(2)老李是大李的父亲。老李是大李的父亲。(3)(3)大李是小李的父亲。大李是小李的父亲。问：上述人员中谁和谁是祖孙关系？问：上述人员中谁和谁是祖孙关系？解：解：先把上述前提中的三个命题符号化为谓词公先把上述前提中的三个命题符号化为谓词公式：式：F1:x y z(F(x,y)F(y,z)G(x,z)F1:x y z(F(x,y)F(y,z)G(x,z)F2:F(Lao,Da)F2:F(Lao,Da)F3:F(Da,Xiao)F3:F(Da,Xiao)求其子句集如下求其子句集如下:S1=S1=乛乛F(x,y)F(x,y)乛乛F(y,z)G(x,z),F(Lao,Da),F(y,z)G(x,z),F(Lao,Da),F(Da,Xiao)F(Da,Xiao)把问题用谓词公式表示，把问题用谓词公式表示，并将其否定与谓词并将其否定与谓词ANSWERANSWER作析取：作析取：设设u,vu,v为祖孙关系，则有为祖孙关系，则有G(u,v)G(u,v)G1:G1:G(u,v)ANSWER(u,v)G(u,v)ANSWER(u,v)将析取式将析取式G1G1化成子句集化成子句集S2,S2,并将并将S1S1与与S2S2合并为新子句集合并为新子句集S S：S2=S2=G(u,v)ANSWER(u,v)G(u,v)ANSWER(u,v)S=S1S2 S=S1S2 =乛乛F(x,y)F(x,y)乛乛F(y,z)G(x,z),F(y,z)G(x,z),.(a).(a)F(Lao,Da),F(Lao,Da),.(b).(b)F(Da,Xiao)F(Da,Xiao).(c).(c)G(u,v)ANSWER(u,v)G(u,v)ANSWER(u,v).(d).(d)应用归结原理进行归结：应用归结原理进行归结：(e)F(Da,z)G(Lao,z)aF(Da,z)G(Lao,z)a与与b b归结，（归结，（Lao/x,Da/y)Lao/x,Da/y)(f)G(Lao,Xiao)c(f)G(Lao,Xiao)c与与e e归结，（归结，（Xiao/z)Xiao/z)(g)ANSWER(Lao,Xiao)d(g)ANSWER(Lao,Xiao)d与与f f归结归结,Lao/u,Xiao/v,Lao/u,Xiao/v 得到归结式得到归结式ANSWERANSWER（Lao,XiaoLao,Xiao），答案即在其中：），答案即在其中：u=Lao,v=Xiaou=Lao,v=Xiao，即老李是小李的祖父。，即老李是小李的祖父。总总 复复 习习人工智能人工智能导导论论图搜索图搜索状状态图搜索搜索盲目搜索盲目搜索宽度度优先先深度深度优先先启启发搜索搜索（代价（代价树）全局全局择优（A/A*）局部局部择优与或与或树搜索搜索知识表示知识表示谓词产生式生式规则产生式系生式系统的机器推理的机器推理语义网网络推推理理谓词逻辑的的归结推理推理定理定理证明明问题求解求解需要掌握的方法：需要掌握的方法：u 图搜索图搜索 具体问题的图描述方法；具体问题的图描述方法；基于状态图利用树式搜索策略进行问题求解；基于状态图利用树式搜索策略进行问题求解；基于代价树利用启发式搜索策略寻求最优解；基于代价树利用启发式搜索策略寻求最优解；求解与或树的最优解树；求解与或树的最优解树；u 知识表示知识表示利用一阶谓词公式表示复杂命题的方法；利用一阶谓词公式表示复杂命题的方法；利用语义网络表示复杂命题的方法；利用语义网络表示复杂命题的方法；利用产生式规则表示复杂命题的方法；利用产生式规则表示复杂命题的方法；u 推推 理理 基于产生式规则的机器推理；基于产生式规则的机器推理；谓词公式的谓词公式的skolemskolem标准型变换；标准型变换；谓词公式的子句集求取；谓词公式的子句集求取；谓词公式集的最一般合一的求解；谓词公式集的最一般合一的求解；应用谓词公式归结原理进行定理证明；应用谓词公式归结原理进行定理证明；应用谓词公式归结原理进行问题求解；应用谓词公式归结原理进行问题求解；学科前沿讲座学科前沿讲座皇帝的新脑还是人类的终结皇帝的新脑还是人类的终结 一、关于人工智能 一、关于人工智能从数值计算文字、图像等多媒体信息处理初步实现了Leibniz提出的“将人的思维机器化”的思想让机器拥有人的心智成为计算机专家梦寐以求的理想！1956年，M.L.Minsky，C.Shanon，J.McCarthy(人工智能之父)等在美国达德茅斯大学召开第一届人工智能学术会议。会上首次使用“人工智能”这一术语。标志着人工智能学科的诞生。一、关于人工智能1950年，W.格雷.瓦尔特，可以自己充电的“乌龟”1960年，K.M.柯尔，模拟了一个精神病疗法专家电脑下棋方面，97年的“深蓝”(Deep Blue)，03年的“小深”(Deep Junior)一、关于人工智能医生：我可以为你效劳吗病人：我不知道医生：请告诉我一些情形病人：不医生：请你说得仔细些病人：今天我厌烦得很医生：你知道这是什么原因病人：是的我老了医生：请继续讲病人：仿佛任何事情都激不起我的兴致医生：请更多地告诉我你的这种感觉病人：我也有些知道为何我会这样感觉医生：是吗病人：我似乎在想有一个家医生：什么东西使你有这样的想法病人：它是一种挑战医生：为什么那对你是重要的二、电脑能否实现人的智能？机器体力电脑计算速度和准确性人脑思维是否电脑能代替人脑实现智能？一旦能够实现，这种被认为是特权的智能行为将受到挑战。二、电脑能否实现人的智能？二、电脑能否实现人的智能？二、电脑能否实现人的智能？l人真实地回答问题并试图说服质问者，他确实是人；l电脑被编好“说谎”的程序，试图说服质问者它是人。三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：爱因斯坦曾经将其比喻为“与上帝的对话”三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：四、对人工智能领域有影响的理论与书籍 四、对人工智能领域有影响的理论与书籍推荐网址http:/ 四、对人工智能领域有影响的理论与书籍镶嵌图案 埃舍尔的版画(1957)四、对人工智能领域有影响的理论与书籍问题求解逻辑推理与定理证明自然语言理解自动程序设计专家系统机器学习神经网络机器人学五、目前人工智能的研究与应用领域模式识别机器视觉智能控制智能检索智能调度与指挥分布式人工智能与Agent计算智能与进化智能数据挖掘与知识发现 六、计算机视觉中的困惑这些与人类视觉活动相比，显得微不足道。人类视觉中的视觉含义的把握以及主观经验在视觉中的作用，使机器不可能拥有的。六、计算机视觉中的困惑六、计算机视觉中的困惑 六、计算机视觉中的困惑六、计算机视觉中的困惑著名的混沌理论“蝴蝶效应”：美国气象学家洛伦芝（Lorenz）于1960年代提出一篇论文，名叫一只蝴蝶拍一下翅膀会不会在德克萨斯州引起龙卷风？，他说，亚马逊流域的一只蝴蝶扇动翅膀，会掀起密西西比河流域的一场风暴。洛伦芝把这种现象戏称做蝴蝶效应，意思即一件表面上看来毫无关系、非常微小的事情，可能带来巨大的改变。六、计算机视觉中的困惑眼睛和大脑的组合并不只具有“摄像机”般的功能。虽然，人们对“视觉理解”发生的机制还不太清楚，但可以肯定其中含有非线性突变的因素，而且导致某种结果的因素是不确定的。（即蝴蝶效应）“视觉理解”中抹不去的主观因素不可能通过确定的算法给出。七、展望在计算机上要实现人的心智，充满困境。要冲破这一困境，必须有理论性的突破：大自然的机理+算法 七、展望问题的解决不依赖于复杂的逻辑运算，而是利用装置本身的复杂性功能。七、展望大自然的机理+算法目前，在计算原理和模式方面出现了一些新的尝试：p生物计算p量子计算p光子计算p