离散数学-数-理-逻-辑.ppt

在命题逻辑中，原子为基本单位，不能再分，因此具有局限性，使有些简单命题无法判断。 7.1 谓词概念与表示 例： 是无理数。 小王是程序员。 小李比小王高 2 厘米。 对于个体词具有数量的概念。如 所有的人都要死的。 有的人活百岁以上。 注意： ④ 但定义域有限时，设D = {a1,a2,...,an} 7.3 谓词公式的翻译与解释 定义2：谓词逻辑中的项，被递归定义为：(1) 任意的个体常项或个体变项是项；(2) 若f (x1,x2,…xn,)是n元函数符号, t1,t2,…tn是项, 则f (t1,t2,…tn)是项；(3) 所有项都是有限次使用(1) (2) 生成的符号串。 定义4 合式公式是如下定义的一个符号串(1) 原子公式是合式公式；(2) 若A, B是合式公式，则如下符号串(?A),  (A?B), (A?B), (A?B), (A?B), (A?? B)也是 合式公式；(3) 若A是合式公式，则?xA, ?xA是合式公式；(4) 所有合式公式(谓词公式)都是有限次使用(1)(2)(3)得到的符号串。 命题符号化： 例1：每一个有理数都是实数。某些实数是有理数。不是每一个实数都是有理数。 例2: (1)所有的正数均可开平方； (2)没有最大的自然数。 例3 不管黑猫白猫，抓住老鼠就是好猫。 定义5：公式?x A(x, y) 或?x A(x, y) 中， x为指导变元，A为 x的作用域或辖域. x 作用域内的 x 称为约束变元，非约束的 y 称为自由变元。 n元谓词：若谓词公式P(x1, x2,..., xm)中有n个自由变元，称n元谓词。 有些量词既是约束的又是自由的，为避免混淆，可采用如下规则： 如上面例1(2) ?x F(x)∧G(x, y);可换名为: ?z F(z)∧G(x, y). 7.5 谓词演算的等价式与蕴含式 例1 (1) ?x (P(f (x))∧Q(x, f (a)))的一个解释 I： (2) ?x (P(x)∧Q(x, a))的一个解释 I： 例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) ?x?y(F(f(x, a), y)→F(f(y, a), x)) (2) ?x?y(F(f(x, a), y)→F(f(y, a), x)) 定义7：设A是谓词公式, 如果A在任何解释下都为真，则称A为逻辑有效式(永真式)；如果A在任何解释下都为假，则称A为矛盾式(永假式)；若至少存在一个解释使A为真，则称A为可满足式。 等值式与重言蕴含式 (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(B?A(x)) ? B??xA(x) 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) 利用上面公式可进行等值推演和形式演绎。 7.6 前束范式 求前束范式要用到两个性质。性质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)) 性质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) ? ?x?y(G(x)∨H(y))(4) ?xG(x)∧?xH(x) ? ?x ?y(G(x)∧H(y)) 定理：对任意公式G，都存在一个与其等值的前束范式。 例1：求公式?xF(x)→?xG