离散数学一阶逻辑等值演算与推理.ppt

*第1页，共37页，星期日，2025年，2月5日5.1一阶逻辑等值式与置换规则定义5.1设A,B是两个谓词公式,如果A?B是永真式,则称A与B等值,记作A?B,并称A?B是等值式。基本等值式:第一组命题逻辑中16组基本等值式的代换实例例如，???xF(x)??xF(x),?xF(x)??yG(y)???xF(x)??yG(y)等第二组(1)消去量词等值式设D={a1,a2,…,an}①?xA(x)?A(a1)?A(a2)?…?A(an)②?xA(x)?A(a1)?A(a2)?…?A(an)*第2页，共37页，星期日，2025年，2月5日基本等值式(2)量词否定等值式①??xA(x)??x?A(x)②??xA(x)??x?A(x)(3)量词辖域收缩与扩张等值式A(x)是含x自由出现的公式，B中不含x的自由出现.关于全称量词的：①?x(A(x)?B)??xA(x)?B②?x(A(x)?B)??xA(x)?B③?x(A(x)?B)??xA(x)?B④?x(B?A(x))?B??xA(x)*第3页，共37页，星期日，2025年，2月5日基本等值式关于存在量词的：①?x(A(x)?B)??xA(x)?B②?x(A(x)?B)??xA(x)?B③?x(A(x)?B)??xA(x)?B④?x(B?A(x))?B??xA(x)(4)量词分配等值式①?x(A(x)?B(x))??xA(x)??xB(x)②?x(A(x)?B(x))??xA(x)??xB(x)注意：?对?，?对?无分配律*第4页，共37页，星期日，2025年，2月5日置换规则、换名规则、代替规则1.置换规则设?(A)是含A的公式,那么,若A?B,则?(A)??(B).2.换名规则设A为一公式，将A中某量词辖域中个体变项的所有约束出现及相应的指导变元换成该量词辖域中未曾出现过的个体变项符号，其余部分不变，设所得公式为A?，则A??A.3.代替规则设A为一公式，将A中某个个体变项的所有自由出现用A中未曾出现过的个体变项符号代替，其余部分不变，设所得公式为A?，则A??A.*第5页，共37页，星期日，2025年，2月5日实例例1将下面命题用两种形式符号化,并证明两者等值:(1)没有不犯错误的人解令F(x)：x是人，G(x)：x犯错误.??x(F(x)??G(x))或?x(F(x)?G(x))??x(F(x)??G(x))??x?(F(x)??G(x))量词否定等值式??x(?F(x)?G(x))置换??x(F(x)?G(x))置换*第6页，共37页，星期日，2025年，2月5日实例(2)不是所有的人都爱看电影解令F(x)：x是人，G(x)：爱看电影.??x(F(x)?G(x))或?x(F(x)??G(x))??x(F(x)?G(x))??x?(F(x)?G(x))量词否定等值式??x?(?F(x)?G(x))置换??x(F(x)??G(x))置换*第7页，共37页，星期日，2025年，2月5日实例例2将公式化成等值的不含既有约束出现、又有自由出现的个体变项:?x(F(x,y,z)??yG(x,y,z))解?x(F(x,y,z)??yG(x,y,z))??x(F(x,y,z)??tG(x,t,z))换名规则??x?t(F(x,y,z)?G(x,t,z))辖域扩张等值式或者?x(F(x,y,z)??yG(x,y,z))??x(F(x,u,z)??yG(x,y,z))代替规则??x?y