[工学]离散数学教案谓词逻辑2.pptVIP

* Discrete Mathematics 西南科技大学 计算机科学与技术学院 第二章 谓词逻辑 2.3 谓词公式的解释与分类 一、谓词公式的解释 定义 谓词公式的解释是指对公式中以下一些符号进行指定： 1.谓词公式A的个体域D 2.为每一个个体变元指定D中的一个元素 3.每一个n元函数Dn到D的一个映射 4.每一个n元谓词Dn 到{0,1}的一个映射 称以上一组指定为谓词公式A的一个解释或赋值。 并采用以下方法消去谓词公式中量词: 当个体域为有限集时，如D={a1,a2,…,an}，由量词的定义可以看出，对于任意的谓词A(x)，都有 　(1) 　(2) 即：个体域有限，“任意”可转化成“合取”； “存在”可转换成“析取” 例 求下列谓词公式的真值： 1. ?x(F(x)∧G(x,a)) 2. ?x(F(f(x))∧G(x,f(x))) 3. ?x?yL(x,y) 假设给定上述公式的一个解释如下： 1. D={2，3}; 2. 个体常元：a=2; 3. 函数f(x)为f(2)=3，f(3)=2; 4. 谓词F(x)为：F(2)=0，F(3)=1 G(x,y)为：G(i,j)=1，i,j=2,3; L(x,y)为：L(2,2)= L(3,3)=1；L(2,3)=L(3,2)=0 解 在解释I下 1. 2. 3. 例2：指定一个解释N如下： (1) 个体域为自然数集合DN (2) 个体常元：a=0 (3) DN上的指定函数为：f(x,y)=x+y，g(x,y)=x*y (4) 指定谓词F(x,y)为：x=y 在以上指定的解释N下，求下列谓词公式的真值： (1) ?xF(g(x,a),x) (2) ?x?y(F(f(x,a),y)?F(f(y,a),x)) (3) F(f(x,y),f(y,z)) 解：(1)在指定解释N下，?xF(g(x,a),x) 即?x(x*0=x)，所以该命题假的 (2)?x?y(F(f(x,a),y)?F(f(y,a),x)) 在解释N下此公式：??x?y(x+0=y?y+0=x)，故此命题为真 (3) 谓词公式F(f(x,y),f(y,z))在解释N下该公式 ?x+y=y+z 此时，x,y,z均为自由变元，由于解释没对自由变元进行指定。因而该公式是命题函数，不是命题，真值不能确定。 对解释的有关说明1. 一个谓词公式如果不含自由变元，则在一个解释下，可以得到确定的真值，不同的解释下可能得到不同的真值。 2. 公式的解释并不需要对自由变元进行指定，如果公式中含有自由变元，即使对公式进行了一个赋值，也得不到确定的真值，结果仅是个命题函数，但约束变元不受此限制。 3. 从公式的解释定义可以看出，一个谓词公式的解释有许多，当D为无限集时，公式有无限多个解释，根本不可能将其一一列出。因而谓词逻辑的公式一般不能用真值表列出。 二、谓词公式的分类及判断 定义 设A为一个谓词公式，如果A在任何解释下均为真，称A为永真式； 如果A在任何解释下均为假，称A为永假式； 如果存在一个解释使A为真，则称A为可满足式； 判断方法一：若谓词公式A的个体域是有限的，谓词的解释也是有限的，则可用真值表判断谓词公式的类型。 判断方法二：根据定义直接判断 例 判断下列谓词公式的类型？ ?xF(x) →?xF(x) 解：设I为任意的解释，某个体域为D。若存在x0∈D，使得F(x0)为假，则?xF(x)为假， 所以?xF(x) →?xG(x)为真。 若对任意x∈D，都有F(x)为真，则?xF(x)、 ?xF(x)均为真，所以?xF(x) →?xG(x)为真。故在解释I下，原公式为真。 由于I的任意性，所以原公式是永真式(逻辑有效)的。 定义 设A0是含命题变元P1，P2，…，Pn的命题公式， A1，A2，…，An是n个谓词公式，用Ai处处代换Pi，所得公式A称为A0的代换实例。 例如，谓词公式F(x) →G(x) ，?xF(x) →?xG(x) 等都是命题公式 p→q的代换实例。 命题公式中的重言式的代换实例在谓词公式中仍为重言式，命题公式中的矛盾式的代换实例仍为矛盾式。 解：(1)由