《数学离散数学》PPT课件.ppt

1、离散数学主讲：路永刚Email: 兰州大学信息科学与工程学院,上节课的内容,谓词 一元谓词 n元谓词 量词 全称量词 存在量词 量词的辖域 自由变元与约束变元 约束变元的改名规则,谓词演算的永真公式,谓词等价的定义,定义 1: 两个任意谓词公式A和B, E是它们公有的论述域, 若 (1) 对公式A和B中的谓词变元, 指派以任一在E上有定义的确定的谓词。 (2) 对谓词命名式中的个体变元, 指派以E中的任一确定的个体。 所得的命题都具有同样的真值, 则称公式A和B遍及E等价, 记为： 在 E 上 AB。 定义 2: 如果两谓词公式A和B, 在任意论述域上都等价, 则称A和B等价, 记为 AB。,

2、定义3: 给定任一谓词公式 A, 如果在 论述域E 上, 对公式A中的谓词和个体变元进行 定义1中的两种指派, 所得命题 (1) 都真，则称A在E上有效或在E上永真。 (2) 至少有一个是真, 则称A在E上 可满足。 (3) 都假, 则称A在E上永假或在E上不可满足。,谓词公式的分类,定义 4： 给定任一谓词公式A, 如果在任意论述域上, 对上述两种指派, (1) A永真, 则称A永真或有效。 (2) A至少在一个域上可满足, 则称A可满足。 (3) A永假, 则称A永假或不可满足。 若谓词公式A的个体域是有限的, 谓词的解释也有限, 则可用真值表判定谓词公式A是否永真。,谓词公式的分类,例：

3、 设P(x)仅可解释为: A(x): x是质数, B(x): x是合数。 论述域是3, 4, 判定谓词公式P(x)xP(x)是否永真。 解: (见右表) 所以, P(x)xP(x)非永真式。,但是，当谓词的解释和个体变元的数量稍大, 用真值表判定是否永真就难以实现。 这时，一般利用推导方法, 因此, 如同命题演算一样, 首先要求出基本的永真公式, 以作为推导的根据。,谓词演算的基本永真公式,1、首先，命题演算的永真公式也是谓词演算的永真公式, 基本的就是前面介绍的表 1.2-1(2)的逻辑恒等式和永真蕴含式。,2. 含有量词的谓词演算的基本永真公式。 (i) xAA xAA 这里A是不含自由变

4、元x的谓词公式, 因为A的真值与x无关, 所以上述等价式成立。,(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),(iii) 量词的否定： (xP(x) xP(x) (xP(x) xP(x),由于“并非对一切x, P(x)是真”等价于“存在一些x, P(x)是真”, 所

5、以前一式成立。 由于“并不存在一x, 使P(x)是真”等价于“对一切x, P(x)是真”, 所以后一式成立。,对比这两个式子, 容易看出, 如果把P(x)看作整体, 那么将x和x两者互换, 可从一个式得出另一个式。 这说明x和x具有对偶性。 另外, 由于两个量词可以互相表达, 所以有一个量词就够了。,(xP(x) xP(x) (xP(x) xP(x),例 ： xyz(x+z=y) xyz(x+z=y) xyz(x+z=y) xyz (x+z=y) xyz (x+zy),(iv) 量词辖域的扩张和收缩,xA(x)P x(A(x)P) xA(x)P x(A(x)P) xA(x)P x(A(x)P)

6、 xA(x)P x(A(x)P),其中P是不含自由变元x的谓词。 这里也可以看出 x和x具有对偶性。,(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)是真。,第个公式可由第个公式推出。 因为中的A(x), B(x)是任意的, 所以可用 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),x (A(x)B(x

7、) xA(x) xB(x),第个公式是成立的, 因为存在一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),第个公式可由第个公式推出。用A(x)和B(x)分别取代A(x)和B(x), 得 x(A(x)B(x) xA(x)xB

8、(x) x (A(x) B(x) (xA(x) (xB(x),否定等价式两边，得： xA(x)xB(x) x(A(x)B(x),(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),(vii) 关于多个量词的永真式: xyP(x, y) yx P(x, y) xyP(x, y) yx P(x, y) yxP(x, y) xy P(x, y) xyP(x, y) yx P(x, y) xyP(x, y) yx P(x, y),注意：

9、xyP(x, y) yxP(x, y) 不成立！ 例: 设P(x, y)表示 x+y=0, 论述域是有理数集合。 则 xy (x+y=0) 是真, 但 yx (x+y=0) 是假。 由此可知, 一般情况下，量词的次序是不能随便颠倒的。,当论述域有限时，可将谓词公式展开为命题公式证明。 例： 设论述域为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),表 1.7 -1 含有量词的永真公式概要表,谓词演算规则 1、代入规则 2、替换规则 3、对偶原理,1. 代入规则 (i)自由个体

10、变元的代入：在一公式中, 任一自由个体变元可代以另一个体变元, 只需该个体变元出现的各处都同样代入, 且代入的变元不允许在原来公式中以约束变元出现。 例: 在公式xP(x, y)Q(w, y)中, 将y代以z, 则得xP(x, z)Q(w, z)， 将y代以w, 则得xP(x, w)Q(w, w)。 所得公式称为原公式的代入实例。 如果原式是永真公式, 则代入后仍得永真公式, 如果原公式非永真公式, 则代入后可能变化。,(ii)谓词变元的代入 在一公式中, 一个n元(n0)谓词变元F(x1, x2, xn)可代以至少有n个自由个体变元的公式G(y1, y2, , yn, yn+1, , yn+

11、r), 只须该n元谓词出现的各处都同样代入, y1, y2, , yn 代以 x1, x2, xn 。 且代入的公式中： 1.后边的r个自由变元 不允许在原公式中以约束变元出现; 2. F(x1,x2, , xn)中的变元也不允许在代入的公式中以约束变元出现。,例: (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内的约束变元。 代入

12、结果为 (G(x)H(y, s)H(t, y)M(G(u)H(x, s)H(t, x),2. 替换规则 设A(x1, x2, xn) B(x1, x2, , xn), 而A是公式C中的子公式, 将B替换C中的A得D (不必每一处), 则：CD。,3. 对偶原理 若量词公式 A 仅含运算符 , 和, 将上式中的全称量词与存在量词互换, 与互换, T和F互换, 则互换后所得的公式A* 称为A的对偶式。 若AB，则 A* B *, 若AB，则 B*A*。,谓词演算实例,例： (a) 证明,证:,证： 根据CP规则, 上式等价于,而,所以,为了证明不是永真的,只需找出一个论述域及域上谓词的一种解释,

13、使(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) 是假。,附加：谓词逻辑的前束范式,定义：设 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) 不是前束范式,前束范式存在定理,定理 谓词逻辑中的任何公式都存在与之等价的前束范式,例 求下列公式的前束范式 (1) x(M(x)F(x),解 x(M(x)F(x) x(M(x)F(x) （量词否定等值式） x(M(x)F(x) 后两步结果都是前束范式， 说明公式的前束范式不唯一。,求前束范式的实例,(2) xF(x)xG(x),解 xF(x)xG(x) xF(x)xG(x) （量词否定等值式） x(F(x)G(x) （量词分配等值式）,或 xF(x)xG(x) xF(x)xG(x) 量词