离散数学DiscreteMathematics上次课回顾四、谓词演算的等价式和蕴含式2、量词与联结词¬之间的关系这里A(x)是任意包括个体变元x的谓词公式，B是不包括个体变元x的任意谓词公式。证明当B为真时,左右两边都为真;否则,B为假,此时左右两边都等价于(x)A(x),证迄.3、量词扩张/收缩律(2)证明(x)A(x)B(x)(A(x)B)(B不含x)证(x)A(x)B¬(x)A(x)∨B条件表达式(x)¬A(x)∨B量词否定(x)(¬A(x)∨B)量词辖域扩张(x)(A(x)B)条件表达式证明B(x)A(x)(x)(BA(x))(B不含x)证B(x)A(x)¬B∨(x)A(x)条件表达式(x)(¬B∨A(x))量词辖域扩张(x)(BA(x))条件表达式4、量词与命题联结词之间的一些等价式5、量词与命题联结词之间的一些蕴含式用分析法证明(x)A(x)∨(x)B(x)(x)(A(x)∨B(x))。证明若(x)(A(x)∨B(x))为假,则必有个体a,使A(a)∨B(a)为假;因此A(a),B(a)皆为假,所以(x)A(x)和(x)B(x)为假，即(x)A(x)∨(x)B(x)为假。故(x)A(x)∨(x)B(x)(x)(A(x)∨B(x))表2―1谓词演算中常用的等价式和蕴含式6、多个量词的使用有两个等价关系：具有两个量词的谓词公式有如下一些蕴含关系：作业定义2-6.1一个合式公式称为前束范式，如果它有如下形式：(Q1x1)(Q2x2)…(Qkxk)A其中Qi(1≤i≤k)为或,A为不含有量词的谓词公式。特别地，若谓词公式中无量词，则该公式也看作是前束范式。前束范式的特点:所有量词均非否定地出现在公式最前面，且它的辖域一直延伸到公式之末。例如，(x)(y)(z)(P(x,y)Q(y,z))R(x,y)都是前束范式，而(x)P(x)(y)Q(y)，(x)(P(x)(y)Q(x,y))不是前束范式。定理2.6.1(前束范式存在定理)任意谓词公式A都有与之等价的前束范式。证明：前束范式的求取方法举例73页例题1、例题2、例题3例题2化公式(x)(y)((z)(P(x,z)∧P(y,z))(u)Q(x,y,u))为前束范式解第一步否定深入练习定义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：求前束合取范式的方法定义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：求前束析取范式的方法作业§2—7谓词演算的推理理论回顾：约束变元、自由变元定义2.7.1在谓词公式A(x)中，若x自由出现在量词(y)或(y)的辖域，则称A(x)对于y是自由的。由定义可知，若y在A(x)中不是约束出现，则A(x)对于y一定是自由的。一、有关量词消去和添加规则量词消去规则：量词消去规则：量词产生规则：量词产生规则：真值表法：前真：看后真；后假：前至少有一个假。直接证法：由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效的结论。间接证法要证明H1∧H2∧…∧HnC，只要证明H1，H2，…，Hn与是┐C是不相容的。要证明H1∧H2∧…∧Hn(R→C)。如能证明H1∧H2∧…∧Hn∧RC，即证得H1∧H2∧…∧Hn(R→C)。这个证明称为CP规则。二、Lp中推理实例Lp的推理方法是Ls推理方法的扩展，因此在Lp中利用的推理规则也是T规则、P规则和CP规则，还有已知的等价式，蕴含式以及有关量词的消去和产生规则。使用的推理方法是直接构造法和间接证法。例题1证明苏格拉底论证：所有的人都是要死的。苏格拉底是人。所以苏格拉底是要死的。例题2证明例题3证明证法2本题可用CP规则例题4构造下面推理的