在命题逻辑中-是把简单命题作为基本单元或说作为原子来上课讲义
o在命题逻辑中，是把简单命题作为基本单元在命题逻辑中，是把简单命题作为基本单元或说作为原子来看待的，不再对简单命题的或说作为原子来看待的，不再对简单命题的内部结构进行内部结构进行(jnxng)分析分析o如如,命题：命题：“squr(2)是无理数是无理数”和和“squr(3)是无理数是无理数”是作为两个独立的命是作为两个独立的命题看待的题看待的,不考虑命题间的联系不考虑命题间的联系o事实上这两个命题仍可作分解，它们都有主事实上这两个命题仍可作分解，它们都有主词和谓词这样的细分带来的好处是可将这词和谓词这样的细分带来的好处是可将这两个有相同谓词两个有相同谓词(“是无理数是无理数”)的命题联系的命题联系起来起来第四章第四章 谓词谓词(wi c)(wi c)逻辑的基本概逻辑的基本概念念第一页，共56页命题逻辑的局限性命题逻辑的局限性o举例：凡有理数都是实数，举例：凡有理数都是实数，2/7是有理数，所以是有理数，所以(suy)2/7是实数是实数o直观上看这样的推理应该是正确的然而在命题逻辑里就不能描述这直观上看这样的推理应该是正确的然而在命题逻辑里就不能描述这种推理种推理o设这三个命题分别以设这三个命题分别以p,q,r表示，相应的推理形式为：表示，相应的推理形式为：(p q)r。
由于对任意的由于对任意的p，q，r来说这推理形式并非重言式，也就是说这个推来说这推理形式并非重言式，也就是说这个推理形式不是正确的理形式不是正确的o对这样的人们熟知的推理关系在命题逻辑中得不到正确的描述，自然对这样的人们熟知的推理关系在命题逻辑中得不到正确的描述，自然是命题逻辑的局限性是命题逻辑的局限性o要认识这种推理规律，只有对简单命题做进一步剖析这就需要引入要认识这种推理规律，只有对简单命题做进一步剖析这就需要引入谓词、变量以及表示变量数量的量词谓词、变量以及表示变量数量的量词(全称量词和存在量词，分别表全称量词和存在量词，分别表示一般的和个别的情况示一般的和个别的情况)，进而研究它们的形式结构和逻辑关系，这，进而研究它们的形式结构和逻辑关系，这便构成了谓词逻辑便构成了谓词逻辑第二页，共56页o约定约定o小写字母表示小写字母表示(biosh)(biosh)命题命题o大写字母表示大写字母表示(biosh)(biosh)谓词谓词o内容仅限于一阶谓词逻辑或称狭谓词逻辑内容仅限于一阶谓词逻辑或称狭谓词逻辑说明说明(shumng)第三页，共56页4.1 谓词谓词(wi c)和个体词和个体词4.1.1 谓词谓词(wi c)o例例 张三是学生李四是学生张三是学生李四是学生o在命题逻辑里，这是两个不同的命题，只能分别以两在命题逻辑里，这是两个不同的命题，只能分别以两个不同的符号如个不同的符号如p，q表示表示o然而这两个命题的共同点是，它们都有主词和谓词然而这两个命题的共同点是，它们都有主词和谓词o主词主词“张三张三”、“李四李四”是不同的，而谓词是不同的，而谓词“是学生是学生”是相同的是相同的o现在强调它们的共同点若以大写符号现在强调它们的共同点若以大写符号P表示表示“是学是学生生”，这样两个命题的共同性可由，这样两个命题的共同性可由P来体现了，但主来体现了，但主词还需区别开来，便可把这两个命题分别写成词还需区别开来，便可把这两个命题分别写成P(张张三三)和和P(李四李四)o明显地描述了这两个命题的共同点和不同点明显地描述了这两个命题的共同点和不同点o一般地可引入变量一般地可引入变量x来表示主词，于是符号来表示主词，于是符号P(x)就表就表示示“x是学生是学生”通常通常(tngchng)把把P(x)称作谓词称作谓词第四页，共56页。
o一元谓词一元谓词o在一个命题里，如果主词只有一个，这时表示该主词在一个命题里，如果主词只有一个，这时表示该主词性质或属性的词便称作谓词这是一元性质或属性的词便称作谓词这是一元(目目)谓词，以谓词，以P(x)，Q(x)，表示表示o多元谓词多元谓词o在一个命题里，如果主词多于一个，那么表示这几个在一个命题里，如果主词多于一个，那么表示这几个主词间的关系的词称作谓词这是多元谓词，以主词间的关系的词称作谓词这是多元谓词，以P(x,y)，Q(x,y)，R(x,y,z),表示表示o举例举例o“张三张三(zhn sn)和李四是表兄弟和李四是表兄弟”其中其中“是表兄弟是表兄弟”是谓词是谓词o“5大于大于3”其中其中“大于大于”是谓词是谓词o“张三张三(zhn sn)比李四高比李四高”其中其中“比比高高”是谓词是谓词o“天津位于北京的东南天津位于北京的东南”其中其中“位于位于东南东南”是谓词是谓词o“A在在B上上”其中其中“在在上上”是谓词是谓词谓词谓词(wi c)描述性定义描述性定义第五页，共56页4.1.2 个体个体(gt)词词 o个体词个体词(主词主词)o个体词是一个命题里表示思维对象的词个体词是一个命题里表示思维对象的词oP(张三张三)中的张三是个体词或称个体常项中的张三是个体词或称个体常项o谓词谓词P(x)中的变量中的变量x为个体变项或个体变元为个体变项或个体变元on项项(目、元目、元)谓词谓词o有有n个个体的谓词个个体的谓词P(x，xn)称称n项项(目、元目、元)谓词谓词o如果如果P是已赋有确定含义的谓词，就称为谓词常项是已赋有确定含义的谓词，就称为谓词常项o如果如果P表示任一谓词时，就称为谓词变项表示任一谓词时，就称为谓词变项o个体域个体域o将个体变项的变化范围称为个体域或论域，以将个体变项的变化范围称为个体域或论域，以D表示表示o论域是重要的概念，同一谓词在不同论域下的描述形式可能不论域是重要的概念，同一谓词在不同论域下的描述形式可能不同，所取的真假值也可能不同同，所取的真假值也可能不同o约定约定o谓词逻辑谓词逻辑(lu j)的个体域除明确指明外，都认为是包括一切的个体域除明确指明外，都认为是包括一切事物的一个最广的集合事物的一个最广的集合o谓词变项的变化范围，不做特别声明时，指一切关系或一切性谓词变项的变化范围，不做特别声明时，指一切关系或一切性质的集合质的集合第六页，共56页。
4.1.3 谓词谓词(wi c)的定义的定义 o谓词视作为谓词视作为(zuwi)一个个体的性质或多个个体间的关系一个个体的性质或多个个体间的关系进一步抽象地定义，谓词是给定的个体域到集合进一步抽象地定义，谓词是给定的个体域到集合T，F上的一个映射上的一个映射o举例举例o如如P(x)其中其中x D，而，而P(x)的取值为的取值为T或或Fo又如又如“房子是黄色的房子是黄色的”可由谓词可由谓词 YELLOW(HOUSE)表示表示.当当HOUSE取值为房子又是黄色的，该命题方为真取值为房子又是黄色的，该命题方为真o借助于谓词的抽象定义，也可用二元谓词借助于谓词的抽象定义，也可用二元谓词 VALUE(COLOR,HOUSE)来描述这命题来描述这命题.VALUE就是个体到就是个体到T,F的映射，不一定有什么具体含义的映射，不一定有什么具体含义o仅当个体仅当个体COLOR取值为黄色的，取值为黄色的，HOUSE取值为房取值为房子时子时VALUE取值为取值为T第七页，共56页o一般地说谓词一般地说谓词(wi c)P(x),Q(x，y)是命题形式而不是命题形式而不是命题是命题o谓词谓词(wi c)符号符号P,Q的含义没有指定，即它们是谓词的含义没有指定，即它们是谓词(wi c)变项变项o个体词个体词x，y也是个体变项也是个体变项o从而不可能确定从而不可能确定P(x)，Q(x，y)的真值是取真还是取假的真值是取真还是取假o仅当谓词仅当谓词(wi c)变项取定为某个谓词变项取定为某个谓词(wi c)常项，常项，并且个体词取定为个体常项时，命题形式才化为命题并且个体词取定为个体常项时，命题形式才化为命题oP(x)表示表示x是有理数，那么是有理数，那么P(3)是命题，真值为是命题，真值为ToQ(x，y)表示表示x大于大于y，那么，那么Q(2，3)是命题，取值为是命题，取值为Fo谓词谓词(wi c)的真值依赖于个体变元的论域的真值依赖于个体变元的论域说明说明(shumng)(shumng)第八页，共56页。
4.1.4 谓词谓词(wi c)逻辑与命题逻逻辑与命题逻辑辑o可认为谓词逻辑是命题逻辑的推广，命题逻辑是谓词逻可认为谓词逻辑是命题逻辑的推广，命题逻辑是谓词逻辑的特殊情形辑的特殊情形o因为任一命题都可通过引入具有相应含义的谓词因为任一命题都可通过引入具有相应含义的谓词(个体个体词视为常项词视为常项)来表示来表示o或认为一个命题是没有个体变元的零元谓词或认为一个命题是没有个体变元的零元谓词o命题逻辑中的很多概念、规则都可推广到谓词逻辑中延命题逻辑中的很多概念、规则都可推广到谓词逻辑中延用用o如联结词可照搬到谓词逻辑，无需再做说明如联结词可照搬到谓词逻辑，无需再做说明o有的等值式推理式也可移植到谓词逻辑有的等值式推理式也可移植到谓词逻辑o然而谓词逻辑里出现了个体变元，谓词、量词等概念，然而谓词逻辑里出现了个体变元，谓词、量词等概念，特别是个体论域常是无限域，加大了处理难度特别是个体论域常是无限域，加大了处理难度o最简单又深刻的例子最简单又深刻的例子o在命题逻辑里一个公式不难判定它是否是重言式，在命题逻辑里一个公式不难判定它是否是重言式，真值表法是能行的方法然而在谓词逻辑里就没有一般真值表法是能行的方法然而在谓词逻辑里就没有一般的能行算法的能行算法(sun f)(sun f)来判定任一公式是不是普遍有效来判定任一公式是不是普遍有效的的(或称定理、永真式或称定理、永真式)第九页，共56页。
4.2 函数函数(hnsh)和量词和量词4.2.1 函数函数(hnsh)o在谓词逻辑中出现变量，自然也会考虑引入函数在谓词逻辑中出现变量，自然也会考虑引入函数o函数是某个体域函数是某个体域(不必是实数不必是实数)到另一个体域的映射到另一个体域的映射o不同于谓词：将个体映射为真假值不同于谓词：将个体映射为真假值o函数并不单独使用函数并不单独使用(shyng)，是嵌入在谓词中，是嵌入在谓词中o举例举例o函数函数father(x)表示表示x的父亲，若的父亲，若P(x)表示表示x是教师，则是教师，则P(father(x)就表示就表示x的父亲是教师的父亲是教师o当当x的取值确定后，的取值确定后，P(father(x)的值或为真或为假的值或为真或为假o又如又如“张三的父亲和李四的哥哥是同事张三的父亲和李四的哥哥是同事”可描述成可描述成COLLEAGUE(father(张三张三),brother(李四李四)o其中谓词其中谓词COLLEAGUE(x，y)表示表示x和和y是同事，而是同事，而father(x),brother(x)是函数是函数o约定函数符号用小写字母表示，如约定函数符号用小写字母表示，如f，g，father，第十页，共56页。
4.2.2 量词量词(lingc)o用来表示个体数量的词是量词用来表示个体数量的词是量词o可看作是对个体词所加的限制、约束的词可看作是对个体词所加的限制、约束的词o主要不是对数量一个、二个、三十主要不是对数量一个、二个、三十的具的具体描述，而是讨论两个最通用体描述，而是讨论两个最通用(tngyng)的的数量限制词：一个是数量限制词：一个是“所有的所有的”一个是一个是“至至少有一个少有一个”，分别称为全称量词和存在量词分别称为全称量词和存在量词在某种意义上说，这是一对相对立的词在某种意义上说，这是一对相对立的词第十一页，共56页全称全称(qun chn)量词量词o举例举例“凡事物都是运动的凡事物都是运动的”o这命题中的这命题中的“凡凡”就是表示个体变元数量的词，就是表示个体变元数量的词，“凡凡”的的等义词有等义词有“所有的所有的”、“一切的一切的”、“任一个任一个”、“每一每一个个”这句话的意思是说对任一事物而言，它都是运动的这句话的意思是说对任一事物而言，它都是运动的或对任一或对任一x而言，而言，x是运动的是运动的o由于个体由于个体x的论域是包含一切事物的集合，这句话可形式的论域是包含一切事物的集合，这句话可形式描述为描述为(x)(x是运动的是运动的).若再以若再以P(x)表示表示x是运动的，是运动的，那么还可写成那么还可写成(x)P(x)o符号符号:(x)读作所有的读作所有的x或任一或任一x，一切，一切x而而 就是全称就是全称量词，它所约束的个体是量词，它所约束的个体是xo定义定义:命题命题(x)P(x)当且仅当对论域中的所有当且仅当对论域中的所有x来说，来说，P(x)均为真时方为真这就是全称量词的定义均为真时方为真这就是全称量词的定义o性质性质:(x)P(x)F成立成立,当且仅当有一个当且仅当有一个x0 D,使使P(x0)Fo注意注意(x)(P(x)Q(x)(x)P(x)Q(x).量词的运算量词的运算(yn sun)优先级高于逻辑联结词优先级高于逻辑联结词第十二页，共56页。
存在存在(cnzi)量词量词o举例举例“有的事物是动物有的事物是动物”o这命题中这命题中“有的有的”就是表示个体变元数量的词，就是表示个体变元数量的词，“有的有的”的等义词有的等义词有“存在一个存在一个”、“有一个有一个”、“有些有些”这句这句话的意思是说有一事物，它是动物或有一话的意思是说有一事物，它是动物或有一x，x是动物是动物o可形式描述可形式描述(mio sh)为为(x)Q(x),其中其中Q(x)表示表示x是是动物动物o符号符号:(x)读作至少有一个读作至少有一个x或存在一个或存在一个x或有某些或有某些x而而 就是对个体词起约束作用的存在量词，所约束的变元是就是对个体词起约束作用的存在量词，所约束的变元是xo定义定义:命题命题(x)Q(x)当且仅当在论域中至少有一个当且仅当在论域中至少有一个x0，Q(x0)为真时方为真这就是存在量词的定义为真时方为真这就是存在量词的定义o性质性质:(x)Q(x)F成立成立,当且仅当对所有的当且仅当对所有的x0 D,使使Q(x0)Fo注意注意(x)(P(x)Q(x)(x)P(x)Q(x)第十三页，共56页4.2.3 约束约束(yush)变元和自由变元和自由变元变元o在一个含有量词的命题在一个含有量词的命题(mng t)形式里，区分个体形式里，区分个体词受量词的约束还是不受量词的约束是重要的无论词受量词的约束还是不受量词的约束是重要的无论在定义合式公式以及对个体变元作代入时都需区分这在定义合式公式以及对个体变元作代入时都需区分这两种情形两种情形o若若P(x)表示表示x是有理数，这时的变元是有理数，这时的变元x不受任何量词不受任何量词约束，便称是自由的而约束，便称是自由的而(x)P(x)中的两处出现的中的两处出现的变元变元x都受量词都受量词 的约束，便称作约束变元，受约束的约束，便称作约束变元，受约束的变元也称被量词量化了的变元的变元也称被量词量化了的变元o命题命题(mng t)形式形式(x)P(x)Q(y)中，变元中，变元x是约束是约束的，而变元的，而变元y是自由的是自由的第十四页，共56页。
量词量词(lingc)的辖域的辖域o量词所约束量词所约束(yush)的范围称为量词的辖域如的范围称为量词的辖域如o(x)R(x,y)中，中，R(x,y)是是(x)的辖域的辖域o(x)(y)P(x,y)中，中，P(x,y)是是(y)的辖域的辖域,(y)P(x,y)是是(x)的辖域的辖域o命题形式命题形式P(x),在在P确定为某个谓词常项时确定为某个谓词常项时,如如P(x)表示表示x是自然数是自然数,如何化为命题如何化为命题?o个体变元个体变元x取为个体常项如：取为个体常项如：P(2)=T是命题是命题o将将x量化即(x)P(x)或者或者(x)P(x)都是命题都是命题o(x)P(x)表示论域表示论域D上任一上任一x,x都是自然数都是自然数o(x)P(x)=Fo(x)P(x)表示论域表示论域D上有一上有一x,x是自然数是自然数o(x)P(x)=To考虑命题形式考虑命题形式P(x,y)如何用量化的方法化为命题？如何用量化的方法化为命题？第十五页，共56页变元易名变元易名(y mn)规则规则o变元易名变元易名(y mn)规则规则:o(x)P(x)=(y)P(y)o注：注：(x)(P(x)Q(x,y)(y)(P(y)Q(y,y)o这样理解。
因为在同一论域这样理解因为在同一论域D上，对一切上，对一切x，x具有性质具有性质P，同对一切，同对一切y，y具有性质具有性质P，除变，除变元元x和和y的区别外并无差异，从而的区别外并无差异，从而(x)P(x)和和(y)P(y)真值相同真值相同第十六页，共56页4.3 合式公式合式公式o目的目的o像命题逻辑一样像命题逻辑一样(yyng)，需限定所讨论的命题形式的，需限定所讨论的命题形式的范围范围o由于谓词逻辑里引入了个体词、量词，从而带来了复杂由于谓词逻辑里引入了个体词、量词，从而带来了复杂性性o关注一阶谓词逻辑，而不是高阶谓词逻辑关注一阶谓词逻辑，而不是高阶谓词逻辑o限定在量词仅作用于个体变元限定在量词仅作用于个体变元o不允许量词作用于命题变项和谓词变项不允许量词作用于命题变项和谓词变项o也不讨论谓词的谓词也不讨论谓词的谓词o例如：不考虑下述公式例如：不考虑下述公式o (p)(Q(x)p)，量词作用于命题，量词作用于命题po(Q)(x)(Q(x)P(x)，量词作用于谓词，量词作用于谓词Q(x)o P(x,Q(y)，谓词的谓词，谓词的谓词第十七页，共56页符号符号(fho)约定约定o命题变项：命题变项：p,q,r,o个体变项：个体变项：x,y,z,o个体常项：个体常项：a,b,c,或者大写英文单词或者大写英文单词o谓词变项：谓词变项：P,Q,R,o谓词常项：大写英文字母谓词常项：大写英文字母,如如GREATo函数：函数：f,g,或者小写英文单词或者小写英文单词o五个联结词：五个联结词：,o两个两个(lin )量词：量词：,o小括号：小括号：(,)第十八页，共56页。
合式公式定义合式公式定义(dngy)1.命题常项、命题变项和原子谓词公式命题常项、命题变项和原子谓词公式(不含联结词的不含联结词的谓词谓词)都是合式公式都是合式公式2.如果如果A是合式公式，则是合式公式，则A也是合式公式也是合式公式3.如果如果A,B是合式公式，而无变元是合式公式，而无变元x在在A,B的一个中的一个中是约束的而在另一个中是自由的是约束的而在另一个中是自由的,则则(AB),(AB),(AB),(A B)也是合式公式也是合式公式(最外层括最外层括号可省略号可省略(shngl)4.如果如果A是合式公式，而是合式公式，而x在在A中是自由变元，则中是自由变元，则(x)A,(x)A也是合式公式也是合式公式5.只有适合以上只有适合以上4条的才是合式公式条的才是合式公式第十九页，共56页判断判断(pndun)一个公式是否为合式公一个公式是否为合式公式式o合式公式合式公式o p,P(x,y)Q(x,y),o(x)(A(x)B(x),o(x)(A(x)(y)B(x,y)o非合式公式非合式公式o(x)F(x)G(x),违反违反(wifn)第第3条条o(x)(x)F(x),违反违反(wifn)第第4条条o(x)P(y),违反违反(wifn)第第4条条第二十页，共56页。
作业作业(zuy)一一oP661(1,4,6,8)2(3)3(3)4(2)第二十一页，共56页4.4 自然自然(zrn)语句的形式化语句的形式化o使用计算机来处理由自然语句或非形式化陈述的问题，首使用计算机来处理由自然语句或非形式化陈述的问题，首要的工作是问题本身的形式描述要的工作是问题本身的形式描述o命题逻辑表达问题能力，仅限于联结词的使用而谓词逻命题逻辑表达问题能力，仅限于联结词的使用而谓词逻辑由于变元、谓词、量词和函数的引入具有强得多的表达辑由于变元、谓词、量词和函数的引入具有强得多的表达问题能力，已成为描述计算机所处理知识的有力工具，问题能力，已成为描述计算机所处理知识的有力工具，AI将谓词逻辑看作是一种基本的知识表示方法将谓词逻辑看作是一种基本的知识表示方法(fngf)和推理方法和推理方法(fngf)o使用谓词逻辑描述以自然语句表达的问题，首先要将问题使用谓词逻辑描述以自然语句表达的问题，首先要将问题分解成一些原子谓词，引入谓词符号，进而使用量词、函分解成一些原子谓词，引入谓词符号，进而使用量词、函数、联结词来构成合式公式数、联结词来构成合式公式第二十二页，共56页4.4.1“所有所有(suyu)的有理数都是实数的有理数都是实数”的的形式化形式化o所有的有理数都是实数，其意思是说，对任一事物而所有的有理数都是实数，其意思是说，对任一事物而言，如果它是有理数，那么它是实数即对任一言，如果它是有理数，那么它是实数即对任一x而而言，如果言，如果x是有理数，那么是有理数，那么x是实数是实数o若以若以P(x)表示表示x是有理数，是有理数，Q(x)表示表示x是实数，这是实数，这句话的形式描述应为句话的形式描述应为o(x)(P(x)Q(x)o因为因为x的论域是一切的论域是一切(yqi)事物的集合，所以事物的集合，所以x是有是有理数是一个条件理数是一个条件第二十三页，共56页。
形式化形式化o注意注意:这句话不能形式化为这句话不能形式化为o(x)(P(x)Q(x)o这公式的意思是说，对所有的这公式的意思是说，对所有的x，x是有理数而且是有理数而且又是实数又是实数o“所有的所有的都是都是”，这类语句，这类语句(yj)的形式描的形式描述只能使用述只能使用而不能使用而不能使用o当当P(x)与与Q(x)为此例中的谓词常项时，为此例中的谓词常项时，(x)(P(x)Q(x)的真值与论域无关的真值与论域无关第二十四页，共56页形式化形式化o所有的有理数都是实数，这句话按通常的认识肯定是成立的，所有的有理数都是实数，这句话按通常的认识肯定是成立的，取值为真，而且其真值与论域是无关的取值为真，而且其真值与论域是无关的o用用(x)(P(x)Q(x)来描述这句话是对的来描述这句话是对的o设论域设论域D1含有有理数也含有非有理数，例如含有有理数也含有非有理数，例如(lr)D1=1/2,张三张三,桌子桌子,因为对所有的因为对所有的x D1都有都有P(x)Q(x)=T,从而从而(x)(P(x)Q(x)=To如果如果D1只含有理数或不含任一个有理数，仍有只含有理数或不含任一个有理数，仍有(x)(P(x)Q(x)=To因此使用因此使用来描述来描述“所有的所有的都是都是”是符合常规理解的是符合常规理解的o以以(x)(P(x)Q(x)来描述是不可行的来描述是不可行的o因为仅当因为仅当D1中只含有理数时，中只含有理数时，(x)(P(x)Q(x)才为真即才为真即(x)(P(x)Q(x)的取值与论域是有关的，的取值与论域是有关的，“所有的有理数都所有的有理数都是实数是实数”，这句话有时对，这句话有时对,有时不对有时不对第二十五页，共56页。
4.4.2“有的实数有的实数(shsh)是有理数是有理数”的形式化的形式化o这句话的意思是说，存在一事物它是实数，而且是有这句话的意思是说，存在一事物它是实数，而且是有理数即有一个理数即有一个x，x是实数并且是有理数是实数并且是有理数o以以P(x)表示表示x是有理数，是有理数，Q(x)表示表示x是实数，这句是实数，这句话的形式描述话的形式描述(mio sh)应为应为o(x)(P(x)Q(x)o需注意的是不能使用需注意的是不能使用(x)(P(x)Q(x)o其真值与论域有关其真值与论域有关第二十六页，共56页o“有的有的是是”这类语句，按人们通常的认识，它的取这类语句，按人们通常的认识，它的取值是真是假应与个体域有关值是真是假应与个体域有关(yugun)o用用(x)(P(x)Q(x)描述是对的描述是对的o设论域设论域D1中没有有理数，如中没有有理数，如D1=e，张三，桌子，张三，桌子，则在则在D1上不存在是有理数的实数，故在上不存在是有理数的实数，故在D1上这句话真值应上这句话真值应为假，也确为假为假，也确为假o仅当仅当D1中有有理数时方为真中有有理数时方为真o若以若以(x)(Q(x)P(x)来描述，就不符合人们的常规理解了来描述，就不符合人们的常规理解了因为凡在不含实数的论域上都有因为凡在不含实数的论域上都有o(x)(Q(x)P(x)=To这是不对的这是不对的形式化形式化第二十七页，共56页。
4.4.3“没有没有(mi yu)无理数是有理数无理数是有理数”的形的形式化式化o这句话有否定词，意思是对任一这句话有否定词，意思是对任一x而言，如果而言，如果x是无理数，是无理数，那么那么x不是有理数不是有理数o若以若以A(x)表示表示x是无理数，是无理数，B(x)表示表示x是有理数，这句是有理数，这句话的形式描述为话的形式描述为o(x)(A(x)B(x)o也可以也可以(ky)逻辑上等价的逻辑上等价的o(x)(A(x)B(x)o(x)(B(x)A(x)第二十八页，共56页4.4.4“有的实数有的实数(shsh)不是有理数不是有理数”的形的形式化式化o这句话的意思是有的这句话的意思是有的x，它是实数而且不是有理数，它是实数而且不是有理数o若以若以A(x)表示表示x是实数，是实数，B(x)表示表示x是有理数，那么是有理数，那么(n me)这句话可形式描述为这句话可形式描述为o(x)(A(x)B(x)第二十九页，共56页4.4.5 自然数集的形式自然数集的形式(xngsh)描述描述o论域是自然数集，来形式化语句论域是自然数集，来形式化语句o(1)对每个数，有且仅有一个相继后元对每个数，有且仅有一个相继后元o(2)没有这样的数，没有这样的数，0是其相继后元是其相继后元o(3)对除对除0而外的数，有且仅有一个相继前元而外的数，有且仅有一个相继前元o(可将这三句话作为建立自然数集合的公理可将这三句话作为建立自然数集合的公理)o引入谓词引入谓词E(x,y)表示表示xy，函数，函数f(x)表示个体表示个体x的相的相继后元，即继后元，即f(x)=x+1函数函数g(x)表示个体表示个体x的相继的相继前元，即前元，即g(x)x-1o对语句对语句1需注意唯一性的描述，常用的办法需注意唯一性的描述，常用的办法(bnf)是是如果有两个则它们必相等，即若对每个如果有两个则它们必相等，即若对每个x都存在都存在y，y是是x的相继后元，且对任一的相继后元，且对任一Z，如果它也是，如果它也是x的相继后元，的相继后元，那么那么y,z必相等必相等第三十页，共56页。
形式化形式化o于是对语句于是对语句1存在唯一性的描述为存在唯一性的描述为o对语句对语句3需注意的是对需注意的是对“除除0而外而外”的描述，可理解的描述，可理解为如果为如果x0则则的形式的形式(xngsh)，于是语句，于是语句3可描述为可描述为o语句语句2的描述是简单的，可写成的描述是简单的，可写成第三十一页，共56页4.4.6“至少至少(zhsho)有一偶数是素数有一偶数是素数”与与 “至少至少(zhsho)有一偶数并且至少有一偶数并且至少(zhsho)有一素数有一素数”的形式化的形式化o需注意两者的区别，分别形式描述为需注意两者的区别，分别形式描述为o这两个逻辑公式并不等值这两个逻辑公式并不等值o注：注：D=3,4o同样，同样，“一切事物它或是生物或是非生物一切事物它或是生物或是非生物”与与“或者或者(huzh)一切事物都是生物，或者一切事物都是生物，或者(huzh)一切事物一切事物都是非生物都是非生物”的形式化也是不同的，可分别形式描述的形式化也是不同的，可分别形式描述为为o这两个逻辑公式也不等值这两个逻辑公式也不等值第三十二页，共56页形式化形式化o再有再有“一切素数都是奇数一切素数都是奇数”与与“若一切事物都是素若一切事物都是素数，那么数，那么(n me)一切事物都是奇数一切事物都是奇数”的形式化的形式化分别是分别是o两者也不等值两者也不等值o注：注：D=2,4第三十三页，共56页。
4.4.7 积木世界的形式积木世界的形式(xngsh)描描述述如图所示三块积木如图所示三块积木(jm)A，B，C放在桌子上放在桌子上第三十四页，共56页形式化形式化相对位置可如下描述：相对位置可如下描述：ON(C,A)表示表示C在在A上上.ON(A,TABLE)表示表示A在桌子上在桌子上.ON(B,TABLE)表示表示B在桌子上在桌子上.CLEAR(C)表示表示C上无积木块上无积木块.CLEAR(B)表示表示B上无积木块上无积木块.表示，对任一表示，对任一x，如果，如果(rgu)x上无积木，那么没有上无积木，那么没有y在在x上，这表上，这表明了谓词明了谓词CLEAR,ON的关系的关系第三十五页，共56页4.4.8 一段话的形式一段话的形式(xngsh)描述描述o“张三在计算机系工作，李四是计算机系的领导人员张三在计算机系工作，李四是计算机系的领导人员如果如果y在计算机系工作，而在计算机系工作，而z是计算机系的领导，那么是计算机系的领导，那么z是是y的上级的上级(shngj)”这段话的形式描述为这段话的形式描述为oWORKS-IN(计算机系，张三计算机系，张三)oMANAGER(计算机系，李四计算机系，李四)第三十六页，共56页。
4.4.9“函数函数f(x)在在a,b上的点上的点x0处连续处连续(linx)”的形式描述的形式描述注：注：“函数函数f(x)在在a,b上的点上的点x0处连续处连续”的定义的定义(dngy)设设f(x)在某邻域在某邻域N(x0,)内有定义内有定义(dngy)，若对任一，若对任一0存在存在0使得当使得当|x-x0|时有时有|f(x)-f(x0)|，则，则称函数称函数f(x)在点在点x0处连续处连续第三十七页，共56页4.4.10 对谓词变元多次量化的分析对谓词变元多次量化的分析(fnx)o设设P(x，y)是二元谓词，对两个变元的量化可得是二元谓词，对两个变元的量化可得4种形式种形式o显然显然,x和和 y可交换可交换,有有o注意：注意：x和和 y不可交换且不可交换且y是是x的函数的函数,或者说或者说y依赖依赖于于xo如如P(x，y)表表x+y0，论域，论域D1为实数这时：为实数这时：o 对对x1D1，有，有y1D1 使使x1+y1=0o 对对x2D1，有，有y2D1 使使x2+y20o 从而从而(cng r)(x)(y)P(x,y)T，这里对，这里对x1有有y1，对，对x2有有y2，并不要求，并不要求y1=y2=第三十八页，共56页。
形式化形式化(3)显然这与显然这与(y)(x)P(x,y)是不同是不同(b tn)的的如如P(x，y)表示表示xy0，论域为实数取，论域为实数取x0时，对时，对所有的所有的y均有均有xy=0成立，从而有成立，从而有(x)(y)P(x，y)T所以所以x和和y不可交换不可交换(4)显然显然x和和y可交换，有可交换，有第三十九页，共56页自然语言形式化小结自然语言形式化小结(xioji)o对更多个量词的情形可同样分析对更多个量词的情形可同样分析o这一节介绍了一些具体语句的形式化，都具有一般这一节介绍了一些具体语句的形式化，都具有一般性，特别是对性，特别是对“所有的所有的都是都是”，“有的有的是是”的形式描述是最基本的格式的形式描述是最基本的格式(g shi)o通过这些例子，也可看出谓词逻辑的广泛的表达能通过这些例子，也可看出谓词逻辑的广泛的表达能力力第四十页，共56页4.5 有限有限(yuxin)域下公式域下公式(x)P(x),(x)P(x)的表的表示法示法o我们曾约定个体变元的论域是包含一切事物的集合，由我们曾约定个体变元的论域是包含一切事物的集合，由于论域的无限性，给公式真值的讨论带来了复杂性于论域的无限性，给公式真值的讨论带来了复杂性o现将论域限定为有限集，为方便又不失一般性，用现将论域限定为有限集，为方便又不失一般性，用1，2，k来代表来代表(dibio)，这时来重新认识一下全，这时来重新认识一下全称量词和存在量词称量词和存在量词第四十一页，共56页。
4.5.1 论域为有限论域为有限(yuxin)域时的公式域时的公式表示法表示法按定义，(x)P(x)就是(jish)一切x都具有性质P，或说对一切x，P(x)都成立论域D11，2，k时，就是(jish)说P(1)，P(2)，P(k)都成立，自然有 即，全称量词乃是合取词的推广有限域下，(x)P(x)就化成了由合取词描述的命题逻辑的公式在任意域下，全称量词的作用“相当于”无限个合取词的作用同样，存在量词乃是析取词V的推广有限域下，(x)P(x)就化成了由析取词描述的命题逻辑的公式在任意域下，存在量词的作用“相当于”无限个析取词的作用第四十二页，共56页公式公式(gngsh)表示法表示法o严格严格(yng)地说，在无穷集地说，在无穷集1，2，k，上上o都是没有定义的，不是合式公式都是没有定义的，不是合式公式o一般地说，谓词逻辑的公式不能转换为命题逻辑公式一般地说，谓词逻辑的公式不能转换为命题逻辑公式第四十三页，共56页4.5.2 在域在域1，2上多次量化公式上多次量化公式(gngsh)对有的谓词公式难于理解(lji)时，可在有限域1，2上转换成命题逻辑公式做些分析，常会帮助理解(lji)注意上式右侧含意注意上式右侧含意(hn y)：x是是y的函数的函数第四十四页，共56页。
4.5.3 域域1，2上谓词上谓词(wi c)公公式的解释式的解释o谓词逻辑里公式的一个解释，比命题逻辑要谓词逻辑里公式的一个解释，比命题逻辑要复杂得多复杂得多o在已知的论域下，需对公式中所含的命题变在已知的论域下，需对公式中所含的命题变项、自由个体变项、谓词变项以及函数给出项、自由个体变项、谓词变项以及函数给出一个具体的设定才构成一个具体的设定才构成(guchng)该公式的该公式的一个解释一个解释I，在，在I下该公式有确定的真值下下该公式有确定的真值下面在论域面在论域1，2上讨论上讨论第四十五页，共56页对公式对公式(x)P(x)的一个的一个(y )解解释释在该解释下在该解释下(x)P(x)=Fx)P(x)=F特点特点(tdin):(tdin):设定谓词设定谓词变项变项第四十六页，共56页对公式对公式(gngsh)(x)(y)P(x,y)的一个解释的一个解释在这解释下，在这解释下，(x)(y)P(x,y)=T特点：设定特点：设定(sh dn)谓词变项谓词变项第四十七页，共56页对公式对公式(gngsh)的的(x)(P(x)Q(f(x),a)=T一个解一个解释释o在这解释下在这解释下,(x)(P(x)Q(f(x),a)=To因为因为o特点：设定特点：设定(sh dn)谓词变项、函数、自由个体谓词变项、函数、自由个体变项变项第四十八页，共56页。
说明说明(shumng)o不难看出，在一般的论域不难看出，在一般的论域D上，一个谓词公式上，一个谓词公式解释的个数是无限的，而且每个解释本身需设解释的个数是无限的，而且每个解释本身需设定的内容也可理解定的内容也可理解(lji)为是无限的，包括为是无限的，包括对对P(1)，P(2)，f(1)，f(2)，的设的设定定第四十九页，共56页4.6 公式公式(gngsh)的普遍有效性和判定的普遍有效性和判定问题问题o谓词逻辑公式也可分为三类，一是普遍有效公式、谓词逻辑公式也可分为三类，一是普遍有效公式、一是可满足公式、一是不可满足公式，它们的定义一是可满足公式、一是不可满足公式，它们的定义依赖于谓词公式的解释依赖于谓词公式的解释o在论域确定之后，一个谓词公式的解释，包括对谓在论域确定之后，一个谓词公式的解释，包括对谓词变项、命题变项、函数和自由个体的具体词变项、命题变项、函数和自由个体的具体(jt)设定设定o判别一个公式的普遍有效性问题就是判定问题判别一个公式的普遍有效性问题就是判定问题第五十页，共56页4.6.1 普遍普遍(pbin)有效的公式有效的公式o对一个谓词公式来说，如果对一个谓词公式来说，如果(rgu)在它的任一解释在它的任一解释I下真值都为真，便称作普遍有效的下真值都为真，便称作普遍有效的第五十一页，共56页。
可满足可满足(mnz)和不可满足和不可满足(mnz)o对一个谓词公式来说，如果在它的某个解释对一个谓词公式来说，如果在它的某个解释I下下真值为真，便称作可满足的真值为真，便称作可满足的o对一个谓词公式来说，如果在它的任一解释对一个谓词公式来说，如果在它的任一解释I下下真值均为假，便称作不可满足的真值均为假，便称作不可满足的o若一个公式是普遍有效若一个公式是普遍有效(yuxio)的，那么这公的，那么这公式的否定就是不可满足的，反过来也成立式的否定就是不可满足的，反过来也成立第五十二页，共56页有限域上公式普遍有效性的几个有限域上公式普遍有效性的几个(j )结论结论o有限域上一个公式的可满足性和普遍有效有限域上一个公式的可满足性和普遍有效(yuxio)性依赖于个体域个体的个数且仅依赖于性依赖于个体域个体的个数且仅依赖于个体域个体的数目个体域个体的数目o即在某个含即在某个含k个元素的个元素的k个体域上普遍有效个体域上普遍有效(yuxio)(或可满足或可满足)，则在任一，则在任一k个体域上也普遍个体域上也普遍有效有效(yuxio)(或可满足或可满足)o如果某公式在如果某公式在k个体域上普遍有效个体域上普遍有效(yuxio)，则在，则在k-1个体域上也普遍有效个体域上也普遍有效(yuxio)o如果某公式在如果某公式在k个体域上可满足，则在个体域上可满足，则在k+1个体域个体域上也可满足上也可满足第五十三页，共56页。
4.6.2 判定判定(pndng)问题问题o谓词逻辑的判定问题，指的是任一公式的普遍有效性谓词逻辑的判定问题，指的是任一公式的普遍有效性o若说谓词逻辑是可判定的，就要求给出一个能行的方法，使得若说谓词逻辑是可判定的，就要求给出一个能行的方法，使得对任一谓词公式都能判断是否是普遍有效的对任一谓词公式都能判断是否是普遍有效的o所谓能行的方法乃是一个机械方法，可一步一步做下去，并在所谓能行的方法乃是一个机械方法，可一步一步做下去，并在有穷步内实现判断有穷步内实现判断o一般地说，像数学定理的证明不是能行的，因为没有一个机械一般地说，像数学定理的证明不是能行的，因为没有一个机械方法实现对任一数学定理的证明，而是针对不同问题靠人的智方法实现对任一数学定理的证明，而是针对不同问题靠人的智慧技巧去解决慧技巧去解决o当然像线性方程组的求解，是有能行方法的当然像线性方程组的求解，是有能行方法的o能行可判定问题关系着找出能行的方法，从而推进有关方法的能行可判定问题关系着找出能行的方法，从而推进有关方法的研究研究o普遍有效性的判定，关系着推理形式的正确与否，关系着公理普遍有效性的判定，关系着推理形式的正确与否，关系着公理系统的一致性等，所以是个重要系统的一致性等，所以是个重要(zhngyo)课题课题第五十四页，共56页。
1.谓词逻辑是不可判定的对任一谓词公式而言，没有能谓词逻辑是不可判定的对任一谓词公式而言，没有能行方法判明它是否是普遍有效的行方法判明它是否是普遍有效的2.然而这并不排除谓词公式有子类是可判定的像命题逻然而这并不排除谓词公式有子类是可判定的像命题逻辑就可用真值表法判明任一命题公式的永真性辑就可用真值表法判明任一命题公式的永真性3.判定问题的困难在于个体域是个无穷集以及对谓词设定判定问题的困难在于个体域是个无穷集以及对谓词设定(sh dn)的任意性的任意性4.只含有一元谓词变项的公式是可判定的只含有一元谓词变项的公式是可判定的5.(x1)(xn)P(x1,xn)和和(x1)(xn)P(x1,xn)型公式，若型公式，若P中无量词和其他自由变项时也是中无量词和其他自由变项时也是可判定的可判定的6.个体域有穷时的谓词公式是可判定的个体域有穷时的谓词公式是可判定的谓词逻辑判定谓词逻辑判定(pndng)问题的几个结问题的几个结论论第五十五页，共56页作业作业(zuy)二二oP665(2,4,8,10)7(10)8(2,4,6)10(1,7)第五十六页，共56页。
