1.7 等价蕴涵范式详解.ppt

例 设 A(x,y)表示x和y同姓,论域x是甲村的人,y是乙村的人,则 (?x)(?y)A(x,y): 甲村和乙村所有的人都同姓。 (?y)(?x)A(x,y)：乙村和甲村所有的人都同姓。 显然上述俩语句的含义相同。故 (?x)(?y)A(x,y) ?(?y)(?x)A(x,y） 同理 (?x)(?y)A(x,y)： 甲村与乙村有人同姓。 (?y)(?x)A(x,y)： 乙村与甲村有人同姓。 故 (?x)(?y)A(x,y) ? (?y)(?x)A(x,y) 但是 (?x)(?y)A(x,y) 表示对于甲村所有的人，乙村都有人和他同姓。 (?y)(?x)A(x,y) 表示存在一个乙村的人，甲村所有的人和他同姓。 (?y)(?x)A(x,y) 表示对于乙村所有的人，甲村都有人和他同姓。 (?x)(?y)A(x,y) 表示存在一个甲村的人，乙村所有的人和他同姓。 上述四种语句，表达的情况各不相同，故全称量词与存在量词的次序，不能随意更换。 熟悉命题定律和蕴涵定律是命题逻辑推理的关键前提 熟悉本节的等价公式和蕴涵公式是谓词逻辑推理的关键前提 前束范式 斯柯林范式 定义2.9.1 一个合式公式称为前束范式，如果它有如下形式： (Q1x1)(Q2x2)…(Qkxk)B 其中Qi(1≤i≤k)为?或?，B为不含有量词的公式。称Q1x1Q2x2…Qkxk为公式的首标，B称为基式。 特别地，若Ａ中无量词，则Ａ也看作是前束范式。 可见，前束范式的特点是，所有量词均非否定地出现在公式最前面，且它的辖域一直延伸到公式之末。 例如，(?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 (前束范式存在定理) Lp中任意公式G都有与之等价的前束范式。 步骤 消去联结词?，?； 将联结词?向内深入，使之只作用于原子公式； 必要的时候，利用换名规则或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同； 利用量词辖域的扩张和收缩律，将所有量词以在公式中出现的顺序移到公式最前面，扩大量词的辖域至整个公式。 (1) (?x)G(x)∨(?x)H(x)? (?x)G(x)∨(?y)H(y) (?x)G(x)∧(?x)H(x) ? (?x)G(x)∧(?y)H(y) (2) (?x)G(x)∧(?x)H(x)? (?x)G(x)∧(?y)H(y) (3) (?x)G(x)∧F(x,y) ? (?z)G(z)∧F(x,y) 1. (?x)(A(x)?B)?(?x)A(x)?B 2. (?x)(A(x)?B)?(?x)A(x)?B 3. (?x)(A(x)?B)?(?x)A(x)?B 4. (?x)(A(x)?B)?(?x)A(x)?B 5. ((?x)A(x)?B))?(?x)(A(x)?B) 6. ((?x)A(x)?B))?(?x)(A(x)?B) 7. (B?(?x)A(x))?(?x)(B?A(x)) 8. (B?(?x)A(x))?(?x)(B?A(x)) 例：把公式(?x)P(x)?(?x)Q(x)转化为前束范式。 解： (?x)P(x)?(?x)Q(x) ?(?x)?P(x)?(?x)Q(x) ?(?x)(?P(x)?Q(x)) 前束范式 (?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)P(x)?(?z)Q(y))?(?x)R(x) ?(?x){(?y)A(x,y)?(?x)(?y)[B(x,y)?(?y)(A(x,y) ?B(x,y)) ]} 前束范式的的优点是全部量词集中在公式前面，其缺点是各量词的排列无一定规则，这样当把一个公式化归为前束范式时，其表达形式会显现多种情形，不便应用。1920年斯柯林(Skolem)提出对前束范式首标中量词出现的次序给出规定：每个存在量词均在全称量词之前。按此规定得到的范式形式，称为斯柯林范式。显然，任一公式均可化为斯柯林范式。它的优点是：全公式按顺序可分为三部分，公式的所有存在量词、所有全称量词和辖域。这给Lp的研究提供了一定的方便。 课本例2.6.2 等价式 蕴涵式 前束范式 斯柯林范式 谓词逻辑的推理理论 Thank you 授课