离散数学第二章第二节.ppt

第2-2讲 谓词公式与翻译 1. 谓词演算的合式公式 2. 用谓词公式表达命题 3. 约束变元和自由变元 4. 约束变元的换名规则 5.自由变元的代入规则 6. 第2-2讲 作业 1、谓词演算的合式公式 定义１ 不出现命题连接词和量词的ｎ元谓词 Ｐ（x1，x2，...，xn）（ｎ≥０） 称为谓词演算的原子公式，简称原子谓词公式。 2、用谓词公式表达命题 例１ 尽管有人聪明，但未必一切人都聪明。 解: 设M(x)： x是人。 P(x)： x聪明。 ?x(M(x)∧P(x)) ∧ ?(?x(M(x)→P(x))) 3、约束变元和自由变元 定义１ 在谓词公式形如(?ｘ)Ｐ(ｘ)和(?ｘ)Ｐ(ｘ)的部分中，?、?之后的ｘ叫相应量词的指导变元或作用变元，Ｐ(ｘ)称为相应量词?ｘ和?ｘ的辖域；在辖域内变元ｘ的一切出现称为约束出现，称ｘ为约束变元。在谓词公式中,除约束变元以外所出现的变元叫自由变元。 3、约束变元和自由变元(续) 4、约束变元的换名规则 5、自由变元的代入规则 第2-2讲 作业 P62 1eg，2，3a，7 P65 2bc，3b，4，5 * * 根据这个定义，命题、命题变元、简单命题函数统称为谓词演算的原子公式。如：R, Q(x), P(x,y), P(f(x),y), A(x,y,z), A(x,a,y)等等。 定义２ 谓词演算的合式公式当且仅当按下列规则生成： ⑴ 原子谓词公式是合式公式； ⑵ 若Ａ是谓词公式，则?Ａ是合式公式； ⑶ 若Ａ、Ｂ是谓词公式，则Ａ∧Ｂ，Ａ∨Ｂ，Ａ→Ｂ，Ａ?Ｂ是合式公式； ⑷ 若Ａ是谓词公式，ｘ是Ａ中出现的任意客体变元，则(?ｘ)Ａ和(?ｘ)Ａ都是合式公式 ⑸ 有限次应用规则⑴－⑷所得到的式子是合式公式。 例2 在高等数学中极限定义为：任给正数ε＞０，存在正数δ，使得当０＜ |x-a| ＜δ时，有 |f(x)-b| ＜ε，则称ｂ是ｆ(ｘ)当ｘ→ａ时的极限。 解: 设P(x,y)表示“x大于y”，Q(x,y)表示“x小于y”，则ｂ是ｆ(ｘ)当ｘ→ａ时的极限可表示为： (?ε)(?δ)(?ｘ)(((P(ε,0)→P(δ,0))∧Q(|x-a|,δ) ∧P(|x-a|,0 ))→Q(|f(x)-b|,ε)) 例１指出下列谓词公式中量词的辖域及自由变元和约束变元： ⑴ (?x)（F(x)→(?y)H(x,y)） ⑵ (?x)(?y)（P(x,y)∨Q(y,z)）∧(?x)P(x,y) 解：⑴ ?y的辖域为H(x,y)。对(?y)H(x,y)而言，ｙ是约束变元，ｘ是自由变元。在整个谓词公式中，?x的辖域为F(x)→(?y)H(x,y)，ｘ、ｙ都是约束变元；ｘ约束出现２次，ｙ约束出现１次。 ⑵ (?x)(?y)的辖域是P(x,y)∨Q(y,z)。这里，ｘ、ｙ是约束变元，而ｚ是自由变元。?x的辖域是R(x,y)，ｘ是约束变元，ｙ是自由变元。在整个谓词公式中，ｘ是约束出现的，ｙ既是约束出现，又是自由出现，ｚ是自由出现的。 Ｐ（x1，x2，…，xn）是ｎ元谓词，它有ｎ个相互独立的自由变元。若对其中ｋ个变元进行约束,则成为ｎ－ｋ元谓词。因此，谓词公式中如果没有自由变元出现，则该式就成为一个命题。例如，P(x,y,z)是三元谓词，而(?x)P(x,y,z)是二元谓词，(?y)(?x)P(x,y,z)是一元谓词。 量词对变元的约束与量词的次序有关。 多个量词连续出现时,约定按从左到右的次序读出。量词的次序不能颠倒，否则会改变命题的意义。 例如,(?y)(?x)(x(y-2))表示“对任何ｙ均存在ｘ，使得x(y-2)”；而(?x)(?y)(x(y-2))表示“存在ｘ对任何ｙ均有x(y-2)”。又如，(?y)(?x)(x(y-2))表示“存在ｙ，有ｘ，使得x(y-2) ”。 ⑴ 约束变元可以换名，更改的范围是量词的指导变元及该量词辖域中的所有约束出现的该变元，而其余部分不变； ⑵换名所用的变元名称应是量词辖域内未出现的符号（最好是整个谓词公式中未出现的符号）。量词对变元的约束与量词的次序有关。 例如： ⑴ (?x)F(x)∧G(x,y)?(?z)F(z)∧G(x,y) ⑵ (?x)(?y)（P(x,y)∨Q(y,z)）∧(?x)P(x,y) ?(?u)?v)(P(u,v)∨Q(v,z))∧(?x)P(x,y) 对谓词公式的自由变元可以用与原公式中所有变元名称不同的符号去代替，但必须处处代替。 例如： (1) (?x)P(x,y)∨Q(z,y)? (?x)P(x,w)∨Q(z,w) (2)