离散数学左孝陵版答案省公共课一等奖全国赛课获奖课件.pptx

Charter twonwelcome第1页第二章第二章 谓词逻辑谓词逻辑n1 谓词概念与表示法n2 命题函数与量词n3 谓词公式与翻译n4 变元约束n5 谓词演算等价式与蕴含式n6 前束范式n7 谓词演算推理理论第2页1 谓词概念与表示法在研究命题逻辑中，原子命题是命题演算中最基本单位，不再对原子命题进行分解，这么会产生二大缺点：（1）不能研究命题结构，成份和内部逻辑特征；（2）也不可能表示二个原子命题所含有共同特征，甚至在命题逻辑中无法处理一些简单又常见推理过程。例：苏格拉底论证是正确，但不能用命题逻辑推理规则推导出来。“全部人总是要死。A “苏格拉底是人。B “所以苏格拉底是要死。”C第3页1 谓词概念与表示法1.谓词：谓词：定义定义：用以刻划客体性质或关系即是谓词谓词。我们可把陈说句分解为二部分：主语（名词，代词）和谓语（动词）。例：张华是学生，李明是学生。则可把它表示成：H:表示“是学生”，j:表示“张华”，m:表示“李明”，则可用以下符号表示上述二个命题：H(j)，H(m)。H作为“谓词”（或者谓词字母）用大写英文字母表示，j,m为主语，称为“客体”或称“个体”。第4页1 谓词概念与表示法（1）谓词填式）谓词填式：谓词字母后填以客体所得式子。例：H(a,b)（2）若谓词字母联络着一个客体，则称作一元谓词一元谓词；若谓词字母联络着二个客体，则称作二元谓词二元谓词；若谓词字母联络着n个客体，则称作n元谓词元谓词。（3）客体次序必须是有要求。例：河南省北接河北省。n L b写成二元谓词为：L(n,b)，但不能写成L(b,n)。第5页2 命题函数与量词命题函数与量词1.命题函数命题函数客体在谓词表示式中能够是任意名词。例：C“总是要死。”j：张三；t：老虎；e：桌子。则C(j),C(t),C(e)均表示了命题。在上面例子中，C：表示“总是要死”；x：表示变元（客体变元），则C(x)表示“x总是要死”，则称C(x)为命题函数。定义定义由一个谓词字母和一个非空客体变元集合所组成表示式，称为简单命题函数。第6页2 命题函数与量词命题函数与量词讨论定义：（a）当简单命题函数仅有一个客体变元时，称为一元简单命题函数；（b）若用任何客体去取代客体变元之后，则命题函数就变为命题；（c）命题函数中客体变元取值范围称为个体域（叙述域）。例：P(x)表示x是质数。这是一个命题函数。其值取决于个体域。能够将命题函数命题，有两种方法：第7页2 命题函数与量词命题函数与量词a)将x取定一个值。如：P(4)，P(5)b)将谓词量化。如：xP(x)，xP(x)个体域给定形式有二种：详细给定。如：j,e,t全总个体域任意域：全部个体从该域中取得。第8页2 命题函数与量词命题函数与量词2.量词量词（1）全称量词“”为全称量词符号，读作“对于全部”，“对任一个”，“对一切”。例：“这里全部都是苹果”可写成：xA(x)或(x)A(x)几个形式读法：xP(x)：“对全部x，x是”；xP(x)：“对全部x，x不是”；xP(x)：“并不是对全部x，x是”；xP(x)：“并不是全部x，x不是”。第9页2 命题函数与量词命题函数与量词例：将“对于全部x和任何y，假如x高于y，那么y不高于x”写成命题表示形式。解：x y(G(x,y)G(y,x)G(x,y)：x高于y（2）存在量词“”为存在量词符号，读作“存在一个”，“对于一些”，“对于一些”，“最少存在一个”，“这里存在着这么”等等。“”表示式读法：x A(x)：存在一个x,使x是；xA(x)：存在一个x,使x不是；x A(x)：不存在一个x,使x是；xA(x)：不存在一个x,使x不是。第10页2 命题函数与量词命题函数与量词例：（a）存在一个人；（b）某个人很聪明；（c）一些实数是有理数 将（a）,（b）,（c）写成命题。解：要求：M(x)：x是人；C(x)：x是很聪明；R1(x)：x是实数(特征谓词)R2(x)：x是有理数。则 （a）x M(x)；（b）x(M(x)C(x)；（c）x(R1(x)R2(x)。（3）量化命题真值：决定于给定个体域给定个体域：a1an以a1an中每一个代入xP(x)P(a1)P(an)xQ(x)Q(a1)Q(an)第11页3谓词公式与翻译谓词公式与翻译1.谓词公式原子谓词公式：不出现命题联结词和量词谓词命名式称为原子谓词公式，并用P(x1xn)来表示。（P称为n元谓词，x1xn称为客体变元），当n=0时称为零元谓词公式。定义（谓词公式归纳法定义）原子谓词公式是谓词公式；若A是谓词公式，则A也是谓词公式；若A,B都是谓词公式，则(AB),(AB),(AB),(AB)都是谓词公式；若A是谓词公式，x是任何变元，则xA,xA也都是谓词公式；第12页3谓词公式与翻译谓词公式与翻译只有按-所求得那些公式才是谓词公式（谓词公式又简称“公式”）。例1：任何整数或是正，或是负。解：设：I(x):x是整数；R1(x)：x是正数；R2(x)：x是负数。此句可写成：x(I(x)(R1(x)R2(x)。例2：试将苏格拉底论证符号化：“全部人总是要死。因为苏格拉底是人，所以苏格拉底是要死。”解：设M(x)：x是人；D(x)：x是要死；M(s)：苏格拉底是人；D(s)：苏格拉底是要死。第13页3谓词公式与翻译谓词公式与翻译写成符号形式：x(M(x)D(x)，M(s)D(s)2.因为对个体描述性质刻划深度不一样，可翻译成不一样形式谓词公式。第14页4变元约束变元约束1.辖域：紧接在量词后面括号内谓词公式。例：xP(x),x(P(x)Q(x)。若量词后括号内为原子谓词公式，则括号能够省去。2.自由变元与约束变元约束变元：在量词辖域内，且与量词下标相同变元。自由变元：当且仅当不受量词约束。例：xP(x,y),x(P(x)y(P(x,y)。第15页4变元约束变元约束3.约束变元更名规则任何谓词公式对约束变元能够更名。我们认为xP(x,y)和zP(z,y)是一等价谓词公式，不过需注意，不能用同一变元去表示同一谓词公式中二个变元。比如：yP(y,y)是不正确。下面介绍约束变元更名规则：（a）在更名中要把公式中全部相同约束变元全部同时改掉；（b）更名时所用变元符号在量词辖域内未出现。第16页4变元约束变元约束例：xP(x)yR(x,y)可改写成xP(x)zR(x,z)，但不能改成xP(x)xR(x,x)，xR(x,x)中前面x原为自由变元，现在变为约束变元了。4.区分是命题还是命题函数方法（a）若在谓词公式中出现有自由变元，则该公式为命题函数；（b）若在谓词公式中变元均为约束出现，则该公式为命题。例：xP(x,y,z)是二元谓词，yxP(x,y,z)是一元谓词，而谓词公式中假如没有自由变元出现，则该公式是一个命题。第17页4变元约束变元约束举例：例1：“没有不犯错人。”解：设F(x)为“x犯错误”，M(x)为“x是人”（特征谓词）。可把此命题写成：(x(M(x)F(x)x(M(x)F(x)例2：“x是y外祖父”“x是z父亲且z是y母亲”设P(z)：z是人；F(x,z)：x是z父亲；M(z,y)：z是y母亲。则谓词公式可写成：z(P(z)F(x,z)M(z,y)。5.代入规则：代入规则：对公式中自由变元更改叫做代入。(a)对公式中出现该自由变元每一处进行代入，(b)用以代入变元与原公式中全部变元名称不能相同。第18页4变元约束变元约束6.个体域（叙述域，客体域）:用特定集合表示被约束变元取值范围。(1)个体域不一样，则表示同一命题谓词公式形式不一样。例：“全部人必死。”令D(x)，x是要死。下面给出不一样个体域来讨论：()个体域为：人类，则可写成xD(x)；()个体域为任意域（全总个体域），则人必须首先从任意域中分离出来，设M(x)，x是人，称M(x)为特征谓词。命题可写成 x(M(x)D(x)第19页4变元约束变元约束（2）个体域不一样，则表示同一命题值不一样。Q(x):x5-1,0,3-3,6,215,30 xQ(x)T F FxQ(x)T T F（3）对于同一个体域，用不一样量词时，特征谓词加入方法不一样。对于全称量词，其特征谓词以前件方式加入；对于存在量词，其特征谓词以与形式加入。第20页4变元约束变元约束例：设个体域为:白虎（白猫），黄咪（黄猫），同时令C(x)：x是猫（特征谓词）；B(x)：x是黑色；A(x)：x是动物。（）描述命题：“全部猫都是动物”。即：x(C(x)A(x)（T）（真命题）写成x(C(x)A(x)（F）则为假命题了。x(C(x)A(x)TT T TT x(C(x)A(x)TT F FF（）描述命题：“一些猫是黑色”。x(C(x)B(x)FF F F F而 x(C(x)B(x)F F T TT第21页4变元约束变元约束7.量词对变元约束，往往与量词次序相关。例：yx(xy-2)表示任何y都有x，使得x3,则可写出：xP(x)P(0)P(1)P(i)xP(x)P(0)P(1)P(i)下面分类介绍在谓词公式中含有量词等价式和永真蕴含式。（1）量词转换律：E25(Q3)xP(x)xP(x)E26(Q4)xP(x)xP(x)下面证实：设个体域为：S=a1,a2,an 第27页5谓词演算谓词演算 等价式与蕴含式等价式与蕴含式 xP(x)(P(a1)P(a2)P(an)P(a1)P(a2)P(an)xP(x)下面举例说明量化命题和非量化命题差异:否定形式不一样例：否定以下命题：(a)上海是一个小城镇 A(s)(b)每一个自然数都是偶数 x(N(x)E(x)上述二命题否定为：(a)上海不是一个小城镇 A(s)(b)有一些自然数不是偶数 x(N(x)E(x)x(N(x)E(x)x(N(x)E(x)x(N(x)E(x)第28页5谓词演算谓词演算 等价式与蕴含式等价式与蕴含式结论：对于非量化命题否定只需将动词否定，而对于量化命题否定不但对动词进行否定而且对量词同时进行否定，其方法是：x否定变为x，x否定变为x。（2）量词辖域扩张及其收缩律 E27(Q6)xA(x)P x(A(x)P)(Q7)xA(x)P x(A(x)P)E28(Q9)xA(x)P x(A(x)P)(Q8)xA(x)P x(A(x)P)P为不含有变元任何谓词公式第29页5谓词演算谓词演算 等价式与蕴含式等价式与蕴含式证实E27(Q6)，设个体域为：S=a1,a2,an xA(x)P(A(a1)A(a2)A(an)P (A(a1)P)(A(a2)P)(A(an)P)x(A(x)P)E30(Q14)xA(x)B x(A(x)B)E31(Q15)xA(x)B x(A(x)B)E32(Q16)AxB(x)x(AB(x)E33(Q17)A x B(x)x(AB(x)证实E30(Q14)，设个体域为：S=a1,a2,an x(A(x)B)(A(a1)B)(A(an)B)(A(a1)B)(A(an)B)第30页5谓词演算谓词演算 等价式与蕴含式等价式与蕴含式 (A(a1)A(an)B x A(x)B x(A(x)B)xA(x)B（3）量词分配律E24(Q10)x(A(x)B(x)xA(x)xB(x)E23(Q11)x(A(x)B(x)xA(x)xB(x)I18(Q12)x(A(x)B(x)xA(x)xB(x)I17(Q13)xA(x)xB(x)x(A(x)B(x)E29(Q18)x(A(x)B(x)xA(x)xB(x)I19(Q19)xA(x)xB(x)x(A(x)B(x)第31页5谓词演算谓词演算 等价式与蕴含式等价式与蕴含式证实E24(Q10)和I19(Q19)，设个体域为：S=a1,a2,anE24(Q10)x(A(x)B(x)(A(a1)B(a1).(A(an)B(an)(A(a1)A(an)(B(a1)B(an)xA(x)x B(x)I19(Q19)xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)(A(a1)A(an)(B(a1)B(an)(A(a1)B(a1)(A(a1)B(an)(A(an)B(a1)(A(an)B(an)第32页5谓词演算谓词演算 等价式与蕴含式等价式与蕴含式 (A(a1)B(a1)(A(an)B(an)x(A(x)B(x)x(A(x)B(x)（4）量词添加和除去永真蕴含式 Q1 xP(x)P(y)Q2 P(y)xP(x)Q5 xP(x)xP(x)xP P xP P(P为不含x变元）Y是个体域中任一元素第33页5谓词演算谓词演算 等价式与蕴含式等价式与蕴含式（5）含有多个量词永真式：（）量词出现次序直接关系到命题含义：“xy”表示：“不论选定一个什么样x值总能找到一个y能使x和y”“yx”表示：“只选取一个y值，以致不论怎样选定一个x，能够使y和x”下面列出对应表示式能够看出其不一样处：设x个体域为：a1,a2,an，y个体域为：b1,b2,bn，则：xyP(x,y)yP(a1,y)yP(an,y)第34页5谓词演算谓词演算 等价式与蕴含式等价式与蕴含式 (P(a1,b1)P(a1,bn)(P(an,b1)P(an,bn)yxP(x,y)xP(x,b1)xP(x,bn)(P(a1,b1)P(an,b1)(P(a1,bn)P(an,bn)例：x,y个体域鞋子，P(x,y):和配成一双鞋子。xyP(x,y)T yxP(x,y)F第35页5谓词演算谓词演算 等价式与蕴含式等价式与蕴含式（）在含有多个量词谓词公式中,xy,xy位置是能够改变,且不影响命题真值。例：x,y个体域为N=0,1,2，则 xyP(x,y)yP(0,y)yP(i,y)(P(0,0)P(0,1)P(0,j)(P(i,0)P(i,1)P(i,j)(P(0,0)P(1,0)P(i,0)(P(0,1)P(1,1)P(i,1)xP(x,0)xP(x,1)xP(x,j)yxP(x,y)第36页5谓词演算谓词演算 等价式与蕴含式等价式与蕴含式一样：xyP(x,y)yxP(x,y)（）量词转换律推广应用:把深入到谓词公式前面去方法。xyzP(x,y,z)x yzP(x,y,z)xyzP(x,y,z)xyzP(x,y,z)（）两个量词,所组成谓词公式等价式和永真蕴含式（8个）xyP(x,y)yxP(x,y)xyP(x,y)yxP(x,y)yxP(x,y)xyP(x,y)yxP(x,y)xyP(x,y)第37页5谓词演算谓词演算 等价式与蕴含式等价式与蕴含式 xyP(x,y)yxP(x,y)xyP(x,y)yxP(x,y)yxP(x,y)xyP(x,y)xyP(x,y)yxP(x,y)（6）谓词公式对偶式定义定义 在一个谓词公式A中（其中不出现,词）把公式A中,F,T,变为公式A*中,T,F,则称A*是A对偶式。定理定理 若谓词公式A B，则A*B*；若谓词公式A B，则B*A*（这里A,B有一样个体域）。第38页5谓词演算谓词演算 等价式与蕴含式等价式与蕴含式例：I17(Q13)xA(x)xB(x)x(A(x)B(x)I18(Q12)xA(x)xB(x)x(A(x)B(x)第39页6 前束范式前束范式定义定义一个公式，假如量词均非否定地在全式开头，它们作用域延伸到整个公式末尾，则称此公式叫前束范式。例：xyz(Q(x,y)R(z)(前束范式)定理定理 任何一个谓词公式均和一个前束范式等价。证实：利用量词转换把深入到原子谓词公式前,利用约束变元更名规则，利用量词辖域扩张收缩律,把量词移到全式最前面，这么一定可得到等价前束范式。第40页6 前束范式前束范式例：xP(x)R(x)yP(y)R(x)y(P(y)R(x)例：把xP(x)xQ(x)变成前束范式。xP(x)xQ(x)xP(x)xQ(x)xP(x)xQ(x)x(P(x)Q(x)第41页7谓词演算推理理论谓词演算推理理论1.含有量词特殊永真式含有量词特殊永真式定义定义 设A(x)是一个谓词公式，x是其中自由变元，若把y代入到A(x)里而不会产生变元新约束出现，则称A(x)对于y是自由。例：下面A(x)对于y是自由：A(x)zP(z)Q(x,z),这里x为自由变元,若用y去取代A(x)中x,A(y)zP(z)Q(y,z),这里y也仍为自由变元；第42页7 谓词演算推理理论谓词演算推理理论下面A(x)对于y不是自由：A(x)y(S(x)S(y),x为自由变元，若用y代入A(x)x中去得：A(y)y(S(y)S(y)，y变为约束变元了，产生了新约束出现。如有必要代入y，则应先将式中约束变元y更名。z(S(x)S(z)然后代入y z(S(y)S(z)y仍为自由变元。归结归结：判定A(x)对于y是自由，只要看公式A(x)中y,y辖域内有没有x自由出现就行：若有x自由出现则A(x)对于y不是自由，若无x自由出现则一定能够必定A(x)对于y是自由。第43页7 谓词演算推理理论谓词演算推理理论下面分别介绍四个推理规则（1）全称指定规则（US规则）。假如对个体域中全部客体x,A(x)成立，则对个体域中某个任意客体c，A(c)成立。该规则表示成：xA(x)A(c)(x,c个体域)（2）全称推广规则（UG规则）假如能够证实对个体域中每一个客体c，命题A(c)都成立，则可得到结论xA(x)成立。该规则表示成：A(x)xA(x)第44页7 谓词演算推理理论谓词演算推理理论（3）存在指定规则（ES规则）假如对于个体域中一些客体A(x)成立，则必有某个特定客体c，使A(c)成立。该规则表示成：xA(x)A(c)例：x个体域为I=整数，P(x):x是偶数，Q(x):x是奇数。xP(x)xQ(x)T 但P(c)Q(c)F第45页7 谓词演算推理理论谓词演算推理理论（4）存在推广规则（EG规则）假如对个体域中某个特定客体c，有A(c)成立，则在个体域中，必存在x，使A(x)成立。该规则表示成：A(c)xA(x)2 推论规则及使用说明推论规则及使用说明 命题逻辑中P,T,CP规则和简接证实法，都能够引用到谓词逻辑推论规则中来，不过要注意对量词做适当处理，其方法是：用US,ES在推导中去掉量词，用UG,EG使结论量化。第46页7谓词演算推理理论谓词演算推理理论规则使用说明：（1）在使用ES,US时一定要是前束范式（2）推导中连续使用US规则可用相同变元 xP(x)P(y),xQ(x)Q(y),（3）推导中既ES用，又用US，则必须先用ES，后用US方可取相同变元，反之不行。xP(x)P(y)xQ(x)Q(y)（4）推导中连续使用ES规则时，使用一次更改一个变元。第47页7谓词演算推理理论谓词演算推理理论例：证实苏格拉底论证x(M(x)D(x)M(s)D(s)(1)M(s)P(2)x(M(x)D(x)P(3)M(s)D(s)US(4)D(s)T例：证：x(H(x)M(x),xH(x)xM(x)第48页7谓词演算推理理论谓词演算推理理论(1)xH(x)P(2)H(c)ES(3)x(H(x)M(x)P(4)H(c)M(c)US(5)M(c)T(6)xM(x)EG例：证:x(P(x)Q(x)x P(x)xQ(x)(1)x P(x)引入前件(2)x(P(x)Q(x)P(3)P(c)Q(c)ES 第49页7谓词演算推理理论谓词演算推理理论(4)P(c)US(5)Q(c)T(6)xQ(x)EG(7)x P(x)xQ(x)CP例：证实：x(P(x)Q(x),xP(x)xQ(x)(1)xQ(x)假设前提(2)xQ(x)T(3)Q(c)US(4)xP(x)P 第50页7谓词演算推理理论谓词演算推理理论(5)P(c)US(6)P(c)Q(c)T(7)x(P(x)Q(x)UG(8)x(P(x)Q(x)P(9)x(P(x)Q(x)x(P(x)Q(x)T(10)F例：以下结论能否从前提中推出：x(P(x)Q(x),Q(a)x P(x)a为x个体域中一个元素(1)Q(a)P(2)x(P(x)Q(x)P第51页7谓词演算推理理论谓词演算推理理论(3)P(a)Q(a)US(4)P(a)T(5)x P(x)UG在使用US,ES,UG,EG这四条规则时,要注意严格按照它们要求去使用。第52页7谓词演算推理理论谓词演算推理理论书中例4证实：(1)x(y(S(x,y)M(y)z(P(z)R(x,z)P(2)y(S(b,y)M(y)z(P(z)R(b,z)US(1)(3)(z)P(z)附加前提(4)z(P(z)T(3)(5)P(a)US(4)(6)P(a)R(b,a)T(5)(7)(P(a)R(b,a)T(6)(8)z(P(z)R(b,z)UG(7)(9)z(P(z)R(b,z)T(8)第53页7谓词演算推理理论谓词演算推理理论(10)y(S(b,y)M(y)T(2)(9)(11)y(S(b,y)M(y)T(10)(12)(S(b,c)M(c)US(11)(13)S(b,c)M(c)T(12)(14)S(b,c)M(c)T(13)(15)y(S(b,y)M(y)UG(14)(16)xy(S(x,y)M(y)UG(15)(17)(z)P(z)xy(S(x,y)M(y)CP(3)(16)第54页7谓词演算推理理论谓词演算推理理论例：二个量词推理比较复杂：xP(x)x(P(x)Q(x)R(x),xP(x),xQ(x)x y(R(x)R(y)(1)xP(x)P(2)P(w)ES(3)P(w)Q(w)T(4)xP(x)x(P(x)Q(x)R(x)P(5)x(P(x)Q(x)R(x)T第55页7谓词演算推理理论谓词演算推理理论(6)P(w)Q(w)R(w)US(7)R(w)T(8)xR(x)EG(9)xQ(x)P(10)Q(z)ES(11)P(z)Q(z)T(12)P(z)Q(z)R(z)US第56页7谓词演算推理理论谓词演算推理理论(13)R(z)T(14)yR(y)EG(15)xR(x)yR(y)T(16)x y(R(x)R(y)T 三个量词推理过程更为复杂第57页第二章小结学习第二章要注意以下几点：(1)同一个命题在不一样个体域内可能有不一样符号化形式，同时也可能有不一样真值，因而在将一个命题符号化之前，必须搞清个体域。(2)在将命题符号化时，要尤其注意量词与联结词搭配。经常情况是全称量词与蕴含词搭配，存在量词与合取词搭配。所以有下面两种形式公式：x(A(x)B(x)x(A(x)B(x)而 x(A(x)B(x)x(A(x)B(x)第58页第二章小结与，与含义完全不一样。(3)记住主要等价式。会用约束变元和自由变元换名规则进行等价演算，求出给定公式前束范式。(4)在谓词演算推理证实中，要尤其注意US，UG，ES，EG规则成立条件。第59页例题选讲例1.符号化以下命题：(1)没有不犯错误人；(2)发光不都是金子；(3)在南京高校学习学生，未必都是南京籍学生。解：(1)设M(x)：x是人。Q(x)：x犯错误。本题符号化为：x(M(x)Q(x)或者：(x)(M(x)Q(x)(2)设L(x)：x是发光东西。G(x)：x是金子。x(L(x)G(x)或 x(L(x)G(x)第60页例题选讲(3)设S(x)：x是南京高校学习学生。F(x)：x是南京籍学生。则 x(S(x)F(x)本题也可加深刻划：S(x)：x是学生。L(x)：x在学习。H(x)：x在南京高校。G(x)：x是南京籍人。则(x)(S(x)L(x)H(x)G(x)S(x)第61页例题选讲例2.写出x(F(x)G(x)(xF(x)xG(x)前束范式。解：原式 x(F(x)G(x)(x)F(x)(x)G(x)(x)(F(x)G(x)(x)F(x)(x)G(x)(x)(F(x)G(x)G(x)(x)F(x)(x)(F(x)G(x)(x)F(x)(x)(F(x)G(x)(y)F(y)(x)(y)(F(x)G(x)F(y)第62页作业P8 1，5P111，5P184(c)，6，7(a),(b)P231，2，6，8(c),(d)P292，3P391，2(b)，3(b)，4(c),(f)，5(b)P461(a),(b)，2(a)，4(a)P591(d)(g)(h)，2(d)(i)(l)P621(f)(g)，5第63页作业P651(c)，2(c)，4P726，7P751(b)(c)P791(a)(d)，2(a)，3(b)第64页