《人工智能第五章2010》由会员分享，可在线阅读，更多相关《人工智能第五章2010（99页珍藏版）》请在金锄头文库上搜索。
1、10/16/2018,1,第三部分 逻辑表示及推理方法,常用的知识表示方法： 非结构化方法 逻辑表示法 QA3,STRIPS,DART,MOMO 产生式系统 DENDRAL，MYCIN 结构化方法 框架 语义网络 过程式知识表示法,10/16/2018,2,第五章 谓词演算（复习）,数理逻辑思想的起源：Leibnitz之梦产生的历史：Boole的工作、Frege的工作发展的现实：计算机学科的基础（软件到硬件）古典数理逻辑主要包括两部分：命题逻辑和谓词逻辑。命题逻辑又是谓词逻辑的一种简单情形。 逻辑研究的基本内容语法 语言部分：基本符号集、公式形成规则推理部分：公理集、推理规则语义语法和语义之间
2、的关系：可靠性、完备性 基本问题逻辑表示下的判定问题,10/16/2018,3,一、命题逻辑,1 命题一句有真假意义的话。 用大写英文字母P，Q，P1，P2，表示。 例： 上海是中国最大的城市。 今天是星期日。 所有素数都是奇数。 1+1=2。 我不会解答这道题。 别的星球上有生物。 长春今天下雪。 如果太阳从西方升起，你就可以长生不老。 严禁吸烟。 今天的温度有多少度？ 全体起立！ 今天好冷啊！ 我正在说谎。,10/16/2018,4,2 真值,如果一个命题是真的，就说它的真值是T； 如果一个命题是假的，就说它的真值是F。T和F统称为命题的真值。 也用T代表一个抽象的真命题，用F代表一个抽象
3、的假命题。,10/16/2018,5,3 联结词 、 、 、 、 ,设P是一个命题，命题 “P是不对的”称为P的否定，记以P，读作非P。 例.Q:张三是好人。Q ：张三不是好人。 语义规定： P是真的当且仅当P是假的。 设P，Q是两个命题，命题 “P或者Q”称为P，Q的析取，记以PQ，读作P析取Q。 例. P：今天下雪，Q：今天刮风， PQ：今天下雪或者刮风。 语义规定： PQ是真的当且仅当P,Q中至少有一个为真。,10/16/2018,6,设P，Q是两个命题，命题 “P并且Q”称为P，Q的合取，记以PQ，读作P合取Q。 例. P：22=5，Q：雪是黑的， PQ：22=5并且雪是黑的。 语义规
4、定： PQ是真的当且仅当P和Q都是真的。 设P，Q是两个命题，命题 “如果P，则Q”称为P蕴涵Q，记以PQ。 例. P：f(x)是可微的，Q：f(x)是连续的， PQ： 若f(x)是可微的，则f(x)是连续的。 语义规定： PQ是假的当且仅当P是真的而Q是假的。,10/16/2018,7,设P，Q是两个命题，命题 “P当且仅当Q”称为P等价Q，记以PQ。 语义规定： PQ是真的当且仅当P，Q或者都是真的，或者都是假的。 例 P ：a2+b2=a2， Q： b=0， PQ： a2+b2=a2当且仅当b=0 。 五种逻辑联结词的优先级按如下次序递增：， 例. 符号串 PQRQ SR意味着： (P(
5、QR)(Q(S)R),10/16/2018,8,4 复合命题用联结词将简单命题连接的结果。 5 原子命题的抽象。用大写的英文字母P，Q，R，等表示。 6 文字原子或原子的否定。 7 子句 有限个文字的析取式称为一个子句。特别，没有文字的子句称为空子句，记为 。只有一个文字的子句称为单元子句。 8 短语 有限个文字的合取式称为一个短语。,10/16/2018,9,复合命题的抽象公式的形成规则-是如下定义的一个符号串：(1)原子是公式；(2)F、T是公式； (3)若G，H是公式，则( G)，(GH)， (GH)，(GH)，(GH)是公式；(4)所有公式都是有限次使用(1)，(2)，(3) 得到的符
6、号串。,9 公式,10/16/2018,10,设G是命题公式,A1,An是出现在G中的所有原子。指定A1,An的一组真值,则这组真值称为G的一个解释。 设G是公式，I是G的一个解释，G在I下的真值记为TI(G)。 例.G=PQ，设解释I，I如下： I： I： 则TI (G)=T，TI (G)=F 注意：该例子中写成G=T或G=F是错误的！,10 解释,P Q,T T,10/16/2018,11,11 真值表公式G在其所有可能的解释下所取真值的表，称为G的真值表。有n个不同原子的公式，共有2n个解释。 12 恒真公式公式G称为恒真的(或有效的)，如果G在它的所有解释下都是真的.,10/16/20
7、18,12,13 恒假公式公式G称为恒假的(或不可满足的)，如果G在它的所有解释下都是假的. 14 可满足公式公式G称为可满足的，如果它不是恒假的。G是恒真的 iff G是恒假的。 G是可满足的 iff 至少有一个解释I，使G在I下为真。 若G是恒真的，则G是可满足的； 反之不对。 如果公式G在解释I下是真的，则称I满足G； 如果G在解释I下是假的，则称I弄假G。,10/16/2018,13,例.考虑G1= (PQ) P，G2=(P Q) P，G3=P P。,10/16/2018,14,15 判定问题,能否给出一个可行方法，对任意的公式，判定其是否是恒真公式。 命题逻辑可判定？原因？因为一个命
8、题公式的原子数目有限(n)，从而解释的数目是有限的(2n)，所以命题逻辑的判定问题是可解的(可判定的，可计算的).,10/16/2018,15,16 公式等价,称公式G，H是等价的，记以G=H，如果G，H在其任意解释I下，其真值相同。公式G，H等价 iff 公式GH恒真。基本等价式 1) (GH)=(GH)(HG)； 2) (GH)=(GH)； 3) GG=G，GG=G； (等幂律) 4) GH=HG，GH=HG； (交换律) 5) G(HS)=(GH)S， G(HS)=(GH)S； (结合律),10/16/2018,16,6) G(GH)=G，G(GH)=G； (吸收律) 7) G(HS)=
9、(GH)(GS)， G(HS)=(GH)(GS)； (分配律) 8) GF=G，GT=G； (同一律) 9) GF=F，GT=T； (零一律) 10) (GH)= GH， (GH)= GH。 (De Morgan律) 11) GG=T；GG=F （互补律） 12) G=G （双重否定律）,10/16/2018,17,17 公式的蕴涵,设G，H是两个公式。 称H是G的逻辑结果(或称G蕴涵H)，当且仅当对G，H的任意解释I，如果I满足G，则I也满足H，记作GH。 公式G蕴涵公式H iff 公式GH是恒真的。 设G1, , Gn，H是公式。 称H是G1, ,Gn的逻辑结果(或称G1, , Gn共同蕴
10、涵H)，当且仅当 (G1 Gn) H。例如，P，PQ共同蕴涵Q。,10/16/2018,18,基本蕴涵式,PQP PQQ PPQ QPQ P(PQ) Q(PQ) (PQ)P,10/16/2018,19,基本蕴涵式,(PQ) Q P，QPQ P，PQQ P，PQQ Q，PQ P PQ，QRPR PQ，PR，QRR,10/16/2018,20,18 范式,有限个短语的析取式称为析取范式； 有限个子句的合取式称为合取范式。 特别，一个文字既可称为是一个合取范式，也可称为是一个析取范式。一个子句，一个短语既可看做是合取范式，也可看做是析取范式。 例如，P，PQ，PQ，(PQ)(P Q)是析取范式。 P
11、，PQ，PQ，(PQ)(PR)是合取范式。,10/16/2018,21,化范式方法：,步1. 使用基本等价式，将G中的逻辑联结词， 删除。 步2. 使用(H)=H和摩根律，将G中所有的否定号都放在原子之前。步3. 反复使用分配律，即可得到等价于G的范 式。,10/16/2018,22,19 演绎,设S是一个命题公式的集合(前提集合)。从S推出公式G的一个演绎是公式的一个有限序列： G1, G2, , Gk 其中，Gi （1i k）或者属于S，或者是某些 Gj (j3,23,503等50个命题。,10/16/2018,25,2 不能描述问题间的逻辑联系例如，逻辑学中著名的三段论： P：凡人必死
12、Q：张三是人 R：张三必死 在命题逻辑中：应该有(PQ) R，从而公式(PQ)R应该是恒真的。 显然该公式不是恒真的，解释P，Q， R就能弄假该公式。,10/16/2018,26,原因：命题R是和命题P, Q有关系的，只是这种关系在命题逻辑中无法表示。 因此，需要对命题的成分、结构和命题间的共同特性等作进一步的分析，这正是谓词逻辑所要研究的问题。,10/16/2018,27,为了表示出这三个命题的内在关系，需要引进谓词的概念。 例如，在前面的例子“张三是人”中的“是人”是谓语，称为谓词，“张三”是主语，称为个体。,10/16/2018,28,二、谓词逻辑,1 谓词 可以独立存在的物体称为个体。
13、如人、学生、桌子、自然数等都可以做个体。在谓词演算中，个体通常指一个命题里的思维对象。 设D是非空个体名称集合，定义在Dn上取值于T，F上的n元函数，称为n元命题函数或n元谓词。其中Dn表示集合D的n次笛卡尔乘积。 一般地，一元谓词描述个体的性质，二元或多元谓词描述两个或多个个体间的关系。0元谓词中无个体，理解为就是命题，这样，谓词逻辑包括命题逻辑。,10/16/2018,29,例.,D=2,3,4 设P(x)：x大于3，则P(x)为一元谓词。指定元素-命题：P(2)=F, P(3)=F, P(4)=T 设P(x,y)：x大于y,则P(x,y)为二元谓词。 指定元素-命题：P(2,3)=F, P(4,2)=T 设P(x,y,z)：若x+y-1=z，则P(x,y,z)为T，否则为F 。则P(x,y,z)为三元谓词。 指定元素-命题：P(2,3,4)=T,P(4,2,2)=F,
