一阶逻辑等值演算与推理课件(离散数学)精讲.ppt

《一阶逻辑等值演算与推理课件(离散数学)精讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章一阶逻辑等值演算与推理1本章主要内容5.1一阶逻辑等值式与置换规则5.2一阶逻辑前束范式5.3一阶逻辑的推理理论25.1一阶逻辑等值式与置换规则等值式的概念基本等值式等值演算与置换规则3所有的学生都上课了，这是错的。令F(x):x是学生,G(x):x上课了。这句话相当于“有些学生没有上课”。4一、等值式的概念定义：若AB为永真式，则称A与B是等值的，记作AB，并称AB为等值式。其中A、B是一阶逻辑中任意的两个合式公式。5二、基本等值式命题逻辑中16组基本等值式的代换实例例：xF(x)yG(y)xF(x)yG(y)(xF(x)yG(y))xF(x)

2、yG(y)即命题逻辑中的基本等值式在谓词逻辑中均适用。6二、基本等值式有限个体域中，消去量词等值式设个体域为D={a1,a2,…,an}xA(x)A(a1)A(a2)…A(an)xA(x)A(a1)A(a2)…A(an)7二、基本等值式量词否定等值式“并不是所有的人都是黄皮肤。”这句话相当于“有的人不是黄皮肤。”8二、基本等值式量词辖域收缩与扩张等值式设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、9二、基本等值式关于存在量词: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)10二、基本等值式量词分配等值式x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)注意：对无分配律，对无分配律11三、等值演算与置换规则置换规则：设(A)是含有公式A的公式，用公式B置换(A)中所有的A后得到新的公式(B)，若AB,则(B)(A)等值演算的基础：（1）一阶逻辑的基本等值式；（2）置换规则、换名规则、代替规则。12例题

4、例1：下面的命题都有两种不同的符号化形式，写出其中的一种，然后通过等值演算得到另一种。(1)没有不犯错误的人(2)不是所有的人都爱看电影13(1)没有不犯错误的人令F(x)：x是人，G(x)：x犯错误例题14(2)不是所有的人都爱看电影令F(x)：x是人，G(x)：爱看电影例题15例2：设个体域D={a,b,c}，在D中消去下列公式中的量词。两次使用“消去等值式”例题16量词辖域收缩与扩张等值式解法二：小结：采用不同的演算过程同样可以达到消去量词的目的，但是如何演算才更简单呢？结论是将量词辖域尽可能的缩小，然后再消量词。例题17方法2：例题18(3)当个体域D={a,b}提问：如果先消去全

5、称量词，后消去存在量词，结果会怎样？例题19该题量词的辖域已经不能再缩小了，所以演算过程无法再简化，演算结果也不易化的更简单。两种消去顺序得到的结果相同。例题20例3给定解释I如下:(a)个体域D={2，3}(b)(c)(d)谓词如下页所示例题21在I下求下列各式的真值。例题22计算过程见教材例题23例4：证明下面的谓词公式是永真式。证明谓词公式是永真式不能像命题公式那样使用真值表。常用的方法是等值演算。例题24经过等值演算可知该公式是永真式。例题25例题26兔子比乌龟跑得快。令：F(x):x是兔子G(y):y是乌龟L(x,y):x比y跑得快命题符号化为：另外一种等值的符号化形式为：275

6、.2前束范式定义：设A为一个一阶逻辑公式,若A具有如下形式Q1x1Q2x2…QkxkB,则称A为前束范式,其中Qi(1ik)为或，B为不含量词的公式。例：xy(F(x)(G(y)H(x,y)))x(F(x)G(x))x(F(x)G(x))不是前束范式。B前束范式B285.2前束范式(1)x(M(x)F(x))解：x(M(x)F(x))x(M(x)F(x))（量词否定等值式）x(M(x)F(x))两步结果都是原公式的前束范式。例1：求下列公式的前束范式295.2前束范式(2)xF(x)xG(x)解：xF(x)xG(x)

7、xF(x)xG(x)（量词否定等值式）x(F(x)G(x))（量词分配等值式）另有一种形式如下：305.2前束范式xF(x)xG(x)xF(x)xG(x)xF(x)yG(y)(换名规则)x(F(x)yG(y))(量词辖域扩张)xy(F(x)G(y))(量词辖域扩张)315.2前束范式(3)xF(x)xG(x)解xF(x)xG(x)xF(