数学离散数学.pptx

《数学离散数学.pptx》由会员分享，可在线阅读，更多相关《数学离散数学.pptx（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、上节课的内容谓词一元谓词n元谓词量词全称量词 存在量词 量词的辖域 自由变元与约束变元约束变元的改名规则第1页/共41页谓词演算的永真公式第2页/共41页谓词谓词等价等价的的定义定义 定义定义 1:两个任意谓词公式谓词公式A和和B,E是它们公有的论述域公有的论述域,若 (1)对公式A和和B中的谓谓词词变变元元,指派以任任一一在在E上上有有定定义义的的确定的谓词谓词。(2)对谓谓词词命命名名式式中的个个体体变变元元,指派以E中中的任任一一确定的个体个体。所得的命题命题都具有同样的有同样的真值真值,则称公式A和B遍及遍及E等价等价,记为：在在 E 上上 AB。定定义义 2:如果两谓词公式A和B,在

2、任任意意论论述述域域上上都等等价价,则称A和和B等价等价,记为 AB。第3页/共41页 定定义义3:给定任一谓谓词词公公式式 A,如果在 论论述述域域E 上,对公式A中的谓词谓词和个体个体变元进行 定义定义1中的两种指派两种指派,所得命题命题 (1)都真都真，则称A在在E上上有效有效或在E上永真永真。(2)至少有一个至少有一个是真,则称A在在E上上 可满足可满足。(3)都假都假,则称A在在E上上永假永假或在E上不可满足不可满足。谓词谓词公式公式的的分类分类 第4页/共41页 定定义义 4：给定任一谓谓词词公公式式A,如果在任任意意论论述述域域上上,对上述两种指派,(1)A永真永真,则称A永真永

3、真或有效有效。(2)A至少至少在一个域一个域上可满足可满足,则称A可满足可满足。(3)A永假永假,则称A永假永假或不可满足不可满足。若谓词公式A的个个体体域域是有有限限的,谓谓词词的的解解释释也有有限限,则可可用用真值表真值表判定判定谓词公式A是否永真是否永真。谓词谓词公式的公式的分类分类 第5页/共41页 例例：设P(x)仅可解释为:A(x):x是质数,B(x):x是合数。论述域论述域是3,4,判定谓词公式P(x)xP(x)是否永真是否永真。解解:(见右表)所以,P(x)xP(x)非永真式。第6页/共41页但是，当谓词的解释和个体变元的数量稍大,用真值表判定是否永真就难以实现。这时，一般利用

4、推导方法,因此,如同命题演算一样,首先要求出基本的永真公式,以作为推导的根据。第7页/共41页谓词演算的基本永真公式谓词演算的基本永真公式 1、首先，命题演算命题演算的永真公式永真公式也是谓词演算谓词演算的永真公式永真公式,基本的就是前面介绍的表 1.2-1(2)的逻辑恒等式逻辑恒等式和永真蕴含式永真蕴含式。第8页/共41页 2.含有量词含有量词的谓词演算的的谓词演算的基本永真公式基本永真公式。(i)xAA xAA 这里A是不不含含自自由由变变元元x的谓谓词词公公式式,因为A的真值与x无关,所以上述等价式成立。第9页/共41页(ii)xP(x)P(y)，或 xP(x)P(x)P(y)xP(x)

5、，或 P(x)xP(x)前一公式的意义是:如果断言“对一切x,P(x)是真”成立,那么对任一确定的x,P(x)是真。后一公式的意义是:如果对某一确定的x,P(x)是真,那么断言“存在一x,使P(x)是真”成立。根据前提三段论,从这两个公式可推得 xP(x)xP(x)第10页/共41页(iii)量词量词的的否定否定：(xP(x)x P(x)(xP(x)x P(x)由于“并非对一切x,P(x)是真”等价于“存在一些x,P(x)是真”,所以前一式成立。由于“并不存在一x,使P(x)是真”等价于“对一切x,P(x)是真”,所以后一式成立。第11页/共41页对比这两个式子,容易看出,如果把P(x)看作整

6、体,那么将x和x两者互换,可从一个式得出另一个式。这说明 x和和 x具有具有对偶性对偶性。另外,由于两个量词可以互相表达,所以有一个量词有一个量词就够就够了了。(xP(x)x P(x)(xP(x)x P(x)第12页/共41页例例：x y z(x+z=y)xy z(x+z=y)x yz(x+z=y)x y z (x+z=y)x y z(x+zy)第13页/共41页(iv)量词辖域量词辖域的扩张扩张和收缩收缩 xA(x)P x(A(x)P)xA(x)P x(A(x)P)xA(x)P x(A(x)P)xA(x)P x(A(x)P)其中P是不含自由变元是不含自由变元x的谓词。这里也可以看出 x和和

7、x具有具有对偶性对偶性。第14页/共41页 (v)量词量词的分配分配:x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)第个等价式的成立是由于对一切x,A(x)B(x)是真,等价于对一切x,A(x)是真并且对一切x,B(x)是真。第15页/共41页 第个公式可由第个公式推出。因为中的A(x),B(x)是任意的,所以可用 A(x),B(x)分别取代取代A(x)和和B(x),得 否定等价式两边否定等价式两边得 x(A(x)B(x)x A(x)x B(x)x (A(x)B(x)(xA(x)(xB(x)x(A(x)B(x)xA(x)xB(x)第16页/共41页第个公式是成

8、立的,因为存在一x使A(x)B(x)是真,所以存在一x使A(x)是真,同时存在一x使B(x)是真。但第个公式不不是是等价等价式式。例例：设A(x)和B(x)分别解释为“x是是奇奇数数”和“x是是偶偶数数”,论论述述域域是自自然然数数N,则xA(x)是真,xB(x)是真,所以xA(x)xB(x)是真,但x(A(x)B(x)是假,所以第个公式不等价不等价。(v)量词的分配:x(A(x)B(x)xA(x)xB(x)xA(x)xB(x)x(A(x)B(x)第17页/共41页 第个公式可由第个公式推出。用A(x)和B(x)分别取代取代A(x)和B(x),得 x(A(x)B(x)xA(x)xB(x)x(A

9、(x)B(x)(xA(x)(xB(x)否定等价式两边否定等价式两边，得：xA(x)xB(x)x(A(x)B(x)第18页/共41页(vi)量词对量词对 及 的处理处理只须应用它们对，的恒等式恒等式即可推出。例例：x(A(x)B(x)xA(x)xB(x)证证：x(A(x)B(x)x(A(x)B(x)xA(x)xB(x)xA(x)xB(x)第19页/共41页(vii)关于多个量词多个量词的永真式永真式:x yP(x,y)y x P(x,y)x yP(x,y)y x P(x,y)y xP(x,y)x y P(x,y)x yP(x,y)y x P(x,y)x yP(x,y)y x P(x,y)第20页

10、/共41页 注意注意：x yP(x,y)y xP(x,y)不成立不成立！例例:设P(x,y)表示 x+y=0,论述域论述域是有理数有理数集合。则 xy(x+y=0)是真,但 yx(x+y=0)是假。由此可知,一般情况下，一般情况下，量词的次序量词的次序是是不能随便颠倒不能随便颠倒的的。第21页/共41页当当论述域有限时论述域有限时，可将，可将谓词公式谓词公式展开为展开为命题公式命题公式证明。证明。例例：设论述域论述域为a0,a1,a2,an,则 xA(x)PA(a0)A(a1)A(a2)A(an)P(A(a0)P)(A(a1)P)(A(an)P)x(A(x)P)第22页/共41页表表 1.7-

11、1 含有量词的永真公式概要表含有量词的永真公式概要表 第23页/共41页谓词演算规则谓词演算规则1、代入规则、代入规则2、替换规则、替换规则3、对偶原理、对偶原理第24页/共41页 1.代入规则代入规则 (i)自自由由个个体体变变元元的的代代入入：在一公式中,任任一一自自由由个个体体变变元元可代代以以另另一一个个体体变变元元,只需该个个体体变变元元出现的各各处处都都同同样样代代入入,且代入的变元代入的变元不允许不允许在原来公式中以约束变元出现以约束变元出现。例例:在公式xP(x,y)Q(w,y)中,将y代以z,则得xP(x,z)Q(w,z)，将y代以w,则得xP(x,w)Q(w,w)。所得公式

12、称为原公式的代入实例代入实例。如果原式是如果原式是永真公式永真公式,则代入后仍得代入后仍得永真公式永真公式,如果原公式非永真公式非永真公式,则代入后可能变化可能变化。第25页/共41页 (ii)谓词变元谓词变元的代入的代入在一公式中,一个n元元(n0)谓谓词词变变元元F(x1,x2,xn)可代以至至少少有有n个个自自由由个个体体变变元元的公式G(y1,y2,yn,yn+1,yn+r),只须该n元谓谓词词出现的各各处处都都同同样样代代入入,y1,y2,yn 代以 x1,x2,xn。且代入的公式中：1.后边的r个自由变元个自由变元 不允许不允许在在原公式原公式中以约束变元出现以约束变元出现;2.F

13、(x1,x2,xn)中中的变变元元也也不不允允许许在代代入入的的公公式式中以以约约束束变变元出现元出现。第26页/共41页例例:(a)对公式(PQ)(PQ)中的P代以 xP(x),Q代以S(x),得(xP(x)S(x)(xP(x)S(x)(b)对公式 A:F(x,y)MF(u,x)中的 F,欲代以 B:G(x1)H(x2,s)H(t,x2),则只需x,y,u不不是是B内内的的约约束变元束变元,而且s,t不是不是A内的约束变元内的约束变元。代入结果为(G(x)H(y,s)H(t,y)M(G(u)H(x,s)H(t,x)第27页/共41页 2.替换规则替换规则 设A(x1,x2,xn)B(x1,x

14、2,xn),而A是公式是公式C中的子公式中的子公式,将B替换替换C中中的的A得D(不必每一处不必每一处),则：CD。第28页/共41页 3.对偶原理对偶原理 若量量词词公公式式 A 仅仅含含运运算算符符,和和,将上式中的全全称称量量词词 与与存存在在量量词词 互互换换,与与互互换换,T和和F互互换换,则互换后所得的公式A*称为A的的对偶式对偶式。若AB，则 A*B*,若AB，则 B*A*。第29页/共41页谓词演算实例第30页/共41页例例：(a)证明证证:第31页/共41页(b)证明 证证：根据根据CP规则规则,上式等价于 而 所以,第32页/共41页于是证明:不是永真的即可。(c)证明 是

15、非永真式非永真式。证：证：第33页/共41页 为了证证明明不不是是永永真真的,只只需需找找出出一一个个论论述述域域及域上谓谓词词的的一种解释种解释,使使(xP(x)xQ(x)(xP(x)xQ(x)是假是假即可。现设论论述述域域是是整整数数集集合合,P(x)表表示示x=0,Q(x)表表示示xx。于是 xP(x)是假,因而 xP(x)xQ(x)是真,但xP(x)是真,xQ(x)是假,xP(x)xQ(x)是假。所以，(xP(x)xQ(x)(xP(x)xQ(x)是假。第34页/共41页第35页/共41页附加：谓词逻辑的前束范式定义：设 A 为一个谓词逻辑公式，若 A=Q1x1Q2x2Qk xk B,其

16、中Qi(1 i k)为 或，B为不含量词的公式，则称A为前束范式。例如，x(F(x)G(x)xy(F(x)(G(y)H(x,y)是前束范式而 x(F(x)G(x)x(F(x)y(G(y)H(x,y)不是前束范式 第36页/共41页前束范式存在定理定理 谓词逻辑中的任何公式都存在与之等价的前束范式例 求下列公式的前束范式 (1)x(M(x)F(x)解 x(M(x)F(x)x(M(x)F(x)（量词否定等值式）x(M(x)F(x)后两步结果都是前束范式，说明公式的前束范式不唯一。第37页/共41页求前束范式的实例 (2)xF(x)xG(x)解 xF(x)xG(x)xF(x)xG(x)（量词否定等值

17、式）x(F(x)G(x)（量词分配等值式）或 xF(x)xG(x)xF(x)xG(x)量词否定等值式 xF(x)yG(y)改名规则 xy(F(x)G(y)辖域收缩扩张规则第38页/共41页(3)xF(x)y(G(x,y)H(y)解 xF(x)y(G(x,y)H(y)zF(z)y(G(x,y)H(y)改名规则 zy(F(z)(G(x,y)H(y)辖域收缩扩张规则求前束范式的实例注意注意：在求前束范式前，要用改名规则改名规则消去既约束出现既约束出现又自由出现自由出现的个体变元变元。第39页/共41页作业作业39-42页：页：1，5，9，13，18，21，22 48页：页：2，5，7第40页/共41页感谢您的观看。第41页/共41页