1、u 要求：理解前束范式、前束合取范式和前束析取范式的定义，要求：理解前束范式、前束合取范式和前束析取范式的定义，会将一个谓词公式会将一个谓词公式wffA化为前束范式、前束合取范式和前束析化为前束范式、前束合取范式和前束析取范式。取范式。u 学习本节的目的是掌握谓词公式的标准化形式。学习本节的目的是掌握谓词公式的标准化形式。u 重点：化谓词公式为前束范式。重点：化谓词公式为前束范式。复习：（1）量词与联结词之间的关系（2）量词扩张/收缩律() ( )()( )x P xxP x () ( )()( )x P xxP x () ( )()( ( )x A xBxA xB () ( )()( ( )

2、x A xBxA xB () ( )()( )Bx A xx BA x () ( )()( )Bx A xx BA x 这里A(x)是任意包括个体变元x的谓词公式，B是不包括个体变元x的任意谓词公式。（3）量词与命题联结词之间的一些等价式）量词与命题联结词之间的一些等价式()( ( )( )() ( )() ( )x A xB xx A xx B x ()( ( )( )() ( )() ( )x A xB xx A xx B x 量词分配律量词分配律()( ( )( )() ( )() ( )x A xB xx A xx B x u（4）指导变元、作用域、约束变元、自由变元）指导变元、作用域

3、、约束变元、自由变元() ( , )x P x y量词指导变元辖域约束变元自由变元（5）约束变元换名和自由变元代入 在一公式中，有的个体变元既是约束出现，又是自由出现，这就容易产生混淆。为了避免混淆，可对约束变元换名或自由变元代入。 约束变元换名 将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。 自由变元代入 对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。2.6 前束范式前束范式(Prenex normal form2.6.1 前束范式前束范式(Prenex normal form 2.6.2 前束

4、析取范式和前束合取范式前束析取范式和前束合取范式(Prenex disjunctive normal form & Prenex conjunctive normal form 2.6.1前束范式前束范式(Prenex normal form u定义定义2.6.1:任何一个谓词公式任何一个谓词公式A，如果具有如下形式：，如果具有如下形式： (x1) (x2) (xn)B其中其中可能是量词可能是量词 或量词或量词 ， xi（i=1， n）是客体变是客体变元，元，B是不含量词的是不含量词的谓词公式，则称谓词公式，则称A是前束范式。是前束范式。u说明说明:前束范式前束范式的量词均在全式的开头

5、的量词均在全式的开头,它们的作用域延它们的作用域延伸到整个公式的末尾。伸到整个公式的末尾。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:任何一个谓词公式任何一个谓词公式,均和一个前束范式等价。均和一个前束范式等价。前束范式的求法：前束范式的求法：第一步：否定深入。即利用量词转化公式，把否定联结第一步：否定深入。即利用量词转化公式，把否定联结 词深入到命题变元和词深入到命题变元和谓词填式的谓词填式的前面。前面。第二步：改名。即利用换名规则、代入规则更换一些变第二步：改名。即利用换名规则、代入规则更换一些变元的名

6、称，以便消除混乱。元的名称，以便消除混乱。第三步：量词前移。即利用量词辖域的收缩与扩张把量第三步：量词前移。即利用量词辖域的收缩与扩张把量词移到前面。这样便可求出与公式等价的前束范式。词移到前面。这样便可求出与公式等价的前束范式。整理ppt10举例 73页 例题1，例题2，例题3整理ppt11例题例题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(

7、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)整理ppt12()() ( , )()() ( , )()( ( , )( , )xy A x yxy B x yyA y xB x y () () ( , )()() ( , )()( ( , )( , )xy A x yxy

8、 B x yyA y xB x y ( )() ( , ) ()()( , ) ()( , )( , )xy A x yxyB x yyA y xB x y 解解 第一步否定深入第一步否定深入原式原式第二步改名，以便把量词提到前面。第二步改名，以便把量词提到前面。()() ( , )()()( , )()( , )( , )xy A x yuvB u vzA z uB u z ()()()()() ( , ) ( , )( , )( , )xyuvzA x yB u vA z uB u z 例题例题3 把公式把公式练习75页（1）题将约束变元x改名为u，将约束变元y改名为z，化为前束范式化为前

9、束范式例例2:2:求下列公式的前束范式。求下列公式的前束范式。),(),()(),()(),()()6(),()()()(),()()5()()()()()4()()()()() 3()()()()()2()()()()() 1 (yxBxyAyyxByxyxAyxyxHxyGyyxFxxGxxFxxGxxFxxGxxFxxGxxFxu解解:)()()()()()()()()()()() 1 (量词分配量词转换律xGxFxxGxxFxxGxxFx)()()()()()()()()()()()()()()()()()()()()2(辖域扩张辖域扩张换名量词转换律yGxFyxyGyxFxyGyxF

10、xxGxxFxxGxxFx )(,()(),()()()()(,()()(),()()()(,()()(),()()()(,()()()(),()()(,()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()()5(辖域扩张辖域扩张辖域扩张换名代入ztHyGzxFtyxztHtyGzxFyxztHtyGzxFyxztHtyGyzxFxzxHxyGyzxFxyxHxyGyyxFxyxHxyGyyxFxyxHxyGyyxFxyxHxyGyyxFxu (6)()() ( , )()() ( , )()( ( , )( ,

11、 )() () ( , )()() ( , )()( , )( , )()() ( , )()()( , )()( ( , )( , )xy A x yxy B x yy A y xB x yxy A x yxy B x yyA y xB x yxy A x yxyB x yy A y xB x y ),(),(),(),()()()()()(,(),()(),()(),()(),(),()(),()(),()()6(zuBuzAvuByxAzvuyxzuBuzAzvuBvuyxAyxyxBxyAyyxByxyxAyx换名续2.5.2前束析取范式和前束合取范式前束析取范式和前束合取范式(Pre

12、nex disjunctive normal form & Prenex conjunctive normal form u在前束范式的基础上在前束范式的基础上,可以定义前束析可以定义前束析(合合)取范式取范式.u定义定义2.6.2:任何一个谓词公式任何一个谓词公式A，如果具有如下形式则称，如果具有如下形式则称为前束合取范式：为前束合取范式： (x1) (x2)(xn)(A11A12A1k1) (A21A22A2k2 )(Am1Am2Amkm) 其其中中n大于等于大于等于1,Aij(j=1, ,ki ,i=1,2,3,m)为原子谓词公为原子谓词公式或其否定式或其否定,为为量词量词 或量

13、词或量词 ， xi（i=1， n）为）为客客体变元体变元. u任何一个谓词公式任何一个谓词公式A，如果具有如下形式则称为前束析取范式：，如果具有如下形式则称为前束析取范式： (x1) (x2)(xn)(A11A12A1k1)(A21A22A2k2 )(Am1Am2Amkm) 其中其中n大于等于大于等于1,Aij(j=1, ,ki ,i=1,2,3,m)为原子为原子谓词公式或其否定谓词公式或其否定,为为量词量词 或量词或量词 ，xi（i=1， n）为）为客体变元客体变元. u定理定理2.6.2:每一个谓词公式都可以转化为与其等价的前束析每一个谓词公式都可以转化为与其等价的前束析(合合)取取范式范

14、式.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)(A1111A12A1l1)(A(A2121A22A2l2) (A(Am1m1Am2Amlm)u其中其中Q Qi i(1ik)(1ik)为量词为量词 或或 ，x xi i(i=1,2, (i=1,2, ,n),n)是客体变元，是客体变元，A Aijij是原子公式或其否定。是原子公式或其否定。()()()()() ( )()xzyPx

15、azbQ yab ()()()( ( )( )( ( )( , )( , )( )( , )( , )xuzP xP uP xQ y zQ x yP uQ x yQ y z 例如公式例如公式是前束合取范式是前束合取范式整理ppt21定理定理2-6.2 每一个每一个wffA都可转化为与其等价的前束合取范式。都可转化为与其等价的前束合取范式。例题例题4 将将wffD： 转化为与其等价的前束合取范式。转化为与其等价的前束合取范式。()() ( )() ( , )() ( , )xy P xz Q z yy R x y () ( )() ( , )() ( , )Dx P xz Q z yy R x

16、y () ( )() ( , )() ( , )Dx P xz Q z yw R x w () ( ( )() ( , )() ( ,)DxP xz Q z yw R x w 解解 第一步取消多余量词第一步取消多余量词第二步换名第二步换名第三步消去条件联结词第三步消去条件联结词第四步将否定深入第四步将否定深入第五步将量词推到左边第五步将量词推到左边()( ) ( )( , ) ()( , )DxP xzQ z yw R x w ()()()( )( , )( , )DxzwP xQ z yR x w ( ( x x)()( z)z)( ( w)(w)(P(x)P(x)R(x,w)R(x,w)(

17、 (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)(A1111A12A1l1) (A(A2121A22A2l2) (A(Am1m1Am2Amlm)u其中其中Q Qi i(1ik)(1ik)为量词为量词 或或 ，x xi i(i=1,2, (i=1,2, ,n),n)是客体变是客体变元，元，A Aijij是原子公式或其否定。是原子公式或

18、其否定。()()()( ( )( , )( ( )( , )xuzP xQ x yP uQ y z例如公式例如公式是前束是前束析析取范式。取范式。)定理定理2-6.3 每一个每一个wffA都可转化为与其等价的前束析取范式。都可转化为与其等价的前束析取范式。例题例题4 将将wffD： 转化为与其等价的前束析取范式。转化为与其等价的前束析取范式。()( ( )( , )() ( )() ( , )x P xQ x yy P yz Q y z ()( )( , ) () ( ) () ( , )DxP xQ x yy P yz Q y z ()( ( )( , ) () ( ) () ( , )x P xQ x yu P uz