离散数学第二章

离散数学第二章第1页，共117页，2023年，2月20日，星期二用命题逻辑处理苏格拉底三段论：谓词逻辑又例:张华是大学生,李明也是大学生。所有的自然数都等于1.(F);存在着自然数等于1.(T)PQR人总是要死的,苏格拉底是人,苏格拉底是要死的。若论证有效则有:PQR,即PQR永真.第2页，共117页，2023年，2月20日，星期二谓词逻辑对简单命题作进一步分析,分离出个体和谓词,并考虑到泛指和特指(全称和存在),在此基础上,研究命题的逻辑结构及命题间的推理关系。PredicateLogic第二章第3页，共117页，2023年，2月20日，星期二２-1谓词的概念与表示２-2量词２-3谓词公式２-5等价式与重言式２-7

谓词演算的推理理论2－6前束范式谓词逻辑２-4谓词公式的解释第4页，共117页，2023年，2月20日，星期二命题是具有确定真值的陈述句。2-1谓词的概念和表示如

“电子计算机是科学技术的工具。”个体:思维的对象,可以是具体的事物或抽象的概念谓词:刻画个体性质或个体之间关系的词。1.

个体和谓词

陈述句由主语和谓语两部分构成，主语谓语个体谓词一元谓词:与一个个体相关联的谓词.(描述个体性质)N元谓词:与N个个体相关联的谓词.(描述个体间的关系)谓词逻辑>谓词的概念和表示第5页，共117页，2023年，2月20日，星期二(a).他是三好学生。(b).7是质数。(c).每天作广播操是好习惯。(d).5大于3.(e).地球绕着太阳转。一元谓词。谓词刻画个体性质(f).张明和张亮是兄弟。(e).上海位于南京和杭州之间。谓词刻画个体间关系。在谓词逻辑中,命题是由一个谓词和若干有序个体组成的。谓词逻辑>谓词的概念和表示二元谓词二元谓词二元谓词三元谓词第6页，共117页，2023年，2月20日，星期二2.个体和谓词的表示

命题由一个谓词和若干个体组成谓词逻辑>谓词的概念和表示用大写字母A,B,C,D,...代表谓词。用小写字母代表个体：用小写字母

a,b,c...表示特定个体:个体常元用小写字母x,y,z...表示任意个体：个体变元.一个n元谓词记作:A(x1,x2,…xn)其中x1,x2,…,xn为个体变元.当A(x1,…xn)中个体变元用个体常元:a1,…an代入后,A(a1…an)就成为一个命题。则A(a)表示命题:张华是大学生,A(b)表示命题:李明是大学生。例:令A(x):x是大学生;a:张华,b:李明第7页，共117页，2023年，2月20日，星期二命题由一个谓词和若干个体组成，但并非任意个体都和任意谓词都能构成命题。如2是偶数,(T)个体域:个体的取值范围,用D表示如谓词“...是偶数”的个体域D:全体整数。“...是要死的”D:全体生物或D:人类全总个体域:所有个体的集合称之。谓词逻辑>谓词的概念和表示3是偶数,(F)x是偶数(不是命题)当谓词确定后,其允许的个体取值范围称为个体域。则A(a)表示命题:张华是大学生,A(b)表示命题:李明是大学生。例:令A(x):x是大学生;D:人类a:张华,b:李明第8页，共117页，2023年，2月20日，星期二又例:上海位于南京和杭州之间。

令L(x,y,z):x位于y和z之间,D:城市则命题符号化为:L(a,b,c)谓词逻辑>谓词的概念和表示则L(2,3)表示命题:2<3.(真)又例:设L(x,y):x小于y,D:实数集合则L(5,1):表示命题:5<1.(假)a:上海b:南京c:杭州当谓词及其个体域确定后，命题的真值与个体的取值有关，因此一个谓词可看作是一个以个体为自变量,函数值取真值的函数。第9页，共117页，2023年，2月20日，星期二由简单命题及连接词可构成复合命题。与命题逻辑同张华和李明都是大学生。例1P(x):x是大学生,D:人,a:张华,b:李明命题符号化:P(a)P(b)如果张三比李四高,李四比王五高,则张三比王五高。命题符号化:P(a,b)P(b,c)P(a,c)例3p:(x,y)x比y高,D:人;a:张三,b:李四,c:王五2既是偶数又是素数。例2P(x):x是偶数,Q(x):x是素数,D:整数,a:2,命题符号化:P(a)Q(a)谓词逻辑>谓词的概念和表示3.复合命题第10页，共117页，2023年，2月20日，星期二例如:张华的母亲爱张华.设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,2·3)自变量和函数值均为个体域中的个体.用小写字母f,g...表示.谓词逻辑>量词4.个体函数例如:张华的母亲爱张华.第11页，共117页，2023年，2月20日，星期二２-1谓词的概念与表示２-2量词２-3谓词公式２-5等价式与蕴含式２-7

谓词演算的推理理论2－6前束范式谓词逻辑２-4谓词公式的解释第12页，共117页，2023年，2月20日，星期二例如:任何人都是要死的.(T)有些人是聪明的.(T)所有的自然数都等于1.(F)存在着自然数等于1.(T)对个体域中的所有个体成立对个体域中的某些个体成立当命题的主语是泛指时,命题的真值还取决于谓词与个体域中个体的数量关系.谓词逻辑>量词2-2

量词1.全称量词与存在量词第13页，共117页，2023年，2月20日，星期二两种量词:命题中表示个体数量的词。全称量词(UniversalQuantifier):表示个体域中全体个体的词，记作

相当于“任意”,“凡是”,“所有”...若个体域中所有个体x,均使A(x)为真,记作(x)A(x)存在量词(ExistentialQuantifier):表示个体域中部分个体的词，记作

相当于“存在”,“至少有一个”,“有些”...若个体域中存在某些个体x,使A(x)为真,记作(x)A(x)谓词逻辑>量词第14页，共117页，2023年，2月20日，星期二设H(x):x是要死的,任何人都是要死的。例如:则命题表示为:(x)H(x)个体域D:人类又例如:有些人是聪明的.设A(x):x是聪明的,个体域D:人类则命题表示为:(x)A(x)谓词逻辑>量词第15页，共117页，2023年，2月20日，星期二当在全总个体域中讨论命题时,需在命题表示中增加一个特性谓词,以给出个体变元的个体域。2.特性谓词(1)带全称量词的命题,特性谓词作为加入.任何人都是要死的例如:M(x):x是人则命题表示为：(x)(M(x)H(x))改为:谓词逻辑>量词设H(x):x是要死的个体域D:全人类则命题表示为：(x)H(x)。H(x):x是要死的条件式的前件第16页，共117页，2023年，2月20日，星期二例如:有些人是聪明的.个体域

D：人设A(x)：x是聪明的,则命题表示为:(x)A(x)改为:A(x)：x是聪明的,则命题表示为:(x)(M(x)A(x))(2)带存在量词的命题,特性谓词作为合取项加入。为何特性谓词以前件加在全称量词后,而以合取项加在存在量词后?能否改为:(x)(H(x)M(x))和(x)(M(x)A(x))?谓词逻辑>量词M(x):x是人第17页，共117页，2023年，2月20日，星期二3.命题符号化谓词逻辑>量词日常用语翻译第18页，共117页，2023年，2月20日，星期二用谓词逻辑处理苏格拉底三段论：人总是要死的,苏格拉底是人,所以,苏格拉底是要死的。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.判断是否复合命题(看有几个主谓结构或连接词).2.对复合命题找出每个原子命题.3.对每个原子命题分出主语和谓语,主语若是泛指需加量词和特性谓词.并用符号表示.4.分析各原子命题的关系,确定连接词.第19页，共117页，2023年，2月20日，星期二存在着最小的自然数.谓词逻辑>量词P61例题补例兔子比乌龟跑的快例题3尽管有人聪明,但未必一切人都聪明.例题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页，2023年，2月20日，星期二命题逻辑>逻辑连接词作业2-1，2-2（1）（e）,（f）,（g）,（h）2-3（3）本节重点掌握的概念:个体，谓词,量词,个体域。本节重点掌握的方法:命题符号化。特别注意特性谓词的两种使用方法。第21页，共117页，2023年，2月20日，星期二谓词逻辑>谓词公式1.个体和谓词2..谓词的表示:P(x1,x2,...xn)每个命题有一个谓词和若干个体组成.当谓词确定后,命题的真值依赖个体,因此采用函数的记法表示谓词,自变量的取值范围称为个体域D3.量词:当句子的主语是泛指的时候,必须引入量词符号4.特性谓词:

若在全总个体域讨论问题,还需在命题表达中增加特性谓词,以说明命题中个体的取值范围.5.命题符号化

“每个计算机系的学生都学离散数学““存在着偶素数”第22页，共117页，2023年，2月20日，星期二谓词逻辑>谓词公式北京是中国的首都甲是乙的父亲3介于2与4之间3大于2仅当3大于4。张三和李四是同班同学天下乌鸦一般黑火车都比汽车跑得快有的火车比所有汽车快。

课堂练习在谓词逻辑中符号化：第23页，共117页，2023年，2月20日，星期二２-1谓词的概念与表示２-2量词２-3谓词公式２-5等价式与蕴含式２-7

谓词演算的推理理论2－6前束范式谓词逻辑２-4谓词公式的解释第24页，共117页，2023年，2月20日，星期二2-3

谓词公式如P,P(x),P(x,y),P(f(x),y),P(a,y)均原子公式。1.

谓词公式

补充定义(项)1).个体常元和个体变元是项.2).若f是n元个体函数,t1,...,tn是项,则f(t1,...tn)是项.3).只有有限次运用1),2)规则得到的符号串是项.如x,a,f(x),g(x,y),g(f(x),a).谓词逻辑>谓词公式项代表公式中以各种形式出现的个体.原子公式:把A(t1,t2,…tn)称为谓词演算的原子公式,其中,t1,t2,…tn是项.不含个体变元的原子公式是原子命题.第25页，共117页，2023年，2月20日，星期二定义2-3.1

谓词演算的合式公式wff,由下述各条组成：(1)原子谓词公式是合式公式。(2)若A是合式公式,则A是合式公式。(3)若A和B都是合式公式,则(AB),(AB),(AB)和(AB)是合式公式。(4)如果A是合式公式,x是A中出现的任何变元,则(x)A和(x)A都是合式公式。(5)只有经过有限次的应用规则(1),(2),(3),(4)所得到的公式是合式公式。简称谓词公式如

xyP(x,y),xP(f(x),y),谓词逻辑>谓词公式P(a,y)

Q

第26页，共117页，2023年，2月20日，星期二2.变元的约束

若给定为一谓词公式,它可带有如下子公式:(x)A(x)或(x)A(x)指导变元辖域约束变元其中,、后的x

称为该量词的指导变元;

A(x)称为量词的作用域或辖域(scope);在辖域中x的一切出现称为x在中的约束出现,x称为约束变元;在中除约束变元以外所出现的变元称为自由变元。P63例题1如x(M(x)R(x)),yP(x,y)R(y)谓词逻辑>谓词公式第27页，共117页，2023年，2月20日，星期二闭式:不含自由变元的公式.开式:含有自由变元的公式.

其中,含有k个自由变元x1,x2,...xk的公式称为

k元谓词,记作A(x1,x2,...xk),0元谓词为闭式.例如

(x)P(x,y,z)

x是小于100的质数:L(x,100)又如任意的实数x,都存在着实数y,使得x<y.（不存在最大实数）令P(x,y):x<y

,

R(x):x是实数xy(R(x)R(y)P(x,y))谓词逻辑>谓词公式

闭式(T)

二元谓词一元谓词由命题符号化得到的公式是闭式.第28页，共117页，2023年，2月20日，星期二２-1谓词的概念与表示２-2量词２-3谓词公式２-4谓词公式的解释２-5等价式与蕴含式２-7

谓词演算的推理理论2－6前束范式谓词逻辑第29页，共117页，2023年，2月20日，星期二谓词公式的真值与那些因素有关?谓词公式的真值能否像命题逻辑那样总可由真值表给出?例xy(P(x)Q(f(x,a),y,z)R)

的真值给出个体域指定谓词2-4.谓词公式的解释指定个体函数和个体指定自由变元谓词逻辑>谓词公式的解释令P(x,y):x<y

,

D:自然数xyP(x,y)(闭命题)

(F)

例(T);令P(x,y):x+y=0,D:自然数Q(x,y)P(x,y)(开命题)例令D:自然数;P(x,y):x<y;

Q(x,y):x+y=0,

令x=2,y=1,(T);令x=1,y=2,(F)第30页，共117页，2023年，2月20日，星期二为公式中的每个自由变元指定个体域DI中的一个个体.谓词公式的一个解释I(Interpretation)解释I下的一个赋值1).指定一个个体域DI.2).为每个个体常元符号指定DI中的一个个体.3).为每个n元个体函数符号指定DI上的n元个体函数.4).为每个n元谓词符号指定一个DI上的n元谓词闭式在一解释下有一确定真值.开式在一组解释I及I下一个赋值下,有一确定真值.补例谓词逻辑>谓词公式的解释第31页，共117页，2023年，2月20日，星期二给定解释I和I中的赋值如下:DI:自然数集,L(x,y):x<y,E(x,y):x=y,h(x,y):x·y,v1:x=0,v2:x=1求公式在解释I下的真值.(1)

y(E(x,y)

L(x,y))(2)

yzE(h(y,z),x)解在解释I下

E(x,y)为x=y;

L(x,y)为x<y当赋值为v1时,命题解释为:对任意自然数y,均有0y(T)

当赋值为v2时,命题解释为:对任意自然数y,均有1y(F)解在解释I下,E(h(y,z),x)为y·z=x当赋值为v1时,命题为:对任意自然数y,存在z使得y·z=0(T)当赋值为v2时,命题为:对任意自然数y,存在z使得y·z=1(F)

谓词逻辑>谓词公式的解释补例第32页，共117页，2023年，2月20日，星期二补例设解释I的个体域为{a1,a2,…,an},则在解释I下,

xA(x)A(a1)A(a1)...A(an)xA(x)A(a1)A(a1)...A(an)当个体域DI中的元素个数有限时,可将变元的所有可能取值一一列举出来,此时量词可消除.谓词逻辑>谓词公式的解释第33页，共117页，2023年，2月20日，星期二谓词逻辑>谓词公式的解释求下列闭式在解释I下的真值给定解释I如下:D={2,3},f(2)=3,f(3)=2,P(2)=TP(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))=

(TF)

(F

T)=TyxQ(x,y)的真值?补例第34页，共117页，2023年，2月20日，星期二谓词逻辑>谓词公式的解释求(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)))=((FT)(FT))((FF)(TT))=F补例第35页，共117页，2023年，2月20日，星期二谓词逻辑>谓词公式的解释课堂练习1.“并非一切推理都能用计算机完成”符号化为()2.设R(x):x是实数,P(x,y):x=y,则命题“对任意的实数

x,y,有x+y=y+x”符号化为()

3.不含有自由变元的谓词公式是命题.()4.

yE(x,y)L(x,y,z))是二元谓词()5.使一阶逻辑公式y

xF(y,x)为真的解释是()A.个体域为自然数集合，F(x,y)为xyB.个体域为自然数集合，F(x,y)为y<xC.个体域为自然数集合，F(x,y)为x=yD.均不属于A、B、C6.在解释I:DI={a,b},P(a,a)=p(b,b)=0P(a,b)=p(b,a)=1下,公式x

yP(x,y)的真值为_____

第36页，共117页，2023年，2月20日，星期二作业2-4（2）（b）,（c）（3）(4)

2-5（1）（b）（2）(a),(d)谓词逻辑>谓词公式的解释本节重点掌握的概念:谓词公式,自由变元,约束变元,开式,闭式。本节重点掌握的方法:求谓词公式的真值第37页，共117页，2023年，2月20日，星期二要点回顾谓词逻辑>等价与蕴含式1.个体和谓词2.谓词的表示:P(x1,x2,...xn)3.量词4.特性谓词5.谓词公式6.谓词公式的赋值:对谓词公式一个赋值称为一个解释。闭式在一组解释下会求得一个真值；开式还需在此基础上对自由变元赋值，才能求出一个真值。例:对任意的自然数x存在着自然数y,使得p(x,y)成立.解释1：p(x,y):x<=y,(T)解释2：p(x,y):x+y=0,(F)第38页，共117页，2023年，2月20日，星期二２-1谓词的概念与表示２-2量词２-3谓词公式２-7

谓词演算的推理理论2－6前束范式谓词逻辑２-4谓词公式的解释２-5等价式与蕴含式第39页，共117页，2023年，2月20日，星期二定义2-5.2,2-5.3如果公式A在任何解释下均为真,称A为永真式;如果

A在某个解释I和I的一个赋值下为真,称A可满足;如果公式在任何解释下均为假,称A为永假式.2-5等价与蕴含1.永真式当个体域有限时,原则上可用真值表法判定一公式永真永假或可满足；但当个体域无限时,真值表法失效.代入定理、等价演算

永真(永假)式的判定：谓词逻辑>等价与蕴含式第40页，共117页，2023年，2月20日，星期二命题逻辑永真式（永假式）的代换实例是谓词逻辑的永真式（永假式）。设A是包含命题变元P1,P2,...Pn的命题公式,B1,B2,...Bn是谓词公式,用B1,B2,...Bn分别代替P1,P2,...Pn

在A中的所有出现,得到的谓词公式B称A的代换实例,命题逻辑永真式的代换实例称为重言式.谓词逻辑>等价与蕴含式命题逻辑的代入定理:一个重言式,对同一分量都用任何合式公式置换,结果仍重言.第41页，共117页，2023年，2月20日，星期二谓词逻辑>等价与蕴含式上式可看作命题公式PP的代入实例1)(x)P(x)(x)P(x)

2)(xP(x)(xQ(x)xP(x)))

上式可看作命题公式(P(QP))的代入实例而(P(QP))(P(QP))F所以,(xP(x)(xQ(x)xP(x)))为永假式而PPT,所以,(x)P(x)(x)P(x)为重言式判定公式的类型重言式是永真式,但永真未必重言.

例如xP(x)xP(x)是永真式，但不是重言式.补例第42页，共117页，2023年，2月20日，星期二2.等价与蕴含定义

2-5.1

设A,B是公式,若AB是永真式,则称A,B等价.记作AB.等价式的判定等价演算:利用基本公式、等价的性质和置换

定理，推演出其他等价式.定义

2-5.2

设A,B是公式,若AB是永真式,则称A蕴含B.记作AB.谓词逻辑>等价与蕴含式AB当且仅当AB且BA第43页，共117页，2023年，2月20日，星期二(1)命题公式的推广例如PQPQ

用

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页，2023年，2月20日，星期二(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页，2023年，2月20日，星期二(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页，2023年，2月20日，星期二(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)B(x)第47页，共117页，2023年，2月20日，星期二(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页，2023年，2月20日，星期二(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.1同理可得谓词逻辑>等价与蕴含式第49页，共117页，2023年，2月20日，星期二(6)多个量词的使用公式中多个量词的出现次序关系到命题的含义,不能随意交换.例如xyA(x,y):对任意x,都存在y,使得A成立.例(x)(y)(x+y=0)为真命题,y=-x

yxA(x,y)

:存在着y,对所有的x都有A成立.(y)(x)(x+y=0)为假命题∵谓词逻辑>等价与蕴含式

y的值独立于x.y的值依赖于x.第50页，共117页，2023年，2月20日，星期二特殊情况:全称量词之间可交换,存在量词之间可交换.全称与存在之间存在如下关系: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)谓词逻辑>等价与蕴含式xyyxyxyxyxxy

xyyx第51页，共117页，2023年，2月20日，星期二例题谓词逻辑>等价与蕴含式右式验证(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页，2023年，2月20日，星期二例题谓词逻辑>等价与蕴含式

(x)P(x)

(x)P(x)

分析真值法:左右且右左.给定公式(x)P(x)(x)P(x)一组解释I,若(x)P(x)

在I下为真,则(x)P(x)为假,即存在aD,使P(a)为假,即P(a)为真,即(x)P(x)为真.给定(x)P(x)(x)P(x)一组解释I,若(x)P(x)在I下为真,则存在aD,使P(a)为真,即P(a)为假,即(x)P(x)为真.则(x)P(x)为假,第53页，共117页，2023年，2月20日，星期二２-1谓词的概念与表示２-2量词２-3谓词公式２-5等价式与蕴含式２-7

谓词演算的推理理论2－6前束范式谓词逻辑２-4谓词公式的解释第54页，共117页，2023年，2月20日，星期二谓词逻辑>前束范式2-6前束范式定义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.1

任一谓词公式,均和一个前束范式等价.第55页，共117页，2023年，2月20日，星期二化前束范式的方法(1).将公式中的连接词化为,,.(非必须)

(2).利用否定律,德.摩根律,及量词转化律,将否定深入到谓词字母前.

(3).利用换名规则或代入规则使所有约束变元均不相同且使所有的自由变元与约束变元不同.

(4).利用量词的的扩张与收缩,扩大量词的辖域至整个公式.谓词逻辑>前束范式例如(x)P(x,y)Q(x)(x)P(x)(x)Q(x)第56页，共117页，2023年，2月20日，星期二因为(x)P(x)(y)P(y),(x)P(x)(y)P(y),所以,若谓词公式中有变元既约束出现,又自由出现,为避免混淆,可对约束变元进行换名或对自由变元代入,使得一个变元在公式中只呈一种出现.

(1)对约束变元换名,其更改的变元名称范围是:量词中的指导变元及该量词辖域中出现的该变元,而公式中其余变元不变.(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页，2023年，2月20日，星期二代入规则(1).代入须对公式中该自由变元的所有出现同时进行.(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页，2023年，2月20日，星期二(□v1)(□v2)…(□vn)(其中□可能是量词或,vi(i=1,2,…,n)是指导变元,Aij是原子公式或其否定。定义2-6.2

一个wffA如果具有如下形式称为前束合取范式例如

(x)(z)(y)((

P(x,y)

(z=b))

(Q(y)(a=b)))定理2-6.2

每一个wffA都可以转换为与它等价的前束合取范式。谓词逻辑>前束范式第59页，共117页，2023年，2月20日，星期二其中□可能是量词或,vi(i=1,2,…,n)是客体变元,Aij是原子公式或其否定。定义2-6.3一个wffA如果具有如下形式称为前束析取范式例如(x)(z)(y)((

P(x,y)

(z=b))

(Q(y)(a=b)))定理2-6.3每一个wffA都可以转换为与它等价的前束析取范式。(□v1)(□v2)…(□vn)(谓词逻辑>前束范式第60页，共117页，2023年，2月20日，星期二谓词逻辑>前束范式化前束范式的方法(1).将公式中的连接词化为,,.(非必须)(2).利用否定律,德.摩根律,及量词转化律,将否定深入到谓词字母前.(3).利用换名规则或代入规则使所有约束变元均不相同且使所有的自由变元与约束变元不同.(4).利用量词的的扩张与收缩,扩大量词的辖域至整个公式.前束范式：(□v1)(□v2)...(□vn)A第61页，共117页，2023年，2月20日，星期二谓词逻辑>前束范式例题xyz(P(x,z)P(y,z))uQ(x,y,u)化为前束析取范式.第62页，共117页，2023年，2月20日，星期二谓词逻辑>前束范式例题x[yP(x)zQ(z,y)

yR(x,y)]的前束合取范式原式消去多余x[P(x)zQ(z,y)y

R(x,y)]换名x[P(x)zQ(z,y)wR(x,w)]自由w消去其它x[(P(x)zQ(z,y))wR(x,w)]否定深入x[(P(x)zQ(z,y))wR(x,w)]量词提出x

zw[(P(x)Q(z,y))R(x,w)]分配律xzw[(P(x)R(x,w)]

(Q(z,y))R(x,w)]量词w联结词前束析取范式第63页，共117页，2023年，2月20日，星期二作业2-5（4）,（6）2-6(1)(a)(2)(a),(b)谓词逻辑>前束范式本节重点掌握的概念:谓词演算的永真式，重言式，等价式,蕴含式;前束范式.本节重点掌握的方法:证明永真式，等价式,求前束合取范式,析取范式.第64页，共117页，2023年，2月20日，星期二２-1谓词的概念与表示２-2量词２-3谓词公式２-5等价式与蕴含式2－6前束范式谓词逻辑２-4谓词公式的解释２-7

谓词演算的推理理论第65页，共117页，2023年，2月20日，星期二2-7谓词演算的推理理论设H1,H2…Hn和C是谓词公式,当且仅当H1H2…,HnC称C是一组前提H1,H2…Hn的有效结论.等价演算、分析真值、证明法。判定谓词公式永真的各种方法都可用于判断推理正确性谓词逻辑>谓词演算的推理...等价演算：AB即ABT例：

xP(x)

xQ(x)x（P(x)Q(x)）分析真值：设前件在一组解释下为真,推出后件也真；或证明后件在一组解释下为假时，前件也为假。第66页，共117页，2023年，2月20日，星期二要证C是一组前提H1,H2…Hn的有效结论,需证:H1H2…,HnC是重言式即证:H1,H2…Hn均为真时,C必为真.为描述这样一个推理过程,可构造一个命题公式序列:其中每个公式或是前提,或是由某些前提利用推理规则推出的.序列的最后一个命题公式就是所要结论.这样一个描述推理过程的命题公式序列称为形式论证(证明或演绎法).证明法谓词逻辑>谓词演算的推理...第67页，共117页，2023年，2月20日，星期二P规则(前提引入规则):前提在推理过程中的任何时候均可引用.T规则(结论引入规则):在推理过程中,如有一个或多个公式蕴含公式S,则S可引入推导过程.推理规则命题逻辑>推理理论

由于谓词公式中包含量词,还需增加一组处理量词的推理规则.

首先命题逻辑中的推理规则都可应用于谓词逻辑的推理中:第68页，共117页，2023年，2月20日，星期二谓词逻辑>谓词演算的推理...(1)全称指定规则US含义:若D中所有个体使A真,则

D中任一个体t也使A真.例

⑴(x)(y)(x<y)P(不存在最大实数)例

⑴(x)P(x):所有的人都是要死的P

⑵P(a):苏格拉底是要死的.US⑵(y)(a<y)US

或⑵(y)(x<y)US(y)(y<y)?或⑵P(x):x是要死的.US使用限制:t不能与其它指导变元同名.第69页，共117页，2023年，2月20日，星期二(2)全称推广规则UG含义:若D中任意一个体使A真,则D中所有个体都使A真.使用限制:x不能是前提中的自由变元.例:P(x):x是偶数D:正整数.(1)P(x)P(2)(x)P(x)UG?谓词逻辑>谓词演算的推理...第70页，共117页，2023年，2月20日，星期二(3)存在指定规则ES含义:若D中存在个体使A真,则D中必有某个体c使A真.使用限制:(x)A(x)为闭式,c为一个新常元(歧义名称).(4)存在推广规则EG含义:若项t使A真,则D中存在个体使A为真.谓词逻辑>谓词演算的推理...使用限制:x不能与A(t)中的自由变元或指导变元同名第71页，共117页，2023年，2月20日，星期二例

(2)(y)(x

<y)US

(3)x

<aES(1)(x)(y)(x<y)P取D:有理数(4)(x)(x<a)UG(5)(y)(x)(x<y)EG谓词逻辑>谓词演算的推理...不是闭式例

(2)F(a)

ES

证明:

(x)F(x)F(a)

(1)(x)F(x)P不是新常元第72页，共117页，2023年，2月20日，星期二(1)(x)Q(x)P(2)(x)Q(x)P(3)Q(a)T1,ES(4)Q(a)T2,ES(5)Q(a)Q(a)T3,4(6)(x)(Q(x)Q(x))T5,EG

例Q(x):x是有理数D:实数(1)(x)Q(x)P(2)(x)Q(x)P(3)Q(a)T1,ES(4)Q(b)T2,ES(5)...谓词逻辑>谓词演算的推理...不是新常元第73页，共117页，2023年，2月20日，星期二例

(2)(x)F(x)

P

(3)F(a)G(a),

US(1)(x)(F(x)G(x))P前提:(x)(F(x)G(x)),(x)F(x)结论:(x)G(x)(4)F(a)ES(5)G(a)EG不是新常元(6)(x)G(x)

EG

(2)(x)F(x)

P

(4)F(a)G(a)

ES(1)(x)(F(x)G(x))P(3)F(a)UG(5)G(a)EG(6)(x)G(x)

EG谓词逻辑>谓词演算的推理...第74页，共117页，2023年，2月20日，星期二谓词逻辑>谓词演算的推理...例题1证明(x)(H(x)M(x))H(s)M(s)证明(1).(x)(H(x)M(x))P(2).H(s)M(s) US,T1(3).H(s) P(4).M(s) T2,3,I13(苏格拉底三段论)P76例题1第75页，共117页，2023年，2月20日，星期二命题逻辑>逻辑连接词例题2证明(x)(C(x)W(x)R(x))(x)(C(x)

Q(x))(x)(Q(x)R(x))证明(1).(x)(C(x)Q(x))

P(2).C(a)Q(a

)

T2,ES(3).C(a)T3,I1(5).(x)(C(x)W(x)R(x))P(6).C(a)W(a)R(a)

T1,3,US(4).Q(a)T3(7).W(a)R(a)T4,5,I(8).R(a)T6,I(9).Q(a)R(a)T7,8,I1P77例题2(10).(x)(Q(x)R(x))T9,EG第76页，共117页，2023年，2月20日，星期二命题逻辑>逻辑连接词例题3(x)(P(x)

Q(x))(x)P(x)(x)Q(x)(CP规则)

x(P(x)Q(x))xP(x)xQ(x)

(1).

xP(x)附加P

(2).

xP(x)T1,E

(3).

P(c))T2,ES

(6).

Q(c))

T3,5,I

(4).

x(P(x)Q(x))

P(7).xQ(x)T6,ES(5).P(c)Q(c)

T4,US(8).xP(x)xQ(x)CP规则P77例题3第77页，共117页，2023年，2月20日，星期二例题3(x)(P(x)

Q(x))(x)P(x)(x)Q(x)(归谬法)(1).((x)P(x)(x)Q(x))

附加P(2).(x)P(x)(x)Q(x))

T1,E(3).(x)P(x)T2,E(4).(x)P(x)T3,E(5).(x)Q(x))

T2,I1(6).(x)Q(x))

T5,E(7).P(c))

T4,ES(8).Q(c))

T6,US(9).P(c)Q(c)T7,8,I(10).(P(c)Q(c))T9,E(11).(x)(P(x)Q(x))

P(13).(P(c)Q(c))(P(c)

Q(c))T10,12(12).P(c)Q(c)T11,USP77例题3第78页，共117页，2023年，2月20日，星期二命题逻辑>逻辑连接词补例所有的有理数是实数.某些有理数是整数.因此,某些实数是整数.

设:R(x):x是实数

Q(x):x是有理数P(x):x是整数x(Q(x)R(x)),(x)(Q(x)P(x))

(x)(R(x)P(x))x（Q(x)R(x)）(x)(Q(x)P(x))(x)(R(x)P(x))第79页，共117页，2023年，2月20日，星期二命题逻辑>逻辑连接词补例每个用功的学生考试不会不及格。小张是用功的学生。所以，小张考试及格。设:P(x):x考试及格Q(x):x是学生R(x):x是用功的。a:小张x（Q(x)R(x)P(x)）R

(a)Q(a)

P

(a)Q(a)第80页，共117页，2023年，2月20日，星期二命题逻辑>逻辑连接词4.设R(x):x是实数,P(x):x是有理数,“并非每个实数都是有理数”符号化为()A.x((R(x)P(x))B.

x(R(x)P(x))

5.谓词公式xP(x)xQ(x)xP(x)的类型是____.6.在解释I:DI={1,2},P(1,1)=P(1,2)=0,P(2,2)=P(2,1)=1下,谓词公式

x

yP(x,y)的真值为_____.7.公式xP(x)xQ(x,y)前束合取范式为______.课堂练习1.在谓词逻辑中,永真式都是重言式。()2.任意谓词公式都有唯一的前束范式与之等价。()3.(x)(A(x)B(x))(x)A(x)(x)B(x)()

第81页，共117页，2023年，2月20日，星期二命题逻辑>逻辑连接词8所有的有理数是实数.所有的无理数是实数.虚数不是实数，所以虚数不是有理数也不是无理数.设:R(x):x是实数

Q(x):x是有理数P(x):x是无理数。S(x):x是虚数x（Q(x)R(x)）

x（P(x)R(x)）x（S(x)R(x)）x（S(x)Q(x)

P(x)）第82页，共117页，2023年，2月20日，星期二命题逻辑>逻辑连接词作业2-7（1）（a）,（b）（2）本节重点掌握的概念:4个推理规则本节重点掌握的方法:推理的形式证明方法第83页，共117页，2023年，2月20日，星期二谓词逻辑PredicateLogic第二章本章小结谓词逻辑小结第84页，共117页，2023年，2月20日，星期二谓词逻辑小结一.谓词的概念和表示量词和特性谓词谓词重点掌握的基本概念和方法(一)个体和个体域谓词公式的翻译(命题符号化)一元谓词:A(x)n元谓词:A(x1,...xn)个体常元:a,b,c...个体变元:x,y,z...D:个体域全称量词:(x)A(x)存在量词:(x)A(x)

(x)(P(x)A(x))(x)(P(x)A(x))特性谓词P(x)第85页，共117页，2023年，2月20日，星期二谓词逻辑小结重点掌握的基本概念和方法(二)二.谓词公式及其解释谓词公式的递归定义谓词公式的解释与赋值变元的约束求谓词公式在一组解释下的真值有限域无限域指导变元与辖域自由变元与约束变元开式与闭式1).指定个体域DI.2).指定个体常元3).指定个体函数.4).指定谓词5).指定自由变元开式闭式第86页，共117页，2023年，2月20日，星期二谓词逻辑小结三.公式类型及相互关系重点掌握的基本概念和方法(三)判别公式的类型或等价公式的类型等价公式AB:即

AB永真蕴含公式AB:即AB永真代入定理等价演算分析真值永真式与重言式永假式

可满足式ABIffAB且BA第87页，共117页，2023年，2月20日，星期二谓词逻辑小结四