在命题逻辑中 是把简单命题作为基本单元或说作为原子来ppt课件.ppt

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