《离散数学课件第二章(第1讲).ppt》由会员分享，可在线阅读，更多相关《离散数学课件第二章(第1讲).ppt（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章第二章 谓词逻辑谓词逻辑n1基本概念基本概念n2谓词逻辑的翻译谓词逻辑的翻译n3谓词公式的解释谓词公式的解释n4谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式n5前束范式前束范式n6谓词逻辑演的推理理论谓词逻辑演的推理理论1 基本概念基本概念在研究命题逻辑中，原子命题是命题演算中最基本的在研究命题逻辑中，原子命题是命题演算中最基本的单位，不再对原子命题进行分解单位，不再对原子命题进行分解.这样会产生二大缺点：这样会产生二大缺点：（1）不能研究命题的结构，成分和内部逻辑的特征；）不能研究命题的结构，成分和内部逻辑的特征；（2）也不可能表达二个原子命题所具有的共同特征，）也不可能表达二个原
2、子命题所具有的共同特征，甚至在命题逻辑中无法处理一些简单又常见的推理过甚至在命题逻辑中无法处理一些简单又常见的推理过程。程。例：苏格拉底论证是正确的，但不能用命题逻辑的推理例：苏格拉底论证是正确的，但不能用命题逻辑的推理规则推导出来。规则推导出来。“所有的人总是要死的。所有的人总是要死的。P“苏格拉底是人。苏格拉底是人。Q“所以苏格拉底是要死的。所以苏格拉底是要死的。”R1.1.谓词谓词定义定义：用以刻划客体的性质或关系的即是：用以刻划客体的性质或关系的即是谓词谓词。我们可把原子命题分解为二部分：我们可把原子命题分解为二部分：主语（名词，代词）和谓语（动词）。主语（名词，代词）和谓语（动词）。
3、例：张华是学生，李明是学生。则可把它表示成：例：张华是学生，李明是学生。则可把它表示成：H:H:表示表示“是学生是学生”，j:j:表示表示“张华张华”，m:m:表示表示“李明李明”，则可用下列符号表示上述二个命题：，则可用下列符号表示上述二个命题：H(j)H(j)，H(m)H(m)。H H作为作为“谓词谓词”用大写英文字母表示，用大写英文字母表示，j,mj,m称为称为“客体客体”或称或称“个体个体”。客体一般用小写的英文字母表示。客体一般用小写的英文字母表示。分析：分析：（1）若谓词字母联系着一个客体，则称作）若谓词字母联系着一个客体，则称作一元谓词一元谓词；若谓；若谓词字母联系着二个客体，则
4、称作词字母联系着二个客体，则称作二元谓词二元谓词；若谓词字母；若谓词字母联系着联系着n个客体，则称作个客体，则称作n元谓词元谓词。（2）客体的次序必须是有规定的。）客体的次序必须是有规定的。例：河南省例：河南省北接北接河北省。河北省。nLb写成二元谓词为：写成二元谓词为：L(n,b)，但不能写成，但不能写成L(b,n)。2.2.命题函数命题函数客体在谓词表达式中可以是任意的名词。客体在谓词表达式中可以是任意的名词。例：例：C C“是有颜色的。是有颜色的。”g g：水果；：水果；y y：树叶；：树叶；f f：衣服。：衣服。则则C(g),C(y),C(f)C(g),C(y),C(f)都是命题。都是
5、命题。在上例中，如果用在上例中，如果用x x表达任意的客体，则表达任意的客体，则x x表示客体变元，表示客体变元，C(x)C(x)表示表示“x x是有颜色的是有颜色的”，则称，则称C(x)C(x)为命题函数。为命题函数。定义定义由一个谓词字母和一些非空的客体变元的集合所组由一个谓词字母和一些非空的客体变元的集合所组成的表达式，称为简单成的表达式，称为简单命题函数命题函数。讨论：讨论：（a）当简单命题函数仅有一个客体变元时，称为一元简单命）当简单命题函数仅有一个客体变元时，称为一元简单命题函数；题函数；（b）若用某一特定客体去取代客体变元之后，则命题函数）若用某一特定客体去取代客体变元之后，则命
6、题函数就变为命题；就变为命题；（c）命题函数中客体变元的取值范围称为个体域（论述域）。）命题函数中客体变元的取值范围称为个体域（论述域）。（d）个体域（论述域）个体域（论述域）:用特定的集合表示的客体变元的取用特定的集合表示的客体变元的取值范围。值范围。例：例：P(x)表示表示x是素数。这是一个命题函数。是素数。这是一个命题函数。其值取决于个体域。其值取决于个体域。个体域的给定形式有二种：个体域的给定形式有二种：具体给定。具体给定。如：如：j,e,tj,e,t全总个体域全总个体域任意域：将各种个体域综合在一起作为论述任意域：将各种个体域综合在一起作为论述范围的域称全总个体域。范围的域称全总个体
7、域。命题函数可以命题函数可以转变为命题，有两种方法：转变为命题，有两种方法：a)a)将将x x取定一个值。如：取定一个值。如：P(4)P(4)，P(5)P(5)b)b)将谓词量化。如：将谓词量化。如：xP(x)xP(x)，xP(x)xP(x)3.3.量词量词（1 1）全称量词）全称量词“”为全称量词符号，读作为全称量词符号，读作“所有的所有的”，“任意的任意的”，“每个每个”。例：例：“这里所有的都是苹果这里所有的都是苹果”可写成：可写成：xA(x)xA(x)或或(x)A(x)x)A(x)全称量词的几种形式的读法：全称量词的几种形式的读法：xP(x)xP(x)：“对所有的对所有的x x，x x
8、是是”；x xP(x)P(x)：“对所有对所有x x，x x不是不是”；xP(x)xP(x)：“并不是对所有的并不是对所有的x x，x x是是”；x xP(x)P(x)：“并不是所有的并不是所有的x x，x x不是不是”。例：将例：将“对于所有对于所有x x和所有和所有y y，如果，如果x x高于高于y y，那么，那么y y不高于不高于x x”写成命题表达形式。写成命题表达形式。解：解：G(x,y)G(x,y)：x x高于高于y y x x y(G(x,y)y(G(x,y)G(y,x)G(y,x)（2 2）存在量词）存在量词“”为存在量词符号，读作为存在量词符号，读作“存在一个存在一个”，“有
9、有些些”，“某些某些”，“至少存在一个至少存在一个”等等。等等。存在量词的几种形式的读法：存在量词的几种形式的读法：x A(x)x A(x)：存在：存在x,x,使使x x是是；x xA(x)A(x)：存在：存在x,x,使使x x不是不是；x A(x)x A(x)：不存在：不存在x,x,使使x x是是；x xA(x)A(x)：不存在：不存在x,x,使使x x不是不是。为什么将谓词量化，命题函数可以为什么将谓词量化，命题函数可以转变为命题？转变为命题？设给定个体域：设给定个体域：aa1 1a an n,以以aa1 1a an n 中的每一个个体代入中的每一个个体代入则：则：xP(x)xP(x)P(
10、aP(a1 1)P(aP(an n)xQ(x)xQ(x)Q(aQ(a1 1)Q(aQ(an n)例如：例如：Q(x)Q(x)表示表示:x5:x5-1,0,3-3,6,215,30 xQ(x)T F FxQ(x)T T F注：个体域不同，则表示同一命题的值不同。注：个体域不同，则表示同一命题的值不同。4.4.谓词公式谓词公式原子谓词公式：不出现命题联结词和量词的谓词命名式称原子谓词公式：不出现命题联结词和量词的谓词命名式称为原子谓词公式，并用为原子谓词公式，并用P(xP(x1 1x xn n)来表示。（来表示。（P P称为称为n n元谓词，元谓词，x x1 1x xn n称为客体变元）。称为客体
11、变元）。定义定义（谓词公式的归纳法定义）（谓词公式的归纳法定义）原子谓词公式是谓词公式；原子谓词公式是谓词公式；若若A A是谓词公式，则是谓词公式，则A A也是谓词公式；也是谓词公式；若若A,BA,B都是谓词公式，则都是谓词公式，则(A(A B),(AB),(A B),(AB),(AB),(AB),(AB)B)都是谓词公式；都是谓词公式；若若A A是谓词公式，是谓词公式，x x是任何变元，则是任何变元，则 xA,xA,xAxA也都是谓也都是谓词公式；词公式；当且仅当有限次地应用当且仅当有限次地应用-所求得的那些公式才是谓所求得的那些公式才是谓词公式。词公式。5.5.自由变元与约束变元自由变元与
12、约束变元(1)辖域：紧跟在量词后面括号内的谓词公式，叫做相辖域：紧跟在量词后面括号内的谓词公式，叫做相应量词的作用域或辖域。应量词的作用域或辖域。例：例：x(P(x),x(P(x)Q(x)P(x)是全称量词的辖域，是全称量词的辖域，P(x)Q(x)是存在量词的辖域。是存在量词的辖域。若量词后括号内为原子谓词公式，则括号可以省去。若量词后括号内为原子谓词公式，则括号可以省去。例：例：x(P(x)xP(x)辖域举例辖域举例在在 xP(x)xP(x)Q(x)Q(x)中中,x x的辖域是的辖域是P(x)P(x);在在 y y(C(y)C(y)x x(T(x)T(x)u uQ Q(x,ux,u)中中,u
13、 u的辖域是：的辖域是：Q Q(x,ux,u);x x的辖域是：的辖域是：T(x)T(x)u uQ Q(x,ux,u);y y的辖域是：的辖域是：C(y)C(y)x x(T(x)T(x)u uQ Q(x,ux,u).).(2)自由变元与约束变元自由变元与约束变元约束变元约束变元：位于量词的辖域内，并且与量词下标相同的变元。：位于量词的辖域内，并且与量词下标相同的变元。自由变元自由变元：当且仅当不受量词约束的变元。：当且仅当不受量词约束的变元。例：例：xP(x,y),xP(x)Q(y)在谓词公式在谓词公式 xP(x,y)中，中，x是约束变元，是约束变元，y是自由变元。是自由变元。在谓词公式在谓词
14、公式 xP(x)Q(y)中，中，x是约束变元，是约束变元，y是自是自由变元。由变元。注：自由变元可以位于量词的辖域内，也可以不在量注：自由变元可以位于量词的辖域内，也可以不在量词的辖域内。词的辖域内。(3)区别是命题还是命题函数的方法区别是命题还是命题函数的方法（a）若谓词公式中有自由变元，则该公式为命题函数；）若谓词公式中有自由变元，则该公式为命题函数；（b）若谓词公式中的变元都是约束变元，则该公式）若谓词公式中的变元都是约束变元，则该公式为命题。为命题。或者说若谓词公式中没有自由变元出现，或者说若谓词公式中没有自由变元出现，则该公式是一个命题。则该公式是一个命题。例：例：xP(x,y,z)
15、是二元命题函数是二元命题函数 y xP(x,y,z)是一元命题函数是一元命题函数 y xP(x,y)是命题是命题(4)(4)约束变元的改名规则约束变元的改名规则我们认为我们认为 xP(x,y)xP(x,y)和和 zP(z,y)zP(z,y)是等价的谓词公式，所是等价的谓词公式，所以任何谓词公式对约束变元都可以改名。以任何谓词公式对约束变元都可以改名。但是，不能用同一个变元去表示谓词公式中的二个不同但是，不能用同一个变元去表示谓词公式中的二个不同变元。变元。例如：例如：xP(x,y)xP(x,y)和和 yP(y,y)yP(y,y)是不等价的。是不等价的。约束变元的改名规则：约束变元的改名规则：（
16、a a）改名时所用的变元符号在量词辖域内未出现的；）改名时所用的变元符号在量词辖域内未出现的；（b b）在改名时要把公式中所有相同的约束变元全部同时）在改名时要把公式中所有相同的约束变元全部同时改掉。改掉。例：例：xP(x)xP(x)yR(x,y)yR(x,y)可改写成可改写成:xP(x)xP(x)zR(x,z)zR(x,z)但不能改成但不能改成:xP(x)xP(x)xR(x,x)xR(x,x)因为在谓词公式因为在谓词公式 xR(xR(x x,x),x)中，前面的中，前面的x x原为自由变元，原为自由变元，现在变为约束变元了。现在变为约束变元了。(5)自由变元的代入规则自由变元的代入规则对谓词
17、公式中的自由变元的更改叫做代入。对谓词公式中的自由变元的更改叫做代入。(a)用以代入的变元与原公式中所有变元的名称不能相同。用以代入的变元与原公式中所有变元的名称不能相同。(b)对公式中出现该自由变元的每一处都进行代入。对公式中出现该自由变元的每一处都进行代入。2 谓词公式的翻译谓词公式的翻译一般来说，将自然语言翻译成谓词公式主要有以下几个步骤：一般来说，将自然语言翻译成谓词公式主要有以下几个步骤：n（1）确定个体域，如无特别说明，一般使用全总个体域；）确定个体域，如无特别说明，一般使用全总个体域；n（2）根据个体域，分析命题中的个体、个体性质以及各个）根据个体域，分析命题中的个体、个体性质以
18、及各个个体间的关系，确定谓词；个体间的关系，确定谓词；n（3）根据表示数量的词确定量词；如果使用全总个体域，）根据表示数量的词确定量词；如果使用全总个体域，则要加入特性谓词。则要加入特性谓词。n（4）利用联结词将整个命题符号化。）利用联结词将整个命题符号化。例：某个人很聪明。例：某个人很聪明。令令C(x)C(x)：x x很聪明。很聪明。下面给出不同的个体域来讨论命题的翻译：下面给出不同的个体域来讨论命题的翻译：个体域为：个体域为：人类人类 则可翻译为则可翻译为:xC(x)xC(x)；个体域为任意域（全总个体域），则人必须首先从任个体域为任意域（全总个体域），则人必须首先从任意域中分离出来。意域
19、中分离出来。设设M(x)M(x)表示：表示：x x是人，是人，M(x)M(x)为特性谓词。为特性谓词。则可翻译为则可翻译为:x(M(x)x(M(x)C(x)C(x)特性谓词：特性谓词：用来限制个体变元取值范围的谓词。用来限制个体变元取值范围的谓词。(2)(2)对于同一个体域，用不同的量词时，特性谓词加入的方对于同一个体域，用不同的量词时，特性谓词加入的方法不同。法不同。对于全称量词，其特性谓词以条件联结词的前件的方式加入；对于全称量词，其特性谓词以条件联结词的前件的方式加入；对于存在量词，其特性谓词以合取的形式加入。对于存在量词，其特性谓词以合取的形式加入。注注:(1)(1)个体域不同，表示同
20、一命题的谓词公式的形式不同。个体域不同，表示同一命题的谓词公式的形式不同。例：例：（1 1）每个学生都要参加考试。每个学生都要参加考试。令令S(x)S(x)：x x是学生是学生 （特性谓词）（特性谓词）T(x):x T(x):x要参加考试要参加考试 可翻译为可翻译为:x x(S(x)S(x)T(x)T(x)（2 2）一些人是聪明的。）一些人是聪明的。令令M(x):xM(x):x是人是人 （特性谓词）（特性谓词）C(x)C(x)：x x是聪明的。是聪明的。可翻译为可翻译为:x x(M(x)C(x)M(x)C(x)解：设解：设 I(x):xI(x):x是整数；是整数；（特性谓词）（特性谓词）R R
21、1 1(x)(x)：x x是正数；是正数；R R2 2(x)(x)：x x是负数。是负数。此句可翻译为：此句可翻译为：x(I(x)x(I(x)(R R1 1(x)(x)R R2 2(x)(x)。例：任何整数或是正的，或是负的。例：任何整数或是正的，或是负的。例：试将苏格拉底论证符号化：例：试将苏格拉底论证符号化：“所有的人总是要死的。因所有的人总是要死的。因为苏格拉底是人，所以苏格拉底是要死的。为苏格拉底是人，所以苏格拉底是要死的。”解：设解：设M(x)M(x)：x x是人；是人；（特性谓词）（特性谓词）D(x)D(x)：x x是要死的；是要死的；M(s)M(s)：苏格拉底是人；：苏格拉底是人
22、；D(s)D(s)：苏格拉底是要死的。：苏格拉底是要死的。则翻译为：则翻译为：x(M(x)x(M(x)D(x)D(x)，M(s)M(s)D(s)D(s)例：例：“没有不犯错的人。没有不犯错的人。”解：设解：设F(x)F(x)为为“x x犯错误犯错误”，M(x)M(x)为为“x x是人是人”（特性谓词）。（特性谓词）。则可翻译为：则可翻译为：(x(M(x)x(M(x)F(x)F(x)也可以翻译为：也可以翻译为：x(M(x)x(M(x)F(x)F(x)解：解：T(x):x坐头等舱坐头等舱J(x):x坐经济舱坐经济舱F(x):x家境富裕家境富裕前提：前提：x(x(T(x)J(x),x(x(T(x)F
23、(x),x xF(x),x xF(x)例：每个乘客或坐头等舱或坐经济舱；每个乘客当且仅当其家境例：每个乘客或坐头等舱或坐经济舱；每个乘客当且仅当其家境富裕时坐头等舱；有些乘客家境富裕；并非所有的乘客都家境富富裕时坐头等舱；有些乘客家境富裕；并非所有的乘客都家境富裕。因此，有些乘客坐经济舱。（裕。因此，有些乘客坐经济舱。（个体域为全体乘客构成的集合个体域为全体乘客构成的集合）结论：结论：x xJ(x)则则可翻译为：可翻译为：(x)(S(x)x)(S(x)L(x)L(x)H(x)H(x)G(x)G(x)S(x)S(x)由于对个体描述性质的刻划深度不同，可翻译成不同形式的由于对个体描述性质的刻划深度
24、不同，可翻译成不同形式的谓词公式。谓词公式。例例：在南京高校学习的学生，未必都是南京籍的学生。：在南京高校学习的学生，未必都是南京籍的学生。设设S(x)：x是南京高校学习的学生。是南京高校学习的学生。F(x)：x是南京籍的学生。是南京籍的学生。则翻译为：则翻译为：x(S(x)F(x)本题也可加深刻划：本题也可加深刻划：S(x)：x是学生。是学生。L(x)：x在学习。在学习。H(x)：x在南京高校。在南京高校。G(x)：x是南京籍的人。是南京籍的人。谓词公式中常常含有：个体常元、个体变元（约束变元或谓词公式中常常含有：个体常元、个体变元（约束变元或自由变元）、函数变元和谓词变元等，对各种变元用指定自由变元）、函数变元和谓词变元等，对各种变元用指定的特殊常元去代替，就构成了一个公式的解释。的特殊常元去代替，就构成了一个公式的解释。3 3 谓词公式的解释谓词公式的解释一个解释一个解释I由由4部分组成：部分组成：(1)非空个体域非空个体域D；(2)D中一部分特定元素；中一部分特定元素；(3)D上一些特定的函数；上一些特定的函数；(4)D上一些特定的谓词。上一些特定的谓词。今后将谓词公式中的自由变元看作常元。于是，若对公式今后将谓词公式中的自由变元看作常元。于是，若对公式A给定了一个解释给定了一个解释I，则，则A在解释在解释I下可以计算其真值。下可以计算其真值。