《201902离散数学课件资料.ppt》由会员分享，可在线阅读，更多相关《201902离散数学课件资料.ppt（52页珍藏版）》请在三一文库上搜索。
1、在命题逻辑中，命题是命题演算的基本单位，不关心每个简单命题反映的具体内容，没有进一步研究命题的内部结构，因而在实际应用中存在很多缺陷。,著名的苏格拉底三段论:,“所有的人都是要死的,苏格拉底是人,所以是苏格拉底是要死的。” p: 所有的人是要死的; q: 苏格拉底是人; r: 苏格拉底是要死的.,由上述文字构造的命题逻辑推理结构为: (p q) r 可知: (p q) r不是一个重言式,因此,按命题逻辑的方法,无法证明上述问题.,为了在命题演算中，反映命题的内在联系，常常要将简单命题分解成个体词、谓词、量词等，并对它们的形式结构及逻辑关系加以研究，总结出正确的推理形式和规则，这就是本章一阶逻辑
2、要研究的内容。,2019/5/13,离散数学,4,第二章 一阶逻辑 2.1 一阶逻辑基本概念 2.2 一阶逻辑合式公式及解释 2.3 一阶逻辑等值式及前束范式,个体词：可以独立存在的客体，既可以是抽象的概念，也可以是具体的事物。,谓 词：用来刻划个体词的性质或个体词之间关系的。,如：李明、自然数、,简单命题总可以被分解成个体词和谓词两部分。,2.1一阶逻辑基本概念,个体常项：指具体或特定的个体的词，用小写字母a, b, c,，表示。,个体变项：表示抽象的或泛指的个体的词，用x, y, z,，表示。,个体域：个体变项的取值范围。,全总个体域：当无特殊声明时,表示宇宙间的一切 事物组成的个体域，又
3、称全总域。,谓词常项：表示具体性质或关系的谓词，用大写英文字母F，G，表示。,谓词变项：表示抽象的或泛指的性质或关系的谓词，也用大写字母F，G，表示。,一般根据上、下文区分常项与变项。,个体变项x具有性质F：记作F(x),个体变项x、y具有关系L：记作L(x,y),(性质),(2) 小李比小赵高2厘米,(关系),设F(x) : x 是无理数, ，,设H(x, y) : x 比 y 高2厘米,a : 小李， b : 小赵,则(2)可表示为： H(a, b) (不是H(b, a),将下列两命题符号化：,则(1)可表示为F(a),解：,解：,元数：在谓词中所包含的个体词(变项)数。,n元谓词：含n(
4、n1)个个体词的谓词，可用D(x1, x2,，xn)表示。,一元谓词表性质；,二元或更多元谓词表示关系。,0元谓词：不含个体变项的谓词 。,如：a为2，b为3，L(a，b)是0元谓词。,例1.将下列命题用0元谓词符号化,(1) 2是素数且是偶数 ；,(2) 如果2大于3，则2大于4 ；,(3) 如果张明比李民高，李民比赵亮高，则张明比赵亮高 ；,（1）解：设F(x) ： x是素数，G(x)：x是偶数， a：2，则,（2）解：引入二元谓词：L(x, y)：x比y大,a:2，b:3，c:4，,(2) 符号化为L(a,b) L(a, c),（3）解：引入二元谓词：H(x, y)：x比y高,a:张,b
5、:李,c:赵,(3) 符号化为(H(a,b)H(b,c)H(a, c),(1) 所有的人都是要死的;,(2) 有些人活百岁以上;,考虑以下形式命题的符号化:,量 词,表示数量的词，分全称量词与存在量词。,：一切、所有的、任意的；,：存在着、有一个、至少有一个；,x：个体域中所有个体；,x：个体域中存在某个个体；,xF(x)：个体域中所有个体具有性质F；,xF(x)：个体域中存在着某个个体具有性质F。,将命题 “所有的人都是要死的”符号化 (个体域为人类集合）,符号化为：xF(x) 其中F(x)表示：x是要死的。,将命题 “有的人活百岁以上”符号化 (个体域为人类集合）,符号化为：xF(x) 其
6、中F(x)表示：x活百岁以上。,特性谓词：在全总个体域的情况下，为了指定某个个体变项的范围，引入特性谓词。,将命题(公式)“所有的人都是要死的”符号化,M(x)：x是人 (特性谓词),F(x)：x是要死的,命题(公式)符号化为： x(M(x)F(x),分析一下： 它与xF(x)有什么区别？,解：,有了个体词、谓词、量词等概念，我们就可以更细致地刻划命题公式。,将命题(公式)“有些人活百岁以上”符号化,M(x)：x是人(特性谓词),F(x)：x活百岁以上,命题(公式)符号化为： x(M(x) F(x),分析一下： 它与xF(x)有什么区别？,解：,使用量词时, 应该注意以下几点:,1 .在不同的
7、个体域中，命题符号化的形式可能不一样;,2. 如没有事先给出个体域,都应以全总个体域为个体域。,3. 在引入特性谓词后，引入全称量词与存在量词符号化 的形式是不同的;,4.当个体域为有限集时，如D=a1,a2,a3,an,对于任意的谓词A(x)，都有 (1) xA(x) A(a1) A(a2) . A(an) (2) xA(x)A(a1)A(a2)A(an),5.多个量词同时出现时，不能随意颠倒顺序;,x y H(x，y) , 其中H(x，y) : x+y=5 量词颠倒顺序成立吗?,例: 对于任意的x, 存在y,使得x+y=5, 取个体域为实数集合,该如何符号化?,例2.在谓词逻辑中将下列命题
8、符号化,(1) 对所有的x，均有x21=(x+1)(x1) (个体域为自然数集),(2) 存在x,使得x+5=2 (个体域为自然数集),(4) 存在着偶素数,(5) 没有不犯错误的人,(3) 凡偶数均能被2整除,(6) 在北京工作的人未必都是北京人,(7) 一切人都不一样高,(8) 每个自然数都有后继数,(9) 有的自然数无先驱数,(10) 有的有理数是整数 (个体域为实数集),(11) 每个人都有一些缺点。,符号化方法,1、 找到所有的个体词; 2、 是否要引入特性谓词; 3、 描述个体词性质：性质谓词(一元); 描述个体词关系：关系谓词(二元); 4、 按原命题的实际意义进行刻划。,设F(
9、x) ：x满足x21=(x+1)(x 1),(1)符号化：xF(x),解：,(1) 对所有的x，均有x2 1=(x+1)(x1) (个体域为自然数集),(2) 存在 x,使得x +5=2 (个体域为自然数集),解：,设G(x) ：x满足x +5=2,(2)符号化：xG(x),解：要引入特性谓词： F(x) ： x是偶数,G(x) ： x能被2整除,解：F(x) ： x是偶数 G(x) ： x是素数,符号化： x(F(x)G(x),符号化： x(F(x)G(x),(4) 存在着偶素数,(3) 凡偶数均能被2整除,解：特性谓词M(x)：x是人,解：F(x) ： x是在北京工作的人，G(x) ：x是
10、北京人,F(x)：x犯错误,符号化： x(M(x) F(x),或x(M(x) F(x),符号化：x(F(x) G(x),(5) 没有不犯错误的人,(6) 在北京工作的人未必都是北京人,或： x(F(x) G(x),解：M(x) ： x是人, L(x，y) ： x与y一样高,H(x，y)：x与y是同一个人,符号化：xy(M(x) M(y) H(x，y) L(x,y),(7) 一切人都不一样高,(8) 每个自然数都有后继数,解：F(x)：x自然数 H(x，y)：y是x的后继数,符号化：x(F(x) y (F(y) H(x，y),或：x y(M(x) M(y) H(x，y) L(x,y),或： x(
11、F(x) y (F(y) H(x，y),解：F(x)：x是自然数 ，H(x，y)：y是x的先驱数,符号化：x(F(x) y(F(y) H(x，y),解： F(x)：x是有理数，G(x)：x是整数,符号化：x(F(x) G(x),(9) 有的自然数无先驱数,(10) 有的有理数是整数 (个体域为实数集),或：x(F(x)y(F(y) H(x，y),解：F(x,y)：x都有y，M(x)：x是人，G(y)：y是缺点,或： (x)(y)(M(x)(G(y)F(x,y),符号化： (x) (M(x)(y) (G(y)F(x,y),(11) 每个人都有一些缺点。,2.2 一阶逻辑合式公式及解释,谓词演算中
12、的合式公式：,原子公式：不出现命题联结词和量词的命题 函数P(x1, x2, xn) ， 其中x1，x2，xn为个体变项或常项。,(1) 原子谓词公式是合式公式；,(2) 若A是合式公式，则A也是；,一、一阶逻辑合式(谓词)公式的概念,(3)若A和B是合式公式，则(AB),(AB)，(AB)和(A B)也是 ；,(4)如果A是合式公式，x是A中出现的个体变项，则 (x)A和(x)A是合式公式 ；,(5)只有有限次地应用规则(1)、(2)、(3)、(4)所得到的公式才是合式公式。,谓词合式公式即按规则(1)、(2)、(3)、(4)、(5)由原子公式、联结词、量词及括号组成的字符串，但最外层括号可
13、以省略。,指导变元及作用域,在谓词公式中，形如(x)P(x)或(x)P(x)的部分，叫做公式的约束部分。,量词，后面的x叫做量词的作用变元，或指导变元，P(x)叫做量词的作用域。,在作用域中，x的一切出现为约束出现，非约束出现的其它变元叫自由出现变元。,在谓词公式中，我们还用到以下概念。,二、谓词公式的改写,解：(y)R(x, y)中，指导变元是y， 的作用域为R(x, y)，其中y是约束出现，x是自由出现的。,(1) (x)(P(x)(y)R (x,y) ；,在整个合式公式中，x是作用变元(指导变元), 的作用域(P(x)(y)R(x, y)，x, y 都是约束出现的，x约束出现2次，y约束
14、出现1次。,例3. 指出下列合式公式中的指导变元，量词的作用域及变元约束的情况。,(2) (x) (y) (P(x, y) Q(y, z) (x) R(x, y),在(x)R(x, y)中，x是指导变元，的作用域为R(x, y)，其中x约束出现1次，y自由出现1次。在整个合式公式中，x约束出现2次，y约束出现2次，自由出现1次，z自由出现1次。,解：(x)(y)(P(x, y)Q(y, z)，x,y是作用变元，两个量词的作用域都是(P(x,y)Q(y,z)，其中x, y均为约束出现，x约束出现1次，y约束出现2次，z为自由出现1次。,解：(x)Q(x, z)中x是作用变元，的辖域为Q(x，z)
15、，其中 x 约束出现，z自由出现；,(3) (x)(P(x) (x)Q(x, z)(y)R(x, y)Q(x, y) ；,(y)R(x, y)中，y是作用变元，的辖域为R(x, y)，其中y约束出现，x自由出现；,在(x)(P(x)(x) Q(x,z)(y)R(x, y) 中，作用变元为x，的作用域为(P(x)(x)Q(x, z) (y)R(x, y), 但Q(x, z)中的x不是的作用变元，x, y均为约束出现，z自由出现；,Q(x, y)中，x, y为自由变元。,在整个公式中，x约束出现3次，自由出现1次，y约束出现1次，自由出现1次，z自由出现1次。,1. 换名规则：,2. 代替规则,将
16、量词作用域中出现的某个约束出现的个体变项及对应的指导变项改成另一个作用域中没有出现过的个体变项符号，公式的其余部分不变。,考虑到谓词公式中，有的个体变项既可以约束出现，又可以自由出现，为避免这种双重性可能引起的混淆，我们要将谓词公式进行改写，改写规则如下：,对某自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替，且处处代替。,(1) (x)(P(x)(y)R (x,y) ；,(2) (x)(y)(P(x,y)Q(y,z)(x)P(x,y) ；,(3) (x)(P(x)(x)Q(x,z)(y)R(x,y)Q(x,y) ；,换名规则与代替规则可避免有的个体变项既可以约束出现，又可以
17、自由出现。,例4.试对下列公式换名或代替。,第一步换名:(x)(y)(P(x,y)Q(y,z)(u)R(u,y) ；,第二步代替:(x)(y)(P(x,y)Q(y,z)(u)R(u, v) ；,第一步换名:(x)(P(x)(u)Q(u,z)(y)R(x,y)Q(x,y),第二步代替:(x)(P(x)(u)Q(u,z)(y)R(x,y)Q(s, t),(2) (x)(y)(P(x,y)Q(y,z)(x)R(x,y) ；,(3) (x)(P(x)(x)Q(x,z)(y)R(x,y)Q(x,y) ；,解：,(1) (x)(P(x)(y)R (x,y) ；不用改写,例5.求下列谓词公式的真值：,(x)
18、(P(x)Q(x)，其中P(x)：x = 1，Q(x)：x = 2，且个体域 E = 1，2；,当个体域是有限集时，如D =a1,a2,an,(x)A(x)A(a1)A(a2)A(an),则：(x)A(x)A(a1)A(a2)A(an),从而谓词公式的真值等价于命题公式的真值。,解题思想,解：,(x)(P(x)Q(x)(P(1)Q(1)(P(2)Q(2),(10)(01), 0,谓词合式公式的解释 (或指派),一个一阶逻辑合式公式中往往含有个体变项、谓词变项等，一组使合式公式成为具有确定真值的常项（个体常项、谓词常项等）就构成了一个公式的解释。,三、谓词公式的解释,例6：给定解释I如下：,DI
19、=2，3；DI中特定的元素a=2; 函数f(x)为f(2)=3，f(3)=2； 谓词F(x)为F(2)=0，F(3)=1; G(x,y)为G(i，j)=1 ，i, j=2,3; L(x,y)为L(2,2)= L(3,3)=1; L(2,3)= L(3,2)=0. 确定下列谓词公式的真值。,（1）x(F(x) G (x,a) (F(2) G (2,2) (F(3) G (3,2) (0 1) (1 1) 0,（2）x(F(f(x) G (x, f(x) (F(f(2) G (2, f(2) (F(f(3) G (3, f(3) (F(3)G (2,3)(F(2)G(3, 2) (11) (01)
20、 1,（3）xy L(x,y) x(L(x,2)L(x,3) (L(2,2)L(2,3) (L(3,2)L(3,3) (10) (01) 1,永真式(逻辑有效式）：任一组解释皆使公式真值为1,永假式： (?),可满足式： (?),没有一个可行的算法来判断一阶逻辑公式的类型，只能对某些特殊的公式进行判断。, x(F (x) F (x)；,四、谓词公式的类型,2.3 一阶逻辑等值式及前束范式,一、谓词演算中常见等值式：,(I) 命题公式的推广,24个常用的命题演算等值式及其代换可推广到谓词演算中使用,如,2. (x)P(x)(y)R(x,y) ( (x)P(x) (y)R(x, y),3. (x)
21、H(x,y) (x)H(x,y)F,1. (x)(P(x)Q(x)(x)( P(x)Q(x),() 量词否定等值式 (量词转换律), (x)P(x) (x) P(x), (x)P(x) (x) P(x),实例：“不是所有人今天都来上课” “存在一些人今天没来上课” “没有一个人今天来上课” “所有的人今天都没来上课” 。,一、谓词演算中常见等值式：,() 量词作用域的扩张与收缩等值式,xA(x)Bx(A(x)B),xA(x)Bx(A(x)B),* xA(x)Bx(A(x)B),BxA(x) x(BA(x),xA(x)Bx(A(x)B),xA(x)Bx(A(x)B),* xA(x)Bx(A(x)
22、B),BxA(x) x(BA(x),注意记住(*)，且各等价式中的B可含其他非指导变元。, xA(x) B, xA(x) B, x(A(x) B, x(A(x) B), x(A(x) B),() 量词分配等价式,(x)(A(x)B(x)(x)A(x) (x)B(x)(对的分配),(x)(A(x)B(x)(x)A(x)(x)B(x) (对的分配),注意： 对 ，对 不存在分配等价式。,一、谓词演算中常见等值式：,() 多个量词的使用,(x)(y)A(x,y)(y)(x)A(x,y),(x)(y)A(x,y) (y)(x)A(x,y),注意： 其他情况下量词换序后一般不等价。,一、谓词演算中常见等
23、值式：,前束范式：一个合式谓词公式，它的所有量词均 非否定地出现在公式的最前面，且它们的作用域一直延伸到公式的末尾。,如： (x)(y)(z)(P(x)F(y,z)Q(y,z),二、常见等值式的应用(前束范式),借助于常见等价式，我们仿照命题公式可以化成标准形式，也想把谓词公式化成标准形式。谓词逻辑中，任何谓词公式的前束范式都存在，但一般不唯一。,例7. 将合式公式(x)P(x)(y)R(y)(x)F(x)化为前束范式：,任一合式公式表示成前束范式可按如下步骤进行：,(1) 消去公式中出现的多余量词；,解题思想,二、常见等值式的应用(前束范式),(2) 利用双重否定定律、德 摩根律及量词转换律
24、将公式中的否定字符深入到谓词字母前(否定符紧贴)；,(3) 利用换名和代换规则使所有约束变元均不相同,并且使自由变元也与约束变元不同(更名)；,(4) 利用量词作用域的扩张和收缩律，扩大量词的作用域至整个公式(扩域)。,二、常见等值式的应用(前束范式),解:,(xP(x)yR(y)xF(x), (xP(x)yR(y) zF(z),(1) 更换变元符号, xyz(P(x) R(y) F(z),(2) 扩大作用域,二、常见等值式的应用(前束范式),例8. 求下列合式公式的前束范式,(1) (x)P(x) (x)Q(x),解： (x)P(x) (x)Q(x), (x)P(x) (x)Q(x), (x
25、)(P(x) Q(x),二、常见等值式的应用(前束范式),例8. 求下列合式公式的前束范式,(2) (x)P(x) (x)Q(x),解： (x)P(x) (x)Q(x), (x)P(x) (x)Q(x), (x)P(x) (y)Q(y), (x)(y)(P(x)Q(y),二、常见等值式的应用(前束范式),(3) (x)P(x)(x)Q(x), (x)P(x)(y)Q(y), (x)(y)(P(x)Q(y),二、常见等值式的应用(前束范式),(4) (x)P(x)(x)Q(x), (x)P(x)(y)Q(y), (x)(y)(P(x)Q(y),例8. 求下列合式公式的前束范式,例8. 求下列合式公式的前束范式,(5) (xF(x，y)yG(y)xH(x，y),二、常见等值式的应用(前束范式),(xF(x，z)yG(y)xH(x，z),(xF(x，z)yG(y)uH(u，z),xy(F(x，z)G(y)uH(u，z), xyu(F(x，z)G(y)H(u，z),前束合取范式：,前束范式(x)P(x)的命题公式部分即P(x)为合取范式。,前束析取范式：,前束范式(x)P(x)的命题公式部分即P(x)为析取范式。,二、常见等值式的应用,