离散数学 第四章的ppt课件.ppt

《离散数学 第四章的ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学 第四章的ppt课件.ppt（38页珍藏版）》请在三一办公上搜索。

1、1,主要内容一阶逻辑命题符号化 个体词、谓词、量词 一阶逻辑命题符号化一阶逻辑公式及其解释 一阶语言 合式公式 合式公式的解释 永真式、矛盾式、可满足式,第四章 一阶逻辑基本概念,2,4.1 一阶逻辑命题符号化,个体词所研究对象中可以独立存在的具体或抽象的客体 个体常项：表示具体或特定的客体的个体词，常用a,b,c表示 个体变项：表示抽象或泛指的个体词，常用x,y,z表示 个体域(论域)个体变项的取值范围 个体域可以是有穷集合，如 a,b,c,1,2,也可以是无穷集合，如 自然数集合N,整数集合Z,实数集合R,全总个体域由宇宙间一切事物组成，包括万事万物 本书在论述或推理中如不指明所采用的个体

2、域，都是使用全总个体域。,3,谓词,谓词表示个体词性质或相互之间关系的词，常用F，G，H，表示。谓词常项表示具体性质或关系的谓词。如,F(a)：a是人 谓词变项表示抽象的或泛指的性质或关系的谓词。如,F(x)：x具有性质F n（n1）元谓词表示以个体域为定义域，以0,1为值域的n元函数或关系。一元谓词(n=1)表示个体词的性质 多元谓词(n2)表示个体词之间的相互关系 如,L(x,y)：x与 y 有关系 L，L(x,y)：xy，0元谓词不含个体变项的谓词,例如：F(a)，G(a,b)，P(a1,a2,a3,an)等都是0元谓词。当谓词为谓词常项时，0元谓词为命题。命题逻辑中的命题均可以表示成0

3、元谓词，因而可以将命题看成特殊的谓词。,4,实例1,例4.1 将下列命题在一阶逻辑中用0元谓词符号化，并讨论它们的真值:(1)只有2是素数，4才是素数。(2)如果5大于4，则4大于6.,解(1)设一元谓词F(x):x是素数，a:2，b:4。(1)中命题符号化为0元谓词的蕴涵式:F(b)F(a)由于此蕴涵式的前件为假，所以(1)中命题为真。(2)设二元谓词G(x，y):x大于y，a:4，b:5，c:6。G(b,a)，G(a,c)是两个0元谓词，把(2)中命题符号化为 G(b,a)G(a,c)由于G(b,a)为真，而G(a,c)为假，所以(2)中命题为假。,5,量词,量词表示个体常项或变项之间数量

4、关系的词 全称量词:表示所有的.如：“一切的”，“所有的”，“每一个”，“任意的”，“凡”，“都”等 x:表示个体域中的所有个体x 如,xF(x)表示个体域中所有个体x都有性质F xyG(x,y)表示个体域中的所有个体x和y有关系G，其中F和G是谓词。存在量词:表示存在,有一个.如：“存在”，“有一个”，“有的”，“至少有一个”，“有的”，“至少有一个”等 x:个体域中存在个体x 如,xF(x)表示个体域中存在个体x具有性质F xyG(x,y)表示个体域中存在个体x和y有关系G全称量词与存在量词可以联合使用。xyG(x,y)表示对个体域中每一个个体x都存在一个个体y使得 x和y有关系G xyG

5、(x,y)表示个体域中存在个体x使得和个体域中的所有个体y具有关系G,6,实例2,例4.2 在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化:(1)凡人都呼吸。(2)有的人用左手写字。其中:(a)个体域D1为人类集合；(b)个体域D2为全总个体域。,解(a)令F(x):x呼吸.G(x)：x用左手写字(1)符号化为 xF(x),(2)符号化为 xG(x),(b)D2中处有人外，还有万物，因而在符号化时必须考虑将人先分离出来。为此引入特性谓词M(x)：x为人,F(x)和 G(x)的含义同(a)中。,(1)x(M(x)F(x),(2)x(M(x)G(x),一定要注意正确使用特性谓词M(x

6、)、和联接词。(a)中的公式(1),(2)是一阶逻辑中两个“基本”公式,当F是谓词常项时，xF(x)是一个命题。如果把个体域中的任何一个个体a代入，F(a)都为真，则xF(x)为真；否则xF(x)为假。,当F是谓词常项时，xF(x)也是一个命题。如果个体域中存在一个个体a，使得F(a)都为真，则xF(x)为真；否则xF(x)为假。,7,实例3,例4.3 在个体域限制为(a)和(b)条件时，将下列命题符号化，并给出真值:(1)对于任意的x，均有x2-3x+2=(x-1)(x-2).(2)存在x，使得x+5=3.其中:(a)个体域D1=N(b)个体域D2=R,解(a)令F(x)：x2-3x+2=(

7、x-1)(x-2)，G(x):x+5=3(1)符号化为 xF(x)真命题,(2)符号化为 xG(x)假命题,(b)在D2内，(1)和(2)的符号化形式还是同(a)，(1)依然是真命题，而此时(2)也是真命题。,从例4.2和例4.3可以看出以下两点:1.在不同个体域内，同一个命题的符号化形式可能不同，也可能相同。2.同一个命题，在不同个体域中的真值也可能不同。3.若没有指明个体域，就采用全总个体域.,8,实例4,例4.4 将下列命题符号化，并讨论真值(1)所有的人都长着黑头发。(2)有的人登上过月球。(3)没有人登上过木星。(4)在美国留学的学生未必都是亚洲人。,解 令M(x)：x为人(1)令F

8、(x):x长着黑头发,则命题(1)符号化为:x(M(x)F(x)设a为某金发姑娘，则M(a)为真，而F(a)为假，其(1)为假命题,(2)令G(x):x登上过月球,则命题(2)符号化为:x(M(x)G(x)设a是1969年登上月球完成阿波罗计划的美国宇航员阿姆斯特朗，则M(a)G(a)为真，所以(2)为真命题。,9,(3)令H(x):x登上过木星,则命题(3)符号化为:x(M(x)H(x)到目前为止，对于任何一个人(含已经去世的人)都还没有登上过木星，所以对任何人a，M(a)H(a)均为假，因而(M(x)H(x)为假，所以(3)为真命题。,(4)令F(x):x是在美国留学的学生，G(x):x是

9、亚洲人。命题(4)符号化形式为 x(F(x)G(x)这个命题也为真。,例4.4 将下列命题符号化，并讨论真值(1)所有的人都长着黑头发。(2)有的人登上过月球。(3)没有人登上过木星。(4)在美国留学的学生未必都是亚洲人。,10,实例5,例4.5 将下列命题符号化:(1)兔子比乌龟跑得快。(2)有的兔子比所有的乌龟跑得快。(3)并不是所有的兔子都比乌龟跑得快。(4)不存在跑得同样快的两只兔子。,解:令F(x):x是兔子，G(y):y是乌龟，H(x,y):x比y跑得快，L(x,y):x与y跑得同样快。这4个命题分别符号化为(1)x y(F(x)G(y)H(x,y)(2)x(F(x)y(G(y)H

10、(x,y)或x y(F(x)(G(y)H(x,y)(3)x y(F(x)G(y)H(x,y)或x y(F(x)G(y)H(x,y)(4)xy(F(x)F(y)L(x,y)或 xy(F(x)F(y)L(x,y),11,注意：1、分析命题中的表示性质和关系的谓词，分别符号化为一元谓词和n(n2)元谓词.2、根据命题的实际意义选用全称量词或存在量词.3、一般说来，多个量词出现时，它们的顺序不能随意调换.4、命题的符号化形式不惟一.,对于含n元谓词的命题，在符号化时应注意以下几点：,12,4.2 一阶逻辑公式及解释,定义4.1 设L是一个非逻辑符号集合,由L生成的一阶语言L 的字母表包括下述符号：非逻

11、辑符号(1)L中的个体常项符号：a,b,c,ai,bi,ci,i 1(2)L中的函数符号：f,g,h,fi,gi,hi,i 1(3)L中的谓词符号：F,G,H,Fi,Gi,Hi,i 1逻辑符号(4)个体变项符号：x,y,z,xi,yi,zi,i 1(5)量词符号：,(6)联结词符号：,(7)括号与逗号：(,),，.,13,一阶语言L的项与原子公式,定义4.2 一阶语言L的项的定义如下：(1)个体常项和个体变项是项.(2)若(x1,x2,xn)是任意的n元函数，t1,t2,tn是任意的 n个项，则(t1,t2,tn)是项.(3)所有的项都是有限次使用(1),(2)得到的 如,a,x,x+y,f(

12、x),g(x,y),f(x+y,z),g(xy,y),h(xy,x+y+z)等都是项,定义4.3 设R(x1,x2,xn)是一阶语言L的任意的n元谓词，t1,t2,tn是一阶语言L的任意的n个项，则称R(t1,t2,tn)是一阶语言L的原子公式.如，F(x,y),F(f(x1,x2),g(x3,x4)等均为原子公式原子公式是由项组成的n元谓词,14,定义4.4 一阶语言L的合式公式定义如下：(1)原子公式是合式公式.(2)若A是合式公式，则(A)也是合式公式(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是 合式公式(4)若A是合式公式，则xA,xA也是合式公式(5)只有有

13、限次地应用(1)(4)形成的符号串才是合式公式.L的合式公式也称为谓词公式，简称公式。如,F(x),F(x)G(x,y),x(F(x)G(x)xy(F(x)G(y)L(x,y)等都是合式公式,一阶语言L的合式公式,15,辖域、指导变元、约束变元、约束出现、自由出现,定义4.5 在公式 xA 和 xA 中，称x为指导变元，A为相应量词的辖域.在x和x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其它变项均称为自由出现.例如，x(F(x,y)G(x,z)，x为指导变元，(F(x,y)G(x,z)为x 的辖域，x的两次出现均为约束出现，y与 z 均为自由出现又如,x(F(x,y,z)y(G

14、(x,y)H(x,y,z),x中的x是指导变元,辖域为(F(x,y,z)y(G(x,y)H(x,y,z).y中的y是指导变元,辖域为(G(x,y)H(x,y,z).x的3次出现都是约束出现,y的第一次出现是自由出现,后2次是约束出现,z的2次出现都是自由出现。注意：在以上公式中，前件中的x（它在x的辖域中）与后件中的x（它不在x的辖域中）不是同一个东西，而是两个不同的东西使用了同一个符号，如同两个人都叫李四，是两个不同的人起了同一个名字。,16,封闭的公式,定义4.6 若公式A中不含自由出现的个体变项，则称A为封闭的公式，简称闭式.例如，xy(F(x)G(y)H(x,y)为闭式，而 x(F(x

15、)G(x,y)不是闭式,17,设公式A，规定在解释I下,取个体域DI,把A中的个体常项符号a、函数符号f、谓词符号F分别替换成它们在I中的解释、,称所得到的公式A为A在I下的解释,或A在I下被解释成 A.,公式的解释,定义4.7 设L是非逻辑符号集合L生成的一阶语言,L的解释I由4部分组成：(a)非空个体域 DI.(b)对每一个个体常项符号aL,有一个 DI,称 为a在I 中的解释.(c)对每一个n元函数符号fL,有一个DI上的n元函数,称 为f在I中的解释.(d)对每一个n元谓词符号FL,有一个DI上的n元谓词常项,称 为F在I中的解释.,18,实例,例4.8 给定解释 I 如下：(a)个体

16、域 D=N(b)(c)(d)写出下列公式在I下的解释,并指出它的真值.(1)F(f(x,y),g(x,y)(2)F(f(x,a),y)F(g(x,y),z)(3)F(g(x,y),g(y,z)(4)xF(g(x,y),z)(5)xF(g(x,a),x)F(x,y)(6)xF(g(x,a),x)(7)x y(F(f(x,a),y)F(f(y,a),x)(8)x y zF(f(x,y),z)(9)xF(f(x,x),g(x,x),在I下，(1)中公式被解释成“x+y=xy”，这不是命题。真值不确定。,在I下，(2)中公式被解释成“(x+0=y)(xy=z)”，这不是命题。真值不确定。,在I下，(3

17、)中公式被解释成“xyyz”，这不是命题。真值不确定。,在I下，(4)中公式被解释成“x(xyz)”，不是命题。真值不确定。,在I下，(5)中公式被解释成“x(x0=x)(x=y)”，由于蕴涵式的前件为假，所以被解释的公式为真。,在I下，(6)中公式被解释成“x(x0=x)”，为假命题。,在I下，(7)中公式被解释成“xy(x+0=y)(y+0=x)”，为真命题。,在I下，(8)中公式被解释成“xyz(x+y=z)”，这也为真命题。,在I下，(9)中公式被解释成“x(x+x=xx)”，为真命题。,19,公式的类型,定理4.1 闭式在任何解释下都是命题注意:不是闭式的公式在某些解释下可能是命题,

18、也可能不是命题.定义4.8 若公式A在任何解释下均为真,则称A为永真式(逻辑有效式).若A在任何解释下均为假,则称A为矛盾式(永假式).若至少有一个解释使A为真,则称A为可满足式.几点说明：永真式为可满足式，但可满足式不一定是永真式。判断公式是否是可满足的(永真式,矛盾式)是不可判定的。,20,代换实例,定义4.9 设A0是含命题变项 p1,p2,pn的命题公式，A1,A2,An是n个谓词公式，用Ai 处处代替A0中的pi，1in，所得公式A称为A0的代换实例.例如，F(x)G(x),xF(x)yG(y)等都是pq的代换实例.定理4.2 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式.

19、,21,实例,例4.9 判断下列公式中，哪些是永真式，哪些是矛盾式？(1)x(F(x)G(x),解：解释I1:个体域N,F(x):x5,G(x):x4,公式为真 解释I2:个体域N,F(x):x5,G(x):x4,公式为假结论:非永真式的可满足式,22,实例,例4.9 判断下列公式中，哪些是永真式，哪些是矛盾式？,(2)x(F(x)G(x),解：解释I1:个体域为实数集合R，F(x):x2+1=1，G(x):x+1=1，公式（2）在I1下为真。公式（2）是可满足式。解释I2:个体域为实数集合R，F(x):x2-1=1，G(x):x2+1=1，公式（2）在解释I2下为假。公式（2）不是永真式。结

20、论:公式（2）是非永真式的可满足式,23,实例,例4.9 判断下列公式中，哪些是永真式，哪些是矛盾式？(3)xF(x)(xyG(x,y)xF(x),解：重言式 p(qp)的代换实例，故为永真式.,(4)(xF(x)yG(y)yG(y),解：矛盾式(pq)q 的代换实例，故为永假式.,24,实例,例4.10 判断下列公式的类型：(1)xF(x)xF(x),解：记(1)中的公式为A。设I为任意一个解释，个体域为D.若后件xF(x)为假，则对所有的xD，F(x)为假。于是，xF(x)为假，从而A为真。所以，在I下A为真。由I的任意性，A是永真式。,25,实例,例4.10 判断下列公式的类型：(2)x

21、yF(x,y)xyF(x,y),解：记(2)中的公式为B。解释I1：个体域为自然数集合N，F(x,y)：xy。在I1下B的前件与后件均为真，B为真，所以B是可满足式。解释I2：个体域为自然数集合N，F(x,y)：xy。在 I2下，B的前件为真后件为假，B为假，所以B不是永真式。故B为非永真式的可满足式。,26,实例,例4.10 判断下列公式的类型：(3)x(F(x)G(x)yG(y),解：记(3)中的公式为C。解释I1：个体域为实数集合R，F(x)：x是无理数，G(x)：x能表示成分数。在I1下C的前件为假，所以C为真，C是可满足式。解释I2：个体域为实数集合R，F(x)：x是整数，G(x)：

22、x是有理数。在I2下，C的前件为真后件为假，C为假，所以C不是永真式。故C为非永真式的可满足式。,27,作业,书本第66页第9题的第（1）和（3）两个小题第11题的第（1）、（3）、（6）三个小题 请大家把答案写在科作业纸上，注意写明题号。下次上课之前交给我。,28,第四章 习题课,主要内容个体词、谓词、量词一阶逻辑命题符号化一阶语言L 项、原子公式、合式公式公式的解释 量词的辖域、指导变元、个体变项的自由出现与约束出现、闭式、解释公式的类型 永真式(逻辑有效式)、矛盾式(永假式)、可满足式,29,基本要求,准确地将给定命题符号化 理解一阶语言的概念 深刻理解一阶语言的解释 熟练地给出公式的解

23、释 记住闭式的性质并能应用它 深刻理解永真式、矛盾式、可满足式的概念,会判断简 单公式的类型,30,练习1,1.在分别取个体域为(a)D1=N(b)D2=R(c)D3为全总个体域的条件下,将下面命题符号化，并讨论真值(1)对于任意的数x，均有,解 设G(x):(a)xG(x),(b)xG(x),(c)又设F(x):x是实数 x(F(x)G(x),真,真,假,31,练习1(续),解 设H(x)：x+7=5(a)xH(x),(2)存在数x，使得 x+7=5,(b)xH(x),(c)又设F(x)：x为实数 x(F(x)H(x),本例说明：不同个体域内，命题符号化形式可能不同（也可能相同），真值可能不

24、同（也可能相同）.,真,真,假,32,练习2,2.在一阶逻辑中将下列命题符号化(1)大熊猫都可爱,(2)有人爱发脾气,(3)说所有人都爱吃面包是不对的,设F(x):x为大熊猫，G(x):x可爱 x(F(x)G(x),设F(x):x是人，G(x):x爱发脾气 x(F(x)G(x),设F(x):x是人，G(x):x爱吃面包 x(F(x)G(x)或 x(F(x)G(x),33,练习2,(4)没有不爱吃糖的人,(5)任何两个不同的人都不一样高,(6)不是所有的汽车都比所有的火车快,设F(x):x是人，G(x):x爱吃糖x(F(x)G(x)或 x(F(x)G(x),设F(x):x是人,H(x,y),x与

25、y相同,L(x,y):x与y一样高 x(F(x)y(F(y)H(x,y)L(x,y)或 xy(F(x)F(y)H(x,y)L(x,y),设F(x):x是汽车,G(y):y是火车,H(x,y):x比y快 xy(F(x)G(y)H(x,y)或 xy(F(x)G(y)H(x,y),34,练习3,x(2x=x)假,3.给定解释 I 如下:(a)个体域D=N(b)=2(c)(d)说明下列公式在 I 下的涵义,并讨论真值(1)xF(g(x,a),x),(2)xy(F(f(x,a),y)F(f(y,a),x),xy(x+2=yy+2=x)假,35,练习3,(3)xyzF(f(x,y),z),(5)xF(f(

26、x,x),g(x,x),(4)xyzF(f(y,z),x),xyz(y+z=x)假,xyz(x+y=z)真,x(x+x=xx)真,(3),(4)说明与不能随意交换,36,练习4,4.证明下面公式既不是永真式，也不是矛盾式:,(1)x(F(x)G(x),(2)xy(F(x)G(y)H(x,y),解释1:D1=N,F(x):x是偶数,G(x):x是素数,真,解释2:D2=N,F(x):x是偶数,G(x):x是奇数,假,解释1:D1=Z,F(x):x是正数,G(x):x是负数,H(x,y):xy 真,解释2:D2=Z,F(x):x是偶数,G(x):x是奇数,H(x,y):xy 假,37,练习5,5.证明下列公式为永真式:(1)(xF(x)yG(y)xF(x)yG(y),(2)x(F(x)(F(x)G(x),(AB)AB的代换实例,设I是任意的一个解释,对每一个xDI,F(x)(F(x)G(x)恒为真,38,作业,书本第65页第2题第5题的第（1）和（3）两个小题书本第66页第8题的第（1）和（3）两个小题 请大家把答案写在科作业纸上，注意写明题号。下次上课之前统一交到学委那里，然后再拿给我。,