工科离散数学课件 第二章 2_4_谓词公式的等价和蕴含(3) - 利用等价关系计算前束范式.pptx

2.4.2 利用等价关系计算前束范式2.4 谓词公式的等价和蕴含-利用等价关系计算前束范式[前束范式]一个谓词公式，如果所有量词作用于公式开头，作用域至公式末尾，则称其为前束范式： ?x1, ?x2, …, ?xnA(x1, x2, …, xn)其中，?表示量词符?或?，谓词公式A(x1, x2, …, xn)不含量词符，且只保留┐、? 和?这3种联结词。前束范式=前缀范式。示例： ?x ?y (A(x) ?B(x, y))是前束范式， ?x(A(x) ??y B(x, y))不是前束范式。定理：任何谓词公式都等价于一个前束范式。 2.4 谓词公式的等价和蕴含-利用等价关系计算前束范式转换方法：Step 1：将公式中的不同变元名唯一化。 ——换名或代入Step 2：将所有联结词转换为┐、? 和?表示。Step 3：利用量词转换律将┐移到量词之后： ┐?x A(x) ? ?x ┐A (x) ┐?x A(x) ? ?x ┐A (x)Step 4：通过等价关系将量词前移。Case 1, 直接前移：?xA(x)?B ? ?x(A(x) ?B) ，?xA(x)?B ? ?x(A(x)?B)Case 2, 先改名(Step 1)，再前移： ——换名或代入?xA(x) ??xB(x) ??xA(x) ??yB(y) ??x?y (A(x) ?B(y))?xA(x) ??xB(x) ??xA(x) ??yB(y) ??x?y (A(x) ?B(y)) 2.4 谓词公式的等价和蕴含-利用等价关系计算前束范式示例2-25：求公式(┐?x(p(x)) ??x(q(x))) ??x(s(x))的前束范式。解： 原式?(量词转换，┐置于量词后) (?x ┐p(x) ??x(q(x))) ??x(s(x)) ?(?对?可分配，直接扩张) ?x( ┐p(x) ?q(x)) ??x(s(x)) ?(变元换名) ?x( ┐p(x) ?q(x)) ??y(s(y)) ?(?y扩张) ?x?y ((┐p(x) ?q(x)) ?s(y))