离散数学及其应用课件第2章第2-4节

22
例题
证明下面的蕴含式成立。 xA(x)xB(x)x(A(x)B(x)) 解 xA(x) xB(x) xA(x)xB(x)
xA(x)xB(x) x(A(x) B(x)) x(A(x)B(x))
23
谓词逻辑的蕴含式
定理2.4.6 设A(x,y)是包含自由变元x,y的二元谓词公式，则有：
1. xyA(x,y)xA(x,x) 2. xA(x,x) xy A(x,y) 3. xyA(x,y)yxA(x,y) 4. yxA(x,y)xyA(x,y)
14
2.4 谓词演算的关系式
定义2.4.1 设A和B是任意两个谓词公式，如果AB是永真 式，则称谓词公式A和B等价，记为A B。
谓词逻辑的等价式有： • 命题逻辑中的等价式的代换实例是谓词逻辑中的等价式 • 谓词逻辑中特有的等价式
15
谓词逻辑的等价式（1）
定理2.4.1 （量词否定转换律）设A(x)是任意谓词公式，则 有
18
谓词逻辑的等价式（4）
定理2.4.4 设A(x,y)是包含自由变元x,y的二元谓词公式，则 有：
(1)xyA(x,y) yxA(x,y) (2) xyA(x,y) yxA(x,y)
19
例题
证明下面的等价式成立。 1. x(A(x) B(x)) xA(x)x B(x)； 2. xA(x) B(x) y(A(y) B(x))
证明
(1) x( A(x) B(x)) x(A(Βιβλιοθήκη Baidu) B(x)) xA(x) xB(x) xA(x) xB(x) xA(x) xB(x)
(2) xA(x) B(x) xA(x) B(x)) xA(x) B(x) yA( y) B(x) y(A( y) B(x)) y(A( y) B(x))
16
谓词逻辑的等价式（2）
定理2.4.2 （量词辖域扩张和收缩律）设A(x)是包含x为自由 变元的公式，B是不包含x的公式，则有
1. x(A(x) B) xA(x) B 2. x(A(x)B) xA(x)B 3. x(A(x) B) xA(x) B 4. x(A(x)B) xA(x)B
5. xA(x)B x(A(x)B) 6. xA(x)B x(A(x)B) 7. B xA(x) x(BA(x)) 8. B xA(x) x(BA(x))
24
前束范式
定义2.5.1 一个谓词公式A，若具有形式Q1x1Q2x2QnxnM， 其中每个Qi(1in)为或，M为不含量词的谓词公式，则称谓 词公式A为前束范式。
21
谓词逻辑的蕴含式
定理2.4.5 证明。 证明 （1）若x(A(x) B(x))为假，则存在个体a使A(a) B(a) 为假，于是A(a) 和B(a)都为假，因而xA(x)和xB(x)都为假， 从而xA(x) xB(x)为假。所以xA(x) xB(x)x(A(x) B(x))。 （3） 利用推理的CP规则，x(A(x)B(x)) xA(x) x((A(x) B(x)) A(x)) x((A(x) B(x)) A(x)) x(B(x) A(x)) xB(x) xA(x)xB(x)，所以x(A(x) B(x)) xA(x) x B(x)。
5
例题
对下列谓词公式中的变元更名，使每一变元只呈现一种出现形式。 (1)x(P(x) Q(x，y))R(x，y)； (2)x(P(x，y)Q(y，z))x R(x，y)yS(y) 解 (1)利用约束变元换名规则，将x(P(x) Q(x，y))中的约束变 元x换成z，得公式为：z(P(z) Q(z，y))R(x，y)； 或利用自由变元代入规则，将R(x，y)中的x用z代入，得公式为： x(P(x) Q(x，y))R(z，y)。 (2)利用约束变元换名规则，将x R(x，y)中的约束变元x换成u， 利用自由变元代入规则，将自由出现的三处y用t代入，得公式为： x(P(x，t)Q(t，z))uR(u，t)yS(y)。
8
例题
给定解释I如下： I. 个体域为自然数集合N； II. a=0； III. N中特定的函数f(x,y)=x+y，g(x,y)=xy； IV. N中特定的谓词F(x,y)：x=y。
在解释I下，求下列公式的真值。 1. xF(g(x,y),z); 2. xF(g(x,a),x)F(x,y); 3. xyzF(f(x,y),z);
9
例题（续）
解 (1) xF(g(x,y),z) x(xy=z)，不是命题，真值不确定。 （2）xF(g(x,a),x)F(x,y) x(xa=x)(x=y) x(0=x)(x=y) 1，因为蕴含式前件为假。 （3）xyzF(f(x,y),z) xyz(x+y=z) 1。 定理2.3.1 封闭的谓词公式在任何解释下都变成命题。 证明 略。 不是闭式的谓词公式在某些解释下也可能变成命题，如公 式(2)
6
闭式
定义2.2.3 任一谓词公式A，若A中没有自由出现的个体变 元，称A是封闭的谓词公式，简称闭式。
例 判断下列谓词公式是否是闭式？ 1. x(P(x) Q(x))； 2. xy (P(x，y)Q(y，z))yS(y)
解 1. 是闭式，因为无自由出现的变元； 2. 不是闭式，有自由出现的变元z。
20
谓词逻辑的蕴含式
定义2.4.2 设A和B是任意两个谓词公式，如果AB是永真 式，则称谓词公式A蕴含B，记为A B，称A B为蕴含式。
定理2.4.5 设A(x)，B(x)是包含自由变元x的公式，则有 (1) xA(x) xB(x)x(A(x) B(x)) (2) x(A(x) B(x))xA(x) x B(x) (3) x(A(x) B(x))xA(x)x B(x) (4) x(A(x) B(x)) xA(x)x B(x)
7
2.3 谓词公式的解释和分类
2.3.1 谓词公式的解释 定义2.3.1 谓词逻辑中公式A的一个解释（或赋值）I由如下 四部分组成： 1. 非空的个体域集合D； 2. A中的每个常元符号，指定D中的某个特定的元素； 3. A中的每个n元函数符号，指定Dn到D的某个特定的函数； 4. A中的每个n元谓词符号，指定Dn到{0,1}的某个特定的谓词；
3
例题
说明以下谓词公式中各量词的辖域及变元的约束情况。 (1)x(P(x)Q(x))； (2)x(P(x) yQ(x，y))； (3)xy(P(x，y)Q(y，z))x R(x，y) 解 (1)x的辖域是P(x)Q(x)，x为约束变元。 (2)x的辖域是P(x) yQ(x，y)，y的辖域是Q(x，y)， x，y为 约束变元。 (3)x的辖域是y(P(x，y)Q(y，z))，y的辖域是P(x，y)Q(y， z)， x的辖域是R(x，y)。在xy(P(x，y)Q(y，z))中，x，y为约束 变元，z为自由变元。在x R(x，y)中，x为约束变元，y为自由变元。
2.2 谓词演算公式
一个谓词P和n个个体变元，如x1，x2，x3， xn，表示成
P(x1，x2，x3， xn)的形式，称为n元原子谓词公式，简称n 元谓词公式。
如果谓词公式中没有个体变元，即n=0时称为0元谓词公式。 0元谓词公式就是原子命题。
1
谓词演算公式
定义2.2.1 谓词演算的合式公式，简称谓词演算公式，定义如下： • 每一个原子谓词公式都是谓词演算公式。 • 如果A是谓词公式，则( A)是谓词公式。 • 如果A和B都是谓词公式，则(A B),(A B),(A B),(A B)都是谓 词公式。 • 如果A是谓词公式，x是其中的任一变元，则xA和xA都是谓词公 式。 • 当且仅当有限次地应用上面的步骤得到的符号串才是谓词公式。
12
命题公式的代换实例
定义2.3.3 设A0是含命题变元p1，p2，p3， pn的命题公 式，A1,A2,…An是n个谓词公式，用Ai(1in)处处代替A0中的pi， 所得公式 A称为A0的代换实例。
如F(x)G(y)，xF(x)xF(x)都是pq的代换实例。 定理2.3.2 命题公式中永真式的代换实例都是永真式，矛盾 式的代换实例都是矛盾式。 证明略。
2
量词的辖域及变元的约束
定义2.2.2 谓词公式xA和xA中出现在量词和后面的变元x称为量 词的指导变元。 每个量词后面的最小的谓词子公式，称为该量词的辖域。 在量词的辖域中，x的所有出现都称为约束出现。约束出现 的变元称为约束变元。 除约束变元以外的其它变元的出现称为自由出现。自由出 现的变元称为自由变元。
证明： 5. xA(x) B xA(x) B
xA(x) B
x(A(x) B)
x( A(x) B)
17
谓词逻辑的等价式（3）
定理2.4.3（量词分配律）设A(x)，B(x)是包含自由变元x的公式，则有 (1)xA(x) xB(x) x(A(x) B(x)) (2)xA(x)xB(x) x(A(x)B(x)) 证明 （1）设I为任意解释。 如果xA(x) xB(x)在I下为真，则xA(x)和xB(x)都为真，于是对于任 意一个个体a都有A(a) B(a)为真，所以x(A(x) B(x))为真，因此xA(x) xB(x)x(A(x) B(x))。 如果x(A(x) B(x))在I下为真，则对于任意一个个体a都有A(a)和B(a)为 真，从而xA(x)和xB(x)都为真，于是xA(x) xB(x))为真，因此x(A(x) B(x)) xA(x) xB(x)。 故xA(x) xB(x) x(A(x) B(x))。
10
2.3.2 谓词公式的分类
定义2.3.2 设A是一个谓词公式，如A在任何解释下的真值恒为真，则 称A为永真式(或逻辑有效式)； 如A在任何解释下的真值恒为假，则称该谓词公式为永假式 (或矛盾式)； 如果至少存在一个解释使A的真值为真，则称A为可满足式。
11
例题
判定公式 xyA(x，y)yxA(x，y) 的类型。 解 设个体域为自然数集合，令A(x，y)表示xy=y。 yxA(x， y)在该解释下的真值为1，而此时xyA(x，y)的真值也为1。因 而在此解释下xyA(x，y)yxA(x，y)的真值为1。 再设个体域为自然数集合，A(x，y)表示xy。 yxA(x，y)在 该解释下的真值为1，而此时xyA(x，y)的真值为0。因而在此 解释下xyA(x，y)yxA(x，y)的真值为0。 因此公式xyA(x，y)yxA(x，y)不是永真式，是可满足 式。
5. yxA(x,y)xyA(x,y) 6. xyA(x,y)yx A(x,y) 7. xyA(x,y)yxA(x,y) 8. yxA(x,y)xyA(x,y)
证明 (1) 设I为任意解释，如果xA(x,x)在解释I下为假，则存 在一个个体a,使得A(a,a)为假，于是yA(a,y)为假，因而有 xyA(x,y)为假，所以xyA(x,y)xA(x,x)。
13
例题
判断下列公式是永真式还是矛盾式。 1. xF(x)xF(x); 2. xF(x)(yG(y) xF(x)); 3. F(x,y) (G(x,y) F(x,y));
解 1. xF(x)xF(x)为永真式。 2. 因为p(qp) 1，而xF(x)(yG(y)xF(x))是p(qp) 的代换实例，所以xF(x)(yG(y)xF(x))是永真式。 3. 因为p(qp) (qp) pqp 0，而F(x,y) (G(x,y)F(x,y))是p(qp)的代换实例，所以F(x,y) (G(x,y) F(x,y))是矛盾式。
(1) xA(x) xA(x) (2) xA(x) xA(x) 证明 （1）xA(x)为真 xA(x)为假 a使A(a)为假 a使A(a)为真 xA(x)为真，所以xA(x) xA(x)。 (2) xA(x)为假 a使A(a)为假 a使A(a)为真 xA(x) 为真 xA(x)为假，所以xA(x) xA(x)。
4
约束变元换名和自由变元代入
对谓词公式中约束出现的变元更改符号名称，称为约束变元换 名。
约束变元换名规则：将量词中的指导变元以及该量词辖域中该 变元的所有出现更改为辖域中没有出现的变元名称，公式的其余 部分不变。
对谓词公式中自由出现的变元更改符号名称，称为自由变元代 入。
自由变元代入规则：对某自由出现的个体变元的每一处都代入 与原公式中所有变元的名称不相同的变元。