东北农业大学《离散数学》课件-第五节 谓词逻辑（第二部分） 刘老师.pptxVIP

谓词逻辑; 谓词逻辑中公式 G 的每一个解释 I 由如下四部分组成： 非空的个体域集合 D； G 中的每个常量符号 ，指定 D 中的某个特定的元素； G 中的每个 n 元函数符号 ，指定 Dn 到 D 中的某个特定的函数； G 中的每个 n 元谓词符号 ，指定 Dn 到 {0’1} 中的某个特定的谓词。; 设有解释 I 为：; 1 (Vx)(Vy)(P(x, y) A Q(x, y) - P(x, y))； 有效公式; y 谓词公式的可判定性 谓词逻辑是不可判定的； 只含有一元谓词变项的公式是可判定的； 如下形式的公式： (Vx1 )(Vx2 ) . . . (Vxn )P(x1 ’x2 ’. . . ???xn )， (3x1 )(3x2 ) . . . (3xn )P(x1 ’x2 ’. . . ’xn )。 若 P 中无量词和其它自由变元时，也是可判定的； 个体域有穷时的谓词公式是可判定的。;; e 命题演算中的基本等价公式 E1— E24 在谓词演算中仍然成立。; 例 设 P(x)： x 今天来上课，个体域为某班全体同学的集合。则 来上课了 同义 同样， A(一x)P(x) 与 (Vx)AP(x) 意义也相同。; 例 设 G(x)： x 勤奋学习， H(x)： x 喜欢体育活动，个体域是大学里的学生。 都喜欢体育活动 同义; 例 利用谓词之间的等价关系证明： A(一x)(M(x) ^ F(x)) = (Vx)(M(x) 二 AF(x)) 证明 ∶ A(一x)(M(x) ^ F(x)) = (Vx)A(M(x) ^ F(x)) = (Vx)(AM(x) V AF(x)) = (Vx)(M(x) 二 AF(x)); 谓词逻辑; 称公式 G 是一个前束范式 ，如果 G 中的一切量词都位于该公式的最前端 (不含否定词) 且这些量 词的辖域都延伸到公式的末端。其标准形式如下： (Q1x1 )(Q2x2 ) (Qnxn )M(x1 , x2 , , xn ) 其中 Qi 为量词 4 或 V(i = 1 , ; 1 消去公式中的联结词“→ ”,“二”(如果有的话)； 2 反复运用量词转换律，德摩根律和双重否定律，直到将所有的“二 ”都内移到原子谓词公式的 前端； 二(Vx)G(x) = (4x)二 G(x); 二(4x)G(x) = (Vx)二 G(x) ● (量词转换律) 3 使用谓词的等价公式将所有量词提到公式的最前端并保证其辖域直到公式的末端。;; 谓词逻辑;设 G1 , G2 , . . . , Gn ， H 是公式，称 H 是 G1 , G2 , . . . , Gn 的逻辑结果(或称 G1 , G2 , . . . , Gn 共同蕴涵 H) 当且仅当对任意解释 I ，若 I 同时满足 G1 , G2 , . . . , Gn ，则 I 满足 H ，记 为G1 , G2 , . . . , Gn ÷ H ，此时称 G1 , G2 , . . . , Gn ÷ H 是有效的，否则称为无效的。 G1 , G2 , . . . , Gn 称为一组前提 (premise) ，有时用集合 Γ 来表示，记Γ = (G1 , G2 , . . . , Gn }， H 称为结论 (conclusion) ，又称 H 是前提集合 Γ 的逻辑结果，记为Γ ÷ H。; 推理规律; 3 I15 : (Vx)(G(x) _ H(x)) 三 (Vx)G(x) _ (Vx)H(x); I16 : (Vx)(G(x) _ H(x)) 三 (3x)G(x) _ (3x)H(x) . 对于多个量词的公式，设 G(xy y) 是含有自由变元 x, y 的谓词公式，则有 4 I17 : (3x)(Vy)G(xy y) 三 (Vy)(3x)G(xy y); I18 : (Vx)(Vy)G(xy y) 三 (3y)(3x)G(xy y); I19 : (Vy)(Vx)G(xy y) 三 (3x)(Vy)G(xy y); I20 : (3y)(Vx)G(xy y) 三 (Vx)(3y)G(xy y);