PPT《人工智能原理》

q:小王是百米赛跑冠军2:?r→ (p→q),其中p:我上街,q:我去书店看看, r:我很累 命题公式及分类 复合命题:?p,p∧q, p∨q,p→q,p?q如果p,q为命题常量,这些复合命题为命题如果p,q为命题变量,这些复合命题为命题公式命题公式:由命题常量、命题变量、逻辑联结词、括号等构成的有效字符串 命题公式及分类 定义6:1. 单个命题常项或变项p,q,r,…,pi,qi,ri ,0,1是合式公式2. 如果A是合式公式,则(?A)为合式公式3. 如果A,B是合式公式,则(A∧B),(A∨ B) ,(A→B) , (A B)也是合式公式4. 只有有限次地应用1-3组成的符号串才是合式公式命题逻辑下的合式公式:命题公式,公式例子:q qvr 公式的层次 定义7若A为单个命题(常项或变项)p,q,r,pi,qi, ri, …,0,1,则称A为0层公式称A是n+1 (n>

=0)层公式是指A符合下列情况之一:A ? ?B,B为n层公式A ? B∧C, 其中B,C分别为i,j层公式,且n= max(i,j)A ? B∨C, 其中B,C的层次同2A ? B→ C, 其中B,C的层次同2A ? B ?C, 其中B,C的层次同2 命题公式的赋值或解释 命题公式中命题常项和变项,不是命题,只有对命题公式中的所有命题变项进行赋值,公式的真值才能够确定下来,才能够变成命题定义8:设A为一个命题公式,p1,p2,…,pn为出现在A中的所有命题变项,给指定一组真值,称为对A的一个赋值或解释.如果指定的一组值使A的值为真,则称这组值为成真赋值,如果指定的一组值使A的值为假,则称这组值为成假赋值. 公式的真值表 真值表:含有n个变项的公式,其赋值有2n个,将每一个赋值及公式在此赋值下的真值构成的表例子: (p∧(p→q)) →q 公式的性质 定义9设A为一个命题公式若A在它的各种赋值下取值均为真,则称A为重言式或永真式(真值表最后一列全为1)若A在它的各种赋值下取值均为假,则称A为矛盾式或永假式(真值表最后一列全为0)若A至少存在一组赋值是成真赋值,则称A为可满足式(真值表最后一列有1) 等值演算 判断公式性质的办法真值表等值演算将之演算成简单形式,判断其性质定义10设A,B为2个命题公式,若等价式A B是重言式,则称A与B是等值的,记做A B? :不是逻辑联结词,一个等值的记号,不能够用=(数值上的相等)代替等值本质上是指:公式A和B在任何解释下都相等 逻辑等值式 逻辑等值式 逻辑等值式 等值演算 利用等值式,将一个公式变换成另外一种形式的过程例子 等值演算 等值演算 简单析取式及简单合取式 简单析取式和简单合取式定义10:仅由有限个命题变项或其否定构成的析取式称为,简单析取式;

仅由有限个命题变项或其否定构成的合取式称为,简单合取式例子:简单析取式:p, q, p∨?q, ?p∨q, ?p∨?q∨r简单合取式:p, q, p∧?q, ?p∧q, ?p∧?q∧r 合取范式 定义11:仅有有限个简单析取式构成的合取式称为合取范式A=A1∧A2∧…∧An其中A1,A2,…,An为简单析取式例子:A=(?p∨q∨r)∧(?p∨q)∧(q∨?q)任何公式都有与其对应的合取范式 化成合取范式的步骤 1. 消去对{?,∧,∨}来说冗余的联结词2. 否定联结词的消除或内移3. 利用分配率 合取范式 原子:命题常项或变项文字:原子或原子的否定 子句:文字的析取合取范式:子句的合取子句集:合取范式的集合表示每一个合取项作为集合的元素元素之间的关系为合取 命题逻辑的问题 命题作为命题演算的基本单位,不再分解无法研究命题内部的结构和命题之间的联系例子:苏格拉底三段论p:凡人都是要死的q:苏格拉底是人r:苏格拉底是要死的命题符号化: (p∧q)→r 真值不定!解决问题的办法将命题进一步分解成:个体词,谓词和量词等研究它们的形式结构和逻辑关系,总结出正确地推理形式和规则一阶谓词逻辑