《谓词逻辑集合》PPT课件.ppt

第2章 谓词演算及其形式系统,在研究命题逻辑中，原子命题是命题演算中最基本的单位，但是不再对原子命题进行分解，会产生二大缺点： （1）不能研究命题的结构，成分和内部逻辑的特征； （2）也不可能表达二个原子命题所具有的共同特征，甚至在命题逻辑中无法推理一些简单又常见的结论。,谓词演算及其形式系统,例：苏格拉底论证是正确的，但不能用命题逻辑的推理规则推导出来。 P：所有的人总是要死的。 Q：苏格拉底是人。 R：所以苏格拉底是要死的。 命题演算无法反映上述推理，因为前提和结论都只能表示为原子命题，在命题演算系统中，无法由前提P,Q推出结论R，结论R也根本不是前提P,Q的逻辑结果。 所以我们必须对原子命题进行分解，研究它的内部结构，并用相应的手段去刻划它们，这正是谓词逻辑所要研究的问题。,2.1 个体 谓词 量词,2.1.1 个体 谓词演算中把一切讨论对象都称为个体，它们可以是客观世界中具体的客体，也可以是抽象的客体，例如数字，符号等。确定的个体常用a，b，c等小写字母表示，并被称为常元。不确定的个体常用字母x，y，z等表示，并被称为变元。 谓词演算中把讨论对象，即个体的全体称为个体域，常用字母D表示，并约定任何D都至少含有一个成员。当讨论对象遍及一切客体时，个体域特称为全总域，用字母U表示。 当给定个体域时，常元表示该域中的一个确定的成员，而变元则可以取该域中的任何一个成员为其值。,个体,2.1.2 谓词,我们把语句中表示个体性质或关系的语言成分（通常是谓语）称为谓词。 例：（1）“苏格拉底是人”中的“是人” （2）“苏格拉底是要死的”中的“是要死的” （3）“实数的平方是非负的”中的“是非负的” （4）“张三生于北京”中的“生于” （5）“3小于2”中的“小于” （6）“325”中的“” 其中： （1），（2），（3）表示个体性质；（4），（5）表示两个个体间的关系；（6）表示3个个体间的关系。,谓词,我们可把陈述句分解为二部分： 主语（名词，代词）和谓语（动词）。 谓词演算中用携有空位的大写字母表示谓词，例如： M（）表示“是人” B（ ， ）表示“生于” A（ ， ，）表示“” 上述表示法可读性差，因此常用变元来代替空位，例如：M(x),B(x,y),A(x,y,z)，它们被称为谓词命名式，简称谓词。 若谓词字母联系着一个个体，则称作一元谓词；若谓词字母联系着二个个体，则称作二元谓词；若谓词字母联系着n个个体，则称作n元谓词。,谓词填式：谓词字母后填以个体所得的式子。例如: R（x）表示“x是实数”（这里x表示个体） L（3，2）表示“3小于2” 注意：个体的次序必须是有规定的。 例：河南省北接河北省。 n L b 用L(x,y)表示x北接y； n：河南省；b：河北省 写成二元谓词为：L(n,b)，但不能写成L(b,n)。 一般的，谓词填式P（t1,tn）表示个体项t1,，tn所代表的个体满足n元谓词P（t1,tn）,注意：当空位处填入变元时，谓词命题式与谓词填式同形，但它们表示不同的意义。例如，R（x）作为命名式时，它只是R（）的另一写法，与x无关，改为R（y）意义照旧；但R（x）作为填式时，它表示“x所取值为实数”，改为R（y）后其意义变为“y所取值为实数”。 当谓词填式中所填个体都是常元时，它是一个命题，因而有确定的真值，例如 L（3，2）为假，A（3，2，5）为真。 从这个意义上，谓词是以个体域为定义域，以真值集为值域的映射。,2.1.3 命题函数与量词 定义 由一个谓词字母和一个非空的个体变元的集合所组成的表达式，称为简单命题函数。 个体在谓词表达式中可以是任意的名词。 例：C“总是要死的。” j：张三；t：老虎；e：桌子。 则C(j), C(t), C(e)均表达了命题。C：表示“总是要死的”；x：表示变元（个体变元），则C(x)表示“x总是要死的”，则称C(x)为命题函数。 讨论：（a）当简单命题函数仅有一个个体变元时，称为一元简单命题函数； （b）若用任何个体去取代个体变元之后，则 命题函数就变为命题。,命题函数,量词 （1）全称量词 “”为全称量词符号，读作“对于所有的”，“对任一个”，“对一切”。 “”表达式的读法 xP(x)： “对所有的x，x满足P(x)”； xP(x) ： “对所有x，x不满足P(x)”； xP(x) ： “并不是对所有的x，x都满足 P(x)”； xP(x) ：“并不是对所有的x，x都不满足 P(x)”。 例：“这里所有的都是苹果” 可写成：xA(x)或(x)A(x),量词 全称量词,例：将“对于所有的x和所有的y，如果x高于y，那么y不高于x”写成命题表达形式。 解： G(x,y)：x高于y x y(G(x,y) G(y,x) （2）存在量词 “”为存在量词符号，读作“存在一个”，“对于一些”，“对于某些”，“至少存在一个”。 “”表达式的读法： x A(x) ：“存在一个x,使x满足A(x)” ； xA(x) ：“存在一个x, 使x不满足A(x)” ； x A(x) ：“不存在一个x, 使x满足A(x)” ； xA(x) ：“不存在一个x, 使x不满足A(x)” 。,存在量词,例：（a）存在一个人； （b）某个人很聪明； （c）某些实数是有理数 将（a）,（b）,（c）写成命题。 解：规定M(x)：x是人； C(x)：x很聪明； R1(x)：x是实数 R2(x)：x是有理数。 则（a） x M(x) ； （b） x (M(x) C(x)； （c） x (R1(x) R2(x) 。 （3）量化命题的真值：取决于给定的个体域 给定个体域：a1，an，则有： xP(x)P(a1) P(an) xQ(x)Q(a1) Q(an),2.1.4 谓词公式和语句的形式化 原子谓词公式：不出现命题联结词和量词的谓词命名式称为原子谓词公式，并用P(x1xn)来表示。 （P称为n元谓词， x1xn称为个体变元），当n=0时称为零元谓词公式。 定义（谓词公式的归纳法定义） 原子谓词公式是谓词公式； 若A是谓词公式，则A也是谓词公式； 若A, B都是谓词公式，则(AB),(AB),(AB),(AB)都是谓词公式； 若A是谓词公式，x是任何变元，则xA, xA也都是谓词公式；,谓词公式,只有有限次利用-所产生的符号串才是谓词公式（谓词公式又称合式公式，简称公式）。 从以上谓词公式的生成法则可见，命题公式是谓词公式的特例。事实上，命题逻辑是谓词逻辑系统的一个子系统，命题逻辑所使用的方法和所获得的结论，在谓词逻辑中是作为不证自明的正确形式而直接使用的。 谓词公式中括号的省略方法与命题公式相同。 例：任何整数或是正的，或是负的。 解：设I(x): x是整数； R1(x)：x是正数；R2(x)：x是负数。 此句可写成：x(I(x)(R1(x) R2(x) ),例：设个体域是人类，将下列语句形式化为谓词公式。 1.有人勇敢，但不是所有的人都勇敢。 设：B(x)：x勇敢 则形式化为： x B(x) x B(x) 2.我为人人，人人为我。 设i表示“我”；S（x, y）：x为y服务 则形式化为： x S（i, x） x S（x，i) 辖域：紧接在量词后面括号内的谓词公式。 例：xP(x)Q（x），量词x的辖域为P(x) x(P(x)Q(x)，量词x的辖域为P(x)Q(x) 若量词后括号内为原子谓词公式，则括号可以省去。 例如 x（P(x)）可写成 xP(x),辖域,约束变元：在量词x或x的辖域内，且与量词下标相同的变元。 自由变元：当且仅当不受量词的约束。 例：xP(x)Q（x） P(x)中的x是约束变元，Q（x）中的x是自由变元 x（P(x，y)Q（x，y） R(x，z)， P(x，y)Q（x，y）中的x是约束变元， R(x，z)中的x是自由变元，y,z都是自由变元 约束变元的改名规则 任何谓词公式，对约束变元可以改名。 我们认为xP(x,y)和zP(z,y)是一等价的谓词公式，但是需注意，不能用同一变元去表示同一谓词公式中的二个变元。例如： yP(y,y)是不正确的。,约束变元 自由变元 改名规则,改名规则： （1）在改名中要把公式中所有相同的约束变元全部同时改掉； （2）改名时所用的变元符号在量词辖域内未出现的。 例： xP(x) yR(x,y) 可改写成xP(x) zR(x,z) ，但不能改成 xP(x) xR(x,x) ， xR(x,x)中前面的x原为自由变元，现在变为约束变元了。 语句形式化应注意： （1）准确从语句中提取谓词，表示性质的谓语用一元谓词，表示关系的谓语用二元或多元数谓词表示。 （2）准确使用量词的辖域，当辖域中多于一个谓语时必须注意括号的使用。多个量词使用时其次序应与原语句意义一致。,改名规则,2.2 谓词演算永真式 2.2.1 谓词公式的真值 在谓词公式中，包含有命题变元和个体变元，当个体变元由确定的个体来取代，命题变元用确定的命题所取代时，就称对谓词公式赋值。一个谓词公式经过赋值后，就成为有确定真值的命题。 例:给下列谓词公式一组赋值，以得到一个命题公式 (1) x（E(x) D(x，6) 解：令E(x)为x是偶数 D（x，6）为x大于6；x8。 则谓词公式代表命题：8是偶数并且8大于6。,谓词公式的真值,(2) x ( B(x)M（x）) 解：令B(x)为x早餐吃面包 M(x)为x早餐吃馒头：x为李明 则谓词公式代表命题：李明早餐吃面包或吃馒头。 2.2.2 谓词演算永真式 定义 给定谓词公式A，若对于A的所有赋值，公式对应的真值总为T，则称该谓词公式为永真式。 定义 给定谓词公式A，若对于A的所有赋值，公式对应的真值总为F，则称该谓词公式为永假式。 定义 给定谓词公式A，若对于A至少存在一组赋值，公式对应的真值总为T，则称该谓词公式为可满足式。,谓词演算永真式,关于永真式的几个基本原理： 代入规则：对公式中的自由变元的更改叫做代入。 (1)对公式中出现该自由变元的每一处进行代入。 (2)用以代入的变元与原公式中所有变元的名称不能相同。 代入原理：若A是永真式，则对A中变元可代入的代入实例都是永真式。 替换原理：设A,D为谓词公式，C为A的子公式，且CD。若B为将A中子公式C的某些出现（未必全部）替换为D后所得到的公式，则CD。 改名原理：若公式A中无自由变元y，则 xA(x)yA(y) xA(x)yA(y),永真式的基本原理,注意：定理中对A的限制是不可忽略的。例如 x(xy)与改名后的y(yy)显然不等价。 谓词公式的对偶式 定义 在一个谓词公式A中（其中不出现,词）把公式A中 , , F, T, , , 变为, , T, F, , 后得到公式A* ，则称A*是A的对偶式。 定理 若谓词公式A B，则A* B* ；若谓词公式A B ，则B* A* （这里A,B有同样的个体域）。例如： xA(x) xB(x) x(A(x)B(x) xA(x) xB(x) x(A(x) B(x),对偶式 定理,2.2.3 谓词演算等价式与蕴含式 定义 设A和B是两个谓词公式， E为它们共同个体域，如果对A和B的任何一组赋值，两者的真值都相同，则称A和B遍及E是等价的。记作。 定义 设A和B是两个谓词公式， E为它们共同个体域，当且仅当是一个永真式时，称永真蕴涵。记作。 1.不含量词的谓词公式的永真式 只要用原子谓词公式去替代命题公式的永真式中的原子命题变元，则在第一章中永真蕴含式和等价公式均可变成谓词演算中的永真式：,谓词演算等价式与蕴含式,命题逻辑 谓词逻辑 (x)(x) (x)(x)(x) . . . . (x)(x) (x) (x) (x)(x)(x) (x)(x) (x) . . . . . .,2.含有量词的等价式和永真蕴含式 （1）量词转换律： xP(x) xP(x) xP(x) xP(x) 结论：对于非量化命题的否定只需将动词否定，而对于量化命题的否定不但需对动词进行否定，同时对量词也要进行否定。其方法是： x的否定变为x ， x的否定变为x 。 （2）量词分配律 x(A(x)B(x) xA(x) xB(x) x(A(x)B(x) xA(x) xB(x),量词转换率 量词分配率,x(A(x)B(x) xA(x) xB(x) xA(x)xB(x) x(A(x) B(x) x(A(x)B(x) xA(x) xB(x) xA(x)xB(x) x(A(x) B(x) （3）量词辖域的扩张及其收缩律 x(AB(x) A xB(x) x(AB(x) A xB(x) x(AB(x) A xB(x) x(AB(x) A xB(x) xA(x)B x (A(x)B) xA(x)B x (A(x)B) AxB(x) x (AB(x) AxB(x) x (AB(x),量词辖域的扩张与收缩率,结论：在某个量词的辖域中若存在着不含有被此量词所约束的个体变元的子公式，则可将这个子公式从量词的辖域中提出来。 xA A xA A (A为不含有变元x的任何谓词公式） 2.3 谓词公式的前束范式 定义 一个公式，如果量词均非否定地在公式的开头，它们的辖域一直延伸到整个公式的末尾，则称此公式叫前束范式。 形如 ，其中 ,Qn为量词或， B称为母式，B中无量词。 例： xyz( Q(x,y) R(z),前束范式,任何一个谓词公式均可转化为与其等价的前束范式，转化步骤如下： （1）将公式中的联结词和化为， （2）利用量词转换把深入到原子谓词公式前 （3）利用改名规则使得所有约束变元，自由变元的名字均不相同 （4）扩大量词辖域至整个公式。 例：把xP(x) xQ(x) 变成前束范式。 xP(x) xQ(x) xP(x)xQ(x) xP(x) xQ(x) x(P(x) Q(x),2.4 谓词演算的推理理论 常用推理规则： （1）全称指定规则（US规则）。 如果对个体域中所有个体x,A(x)成立，则对个体域中某个任意个体c，A(c)成立。该规则表示成： xA(x) A(c) (x,c个体域) （2）全称推广规则（UG规则） 如果能够证明对个体域中每一个个体c，命题A(c) 都成立，则可得到结论xA(x)成立。该规则表示成： A(x) xA(x),谓词演算的推理理论,（3）存在指定规则（ES规则） 如果对于个体域中某些个体A(x)成立，则必有某个特定的个体c，使A(c)成立。该规则表示成： xA(x) A(c) （4）存在推广规则（EG规则） 如果对个体域中某个特定个体c，有A(c) 成立，则在个体域中，必存在x，使A(x)成立。该规则表示成： A(c) xA(x),推论规则： 命题逻辑中的P规则,T规则和间接证明法，都可以引用到谓词逻辑的推论规则中来，不过要注意对量词做适当处理，其方法是：用US,ES在推导中去掉量词，用UG,EG使结论量化。 规则使用说明： （1）在使用ES,US时一定要是前束范式 （2）推导中连续使用US规则可用相同变元 xP(x)P(y), xQ(x)Q(y), （3）推导中连续使用ES规则时，使用一次更改一个变元。 （4）推导中既用ES，又用US时， 则必须先用ES，后用US方可取相同变元，反之不行。 xP(x)P(y) xQ(x)Q(y),推论规则使用说明,xA(x)A(c) (US) A(x)xA(x) (UG) xA(x)A(c) (ES) A(c)xA(x) (EG) 例：证明苏格拉底论证 x(M(x)D(x) M(s) D(s) 证明： 前提：x(M(x)D(x) ， M(s) 结论：D(s) M(s) P x(M(x)D(x) P M(s)D(s) US D(s) 假言推理,小结,学习第一章要注意以下几点： （1）清楚命题与陈述句的关系。 （2）清楚由5种基本联结词联结的复合命题的逻辑关系及其真值。特别是要弄清蕴含式“PQ”的逻辑关系及其真值。 （3）记住常用的蕴含式和等价式，这是学好命题逻辑的关键。 （4）会准确地求出给定公式的主析取范式和主合取范式。 （5）会用多种方法判断公式的类型及判断两个公式是否等价。 （6）掌握推理和判断推理是否有效的方法。,小结,学习第二章要注意以下几点： (1)同一个命题在不同个体域内可能有不同的符号化形式，同时也可能有不同的真值，因而在将一个命题符号化之前，必须弄清个体域。 (2)在将命题符号化时，要特别注意量词与联结词的搭配。经常的情况是全称量词与蕴含词搭配，存在量词与合取词搭配。 (3)记住主要的等价式。会用约束变元和自由变元换名规则进行等价演算，求出给定公式的前束范式。 (4)在谓词演算的推理证明中，要特别注意US，UG，ES，EG规则成立的条件。,第二部分 集合论,集合论是计算机科学领域不可缺少的数学工具,它是研究集合的一般性质的数学分支。 在现代数学中，每个对象（如数、函数等）本质上都是集合，都可以用某种集合来定义。数学的各个分支，本质上都是在研究这种或那种对象的集合的性质。集合论已成为全部现代数学的理论基础。 集合论的特点是研究对象的广泛性。它总结出由各种对象构成的集合的共同性质，并用统一的方法来处理。因此，集合论被广泛地应用于各种科学和技术领域。,第二部分 集合论,由于集合论的语言适合于描述和研究离散对象及其关系，因此，集合论在计算机程序设计语言,数据结构,形式语言,开关理论,人工智能,数据库等领域都有着重要的应用。对于计算机科学工作者来说,集合论是不可缺少的理论基础知识。 本部分介绍集合论的基础知识,如集合的概念,运算和性质,序偶,关系,函数,基数等内容.,第3章 集合,3.1 集合的基本概念与表示 3.1.1 集合的基本概念 集合是数学中最基本的概念，它是一个不定义概念。 一般来说，把具有确定的共同性质的一些事物，汇集成一个整体，就形成一个集合，即集合的元素具有无序性。 讨论： 1.元素（成员）：一个集合中的每个事物 2.符号：通常用大写英文字母,如A,B,C,表示集合，用小写英文字母a,b,c,表示元素。,集合的基本概念,3.元素与集合间的关系： 若a是集合A中的元素， 则称“a属于A”，记作：aA ；若a不是集合A中的元素，则称“a不属于A”，并记作：aA 。 4.有限集合：集合的元素个数是有限个的。 无限集合：集合的元素个数是无限个的。 5.集合基数：有限集A中元素的个数称为A的基， 记作|A|。 例如：A1，3，5，7，9，则|A|5 6.性质： a.集合具有无序性 由于集合是由一些事物组成的整体，因此不计较这些事物的排列次序。例如,由1，2，3组成的集合与由2，3，1组成的集合是同一个集合。,b.集合具有互异性 集合中的元素是互不相同的，如果同一个元素在集合中多次出现，则认为是一个元素。例如，由1，1，2，3，3组成的集合与由1，2，3组成的集合是同一个集合。 3.1.2 集合的表示 表示一个集合，一般常用下列三种方法： 1.列举法 又称穷举法，是把集合的所有元素一一列举出来放在大括号内，元素之间用逗号分开。例如： A=1,3,5,7,9,这表示集合A由5个元素组成,它们分别是1,3,5,7,9。显然3A,10A。,集合的表示 列举法,当一个集合的元素较多，或者它有无穷多个元素时，可以只写出几个元素，其他元素用省略号表示并且把它们放在一个大括号内。要注意写出的元素必须让人明白省略了哪些元素。 如：小于100的自然数组成的集合可以表示为 0，1, 2， ，99 2.描述法 就是指出一个集合中所有元素共同具有的性质，而不属于这个集合的元素都不具有该性质。它的一般表示方法是： S=x|x具有性质P,描述法,例:A=x|x是24的约束且x0 3.文氏图法 用一个矩形表示全集，在矩形内画一些圆，用圆的内部表示集合。 以下是一些常用的集合，用固定的符号表示： N 自然数集合 0,1,2 Z 整数集合 -1,0,1,2 Z 正整数集合 1,2，3， Q 有理数集合 R 实数集合 C 复数集合,文氏图法,三个特殊集合：全集合、空集、集合族 定义 如果一个集合包含了所要讨论的每一个集合，则称该集合为全集合，简称全集，用U表示。 集合中的元素可以是多种多样的，一个集合也可作为另一集合的元素。例：S=a,1,2,p,q 定义 不含有任何元素的集合称为空集，用表示。 例如，A=x|x是大于2且小于3的自然数 注意： 前者是空集，是没有元素的集合；后者是以作为元素的集合。 定义 集合中的元素均为集合，称这样的集合为集合族。 例如， A=a，b，c、d,三个特殊集合,3.2 集合之间的关系 定义 设A、B是任意二个集合，如果集合A的每一个元素都是B的一个元素，则称A是B的子集，或者说A包含于B，或者说B包含A.记作 AB 或 BA 如果A不是B的子集，即在A中至少有一个元素不属于B时，称B不包含A，记作 A B 例：A1=1,2,3 A2=0 A3=1,2,3,4 B=1,2,3,0 则A1、A2均为B的子集合，并记为A1B，A2B。 但A3不是B的子集，因为元素4A3,但4B。,集合之间的关系 包含,讨论： a.对于任何一个集合A，它的任何一个元素都属于它本身，因此有AA,即任何一个集合是它本身的子集。 b.规定空集是任何集合的子集。即对于任何集合A,有A。 定义 如果两个集合A和B的元素完全相同，则称这两 个集合相等，记作AB。 例如， 设A=1,2,3,4, B=3,1,2,4,显然有A=B 设P=1,2,4，Q=1,2,4，则PQ 定理 任意二个集合A、B相等的充分必要条件是 AB且BA。,相等,定义 设A、B是任意二个集合，若AB且AB，即在B中至少有一个元素不属于A,则称A是B的真子集。记作AB（A真包含于B） 若A不真包含于B，则也可表示成AB 注意：区分“”和“”的关系： “”：是指集合和该集合中元素之间的关系。 例：S=a,b,c 则aS，bS，cS “”：是指二个集合之间的关系。 例：S1=a, b S2=a,b,1,2 则S1S2 定理 设U是全集，A是一个集合，则一定有AU。 定理 设A、B、C是任意集合，如果AB和BC，则AC 。若AB和BC，则AC 。,真包含,定理 是唯一的。 定义 设A是有限集，由A的所有子集作为元素而构成的集合称为A的幂集。 记作(A)，即(A)=x|xA 在A的所有子集中，A和这两个子集又叫平凡子集。 一定有A(A)，(A)， 即对非空集合，在幂集中至少有两个子集和A。 例：若A=，则(A)= 若B=1，2，则(B)=，1，2，1，2 推广：含有n个元素的集合A的所有子集的个数是 2n,幂集,3.3 集合的运算,集合上的运算是以给定的一个或多个集合（称作运算对象），按某种规则去确定一个新的集合（称作运算结果）的过程。 3.1.1 集合的并运算 定义 A、B是任意二个集合，A和B的并集记作AB，是由A和B的所有元素构成的集合。 即：AB=xxA或xB。 例：A=a, b, c B=1,2,3 则AB=a,b,c,1,2,3 平面上的矩形表示全集U，阴影 部分就表示AB,U,集合的运算 并运算,并运算的性质： (1) 幂等律 AA=A (2) 同一律 A=A (3) 零律 AU=U (4) 结合律 （AB）C=A（BC） (5) 交换律 AB=BA 3.3.2 集合的交运算 定义 任何二个集合A和B的交集AB，是由所有既属于A又属于B的元素构成的集合。 即：AB=x | xA 且 xB 例：A=a，b B=a，c AB=a 如果A和B没有公共元素， 则称A,B不相交，即AB=,交运算,交运算的性质： (1)