离散数学第四章的课件

1、1主要内容主要内容l 一阶逻辑命题符号化一阶逻辑命题符号化 个体词、谓词、量词个体词、谓词、量词 一阶逻辑命题符号化一阶逻辑命题符号化l 一阶逻辑公式及其解释一阶逻辑公式及其解释 一阶语言一阶语言 合式公式合式公式 合式公式的解释合式公式的解释 永真式、矛盾式、可满足式永真式、矛盾式、可满足式第四章第四章 一阶逻辑基本概念一阶逻辑基本概念24.1 一阶逻辑命题符号化一阶逻辑命题符号化 个体词个体词所研究对象中可以独立存在的具体或抽象的客体所研究对象中可以独立存在的具体或抽象的客体 个体常项个体常项：表示具体或特定的客体的个体词，常用：表示具体或特定的客体的个体词，常用a, b, c表示表示 个

2、体变项个体变项：表示抽象或泛指的个体词，常用：表示抽象或泛指的个体词，常用x, y, z表示表示 个体域个体域(论域论域)个体变项的取值范围个体变项的取值范围 个体域可以是有穷集合，如个体域可以是有穷集合，如 a, b, c, 1, 2 , 也可以是无穷集合，如也可以是无穷集合，如 自然数集合自然数集合N, 整数集合整数集合Z, 实数集实数集合合R, 全总个体域全总个体域由宇宙间一切事物组成，包括万事万物由宇宙间一切事物组成，包括万事万物 本书在论述或推理中如不指明所采用的个体域，都是使本书在论述或推理中如不指明所采用的个体域，都是使用全总个体域。用全总个体域。3谓词谓词谓词谓词表示个体词性质

3、或相互之间关系的词，常用表示个体词性质或相互之间关系的词，常用F，G，H，表示。表示。 谓词常项谓词常项表示具体性质或关系的谓词。如表示具体性质或关系的谓词。如, F(a)：a是人是人 谓词变项谓词变项表示抽象的或泛指的性质或关系的谓词。如表示抽象的或泛指的性质或关系的谓词。如, F(x)：x具有性质具有性质F n（n 1）元谓词）元谓词表示以个体域为定义域，以表示以个体域为定义域，以0 , 1为值域的为值域的n元函数或元函数或关系。关系。 一元谓词一元谓词(n=1)表示个体词的性质表示个体词的性质 多元谓词多元谓词(n 2)表示个体词之间的相互关系表示个体词之间的相互关系 如如, L(x,y

4、)：x与与 y 有关系有关系 L，L(x,y)：x y， 0元谓词元谓词不含个体变项的谓词不含个体变项的谓词, 例如：例如：F(a) ，G(a,b) ，P(a1,a2,a3, ,an)等都是等都是0元谓词。元谓词。 当谓词为谓词常项时，当谓词为谓词常项时，0元谓词为命题。元谓词为命题。 命题逻辑中的命题均可以表示成命题逻辑中的命题均可以表示成0元谓词，因而可以将命题看成特殊的谓元谓词，因而可以将命题看成特殊的谓词。词。 4实例实例1例例4.1 将下列命题在一阶逻辑中用将下列命题在一阶逻辑中用0元谓词符号化，并讨论它们元谓词符号化，并讨论它们的真值的真值: (1)只有只有2是素数，是素数，4才是

5、素数。才是素数。 (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)中命题

6、为假。中命题为假。 5量词量词量词量词表示个体常项或变项之间数量关系的词表示个体常项或变项之间数量关系的词 全称量词全称量词 : 表示所有的表示所有的.如：如：“一切的一切的”，“所有的所有的”，“每一个每一个”，“任意的任意的”，“凡凡”，“都都”等等 x : 表示个体域中的所有个体表示个体域中的所有个体x 如如, xF(x)表示个体域中所有个体表示个体域中所有个体x都有性质都有性质F x yG(x,y)表示个体域中的所有个体表示个体域中的所有个体x和和y有关系有关系G，其中，其中F和和G是谓词。是谓词。 存在量词存在量词 : 表示存在表示存在, 有一个有一个. 如：如：“存在存在”，“有一

7、个有一个”，“有的有的”，“至少有一个至少有一个”，“有的有的”，“至至少有一个少有一个”等等 x : 个体域中存在个体个体域中存在个体x 如如, xF(x)表示个体域中存在个体表示个体域中存在个体x具有性质具有性质F x yG(x,y)表示个体域中存在个体表示个体域中存在个体x和和y有关系有关系G全称量词全称量词 与与存在量词存在量词 可以联合使用。可以联合使用。 x yG(x,y)表示对个体域中每一个个体表示对个体域中每一个个体x都存在一个个体都存在一个个体y使得使得 x和和y有关系有关系G x yG(x,y)表示个体域中存在个体表示个体域中存在个体x使得和个体域中的所有个体使得和个体域中

8、的所有个体y具有具有关系关系G6实例实例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中处有人外，还有万物，因而在符号化中处有人外，还有万物，因而在符号化时必须考虑

9、将人先分离出来。为此引入特性时必须考虑将人先分离出来。为此引入特性谓词谓词M(x)：x为人为人, F(x) 和和 G(x)的含义同的含义同(a)中。中。 (1) x(M(x)F(x) (2) x(M(x) G(x)l一定要注意正确使用特性谓词一定要注意正确使用特性谓词M(x) 、 和和 联接词。联接词。l(a)中的公式中的公式(1),(2)是一阶逻辑中两个是一阶逻辑中两个“基本基本”公式公式当当F是谓词常项时，是谓词常项时， xF(x)是一个命题。是一个命题。如果把个体域中的任如果把个体域中的任何一个个体何一个个体a代入，代入，F(a)都为真，则都为真，则 xF(x)为真；否则为真；否则 xF

10、(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(

11、x)：x2-3x+2=(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. 同一个命题，在不同个体域中的真值也可能不同。同一个命题，在不同个体域中

12、的真值也可能不同。 3.若没有指明个体域，就采用全总个体域若没有指明个体域，就采用全总个体域.8实例实例4例例4.4 将下列命题符号化，并讨论真值将下列命题符号化，并讨论真值 (1)所有的人都长着黑头发。所有的人都长着黑头发。 (2)有的人登上过月球。有的人登上过月球。 (3)没有人登上过木星。没有人登上过木星。 (4)在美国留学的学生未必都是亚洲人。在美国留学的学生未必都是亚洲人。 解解 令令M(x)：x为人为人 (1) 令令F(x): x长着黑头发长着黑头发, 则命题则命题(1)符号化为符号化为: x(M(x)F(x) 设设a为某金发姑娘，则为某金发姑娘，则M(a)为真，而为真，而F(a)

13、为假，其为假，其(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(

14、a)均为假，因而均为假，因而 (M(x)H(x)为假，所以为假，所以(3) 为真命题。为真命题。 (4)令令F(x):x是在美国留学的学生，是在美国留学的学生，G(x):x是亚洲人。命题是亚洲人。命题(4)符号化形式为符号化形式为 x(F(x)G(x) 这个命题也为真。这个命题也为真。 例例4.4 将下列命题符号化，并讨论真值将下列命题符号化，并讨论真值 (1)所有的人都长着黑头发。所有的人都长着黑头发。 (2)有的人登上过月球。有的人登上过月球。 (3)没有人登上过木星。没有人登上过木星。 (4)在美国留学的学生未必都是亚洲人。在美国留学的学生未必都是亚洲人。 10实例实例5例例4.5 将下

15、列命题符号化将下列命题符号化: (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(x,y) 或或 x y(F(x)(

16、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) x y(F(x)F(y)L(x,y) 或或 x y(F(x)F(y) L(x,y) 11 注意：注意：1、分析命题中的表示性质和关系的谓词，分别符号化为一元、分析命题中的表示性质和关系的谓词，分别符号化为一元谓词和谓词和n(n2)元谓词元谓词.2、根据命题的实际意义选用全称量词、根据命题的实际意义选用全称量词 或存在量词或存在量词 .3、 一般说来，多个量词出现时，它们的顺序不能随意调换一般说来，多个量词出现时，它们的顺序不能随意调换. 4、命题的符号化形式不惟一、命题的符号化

17、形式不惟一. 对于含对于含n元谓词的命题，在符号化时应注意以下几点：元谓词的命题，在符号化时应注意以下几点：124.2 一阶逻辑公式及解释一阶逻辑公式及解释定义定义4.1 设设L是一个非逻辑符号集合是一个非逻辑符号集合, 由由L生成的生成的一阶语言一阶语言L 的的字母表字母表包括下述符号：包括下述符号：非逻辑符号非逻辑符号 (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,

18、 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

19、) 是项是项.(3) 所有的项都是有限次使用所有的项都是有限次使用(1),(2)得到的得到的 如如, a, x, x+y, f(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)等均为原子公式等均为原子公式原子

20、公式是由项组成的原子公式是由项组成的n元谓词元谓词14定义定义4.4 一阶语言一阶语言L的的合式公式合式公式定义如下：定义如下： (1) 原子公式是合式公式原子公式是合式公式. (2) 若若A是合式公式，则是合式公式，则 ( A)也是合式公式也是合式公式 (3) 若若A, B是合式公式，则是合式公式，则(A B), (A B), (AB), (AB)也是也是 合式公式合式公式 (4) 若若A是合式公式，则是合式公式，则 xA, xA也是合式公式也是合式公式 (5) 只有有限次地应用只有有限次地应用(1)(4)形成的符号串才是合式公式形成的符号串才是合式公式.L的的合式公式合式公式也称为谓词公式

21、，简称公式。也称为谓词公式，简称公式。如如, F(x), F(x)G(x,y), x(F(x)G(x) x y(F(x)G(y) L(x,y)等都是合式公式等都是合式公式一阶语言一阶语言L的合式公式的合式公式15辖域、指导变元、约束变元、约束出现、自由出现辖域、指导变元、约束变元、约束出现、自由出现定义定义4.5 在公式在公式 xA 和和 xA 中，称中，称x为为指导变元指导变元，A为相应量词的为相应量词的辖域辖域. 在在 x和和 x的辖域中，的辖域中，x的所有出现都称为的所有出现都称为约束出现约束出现，A中不是约束出现中不是约束出现的其它变项均称为的其它变项均称为自由出现自由出现. 例如，例

22、如， 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(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

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

24、y)H(x,y) 为闭式，为闭式，而而 x(F(x) G(x,y) 不是闭式不是闭式 17 设公式设公式A，规定在解释，规定在解释I下下, 取个体域取个体域DI , 把把A中的个体常项中的个体常项符号符号a、函数符号、函数符号f、谓词符号、谓词符号F分别替换成它们在分别替换成它们在I中的解中的解释释 、 、 , 称所得到的公式称所得到的公式A 为为A在在I下的下的解释解释, 或或A在在I下下被解释成被解释成 A .公式的解释公式的解释FafF定义定义4.7 设设L是非逻辑符号集合是非逻辑符号集合L生成的一阶语言生成的一阶语言, L的的解释解释I由由4部部分组成：分组成： (a) 非空个体域非空

25、个体域 DI . (b) 对每一个个体常项符号对每一个个体常项符号a L, 有一个有一个 DI , 称称 为为a在在I 中的解释中的解释. (c) 对每一个对每一个n元函数符号元函数符号f L , 有一个有一个DI上的上的n元函数元函数 , 称称 为为f在在I中的解释中的解释. (d) 对每一个对每一个n元谓词符号元谓词符号F L, 有一个有一个DI上的上的n元谓词常项元谓词常项 , 称称 为为F在在I中的解释中的解释.aInIDDf:afF18实例实例yxyxF :),(0 ayxyxgyxyxf ),(,),(例例4.8 给定解释给定解释 I 如下：如下： (a) 个体域个体域 D=N (

26、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”，这不是，这不是命题。真值不确定。命题。真值

27、不确定。在在I下，下，(2)中公式被解释成中公式被解释成“(x+0=y)(xy=z)”，这，这不是命题。真值不确定。不是命题。真值不确定。 在在I下，下，(3)中公式被解释中公式被解释成成“xyyz”，这不是，这不是命题。真值不确定。命题。真值不确定。 在在I下，下，(4)中公式被解释中公式被解释成成“ x(xyz)”，不是，不是命题。真值不确定。命题。真值不确定。 在在I下，下，(5)中公式被解中公式被解释成释成“ x(x0=x)(x=y)”，由于蕴涵式的前件为由于蕴涵式的前件为假，所以被解释的公假，所以被解释的公式为真。式为真。 在在I下，下，(6)中公式被解中公式被解释成释成“ x(x0

28、=x)”，为，为假命题。假命题。在在I下，下，(7)中公式被解释成中公式被解释成“ x y(x+0=y)(y+0=x)”，为真命题。为真命题。 在在I下，下，(8)中公式被解释成中公式被解释成“ x y z(x+y=z)”，这也为真，这也为真命题。命题。 在在I下，下，(9)中公式被解释成中公式被解释成“ x(x+x=xx)”，为真命题。，为真命题。 19公式的类型公式的类型定理定理4.1 闭式在任何解释下都是命题闭式在任何解释下都是命题注意注意: 不是闭式的公式在某些解释下可能是命题不是闭式的公式在某些解释下可能是命题, 也可能不是也可能不是命题命题. 定义定义4.8 若公式若公式A在任何解释下均为真在任何解释下均为真, 则称则称A为为永真式永真式(逻辑逻辑有效式有效式). 若若A在任何解释下均为假在任何解释下均为假, 则称则称A为为矛盾式矛盾式(永假式永假式).