第3 编数理逻辑第7 章命题逻辑.ppt

1、1,第 3 编 数 理 逻 辑,第 7 章 命 题 逻 辑,2,在命题逻辑中，原子为基本单位，不能再分，因此具有局限性，使有些简单命题无法判断。,例：著名的“苏格拉底三段论”： P : 凡人都是要死的。 Q : 张三是人。 R : 张三要死的。 PQR 应该是永真式，但在命题逻辑中无法证明。 解决方法：命题分解成个体词、谓词、量词。,3,7.1 谓词概念与表示,个体词：可以独立存在的客体。可以是具体的事物，也可以是抽象的概念。用小写字母表示：a, b, c,.,x, y, z. 定义：用以刻划个体词的性质或关系的词(命题函数)称为谓词。用大写字母表示：F( ), G( ). 个体域D：个体词的

2、取值范围。 全总个体域D：包含宇宙间所有的事物组成的个体，是研究问题中最大的个体域。 谓词的取值范围：0, 1.,4,例： 是无理数。 小王是程序员。 小李比小王高 2 厘米。,H(x): x 是程序员。 H(小王)。 G(x, y): x 比 y 高 2 厘米。G(小李, 小王)。 F(x)、H(x)是一元联结词；G(x, y)是二元联结词。 含n个个体词的谓词称 n元谓词。P(x1,x2,.,xn). 不含个体词的谓词称 零元谓词。,符号化：设F(x): x 是无理数。F( ) ， F( )。,5,对于个体词具有数量的概念。如 所有的人都要死的。 有的人活百岁以上。,定义：“任意x ”称全

3、称量词，记x。 “存在一个x ”称存在量词，记x。,对上面的例子，可设 F(x): x 要死的。xF(x). G(x): x 活百岁以上。xG(x). 这两个命题的真值都为T.,7.2 命题函数与量词,6,注意：, x 的定义域D不同，符号可能不一样。 如：D = 人类，符号同上； 如：D 为全总个体域，加特性谓词：M(x): x是人。,x (M(x)F(x) .(1) x (M(x)G(x) .(2), 没有给定定义域，则为全总个体域。 全称量词和存在量词的符号化形式不同： 见(1), (2)式。,7, 但定义域有限时，设D = a1,a2,.,an,x F(x) F(a1)F(a2)F(a

4、n). x G(x) G(a1)G(a2)G(an)., 不能随意颠倒量词的顺序。 例：“对任意的x，存在y，使x + y = 5”。 D = R, H(x, y): x + y = 5. 则 xy H(x, y) T 。但 yx H(x, y) F 。,8,7.3 谓词公式的翻译与解释,定义1 字母表如下： (1) 个体常项：a,b,c, (2) 个体变项：x,y,z, (3) 函数符号：f ( ),g( ), (4) 谓词符号：P( ),Q( ), (5) 量词符号：, (6) 逻辑符号：, (7) 括号与逗号：(, ), ，,个体词D,注意函数与谓词的区别,9,定义2：谓词逻辑中的项，被

5、递归定义为：(1) 任意的个体常项或个体变项是项；(2) 若f (x1,x2,xn,)是n元函数符号, t1,t2,tn是项, 则f (t1,t2,tn)是项；(3) 所有项都是有限次使用(1) (2) 生成的符号串。,例：a是项，x是项，g(x)是项，f (x, y)是项，f (g(x), a)是项.,定义3: 若P(x1,x2,xn,)是n元谓词, t1,t2,tn 是项, 则P(t1,t2,tn)是原子公式。,10,定义4 合式公式是如下定义的一个符号串(1) 原子公式是合式公式；(2) 若A, B是合式公式，则如下符号串(A), (AB), (AB), (AB), (AB), (A B

6、)也是 合式公式；(3) 若A是合式公式，则xA, xA是合式公式；(4) 所有合式公式(谓词公式)都是有限次使用(1)(2)(3)得到的符号串。,例：(1) x (P(f (x)Q(x, f (a); (2) x (P(x)Q(x, a). 两个符号串都是公式。,11,命题符号化：,确定谓词确定个体词及量词依量词确定逻辑关系。,x (M(x)F(x) .(1) x (M(x)G(x) .(2),12,例1：每一个有理数都是实数。某些实数是有理数。不是每一个实数都是有理数。,解：设P(x): x 是有理数。Q(x): x 是实数。 x(P(x)Q(x). x(Q(x)P(x). x(Q(x)P

7、(x). ,13,例2:(1)所有的正数均可开平方；(2)没有最大的自然数。,解：(1) 设 R(x): x 是实数。 G(x,y): x y。 S(x): x 可以开平方。 x(R(x)G(x,0)S(x). (2) 设 N(x): x 是自然数。 G(x,y): x y。 x(N(x)y(N(y)G(y,x). ,14,例3 不管黑猫白猫，抓住老鼠就是好猫。,解：设B(x): x 是黑猫； W(x): x 是白猫； M(x): x 抓住老鼠； G(x): x 是好猫。,x (B(x)W(x)M(x) G(x).,15,定义5：公式x A(x, y) 或x A(x, y) 中， x为指导变元

8、，A为 x的作用域或辖域. x 作用域内的 x 称为约束变元，非约束的 y 称为自由变元。,例1：(1) x (P(x)yQ(x, y); x 和 y 都是约束变元。 (2) x F(x)G(x, y); 第一个 x 是约束变元，第二个 x 是自由变元， y 是自由变元。 (3) xy(R(x, y)L(y, z)x H(x, y). x 是约束变元，第一个y和第二个y是约束变元，第三个y是 自由变元，z 是自由变元。,7.4 变元的约束,16,n元谓词：若谓词公式P(x1, x2,., xm)中有n个自由变元，称n元谓词。,若谓词公式P(x1, x2,., xm)中有k个约束变元，则为m-k

9、元谓词。如 x yQ(x, y) 为零元谓词； x Q(x, y) 为1元谓词； Q(x, y) 为2元谓词.,17,有些量词既是约束的又是自由的，为避免混淆，可采用如下规则：,换名规则：对约束变元进行换名，即将量词作用域中出现的某个约束变元换成另外作用域中未曾出现变元符号，公式中的其余部分不变。 代入规则：对自由变元进行代入，即对自由变元用与原公式中所有变元符号不同的符号去代替。,18,如上面例1(2) x F(x)G(x, y);可换名为: z F(z)G(x, y).,(3) xy(R(x, y)L(y, z)x H(x, y). 可换名为: xu(R(x, u)L(u, z)t H(t

10、, y).,19,7.5 谓词演算的等价式与蕴含式,对一个解释 I，公式就有一个确定的真值。,定义6：设谓词公式A的个体域为D。 (1) 对每个常项指定D中一个元素；(2) 对每个n元函数指定Dn到D的一个函数；(3) 对每个n元谓词指定Dn到0, 1的一个谓词. 按这样规则作出的一组指派称为A的一个解释 或赋值 I 。,20,例1 (1) x (P(f (x)Q(x, f (a)的一个解释 I：,于是 x (P(f (x)Q(x, f (a) (P(f (2)Q(2, f (2)(P(f (3)Q(3, f (2) (P(3)Q(2, 3)(P(2)Q(3, 3) (11)(01) 10 1

11、.,D = 2, 3,21,(2) x (P(x)Q(x, a)的一个解释 I：,D = 2, 3,x (P(x)Q(x, a) (P(2)Q(2, 2)(P(3)Q(3, 2) (01)(10) 0. ,22,例2 已知解释N如下：1) 个体域为自然数集合Dn;2) Dn中特定元素 a = 0 ;3) Dn上的特定函数 f(x,y) = x+y, g(x,y) = x y;4) Dn上的特定谓词 F(x,y) 为 x = y 。在解释N下，试说明下列公式的真假：(1) x F(g(x, a), x)(2) xy(F(f(x, a), y)F(f(y, a), x),解：在解释N下，公式分别为

12、 (1) x F(g(x, a), x) x (x 0 = x) x (0 = x) 0,23,(2) xy(F(f(x, a), y)F(f(y, a), x), xy( x + 0 = y y + 0 = x) xy( x = y y = x) 11 1,24,定义7：设A是谓词公式, 如果A在任何解释下都为真，则称A为逻辑有效式(永真式)；如果A在任何解释下都为假，则称A为矛盾式(永假式)；若至少存在一个解释使A为真，则称A为可满足式。,例：P(x)P(x) 逻辑有效式； P(x)P(x) 矛盾式。 谓词公式的真值表不存在。,定义8 设命题公式A0，命题变项为P1,P2,.,Pn，A1,

13、A2,.,An为谓词公式，用Ai代替Pi(i=1,2,.,n)所得公式A称为A0的代换实例。,25,等值式与重言蕴含式,1. 命题公式仍可用(16个等值式)。 2. 量词否定等值式 (1) xA(x) x(A(x) (2) xA(x) x(A(x) 3. 量词辖区扩张与收缩等值式 (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(BA(x) BxA(x),26,(5) x(A(x)B) xA(x)B (6) x(A(x)B) xA(x)B (7) x(A(x)B) xA(x)B (8) x(BA(x) BxA(x

14、),4. 一般等值式 (9) xA(x)xB(x) x(A(x)B(x) (10) xA(x)xB(x) x(A(x)B(x) (11) xA(x)xB(x) xy(A(x)B(y) (12) xA(x)xB(x) xy(A(x)B(y) (13) x(A(x)B(x) xA(x)xB(x),27,5. 一般重言蕴含式 (14) xA(x)xB(x) x(A(x)B(x) (15) x(A(x)B(x) xA(x)xB(x) (16) x(A(x)B(x) xA(x)xB(x) (17) xA(x)xB(x) x(A(x)B(x) (18) x(A(x)B(x) xA(x)xB(x),6. 两

15、个量词的等值式与重言蕴含式 交换量词位置，自己看。,28,利用上面公式可进行等值推演和形式演绎。,例：证三段论x(H(x)M(x), H(a) M(a). 其中H(x): x是人; M(x): x要死的; a: 张三。 证：(1) H(a) P (2) x(H(x)M(x) P (3) H(a)M(a) US(2) 全称指定 (4) M(a) Q (1)(3) x(H(x)M(x), H(a) M(a). ,29,7.6 前束范式,定义9：一个公式，如果量词均在公式的开头，它们的作用域延伸到整个公式的末尾，则称该公式为前束范式。 谓词公式A具有如下形式 Q1x1Q2x2QnxnB 其中Qi x

16、i或者是xi，或者是xi，i =1,n, B是不含量词的谓词公式，则称A为前束范式。,一种较简单的范式。,例：xyz(P(x, y)Q(x, z)就是前束范式。,30,求前束范式要用到两个性质。性质1: (1) x(G(x)H) xG(x)H(1)/ x(G(x)H) xG(x)H (2) x(G(x)H) xG(x)H(2)/ x(G(x)H) xG(x)H (3) (xG(x) x(G(x)(3)/ (xG(x) x(G(x),为前3(1)式,为前3(5)式,为前3(2)式,为前3(6)式,为前2(1)式,为前2(2)式,实际上以上等值式都不是新的公式，它们在前面已经出现过或者是它们的特殊

17、情况。,31,性质2: (1) xG(x)xH(x) x(G(x)H(x)(2) xG(x)xH(x) x(G(x)H(x)(3) xG(x)xH(x) xy(G(x)H(y)(4) xG(x)xH(x) x y(G(x)H(y),前4(9)式,前4(10)式,前4(11)式,前4(12)式,32,定理：对任意公式G，都存在一个与其等值的前束范式。,证: 通过以下步骤可将G化为等值的前束范式。 第一步：使用基本等值式，将联结词, 化为, , ； 第二步：将所有否定 放到原子前； 第三步：根据需要将约束变量改名； 第四步：使用性质1, 2, 将所有量词都提到公式的最左边。 于是将公式G在等值意义

18、下，化成了一个前束范式。 ,33,例1：求公式xF(x)xG(x)的前束范式。,解：xF(x)xG(x) xF(x)xG(x) xF(x)xG(x) xF(x)yG(y) xy(F(x)G(y) ,例2：求公式xF(x)xG(x)的前束范式。,解：xF(x)xG(x) x(F(x)G(x) ,34,例3：求公式xF(x)xG(x)的前束范式。,解：xF(x)xG(x) xF(x)xG(x) xF(x)xG(x) x(F(x)G(x) ,例4：求公式xF(x)xG(x)的前束范式。,解：xF(x)xG(x) xF(x)yG(y) x(F(x)yG(y) xy(F(x)G(y) ,35,附：几个谓

19、词公式的证明,设D = a1, a2,an. 4(10) xA(x)xB(x) x(A(x)B(x) 证：x(A(x)B(x) (A(a1)B(a1)(A(an)B(an) (A(a1)A(an)(B(a1)B(an) xA(x)xB(x)。 ,36,5(14) xA(x)xB(x) x(A(x)B(x),证：xA(x)xB(x) (A(a1)A(an)(B(a1)B(an) (A(a1)B(a1)(A(an)B(an) (A(a1)B(a2)(A(a1)B(a3) (A(an-1)B(an) x(A(x)B(x) (A(a1)B(a2) x(A(x)B(x). ,37,2(2) xA(x)

20、x(A(x),证：xA(x) (A(a1)A(an) A(a1)A(an) x(A(x). 3(1) x(A(x)B) xA(x)B 证：x(A(x)B) (A(a1)B)(A(an)B) (A(a1)A(an)B xA(x)B. ,38,3(3) (xA(x)B) x(A(x)B),证：(xA(x)B) xA(x)B xA(x)B x(A(x)B) x(A(x)B)。 3(4) BxA(x) x(BA(x) 证：BxA(x) BxA(x) x(BA(x) x(BA(x)。 ,39,7.7 谓词逻辑的推理理论,A1,A2,.,Am C 可用公式： 命题逻辑: 等值式(16个), 蕴含式(14个) 谓词逻辑: 等值式(13个),