离散数学教程ch2谓词演算(A13信息).ppt

* 例2.13 由A╞╡┐A*(┐p1/p1, …, ┐pn/pn) 可立即推得 ┐?xp(x)╞╡┐┐?x┐p(x)╞╡?x┐p(x) 对偶原理 定理1.5设A，B为仅含联结词┐，∧，∨和命题变元p1,…,pn的命题公式， 且满足A╞ B，那么有B*╞ A*。 进而当A╞╡B时有A*╞╡B*。 常把B*╞ A*，A*╞╡B*称为 A╞B和A╞╡B的对偶式。 * 例2.13 利用“若A╞B，则B*╞A*” ， ?x A(x)∨?x B(x)╞ ?x (A(x)∨B(x)) 可导出 ?x (A(x)∧B(x))╞ ?x A(x)∧?x B(x) 利用“若 A╞╡B，则A*╞╡B*” ?x?yA(x,y)╞╡?y?x A(x,y) 可导出 ?x?yA(x,y)╞╡?y?x A(x,y) * 十二、谓词公式的前束范式 定义2.7 ：公式A’称为公式A的前束范式， 如果 A╞╡A’， 且A’形如Q1x1…QnxnB 其中Q1，…，Qn为量词 ? 或 ?， B称为母式，B中无量词。 当B为合取（析取）范式时，A’称为A的前束 合取（析取）范式。 * 十二、谓词公式的前束范式 例如： ?x ?y (A(x)∧B(y)) ?x ?y (A(x,y)→B(x,y)) 是前束范式 ?x?y (?zA(x,y,z) ??z B(x,y,z)) ?xA(x,y)→?yB(x,y) ?x ?y A(x,y)→B(x,y) 均不是前束范式 * 十二、谓词公式的前束范式 对任何谓词公式均可作出其前束范式，因为我 们总可以利用各组逻辑等价式将量词逐个移至 公式的前部，其步骤是: 1）将公式中联结词→,? 消除。 2）将否定词 ┐深入到各原子公式之前。 3）如果需要的话，将约束变元进行改名。 4）利用2.2.2节的第（5）组和第（6）组永真式（不包括逻辑蕴涵式）将量词逐个移至公式前部。 * 说明：需要改名的情况： 1) ?xA(x)∨?xB(x)┝┥?x?y(A(x)∨B(y)) ?xA(x)∧?xB(x)┝┥?x?y(A(x)∧B(y)) (?对∨，?对∧，量词不能合并，因而其中一个约束变元需要改名。) 2) ?xA(x)∧?x B(x)┝┥?x?y (A(x)∧B(y)) (两个不同性质的量词，用的是同一指导变元，必须改名。) 3)?xA(x)∧B(x,y)┝┥?z(A(z)∧B(x,y)) (X既是约束变元，又是自由变元，约束变元必须改名，然后再辖域扩充。) * 例2.15 ： 求以下两式的前束范式： （1）?xA(x)→?x B(x) （2）?x?y (?z(P(x,z)∧P(y,z))→?zQ(x,y,z)) * 例2.14 ： 求以下两式的前束范式： （1）?xA(x)→?x B(x) 解： ?xA(x)→?x B(x) ╞╡┐?xA(x)∨?x B(x) ╞╡ ?x┐A(x)∨?x B(x) ╞╡ ?x(┐A(x)∨B(x)) （已是前束范式） ╞╡ ?x(A(x)→B(x))) * 例2.14 ： 求以下两式的前束范式： ?x?y(?z(P(x,z)∧P(y,z))→?zQ(x,y,z)) ╞╡?x?y(┐?z(P(x,z)∧P(y,z))∨?zQ(x,y,z)) ╞╡?x?y(?z(┐P(x,z)∨┐P(y,z))∨?z Q(x,y,z)) ╞╡?x?y (?z(┐P(x,z)∨┐P(y,z))∨?u Q(x,y,u)) ╞╡?x?y ?z?u (┐P(x,z)∨┐P(y,z)∨Q(x,y,u)) ╞╡?x?y ?z?u (P(x,z)∧P(y,z)→Q(x,y,u)) * 在命题演算中，任一逻辑等价式或逻辑蕴涵式，其中同一命题变元，当用同一命题公式取代时，其结果仍是逻辑等价式或逻辑蕴涵式。　 将此情况推广到谓词公式中，用谓词公式去取代命题演算中逻辑等价式或逻辑蕴涵式的命题变元时，便得到谓词演算的逻辑等价式或逻辑蕴涵式。 （1）所有命题演算中的重言式 * 例2.8 A(x)→A(x) A(x)→(B(x)→A(x)) (┐A(x)→┐B(x))→(B(x)→A(x)) （1）所有命题演算中的重言式 * 又例： A∧A╞╡A ?xA(x) ∧ ?xA(x) ╞╡ ?xA(x) A→B ╞╡┓A∨B ?xA(x) → ?