《离散数学chapter04-2013》由会员分享，可在线阅读，更多相关《离散数学chapter04-2013（56页珍藏版）》请在金锄头文库上搜索。
1、在命题逻辑中，是把简单命题作为基本单元或 说作为原子来看待的，不再对简单命题的内部 结构进行分析在命题逻辑中，是把简单命题作为基本单元或 说作为原子来看待的，不再对简单命题的内部 结构进行分析如如, 命题：命题：“squr(2)是无理数是无理数”和和“ squr(3)是无理数是无理数”是作为 两个独立的命题看待的是作为 两个独立的命题看待的, 不考虑命题间的联系不考虑命题间的联系事实上这两个命题仍可作分解，它们都有主词和谓词。这样 的细分带来的好处是可将这两个有相同谓词事实上这两个命题仍可作分解，它们都有主词和谓词。这样 的细分带来的好处是可将这两个有相同谓词(“是无理数是无理数”)的 命题联
2、系起来的 命题联系起来第四章 谓词逻辑的基本概念第四章 谓词逻辑的基本概念命题逻辑的局限性命题逻辑的局限性举例：凡有理数都是实数，举例：凡有理数都是实数，2/7是有理数，所以是有理数，所以2/7是实数是实数直观上看这样的推理应该是正确的。然而在命题逻辑里就不能描述这 种推理直观上看这样的推理应该是正确的。然而在命题逻辑里就不能描述这 种推理 设这三个命题分别以设这三个命题分别以p, q, r表示，相应的推理形式为：表示，相应的推理形式为：(p q) r。由于对任意的。由于对任意的p，q，r来说这推理形式并非重言式，也就是说这 个推理形式不是正确的来说这推理形式并非重言式，也就是说这 个推理形式
3、不是正确的 对这样的人们熟知的推理关系在命题逻辑中得不到正确的描述，自然 是命题逻辑的局限性对这样的人们熟知的推理关系在命题逻辑中得不到正确的描述，自然 是命题逻辑的局限性 要认识这种推理规律，只有对简单命题做进一步剖析。这就需要 引入要认识这种推理规律，只有对简单命题做进一步剖析。这就需要 引入谓词谓词、变量变量以及表示变量数量的以及表示变量数量的量词量词(全称量词和存在量词， 分别表示一般的和个别的情况全称量词和存在量词， 分别表示一般的和个别的情况) ，进而研究它们的形式结构和逻 辑关系，这便构成了谓词逻辑，进而研究它们的形式结构和逻 辑关系，这便构成了谓词逻辑约定约定小写字母表示命题
4、大写字母表示谓词小写字母表示命题 大写字母表示谓词内容仅限于一阶谓词逻辑或称狭谓词逻辑内容仅限于一阶谓词逻辑或称狭谓词逻辑说明说明4.1 谓词和个体词谓词和个体词 4.1.1 谓词谓词例 张三是学生李四是学生例 张三是学生李四是学生在命题逻辑里，这是两个不同的命题，只能分别以两个不同的 符号如在命题逻辑里，这是两个不同的命题，只能分别以两个不同的 符号如p，q表示表示然而这两个命题的共同点是，它们都有主词和谓词然而这两个命题的共同点是，它们都有主词和谓词主词主词“张三张三”、“李四李四”是不同的，而谓词是不同的，而谓词“是学生是学生”是相同的是相同的现在强调它们的共同点若以大写符号现在强调它们
5、的共同点若以大写符号P表示表示“是学生是学生”，这样 两个命题的共同性可由，这样 两个命题的共同性可由P来体现了，但主词还需区别开来，便 可把这两个命题分别写成来体现了，但主词还需区别开来，便 可把这两个命题分别写成P(张三张三) 和和P(李四李四)明显地描述了这两个命题的共同点和不同点明显地描述了这两个命题的共同点和不同点一般地可引入变量一般地可引入变量x来表示主词，于是符号来表示主词，于是符号P(x)就表示就表示“x是学 生是学 生”通常把通常把P(x)称作谓词称作谓词一元谓词一元谓词 在一个命题里，如果主词只有一个，这时表示该主词性质或 属性的词便称作谓词这是一元在一个命题里，如果主词只
6、有一个，这时表示该主词性质或 属性的词便称作谓词这是一元(目目)谓词，以谓词，以P(x)， Q(x)，表示表示多元谓词多元谓词 在一个命题里，如果主词多于一个，那么表示这几个主词间 的关系的词称作谓词这是多元谓词，以在一个命题里，如果主词多于一个，那么表示这几个主词间 的关系的词称作谓词这是多元谓词，以P(x, y)，Q(x, y)， R(x, y, z), 表示表示举例举例 “张三和李四是表兄弟张三和李四是表兄弟”其中其中“是表兄弟是表兄弟”是谓词是谓词 “5大于大于3”其中其中“大于大于”是谓词是谓词 “张三比李四高张三比李四高”其中其中“比比高高”是谓词是谓词 “天津位于北京的东南天津位
7、于北京的东南”其中其中“位于位于东南东南”是谓词是谓词 “A在在B上上”其中其中“在在上上”是谓词是谓词谓词描述性定义谓词描述性定义4.1.2 个体词个体词个体词个体词(主词主词)个体词是一个命题里表示思维对象的词个体词是一个命题里表示思维对象的词P(张三张三)中的张三是个体词或称中的张三是个体词或称个体常项个体常项谓词谓词P(x)中的变量中的变量x为为个体变项个体变项或个体变元或个体变元n项项(目、元目、元)谓词谓词有有n个个体的谓词个个体的谓词P(x，xn)称称n项项(目、元目、元)谓词谓词如果如果P是已赋有确定含义的谓词，就称为是已赋有确定含义的谓词，就称为谓词常项谓词常项如果如果P表示
8、任一谓词时，就称为表示任一谓词时，就称为谓词变项谓词变项个体域个体域将个体变项的变化范围称为个体域或论域，以将个体变项的变化范围称为个体域或论域，以D表示表示论域是重要的概念，同一谓词在不同论域下的描述形式可能不同，所取的真假 值也可能不同论域是重要的概念，同一谓词在不同论域下的描述形式可能不同，所取的真假 值也可能不同约定约定谓词逻辑的个体域除明确指明外，都认为是包括一切事物的一个最广的集合谓词逻辑的个体域除明确指明外，都认为是包括一切事物的一个最广的集合谓词变项的变化范围，不做特别声明时，指一切关系或一切性质的集合谓词变项的变化范围，不做特别声明时，指一切关系或一切性质的集合4.1.3 谓
9、词的定义谓词的定义谓词视作为一个个体的性质或多个个体间的关系。进一步 抽象地定义，谓词视作为一个个体的性质或多个个体间的关系。进一步 抽象地定义，谓词是给定的个体域到集合谓词是给定的个体域到集合T，F上的一个 映射上的一个 映射举例举例如如P(x)其中其中x D，而，而P(x)的取值为的取值为T或或F又如又如“房子是黄色的房子是黄色的”可由谓词可由谓词 YELLOW(HOUSE) 表示表示. 当当 HOUSE取值为房子又是黄色的，该命题方为真取值为房子又是黄色的，该命题方为真借助于谓词的抽象定义，也可用二元谓词借助于谓词的抽象定义，也可用二元谓词 VALUE(COLOR, HOUSE) 来描述
10、这命题来描述这命题. VALUE就是个体到就是个体到T, F的映射，不一定 有什么具体含义 仅当个体的映射，不一定 有什么具体含义 仅当个体COLOR取值为黄色的，取值为黄色的，HOUSE取值为房子时取值为房子时VALUE取 值为取 值为T一般地说谓词一般地说谓词P(x), Q(x，y)是是命题形式命题形式而不是而不是命题命题谓词符号谓词符号P, Q的含义没有指定，即它们是的含义没有指定，即它们是谓词变项谓词变项个体词个体词x，y也是也是个体变项个体变项从而不可能确定从而不可能确定P(x)，Q(x，y)的真值是取真还是取假的真值是取真还是取假仅当谓词变项取定为某个仅当谓词变项取定为某个谓词常项
11、谓词常项，并且个体词取定 为，并且个体词取定 为个体常项个体常项时，命题形式才化为命题时，命题形式才化为命题P(x)表示表示x是有理数，那么是有理数，那么P(3)是命题，真值为是命题，真值为TQ(x，y)表示表示x大于大于y，那么，那么Q(2，3)是命题，取值为是命题，取值为F谓词的真值依赖于个体变元的论域谓词的真值依赖于个体变元的论域说明说明4.1.4 谓词逻辑与命题逻辑谓词逻辑与命题逻辑可认为谓词逻辑是命题逻辑的推广，命题逻辑是谓词逻 辑的特殊情形可认为谓词逻辑是命题逻辑的推广，命题逻辑是谓词逻 辑的特殊情形因为任一命题都可通过引入具有相应含义的谓词(个体词视为常 项)来表示因为任一命题都
12、可通过引入具有相应含义的谓词(个体词视为常 项)来表示或认为一个命题是没有个体变元的零元谓词或认为一个命题是没有个体变元的零元谓词命题逻辑中的很多概念、规则都可推广到谓词逻辑中延 用命题逻辑中的很多概念、规则都可推广到谓词逻辑中延 用如联结词可照搬到谓词逻辑，无需再做说明如联结词可照搬到谓词逻辑，无需再做说明有的等值式推理式也可移植到谓词逻辑有的等值式推理式也可移植到谓词逻辑然而谓词逻辑里出现了个体变元，谓词、量词等概念，特别是个 体论域常是无限域，加大了处理难度然而谓词逻辑里出现了个体变元，谓词、量词等概念，特别是个 体论域常是无限域，加大了处理难度最简单又深刻的例子 在命题逻辑里一个公式不
13、难判定它是否是重言式，真值表法是能 行的方法然而在谓词逻辑里就最简单又深刻的例子 在命题逻辑里一个公式不难判定它是否是重言式，真值表法是能 行的方法然而在谓词逻辑里就没有没有一般的能行算法来判定任一 公式是不是普遍有效的(或称定理、永真式)一般的能行算法来判定任一 公式是不是普遍有效的(或称定理、永真式)4.2 函数和量词函数和量词 4.2.1 函数函数在谓词逻辑中出现变量，自然也会考虑引入在谓词逻辑中出现变量，自然也会考虑引入函数函数函数是函数是某个体域某个体域(不必是实数不必是实数)到另一到另一个体域个体域的映射的映射不同于谓词不同于谓词：将个体映射为真假值：将个体映射为真假值函数并不单独
14、使用，是嵌入在谓词中函数并不单独使用，是嵌入在谓词中举例举例函数函数father(x)表示表示x的父亲，若的父亲，若P(x)表示表示x是教师，则是教师，则P(father(x) 就表示就表示x的父亲是教师 当的父亲是教师 当x的取值确定后，的取值确定后，P(father(x)的值或为真或为假的值或为真或为假又如又如“张三的父亲和李四的哥哥是同事张三的父亲和李四的哥哥是同事”可描述成可描述成 COLLEAGUE(father(张三张三), brother(李四李四) 其中谓词其中谓词COLLEAGUE(x，y)表示表示x和和y是同事，而是同事，而father(x), brother(x)是函数是
15、函数约定函数符号用小写字母表示，如约定函数符号用小写字母表示，如f，g，father，4.2.2 量词量词用来表示个体数量的词是用来表示个体数量的词是量词量词可看作是对个体词所加的限制、约束的词可看作是对个体词所加的限制、约束的词主要不是对数量一个、二个、三十主要不是对数量一个、二个、三十的具体描 述，而是讨论两个最通用的数量限制词：一个是的具体描 述，而是讨论两个最通用的数量限制词：一个是 “所有的所有的”一个是一个是“至少有一个至少有一个”，分别称为全称量 词和存在量词。在某种意义上说，这是一对相对 立的词，分别称为全称量 词和存在量词。在某种意义上说，这是一对相对 立的词全称量词全称量词
16、举例举例 “凡事物都是运动的凡事物都是运动的”这命题中的这命题中的“凡凡”就是表示个体变元数量的词，就是表示个体变元数量的词，“凡凡”的等义词有的等义词有“所有的所有的”、 “一切的一切的”、“任一个任一个”、“每一个每一个”这句话的意思是说对任一事物而言， 它都是运动的或对任一这句话的意思是说对任一事物而言， 它都是运动的或对任一x而言，而言，x是运动的是运动的由于个体由于个体x的论域是的论域是包含一切事物的集合包含一切事物的集合，这句话可形式描述为，这句话可形式描述为( x)(x是 运动的是 运动的). 若再以若再以P(x)表示表示x是运动的，那么还可写成是运动的，那么还可写成( x)P(x)符号符号: ( x)读作所有的读作所
