第2章一阶逻辑

1、第第2 2章章 一阶逻辑一阶逻辑2 在命题逻辑中，我们把命题分解到在命题逻辑中，我们把命题分解到原子命题为止，认为原子命题是不能再原子命题为止，认为原子命题是不能再分解的，仅仅研究以原子命题为基本单分解的，仅仅研究以原子命题为基本单位的复合命题之间的逻辑关系和推理。位的复合命题之间的逻辑关系和推理。 实际上，简单命题还可以进行分解实际上，简单命题还可以进行分解，例如，例如，“王平是大学生王平是大学生”这一简单命这一简单命题可以分解为主语题可以分解为主语(王平王平)和谓语和谓语(是大学是大学生生)，命题逻辑反映不出这一特点。，命题逻辑反映不出这一特点。 其次，如下两个简单命题其次，如下两个简单命

2、题“王平是王平是大学生大学生”和和“李明是大学生李明是大学生”，有一个，有一个共同特点共同特点是大学生，这一共性在命是大学生，这一共性在命题逻辑中也表示不出来。因此，有必要题逻辑中也表示不出来。因此，有必要推广命题逻辑。推广命题逻辑。3 第三，有些简单而正确的推理过第三，有些简单而正确的推理过程在命题演算里不能得到证明。例如著程在命题演算里不能得到证明。例如著名的苏格拉底三段论：名的苏格拉底三段论： “ “人都是要死的，苏格拉底是人人都是要死的，苏格拉底是人，所以苏格拉底是要死的。，所以苏格拉底是要死的。” ” 在命题逻辑中，三个原子命题分在命题逻辑中，三个原子命题分别用别用P P，Q Q，R

3、 R表示，现在要证明表示，现在要证明P P Q QR R，即证明即证明P P Q QR R是重言式，但这在命是重言式，但这在命题逻辑中是不可能的。因此从推理的角题逻辑中是不可能的。因此从推理的角度看，也有必要推广命题逻辑。度看，也有必要推广命题逻辑。 一阶逻辑就是命题逻辑的自然推广。一阶逻辑就是命题逻辑的自然推广。4本章内容提要：本章内容提要： 1. 1.一阶逻辑中的基本概念一阶逻辑中的基本概念 2. 2.一阶逻辑合式公式与解释一阶逻辑合式公式与解释 3. 3.一阶逻辑等值式与前束范式一阶逻辑等值式与前束范式 5本章学习要求：本章学习要求：一、重点掌握的核心知识点一、重点掌握的核心知识点 1.

4、1.能够熟练运用一阶逻辑中的翻译原理对语句进能够熟练运用一阶逻辑中的翻译原理对语句进行符号化行符号化, ,并判断谓词的真值。并判断谓词的真值。2.2.能正确地理解一阶逻辑公式的有效性，记住一能正确地理解一阶逻辑公式的有效性，记住一阶逻辑公式的基本等价公式并能加以运用。阶逻辑公式的基本等价公式并能加以运用。二、一般掌握的知识点二、一般掌握的知识点1.1.能给出一个一阶逻辑公式的解释并能判断其真能给出一个一阶逻辑公式的解释并能判断其真值。值。2.2.基本理解量词辖域、约束变元、自由变元基本理解量词辖域、约束变元、自由变元6 定义定义2.1.12.1.1 在原子命题中，在原子命题中，可以独立存可以独

5、立存在的客体称为在的客体称为个体词个体词。而。而表示单个表示单个个体的性个体的性质或两个以上个体关系的词叫质或两个以上个体关系的词叫谓词谓词。 如王平，李明，计算机，离散数学，如王平，李明，计算机，离散数学，精神等都可以作为个体。精神等都可以作为个体。(1)将表示具体的或确定的个体词称为将表示具体的或确定的个体词称为个体个体常元常元;(2)将表示抽象的或泛指的将表示抽象的或泛指的(或者说取值不或者说取值不确定的确定的)个体词称为个体词称为个体变元个体变元。 个体常量一般用小写英文字母个体常量一般用小写英文字母a,b,ca,b,c或带下或带下标的标的a ai i,b,bi i, ,c ci i表

6、示，个体变量一般用小写英文字表示，个体变量一般用小写英文字母母x,y,zx,y,z或带下标的或带下标的x xi i, ,y yi i, ,z zi i表示。表示。2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念2.1.1谓词谓词7 如：考查下列句子如：考查下列句子(1)(1)北京是中国的首都。北京是中国的首都。(2)(2)离散数学是计算机的基础课程。离散数学是计算机的基础课程。(3)(3)中国人是很聪明的。中国人是很聪明的。(4)(4)小李比小赵高小李比小赵高2 2厘米。厘米。2.1.1谓词谓词 2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念8 定义定义2.1.22.1.2 个体变元的取值范

7、围个体变元的取值范围称为称为个体域个体域( (或论域或论域) )，把宇宙间，把宇宙间所有个体域聚集在一起组成的个所有个体域聚集在一起组成的个体域称为体域称为全总个体域全总个体域。 个体域可以是有穷集合，例如个体域可以是有穷集合，例如1,2,3,4,51,2,3,4,5， a,b,ca,b,c等，也可以等，也可以是无穷集合，例如自然数集，实数是无穷集合，例如自然数集，实数集等。集等。2.1.1谓词谓词2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念9 定义定义2.1.32.1.3 谓词中包含的个体词数称谓词中包含的个体词数称为元数。含为元数。含n(n1)n(n1)个个体词的谓词个个体词的谓词称为

8、称为n n元谓词元谓词。 记为记为P(xP(x1 1，x x2 2，x xn n) )。 此时此时它以它以x x1 1，x x2 2，x xn n的的个体域为定个体域为定义义域，域，P(xP(x1 1，x x2 2，x xn n) )的值域为的值域为00，11。 当当n=1n=1时，称一元谓词；当时，称一元谓词；当n=2n=2时，称时，称为二元谓词，为二元谓词，。特别地，当。特别地，当n=0n=0，称称为零元谓词，即不带个体变元的谓词为为零元谓词，即不带个体变元的谓词为零元谓词。零元谓词是命题，这样命题零元谓词。零元谓词是命题，这样命题与谓词就得到了统一，因而可将命题看与谓词就得到了统一，因而

9、可将命题看成特殊的谓词。成特殊的谓词。2.1.1 谓词谓词2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念10一般来说，一般来说，“x是是A”类型的命题可以用类型的命题可以用A( (x) )表达。表达。对于对于“x大于大于y”这种两个个体之间关系的这种两个个体之间关系的命题，命题，可表达为可表达为B( (x，y) )，这里这里B表示表示“大于大于”谓词。谓词。我们把我们把A( (x) )称为一元谓词，称为一元谓词，B( (x，y) )称为二元谓词，称为二元谓词，M( (a，b，c) )称为三元谓词，称为三元谓词，依次类推，通常把二元以上谓词称作多元依次类推，通常把二元以上谓词称作多元谓词。谓词

10、。2.1.1谓词谓词2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念11解解(1)(1)设谓词设谓词G(x)G(x)：x x是素数，是素数，a a：4 4，b b：8 8；(1)(1)中的题符号化为谓词的蕴涵式：中的题符号化为谓词的蕴涵式：G(a)G(b)G(a)G(b)由于此蕴涵式的前件为假，所以由于此蕴涵式的前件为假，所以(1)(1)中的命题为真。中的命题为真。(2)(2)设谓词设谓词H(xH(x，y)y)：x x小于小于y y，a a：1 1，b b：2 2，c c：5 5，d d：4(2)4(2)中的命题符号化为谓词的蕴涵式：中的命题符号化为谓词的蕴涵式：H(aH(a，b)H(cb)H

11、(c，d)d)由于此蕴涵式的前件为真，后件为假，所以由于此蕴涵式的前件为真，后件为假，所以(2)(2)中的命题为假。中的命题为假。例例2.1.1 将下列命题符号化，并讨论它们的真值：将下列命题符号化，并讨论它们的真值：(1 1)只有只有4 4是素数，是素数，8 8才是素数。才是素数。(2 2)如果如果1 1小于小于2 2，则，则5 5小于小于4 4。2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念12 例例2.1.22.1.2 用个体词，谓词表示下列命题。用个体词，谓词表示下列命题。 (1)(1)张华是大学生。张华是大学生。 解解 令令a a：张华；：张华； S(x)S(x)：x x是大学生。

12、整个命是大学生。整个命题可表示为：题可表示为：S(a)S(a)。 说明说明： 若若x x的个体域为某大学计算机系的全体的个体域为某大学计算机系的全体学生，则学生，则S(a)S(a)为真；为真； 若若x x的个体域为某中学的全体学生，则的个体域为某中学的全体学生，则S(a)S(a)为假；为假； 若若x x的个体域为某电影院中的观众，则的个体域为某电影院中的观众，则S(a)S(a)真值不确定。所以个体变量在哪些个体域取真值不确定。所以个体变量在哪些个体域取特定的值，对命题的真值极有影响。特定的值，对命题的真值极有影响。2.1.1 谓词谓词2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念13(2)(

13、2)武汉位于重庆和上海之间。武汉位于重庆和上海之间。 解解 令令a a：武汉；：武汉； b b：重庆；：重庆； c c：上：上海；海； P(x,y,z)P(x,y,z)：x x位于位于y y和和z z之间。之间。整个命题可表示为整个命题可表示为P(a,b,c)P(a,b,c)。 说明说明：显然：显然P(a,b,c)P(a,b,c)为真，但为真，但P(b,a,c)P(b,a,c)为假。所以个体变量的顺序为假。所以个体变量的顺序影响命题真值，不能随意改动。影响命题真值，不能随意改动。 2.1.1 谓词谓词2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念14综上，有如下结论：综上，有如下结论： (1

14、)(1)谓词中个体词的顺序不能随意变更。(2)(2)一元谓词用以描述一个个体的某种特性，一元谓词用以描述一个个体的某种特性，而而n n元谓词则用以描述元谓词则用以描述n n个个体之间的关系。个个体之间的关系。(3)0(3)0元谓词就是一般命题。元谓词就是一般命题。(4)(4)具体命题的谓词表示形式和具体命题的谓词表示形式和n n元谓词是不同的，元谓词是不同的，前者是有真值的，而后者不是命题，它的前者是有真值的，而后者不是命题，它的真值是不确定的。真值是不确定的。(5)(5)一个一个n n元谓词不是一个命题，但将元谓词不是一个命题，但将n n元谓词中的元谓词中的个体变元都用个体域中某个具体的个体

15、取代后，个体变元都用个体域中某个具体的个体取代后，就成为一个命题。而且，个体变元在不同的个体域就成为一个命题。而且，个体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大中取不同的值对是否成为命题及命题的真值有很大的影响。的影响。 2.1.1 谓词谓词2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念15例例2.1.32.1.3 将下列命题符号化：将下列命题符号化： (1)(1)2是素数且是偶数(2)(2)如果如果2 2大于大于3 3，则，则2 2大于大于4 4(3)(3)如果张明比李民高，李民比赵亮高，则张明如果张明比李民高，李民比赵亮高，则张明比赵亮高。比赵亮高。解解(1)F(x

16、)(1)F(x)：x x是素数；是素数；G(x)G(x)：x x是偶数；是偶数；a a：2 2F(a) F(a) G(a)(2)L(x,y)(2)L(x,y)：x x大于大于y y；a a：2 2；b b：3 3；c c：4 4L(a,b) L(a,b) L(a,c)(3)H(x,y)(3)H(x,y)：x x比比y y高；高；a a：张明；：张明；b b：李民；：李民；c c：赵亮：赵亮H(a,b)H(a,b) H(b,c) H(b,c) H(a,c)H(a,c) 2.1.1 谓词谓词2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念16考虑考虑下列命题的符号化：下列命题的符号化： (1)(1

17、)所有的人都要死的所有的人都要死的(2)(2)有的人活到百岁以上有的人活到百岁以上2.1.1 谓词谓词2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念17 定义定义2.1.42.1.4 表示个体常元或变元之间表示个体常元或变元之间数量关系的词叫数量关系的词叫量词量词；1.1.全称量词：全称量词：表示表示“全部全部”，“所有的所有的”，“一切的一切的”，“每一个每一个”，“任意的任意的”等数量关系的词，用符号等数量关系的词，用符号“ ”表示；表示；( ( x)F(x)x)F(x)表示个体域里的所有个体都有表示个体域里的所有个体都有有性质有性质F F。2.2.存在量词：存在量词：表示表示“存在一些

18、存在一些”，“有一有一些些”，“至少有一个至少有一个”等数量关系的词，等数量关系的词，用符号用符号“ ”表示；表示；( ( x)F(x),x)F(x),表示存在着个体域里的某个体具有表示存在着个体域里的某个体具有有性质有性质F F。其中的其中的x x称为称为作用变量作用变量，F(x)F(x)称为全称量词或存称为全称量词或存在量词的在量词的辖域辖域2.1.2 量词量词2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念18 注意注意：量词的优先级高于任：量词的优先级高于任何联结词，所以何联结词，所以( ( x)P(xx)P(x1 1,x,x2 2,x xn n) )、( ( x)P(xx)P(x1

19、1,x,x2 2,x xn n) )、可分别写成可分别写成 xPxP(x(x1 1,x,x2 2,x xn n) )、 xPxP(x(x1 1,x,x2 2,x xn n) )，但要注意明确但要注意明确量词的辖域量词的辖域2.1.2 量词量词2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念19 例例2.1.42.1.4 符号化下列命题符号化下列命题( (设个体设个体域为整数集合域为整数集合) )。 (1)(1)所有的整数都是有理数。所有的整数都是有理数。 (2)(2)有些整数是奇数。有些整数是奇数。解解 (1)(1)令令P(x)P(x)：x x是有理数，则命题是有理数，则命题可表示为：可表示为

20、： xPxP(x)(x)。 (2)(2)令令Q(x)Q(x)：x x是奇数，则命题可表是奇数，则命题可表示为：示为： xQxQ(x)(x)。 2.1.2 量词量词2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念20将将下列命题的符号化：下列命题的符号化： 考虑个体域为人类的情况：考虑个体域为人类的情况：(1)(1)所有的人都要死的所有的人都要死的F(x):x是要死的 xFxF(x)(x)(2)(2)有的人活到百岁以上有的人活到百岁以上G(x)G(x)：x x活百岁以上活百岁以上 xFxF(x)(x)若个体域为全总个体域？若个体域为全总个体域？2.1.2 量词量词2.1 2.1 一一阶阶逻逻辑辑

21、基基本本概概念念21引出一个新的谓词，将人分离出来引出一个新的谓词，将人分离出来 。M(x)：x是人在全总个体域的情况下以上两命题在全总个体域的情况下以上两命题可叙述如下：可叙述如下：(1)(1)对所有的个体而言，如果它是人，对所有的个体而言，如果它是人，则它是要死的。则它是要死的。 x(M(x) x(M(x) F(x)F(x)(2)(2)有的人活到百岁以上有的人活到百岁以上 x(M(x) x(M(x) F(x)F(x)2.1.2 量词量词2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念22 定义定义2.1.52.1.5 若一个谓词若一个谓词P(x)P(x)是用是用来限制个体变元的取值范围，那

22、来限制个体变元的取值范围，那么称谓词么称谓词P(x)P(x)为为特性谓词特性谓词。 在使用全总个体域时，对个在使用全总个体域时，对个体变化的真正取值范围，用特性体变化的真正取值范围，用特性谓词加以限制。谓词加以限制。一般地，对全称一般地，对全称量词，将特性谓词作蕴含的前件量词，将特性谓词作蕴含的前件；对存在量词，将特性谓词作合；对存在量词，将特性谓词作合取项取项。2.1.2 量词量词2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念23 例例2.1.52.1.5 符号化下列命题符号化下列命题( (设个体设个体域为整数集合域为整数集合) )。(1)(1)所有的老虎都要吃人。所有的老虎都要吃人。(2

23、)(2)每一个大学生都会说英语。每一个大学生都会说英语。( (3)3)所有的人都长着黑头发。所有的人都长着黑头发。(4)(4)有一些人登上过月球。有一些人登上过月球。(5)(5)有一些自然数是素数。有一些自然数是素数。 2.1.2 量词量词2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念24解：解：(1)P(x):x(1)P(x):x会吃人；会吃人；Q(x)Q(x)：x x是老虎是老虎( ( x)(Q(x)x)(Q(x)P(x)P(x)(2)H(x):x(2)H(x):x是大学生；是大学生；G(x)G(x)：x x会说英语会说英语( ( x)(H(x)x)(H(x)G(x)G(x)(3)F(x

24、):x(3)F(x):x是人；是人；R(x)R(x)：x x长着黑头发长着黑头发( ( x)(F(x)x)(F(x)R(x)R(x)(4)F(x):x(4)F(x):x是人；是人；M(x)M(x)：x x登上过月球登上过月球( ( x)(F(x)x)(F(x) M(x)M(x) )(5)H(x):x(5)H(x):x是自然数；是自然数；S(x)S(x)：x x是素数是素数( ( x)(H(x)x)(H(x) S(x)S(x) )2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念25一阶逻辑符号化的两条规则：一阶逻辑符号化的两条规则： 统一个体域为全总个体域，而对每统一个体域为全总个体域，而对每一

25、个句子中个体变量的变化范围一个句子中个体变量的变化范围用一元特性谓词刻画之。特性谓用一元特性谓词刻画之。特性谓词在加入到命题函数中时必遵守词在加入到命题函数中时必遵守如下原则：如下原则：(1)(1)对全称量词，将特性谓词作为蕴对全称量词，将特性谓词作为蕴含式的前件加入；含式的前件加入；(2)(2)对存在量词，将特性谓词作为合对存在量词，将特性谓词作为合取式之合取项加入。取式之合取项加入。2.2.1 一阶逻辑公式的语言翻译一阶逻辑公式的语言翻译2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念26在进行句子翻译时，应弄清楚以下在进行句子翻译时，应弄清楚以下几个方面的问题：几个方面的问题： (1)(

26、1)首先假定个体域为全总个体域首先假定个体域为全总个体域，然后找出每个句子中具体个体，然后找出每个句子中具体个体域，并用一元特性谓词表示。域，并用一元特性谓词表示。(2)(2)确定句子中反应个体性质或者个确定句子中反应个体性质或者个体之间关系的谓词，并用合适的体之间关系的谓词，并用合适的n n元谓词表示。元谓词表示。(2)(2)确定修饰个体词的量词，是全称确定修饰个体词的量词，是全称量词还是存在量词。量词还是存在量词。2.2.1 一阶逻辑公式的语言翻译一阶逻辑公式的语言翻译2.1 2.1 一一阶阶逻逻辑辑基基本本概概念念27 例例2.2.12.2.1 用一阶逻辑符号化下述语句用一阶逻辑符号化下

27、述语句. .(1)天下乌鸦一般黑。天下乌鸦一般黑。(2)(2)没有人登上过木星。没有人登上过木星。(3)(3)在美国留学的学生未必都是亚洲人。在美国留学的学生未必都是亚洲人。(4)(4)每个实数都存在比它大的另外的实数。每个实数都存在比它大的另外的实数。(5)(5)尽管有人很聪明，但未必一切人都聪明尽管有人很聪明，但未必一切人都聪明(6)(6)对任意给定的对任意给定的00，必存在着，必存在着00，使，使得对任意的得对任意的x x，只要，只要|x-a|x-a|，就有，就有|f(x)-f(a)|f(x)-f(a)|00，必存在着，必存在着00，使得对任意的，使得对任意的x x，只，只要要|x-a|

28、x-a|，就有，就有|f(x)-f(a)|f(x)-f(a)|00) )( ( )()(0) 0) ( ( x)(x)( |x-a| |x-a| (|f(x)-f(a)|)(|f(x)-f(a)|yxy解：因为对任意的解：因为对任意的x x，任意，任意y y D D，有，有x+yx+y0 0为为“假假”，所以无论，所以无论G G(x x，y y)为为“真真”或或“假假”，都，都有有F F(x x，y y)GG(x x，y y)为为“真真”所以所以( ( x)(x)( y)(F(xy)(F(x，y)G(xy)G(x，y)y)为为“真真”。 2.2 2.2 一一阶阶逻逻辑辑公公式式及及其其解解释释

29、55(2 2)解释解释I I为：为：D D：整数集合，：整数集合， F F(x x，y y)：xyxy0 , 0 , G G(x x，y y)：x xy y。解：因为对任意的解：因为对任意的x x 0 0，当，当y y0 0时，时，有有F F(x x，y y)GG(x x，y y)为为“假假”，即有即有( y y)(F F(x x，y y)GG(x x，y y)为为“假假”。对对x x0 0，当，当y y 0 0时，时，有有F F(x x，y y)GG(x x，y y)为为“假假”，即有，即有( y y)(F F(x x，y y)GG(x x，y y)为为“假假”。所以，对任意的所以，对任意的

30、x x D D，都有，都有( y y)(F F(x x，y y)GG(x x，y y)为为“假假”。即有：即有：( ( x)(x)( y)(F(xy)(F(x，y)G(xy)G(x，y)y)为为“假假”。 2.2 2.2 一一阶阶逻逻辑辑公公式式及及其其解解释释2.2.3 2.2.3 一阶逻辑公式的解释一阶逻辑公式的解释56例例2.2.92.2.9 指出下面公式在解释指出下面公式在解释I I下的真值。下的真值。(1)G=(1)G= x(P(f(x)Q(xx(P(f(x)Q(x，f(a)f(a)；(2)H=(2)H= x(P(x)Q(xx(P(x)Q(x，a)a)。给出如下的解释给出如下的解释I

31、 I：D=2D=2，33；a a：2 2；f(2)f(2)：3 3、f(3)f(3)：2 2；P(2)P(2)：0 0、P(3)P(3)：1 1； Q(2Q(2，2)2)：1 1、Q(2Q(2，3)3)：1 1、Q(3Q(3，2)2)：0 0、Q(3Q(3，3)3)：1 1；2.2 2.2 一一阶阶逻逻辑辑公公式式及及其其解解释释2.2.3 2.2.3 一阶逻辑公式的解释一阶逻辑公式的解释572.2.3 2.2.3 谓词公式的解释谓词公式的解释2.2 2.2 谓谓词词合合式式公公式式与与解解释释解解 (1)G=P(f(2)Q(2(1)G=P(f(2)Q(2，f(2)f(2)(P(f(3)Q(3

32、(P(f(3)Q(3，f(2)f(2) = (P(3)Q(2= (P(3)Q(2，3)(P(2)Q(33)(P(2)Q(3，3)3) = (11)(01)= (11)(01) = 1= 1(2)H= P(2)Q(2(2)H= P(2)Q(2，2)P(3)Q(32)P(3)Q(3，2)2) =0110=0110 =0 =058 定义定义2.2.82.2.8 (1)(1)如果公式如果公式G G对个体域对个体域D D中任何解释中任何解释均取得真值，则称均取得真值，则称G G为为D D中的中的有效有效公式（永真式）公式（永真式）；(2)(2)如果均取得假值，则称如果均取得假值，则称G G为为D D中的

33、中的矛盾公式矛盾公式；(3)(3)如果至少有一个解释取得真值，如果至少有一个解释取得真值，则称则称G G为为D D中的中的可满足公式可满足公式。2.2 2.2 一一阶阶逻逻辑辑公公式式及及其其解解释释2.2.3 2.2.3 一阶逻辑公式的解释一阶逻辑公式的解释59 例例2.2.102.2.10 判断下列公式的类型。判断下列公式的类型。 (1)(1) x x yGyG(x-y,x+y)(x-y,x+y) (Q(QQ)Q) (2)G(x-y,x+y) (2)G(x-y,x+y) (3) (3) x x y(G(x,y)y(G(x,y)G(x,y)G(x,y) Q Q 其中其中x,yx,y的个体域为

34、整数集的个体域为整数集I I，Q Q为命题变元，为命题变元， G(x,y)G(x,y)表示表示x x y y。2.2 2.2 一一阶阶逻逻辑辑公公式式及及其其解解释释2.2.4 2.2.4 一阶逻辑公式的解释一阶逻辑公式的解释60 解解 (1)(1)无论对无论对Q Q指派何种命题常指派何种命题常元，元，Q QQ Q的真值总为的真值总为1 1，而在，而在I I中中对任意的对任意的x x，总存在，总存在y=1y=1使使x-1x-1 x+1x+1成立，所以成立，所以 x x yGyG(x-y,x+y)(x-y,x+y)在在I I中中总为真，因此总为真，因此 x x yGyG(x-(x-,x+y),x

35、+y) (Q(QQ)Q)对任意的指派总为对任意的指派总为真，是永真式。真，是永真式。 2.2 2.2 一一阶阶逻逻辑辑公公式式及及其其解解释释2.2.4 2.2.4 一阶逻辑公式的解释一阶逻辑公式的解释 (2)(2)因为因为x-yx-y x+yx+y在在I I中的真值不确中的真值不确定，当指派定，当指派x=1,y=1x=1,y=1时，时，0 0 2 2，即，即x-yx-y x+yx+y取值为真；当指派取值为真；当指派x=1,y=-1x=1,y=-1时，时，2 2 0 0不成立，即不成立，即x-x-y y x+yx+y取值为假，所以，公式取值为假，所以，公式G(x-G(x-y,x+y)y,x+y

36、)是可满足式。是可满足式。 (3)(3)无论在个体域无论在个体域I I中对中对x x，y y指派什指派什么个体常元，么个体常元，G(x,y)G(x,y)G(x,y)G(x,y)总总为假，从而为假，从而 x x y(G(x,y)y(G(x,y)G(x,y)G(x,y) Q Q总为假总为假，所以该公式是永假式。，所以该公式是永假式。 62定义定义 2.82.8 公式公式G G，H H称为等价的记为称为等价的记为G GH H，公式，如果公式，公式，如果公式G GH H为有效公式。为有效公式。定义定义 2.9 2.9 设设G G（P P1 1,P,P2 2,P Pn n）是命题公式）是命题公式， P

37、P1 1,P,P2 2,P Pn n 是出现在是出现在G G中的命题变元中的命题变元，当用任意的谓词公式，当用任意的谓词公式G Gi i分别代入分别代入P Pi i得到得到的新谓词公式的新谓词公式G G（G G1 1,G,G2 2,GnGn）称为原公）称为原公式的代入实例。式的代入实例。 永真公式的任意一个代入实例必为有永真公式的任意一个代入实例必为有效公式效公式 。2.3.1 2.3.1 谓词公式的基本等价关系谓词公式的基本等价关系2.3 2.3 一一阶阶逻逻辑辑等等值值式式632.3.1 2.3.1 谓词公式的基本等价关系谓词公式的基本等价关系1. 由命题逻辑推理定律推广而来的谓由命题逻辑

38、推理定律推广而来的谓词逻辑推理定律词逻辑推理定律 利用利用代入定理将命题逻辑中的代入定理将命题逻辑中的推理定律推广而得到谓词逻辑中的推理定律推广而得到谓词逻辑中的推理定律。推理定律。 如在命题逻辑中有公式：如在命题逻辑中有公式： G G H HG G，G GG G H H， 可推广而得：可推广而得： xAxA(x)(x)yByB(y)(y)xAxA(x)(x)， xAxA(x)(x)xAxA(x)(x)yByB(y) (y) 等等。等等。2.3 2.3 一一阶阶逻逻辑辑等等值值式式2. 由基本等值式生成的推理定律由基本等值式生成的推理定律前面给出的等值式中的每个等值式可生前面给出的等值式中的每

39、个等值式可生成两个推理定律。例如，成两个推理定律。例如， xAxA(x)(x)xAxA(x)(x)，xAxA(x)(x)xAxA(x)(x) 和和xAxA(x)(x)x x A(x), A(x), x x A(x)A(x)xAxA(x)(x) 等等。等等。2.3.1 2.3.1 谓词公式的基本等价关系谓词公式的基本等价关系2.3 2.3 一一阶阶逻逻辑辑等等值值式式653 3. . 关于量词与联结词的一元谓词等值式关于量词与联结词的一元谓词等值式 1)消去量词等值式消去量词等值式 设个体域为有限设个体域为有限集集D=aD=a1 1,a,a2 2,a,an n ，则则有有 (1)(1) xAxA

40、(x)(x)=A(a=A(a1 1) ) A(aA(a2 2) ) A(aA(an n) ) (2) (2) xAxA(x)=A(a(x)=A(a1 1) ) A(aA(a2 2) ) A(aA(an n) ) 2)2)量词否定量词否定等值式（等值式（转换律）转换律）(1)(1)xAxA(x)=(x)= x x A(x)A(x)(2)(2)xAxA(x)=(x)= x x A(x)A(x)2.3.1 2.3.1 谓词公式的基本等价关系谓词公式的基本等价关系2.3 2.3 一一阶阶逻逻辑辑等等值值式式662.3.1 2.3.1 谓词公式的基本等价关系谓词公式的基本等价关系例例 2 2 求下列各式

41、的真值。 （1）)()(yQyPy， 其中)(yP：1y，)(yQ：2y， 个体域为1，2 （2）)()(aRxQPx， 其中P：12，)(xQ：x3， )(xR：x5，a：3， 个体域为-2，3，5，6 2.3 2.3 一一阶阶逻逻辑辑等等值值式式672.3.1 2.3.1 谓词公式的基本等价关系谓词公式的基本等价关系2.3 2.3 一一阶阶逻逻辑辑等等值值式式及置换规则68例例 1 设个体域为a，b，c，试消去表达式)()(xxQxPx中的量词， 写成与之等价的命题公式。 解解 )(xPx消去量词后的等价的命题公式为： )()()()()()(bPbPaPcPbPaP )(xxQ消去量词后

42、的等价的命题公式为： )()()(cQbQaQ 2.3.1 2.3.1 谓词公式的基本等价关系谓词公式的基本等价关系2.3 2.3 一一阶阶逻逻辑辑等等值值式式693 3) )量词辖域的收缩与扩张量词辖域的收缩与扩张律律( (下述等值式下述等值式中，变元中，变元x x不在不在B B中出现中出现) )(1)(1) x(A(x)x(A(x) B)B)xAxA(x)(x) B B(2)(2) x(A(x)x(A(x) B)B)xAxA(x)(x) B B(3)(3) x(A(x)x(A(x)B)B)xAxA(x)(x)B B(4)(4) x(Bx(BA(x)A(x)B BxAxA(x)(x)(5)(

43、5) x(A(x)x(A(x) B)B)xAxA(x)(x) B B(6)(6) x(A(x)x(A(x) B)B)xAxA(x)(x) B B(7)(7) x(A(x)x(A(x)B)B)xAxA(x)(x)B B(8)(8) x(Bx(BA(x)A(x)B BxAxA(x)(x)2.3.1 2.3.1 谓词公式的基本等价关系谓词公式的基本等价关系2.3 2.3 一一阶阶逻逻辑辑等等值值式式704 4) )量词分配律量词分配律(1)(1) x(A(x)x(A(x) B(x)B(x)xAxA(x)(x)xBxB(x)(x)(2)(2) x(A(x)x(A(x) B(x)B(x)xAxA(x)(

44、x)xBxB(x)(x) 要特别注意的是，量词分配律中要特别注意的是，量词分配律中的的“ ”和和“ ”联结词不要记错。联结词不要记错。2.3.1 2.3.1 谓词公式的基本等价关系谓词公式的基本等价关系2.3 2.3 一一阶阶逻逻辑辑等等值值式式71 例例 3 3 证明下列各等价式证明下列各等价式(1)( x)(F(x)G(x)=( x)(F(x)G(x)(2)( x)(F(x)G(x)=( x)(F(x)G(x)证明证明 (1)( x)(F(x)G(x) =( x)(F(x)G(x) =( x)(F(x)G(x) =( x)(F(x)G(x) 2.3.2 2.3.2 常用等值式及等值演算常用

45、等值式及等值演算2.3 2.3 一一阶阶逻逻辑辑等等值值式式72 证明证明 （2） （ x）（）（F（x）G（x） =（ x）（F（x）G（x） =（ x）（F（x）G（x） =（ x）（）（F（x）G（x） 2.3.2 2.3.2 常用等值式及等值演算常用等值式及等值演算2.3 2.3 一一阶阶逻逻辑辑等等值值式式73 例例 4 4 证明下列等值式。证明下列等值式。(1) (1) ( x)P(x)Q(x)x)P(x)Q(x)= = y(P(y)Q(x)y(P(y)Q(x) 证明证明 ( ( x)P(x)Q(x)x)P(x)Q(x) = = ( ( x)P(x) x)P(x) Q(x)Q(x)

46、 = = x x P(x)P(x) Q(x)Q(x) = = y y P(y)P(y) Q(x)Q(x) = = y(y( P(y)P(y) Q(x)Q(x) = = y(P(y)y(P(y)Q(x)Q(x)2.3.2 2.3.2 常用等值式及等值演算常用等值式及等值演算2.3 2.3 一一阶阶逻逻辑辑等等值值式式74 (2)(2) x(A(x)B(x)x(A(x)B(x)= = xAxA(x)(x) xBxB(x)(x) 证明证明 x(A(x)x(A(x)B(x) B(x) = = x(x( A(x)A(x) B(x)B(x) = = x x A(x)A(x)xBxB(x)(x) = =xA

47、xA(x)(x)xBxB(x) (x) = = xAxA(x)(x)xBxB(x)(x)2.3.2 2.3.2 常用等值式及等值演算常用等值式及等值演算2.3 2.3 一一阶阶逻逻辑辑等等值值式式75(3)(3) x x y(P(x)Q(y)y(P(x)Q(y)= = xPxP(x)(x) yQyQ(y)(y)证明证明 x x y(P(x)y(P(x)Q(y) Q(y) = = x x y(y( P(x)P(x) Q(y)Q(y) = = x(x( P(x)P(x)yQyQ(y)(y) = = x x P(x)P(x)yQyQ(y)(y) = =xPxP(x)(x)yQyQ(y)(y) = = xPxP(x)(x)yQyQ(y)(y) 2.3.2 2.3.2 常用等值式及等值演算常用等值式及等值演算2.3 2.3 一一阶阶逻逻辑辑等等值值式式76 例例 5 5 判断公式。判断公式。( x)P(x)Q(x) (x)P(x)Q(x)