离散数学-教案 -第2章2.3 一阶逻辑等值式与前束范式

课堂教学设计8章节（专题）第2章一阶逻辑计划学时2课题（内容）2.3一阶逻辑等值式与前束范式教育教学目的1.理解等值式的基本概念2.掌握常用的基本等值式及前束范式的求解3.思政目标：通过学习等值式的转换与前束范式的构造，提升学生分析和解决问题的能力，培养严谨的逻辑思维。通过严格的数学证明和规范的逻辑推理，增强学生的数学思维和表达能力鼓励学生在逻辑转换中寻找规律，激发创新思维，为解决实际问题提供新思路。通过逻辑知识在社会生活中的应用，帮助学生认识到逻辑思维在推动科技进步和社会发展中的重要作用，增强社会责任感。教学重点及难点1.重点：基本等值式2.难点：前束范式教学方法及手段1.讲授法2.互动式教学3.多媒体辅助教学4.案例教学法教学互动环节设计1.小组讨论：命题符号化与转换2.逻辑推理挑战：判断这两个公式是否等值，并通过逻辑推理证明或反驳3.多媒体互动练习：使用学习通，设计一些互动练习课后总结与反思第2章一阶逻辑2.3一阶逻辑等值式与前束范式谓词公式等值的定义若A«B为逻辑有效式，则称A与B是等值的，记作A⟺B，并称A⟺B为等值式.显然,A⟺B的充要条件是谓词公式A«B永真.基本等值式第一章命题逻辑中16组24个基本等值式在本节中采用代换实例之后仍然适用，例如：xF(x)yG(y)xF(x)yG(y)(xF(x)yG(y))xF(x)yG(y)消去量词等值式设D={a1,a2,…,an}xA(x)A(a1)A(a2)…A(an)xA(x)A(a1)A(a2)…A(an)量词辖域收缩与扩张等值式设A(x)是含x自由出现的公式，B中不含x的出现关于全称量词的x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)关于存在量词的x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)量词否定等值式设A(x)是含x自由出现的公式xA(x)xA(x)xA(x)xA(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)x(A(x)B(x))⇎xA(x)xB(x)但当B(x)换成没有x出现的B时，则有x(A(x)B)xA(x)B、x(A(x)B)xA(x)B通过以下例题说明等值式的应用。 例1将下面命题用两种形式符号化。(1)没有不犯错误的人(2)不是所有的人都爱看电影解：(1)令F(x)：x是人，G(x)：x犯错误.可符号化为：x(F(x)G(x))x(F(x)G(x))x(F(x)G(x))(2)令F(x)：x是人，G(x)：爱看电影.可符号化为：x(F(x)G(x))x(F(x)G(x))x(F(x)G(x))例2设个体域为D={a,b,c},，将下面各公式的量词消去：(1)xy(F(x)G(y))解：解法一xy(F(x)G(y))(y(F(a)G(y)))(y(F(b)G(y)))(y(F(c)G(y)))((F(a)G(a))(F(a)G(b))(F(a)G(c)))((F(b)G(a))(F(b)G(b))(F(b)G(c)))((F(c)G(a))(F(c)G(b))(F(c)G(c)))解法二xy(F(x)G(y))x(F(x)yG(y))量词辖域收缩与扩张等值式x(F(x)G(a)G(b)G(c))(F(a)G(a)G(b)G(c))(F(b)G(a)G(b)G(c))(F(c)G(a)G(b)G(c))(2)xyF(x,y)解：xyF(x,y)x(F(x,a)F(x,b)F(x,c))(F(a,a)F(a,b)F(a,c))(F(b,a)F(b,b)F(b,c))(F(c,a)F(c,b)F(c,c))前束范式的定义定义设A为一个一阶逻辑公式,若A具有如下形式q1x1q2x2…qkxkB,则称A为前束范式,其中qi(1ik)为或，B为不含量词的公式.例如：xy(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))换名规则：将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成其他辖域中未曾出现过的个体变项符号，公式中其余部分不变，则所得公式与原来的公式等值.公式的前束范式前束范式存在定理：一阶逻辑中的任何公式都存在与之等值的前束范式。求前束范式:使用重要等值式、置换规则、换名规则进行等值演算。例2求下列公式的前束范式(1)x(M(x)F(x))解：x(M(x)F(x))量词否定等值式x(M(x)F(x))两步结果都是前束范式，说明前束范式不唯一。(2)xF(x)xG(x)解：xF(x)xG(x)量词否定等值式x(F(x)G(x))量词分配等值式或者：xF(x)xG(x)xF(x)yG(y)换名规则xy(F(x)G(y))量词辖域扩张(3)xF(x)xG(x)解：xF(x)xG(x)x(F(x)G(x))或者：xF(x)yG(y)x(F(x)yG(y))xy(F(x)G(y))(4)xF(x)y(G(x,y)H(y))解：zF(z)y(G(x,y)H(y))zy(F(z)(G(x,y)H(y)))(5)x(F(x,y)y(G(x,y)H(x,z)))解：x(F(x,y)u(G(x,u)H(x,z)))xu(F(x,y)G(x,u)H(x,z)))注意：与不能颠倒.苏格拉底三段论的正确性“凡是人都要死的.苏格拉底是人.所以苏格拉底是要死的.”设F(x)：x是人，G(x)：x