人工智能的数学基础.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,模式识别与智能系统研究所,版权所有,人工智能的数学基础,-1,人工智能导论,人工智能的数学基础,-1,信息学院：韩延彬,课程进度,人工智能原理与应用,前言,绪论,数学,基础,知识,表示,(1),知识,表示,(2),经典,逻辑,推理,(1),经典,逻辑,推理,(2),经典,逻辑,推理,(3),经典,逻辑,推理,(4),课程,设计,(1),课程,设计,(2),不确,定推,理,(1),不确,定推,理,(2),不确,定推,理,(3),经典,逻辑,推理,(5),本节知识框架,回顾上一节课的内容,重点：智能、人工智能的定义，研究目标（,2,），基本内容（,5,）,人工智能的研究途径（,3,）,为什么要研究数学,思维,形式化、符号化,人工智能,研究课题基础,逻辑、概率、模糊,知识的表示与处理中占有重要地位。,因此，在系统学习人工智能的理论与技术之前，,先掌握些有关逻辑、概率论及模糊理论方面的知识是很有必要的。,命题逻辑与谓词逻辑,谓向逻辑是在命题逻辑基础上发展起来的，命题逻辑可看作是谓词逻辑的一种特殊形式,命题逻辑与谓词逻辑命题（,1,）,什么是命题？,命题是具有真假意义的语句,命题代表人们进行思维时的一种判断，或者是肯定，或者是否定，只有这两种情况,例子：,北京是中华人民共和国的首都。,35,。,太阳从西边升起。,我今天吃的很饱。,多么美丽的祖国。,我吃的很饱是一个命题。,表示形式用,P,描述,命题逻辑与谓词逻辑命题,命题,语句,真假含义,注意：语句和真假的含义缺一不可,命题逻辑与谓词逻辑命题,命题逻辑的局限性？,无法把它所描述的客观事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特征表述出来。,例如：,老李是小李的父亲,李白是诗人，杜甫也是诗人。,思考？,面对这样的问题，我们怎样解决？提示：,通常在编程当中，我们采用什么样的方式来解决相同特征的问题，,函数（,Function,）,命题逻辑与谓词逻辑谓词,谓词,谓名词,个体,函数名称,参变量,个体表某个独立存在的事物或者某个抽象的概念,谓名词用于刻画个体的性质、状态或个体间的关系,命题逻辑与谓词逻辑谓词,老张是教师,Teacher,（,Zhang,）,谓名词,个体,Teacher,刻画了,zhang,的职业是教师？,如果是老李也是教师，怎么描述,命题逻辑与谓词逻辑谓词,5,3,：,Greater(5,3),。,Greater(3,5)?,谓词的一般形式是：,P(x,1,x,2,x,n,),谓词名：,个体：,通常情况谓词名用大写表示，而个体用小写表示,谓词的个体，可以是一个常量，也可以是一个变元，还可以是一个函数,例如：,X,5,：,Less,（,x,5,）,小王的父亲是教师：,Teacher(Father(Wang,),比较,C,中的函数,命题逻辑与谓词逻辑谓词,几个概念：,当谓词中的变元都用特定的个体取代时，谓词就具有一个确定的真值：,T,或,F,P(x,1,x,2,x,n,),，其中,n,是阶数,个体变元的取值范围成为个体域。有限，无限,谓词和函数的联系和区别,个体常量、个体变元、函数统称为“项”,采用谓词有什么样的优点,命题逻辑与谓词逻辑谓词公式,谓词公式：无论是命题逻辑还是谓词逻辑，可以利用连接词把一些简单的命题连接起来构成一个合命题，表示一个比较复杂的含义。,非,合取,析取,条件或者蕴含，,pq,双条件：当且仅当,命题逻辑与谓词逻辑谓词公式,量词,全称量词,存在量词,P(x,),表示是证书，,F(x,y,),表示,x,，,y,是朋友,命题逻辑与谓词逻辑谓词公式,谓词公式：,单个谓词是合式公式，成为原子谓词公式,若,A,是合式公式，则,A,也是合式公式,若,A,，,B,都是合式公式，则,AB,，,AB,，,AB,，,AB,若,A,是合式公式，,X,是任一个体变元，包含全称量词和存在量词的也是合式公式,命题逻辑与谓词逻辑谓词公式,分析一个谓词公式,约束变元,自由变元,变元换名原则,:,同名的约束变元应该统一变成相同的名字，注意约束条件也得修改,谓词公式的解释,在命题逻辑中，对命题公式中各个命题变元的一次真值指派成为命题公式的一个解释,形象理解：赋值,函数值,谓词公式的解释：,设,D,为谓词公式,P,的个体域，若对,P,中的个体常量，函数和谓词按如下规定赋值：,（,1,）为每个个体常量指派,D,中的一个元素,（,2,）为每个,n,元函数指派一个从,D,n,到,D,的映射，其中,D,n,（,x1,x2,xn,）,/x1,x2,xnD,（,3,）为每个,n,元谓词指派一个从,D,n,到,F,T,的映射，责成这些指派为公式,P,在,D,上的一个解释。,谓词公式的解释,例如个体域,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,是永真的,谓词公式的永真性、可满足性等,永真性：如果谓词公式,P,对个体域,D,上的任何一个解释都取得真值,T,，则称,P,在,D,上是永真的；如果,P,在每个非空个体域上均永真，则称,P,在每个非空个体域上均永真，则称,P,永真。,可满足性：对于谓词公式,P,，如果至少存在一个解释使得公式,P,在此解释下的真值为,T,，则称公式,P,是可满足的。,不可满足性：如果谓词公式,P,对于个体域,D,上的任何一个解释都取得真值,F,，则称,P,在,D,上是永久假的，如果,P,在每个非空个体域上均永假，则称,P,永假。,谓词公式的等价性与永真蕴含,交换律：,PQ Q P,PQ Q P,结合律：,(PQ)R P(Q R),(P Q)R P(Q R),分配律：,P(QR)(PQ)(P R),P(Q R)(P Q)(P R),德,.,摩根律,！,(P Q),！,P !Q,！,(P Q),！,P !Q,双重否定,！,P P,吸收律,P(PR)P,P(P R)P,谓词公式的等价性与永真蕴含,补余律,P,！,P T!P P F,结合律,(PQ)R P(Q R),(P Q)R P(Q R),连接词化归律,PQ,！,P Q,量词转化律,谓词公式的等价性与永真蕴含,谓词公式的等价性与永真蕴含,P,规则：推理的任何步骤可以引入的前提,T,规则：前面推出的结论，在后续的推理中，使用,CP,规则：从,R,和前提结合中推出来,S,，使用结论,RS,反证法：,这些规则在后续的讨论中，我们在进行相关介绍。,多值逻辑,经典命题逻辑和谓词逻辑的语义解释只有两个：真和假，,0,和,1,。,现实生活中的某些问题不是简单的真和假的问题，而是存在于真和假之间的某个位置上（甚至更复杂）,三值逻辑：第三个结论有很多讨论，有人提出无意义这个值，是为了解决悖论,多值逻辑,命题取值只能有三个：真，假，还有一个（无意义，不能判定：,悖论,）,城里所有不自己刮脸的男人都由我给他们刮脸，我也只给这些人刮脸,。,命题：理发师给自己刮脸吗？,www.oursci.org,/lib/paradox/,概率论,概率论,为什么要引入概率论,概率,关系,模拟,概率论是研究随机现象中数量规律的一门学科。反应了事物的不确定性,概率论随机现象,在相同的条件下重复进行某种试验时，试验结果不一定完全相同且不可预知的现象称为随机现象。,难忘一课（老师名单）,样本空间与随机事件,在试验中每一个可能出现的结果称为试验的一个样本点，由样本电的全体构成的集合称为样本空间。,抛硬币：,2,个,色子：,6,个,彩票：？，中彩票的概率是多少？,样本空间与随机事件,我们把要考察的由一些样本点构成的集合称为随机事件，简称事件。,在某次试验中，若事件包含的某一个样本点出现，就称这一事件发生。,必然事件，不可能事件。,样本空间与随机事件,事件的概率,表示事件发生可能性大小的数称为事件概率,P(A),古典概型：如果随机试验,E,的样本空间,D,中只包含有限个基本条件，并且在每次试验中每个基本事件发生的可能性相同，则称,E,为古典型随机试验，简称古典概型。,P(A)=m/n,如：,1,2,7,这,7,个数字当中，取一个数字,A,取数字,3,的倍数,B,取偶数,事件的概率,统计概率,在同一组条件下所做的大量重复试验中，事件,A,出现的频率,f,n,(A,),总是在,0,1,上的一个确定的常数,p,附近摆动，并且稳定于,p,，则称,P,为事件,A,的概率。,硬币，色子等,事件的概率,P(A)0,1,必然事件,P(D)=1,不可能事件,P(D)=0,P(!A)=1-P(A),P(AB),P(A)+P(B)-P(AB),A1,A2,An,两两互补相容,:?,事件,B,是事件,A,的子集：,P(A-B)=P(A)-P(B),条件概率,假设,A,与,B,是某个随机试验中的两个事件，如果在事件,B,发生的条件下考虑事件,A,发生的概率，就称它为事件,A,的条件概率，,P(A/B),P(A/B)=P(AB)/P(B),S=,（,1,2,3,4,5,6,7,）,A:,取,3,的倍数,P(A),2/7,B:,取偶数,P(B),3/7,D,：是,3,的倍数，又是偶数：,p(D,)=1/7,P(A/B),1/3,全概率公式,设事件,A1,An,满足：,两两互补相容,P(Ai,)0,D=P(Ai,),P(B)=P(Ai)P(B,/Ai),全概率公式,Bayes,公式,P(Ai/B)=P(Ai)P(B/Ai)/(P(Aj)P(B/Aj,),这个公式就是著名的,Bayes,公式，我们怎样取理解这个公式的内容？,先验概率和后验概率的转换,本课知识总结,作业,什么是命题,什么是谓词公式,欲穷千里目更上一层楼，翻译命题,在,0,1,9,，这,10,个数字当中，一次任取两个，问抽到,5,这个数字的概率,