离散数学教学课件02-谓词逻辑-2.5-2.6.pptVIP

第二章 谓词逻辑 Predicate Logic 第五节 谓词公式范式 第五节 谓词公式范式 一、前束范式（Prenex Normal Forms） 定义：一个公式A如果有如下形式 (Q1x1) (Q2x2) … (QKxK) B其中，Qi是 ?或?，B为不含量词的公式 称它为A的为前束范式，(Q1x1)(Q2x2)…(QKxK)称作首标 特点： 所有量词均非否定地出现在公式最前面， 且辖域一直延伸到公式末尾 前束范式 前束范式存在定理：Lp中任意公式A都有与之等价的前束范式 证明： （略） P43 前束范式 例2.11：将公式((?x)P(x) ∨ (?y)Q(y)) ? (?x)R(x)化为前束范式 斯柯伦范式 二、斯柯伦(Skolem)范式 前束范式的缺点是：量词的排列无一定规则，会形成很多形式的前束范式 斯柯伦范式规定：将前束范式的首标中的量词进行排列，每个存在量词均放到全称量词的前面 斯柯伦范式 例2.12 将公式(?x)((?P(x)∨(?y)Q(y,z)) ??(?z)R(y,z))化为斯柯伦范式 第六节 谓词逻辑的推理理论 一、A(x)对y是自由的 定义：在谓词公式A(x)中，若x不自由出现在量词(?y)或(?y)的辖域内，则称A(x)对于y是自由的。 若y在A(x)中不是约束出现，则A(x)对于y一定是自由的。 考察目的：使y代入到A(x)中得到A(y)，不会改变原公式A(x)的约束关系。 A(x)对y是自由的 例2.13 A(x)是下列公式，考察A(x)对y是否自由，并求A(y) A(x) = (?y)P(y) ∧ Q(x) A(x)对y是自由的。A(y)= (?y)P(y) ∧ Q(y) A(x) = (?y)P(y) ∧ Q(x, y) A(x)对y是自由的。A(y)= (?y)P(y) ∧ Q(y, y) A(x)对y是自由的 A(x) = (?x)P(x) ∧ Q(x, y) A(x)对y是自由的。A(y)= (?x)P(x) ∧ Q(y, y) A(x) = (?y)( P(y) ∧ Q(x, y) ) A(x)对y不是自由的。 此时可以将A(x)中的约束变元y进行改名： A(x) = (?z)( P(z) ∧ Q(x, z) )， 此时A(x)对y是自由的 A(y)= (?z)( P(z) ∧ Q(y, z) ) 自由变元代入规则 自由变元代入规则：对公式中的某个自由出现的个体变元，可以用个体常元或与整个公式中所有约束变元不同的个体变元去代入，而且是处处代入。 A(x)可以用项t代入，条件是x不出现在项t所含的任意个体变元y的量词(?y)或(?y)的辖域内，称项t对x是自由的。 例如：A(x) = (?y)( P(y) ∧ Q(x, y) )项f(y,z)对x不是自由的，而项 f(x,z) 对x是自由的。 谓词逻辑的推理理论 二、谓词逻辑的推理理论 全称量词的消去规则 UI/US 存在量词的消去规则 EI/ES 存在量词的产生规则 EG 全称量词的产生规则 UG 全称量词的消去规则 UI/US 全称量词的消去规则 UI/US 也叫作全称指定规则（Universal Specification） 规则内容：(?x)A(x) ? A(c) 其中c为任意个体常元(?x)A(x) ? A(y) y为任意变元， 且A(x)对y是自由的 该规则用于删除全称量词 全称量词的消去规则 UI/US 例2.14 考察下面公式(?x)A(x)，能推导出怎样的A(y)来？ (?x)A(x) = (?x)((?y)P(y) ∧ Q(x, y)) 由于x没有出现在(?y)的辖域内，所以A(x)对y是自由的 A(y) = (?y)P(y) ∧ Q(y, y) 即(?x)((?y)P(y) ∧ Q(x, y)) ? (?y)P(y) ∧ Q(y, y) 全称量词的消去规则 UI/US (?x)A(x) = (?x)((?y)P(x, y) ∧ Q(x, y)) 由于x出现在(?y)的辖域内，因此需要对约束变元y改名 (?x)A(x)经过改名得到：(?x)((?z)P(x, z)∧Q(x, y)) A(y) = (?z)P(y, z) ∧ Q(y, y) 即(?x)((?y)P(y, z)∧Q(x, y))?(?z)P(y,z)∧Q(y, y) 全称量词的消去规则 UI/US 例2.18 证明以下论证： 所有人都是要死的 苏格拉底是人 所以苏格拉底是要死的 解：令P(x)：x是人，D(x)：x是要死的，a：苏格拉底 求证： (?x) (P(x) ?D(x)), P(a) ? D(a) 全称量词的消去规则 UI/