《离散数学第二章课件.ppt》由会员分享，可在线阅读，更多相关《离散数学第二章课件.ppt（216页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、河南工业大学离散数学课程组河南工业大学离散数学课程组离 散 数 学河南工业大学信息科学与工程学院31 31 十二月十二月 2022 2022第一章第一章 谓词逻辑谓词逻辑河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第2 2第一章第一章 内容回顾内容回顾1 1命题的概念、表示方法；联结词的逻辑意义。命题的概念、表示方法；联结词的逻辑意义。2 2命题公式的递归定义，自然语言翻译成命题公式。命题公式的递归定义，自然语言翻译成命题公式。3 3真值表的构造、命题公式等价的概念。真值表的构造、命题公式等价的概念。4 4重重言言式式与与蕴蕴含含式式的的定定义义、逻逻辑辑意意义义，
2、逻逻辑辑等等价价与与逻逻辑辑蕴蕴含含的意义和证明方法。常用的逻辑等价公式和逻辑蕴含公式。的意义和证明方法。常用的逻辑等价公式和逻辑蕴含公式。5 5命命题题公公式式的的对对偶偶式式、合合取取范范式式、析析取取范范式式、主主合合取取范范式式、主主析析取取范范式式。小小项项、大大项项。任任给给公公式式化化为为析析取取范范式式、任任给给公公式式化化为为主主析析取取范范式式、任任给给公公式式化化为为合合取取范范式式、任任给给公公式式化化为为主主合合取范式。取范式。6 6命命题题逻逻辑辑的的推推理理理理论论，主主要要的的推推理理方方法法：真真值值表表法法、直直接接证明法、间接证明法。证明法、间接证明法。河
3、南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第3 3第二章主要内容第二章主要内容谓词逻辑的引入谓词逻辑的引入2.1 2.1 谓词的概念与表示谓词的概念与表示2.2 2.2 命题函数与量词命题函数与量词2.3 2.3 谓词公式与翻译谓词公式与翻译2.4 2.4 变元的约束变元的约束2.5 2.5 谓词演算的等价与蕴含式谓词演算的等价与蕴含式2.6 2.6 前束范式前束范式2.7 2.7 谓词演算的推理理论谓词演算的推理理论小结小结 习题习题河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第4 4本章学习要求本章学习要求 重点掌握重点掌握了解了解1
4、1 1 谓词逻辑符谓词逻辑符号化及真值号化及真值2 2 谓词公式的谓词公式的有效性和基本有效性和基本等价公式等价公式3 3 谓词演算的谓词演算的推理推理3前束范式前束范式21 1 谓词公式的谓词公式的解释和真值解释和真值2 2 自由变元和自由变元和约束变元约束变元一般掌握一般掌握2.6 前束范式前束范式2.4 变元的约束变元的约束2.12.22.32.52.7 河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第5 5谓词逻辑的引入谓词逻辑的引入问题的提出：问题的提出：在在命命题题逻逻辑辑中中，主主要要研研究究命命题题和和命命题题演演算算，其其基基本本组组成成单单位位是是
5、原原子子命命题题，原原子子命命题题是是基基本本的的、不不可可再再分分的的单单位位；但但实实际际上上，有有些些原原子子命命题题间间常常常常有有一一些些共共同同特特性性，还还可可进进一一步步对对其其进进行行分分析析，即即研研究究刻刻划划命命题题内内部部的的逻逻辑辑结结构构。(即即命命题题逻逻辑辑的的局局限限性性)在在第第一一章章,一一个个原原子子命命题题只只用用一一个个字字母母表表示示，而而不不再再对对命命题题中中的的句句子子成成分分细细分分。这这样样有有一一些些逻逻辑辑问问题题无无法法解解决决。如如部部分分简简单单的的论论断断不不能能用命题逻辑进行推证等。用命题逻辑进行推证等。如下面的例子。如下
6、面的例子。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第6 6例子例子例如例如.令：小张是大学生。令：小张是大学生。：小李是大学生。：小李是大学生。n命命题题与与中中的的谓谓语语是是相相同同的的(是是大大学学生生),),只只是是主主语不同。语不同。n从符号、中从符号、中不能归纳出他们都是大学生的共性不能归纳出他们都是大学生的共性。n我我们们希希望望从从所所使使用用的的符符号号那那里里带带给给我我们们更更多多的的信信息息，比比如如可可以以看看出出他他们们的的共共性性。这这种种想想法法在在第第一一章章是是无无法实现的。法实现的。河南工业大学离散数学课程组河南工业大学离散
7、数学课程组213213页页-第第7 7出现问题的原因出现问题的原因在于，三段论中，在于，三段论中，结论结论R与前提与前提P，Q的内在联系不的内在联系不可能在命题逻辑可能在命题逻辑中表示出来。中表示出来。逻辑学中著名的三段论方法，是由一个大前提，一个小前提推出结论的方法。这方面的例子如：著名的苏格拉底三段论：显然这是正确的推理，但在命题逻辑中却无法得到证明，因为三段论的每句话都是一个原子命题，我们可分别用P，Q，R来表示。这样，三段论方法用形式符号表示应为 PQ R 但在命题逻辑里，PQR显然不是重言式。命题演算的局限性:不能反映命题之间的内在联系,即不能将命题分解开。所有的人都是要死的。所有的
8、人都是要死的。苏格拉底是人。苏格拉底是人。所以苏格拉底是要死的。所以苏格拉底是要死的。苏格拉底（前苏格拉底（前469-469-前前399399）古希腊唯心主义哲古希腊唯心主义哲学家。学家。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第8 8谓词逻辑谓词逻辑解决这个问题的方法：解决这个问题的方法：在表示命题时，既表示出主语，也表示出谓语，就可以解决上述问题。这就提出了谓词的概念。令S(x)表示x是大学生，a:小张，b:小李 命题P表示成S(a):小张是大学生。命题Q表示成S(b):小李是大学生。从符号S(a)、S(b)可看出小张和小李都是大学生的共性.河南工业大学离散
9、数学课程组河南工业大学离散数学课程组213213页页-第第9 9谓词逻辑谓词逻辑令N(x):x是自然数。I(x):x是整数。表示所有的。A:x(N(x)I(x)B:N(8)C:I(8)N(8)N(8)I(8)I(8)推理如此实现：推理如此实现：N(8)I(8N(8)I(8)符号符号 S(x)S(x)、N(x)N(x)、I(x)I(x)就是所谓的谓词就是所谓的谓词。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第1010谓词逻辑谓词逻辑学习目的学习目的命命题题逻逻辑辑中中原原子子命命题题是是最最小小的的单单位位，不不能能够够再再进进行行分分解解，这这给给推推理理带带来来
10、了了很很大大局局限限性性，本本章章引引入入谓谓词词逻逻辑辑。学学习习关关于于谓谓词词逻逻辑辑的的相相关关概概念念和和定定理理，解决实际问题。解决实际问题。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第11112-1 2-1 谓词逻辑中的基本概念与表示谓词逻辑中的基本概念与表示 要求：要求：掌握的概念：掌握的概念：谓词、谓词填式、谓词、谓词填式、n n元谓词元谓词。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第1212基本概念的引入基本概念的引入 n命题是具有真假意义的陈述句。命题是具有真假意义的陈述句。p从语法上分析，这种句子一般有主语和
11、谓语。从语法上分析，这种句子一般有主语和谓语。如：如：“我我是大学生是大学生”，“7 7是质数是质数”。p主主语语是是谓谓语语陈陈述述的的对对象象，指指出出谓谓语语说说的的是是“谁谁”或者或者“什么什么”；p谓谓语语是是用用来来陈陈述述主主语语的的，说说明明主主语语“怎怎么么样样”或者或者“是什么是什么”。p对对应应的的，在在研研究究命命题题内内部部逻逻辑辑结结构构时时，把把这这两两部分称为部分称为客体客体或或个体、谓词个体、谓词。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第1313一、客体与谓词一、客体与谓词n客客体体定定义义：能能够够独独立立存存在在的的事事物
12、物（句句子子中中的的主主语语、宾宾语语等等），称称之之为为客客体体(Individual)，也也称称之之为为个个体体。它可以是它可以是具体具体的，也可以是的，也可以是抽象的事物抽象的事物。n谓谓词词定定义义：用用以以表表示示客客体体的的性性质质或或者者客客体体之之间间的的关系，称之为关系，称之为谓词谓词(Predicate)。例如，例如，找出下面的客体、谓词。找出下面的客体、谓词。命题：电子计算机是科学技术的工具。命题：电子计算机是科学技术的工具。客体客体：电子计算机：电子计算机谓词谓词：是科学技术的工具是科学技术的工具命题：张三命题：张三比比李四李四高高。客体客体：张三、李四。：张三、李四。
13、谓词谓词：比比高高q客体一般客体一般是充当主语是充当主语的名词或代的名词或代词。词。q客体和谓客体和谓词，它们都词，它们都不能构成完不能构成完整的句子。整的句子。说说明明河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第1414客体词的分类及表示客体词的分类及表示1.表表示示具具体体的的或或特特定定的的客客体体词词称称为为客客体体常常量量(Individual Constant)，一一般般客客体体词词常常量量用用带带或或不不带带下下标标的的小小写写英英文文字字母母a,b,c,a1,b1,c1,等等表示；表示；2.表表示示抽抽象象的的或或泛泛指指的的客客体体词词称称为为客
14、客体体变变量量(Individual Variable)，一一般般用用带带或或不不带带下下标标的的小写英文字母小写英文字母x,y,z,x1,y1,z1,等表示。等表示。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第1515谓词分类与表示谓词分类与表示用用带或不带下标的大写字母带或不带下标的大写字母来表示谓词，来表示谓词，如如P,Q,R,或或A1,A2,A3,，n表示具体性质或关系的谓词，称为表示具体性质或关系的谓词，称为谓词常量谓词常量。如：如：P:“是大学生是大学生”n表表示示抽抽象象的的、泛泛指指的的性性质质或或关关系系的的谓谓词词，称称为为谓词变元谓词变元。如
15、：如：x与与y具有具有关系关系L。x，y都是客体变元，谓词为都是客体变元，谓词为L。n这里仅讨论这里仅讨论谓词常量谓词常量。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第1616用谓词表示命题用谓词表示命题n用用谓谓词词表表达达原原子子命命题题，必必须须包包括括客客体体和和谓谓词词字字母母两两个部分。个部分。n单单独独一一个个谓谓词词不不是是完完整整的的命命题题，必必须须在在谓谓词词字字母母后后填以客体填以客体才能表示命题。才能表示命题。n谓词字母后填以客体所得的式子称为谓词字母后填以客体所得的式子称为谓词填式谓词填式。n一一个个原原子子命命题题用用一一个个谓谓词词
16、（如如P P）和和n n个个有有次次序序的的客客体体(如如a a1 1,a,a2 2,a,an n)表表示示成成P(aP(a1 1,a,a2 2,a,an n),),称称它它为为该原子命题的谓词形式或命题的谓词形式。该原子命题的谓词形式或命题的谓词形式。例如例如 “陈华陈华是河南工业大学的学生是河南工业大学的学生”；“张强张强是河南工业大学的学生是河南工业大学的学生”。若若(x)(x)：x x是河南工业大学的学生是河南工业大学的学生-P(-P(陈华陈华)-P(-P(张强张强)a a：陈华，：陈华，b b：张强：张强 P(a),P(bP(a),P(b)河南工业大学离散数学课程组河南工业大学离散数
17、学课程组213213页页-第第1717谓词谓词更一般地，更一般地，P(xP(x)：x x是河南工业大学的学生。是河南工业大学的学生。x x：客体词：客体词P P：谓词：谓词P(xP(x):):原子命题原子命题的谓词形式的谓词形式P(xP(x)河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第1818n n元谓词元谓词定定义义4.2.3 n元元谓谓词词：含含n个个命命题题变变元元的的谓谓词词称称为为n元元原原子谓词简称子谓词简称n元谓词。元谓词。p用用P(x1,x2,xn)表示。表示。pP(x1,x2,xn)的的值值为为0或或1。pn=1时，一元谓词时，一元谓词表示表示x
18、1具有性质具有性质P。pn2时，多元谓词时，多元谓词表示表示x1,x2,xn具有关系具有关系P。p0元元谓谓词词：不不含含客客体体变变元元的的谓谓词词。如如F(a)、G(a,b)、P(a1,a2,an)，实际上就是一般的命题实际上就是一般的命题。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第1919例例设有如下命题，并用设有如下命题，并用n n元谓词进行表示。元谓词进行表示。P P：王童王童是一个三好学生是一个三好学生；Q Q：李新华李新华是是李兰李兰的父亲的父亲；R R：张强张强与与谢莉谢莉是好朋友是好朋友；S S：武汉武汉位于位于北京北京和和广州广州之间之间。S
19、(xS(x)：x x是一个三好学生是一个三好学生 a a：王童：王童 命题命题P P可表示为：可表示为：S(a)S(a)F(xF(x,y),y)：x x是是y y的父亲的父亲 b b：李新华：李新华 c c：李兰：李兰 命题命题Q Q可表示为：可表示为：F(b,c)F(b,c)T(xT(x,y),y)：x x与与y y是好朋友是好朋友 d d：张强：张强 e e：谢莉：谢莉 命题命题R R可表示为：可表示为：T(d,e)T(d,e)B(x,y,zB(x,y,z)：x x位于位于y y和和z z之间之间 f f：武汉：武汉 g g：北京：北京 h h：广州：广州 命题命题S S可表示为：可表示为
20、：B(f,g,h)B(f,g,h)河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第2020结论结论n1.谓谓词词中中客客体体词词的的顺顺序序是是十十分分重重要要的的，不不能能随随意意变变更更。如命题如命题F(b,c)为为“真真”，但命题，但命题F(c,b)为为“假假”；n2.具具体体命命题题的的谓谓词词表表示示形形式式和和n元元谓谓词词是是不不同同的的，前前者者是是有有真真值值的的，而而后后者者不不是是命命题题，它它的的真真值值是是不不确确定定的的。如如上上例例中中S(x)：x是是一一个个三三好好学学生生，a为为王王童童，S(a)是有真值的，但是有真值的，但S(x)却
21、没有真值。却没有真值。n3.一一个个n元元谓谓词词不不是是一一个个命命题题，但但将将n元元谓谓词词中中的的客客体体变变元元都都用用具具体体的的客客体体取取代代后后，就就成成为为一一个个命命题题。而而且且，客客体体变变元元取取不不同同的的值值对对是是否否成成为为命命题题及及命命题题的真值有很大的影响。的真值有很大的影响。F(xF(x,y),y)：x x是是y y的父亲的父亲河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第21212-2 2-2 命题函数与量词命题函数与量词一、命题函数一、命题函数1 1、命题函数、命题函数n单单独独一一个个谓谓词词不不是是命命题题,例例如
22、如设设A:A:是是大大学学生生,不不是是命命题题,只只有有当当这这个个谓谓词词后后面面紧紧跟跟一一个个具具体体客客体体后后才才是是命题命题,如如A(A(张三张三)是一个命题。是一个命题。p设设L(xL(x,y):y):x x小小于于y,y,则则L(2,L(2,3)3)表表示示“2 2小小于于3”3”是真命题是真命题,而而L(5,1)L(5,1)表示表示“5 5小于小于1”1”是假命题。是假命题。p上例中当上例中当x,yx,y是客体变元时是客体变元时,谓词谓词L(x,yL(x,y)不是命题。不是命题。n设设P(xP(x)表示表示“x x是大学生是大学生”,p当当x x取特定的客体取特定的客体即即
23、客体常量客体常量时时,则则P(xP(x)是命题是命题,p而而当当x x可可在在一一定定的的范范围围任任意意取取值值,则则P(xP(x)不不是是命命题题，称为称为命题函数命题函数。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第2222命题函数命题函数n命题函数分为简单命题函数与复合命题函数。命题函数分为简单命题函数与复合命题函数。n定定义义2-2.1：n元元谓谓词词P(x1,x2,xn)称称之之为为简简单单命命题题函函数数。（一个谓词，一些客体变元）。（一个谓词，一些客体变元）p规规定定：当当命命题题函函数数P(x1,x2,xn)中中 n=0 时时，即即0元元谓谓词词
24、，表表示示不不含含有有客客体体变变元元的的谓谓词词，它它本本身身就就是是一个命题。一个命题。n定定义义：将将若若干干个个简简单单命命题题函函数数用用逻逻辑辑联联结结词词联联结结起起来，构成的表达式，称之为来，构成的表达式，称之为复合命题函数复合命题函数。p逻逻辑辑联联结结词词、的的意意义义与与命命题题演算中的解释完全类似。演算中的解释完全类似。nn n元谓词就是有元谓词就是有n n个客体变元的命题函数。个客体变元的命题函数。由一个谓词和若干个客体变由一个谓词和若干个客体变元组成的表达式元组成的表达式河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第2323命题函数举例命
25、题函数举例例例2.1.设设S(x)表表示示“x学学习习很很好好”,W(x)表表示示“x工工作作很很 好好”,A(xA(x)表示表示“x x身体好身体好”p S(x)n表示表示“x学习不是很好学习不是很好”,pS(x)W(x)n表示表示“x学习和工作都很好学习和工作都很好”。p A(x)(A(x)(S(x)S(x)W(xW(x)n表表示示“如如果果x x身身体体不不好好，则则x x的的学学习习与与工工作作都都不不会好会好”。p S(x),W(x)是简单命题函数是简单命题函数,p 而而 S(x),S(x)W(x),A(x)(A(x)(S(x)S(x)W(xW(x)是复合命题函数。是复合命题函数。河
26、南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第2424命题函数举例命题函数举例例例2.2.设设H(x,y)表表示示“x比比y长长得得高高”,p H(x,y)“x不比不比y长得高长得高”,p H(x,y)H(y,x)“x不不比比y长长得得高高并并且且y不不比比x长长得得高高”,即即“与与y长长得得一一样高样高”。nH(x,y)是简单命题函数是简单命题函数,n H(x,y)H(y,x)是是复复合合命命题题函函数。数。nH(x,y)与与 H(x,y)H(y,x)都都不不是是命题命题。它们都是。它们都是命题函数命题函数。n再设再设l l表示李四表示李四,z z表示张三表示张三
27、,p H(H(l l,z z)“李四长得不李四长得不比张三高比张三高”。p H(H(l,zl,z)H(H(z z,l l)“李四与张三李四与张三长得一样高长得一样高”。p H(H(l l,z z)与与 H(H(l l,z z)都是都是命题。命题。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第2525论域引入论域引入2、个体域、个体域(论域论域)n命命题题函函数数不不是是一一个个命命题题，只只有有客客体体变变元元取取特特定定名名称称时，才能成为一个命题。时，才能成为一个命题。n但但客客体体变变元元在在哪哪些些范范围围内内取取特特定定的的值值，对对是是否否成成为为命题及
28、命题的真值极有影响。命题及命题的真值极有影响。n例例2-3.P(x):x是大学生是大学生,p若若x在某大学的一个班级内取在某大学的一个班级内取,则则P(x)为真。为真。p若若x在某中学的一个班级内取在某中学的一个班级内取,则则P(x)为假。为假。p若若x在一个剧场中的观众内取在一个剧场中的观众内取,则则P(x)真假不定真假不定n例例2.4.Q(x,y)表示表示“x比比y重重”p当当x,y指人或物时，它是一个命题，指人或物时，它是一个命题，p但若但若x,y指实数时指实数时,Q(x,y)就不是一个命题。就不是一个命题。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第262
29、6论域引入论域引入例如例如2-5：(P(x,y)P(y,z)P(x,z)p若若P(x,y)解释为解释为“x小于小于y”，当当x，y，x都都在在实实数数域域中中取取值值，则则这这个个式式子子表表示示为为“若若x小小于于y且且y小于小于z，则，则x小于小于z”。这是一重言式。这是一重言式。p若若P(x,y)解释为解释为“x为为y的儿子的儿子”，当当x，y，z都都指指人人，则则“若若x为为y的的儿儿子子且且y是是z的的儿儿子子则则x是是z的儿子的儿子”。这个式子表达的是一个永假公式。这个式子表达的是一个永假公式。p如果如果P(x,y)解释为解释为“x距离距离y 10米米”，若若x，y，z表表示示地地
30、面面上上的的房房子子，那那么么“x距距离离y10米米且且y距距离离z10米则米则x距离距离z10米米”。这这个个命命题题的的真真值值将将由由x，y，z的的具具体体位位置置而而定定，它它可可能能为为T，也可能为也可能为F。xyzxyz河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第2727个体域个体域(论域论域)定定义义2-2.22-2.2 在在命命题题函函数数中中,客客体体变变元元的的取取值值范范围围称称为为个体域个体域,所有个体域的总和称为是所有个体域的总和称为是全总个体域全总个体域。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第2828
31、量词的引入量词的引入利利用用n元元谓谓词词和和它它的的论论域域概概念念，有有时时还还是是不不能能用用符符号来很准确地表达某些命题，号来很准确地表达某些命题，例如例如S(x)表示表示x是大学生是大学生，px的个体域为某单位的职工。的个体域为某单位的职工。pS(x)可表示某单位职工可表示某单位职工都是都是大学生。大学生。p也可表示某单位也可表示某单位有一些有一些职工是大学生。职工是大学生。为为了了避避免免理理解解上上的的歧歧义义，需需要要引引入入用用以以刻刻划划“所所有有的的”、“存存在在一一些些”等等表表示示不不同同数数量量的的词词，即即量量词词，全称量词、存在量词统称量词。全称量词、存在量词统
32、称量词。量词是由逻辑学家量词是由逻辑学家Fray引入的。引入的。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第2929量词量词含义含义定义定义2-2.3：在命题中表示客体数量的词，称之为：在命题中表示客体数量的词，称之为量词量词。定义定义2-2.4：量词后边要有一个客体变元，指明对哪个：量词后边要有一个客体变元，指明对哪个 客体变元量化，称此客体变元是客体变元量化，称此客体变元是量词后的量词后的 指导变元指导变元。定义定义2-2.5 称称 x x为为全称量词全称量词（Universal Quantifier），），为为 x存在量词存在量词（Existential Q
33、uantifier），），p 其中的其中的x称为称为指导变元指导变元(Function Variable)。p 一般将其量词加在其谓词之前，一般将其量词加在其谓词之前，记为记为(x x)F(x)，(x)F(x)。p此此时时，F(x)称称为为全全称称量量词词和和存存在在量量词词的的辖辖域域(Scope)。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第3030全称量词与存在量词全称量词与存在量词有些有些x x；至少有一个至少有一个x x；某一些某一些x x；存在存在x x；等等。等等。所有的所有的x x；任意的任意的x x；一切的一切的x x；每一个每一个x x；等等。
34、等等。X X即为即为指导变元指导变元河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第3131（1 1）所有的所有的老虎都要吃人；老虎都要吃人；（2 2）每一个每一个大学生都会说英语；大学生都会说英语；（3 3）所有的所有的人都长着黑头发；人都长着黑头发；（4 4）有一些有一些人登上过月球；人登上过月球；（5 5）有一些有一些自然数是素数。自然数是素数。例例2-4 2-4(x x)P(x)P(x)x x 老虎老虎(x x)Q(x)Q(x)x x 大学生大学生(x x)R(x)R(x)x x 人人(x)S(xS(x)x x 人人(x)T(xT(x)x x 自然数自然数。P
35、(xP(x)：x x会吃人会吃人则有：所有的则有：所有的x x，P(xP(x)x)x 老虎老虎 Q(xQ(x)：x x会说英语会说英语则有：每一个则有：每一个x x，Q(xQ(x)x)x 大学生大学生 R(xR(x)：x x长着黑头发长着黑头发则有：所有的则有：所有的x x，R(xR(x)x)x 人人 S(xS(x)：x x登上过月球登上过月球则有：有一些则有：有一些x x，S(xS(x)x)x 人人 T(xT(x)：x x是素数是素数则有：有一些则有：有一些x x，T(xT(x)x)x 自然数自然数 河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第3232不便之处不
36、便之处1.1.从从书写上书写上十分不便，总要特别注明个体域；十分不便，总要特别注明个体域；2.2.在在同同一一个个比比较较复复杂杂的的句句子子中中，对对于于不不同同命命题题函函数数中中的的客客体体可可能能属属于于不不同同的的个个体体域域，此此时时无无法法清清晰晰表达；表达；如例如例 (1)(1)和和(4)(4)的合取的合取 (x x)P(xP(x)(x)R(xR(x)x x 人人 x x 老虎老虎（1 1）所有的所有的老虎都老虎都要吃人；要吃人；（4 4）有一些有一些人登上人登上过月球；过月球；河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第3333不便之处不便之处(
37、续续)3.若若个个体体域域的的注注明明不不清清楚楚，将将造造成成无无法法确确定定其其真真值值。即即对对于于同同一一个个n元元谓谓词词，不不同同的的个个体体域域有有可可能能带带来来不同的真值不同的真值。例如例如 对于语句对于语句“(x)(x+6=5)”可表示为：可表示为：“有一些有一些x，使得，使得x+6=5”。该语句在下面两种个体域下有不同的真值：该语句在下面两种个体域下有不同的真值：n(1)在在实实数数范范围围内内时时，确确有有x=-1使使得得x+6=5，因此，因此，(x)(x+6=5)为为“真真”；n(2)在在正正整整数数范范围围内内时时，则则找找不不到到任任何何x，使使得得x+6=5为为
38、“真真”，所所以以，(x)(x+6=5)为为“假假”。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第3434不便之处的根源不便之处的根源都都是是因因为为需需要要特特别别标标注注每每个个谓谓词词的的个体域所致！个体域所致！全总个体域全总个体域河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第3535特性谓词特性谓词新新 的的 问问 题题 出出 现现 了了，U(xU(x)如如 何何 与与(x x)P(xP(x)结合才符合逻辑呢？结合才符合逻辑呢？U(xU(x)：x x是老虎是老虎x x老虎老虎所有的所有的老虎都要吃人；老虎都要吃人；(x x)P(
39、x)P(x)x x 老虎老虎 n对每一个客体变元的变化范围，用特性谓词加以限制。对每一个客体变元的变化范围，用特性谓词加以限制。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第3636谓词逻辑符号化的两条规则谓词逻辑符号化的两条规则统统一一个个体体域域为为全全总总个个体体域域，而而对对每每一一个个句句子子中中客客体体变变量量的的变变化化范范围围用用一一元元特特性性谓谓词词刻刻划划之之。这这种种特特性性谓词在加入到命题函数中时必定遵循如下原则：谓词在加入到命题函数中时必定遵循如下原则：（1 1）对对于于全全称称量量词词 (x x)，刻刻划划其其对对应应个个体体域域的特性
40、谓词作为的特性谓词作为蕴含式之前件蕴含式之前件加入。加入。（2 2）对对于于存存在在量量词词(x)，刻刻划划其其对对应应个个体体域域的特性谓词作为的特性谓词作为合取式之合取项合取式之合取项加入。加入。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第3737特性谓词的例子特性谓词的例子2-52-5想想想想，为为什什么么要要这这样样规规定定特特性性谓谓词词加加入入的的原则呢？若不遵循会出现什么样的问题？原则呢？若不遵循会出现什么样的问题？例例如如（1 1），符符号号化化“所所有有的的老老虎虎都都要要吃吃人人”这这个个命命题题 若若P(x)：x会吃人会吃人 U(x)：x是老
41、虎是老虎n 则符号化的正确形式应该是则符号化的正确形式应该是p(x)(U(x)P(x)p 它它的的含含义义是是：“对对于于任任意意的的x,如如果果x是是老老虎虎，则则x会吃人会吃人”，符合原命题的逻辑含义。，符合原命题的逻辑含义。n 若符号化为若符号化为 (x x)(U(x)(U(x)P(xP(x)p它它的的含含义义是是：“对对于于任任意意的的x,xx,x是是老老虎虎，并并且且x x会会吃吃人人”，与与原原命命题题“所所有有的的老老虎虎都都要要吃吃人人”的逻辑含义不符。的逻辑含义不符。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第3838特性谓词的例子（续）特性谓词
42、的例子（续）（2）有一些）有一些人登上过月球；人登上过月球；若若S(x)：x登上过月球登上过月球 U(x)：x是人是人n则符号化的正确形式应该是则符号化的正确形式应该是p(x)（U(x)S(x)p它它的的含含义义是是：“存存在在一一些些x,x是是人人，且且x登登上上过过月球月球”，符合原命题的逻辑含义。，符合原命题的逻辑含义。n 若符号化为若符号化为 (x)(U(x)P(x)p它它的的含含义义是是：“存存在在一一些些x,x,若若x x是是人人，则则x x登登上上过过月月球球”，与与原原命命题题“有有些些人人登登上上过过月月球球”的逻辑含义不符。的逻辑含义不符。河南工业大学离散数学课程组河南工业
43、大学离散数学课程组213213页页-第第3939（3 3）每一个每一个大学生都会说英语；大学生都会说英语；（4 4）有一些有一些自然数是素数。自然数是素数。特性谓词的例子（续）特性谓词的例子（续）U(x):x是大学生是大学生 Q(x):x会说英语会说英语(x x)(U(x)Q(x)U(x)：x是自然数是自然数 T(x)：x是素数是素数(x)(U(x)T(x)河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第4040特性谓词的例子（续）特性谓词的例子（续）（5 5）.有些自然数是偶数。有些自然数是偶数。设设 N(x)：x是自然数是自然数 E(xE(x)：x x是偶数是偶数
44、 此命题可以写成此命题可以写成 x(N(x)E(x)x(N(x)E(x)（6 6）.每个人都有一个生母。每个人都有一个生母。设设 P(x):xP(x):x是个人。是个人。M(x,y):yM(x,y):y是是x x的生母。的生母。此命题可以写成此命题可以写成 x x(P(x)(P(x)y y(P(y)M(x,y)(P(y)M(x,y)河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第41412-3 2-3 谓词公式及命题符号化谓词公式及命题符号化命命题题逻逻辑辑中中有有命命题题公公式式，类类似似地地，在在谓谓词词逻逻辑辑中中，要要研研究究由由简简单单命命题题函函数数与与逻
45、逻辑辑联联结结词词组组合合成成的的谓谓词词公式。公式。要求：要求：对自然语言与逻辑语言能进行翻译。对自然语言与逻辑语言能进行翻译。重点：重点：用谓词公式表达自然语言中的命题。用谓词公式表达自然语言中的命题。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第4242一一.谓词公式涉及如下四种符号：谓词公式涉及如下四种符号：（1 1）常常量量符符号号：用用带带或或不不带带下下标标的的小小写写英英文文字字母母a,a,b,cb,c,a,a1 1,b,b1 1,c,c1 1,来来表表示示。当当个个体体域域名名称称集集合合D D给给出出时时，它可以是它可以是D D中的某个元素中的某
46、个元素；（2 2）变变量量符符号号：用用带带或或不不带带下下标标的的小小写写英英文文字字母母x,x,y,zy,z,.,x,.,x1 1,y,y1 1,z,z1 1,.,.来来表表示示。当当个个体体域域名名称称集集合合D D给给出出时，它可以是时，它可以是D D中的任意元素中的任意元素；（3 3）谓谓词词符符号号：用用带带或或不不带带下下标标的的大大写写英英文文字字母母P,P,Q,R,.,PQ,R,.,P1 1,Q,Q1 1,R,R1 1.来来表表示示。当当个个体体域域名名称称集集合合D D给给出出时，时，n n元谓词符号元谓词符号P(xP(x1 1,x,x2 2,x xn n)可以是任意一个谓
47、词。可以是任意一个谓词。（4 4）客客体体函函数数符符号号：用用带带或或不不带带下下标标的的小小写写英英文文字字母母f,g,hf,g,h,.,f,.,f1 1,g,g1 1,h,h1 1,.,.来来表表示示。当当个个体体域域名名称称集集合合D D给给出出时时，n n元元函函数数符符号号f(xf(x1 1,x,x2 2,x xn n)可可以以是是D Dn nDD的的任任意意一个函数；一个函数；描述客体之间的关系。描述客体之间的关系。河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第4343为何需要客体函数符号？例为何需要客体函数符号？例2-3.12-3.1例如例如(1)(
48、1)符号化符号化“周红的父亲周红的父亲是教授是教授”：设设 P(xP(x)：x x是教授；是教授；f(xf(x)：x x的父亲；的父亲；c c：周红：周红此时此时P(f(cP(f(c)表示表示“周红的父亲是教授周红的父亲是教授”这一命题。这一命题。函数的使用给谓词逻辑中的客体词函数的使用给谓词逻辑中的客体词表示带来了很大的方便表示带来了很大的方便1 1、个体域：人、个体域：人2 2、周红的父亲、周红的父亲属于个体域属于个体域河南工业大学离散数学课程组河南工业大学离散数学课程组213213页页-第第4444客体函数客体函数 例例2-3.12-3.1(2)(2).如果如果x x是奇数，则是奇数，则
49、2x2x是偶数。是偶数。其其中中客客体体x x与与客客体体2x2x之之间间就就有有函函数数关关系系，可可以以设设客客体函数体函数 g(x)=2xg(x)=2x，谓词谓词 O(x)O(x)：x x是奇数，是奇数，E(x)E(x)：x x是偶数，是偶数，则此命题可以表示为：则此命题可以表示为：x(O(x)E(g(xx(O(x)E(g(x)(3).(3).小王的父亲是个医生。小王的父亲是个医生。设函数设函数f(xf(x)为为x x的父亲的父亲谓词谓词D(x):xD(x):x是个医生，是个医生，a:a:小王小王此命题可以表示为此命题可以表示为D(f(aD(f(a)河南工业大学离散数学课程组河南工业大学
50、离散数学课程组213213页页-第第4545客体函数和简单命题函数的区别客体函数和简单命题函数的区别把它们都看成把它们都看成“映射映射”的话的话n 客体函数是论域到论域的映射客体函数是论域到论域的映射，g:NNg:NN，p即即客客体体函函数数中中的的客客体体变变元元用用客客体体常常量量带带入入后后的的结结果果依然是个依然是个客体，客体，n而简单命题函数是从论域到而简单命题函数是从论域到T,FT,F的映射的映射，即，即E(xE(x)可以可以 看成映射看成映射E:NT,FE:NT,F，p简简单单命命题题函函数数中中的的客客体体变变元元用用客客体体常常量量带带入入后后就就变变成了成了命题命题，其真值