离散数学谓词逻辑讲述.pptVIP

* * * 一、前束范式(Prenex normal form) 2.6 前束范式(Prenex normal form) 定义2-6.1 任何一个谓词公式A，如果具有如下形式： (□x1) (□x2)… (□xn)B 其中□可能是量词?或量词?，xi (i=1，…，n)是客体变元，B是不含量词的谓词公式，则称A是前束范式。 前束范式的量词均在全式的开头，它们的作用域延伸到整个公式的末尾。 1. 前束范式的定义 * * 2.6 前束范式(Prenex normal form) 例1 ?x?y((F(x)∧G(y))∧?H(x,y)) ?x?y(F(x,y)∧G(y,z))∨?xH(x,y,z) ?x?y(F(x)∧G(y))∧?H(x,y) 定理2-6.1 任何一个谓词公式，均和一个前束范式等价。 √ × × * * * 2.6 前束范式(Prenex normal form) 2. 前束范式的求法 第一步：否定深入。即利用德?摩根律和量词转化公式，把否定联结词深入到命题变元和谓词填式的前面。 第二步：改名。即利用换名规则、代入规则更换一些变元的名称，以便消除混乱。 第三步：量词前移。即利用量词辖域的收缩与扩张把量词移到前面。 * * * 例2 求下列公式的前束范式。 2.6 前束范式(Prenex normal form) * * * 解 (1) 2.6 前束范式(Prenex normal form) (2) * * * 2.6 前束范式(Prenex normal form) (5) * * * 2.6 前束范式(Prenex normal form) (6) * * * 二、前束析取范式和前束合取范式 2.6 前束范式(Prenex normal form) 在前束范式的基础上,可以定义前束析(合)取范式。 定义2-6.2 任何一个谓词公式A，如果具有如下形式则称为前束合取范式： 其中n大于等于1，Aij(j=1, …,ki，i=1,2,3,…,m)为原子谓词公式或其否定，□为量词?或量词?，xi (i=1，… n)为客体变元. * * * 2.6 前束范式(Prenex normal form) 任何一个谓词公式A，如果具有如下形式则称为前束析取范式： 其中n大于等于1，Aij(j=1, …,ki，i=1,2,3,…,m)为原子谓词公式或其否定，□为量词?或量词?，xi (i=1，… n)为客体变元。 定理2-6.2 每一个谓词公式都可以转化为与其等价的前束析(合)取范式。 * * * 例2 求下列公式的前束析取范式和前束合取范式。 (1) (2) 2.6 前束范式(Prenex normal form) 解 （略） * * * 作业：P75 (2) b，d 2.6 前束范式(Prenex normal form) 三、小结 本节介绍了谓词公式的前束范式、前束析取范式和前束合取范式。 重点掌握前束析取范式和前束合取范式求法。 * * 离散数学(Discrete Mathematics) * * * 2.7 谓词演算的推理理论(Inference theory of predicate calculus) 推理规则(Rules of inference) 推理应用举例 小结 * * * 一、推理规则(Rules of inference) 2.7 谓词演算的推理理论 在谓词演算中，推理的形式结构仍为 H1?H2?H3?....?Hn?C 若 H1?H2?H3?....?Hn?C是永真式，则称由前提H1、H2、H3、.…、Hn逻辑的推出结论C，但在谓词逻辑中，H1、H2、H3、.…、Hn 、C均为谓词公式。 命题演算中的推理规则，可在谓词推理理论中应用。 * * * 与量词有关的四条重要推理规则： 2.7 谓词演算的推理理论 全称指定规则（US规则） 全称推广规则（UG规则） 存在指定规则（ES规则） 存在推广规则（EG规则） 注意： 只能对前束范式适用上述规则。 * * * 1. 全称指定规则(US，UI) 2.7 谓词演算的推理理论 两种形式： ?xA(x) 或 ?xA(x) ∴ A(y) ∴ A(c) 以上两式成立的条件是： (1) x是A(x)中的自由变元； (2) A(y)中的