2-67 前束范式推理理论.ppt

2-6 前束范式(prenex normal form)
定义2- 前束范式:
一个公式如果量词均包含在全式的开头,它们的作用域延伸到整个公式的末尾,则该公式叫做前束范式。
设A是一个谓词公式,如果A具有如下形式:
(Q1x1)(Q2x2) …(Qnxn)B, 其中Qi (1≤i≤n)为或,xi为客体变元,B为不含量词的谓词公式,则称A是前束范式。
定理2-:任意一个谓词公式,均与一个前束范式等价。
转化方法:
把条件或双条件联结词转化。
利用量词否定等价公式,把否定深入到命题变元和谓词公式的前面。
换名。
利用量词作用域的扩张和收缩等价式,把量词提到前面。
2-6 前束范式(prenex normal form)
前束合取范式
定义2- 前束合取范式:
一个wff A如果具有如下形式,则称为前束合取范式:
(Q1x1)(Q2x2)…(Qnxn)[(A11A12A1k1)(A21A22A2k2)(Am1Am2Amkm)]
其中Qi (1≤i≤n)为或,xi为客体变元,Aij是原子变元或其否定。
前束合取范式
定理2- :每一个wff A都可转化为与其等价的前束合取范式。
转化方法:
取消多余量词。
换名
消去条件联结词。
利用量词转化公式,把否定深入到命题变元和谓词填式的前面。
利用量词作用域的扩张和收缩等价式,把量词提到前面。
前束析取范式
定义2- 前束析取范式:
一个wff A如果具有如下形式,则称为前束析取范式:
(Q1x1)(Q2x2)…(Qnxn)[(A11A12A1k1)(A21A22A2k2)(Am1Am2Amkm)]
其中Qi (1≤i≤n)为或,xi为客体变元,Aij是原子变元或其否定。
前束析取范式
定理2- :每一个wff A都可转化为与其等价的前束析取范式。
转化方法同前。
例题4 将wff D:
(x) [(y)P(x)(z)q(z,y) (y)R(x,y)]
化为与它等价的前束合取范式。
解第一步取消多余的量词。
D (x) [P(x)(z)q(z,y) (y)R(x,y)]
第二步换名。
D (x) [P(x)(z)q(z,y) (w)R(x,w)]
第三步消去条件联接词。
D (x) [P(x)(z)q(z,y) (w)R(x,w)]
第四步将深入
D (x) [(P(x)(z)q(z,y)) (w)R(x,w)]
第五步将量词推到左边
D (x)(z)(w) [(P(x)q(z,y)) R(x,w)]
(x)(z)(w) [(P(x)R(x,w)) 
(q(z,y)R(x,w)]
2-7 谓词演算的推理理论
在谓词逻辑中,如果A1∧A2∧…∧An→B是逻辑有效式,则称B是A1, A2, …,An的有效结论,记作
A1∧A2∧…∧AnB
AB 当且仅当 AB是重言式
例如: (x)F(x) (x)F(x)
2-7 谓词演算的推理理论
谓词演算的推理,是命题演算推理的扩展,命题演算中的推理规则,如P,T和CP规则同样可以在谓词演算的推理中使用。
但是在谓词推理中,前提和结论可能会受到量词的限制。所以需要在适当时候利用消去和添加量词的规则,使得谓词演算的推理过程类似于命题演算的推理那样进行。