离散数学-数理逻辑2.3-4.pptVIP

2.3一阶逻辑等值式等值式根本等值式量词否认等值式量词辖域收缩与扩张等值式量词分配等值式前束范式1

等值式与根本等值式根本等值式:命题逻辑中16组根本等值式的代换实例如，?xF(x)??xF(x)??xF(x)?xF(x)??yG(y)???xF(x)??yG(y)?(?xF(x)??yG(y))???xF(x)???yG(y)定义设A、B是一阶逻辑中的任意两个公式，假设A?B为逻辑有效式，那么称A与B是等值的，记作A?B，并称A?B为等值式.2

根本等值式:消去量词等值式设D={a1,a2,…,an}(1)?xA(x)?A(a1)?A(a2)?…?A(an)(2)?xA(x)?A(a1)?A(a2)?…?A(an)量词否认等值式(1)??xA(x)??x?A(x)(2)??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)关于存在量词的:?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)注意：?对?无分配律，?对?无分配律量词等值式?x?yA(x,y)??y?xA(x,y)?x?y??y?xA(x,y)其中A(x,y)是x,y自由出现的谓词公式5

根本的等值式(续)例将下面命题用两种形式符号化(1)没有不犯错误的人(2)不是所有的人都爱看电影解(1)令F(x)：x是人，G(x)：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))给出演算过程，并说明理由.6

前束范式例如，?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))不是前束范式，定义设A为一个一阶逻辑公式,假设A具有如下形式Q1x1Q2x2…QkxkB,那么称A为前束范式,其中Qi(1?i?k)为?或?，B为不含量词的公式.7

公式的前束范式定理〔前束范式存在定理〕一阶逻辑中的任何公式都存在与之等值的前束范式注意:公式的前束范式不惟一求公式的前束范式的方法:利用重要等值式、置换规那么、换名规那么、代替规那么进行等值演算.8

换名规那么与代替规那么换名规那么:将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成另一个辖域中未曾出现过的个体变项符号，公式中其余局部不变，那么所得公式与原来的公式等值.代替规那么:对某自由出现的个体变项用与原公式中所有个体变项符号不同的符号去代替，那么所得公式与原来的公式等值.9

公式的前束范式(续)例求以下公式的前束范式(1)??x(M(x)?F(x))解??x(M(x)?F(x))??x(?M(x)??F(x))〔量词否认等值式〕??x(M(x)??F(x))两步结果都是前束范式，说明前束范式不惟一.10

例(续)(2)?xF(x)???xG(x)解?xF(x)???xG(x)??xF(x)??x?G(x)〔量词否认等值式〕??x(F(x)??G(x))〔量词分配等值式〕另有一种形式?xF(x)???xG(x)??xF(x)??x?G(x)??xF(x)??y?G(y)(代替规