人工智能-2数学基础.ppt

1、第二章人工智能的数学基础,2.1 命题逻辑与谓词逻辑 2.2 多值逻辑 2.3 概率论 2.4 模糊理论,AI中的逻辑,可划分为两大类： 经典逻辑 命题逻辑和一阶谓词逻辑。 特点：二值 非经典逻辑 三值逻辑、多值逻辑、模糊逻辑、模态逻辑、时态逻辑等等。,非经典逻辑,与经典逻辑平行的逻辑：多值、模糊逻辑 一些定理不成立，有新概念、新定理。 对经典逻辑的扩充：模态、时态逻辑 一般承认经典逻辑的定理。一是扩充语言；二是扩充定理。 例如：模态逻辑增加了L(是必然的)算子和M(是可能的)算子。,2.1 命题逻辑与谓词逻辑,2.1.1 命题 定义2.1：命题是具有真假意义的语句。 在命题逻辑中命题通常用大

2、写英文字母表示。 命题逻辑无法把客观事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特征表述出来。 例如： P”老李是小李的父亲”。 看不出老李和小李的关系。 P”李白是诗人”，Q”杜甫也是诗人”。 无法形式地表示出二者的共同特点（都是诗人）。 P=“每个人都是要死的”。 Q=“孔子是人”。 R=“孔子是要死的”。 写成命题形式:PQR(R是P, Q的逻辑结论?),2.1.2 谓词（1）,1. 一个谓词分为谓词名与个体两个部分。 谓词名刻画个体的性质、状态或个体间的关系。 个体表示独立存在的事物或者概念。 例如： Teacher(zhang)，Greater(5,3) 谓词的一般形式 P

3、 (x1, x2,xn) 其中，P是谓词名，x1, x2,xn是个体。谓词名通常用大写的英文字母表示，个体通常用小写的英文字母表示。,2.1.2 谓词（2）,2. 个体可以是常量、变元或者函数。 例如： Less(x,5),x是一个变元。 Teacher(father(wang),其中father(wang)是一个函数。 3.谓词的语义由人指定。 例如： S(x)，可以表示x是一个人；也可以表示x是一朵花。,2.1.2 谓词（3）,4. 当谓词中的所有变元都用特定个体取代时，谓词就具有一个确定的真值：T或者F。 谓词中包含的个体数目称为谓词的元数。 例如：P(x)是一元谓词,P(x,y)是二元

4、谓词,P(x1, x2,xn)是n元谓词。 在谓词P(x1, x2,xn)中，若xi (i=1,n)都是个体常量、变元或者函数，则称为1阶谓词。若xi本身是一阶谓词，则P称为2阶谓词。余者类推， 5. 个体变元的取值范围称为个体域。 6. 谓词与函数不同。 谓词是从个体到真值的映射。 函数是从个体到个体的映射。 7. 个体常量、变元、函数统称为“项”。,1. 连接词 非：；析取：；合取：；蕴含：； 等价： ； 谓词逻辑真值表,2.1.3 谓词公式（1）,2.1.3 谓词公式（2）,2. 量词 全称量词 ；存在量词 例如： P(x)表示x是正数；F(x,y)表示x与y是朋友。 表示个体域中任何x

5、都是正数。 表示对于个体域中任何x，都存在y， x与y是朋友。 表示在个体域中存在x，与个体域中任何个体y都是朋友。,2.1.3 谓词公式（3）,3. 谓词公式 定义2.2 按下述规则得到的合式公式： (1)单个谓词是合式公式，称为原子公式； (2)若A是合式公式，则 也是合式公式； (3)若A，B是合式公式，则 都是合式公式； (4)若A是合式公式，x是任一个体变元，则 都是合式公式； (5)运用有限步上述规则得到的公式是合式公式。,2.1.3 谓词公式（4）,辖域：位于量词后面的单个谓词或者用括弧括起来的合式公式称为量词的辖域。 辖域内与量词中同名的变元称为约束变元，不受约束的变元称为自由

6、变元。 例如： 更名：变元名称无关紧要。 注意：对量词辖域内的变元更名时，必须把同名的约束变元都统一改成相同名字，且不能与辖域内自由变元同名。辖域内自由变元也不能改为与约束变元同名。 例如：,2.1.4 谓词公式的解释（1）,在命题逻辑中对各命题变元的一次真值指派称为命题公式的一个解释。 对于谓词逻辑： 首先考虑个体常量和函数在个体域中的取值，然后为谓词分别指派真值。由于存在多种组合情况，所以一个谓词公式的解释可能有多个。对每一个解释，谓词公式都可求出一个真值。,2.1.4 谓词公式的解释（2）,定义2.3 设D为谓词公式P的个体域，对P中个体常量、函数和谓词按如下规定赋值： 为每个个体常量指

7、派D中一个元素； 为每个n元函数指派一个DnD的映射， Dn=(x1,xn)|x1,xnD 为每个n元谓词指派一个DnF,T的映射。 则称这些指派为公式P在D上的一个解释。,2.1.4 谓词公式的解释（3）,例2.1 设D1,2，求公式在D上的一个解释及在该解释下的真值。 解：在A中没有个体常量和函数，所以直接为谓词指派真值。设为 解释1：P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F 当x1时，y1为T； 当x2时，y1为T； 解释2：P(1,1)=T,P(1,2)=T,P(2,1)=F,P(2,2)=F 当x1时，y1,2为T； 当x2时，y1,2为F；因此不存在y

8、，则AF,2.1.4 谓词公式的解释（4）,例2.2 D=1,2, 解： 解释： b=1, f(1)=2, f(2)=1, P(1)=F, P(2)=T, Q(1,1)=T, Q(2,1)=F, Q(*,2)不可能。 当x=1时，P(x)=F，公式真值为T； 当x=2时，P(x)=T,Q(f(x),b)=T，公式真值为T； 所以在此解释下，BT。 真值是针对某一个解释而言的。,2.1.5 谓词公式的永真性、可满足性、不可满足性,定义2.4 如果谓词公式P对个体域D上的任何一个解释都得真值T，则称P在D上是永真的；如果P在每个非空个体域上均永真，则称P永真。 定义2.5 对谓词公式P，如果至少存

9、在一个解释使P在此解释下的真值为T则称公式P是可满足的。 谓词公式的可满足性又称为相容性。 定义2.6 如果谓词公式P对于个体域D上任何一个解释都取得真值F，则称P在D上是永假的；如果P在每个非空个体域上均永假，则称P永假。 谓词公式的永假性又称为不可满足性或不相容性。,2.1.6 谓词公式的等价性与永真蕴含,定义2.7 设P、Q都是D上的谓词公式，若对D上任何一个解释，P与Q都有相同的真值，则称P和Q在D上等价。如果D是任意个体域，则称P和Q是等价的，记为 。 定义2.8 对于谓词公式P和Q，如果PQ永真，则称P永真蕴含Q，且称Q为P的逻辑结论，P为Q的前提，记为。,一些重要的等价式,一些重

10、要的永真蕴含式,推理规则,上述等价式和永真蕴含式可以作为推理规则。除此之外，谓词逻辑中如下一些推理规则： P规则：在推理的任何步骤都可以引入前提。 T规则：推理时，如果前面步骤中有一个或者多个公式永真蕴含公式S，则可把S引入推理过程中。 CP规则：如果能从R和前提集合中推理S来，则可从前提集合推理RS。 反证法：，当且仅当 。即Q为P的逻辑结论，当且仅当 是不可满足的。 定理2.1: Q为P1,P2,Pn的逻辑结论，当且仅当是不可满足的。,2.2 多值逻辑（1）,用T(A)表示命题A为真的程度。 0T(A)1 多值逻辑也定义了用连接词表示的逻辑运算。 T(A)=1-T(A) T(AB)=min

11、T(A),T(B) T(AB)=maxT(A),T(B) T(AB)=min1,1-T(A)+T(B) T(A B)=1-|T(A)-T(B)|,2.2 多值逻辑（2）,其它的T(AB)定义： Rb:T(AB)=min1-T(A),T(B) Rc:T(AB)=minT(A),T(B) Rp:T(AB)=T(A)T(B) R*:T(AB)=1-T(A)+T(A)T(B) Rst:T(AB)=max1-T(A),T(B) ,三值逻辑,关于第三个真值： Kleene：强三值逻辑认为是“不能判定”。条件成熟则非真即假。 Luckasiewicz： 认为是“不确定”，即不真也不假，也许不具有真值。 Bo

12、chvar： “无意义”，非真非假。为了解决语义悖论。 多值逻辑只是用穷举中介的方法表示真值的过渡性，把中介看作彼此独立、界限分明的对象，没有反映出中介之间的相互渗透，因而不能完全解决不确定性知识的表示问题。,2.3 概率论,2.3.1 随机现象 2.3.2 样本空间与随机事件 样本空间： 一个可能的实验结果为一个样本点，样本点的全体构成的集合称为样本空间。 随机事件： 要考察的由一些样本点构成的集合称为随机事件。 事件发生了：出现了样本点集合中的一个元素。 必然事件：样本点全体构成的集合(即样本空间)所表示的事件。 不可能事件： 基本事件：单点集合 事件的关系 包含、并、交、差、逆,2.3.

13、3 事件的概率（1）,古典概型 定义2.9 设E为古典概型，样本空间共有n个基本事件，事件A中含有m个基本事件，则称 P(A) = m/n 为事件A的概率。 例如：D1,2,3,4,5,6,7，A=取数字3的倍数，B=取偶数。 解：基本事件有7个，n7。 对于事件A，m=2，所以P(A) = m/n = 2/7 对于事件B，m=3，所以P(B) = m/n = 3/7,2.3.3 事件的概率（2）,2. 统计概率 当试验次数足够多时，一个事件(A)发生的次数m与试验的总次数n之比： fn(A)=m/n 在一个常数p(0p1)附近摆动，并稳定于p。 定义2.10 在同一组条件下所作的大量重复试验

14、中，事件A出现的频率fn(A)总是在0,1上的一个确定常数p附近摆动，并且稳定于p，则称p为事件A的概率。即 P(A)=p,2.3.3 事件的概率（3）,3. 概率的性质 0P(A)1 P(D)=1,P()=0 设事件A1,A2,Ak(kn)是两两互不相容的事件，即有AiAj=(ij)，则 P(A)=1-P(A) P(AB)=P(A)+P(B)-P(AB) 如果，则P(A-B)=P(A)-P(B),2.3.4 条件概率（1）,如果在事件B发生的条件下考虑事件A发生的概率，就称它为事件A的条件概率，记为P(A|B)。 定义2.11 设A，B是两个事件，P(B)0,则称 为在事件B已发生的条件下事

15、件A的条件概率。 条件概率中的条件缩小了样本空间，即条件概率是在条件所确定的新空间中求AB的概率。,2.3.4 条件概率（2）,例2.6 对于例2.5，求解在事件B发生的条件下，事件A发生的条件概率。 解：事件B是已经发生的事件，即 取到2；取到4；取到6 中必有一个出现。由于事件A是“取3的倍数”，而在上述三个事件中只有一种可能使A发生。所以在B发生的条件下事件A的概率是1/3。,2.3.5 全概率公式与Bayes公式（1）,全概率公式 定理2.2 设事件A1,A2,An，满足： (1)两两互不相容，即当ij时，有AiAj=； (2)P(Ai)0 (1in) (3) 则对任何事件B有下式成立

16、：,2.3.5 全概率公式与Bayes公式（2）,2. Bayes公式 定理2.3 条件同定理2.2。则对任何事件B有下式成立：,2.4 模糊理论,1965年由L.A. Zadeh等人提出。 2.4.1 模糊性 随机性：事物本身含义明确，但条件不明而不可预知。 模糊性：事物本身是模糊的。例如：青年、老年；高低； 2.4.2 集合与特征函数 定义2.12 设A是论域U上的一个集合，对于任意uU，令 则称CA(u)为集合A的特征函数。特征函数CA(u)在u=u0处的取值CA(u0)称为u0对A的隶属度。 集合A与其特征函数可以认为是等价的。 A=u|CA(u)=1,2.4.3 模糊集与隶属函数（1

17、）,确定性概念可用普通集合表示。例如“奇数”在论域U=1,2,3,4,5上。那么如何表示模糊性概念？例如“大”，“小”。 模糊集的思路：把特征函数的取值范围从0,1推广到0,1上。 定义2.13 设U是论域，A是把任意uU映射为0,1上某个值的函数，即 A :U0,1或者uA(u) 则称A为定义在U上的一个隶属函数，由A(u)(uU)所构成的集合A称为U上的一个模糊集，A(u)称为对A的隶属度。,2.4.3 模糊集与隶属函数（2）,模糊集的例子。 例2.7 论域U=1,2,3,4,5，用模糊集表示“大”和“小”。 解：设A、B分别表示“大”与“小”的模糊集，A ，B分别为相应的隶属函数。 A=

18、0,0,0.1,0.6,1 B=1,0.5,0.01,0,0 其中：A(1)=0,A(2)=0 ,A(3)=0.1 ,A(4)=0.6 ,A(5)=1 B(1)=1,B(2)=0.5 ,B(3)=0.01 ,B(4)=0,B(5)=0,2.4.3 模糊集与隶属函数（3）,例2.8 论域U=高山，刘水，秦声，用模糊集A表示“学习好”这个概念。 解：先给出三人的平均成绩： 高山：98分，刘水：90分，秦声：86分 上述成绩除以100后，就分别得到了各自对“学习好”的隶属度： A(高山)=0.98,A(刘水)=0.90 ,A(秦声)=0.86 则模糊集A为： A=0.98, 0.90, 0.86,2

19、.4.4 模糊集的表示方法（1）,若论域离散且有限，则模糊集A可表示为： A=A(u1),A(u2),A(un) 也可写为： A=A(u1)/u1+A(u2)/u2+A(un)/un 或者： A=A(u1)/u1,A(u2)/u2,A(un)/un A=(A(u1),u1),(A(u2),u2),(A(un),un) 隶属度为0的元素可以不写。 例如： A=1/u1+0.7/u2+0/u3+0.4/u4 =1/u1+0.7/u2+0.4/u4,2.4.4 模糊集的表示方法（2）,若论域是连续的，则模糊集可用实函数表示。 例如： 以年龄为论域U=0,100， “年轻”和“年老”这两个概念可表示为

20、：,2.4.4 模糊集的表示方法（3）,无论论域U有限还是无限，离散还是连续，扎德用如下记号作为模糊集A的一般表示形式: U上的全体模糊集，记为： F(U)=A|A:U0,1,2.4.5 模糊集的运算（1）,模糊集上的运算主要有：包含、交、并、补等等。 1. 包含运算 定义2.14 设A，BF(U)，若对任意uU，都有 B(u)A(u) 成立，则称A包含B，记为 2. 交、并、补运算 定义2.15 设A，BF(U)，以下为扎德算子,2.4.5 模糊集的运算（2）,例2.9 设U=u1,u2,u3， A=0.3/u1+0.8/u2+0.6/u3 B=0.6/u1+0.4/u2+0.7/u3 则：

21、 AB=(0.30.6)/u1+(0.80.4)/u2+(0.60.7)/u3 =0.3/u1+0.4/u2+0.6/u3 AB=(0.30.6)/u1+(0.80.4)/u2+(0.60.7)/u3 =0.6/u1+0.8/u2+0.7/u3 A=(1-0.3)/u1+(1-0.8)/u2+(1-0.6)/u3 =0.7/u1+0.2/u2+0.4/u3,2.4.5 模糊集的运算（3）,例2.10 A表示“年老”的模糊集，B表示“年轻”的模糊集。 则：,2.4.5 模糊集的运算（4）,其它的模糊集运算： 有界和算子 和有界积算子 概率和算子 与实数积算子 爱因斯坦和算子 与爱因斯坦积算子,2

22、.4.6 模糊集的水平截集（1）,水平截集是把模糊集合转化成普通集合的一个重要概念。 定义2.16 设AF(U),0,1，则称普通集合 A=u|uU,A(u) 为A的一个水平截集， 称为阈值或置信水平。 水平截集有如下性质： (1)设A，B F(U)，则： (AB)=AB (AB)=AB (2)若1, 20,1，且12 ，则： 阈值越大，其水平截集A越小，当1时，A最小，称它为模糊集的核。,2.4.6 模糊集的水平截集（2）,定义2.17 设AF(U) ，则称 Ker A=u|uU, A(u)=1 Supp A=u|uU, A(u)0 分别为模糊集A的核及支集。当KerA时，称A为正规模糊集。

23、,2.4.6 模糊集的水平截集（3）,例2.11 设模糊集 A=0.3/u1+0.7/u2+1/u3+0.6/u4+0.5/u5 若分别为1,0.6,0.5,0.3，则相应的水平截集为： A1=u3 A0.6=u2,u3,u4 A0.5=u2,u3,u4,u5 A0.3=u1,u2,u3,u4,u5 A的核及支集分别是： KerA=u3 SuppA=u1,u2,u3,u4,u5,2.4.7 模糊度（1）,模糊度是模糊集的模糊程度的一种度量。 定义2.18 设AF(U)，d是定义在F(U)上的一个实函数，如果它满足以下条件： (1)对任意AF(U)，有d(A)0,1; (2)当且仅当A是一个普通

24、集合时，d(A)=0； (3)若A的隶属函数A(u)0.5，则d(A)=1; (4)若A,BF(U),且对任意uU,满足 B(u)A(u)0.5或者B(u)A(u)0.5 则有d(B)d(A) (5)对任意AF(U) ，有d(A)=d(A) 则称d为定义在F(U)上的一个模糊度，d(A)称为A的模糊度。,2.4.7 模糊度（2）,2. 模糊度的直观含义 是0,1上一个数； 普通集合的模糊度是0，表示所刻画的概念不模糊； 越靠近0.5就越模糊，当A(u)0.5时最模糊； 模糊集A与其补集A有相同的模糊度。,2.4.7 模糊度（3）,3. 计算模糊度的方法 海明(Haming)模糊度 其中，A0.

25、5(ui)是A的0.5截集的隶属函数。由于A0.5是一个普通集合，所以A0.5(ui)实际上是特征函数。 欧几里德(Euclid)模糊度,2.4.7 模糊度（4）,明可夫斯基(Minkowski)模糊度 香农模糊度 其中S(x)是定义在0,1上的香农函数，即,2.4.7 模糊度（5）,例2.12 设U=u1,u2,u3,u4 A=0.8/u1+0.9/u2+0.1/u3+0.6/u4 则,2.4.8 模糊数（1）,模糊的数量，例如：500人左右，大约0.6 定义2.19 如果实数域R上的模糊集A的隶属函数A(u)在R上连续且具有如下性质： (1)A是凸模糊集，即对任意0,1, A是闭区间； (

26、2)A是正规模糊集，即存在uR，使A(u)1。 则称A为一个模糊数。 直观上模糊数的隶属函数图形是单峰的，且在峰顶使隶属度达到1。,2.4.8 模糊数（2）,一个模糊数的例子。 “6左右”,2.4.8 模糊数（3）,2. 模糊数的运算 定义2.20 设是实数域R上的一种二元运算，A和B为任意的模糊数，则模糊数间的运算定义为 两个模糊数之间的运算，实际上是对应元素的隶属度先取极小，再取极大。,2.4.8 模糊数（4）,例2.13 设有 3左右=0.5/2+1/3+0.6/4 2左右=0.4/1+1/2+0.7/3,2.4.8 模糊数（5）,续上例 模糊数乘或者除的结果可能不是一个模糊数。,2.4

27、.9 模糊关系及其合成（1）,模糊关系 定义2.21 Ai是Ui(i=1,2,n)上的模糊集，则称 为A1,A2,An的笛卡儿乘积，它是U1U2Un上的一个模糊集。 定义2.22 在U1U2Un上一个n元模糊关系R是指以U1U2Un为论域的一个模糊集，记为,2.4.9 模糊关系及其合成（2）,例2.15 U=张三，李四，王五 V=篮球，排球，足球，乒乓球 UV上的一个模糊关系R,2.4.9 模糊关系及其合成（3）,一般地说，当U和V都是有限论域时，其模糊关系R可用一个模糊矩阵表示。 U=u1,u2,um V=v1,v2,vn 则UV上的模糊关系为,2.4.9 模糊关系及其合成（4）,例2.16 设U=V=u1,u2,u3,R是“信任关系”， 可有,2.4.9 模糊关系及其合