Discrete Mathematics 第5讲 §2—6 前束范式 u 要求：理解前束范式、前束合取范式和前束析取范式的定义，要求：理解前束范式、前束合取范式和前束析取范式的定义，会将一个谓词公式会将一个谓词公式wffA化为前束范式、前束合取范式和前束析化为前束范式、前束合取范式和前束析取范式u 学习本节的目的是掌握谓词公式的标准化形式学习本节的目的是掌握谓词公式的标准化形式u 重点：化谓词公式为前束范式重点：化谓词公式为前束范式 复习：（1）量词与联结词¬之间的关系（2）量词扩张/收缩律 这里A(x)是任意包括个体变元x的谓词公式，B是不包括个体变元x的任意谓词公式 （（3）量词与命题联结词之间的一些等价式）量词与命题联结词之间的一些等价式量词分配律量词分配律 u（（4）指导变元、作用域、约束变元、自由变元）指导变元、作用域、约束变元、自由变元量词指导变元辖域约束变元自由变元 （5）约束变元换名和自由变元代入 在一公式中，有的个体变元既是约束出现，又是自由出现，这就容易产生混淆为了避免混淆，可对约束变元换名或自由变元代入 约束变元换名 将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。
自由变元代入 对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入 离散数学离散数学第二章第二章 谓词逻辑谓词逻辑（（Predicate Logic）） 2. 6前束范式前束范式(Prenex Normal Form(Prenex Normal Form) )2.6 前束范式前束范式(Prenex normal form) )2.6.1 前束范式前束范式(Prenex normal form) ) 2.6.2 前束析取范式和前束合取范式前束析取范式和前束合取范式(Prenex disjunctive normal form & Prenex conjunctive normal form) ) 离散数学离散数学 2. 6 前束范式前束范式(Prenex Normal Form(Prenex Normal Form) )2.6.1前束范式前束范式(Prenex normal form) ) u定义定义2.6.1:任何一个谓词公式任何一个谓词公式A，如果具有如下形式：，如果具有如下形式： (□x1) (□x2)… (□xn)B其中其中□可能是量词可能是量词 或量词或量词 ，， xi（（i=1，，… n））是客体变是客体变元，元，B是不含量词的是不含量词的谓词公式，则称谓词公式，则称A是前束范式。
是前束范式u说说明明:前前束束范范式式的的量量词词均均在在全全式式的的开开头头,它它们们的的作作用用域域延延伸到整个公式的末尾伸到整个公式的末尾u例例1: x y（（（（F(x)∧∧G(y)））∧∧┐┐H(x,y)）） √√ x y(F(x,y)∧∧G(y,z))∨∨ x H(x,y,z) ×× 离散数学离散数学u定理定理2.5.1:任何一个谓词公式任何一个谓词公式,均和一个前束范式等价均和一个前束范式等价前束范式的求法：前束范式的求法：第一步：否定深入即利用量词转化公式，把否定联结第一步：否定深入即利用量词转化公式，把否定联结 词深入到命题变元和词深入到命题变元和谓词填式的谓词填式的前面第第二二步步：：改改名名即即利利用用换换名名规规则则、、代代入入规规则则更更换换一一些些变变元的名称，以便消除混乱元的名称，以便消除混乱第第三三步步：：量量词词前前移移即即利利用用量量词词辖辖域域的的收收缩缩与与扩扩张张把把量量词移到前面这样便可求出与公式等价的前束范式词移到前面这样便可求出与公式等价的前束范式 离散数学离散数学举例 73页 例题1，例题2，例题3 离散数学离散数学例题例题2 化公式化公式( ( x x) )( ( y y)()(( ( z)(P(x,z)z)(P(x,z)∧∧P(y,z))P(y,z))( ( u)Q(x,y,u))u)Q(x,y,u))为前束为前束范式范式解解 原公式原公式( ( x x) )( ( y y)()(┐┐( ( z)(P(x,z)z)(P(x,z)∧∧P(y,z))P(y,z))∨∨( ( u)Q(x,y,u))u)Q(x,y,u))( ( x x) )( ( y y)(()(( z)(z)(┐┐P(x,z)P(x,z)∨∨┐┐P(y,z))P(y,z))∨∨( ( u)Q(x,y,u))u)Q(x,y,u))( ( x x) )( ( y y)()( z)z)( ( u)u)( (┐┐P(x,z)P(x,z)∨∨┐┐P(y,z)P(y,z)∨∨Q(x,y,u))Q(x,y,u)) 离散数学离散数学解解 第一步否定深入第一步否定深入原式原式第二步改名，以便把量词提到前面。
第二步改名，以便把量词提到前面例题例题3 把公式把公式练习75页（1）题将约束变元x改名为u，将约束变元y改名为z，化为前束范式化为前束范式 离散数学离散数学例例2:2:求下列公式的前束范式求下列公式的前束范式 离散数学离散数学u解解: 离散数学离散数学 离散数学离散数学u 离散数学离散数学 离散数学离散数学2.5.2前束析取范式和前束合取范式前束析取范式和前束合取范式(Prenex disjunctive normal form & Prenex conjunctive normal form) ) u在前束范式的基础上在前束范式的基础上,可以定义前束析可以定义前束析(合合)取范式取范式.u定定义义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））为为客客体体变元变元. 离散数学离散数学u任何一个谓词公式任何一个谓词公式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）为）为客体变元客体变元. u定理定理2.6.2:每一个谓词公式都可以转化为与其等价的前束析每一个谓词公式都可以转化为与其等价的前束析(合合)取取范式范式. 离散数学离散数学u二、前束合取范式二、前束合取范式u定义定义2-6.2 2-6.2 一个一个wffAwffA称为前束合取范式，如果它有如下形式：称为前束合取范式，如果它有如下形式：u(Q(Q1 1x x1 1)(Q)(Q2 2x x2 2) )…(Q(Qk kx xk k)[(A)[(A1111∨ ∨A12∨ ∨…∨ ∨A1l1)∧ ∧(A(A2121∨ ∨A22∨ ∨…∨ ∨A2l2) ∧ ∧ …∧ ∧(A(Am1m1∨ ∨Am2∨ ∨…∨ ∨Amlm)]u其中其中Q Qi i(1≤i≤k)(1≤i≤k)为量词为量词 或或 ，，x xi i(i=1,2, (i=1,2, …,n),n)是客体变元，是客体变元，A Aijij是原子公式或其否定。
是原子公式或其否定例如公式例如公式是前束合取范式是前束合取范式 离散数学离散数学定理定理2-6.2 每一个每一个wffA都可转化为与其等价的前束合取范式都可转化为与其等价的前束合取范式例题例题4 将将wffD：： 转化为与其等价的前束合取范式转化为与其等价的前束合取范式解解 第一步取消多余量词第一步取消多余量词第二步换名第二步换名第三步消去条件联结词第三步消去条件联结词第四步将否定深入第四步将否定深入第五步将量词推到左边第五步将量词推到左边( ( x x)()( z)z)( ( w)[w)[( (┐┐P(x)P(x)∨∨┐┐R(x,w))R(x,w))∧∧( (┐┐Q(z,y)Q(z,y)∨∨┐┐R(x,w))]R(x,w))] 离散数学离散数学u三、前束析取范式三、前束析取范式u定义定义2-6.3 2-6.3 一个一个wffAwffA称为前束析取范式，如果它有如下称为前束析取范式，如果它有如下形式：形式：u(Q(Q1 1x x1 1)(Q)(Q2 2x x2 2) )…(Q(Qk kx xk k)[(A)[(A1111∧ ∧A12∧ ∧…∧ ∧A1l1) ∨ ∨(A(A2121∧ ∧A22∧ ∧…∧ ∧A2l2) ∨ ∨ …∨ ∨ (A(Am1m1∧ ∧Am2∧ ∧…∧ ∧Amlm)]u其中其中Q Qi i(1≤i≤k)(1≤i≤k)为量词为量词 或或 ，，x xi i(i=1,2, (i=1,2, …,n),n)是客体变是客体变元，元，A Aijij是原子公式或其否定。
是原子公式或其否定例如公式例如公式是前束是前束析析取范式) 离散数学离散数学定理定理2-6.3 每一个每一个wffA都可转化为与其等价的前束析取范式都可转化为与其等价的前束析取范式例题例题4 将将wffD：： 转化为与其等价的前束析取范式转化为与其等价的前束析取范式解解 离散数学离散数学小结：小结：本节介绍了本节介绍了谓词公式的谓词公式的前束范式、前束前束范式、前束析取析取范式和前束范式和前束合取合取范式范式. .重点掌握重点掌握前束前束析取析取范式和前束范式和前束合取合取范式求法范式求法作业作业: : 离散数学离散数学作业作业: :求下列公式的前束求下列公式的前束析取析取范式和前束范式和前束合取合取范式范式. . 离散数学离散数学 。