离散数学DiscreteMathematics 第5讲 2 6前束范式 要求 理解前束范式 前束合取范式和前束析取范式的定义 会将一个谓词公式wffA化为前束范式 前束合取范式和前束析取范式 学习本节的目的是掌握谓词公式的标准化形式 重点 化谓词公式为前束范式 复习 1 量词与联结词 之间的关系 2 量词扩张 收缩律 这里A x 是任意包括个体变元x的谓词公式 B是不包括个体变元x的任意谓词公式 3 量词与命题联结词之间的一些等价式 量词分配律 4 指导变元 作用域 约束变元 自由变元 量词 指导变元 辖域 约束变元 自由变元 5 约束变元换名和自由变元代入在一公式中 有的个体变元既是约束出现 又是自由出现 这就容易产生混淆 为了避免混淆 可对约束变元换名或自由变元代入 约束变元换名将量词辖域中某个约束出现的个体变元及相应指导变元 改成本辖域中未曾出现过的个体变元 其余不变 自由变元代入对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入 且处处代入 第二章谓词逻辑 PredicateLogic 2 6前束范式 PrenexNormalForm 2 6前束范式 Prenexnormalform 2 6 1前束范式 Prenexnormalform 2 6 2前束析取范式和前束合取范式 Prenexdisjunctivenormalform Prenexconjunctivenormalform 2 6前束范式 PrenexNormalForm 2 6 1前束范式 Prenexnormalform 定义2 6 1 任何一个谓词公式A 如果具有如下形式 x1 x2 xn B其中 可能是量词 或量词 xi i 1 n 是客体变元 B是不含量词的谓词公式 则称A是前束范式 说明 前束范式的量词均在全式的开头 它们的作用域延伸到整个公式的末尾 例1 x y F x G y H x y x y F x y G y z xH x y z 定理2 5 1 任何一个谓词公式 均和一个前束范式等价 前束范式的求法 第一步 否定深入 即利用量词转化公式 把否定联结词深入到命题变元和谓词填式的前面 第二步 改名 即利用换名规则 代入规则更换一些变元的名称 以便消除混乱 第三步 量词前移 即利用量词辖域的收缩与扩张把量词移到前面 这样便可求出与公式等价的前束范式 举例73页例题1 例题2 例题3 例题2化公式 x y z P x z P y z u Q x y u 为前束范式 解原公式 x y z P x z P y z u Q x y u x y z P x z P y z u Q x y u x y z u P x z P y z Q x y u 解第一步否定深入 原式 第二步改名 以便把量词提到前面 例题3把公式 练习75页 1 题 将约束变元x改名为u 将约束变元y改名为z 化为前束范式 例2 求下列公式的前束范式 解 2 5 2前束析取范式和前束合取范式 Prenexdisjunctivenormalform Prenexconjunctivenormalform 在前束范式的基础上 可以定义前束析 合 取范式 定义2 6 2 任何一个谓词公式A 如果具有如下形式则称为前束合取范式 x1 x2 xn A11 A12 A1k1 A21 A22 A2k2 Am1 Am2 Amkm 其中n大于等于1 Aij j 1 ki i 1 2 3 m 为原子谓词公式或其否定 为量词 或量词 xi i 1 n 为客体变元 任何一个谓词公式A 如果具有如下形式则称为前束析取范式 x1 x2 xn A11 A12 A1k1 A21 A22 A2k2 Am1 Am2 Amkm 其中n大于等于1 Aij j 1 ki i 1 2 3 m 为原子谓词公式或其否定 为量词 或量词 xi i 1 n 为客体变元 定理2 6 2 每一个谓词公式都可以转化为与其等价的前束析 合 取范式 二 前束合取范式定义2 6 2一个wffA称为前束合取范式 如果它有如下形式 Q1x1 Q2x2 Qkxk A11 A12 A1l1 A21 A22 A2l2 Am1 Am2 Amlm 其中Qi 1 i k 为量词 或 xi i 1 2 n 是客体变元 Aij是原子公式或其否定 例如公式 是前束合取范式 定理2 6 2每一个wffA都可转化为与其等价的前束合取范式 例题4将wffD 转化为与其等价的前束合取范式 解第一步取消多余量词 第二步换名 第三步消去条件联结词 第四步将否定深入 第五步将量词推到左边 x z w P x R x w Q z y R x w 三 前束析取范式定义2 6 3一个wffA称为前束析取范式 如果它有如下形式 Q1x1 Q2x2 Qkxk A11 A12 A1l1 A21 A22 A2l2 Am1 Am2 Amlm 其中Qi 1 i k 为量词 或 xi i 1 2 n 是客体变元 Aij是原子公式或其否定 例如公式 是前束析取范式 定理2 6 3每一个wffA都可转化为与其等价的前束析取范式 例题4将wffD 转化为与其等价的前束析取范式 解 小结 本节介绍了谓词公式的前束范式 前束析取范式和前束合取范式 重点掌握前束析取范式和前束合取范式求法 作业 作业 求下列公式的前束析取范式和前束合取范式 。
