离散数学第二章精.ppt

离散数学第二章第1页，本讲稿共117页用命题逻辑处理苏格拉底三段论：用命题逻辑处理苏格拉底三段论：谓词逻辑谓词逻辑又例又例:张华是大学生张华是大学生,李明也是大学生。李明也是大学生。所有的自然数都等于所有的自然数都等于1.(F);存在着自然数等于存在着自然数等于1.(T)PQR人总是要死的人总是要死的,苏格拉底是人苏格拉底是人,苏格拉底是要死的。苏格拉底是要死的。若论证有效则有若论证有效则有:P QR,即即 P QR 永真永真.第2页，本讲稿共117页谓词逻辑谓词逻辑对对简简单单命命题题作作进进一一步步分分析析,分分离离出出个个体体和和谓谓词词,并并考考虑虑到到泛泛指指和和特特指指 (全全称称和和存存在在),在在此此基基础础上上,研研究究命命题题的的逻逻辑辑结结构构及及命命题题间间的的推推理理关关系系。Predicate Logic第二章第二章第3页，本讲稿共117页-1 1 谓谓 词词 的的 概概 念念 与与 表表 示示-2-2 量词量词-3-3 谓词公式谓词公式-5 5 等价式与重言式等价式与重言式 -7 7 谓谓词词演演算算的的推推理理理理论论2 26 6 前束范式前束范式谓词逻辑谓词逻辑 -4 谓词公式的解释谓词公式的解释第4页，本讲稿共117页命题是具有确定真值的命题是具有确定真值的陈述句陈述句。2-12-1谓词的概念和表示谓词的概念和表示如如 “电子计算机是科学技术的工具电子计算机是科学技术的工具。”个体个体:思维的对象思维的对象,可以是具体的事物或抽象的概念可以是具体的事物或抽象的概念谓词谓词:刻画个体性质或个体之间关系的词。刻画个体性质或个体之间关系的词。1 1.个体和谓词个体和谓词 陈述句由主语和谓语两部分构成，陈述句由主语和谓语两部分构成，主语主语谓语谓语个体个体谓词谓词一元谓词一元谓词:与一个个体相关联的谓词与一个个体相关联的谓词.(描述个体性质描述个体性质)N元谓词元谓词:与与N个个体相关联的谓词个个体相关联的谓词.(描述个体间的关系描述个体间的关系)谓词逻辑谓词逻辑 谓词的概念和表示谓词的概念和表示第5页，本讲稿共117页(a).).他是三好学生。他是三好学生。(b).7(b).7 是质数。是质数。(c).(c).每天作广播操是好习惯。每天作广播操是好习惯。(d).5(d).5 大于大于 3.3.(e).(e).地球绕着太阳转。地球绕着太阳转。一元谓词。一元谓词。谓词刻画个体性质谓词刻画个体性质(f).(f).张明和张亮是兄弟。张明和张亮是兄弟。(e).(e).上海位于南京和杭州之间。上海位于南京和杭州之间。谓词刻谓词刻画个体画个体间关系。间关系。在谓词逻辑中在谓词逻辑中,命题是由一个谓词和若干有序个体组成的。命题是由一个谓词和若干有序个体组成的。谓词逻辑谓词逻辑 谓词的概念和表示谓词的概念和表示二元谓词二元谓词二元谓词二元谓词二元谓词二元谓词三元谓词三元谓词第6页，本讲稿共117页2.2.个体和谓词的表示个体和谓词的表示 命题由一个谓词和若干个体组成命题由一个谓词和若干个体组成谓词逻辑谓词逻辑 谓词的概念和表示谓词的概念和表示用大写字母用大写字母 A,B,C,D,.代表谓词。代表谓词。用小写字母代表个体用小写字母代表个体：用小写字母用小写字母 a,b,c.表示特定个体表示特定个体:个体常元个体常元 用小写字母用小写字母 x,y,z.表示任意个体：表示任意个体：个体变元个体变元.一个一个 n 元谓词记作元谓词记作:A(x1,x2,xn)其中其中 x1,x2,x1,x2,xn,xn 为个体变元为个体变元.当当A(x1,A(x1,xn)xn)中个体变中个体变元用个体常元元用个体常元:a1,:a1,an an 代入后代入后,A(a1A(a1an)an)就成为一个命题。就成为一个命题。则则 A(a)表示命题表示命题:张华是大学生张华是大学生,A(b)表示命题表示命题:李明是大学生李明是大学生。例例:令令 A(x):x 是大学生是大学生;a:张华张华,b:李明李明第7页，本讲稿共117页命题由一个谓词和若干个体组成，但并非任意个体都和任意谓词都命题由一个谓词和若干个体组成，但并非任意个体都和任意谓词都能构成命题。能构成命题。如如 2 是偶数是偶数,(T)个体域个体域:个体的取值范围个体的取值范围,用用D表示表示 如谓词如谓词“.是偶数是偶数”的个体域的个体域 D:全体整数。全体整数。“.是要死的是要死的”D:全体生物全体生物 或或 D:人类人类全总个体域全总个体域:所有个体的集合称之所有个体的集合称之。谓词逻辑谓词逻辑 谓词的概念和表示谓词的概念和表示3 是偶数是偶数,(F)x 是偶数是偶数(不是命题不是命题)当谓词确定后当谓词确定后,其允许的个体取值范围称为其允许的个体取值范围称为个体域个体域。则则 A(a)表示命题表示命题:张华是大学生张华是大学生,A(b)表示命题表示命题:李明是大学生李明是大学生。例例:令令 A(x):x 是大学生是大学生;D:人类人类 a:张华张华,b:李明李明第8页，本讲稿共117页又例又例:上海位于南京和杭州之间。上海位于南京和杭州之间。令令 L(x,y,z):x 位于位于 y 和和 z 之间之间,D:城市城市则命题符号化为则命题符号化为:L(a,b,c)谓词逻辑谓词逻辑 谓词的概念和表示谓词的概念和表示 则则 L(2,3)表示命题表示命题:23.(真真)又例又例:设设 L(x,y):x 小于小于 y,D:实数集合实数集合 则则 L(5,1):表示命题表示命题:5 谓词的概念和表示谓词的概念和表示3.3.复合命题复合命题第10页，本讲稿共117页例如例如:张华的母亲爱张华张华的母亲爱张华.设设 P(x,y):x爱爱y;D:人人;f(x):x的母亲的母亲;a:张华张华命题符号化命题符号化:P(f(a),a)例如例如:2与与3之和小于之和小于2与与3之积之积.设设 P(x,y):x小于小于y;D:整数整数;f(x,y):x与与 y之和之和 g(x,y):x与与 y之积之积;a:2;b:3命题符号化命题符号化:P(f(a,b),g(a,b)或或 P(2+3,23 )自变量和函数值均为个体域中的个体自变量和函数值均为个体域中的个体.用小写字母用小写字母f,g.f,g.表示表示.谓词逻辑谓词逻辑 量词量词4.4.个体函数个体函数例如例如:张华的母亲爱张华张华的母亲爱张华.第11页，本讲稿共117页-1 1 谓谓 词词 的的 概概 念念 与与 表表 示示-2-2 量词量词-3-3 谓词公式谓词公式-5 5 等价式与蕴含式等价式与蕴含式 -7 7 谓谓 词词 演演 算算 的的 推推 理理 理理 论论2 26 6 前束范式前束范式谓词逻辑谓词逻辑 -4 谓词公式的解释谓词公式的解释第12页，本讲稿共117页例如例如:任何人都是要死的任何人都是要死的.(T).(T)有些人是聪明的有些人是聪明的.(T).(T)所有的自然数都等于所有的自然数都等于1 1.(F).(F)存在着自然数等于存在着自然数等于1 1.(T).(T)对个体域中的对个体域中的所有个体成立所有个体成立对个体域中的对个体域中的某些个体成立某些个体成立当命题的主语是泛指时当命题的主语是泛指时,命题的真值还取决于谓词与个体域命题的真值还取决于谓词与个体域中个体的数量关系中个体的数量关系.谓词逻辑谓词逻辑 量词量词2-22-2量词量词1.1.全称量词与存在全称量词与存在量词量词第13页，本讲稿共117页两两种种量词量词:命题中表示个体数量的词。命题中表示个体数量的词。全称量词全称量词(Universal Quantifier):(Universal Quantifier):表示个体域中全体个体的词，记作表示个体域中全体个体的词，记作 相当于相当于 “任意任意”,“凡是凡是”,“所有所有”.若个体域中所有个体若个体域中所有个体x,均使均使A(x)为真为真,记作记作(x)A(x)存在量词存在量词(Existential Quantifier):(Existential Quantifier):表示个体域中部分个体的词，表示个体域中部分个体的词，记作记作 相当于相当于 “存在存在”,“至少有一个至少有一个”,“有些有些”.若个体域中存在某些个体若个体域中存在某些个体x,使使A(x)为真为真,记作记作(x)A(x)谓词逻辑谓词逻辑 量词量词第14页，本讲稿共117页设设H(x):x 是要死的是要死的,任何人都是要死的。任何人都是要死的。例如例如:则命题表示为则命题表示为:(x)H(x)个体域个体域D:人类人类 又例如又例如:有些人是聪明的有些人是聪明的.设设A(x):x是聪明的是聪明的,个体域个体域 D:人类人类则命题表示为则命题表示为:(x)A(x)谓词逻辑谓词逻辑 量词量词第15页，本讲稿共117页当在全总个体域中讨论命题时当在全总个体域中讨论命题时,需在命题表示中增加一个需在命题表示中增加一个特性谓词特性谓词,以以给出个体变元的个体域。给出个体变元的个体域。2.2.特性谓词特性谓词(1)(1)带全称量词的命题带全称量词的命题,特性谓词作为特性谓词作为 加入加入.任何人都是要死的任何人都是要死的例如例如:M(x):x是人是人则命题表示为则命题表示为：(x)(M(x)H(x)改为改为:谓词逻辑谓词逻辑 量词量词设设 H(x):x是要死的是要死的 个体域个体域D:全人类全人类 则则命题表示为命题表示为：(x)H(x)。H(x):x是要死的是要死的条件式的前件条件式的前件第16页，本讲稿共117页例如例如:有些人是聪明的有些人是聪明的.个体域个体域 D：人：人设设A(x)：x是聪明的是聪明的,则命题表示为则命题表示为:(x)A(x)改为改为:A(x)：x是聪明的是聪明的,则命题表示为则命题表示为:(x)(M(x)A(x)(2)(2)带存在量词的命题带存在量词的命题,特性谓词作为特性谓词作为合取项合取项加入加入。为何特性谓词以前件加在全称量词后为何特性谓词以前件加在全称量词后,而以合取项加在存在量词后而以合取项加在存在量词后?能能否改为否改为:(x)(H(x)M(x)和和(x)(M(x)A(x)?谓词逻辑谓词逻辑 量词量词M(x):x是人是人第17页，本讲稿共117页3.3.命题符号化命题符号化谓词逻辑谓词逻辑 量词量词日常用语翻译日常用语翻译第18页，本讲稿共117页用谓词逻辑处理苏格拉底三段论：用谓词逻辑处理苏格拉底三段论：人总是要死的人总是要死的,苏格拉底是人苏格拉底是人,所以所以,苏格拉底是要死的。苏格拉底是要死的。a:苏格拉底苏格拉底 M(x):x是人是人,(x)(M(x)P(x),M(a),P(a).令令谓词逻辑谓词逻辑 量词量词例题例题P(x):x是要死的是要死的,推理形式为推理形式为:(x)(M(x)P(x),M(a)P(a).1.1.判断是否复合命题判断是否复合命题(看有几个主谓结构或连接词看有几个主谓结构或连接词).).2.2.对复合命题找出每个原子命题对复合命题找出每个原子命题.3.3.对每个原子命题分出主语和谓语对每个原子命题分出主语和谓语,主语若是泛指需加量主语若是泛指需加量 词和特性谓词词和特性谓词.并用符号表示并用符号表示.4.4.分析各原子命题的关系分析各原子命题的关系,确定连接词确定连接词.第19页，本讲稿共117页存在着最小的自然数存在着最小的自然数.谓词逻辑谓词逻辑 量词量词P61 例题例题补例补例 兔子比乌龟跑的快兔子比乌龟跑的快例题例题3 3 尽管有人聪明尽管有人聪明,但未必一切人都聪明但未必一切人都聪明.例题例题1 1 并非每个实数都是有理数并非每个实数都是有理数.每个人都有自己喜欢的职业每个人都有自己喜欢的职业.R(x):x是实数是实数设设 Q(x):x是有理数是有理数,故符号化为故符号化为:(x)(R(x)Q(x)M(x):x是人是人设设 P(x):x是聪明的是聪明的,(x)(P(x)M(x)(x)(M(x)P(x)第20页，本讲稿共117页命题逻辑命题逻辑 逻辑连接词逻辑连接词作作 业业2-1，2-2 （1）（）（e）,（f）,（g）,（h）2-3 （3）本节重点掌握的概念本节重点掌握的概念:个体，谓词个体，谓词,量词量词,个体域。个体域。本节重点掌握的方法本节重点掌握的方法:命题符号化。特别注意特命题符号化。特别注意特 性谓词的两种使用方法。性谓词的两种使用方法。第21页，本讲稿共117页谓词逻辑谓词逻辑 谓词公式谓词公式1.个体和谓词个体和谓词2.谓词的表示谓词的表示:P(x1,x2,.xn)每个命题有一个谓词和若干个体组成每个命题有一个谓词和若干个体组成.当谓词确定后当谓词确定后,命题的真值依赖个体命题的真值依赖个体,因此采用函数的记法表示谓词因此采用函数的记法表示谓词,自变自变量的取值范围称为个体域量的取值范围称为个体域 D D3.量词量词:当句子的主语是泛指的时候当句子的主语是泛指的时候,必须引入量词符号必须引入量词符号4.特性谓词特性谓词:若在全总个体域讨论问题若在全总个体域讨论问题,还需在命题表达中还需在命题表达中增加特性谓词增加特性谓词,以说明命题中个体的取值范围以说明命题中个体的取值范围.5.5.命题符号化命题符号化 “每个计算机系的学生都学离散数学每个计算机系的学生都学离散数学“存在着偶素数存在着偶素数”第22页，本讲稿共117页谓词逻辑谓词逻辑 谓词公式谓词公式1.北京是中国的首都北京是中国的首都2.甲是乙的父亲甲是乙的父亲3.3介于介于2与与4之间之间4.3大于大于2仅当仅当3大于大于4。5.张三和李四是同班同学张三和李四是同班同学6.天下乌鸦一般黑天下乌鸦一般黑7.火车都比汽车跑得快火车都比汽车跑得快8.有的火车比所有汽车快。有的火车比所有汽车快。课堂练习课堂练习在谓词逻辑中符号化：在谓词逻辑中符号化：第23页，本讲稿共117页-1 1 谓谓 词词 的的 概概 念念 与与 表表 示示-2-2 量词量词-3-3 谓词公式谓词公式-5 5 等价式与蕴含式等价式与蕴含式 -7 7 谓谓 词词 演演 算算 的的 推推 理理 理理 论论2 26 6 前束范式前束范式谓词逻辑谓词逻辑 -4 谓词公式的解释谓词公式的解释第24页，本讲稿共117页2-32-3谓词公式谓词公式如如 P,P(x),P(x,y),P(f(x),y),P(a,y)均原子公式均原子公式。1 1.谓词公式谓词公式 补充定义补充定义(项项)1).1).个体常元和个体变元是项个体常元和个体变元是项.2).2).若若f 是是n n元个体函数元个体函数,t1,.,tn,t1,.,tn是项是项,则则 f(t1,.tn)(t1,.tn)是项是项.3).3).只有有限次运用只有有限次运用1),2)1),2)规则得到的符号串是项规则得到的符号串是项.如如 x,a,f(x),g(x,y),g(f(x),a).谓词逻辑谓词逻辑 谓词公式谓词公式项代表公式中以各种形式出现的个体项代表公式中以各种形式出现的个体.原原 子子 公公 式式:把把 A(t1,t2,tn)称称 为为 谓谓 词词 演演 算算 的的 原原 子子 公公 式式,其中其中,t1,t2,tn是项是项.不含个体变元的原子公式是原子命题不含个体变元的原子公式是原子命题.第25页，本讲稿共117页定义定义 2-3.1 谓词演算的合式公式谓词演算的合式公式wff,由下述各条组成：由下述各条组成：(1)原子谓词公式是合式公式。原子谓词公式是合式公式。(2)若若A是合式公式是合式公式,则则 A是合式公式。是合式公式。(3)若若A和和B都是合式公式都是合式公式,则则(A B),(A B),(AB)和和(AB)是合式公式。是合式公式。(4)如果如果A是合式公式是合式公式,x是是A中出现的任何变元中出现的任何变元,则则(x)A和和(x)A都是合式公式。都是合式公式。(5)只有经过有限次的应用规则只有经过有限次的应用规则(1),(2),(3),(4)所得到的公式是所得到的公式是合式公式合式公式。简称简称谓词公式谓词公式如如 x y P(x,y),x P(f(x),y),谓词逻辑谓词逻辑 谓词公式谓词公式 P(a,y)Q Q 第26页，本讲稿共117页2 2.变元的约束变元的约束 若给定若给定 为一谓词公式为一谓词公式,它可带有如下子公式它可带有如下子公式:(x)A(x)或或 (x)A(x)指导变元指导变元辖域辖域约束变元约束变元其中其中,、后的后的 x 称为该量词的称为该量词的指导变元指导变元;A A(x)称为量词的称为量词的作作用域用域或或辖域辖域(scope)(scope);在辖域中在辖域中 x 的一切出现称为的一切出现称为x在在 中的中的约束约束出现出现,x称为称为约束变元约束变元;在在 中除约束变元以外所出现的变元称为中除约束变元以外所出现的变元称为自由变元自由变元。P63例题例题1如如 x(M(x)R(x),yP(x,y)R(y)谓词逻辑谓词逻辑 谓词公式谓词公式第27页，本讲稿共117页 闭式闭式:不含自由变元的公式不含自由变元的公式.开式开式:含有自由变元的公式含有自由变元的公式.其其 中中,含含 有有k个个 自自 由由 变变 元元 x1,x2,.xk的的 公公 式式称称 为为 k元谓词元谓词,记作记作A(x1,x2,.xk),),0 0元谓词元谓词为闭式为闭式.例如例如 (x)P(x,y,z)x是小于是小于100100的质数的质数:L(L(x,100)又如又如 任意的实数任意的实数x,都存在着实数都存在着实数y,使得使得xy.（不存在最大实数）不存在最大实数）令令 P(x,y):x 谓词公式谓词公式 闭式闭式(T)二元谓词二元谓词一元谓词一元谓词由命题符号化得到的公式是闭式由命题符号化得到的公式是闭式.第28页，本讲稿共117页-1 1 谓谓 词词 的的 概概 念念 与与 表表 示示-2-2 量词量词-3-3 谓词公式谓词公式 -4 谓词公式的解释谓词公式的解释-5 5 等价式与蕴含式等价式与蕴含式 -7 7 谓谓 词词 演演 算算 的的 推推 理理 理理 论论2 26 6 前束范式前束范式谓词逻辑谓词逻辑第29页，本讲稿共117页谓词公式的真值与那些因素有关谓词公式的真值与那些因素有关?谓词公式的真值能否像命题逻辑谓词公式的真值能否像命题逻辑那样总可由真值表给出那样总可由真值表给出?例例 x y(P(x)Q(f(x,a),y,z)R)的真的真值值给出个体域给出个体域指定谓词指定谓词2-4.2-4.谓词公式的解释谓词公式的解释指定个体函数和个体指定个体函数和个体指定自由变元指定自由变元谓词逻辑谓词逻辑 谓词公式的解释谓词公式的解释令令 P(x,y):xy,D:自然数自然数 x y P(x,y)(闭命题闭命题)(F)例例(T);令令 P(x,y):x+y=0,D:自然数自然数Q(x,y)P(x,y)(开命题开命题)例例令令D:自然数自然数;P(x,y):x 谓词公式的解释谓词公式的解释第31页，本讲稿共117页 给定解释给定解释I和和I 中的赋值如下中的赋值如下:DI:自然数集自然数集,L(x,y):xy,E(x,y):x=y,h(x,y):xy,v1:x=0,v2:x=1求公式在解释求公式在解释I下的真值下的真值.(1)y(E(x,y)L(x,y)(2)y z E(h(y,z),x)解解 在解释在解释I下下 E(x,y)为为 x=y;L(x,y)为为x 谓词公式的解释谓词公式的解释补例补例第32页，本讲稿共117页补例补例 设解释设解释I I的个体域为的个体域为 a1,a2,an,则在解释则在解释I下下,xA(x)A(a 1)A(a 1).A(a n)xA(x)A(a1)A(a1).A(an)当当个个体体域域D DI I中中的的元元素素个个数数有有限限时时,可可将将变变元元的的所所有有可能取值一一列举出来可能取值一一列举出来,此时量词可消除此时量词可消除.谓词逻辑谓词逻辑 谓词公式的解释谓词公式的解释第33页，本讲稿共117页谓词逻辑谓词逻辑 谓词公式的解释谓词公式的解释求下列闭式在解释求下列闭式在解释I下的真值下的真值 给定解释给定解释I如下如下:D=2,3,f(2)=3,f(3)=2,P(2)=T P(3)=F,Q(2,2)=T,Q(3,3)=T,Q(2,3)=F,Q(3,2)=F.解解1)x(Q(f(x),x)P(x)2)x(y)Q(x,y)1).原式原式=(Q(f(2),2)P(2)(Q(f(3),3)P(3)=(Q(3,2)P(2)(Q(2,3)P(3)=(FT)(FF)=T 2).原式原式=x(Q(x,2)Q(x,3)=(Q(2,2)Q(2,3)(Q(3,2)Q(3,3)=(T F)(F T)=T y x Q(x,y)的真值的真值?补例补例第34页，本讲稿共117页谓词逻辑谓词逻辑 谓词公式的解释谓词公式的解释 求求(x)(y)(P(x)Q(x,y)在解释在解释I的真的真值值 DI=1,2,P(1)=F,P(2)=T,Q(1,1)=T,Q(2,2)=T;Q(1,2)=F,Q(2,1)=F.原式原式=(x)(P(x)Q(x,1)(P(x)Q(x,2)=(P(1)Q(1,1)(P(1)Q(1,2)(P(2)Q(2,1)(P(2)Q(2,2)=(F T)(F T)(F F)(T T)=F补例补例第35页，本讲稿共117页谓词逻辑谓词逻辑 谓词公式的解释谓词公式的解释课堂练习课堂练习1.“并非一切推理都能用计算机完成并非一切推理都能用计算机完成”符号化为符号化为()2.设设R(x):x是实数是实数,P(x,y):x=y,则命题则命题“对任意的实数对任意的实数 x,y,有有x+y=y+x”符号化为符号化为()3.不含有自由变元的谓词公式是命题不含有自由变元的谓词公式是命题.()4.y E(x,y)L(x,y,z)是二元谓词是二元谓词()5.使一阶逻辑公式使一阶逻辑公式 y x F(y,x)为真的解释是为真的解释是()A.个体域为自然数集合，个体域为自然数集合，F(x,y)为为 x y B.个体域为自然数集合，个体域为自然数集合，F(x,y)为为 y 谓词公式的解释谓词公式的解释 本节重点掌握的概念本节重点掌握的概念:谓词公式谓词公式,自由变元自由变元,约束变元约束变元,开式开式,闭式。闭式。本节重点掌握的方法本节重点掌握的方法:求谓词公式的真值求谓词公式的真值第37页，本讲稿共117页要点回顾要点回顾谓词逻辑谓词逻辑 等价与蕴含式等价与蕴含式1.个体和谓词个体和谓词2.谓词的表示谓词的表示:P(x1,x2,.xn)3.量词量词4.特性谓词特性谓词5.谓词公式谓词公式6.谓词公式的赋值谓词公式的赋值:对谓词公式一个赋值称为一个解释。闭式在对谓词公式一个赋值称为一个解释。闭式在一组解释下会求得一个真值；开式还需在此基础上对自由变元赋值，一组解释下会求得一个真值；开式还需在此基础上对自由变元赋值，才能求出一个真值才能求出一个真值。例例:对对任意的自然数任意的自然数x存在着自然数存在着自然数y,使得使得 p(x,y)成立成立.解释解释1：p(x,y):x 等价与蕴含式等价与蕴含式第40页，本讲稿共117页命题逻辑永真式（永假式）的代换实例是谓词逻辑的永真式（永命题逻辑永真式（永假式）的代换实例是谓词逻辑的永真式（永假式）。假式）。设设A是包含命题变元是包含命题变元 P1,P2,.Pn的命题公式的命题公式,B1,B2,.Bn是是谓词公式谓词公式,用用 B1,B2,.Bn 分别代替分别代替P1,P2,.Pn 在在A中的所有中的所有出现出现,得到的谓词公式得到的谓词公式B称称A的的代换实例代换实例,命题逻辑永真式命题逻辑永真式的代换实例称为的代换实例称为重言式重言式.谓词逻辑谓词逻辑 等价与蕴含式等价与蕴含式命题逻辑的代入定理命题逻辑的代入定理:一个重言式一个重言式,对同一分量都用任对同一分量都用任何合式公式置换何合式公式置换,结果仍重言结果仍重言.第41页，本讲稿共117页谓词逻辑谓词逻辑 等价与蕴含式等价与蕴含式上式可看作命题公式上式可看作命题公式PP的代入实例的代入实例1)(x)P(x)(x)P(x)2)(xP(x)(xQ(x)xP(x)上式可看作命题公式上式可看作命题公式 (P(Q P)的代入实例的代入实例 而而(P(Q P)(P (Q P)F 所以所以,(xP(x)(xQ(x)x P(x)为永假式为永假式而而PP T,所以所以,(x)P(x)(x)P(x)为重言式为重言式 判定公式的类型判定公式的类型重言式是永真式重言式是永真式,但永真未必重言但永真未必重言.例如例如 xP(x)xP(x)是永真式，但不是重言式是永真式，但不是重言式.补例补例第42页，本讲稿共117页2.2.等价与蕴含等价与蕴含定定义义 2-5.1 设设A,B是是公公式式,若若AB是是永永真真式式,则则称称A,B等价等价.记作记作AB.等价式的判定等价式的判定等价演算等价演算:利用利用基本公式基本公式、等价的性质等价的性质 和和 置换置换 定理定理，推演出其他等价式推演出其他等价式.定定义义 2-5.2 设设A,B是是公公式式,若若AB是是永永真真式式,则则称称A蕴含蕴含B.记作记作AB.谓词逻辑谓词逻辑 等价与蕴含式等价与蕴含式AB 当且仅当当且仅当 A B且且B A第43页，本讲稿共117页(1)(1)命题公式的推广命题公式的推广例如例如 P PQ QP P Q Q 用用 xP(x)代替代替 P;(x)P(x)(x)Q(x)(x)P(x)(x)Q(x)xQ(x)代替代替 Q 得到得到:(x)(P(x)Q(x)(x)R(x)(x(P(x)Q(x)(x)R(x)同理同理 P(x)Q(x)P(x)Q(x)利用代入定理利用代入定理,将命题逻辑的所有等价式推广到谓将命题逻辑的所有等价式推广到谓词逻辑词逻辑.谓词逻辑谓词逻辑 等价与蕴含式等价与蕴含式第44页，本讲稿共117页(2)(2)量词与联结词量词与联结词 的关系的关系例例 设设 P(x):x今天来校上课今天来校上课,D:学生学生 则则 P(x)表示表示:x今天没来校上课今天没来校上课 “并非所有人今天来校上课并非所有人今天来校上课”(x)P(x)等价等价 “有人今天没来校上课有人今天没来校上课”(x)P(x)(x)P(x)(x)P(x)“没有人今天来校上课没有人今天来校上课”(x)P(x)等价等价 “所有人今天都没来校上课所有人今天都没来校上课”(x)P(x)(x)P(x)(x)P(x)谓词逻辑谓词逻辑 等价与蕴含式等价与蕴含式第45页，本讲稿共117页(3)(3)量词作用域的扩张与收缩量词作用域的扩张与收缩(x)(A(x)B)(x)A(x)BB(x)A(x)(x)(A(x)B)(x)A(x)BB (x)A(x)(x)A(x)B (x)(A(x)B)(x)A(x)B (x)A(x)B)B(x)A(x)(B(x)A(x)B(x)A(x)(B(x)A(x)由上式可推出由上式可推出谓词逻辑谓词逻辑 等价与蕴含式等价与蕴含式第46页，本讲稿共117页(4)(4)量词与联结词之间的一些等价式量词与联结词之间的一些等价式例例第一式中用第一式中用 A代代A,用用 B代代B：(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)与与“联欢会上所有人唱歌且所有人跳舞联欢会上所有人唱歌且所有人跳舞”意义相同意义相同(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)对对 满足满足分配律分配律 对对 满足满足分配律分配律“联欢会上所有人即唱歌又跳舞联欢会上所有人即唱歌又跳舞.”谓词逻辑谓词逻辑 等价与蕴含式等价与蕴含式(x)(A(x)B(x)(x)A(x)(x x)B()B(x x)第47页，本讲稿共117页 (x)(A(x)B(x)(x)A(x)(x)B(x)?(x)(A(x)B(x)(x)A(x)(x)B(x)?(x)(A(x)B(x):对所有的对所有的x,有有A(x)或或B(x)成立成立.(x)(A(x)B(x):存存在在着着x,使使A(x)和和B(x)同同时时成成 立立.例例 D:整数集合整数集合,A(x):x是偶数是偶数,B(x):x是奇数是奇数(x)A(x)(x)B(x)(T)(x)(A(x)B(x)(F)谓词逻辑谓词逻辑 等价与蕴含式等价与蕴含式(x)A(x)(x)B(x):对所有的对所有的x,A(x)成立成立;或对所有或对所有的的x,B(x)成立成立.(x)A(x)(x)B(x):存在着存在着x,使使A(x)成立成立,且且存在存在x,使使B(x)成立成立.第48页，本讲稿共117页(5)(5)量词与联结词之间的一些蕴含式量词与联结词之间的一些蕴含式(x)A(x)(x)B(x)(x)(A(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)常见的等价式与蕴含式见表常见的等价式与蕴含式见表2-5.12-5.1同理可得同理可得谓词逻辑谓词逻辑 等价与蕴含式等价与蕴含式第49页，本讲稿共117页(6)(6)多个多个量词的使用量词的使用公式中多个量词的出现次序关系到命题的含义公式中多个量词的出现次序关系到命题的含义,不能随意交换不能随意交换.例如例如 x y A(x,y):对任意对任意x,都存在都存在y,使得使得A成立成立.例例 (x)(y)(x+y=0)为真命题为真命题,y=-x y xA(x,y):存在着存在着y,对所有的对所有的x 都有都有A成立成立.(y)(x)(x+y=0)为假命题为假命题谓词逻辑谓词逻辑 等价与蕴含式等价与蕴含式 y 的值独立于的值独立于x.y 的值依赖于的值依赖于x.第50页，本讲稿共117页特殊情况特殊情况:全称量词之间可交换全称量词之间可交换,存在量词之间可交换存在量词之间可交换.全称与存在之间存在如下关系全称与存在之间存在如下关系:I18 (x)(y)A(x,y)(y)(x)A(x,y)I19 (x)(y)A(x,y)(x)(y)A(x,y)I20 (y)(x)A(x,y)(x)(y)A(x,y)I21 (x)(y)A(x,y)(y)(x)A(x,y)I22 (x)(y)A(x,y)(y)(x)A(x,y)I23 (y)(x)A(x,y)(x)(y)A(x,y)谓词逻辑谓词逻辑 等价与蕴含式等价与蕴含式 x y y x y x y x y x x y x y y x第51页，本讲稿共117页例题例题谓词逻辑谓词逻辑 等价与蕴含式等价与蕴含式右式右式验证验证(x)(A(x)B(x)(x)A(x)(x)B(x)(x)A(x)(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)(A(x)B(x)证明证明 (x)P(x)(x)P(x)为永真式。为永真式。证明证明 (P(x)(Q(x)P(x)为永假式。为永假式。第52页，本讲稿共117页例题例题谓词逻辑谓词逻辑 等价与蕴含式等价与蕴含式 (x)P(x)(x)P(x)分析真值法分析真值法:左左右右 且且 右右左左.给定公式给定公式(x)P(x)(x)P(x)一组解释一组解释I,若若 (x)P(x)在在 I下为真下为真,则则(x)P(x)为假为假,即存在即存在 a D,使使P(a)为假为假,即即 P(a)为真为真,即即(x)P(x)为真为真.给定给定(x)P(x)(x)P(x)一组解释一组解释I,若若(x)P(x)在在I下为真下为真,则存在则存在 a D,使使 P(a)为真为真,即即P(a)为假为假,即即(x)P(x)为真为真.则则(x)P(x)为假为假,第53页，本讲稿共117页-1 1 谓谓词词的的概概念念与与表表示示-2-2 量词量词-3-3 谓词公式谓词公式-5 5 等价式与蕴含式等价式与蕴含式 -7 7 谓谓 词词 演演 算算 的的 推推 理理 理理 论论2 26 6 前束范式前束范式谓词逻辑谓词逻辑 -4 谓词公式的解释谓词公式的解释第54页，本讲稿共117页谓词逻辑谓词逻辑 前束范式前束范式2-62-6前束范式前束范式定义定义 2-6.1 2-6.1 一个公式一个公式,如果量词均在全式的开头如果量词均在全式的开头,它们的作用域它们的作用域,延伸到整个公式的末尾延伸到整个公式的末尾,则该公式叫做则该公式叫做前束范式前束范式。前束范式简记为前束范式简记为:(v1)(v2).(vn)A 或或 指导变元指导变元母式母式(不含量词不含量词)例如例如 (x)(y)(z)(Q(x,y)R(z)(x)P(x)(x)Q(x)?Q(x,y)R(z)定理定理2-6.12-6.1 任一谓词公式任一谓词公式,均和一个前束范式等价均和一个前束范式等价.第55页，本讲稿共117页化前束范式的方法化前束范式的方法(1).1).将公式中的连接词化为将公式中的连接词化为,.(.(非必须非必须)(2).(2).利用否定律利用否定律,德德.摩根律摩根律,及量词转化律及量词转化律,将否将否 定深入到谓词字母前定深入到谓词字母前.(3).(3).利用利用换名规则或或代入规则使所有约束变元均使所有约束变元均 不相同且使所有的自由变元与约束变元不同不相同且使所有的自由变元与约束变元不同.(4).(4).利用量词的的扩张与收缩利用量词的的扩张与收缩,扩大量词的辖域扩大量词的辖域 至整个公式至整个公式.谓词逻辑谓词逻辑 前束范式前束范式例如例如 (x)P(x,y)Q(x)(x)P(x)(x)Q(x)第56页，本讲稿共117页因为因为 (x)P(x)(y)P(y),(x)P(x)(y)P(y),所所以以,若若谓谓词词公公式式中中有有变变元元既既约约束束出出现现,又又自自由由出出现现,为为避避免免 混混 淆淆,可可 对对约约 束束变变 元元 进进 行行 换换 名名或或 对对自自 由由 变变 元元 代代 入入,使得一个使得一个变元在公式中只呈一种变元在公式中只呈一种出现出现.(1 1)对对 约约 束束变变 元元 换换 名名,其其更更改改的的变变元元名名称称范范围围是是:量量 词词 中中的的指指导导变变元元及及该该量量词词辖辖域域中中出出现现的的该该变变元元,而而 公式中其余变元不变公式中其余变元不变.(2 2)对对 约约 束束变变 元元 换换 名名 时时 一一 定定 要要 更更 改改 为为 辖辖 域域 中中 未未 出出 现现 的变元名的变元名.换换名名规规则则 例如例如 (x)P(x)(x)Q(x)(x)P(x)(y)Q(y)谓词逻辑谓词逻辑 前束范式前束范式(x)(y)(P(x)Q(y)(x)(P(x)R(x,y)Q(x,y)=?第57页，本讲稿共117页代入规则代入规则(1).(1).代入须对公式中该代入须对公式中该自由变元的所有出现同自由变元的所有出现同 时进行时进行.(2).(2).代入的变元不能与公式中其它变元同名代入的变元不能与公式中其它变元同名.例如例如 (x)P(x)Q(x,y)(x)P(x)Q(r,y)(x)(y)P(x,y)R(x,y,z)(x)(y)P(x,y)R(u,v,z)(x)(y)(P(x,y)R(u,v,z)谓词逻辑谓词逻辑 前束范式前束范式第58页，本讲稿共117页(v1)(v2)(vn)(其中其中可能是量词可能是量词 或或,vi(i=1,2,n)是指导变元是指导变元,Aij是原子公是原子公式或其否定。式或其否定。定义定义2-6.2 一个一个wff A如果具有如下形式称为如果具有如下形式称为前束合取范式前束合取范式例如例如 (x)(z)(y)(P(x,y)(z=b)(Q(y)(a=b)定理定理2-6.22-6.2 每一个每一个wff Awff A都可以转换为与它等价的都可以转换为与它等价的前束合取范式。前束合取范式。谓词逻辑谓词逻辑 前束范式前束范式第59页，本讲稿共117页其其中中可可能能是是量量词词 或或,vi(i=1,2,n)是是客客体体变变元元,Aij是是原原子子公公式式或其否定。或其否定。定义定义2-6.3 一个一个wff