人工智能的数学基础课件.ppt

1、第二章 人工智能的数学基础本章主要介绍有关逻辑、概率论、模糊理论方面的知识逻辑 -经典命题逻辑和一阶谓词逻辑：二值逻辑 -除经典逻辑外的那些逻辑 三值逻辑 多值逻辑 模糊逻辑 经典平行 模态逻辑 时态逻辑 经典扩充（语言、定理）2.1命题逻辑与谓词逻辑 谓词逻辑是在命题逻辑基础上发展起来的，命题逻辑是谓词逻辑的一种特殊形式。 1. 命题：是具有真假意义的语句。代表人们进行思维时的一种判断，或肯定（真T），或否定（假F），只有两种情况。 例：永真 北京是中华人民共和国的首都 有条件 1 1=10是在二进制条件下成立 命题通常用大写字母表示 命题的缺陷是无法表达结构、逻辑关系2 谓词：一个谓词可分

2、为 谓词名个体 两部分。 谓词名用于刻画个体的性质、状态或个体间的关系，个体表示某个独立存在的事物或某个抽象的概念。 谓词的一般形式：P(x1,x2,.,xn) -谓词名用大写字母 -个体用小写字母，可为常量、变元、函数 谓词中包含的个体数目称为谓词的元数 P(x) 一元谓词 P(x，y) 二元谓词 P(x1,x2,.,xn) n元谓词 在P(x1,x2,.,xn)中，若xi (i=1,n) 都是个体常量、变元、函数，称它为一阶谓词。如果xi本身又是一个一阶谓词，称为二阶谓词个体变元的取值范围称为个体域(有限，无限)个体常量、个体变元、函数统称为“项” 例： 老张是教师 Teacher(zha

3、ng) 谓词名 个体 53 Greater(5,3) 谓词名 个体 小王的父亲是教师 Teacher(Father(zhang)谓词公式（1）连接词 ：否定、非，P为真， P为假：合取，与：析取，或：条件，蕴含PQ,如果P 则 Q : 双条件 P Q P当且仅当Q P Q P PQ PQ PQ P Q T T F T T T T T F F T F F F F T T T F T F F F T F F T T(2)量词全称量词( X): 对个体域中所有（任一个）个体X存在量词( X): 个体域中存在个体X例 P(x) 表示x是正数 F(x,y) 表示x与y是朋友 ( x)P(x) 表示个体域

4、中所有个体x都是正数 ( x) ( y)F(x，y)表示个体域中任何一个x，都存在个y，x与y是朋友(3) 谓词公式单个谓词是合式公式，称为原子谓词公式若A是合式公式，则A是合式公式若A、B都是合式公式，则AB,AB,AB, A B也都是合式公式若A是合适公式，x是任意个体变元，则( x)A(x)和( x)A(x)也都是合式公式在合式公式中，连词的优先级别是、 、 、 、n辖域内与量词中同名的变元称为约束变元，其他称为自由变元( x)P(x,y) Q(x,y) R(x,y)(4) 谓词公式的解释：在命题逻辑中，对命题公式中各个命题变元的一次真值指派称为命题公式的一个解释。定义：设D为谓词公式P

5、的个体域，若对P中个体常量，函数和谓词按如下规定赋值为每个个体常量指派D 中的一个元素为每个n元函数指派一个从Dn到D的映射，其中Dn =(x1,x2,.,xn)/ x1,x2,.,xnD为每个n元谓词指派一个从Dn到F,T的映射，则称这些指派为公式P到D上的一个解释例：设个体域D=1，2，求公式 在D上的一个解释，并指出在每一种解释下公式A的真值解：在公式A中没有包含个体常量和函数，所以可直接为谓词指派真值，设为 P(1,1)=T, P(1,2)=F, P(2,1)=T, P(2,2)=F这就是公式A在D上的一个解释。在此解释，因为x=1时y=1,使P(x,y)的真值为T；x=2时y=1,使

6、P(x,y)的真值为T，即对于D中的所有x都有y=1使P(x,y)的真值为T，所以在此解释下公式A的真值为T。还可以对公式A中的谓词指派另外一组真值，设为 P(1,1)=T, P(1,2)=T, P(2,1)=F, P(2,2)=F这是对公式A的另一个解释。在此解释下，对D中的所有x（即x=1与x=2） 不存在一个y ，使得公式A的真值为 T，所以在此解释下公式A的真值为F。 公式A在D上共有16种解释。y)y)P(x,x)(A(5) 谓词公式的永真性，可满足性，不可满足性定义1：如果谓词公式P 对个体域D上的任何一个解释都取得真值T，则称P在D上是永真的；如果P在每个非空个体域上均永真，则称

7、P永真。定义2：对于谓词公式P，如果至少存在一个解释使得公式P在此解释下的真值为T，则称公式P是可以满足的。可满足性又称为相容性定义3：如果谓词公式P对于个体域D上的任何一个解释都取得真值F，则称P在D上是永假。谓词公式的永假性称为不可满足性。(6) 谓词公式的等价性与永真蕴含定义：设P与Q是两个谓词公式，D是他们共同的个体域，若对D上的任何一个解释，P与Q都有相同的真假，则称公式P和Q在D上是等价的。记做P Q交换律：PQ QP, PQ QP结合律： (PQ)R P(QR) (PQ)R P(QR)分配律：P( QR ) (PQ)(QR) P( QR ) (PQ)(PR)摩根律： (PQ) P

8、Q (PQ) PQ双重否定律： P P吸收律： P( PQ ) P P( PQ ) P补余律： P P T P P F连接词化归律： PQ P Q (PQ)(QP) P Q (PQ)( PQ)量词转换律： ( x)P ( x)(P) ( x)P ( x)(P)量词分配律: ( x)(PQ) ( x)P( x)Q ( x)(PQ) ( x)P( x)Q定义：对于谓词公式P和Q，如果PQ永真，则称P永真蕴含Q，且称Q为P的逻辑结论，称P为Q的前提，记作 P Q化简式 P Q P P Q Q附加式 P P Q P P Q 析取三段论 P ， P Q Q假言推理 P, PQ Q拒取式 Q， PQ P

9、假言三段论 PQ， QR PR二难推论 P Q ， PR， QR R全称固化 ( x)P(x) P(x)存在固化 ( x)P(x) P(x)2.2 概率论1随机现象 在相同条件下做同一个实验时，得到的结果可能相同，也可能不相同，而且在实验之前无法预言一定会出现哪一个结果，具有偶然性。例 投硬币2样本空间与随机事件样本空间：把实验中每一个可能出现的结果称为试验的一个样本点。由样本点的全体构成的集合称为样本空间。若d表示样本点，D表示样本空间，则有 硬币 D=d1，d2 投篮 D=d1，d2 ，. ， dn随机事件：由一些样本点构成的集合称为随机事件。用大写字母表示。 -由全体样本点构成的集合（样

10、本空间）所表示的事件是一个必然要发生的事件，称为必然事件，记为D. -由空集所表示的事件，即不包含任何样本点的事件，在任何一次试验中都不会发生，称为不可能事件，记为事件之间的关系 -事件的包含：若事件A的发生必然导致事件B的发生，A的样本点是B的样本点，称B包含A,记做B A或A B -事件的并(和)：事件A与事件B至少有一个发生， A B -事件的交(积)：事件A与事件B同时发生，A B -事件的差：事件A发生而事件B不发生A-B -事件的逆：若事件A与B同时满足AB= ，A B=D,则A与B为互逆事件，A B或B A3事件的概率 表示事件发生可能性大小的数称为事件的概率。若A表示某一事件，

11、它的概率记做P(A) (1)古典概率：如果随机试验E的样本空间D中只包含有限个基本事件，并且在每次试验中每个基本事件发生的可能性相同，则称E为古典随机试验，简称为古典概率。 定义：设E为古典概率，样本空间中共有n个基本事件，事件A中含有m个基本事件，则称P(A)=m/n为事件A的概率。 例：A=取数字3的倍数，事件为1,2,3,7 P(A)=2/7(n=2,m=7)(2)统计概率：一个事件A发生的次数m与试验的总次数n之比 fn(A)=m/n 是一个常数p（0 p1）定义：在同一组条件下所作的大量重复试验中，事件A出现的频率fn(A)总是在0,1上的一个确定的常数P附近摆动，并且稳定与p ，则

12、称p为事件A的概率P(A)=p(3) 概率的性质对于任意事件A，有0P(A)1必然事件D的概率P(D)=1，不可能事件 的概率P( )=O设事件A1,A2,Ak(k0 (1in)D= Ai则对任何时间B有下式成立 P(B)= 全概率公式k1iU)/()(1iniiABPAP(2)Bayes公式 定理：设事件A1,A2,An满足定理1规定的条件，则对任何事件B有下列Bayes公式成立n1jjjiii)P(B/A)P(A)P(B/A)P(A/B)P(An,.,2, 1iP(B)P(B/A)P(A/B)P(Aiii2.3 模糊理论1. 模糊性：是指客观事物在形态及类属方面的不分明性 例：“某人个子高

13、”，“某个人个子较高” 分解线是模糊的2. 集合与特征函数范围-问题的论域集合用大写字母A，B，.表示，集合元素用小写字母a，b，若a属于A，记aA，a不属于A，记Aa 定义：设A是论域上的一个集合，对任意uU，令 集合A的特征函数 u=UoUo，CA(UoUo)称为UoUo对A的隶属度 A=u| CA(U U)=1模糊集集合A就是其特征函数值等于1的元素所构成的集合 Au0Au1CA当当3. 模糊集与隶属函数定义：设U是论域， 是把任意uU映射为0,1 上某个值的函数，即 ， ，则 称 为定义在U上的一个隶属函数，由 (uU)所构成的集合A称为U上的一个模糊集， 称为 u对A的隶属度。 例：

14、U=1, 2, 3, 4, 5 A=0,0,0.1,0.6,1 较小 较大 B=1,0.5,0.01,0,0A0,1U:A)u(uA(u)A(u)A(u)AAAAAABBBBB (1)=0 (2)=0 (3)=0.1 (4)=0.6 (5)=1 (1)=1 (2)=0.5 (3)=0.01 (4)=0 (5)=04 模糊集的表示方法(1) 若论域是离散且为有限集 U=u1 1,u2 2,un n时，其模糊集可表示为： 为了具体指出论域元素和其隶属度之间的对应关系，模糊集表示为： 也可以表示为： 模糊集还可表示为： )(u),.,(u),(uAnA2A1AA11A22AnnA (u )/u +

15、(u )/u +.+ (u )/uAii1A (u )/uniA11A22AnnA (u )/u , (u )/u ,., (u )/u A11A22AnnA( (u ),u ),( (u ),u ),.,( (u ),u )(2) 若论域是连续的，可用函数表示，若年龄论域0,100，给出“年老”，“年轻”两个模糊概念的隶属度函数。其模糊集为(3) 论域有限、无限、连续、离散、扎德表示模糊集A 001u05)25-u/(5(1 50u00)u(001u25)5/ )25-u(1 25u01)u(121年老年轻u/ )u(AUuA5. 模糊集的运算(1)包含运算 A,B ,对任意uU，都有 成立

16、，则称A包含B，记 (2) 并、交、补运算 A，B ，分别称 (并)， (交)， (补) 隶属函数为：)U(u)AB (u)ABBABA)u(1)u(:A(u)(u)u(:BA(u)(u),min)u(:BA(u)(u)u(:BA(u)(u),max)u(:BAAABABABABABABABABAA)U(例：U=u1,u2,u3 A=0.3/u1+0.8/u2+0.6/u3 B=0.6/u1+0.4/u2+0.7/u3 AB =(0.30.6)/u1+(0.8 0.4)/u2+(0.6 0.7)/u3 =0.3/u1+0.4/u2+0.6/u36 模糊关系及其合成(1) 设U和V是两个集合，则

17、称下式为U与V的笛卡尔积： UxV=(u,v)|u U，v V 也就是说，由U和V上所有可能的序偶(u，v)构成的集合，就是U与V的笛卡尔积。 所谓从U到V的关系R，是指UxV上的一个子集，即 记为 ，对于UxV中的元素(u,v)，若 ，则称u，v有关系R，若 ，则称u，v没有关系R。 例 设U=红桃，方块，黑桃，梅花 V=1,2,3,4,5,6,7,8,9,10,J,Q,K 则UxV中有52个元素 VURVURv)(u,Rv)(u,定义：设Ai是Ui(i=1,2,n)上的模糊集，则称为A1 ,A2, An的笛卡尔积，它是U1 xU2xxUn上的一个模糊集.定义：在U1 xU2xxUn上的一个

18、n元模糊关系R是指以U1 xU2xxUn为论域的一个模糊集，记为),/()()()(2121212121nUUUnAAAnuuuuuuAAAnn),/(),(212121nUUUnRuuuuuuRn121212(,) /(,)RUURu uu u)v,u ()v,u ()v,u ()v,u ()v,u ()v,u ()v,u ()v,u ()v,u (RnmR2mR1mRn2R22R12Rn1R21R11R一般地说，当U与V都是有限论域时，其模糊关系R可用一个模糊矩阵表示，设 U=u1,u2, .,um V=v1,v2, .,vn(2) 模糊关系的合成 定义：设R1与R2分别是UxV与VxW上

19、的两个模糊关系，则R1与R2的合成是从U到W的一个模糊关系，记为R1R2，其隶属函数为 例： )w(v,v)(u,V)wu,(2121RRRR10.40.50.1R0.20.60.20.50.30.220.20.8R0.40.60.60.4120.40.5R=RR0.40.60.30.5 其方法是取R1的第i行元素分别与R2的第j列的对应元素相比较，两个数中取其小者，然后再在所得的一组最小数中取最大的一个，作为R1R2的第i行，第j列的元素。7 模糊变换定义：设 是论域上的模糊集，R是UxV上的模糊关系，则AR=B称为模糊变换A1A2AnA= (u ), (u ),L, (u )0.2,0.5,0.3A 0.20.70.1000.40.50.10.20.30.40.1RB=A0.2,0.4,0.5,0.1 R