离散数学2一阶逻辑中的等值一阶逻辑中的等值3等值A与与B是是等值等值的的AB为逻辑有效为逻辑有效式式记记作作 AB，并并称称AB为为等值式等值式. 常用的等值式常用的等值式？4命题逻辑中命题逻辑中1616组基本等值式的代换实例组基本等值式的代换实例如， xF(x)yG(y) xF(x)yG(y) ( xF(x)yG(y) xF(x)yG(y) 等5消去量词等值式消去量词等值式设D=a1,a2,an xA(x)A(a1) A(a2) A(an) xA(x)A(a1) A(a2) A(an)6量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式关于全称量词的： x(A(x) B)xA(x) B x(A(x) B)xA(x) B x(A(x)B)xA(x)B x(BA(x)BxA(x)关于存在量词的: x(A(x) B)xA(x) B x(A(x) B)xA(x) B x(A(x)B)xA(x)B x(BA(x)BxA(x)注：A(x)是含x自由出现的公式，B中不含x的出现7量词否定等值式量词否定等值式设设A(x)是含是含x自由出现的公式自由出现的公式 xA(x) x A(x) xA(x)x A(x)8量词分配等值式量词分配等值式 x(A(x) B(x) xA(x)xB(x) x(A(x) B(x) xA(x)xB(x)注意：注意： 对对 无分配律，无分配律， 对对 无分配律无分配律, , 即即 x(A(x) B(x) xA(x)xB(x) x(A(x) B(x) xA(x)xB(x) 9将下面命题用两种形式符号化(1) 没有不犯错误的人令F(x)：x是人，G(x)：x犯错误.x(F(x)G(x)x (F(x)G(x)x(F(x)G(x)10将下面命题用两种形式符号化(2) 不是所有的人都爱看电影令F(x)：x是人，G(x)：爱看电影.x(F(x)G(x)x (F(x)G(x)x(F(x)G(x)11一阶逻一阶逻辑的规范化辑的规范化12前束范式一阶逻辑公式A的前束范式具有形式 Q1x1Q2x2QkxkB 其中Qi(1 i k)为 或 ，B为不含量词的公式13前束范式举例 x y(F(x)(G(y) H(x,y) x (F(x) G(x)是前束范式 x(F(x)y(G(y) H(x,y)x(F(x) G(x)不是前束范式.14换名规则换什么？将量词辖域中出现的某个约束出现的个体变项及对应的指导变项怎么换？改成其他辖域中未曾出现过的个体变项符号如何处理余下部分？公式中其余部分不变结果怎么样？则所得公式与原来的公式等值. .前束范式存在定理一阶逻辑中的任何公式都存在与之等值的 前束范式怎么求？使用重要等值式置换规则换名规则15前束范式一定存在吗？16 x( M(x)F(x)（量量词否定等值词否定等值式式） x(M(x)F(x)两两步结果都是前束范式步结果都是前束范式，说说明明前束范式不惟一前束范式不惟一.x(M(x) F(x)17 xF(x)xG(x)xF(x)x G(x)（量词否定等值式量词否定等值式） x(F(x)G(x)（量词分配等值式量词分配等值式）xF(x)x G(x)（量量词否定等值式词否定等值式）xF(x)y G(y) （换（换名规名规则）则）x y(F(x)G(y) （量（量词辖域扩词辖域扩张）张）或者18 xF(x)xG(x)xF(x)x G(x)x(F(x)G(x)xF(x) yG(y)x(F(x)y G(y) x y(F(x)G(y)或者19 xF(x)y(G(x,y)H(y) zF(z)y(G(x,y)H(y) z y(F(z)(G(x,y)H(y)20 x(F(x,y)y(G(x,y) H(x,z) x(F(x,y)u(G(x,u) H(x,z) x u(F(x,y)G(x,u) H(x,z)注意： 与 不能颠倒苏格拉底三段论的正确性凡是人都要死的. 苏格拉底是人. 所以苏格拉底是要死的.设F(x)：x是人，G(x)：x是要死的，a：苏格拉底. x(F(x)G(x) F(a)G(a)设前件为真，即 x(F(x)G(x)与F(a)都为真. 由于 x(F(x)G(x)为真，故F(a)G(a)为真. 由F(a) 与F(a)G(a)为真，根据假言推理得证G(a)为真.21