离散数学223.pptVIP

2.2 谓词公式与翻译 1. 谓词公式 定义：设x1,x2,…,xn是客体变元，A(x1,x2,…,xn)称作是谓词演算的原子公式，简称原子公式。 下面由原子公式出发，给出谓词演算的合式公式的归纳定义： 定义：谓词演算的合式公式定义如下： 1. 原子谓词公式是一个合式公式； 2. 如果 A 是合式公式，则? A 也是合式公式； 3. 如果 A 和 B 是合式公式，则A ? B，A ? B，A ? B，A ? B 都是合式公式； 4. 如果 A 是合式公式，x是A中出现的任何变元，则(?x)A和(?x)A都是合式公式 5. 当且仅当能够有限此地应用1、2、3、4步骤所得到的公式才是合式公式。 约定： 最外层括号可以省略；量词后面如果有括号，则不能够省略。 例如：(?x)(P(x) ? Q(x)) ? (?x) P(x) ? Q(x) 2. 谓词公式的翻译 有了谓词公式，就可以表达日常语言中的一些有关命题，这称为谓词逻辑的翻译或符号化。 例1：并非名人的话都是名言 解：设 R(x): x是名人的话 F(x): x是名言 ? (?x)( R(x) ? F(x) ) 例2：新进的这批微机有质量合格的，也有质量不合格的 解：设 C(x): x是新进的微机 H(x): x质量合格  B(x): x质量不合格 (?x)( C(x) ? H(x) ) ? (?x)( C(x) ? B(x) ) 例3：尽管有人聪明，但未必一切人都聪明 解：设 M(x): x是人 P(x): x聪明 (?x)( M(x) ? P(x) ) ? ? ((?x)( M(x) ? P(x))) 例4：如果有限个数的乘积为零，那么至少有一个因子 等于零 解：设 A(x): x是有限个数的乘积 B(x): x为零  C(x): x是 乘积中的一个因子 (?x)( A(x) ? B(x) ) ? (?y)( C(y) ? B(y)) 例5：(1) 所有人都不一样高。 (2) 每个自然数都有后继数。 (3) 有的自然数无先驱数。 解：(1) M(x): x是人，H(x,y): x?y，L(x,y): x与y一样高 (?x) (?y)(M(x)?M(y)?H(x,y) ? ?L(x,y)) 或者?(? x) (? y)(M(x)?M(y)?H(x,y) ? L(x,y)) (2) F(x): x是自然数，H(x,y):y是x的后继数 (?x)(F(x) ?(?y)(F(y) ?H(x,y))) (3) F(x): x是自然数，L(x,y):y是x的先驱数 (?x)(F(x) ?(?y)(F(y) ? H(x,y))) 总结： 翻译的步骤： 找出原子命题及其关系； 将原子命题分解成客体、谓词和量词，在全总个体域中讨论时，要给出特性谓词； 找出恰当量词； 用恰当的联结词把命题表示出来。 作业 P62 1 g）h) 3 b) 给定一个谓词公式，其中一部分公式形式为 (?x) P(x) 或者 (?x) P(x)。 改名范围是量词中的指导变元，该量词辖域中所出现的该变元，其余部分不变； 所选择的变元符号不能够和辖域中变元相同。 例2：对上页例中需换名的公式换名 1) (?x) P(x) ? Q(x) (?y) P(y) ? Q(x) 2) (?x) (P(x,y) ? Q(x)) ? R(x,y) (?z) (P(z,y) ? Q(z)) ? R(x,y) 3) (?x) ((P ? Q(x,y)) ? (?x) R(x)) (?x) ((P ? Q(x,y)) ? (?z) R(z)) 同样，对公式中的自由变元也可以更改，称作代入。 在同一个自由变元出现之处都要代入; 采用的变元符号与公式中所有变元的名称不能够相同。 例3：对上页例中需代入的公式进行代入 1) (?x) P(x) ? Q(x) (?x) P(x) ? Q(y) 2) (?x) (P(x,y) ? Q(x)) ? R(x,y) (?x) (P(x,y) ? Q(x)) ? R(z,y) 3) (?x) ((P ? Q(x,y)) ? (?x) R(x)) 不需代入，只能使用换名规则 对量词辖域中的约束变元，当论域中的元素是有限时（设为a1,a2,…an），客体变元的所有可能取代是可枚举的。即量化命题函数与命题的关系是： (?x)A(x) ? A(a1) ? A(a2) ? …? A(an) （1） (?x)A(x) ? A(a1) ? A(a2) ? … ? A(an) （2） 例如：我们班全班同