人工智能的数学基础153

模式识别与智能系统研究所@版权所有人工智能的数学基础-1人工智能导论人工智能的数学基础-1信息学院：韩延彬模式识别与智能系统研究所@版权所有人工智能的数学基础-1课程进度人工智能原理与应用前言绪论数学基础知识表示(1)知识表示(2)经典逻辑推理(1)经典逻辑推理(2)经典逻辑推理(3)经典逻辑推理(4)课程设计(1)课程设计(2)不确定推理(1)不确定推理(2)不确定推理(3)经典逻辑推理(5)模式识别与智能系统研究所@版权所有人工智能的数学基础-1本节知识框架人工智能的数学基础(1)命题逻辑与谓词逻辑多值逻辑（扩展）概率论命题谓词谓词公式谓词公式的一些特性随机现象样本空间与随机事件事件的概率条件概率模式识别与智能系统研究所@版权所有人工智能的数学基础-1回顾上一节课的内容绪论什么是人工智能人工智能的研究目标及内容人工智能的研究途径人工智能的研究领域智能人工智能发展简史研究目标基本内容符号处理为核心网络连接为主的专家系统机器学习模式识别自然语言理解等10重点：智能、人工智能的定义，研究目标（2），基本内容（5）,人工智能的研究途径（3）模式识别与智能系统研究所@版权所有人工智能的数学基础-1为什么要研究数学思维形式化、符号化人工智能研究课题基础逻辑、概率、模糊知识的表示与处理中占有重要地位。因此，在系统学习人工智能的理论与技术之前，先掌握些有关逻辑、概率论及模糊理论方面的知识是很有必要的。模式识别与智能系统研究所@版权所有人工智能的数学基础-1人工智能的数学基础(1)命题逻辑与谓词逻辑多值逻辑（扩展）概率论命题谓词谓词公式谓词公式的一些特性随机现象样本空间与随机事件事件的概率条件概率模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑命题逻辑与谓词逻辑命题谓词谓词公式谓词公式的解释谓词公式的永真性、可满足性、不可满足性谓词公式的等价性与用真蕴含谓向逻辑是在命题逻辑基础上发展起来的，命题逻辑可看作是谓词逻辑的一种特殊形式模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑－命题（1）什么是命题？命题是具有真假意义的语句命题代表人们进行思维时的一种判断，或者是肯定，或者是否定，只有这两种情况例子：北京是中华人民共和国的首都。3≤5。太阳从西边升起。我今天吃的很饱。多么美丽的祖国。我吃的很饱是一个命题。表示形式用P描述模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑－命题命题语句真假含义注意：语句和真假的含义缺一不可模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑－命题命题逻辑的局限性？无法把它所描述的客观事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特征表述出来。例如：老李是小李的父亲李白是诗人，杜甫也是诗人。思考？面对这样的问题，我们怎样解决？提示：通常在编程当中，我们采用什么样的方式来解决相同特征的问题，函数（Function）模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑－谓词谓词谓名词个体函数名称参变量个体表某个独立存在的事物或者某个抽象的概念谓名词用于刻画个体的性质、状态或个体间的关系模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑命题谓词谓词公式谓词公式的解释谓词公式的永真性、可满足性、不可满足性谓词公式的等价性与用真蕴含模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑－谓词老张是教师Teacher（Zhang）谓名词个体Teacher刻画了zhang的职业是教师？如果是老李也是教师，怎么描述模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑－谓词5＞3：Greater(5,3)。Greater(3,5)?谓词的一般形式是：P(x1,x2,…,xn)谓词名：个体：通常情况谓词名用大写表示，而个体用小写表示谓词的个体，可以是一个常量，也可以是一个变元，还可以是一个函数例如：X＜5：Less（x,5）小王的父亲是教师：Teacher(Father(Wang))比较C中的函数模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑－谓词几个概念：当谓词中的变元都用特定的个体取代时，谓词就具有一个确定的真值：T或FP(x1,x2,…,xn)，其中n是阶数个体变元的取值范围成为个体域。有限，无限谓词和函数的联系和区别个体常量、个体变元、函数统称为“项”采用谓词有什么样的优点模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑命题谓词谓词公式谓词公式的解释谓词公式的永真性、可满足性、不可满足性谓词公式的等价性与用真蕴含模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑－谓词公式谓词公式：无论是命题逻辑还是谓词逻辑，可以利用连接词把一些简单的命题连接起来构成一个合命题，表示一个比较复杂的含义。非合取析取条件或者蕴含，p→q双条件：当且仅当模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑－谓词公式量词全称量词存在量词P(x)表示是证书，F(x,y)表示x，y是朋友)()(xPx),()()(yxFyx),()()(yxFyx模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑－谓词公式谓词公式：单个谓词是合式公式，成为原子谓词公式若A是合式公式，则┐A也是合式公式若A，B都是合式公式，则A∧B，A∨B，A→B，A←→B若A是合式公式，X是任一个体变元，包含全称量词和存在量词的也是合式公式模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑－谓词公式分析一个谓词公式),()),(),()((yxRyxQyxPx约束变元自由变元变元换名原则:同名的约束变元应该统一变成相同的名字，注意约束条件也得修改模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑命题谓词谓词公式谓词公式的解释谓词公式的永真性、可满足性、不可满足性谓词公式的等价性与用真蕴含模式识别与智能系统研究所@版权所有人工智能的数学基础-1谓词公式的解释在命题逻辑中，对命题公式中各个命题变元的一次真值指派成为命题公式的一个解释形象理解：赋值→函数值谓词公式的解释：设D为谓词公式P的个体域，若对P中的个体常量，函数和谓词按如下规定赋值：（1）为每个个体常量指派D中的一个元素（2）为每个n元函数指派一个从Dn到D的映射，其中Dn＝｛（x1,x2,…,xn）/x1,x2,…,xn∈D｝（3）为每个n元谓词指派一个从Dn到｛F,T｝的映射，责成这些指派为公式P在D上的一个解释。模式识别与智能系统研究所@版权所有人工智能的数学基础-1谓词公式的解释例如个体域D＝｛1,2｝，求公式在D上的某一个解释解:个体常量b＝1，f(1)=2,f(2)=1对谓词指派的真值：P(1)=F,P(2)=T,Q(1,1)=T,Q(2,1)=F当x=1时P(1)=F,Q(f(1),1)=Q(2,1)=FP(1)→Q(f(1),1)＝T同理x=2时，T当前的解释是的公式B是永真的))),(()()((bxfQxPxB模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑命题谓词谓词公式谓词公式的解释谓词公式的永真性、可满足性、不可满足性谓词公式的等价性与用真蕴含模式识别与智能系统研究所@版权所有人工智能的数学基础-1谓词公式的永真性、可满足性等永真性：如果谓词公式P对个体域D上的任何一个解释都取得真值T，则称P在D上是永真的；如果P在每个非空个体域上均永真，则称P在每个非空个体域上均永真，则称P永真。可满足性：对于谓词公式P，如果至少存在一个解释使得公式P在此解释下的真值为T，则称公式P是可满足的。不可满足性：如果谓词公式P对于个体域D上的任何一个解释都取得真值F，则称P在D上是永久假的，如果P在每个非空个体域上均永假，则称P永假。模式识别与智能系统研究所@版权所有人工智能的数学基础-1命题逻辑与谓词逻辑命题谓词谓词公式谓词公式的解释谓词公式的永真性、可满足性、不可满足性谓词公式的等价性与用真蕴含模式识别与智能系统研究所@版权所有人工智能的数学基础-1谓词公式的等价性与永真蕴含交换律：P∨Q←→Q∨P,P∧Q←→Q∧P结合律：(P∨Q)∨R←→P∨(Q∨R)(P∧Q)∧R←→P∧(Q∧R)分配律：P∨(Q∧R)←→(P∨Q)∧(P∨R)P∧(Q∨R)←→(P∧Q)∨(P∧R)德.摩根律！(P∨Q)←→！P∧!Q！(P∧Q)←→！P∨!Q双重否定！！P←→P吸收律P∨(P∧R)←→P,P∧(P∨R)←→P模式识别与智能系统研究所@版权所有人工智能的数学基础-1谓词公式的等价性与永真蕴含补余律P∨！P←→T!P∧P←→F结合律(P∨Q)∨R←→P∨(Q∨R)(P∧Q)∧R←→P∧(Q∧R)连接词化归律P→Q←→！P∨Q量词转化律))(()())(()(PxPxPxPx模式识别与智能系统研究所@版权所有人工智能的数学基础-1谓词公式的等价性与永真蕴含)()().(9)()().(8,,.7,.6,.5,.4,.3,.2,.1yPxPxyPxPxRRQQPQPRPRQQPPQPQQQPPQQPPQPQQPPQQPPQP模式识别与智能系统研究所@版权所有人工智能的数学基础-1谓词公式的等价性与永真蕴含P规则：推理的任何步骤可以引入的前提T规则：前面推出的结论，在后续的推理中，使用CP规则：从R和前提结合中推出来S，使用结论R→S反证法：这些规则在后续的讨论中，我们在进行相关介绍。模式识别与智能系统研究所@版权所有人工智能的数学基础-1人工智能的数学基础(1)命题逻辑与谓词逻辑多值逻辑（扩展）概率论命题谓词谓词公式谓词公式的一些特性随机现象样本空间与随机事件事件的概率条件概率模式识别与智能系统研究所@版权所有人工智能的数学基础-1多值逻辑经典命题逻辑和谓词逻辑的语义解释只有两个：真和假，0和1。现实生活中的某些问题不是简单的真和假的问题，而是存在于真和假之间的某个位置上（甚至更复杂）三值逻辑：第三个结论有很多讨论，有人提出无意义这个值，是为了解决悖论模式识别与智能系统研究所@版权所有人工智能的数学基础-1多值逻辑命题取值只能有三个：真，假，还有一个（无意义，不能判定：悖论）城里所有不自己刮脸的男人都由我给他们刮脸，我也只给这些人刮脸。命题：理发师给自己刮脸吗？@版权所有人工智能的数学基础-1人工智能的数学基础(1)命题逻辑与谓词逻辑多值逻辑（扩展）概率论命题谓词谓词公式谓词公式的一些特性随机现象样本空间与随机事件事件的概率条件概率模式识别与智能系统研究所@版权所有人工智能的数学基础-1概率论概率论随机现象样本空间与随机事件事件概率条件概率全概率公式与Bayes公式模式识别与智能系统研究所@版权所有人工智能的数学基础-1概率论为什么要引入概率论概率关系模拟概率论是研究随机现象中数量规律的一门学科。反应了事物的不确定性模式识别与智能系统研究所@版权所有人工智能的数学基础-1概率论随机现象样本空间与随机事件事件概率条件概率全概率公式与Bayes公式模式识别与智能系统研究所@版权所有人工智能的数学基础-1概率论－随机现象在相同的条件下重复进行某种试验时，试验结果不一定完全相同且不可预知的现象称为随机现象。难忘一课（老师名单）模式识别与智能系统研究所@版权所有人工智能的数学基础-1概率论随机现象样本空间与随机事件事件概率条件概率全概