《离散数学一阶逻辑ppt培训课件》由会员分享，可在线阅读，更多相关《离散数学一阶逻辑ppt培训课件（50页珍藏版）》请在金锄头文库上搜索。
1、,一阶逻辑,理学院数学系 仝 辉,一阶逻辑的基本概念 一阶逻辑合式公式及解释 一阶逻辑等值式 一阶逻辑推理理论,第二章 一阶逻辑,苏格拉底三段论,判断下面推理的正确性 凡人都是要死的。 苏格拉底是人。 所以苏格拉底是要死的。 用p,q,r表示三个命题，则（pq）r 并不是重言式。 原因缺少命题内在的联系的反映。,个体词,谓词,简单的命题被分解成个体词与谓词.6是合数； 王宏是程序员； 小李比小赵高2厘米。,个体词相关的基本概念,个体词:是可以独立存在的客体. 个体常项:用小写的英文字母 a,b,c,d. 个体变项:用小写的英文字母x,y,z. 个体域:个体的取值范围. 全总个体域:指宇宙中的一
2、切事物.,谓词相关的基本概念,谓词常项:表示具体性质或关系的谓词,用F,G,H表示. 谓词变项:表示抽象的性质或关系的谓词,也用F,G,H表示,但要根据个体变项x,y等来定. x具有属性F, 则用F(x)表示. x,y具有关系L, 则用L(x,y)表示. 谓词中的个体词数称为元数,含n 个个体词的谓词称为n元谓词 ,如： P(x1,x2,x3, ,xn). 通常，一元谓词是表示个体词的性质；n(n1)元谓词是表示个体词之间的关系，且各个体词顺序不能随意改动。如： L(x,y): 代表x小于y；而L(y,x): 代表y小于x。,谓词和命题的关系,通常，n元谓词不是命题，因其真值无法确定。如： L
3、(x,y)。并没说明其谓词的意思。 当其谓词已为常项，其还不是命题。如： L(x,y)： x小于y 。其真值仍无法确定。 只有当其谓词为常项，且n元个体词全为常量时， L(a,b)才是命题。如：a=2, b=3, 其真值可唯一确定。 通常，将不带个体变项的谓词叫0元谓词。此时其不一定是命题。只有当谓词为常项时，才是命题。 命题逻辑中的联结词在一阶逻辑中均可使用。,例题,2是素数且是偶数. F(x): x是素数; G(x): x是偶数; a:2 符号化为F(a)G(a)如果2大于3,则2大于4. L(x,y): x大于y. a:2; b:3; c:4 符号化为L(a,b)-L(a,c),量词,量
4、词:表示数量的词. 全称量词:对应日常生活中用到的“一切”，“所有的”，“任意的”，“不存在一个不”等词，用符号“”表示。x表示个体域中的所有个体。 x F(x) 表示个体域中的所有个体具有属性 F。 存在量词: 对应日常生活中用到的“存在着”，“有一个”，“至少有一个”, “不是所有的都不”等词，用符号“”表示。x 表示存在个体域中的个体。 x F(x) 表示存在个体域中的个体具有属性 F。,明确个体域,考虑个体域D为人类集合 凡人都要死的。 xF(x), 其中F(x)：x是要死的。 有人活百岁以上。 xG(x), 其中G(x)：x活百岁以上。 考虑个体域为全总个体域 对于所有个体而言，如果
5、它是人，则它是要死的。 引入新谓词M(x): x是人。M(x)称为特性谓词 x(M(x)F(x) 存在着个体，它是人并且活百岁以上。 x(M(x)G(x),用量词时的注意点,在不同的个体域中，命题符号化的形式可能不一样； 如果事先没有给出个体域，都应以全总个体域为个体域； 个体域和谓词的含义确定之后，n元谓词要转化为命题至少需要n个量词(此点以后再讨论)； 当个体域为有限集时，如果D=a1,a2,an,由量词的意义可以看出，对于任意的谓词A(x), 都有： xA(x) A(a1)A(a2) A(an); xA(x) A(a1)A(a2) A(an). 多个量词同时出现时，不能随意颠倒他们的顺序
6、。,例题,对任意的x，存在着y，使得 x+y=5. H(x,y)表示x+y=5 可符号化成：x y H(x,y) 不可符号化成： y x H(x,y),P40. 例题2.2、2.3、2.4、2.5,一阶逻辑的基本概念 一阶逻辑合式公式及解释 一阶逻辑等值式 一阶逻辑推理理论,第二章 一阶逻辑,一阶逻辑合式公式采用字母表,定义2.1字母表 个体常项：a,b,c,ai,bi,ci,., i1; 个体变项：x,y,z,xi,yi,zi,., i1; 函数符号：f,g,h,fi,gi,hi,., i1; 谓词符号：F,G,H, ,Fi,Gi,Hi, i1; 量词符号：，； 联结词：，； 括号和逗号:
7、( , ).,项的递归定义,定义2.2 个体常项和变项是项； 若（x1 ,x2 , . , xn ）是任意的n元函数， t1 ,t2 , . , tn是项，则 （t1 ,t2 , . , tn ）是项。 只有有限次地使用、生成的符号串才是项。a,b, x,y, f(x,y)=x+y，h(x,y)=xy都是项。,原子公式、合式公式,定义2.3: 原子公式 设R(x1 ,x2 ,xn)是任意的n元谓词， t1 ,t2 ,tn是项，则称R(t1 ,t2 , . , tn)为原子公式。 定义2.4: 合式公式 原子公式是合式公式； 若A是合式公式，则(7A)是合式公式； 若A,B是合式公式，则(AB)
8、,(AB), (AB), (AB)也是合式公式； 若A是合式公式，则xA，xA也是合式公式； 只有有限次地应用构成的符号串才是合式公式。,指导变项, 辖域, 约束出现,自由出现,定义2.5在合式公式xA和xA中，称x为指导变项，称A为相应量词的辖域。在辖域中，x的所有出现称为约束出现（即x受相应量词指导变项的约束），A中不是约束出现的其他变项的出现称为自由出现。,例题2.6,指出下列合式公式中指导变项，量词辖域，个体变项的约束出现，自由出现。x(F(x)yH(x,y) yH(x,y)中，y为指导变项,的辖域为H(x,y)，其中y为约束出现，x为自由出现。 整个公式，的辖域为(F(x)yH(x,
9、y)，x,y为约束出现，x约束两次，y约束一次。,封闭的合式公式,定义2.6: 设A为任一公式，若A中无自由出现的个体变项，则称A是封闭的合式公式，简称闭式。 x(F(x)G(x), xy(F(x)G(x,y)是闭式。 x(F(x)G(x,y), zyL(x,y,z)不是闭式。 xF(x)vG(x) 不是闭式。,换名规则,换名规则：将量词辖域中出现的某个约束出现的个体变项及对应的指导变项,改成另一个辖域中未曾出现的个体变项符号,公式其余部分不变. 如：在xF(x)G(x,y)中,将约束出现的x改成z,得到的公式为: zF(z)G(x,y),代替规则,代替规则:对某自由出现的个体变项用与原公式中
10、所有个体变项符号不同的变项符号去代替,且处处代替.如：在xF(x)G(x,y)中,利用代替规则,将自由出现的x用z代替,得 xF(x)G(z,y),解释I,定义2.7 一个解释I由下面4部分组成 非空个体域D; D中一部分特定元素; D上一些特定的函数; D上一些特定的谓词;在使用一个解释I解释一个公式A时,将A中的个体常项用I中特定常项代替,函数和谓词用I中的特定函数和谓词代替.如例题2.7（见下页）,例题2.7,解释I如下: D1=2,3; D1中特定元素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,
11、i, j=2,3;L(x,y)为L(2,2)=L(3,3)=1; L(2,3)=L(3,2)=0在解释I下,求下列各式的真值. (1)x(F(x)G(x,a) (2)x(F(f(x)G(x,f(x) (3) x yL(x,y),2. 解 (1),(2),(3)中公式分别为A,B,C,则 A(F(2)G(2,2)(F(3) G(3,2)(01) (1 1) 0 B(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)(0 1) 1 C(L(2,2)L(2,3) (L(3,2) L(3,3)111,例题2.8 解释N,解释N 个体
12、域为自然数集合Dn; Dn中特定元素 a=0; Dn上特定函数f(x,y)=x+y,g(x,y)=xy; Dn上特定谓词F(x,y)为x=y.,解:在解释N下,公式分别化为: x(x0=x) 假命题; (2) xy(F(f(x,0),y) F(f(y,0),x)xy(x+0=yy+0=x)真命题; (3) x+y=y+z真值不确定,不是命题.,在解释N下,下面那些公式为真?那些公式为假? (1)xF(g(x,a),x); (2)xy(F(f(x,a),y)F(f(y,a),x); (3)F(f(x,y),f(y,z),永真式,矛盾式,可满足式,设A为一公式(谓词公式)如果A在任何解释下都是真的
13、, 称A为逻辑有效式(或永真式); 如果A在任何解释下都是假的, 称A为矛盾式(或永假式); 若至少存在一个解释使A为真, 则称A是可满足式(协调式).,代换实例,设A0是含命题变项p1,p2,pn的命题公式,A1,A2,An是n个谓词公式,用Ai(1in)处处代替pi,所得公式A称为A0的代换实例.F(x)G(X), xF(x) xG(x)都是pq的代替实例.,例题2.9,判断哪些是永真式,哪些是矛盾式? xF(x)xF(x) xF(x)(x yG(x,y) xF(x) 解 设I为任意的解释,其个体域为D。若存在x0D,使得F(x0)为假, xF(x)为假,所以xF(x)xF(x)为真.对于
14、任意xD，F(x)为真,则xF(x), xF(x)同时为真.所以xF(x)xF(x)是永真式. p(qp)的代替实例,由p(pv7q)是重言式可知, xF(x)(x yG(x,y) xF(x).,一阶逻辑的基本概念 一阶逻辑合式公式及解释 一阶逻辑等值式 一阶逻辑推理理论,第二章 一阶逻辑,一阶逻辑等值式,定义2.10设A,B是一阶逻辑中任意的两公式,若AB为逻辑有效式,则称A与B是等值的,记作AB,称AB为等值式. ppp代换实例:xA(x) xA(x)xA(x) pq pqxA(x) xB(x) ( xA(x) )xB(x),量词否定等值式,定理2.1 量词否定等值式 xA(x) xA(x
15、) xA(x) xA(x) 证明:设D=a1,a2,an xA(x) (A(a1)A(a2)A(an) A(a1) A(a2) A(an) xA(x) xA(x) (A(a1)A(a2)A(an) A(a1) A(a2) A(an) xA(x),量词否定等值式,量词否定等值式 xA(x) xA(x) xA(x) xA(x) 所有人都不是一样高A(x): x是人；H(x,y): x与y不是同一个人；B(x,y): x与y一样高。 xy (A(x)A(y)H(x,y)7B(x,y)x 7y (A(x)A(y)H(x,y)B(x,y),量词辖域收缩与扩展等式,定理2.2 量词辖域收缩与扩展等式(1) x(A(x)B) (xA(x)B) x(A(x)B) ( xA(x) B) x(A(x)B) ( xA(x)B) x(B A(x) (B xA(x),
