数学离散数学PPT课件

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

2、定义 2: 如果两谓词公式A和B, 在任意论述域任意论述域上上都等价等价, 则称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, 如果在任

3、意论述域任意论述域上上, 对上述两种指派, (1) A永真永真, 则称A永真永真或有效有效。 (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

4、(x)非永真式。 第6页/共41页 但是，当谓词的解释和个体变元的数量稍大, 用真值表判定是否永真就难以实现。 这时，一般利用推导方法, 因此, 如同命题演算一样, 首先要求出基本的永真公式, 以作为推导的根据。 第7页/共41页谓词演算的基本永真公式谓词演算的基本永真公式 1、首先，命题演算命题演算的永真公式永真公式也是谓词演算谓词演算的永真公式永真公式, 基本的就是前面介绍的表 1.2-1(2)的逻辑恒等式逻辑恒等式和永真蕴含式永真蕴含式。 第8页/共41页 2. 含有量词含有量词的谓词演算的的谓词演算的基本永真公式基本永真公式。 (i) xAA xAA 这里A是不含自由变元不含自由变元x

5、的谓词公式谓词公式, 因为A的真值与x无关, 所以上述等价式成立。第9页/共41页 (ii) xP(x) P(y)， 或 xP(x) P(x) P(y) xP(x)，或 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(

6、x)是真”等价于“存在一些x, P(x)是真”, 所以前一式成立。由于“并不存在一x, 使P(x)是真”等价于“对一切x, P(x)是真”, 所以后一式成立。第11页/共41页对比这两个式子, 容易看出, 如果把P(x)看作整体, 那么将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

7、+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和和 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页 第个公式可由第个公式推出

8、。因为中的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页第个公式是成立的, 因为存在一x使A(x)B(x)是真, 所以存在一x使A(x)是真, 同时存在一x使B(x)是真。但第个公式不不是是等价等价式式。例例：设A(x)和B(x)分别解释为“x是奇数是奇数”和“x是偶数是偶数”, 论述域论述域是自然数自然数N, 则xA(x)是真, x

9、B(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(x) B(x) ( xA(x) ( xB(x)否定等价式两边否定等价式两边，得： xA(x) xB(x) x(A(x)B(x) 第18页/共41页(vi) 量词对量词对 及 的处理处理只须应用它们对 ， ， 的恒等式恒等式即

10、可推出。例例： 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页/共41页 注意注意： x yP(x, y) y xP(x, y) 不成立不成立！例例: 设P(x, y)表示 x+y=0, 论述域论述域是

11、有理数有理数集合。则 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 -1 含有量词的永真公式概要表含有量词的永真公式概要表 第23页/共41页谓词演算规则谓

12、词演算规则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)。所得公式称为原公式的代入实例代入实例。 如果原式是如果原式是永真公

13、式永真公式, 则代入后仍得代入后仍得永真公式永真公式, 如果原公式非永真公式非永真公式, 则代入后可能变化可能变化。 第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(x

14、1,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页/共

15、41页 2. 替换规则替换规则 设A(x1, x2, xn) B(x1, x2, , 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) 证明)()()()(xxQ

16、xxPxQxPx1441114)()()()()()()()()()(ExxQxxPQxxQxxPQxxQxPxExQxPxxQxPx证证:第31页/共41页(b) 证明 )()()()()()(xPxRxQxRxxQxPx证证： 根据根据CP规则规则, 上式等价于 而 )()()()()()(xPxRxQxRxxQxPx)()()()()()()()()()()()()()()()()()(xPxRxPxQxQxRxPxQxQxRxxQxRxQxPxxQxRxxQxPx所以, )()()()()()(xPxRxQxRxxQxPx第32页/共41页于是证明: )()()()(xxQxxPxxQ

17、xxP不是永真的即可。 (c) 证明 )()()()(xxQxxPxQxPx是非永真式非永真式。 证：证： )()()()()()()()()()(xxQxxPxxQxxPxxQxPxxQxPxxQxPx第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)

18、 是假。 所以，( xP(x) xQ(x)( xP(x) xQ(x) 是假。第34页/共41页第35页/共41页附加：谓词逻辑的前束范式定义：设 A 为一个谓词逻辑公式，若 A=Q1x1Q2x2Qk xk B, 其中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) （量词否定等值式） x(F(x)G(x) （量词分配等值式）或 xF(x)xG(x)