利用联结词谓词与量词构成命题函数.PPT

计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn * * 计算机学院 * 主要内容 谓词的合适公式 谓词公式的等价 范式 * 计算机学院 * §2.2　谓词公式及其解释 同命题演算一样，在谓词逻辑中也同样包含命题变元和命题联结词，为了能够进行演绎和推理，对谓词逻辑中关于谓词的表达式加以形式化，利用联结词、谓词与量词构成命题函数，因此我们引入公式的概念。 * 计算机学院 * 四类符号 常量符号：一般用a,b,c,…；a1,b1,c1,…来表示，它可以是D中的某个元素; 变量符号：一般用x,y,z,…, x1,y1,z1,…来表示.它可以取值于D中的任意元素； 函数符号：一般用f,g,h,…, f1,g1,h1,…来表示。n元函数符号f(x1,x2,...xn)可以是Dn→D的任意一个函数； 谓词符号：一般用P,Q,R,..., P1,Q1,R1,...来表示。n元谓词符号P(x1,x2,...xn)可以是Dn→{0,1}的任意一个谓词。 注：不含变元的函数是常量； 不含客体变元的谓词是命题。 * 计算机学院 * 一、谓词的合适公式 定义2.6 谓词逻辑中的,项被递归地定义为： 1）任意的常量符号是项； 2）任意的个体变元符号是项； 3）若f(x1,x2,x3,…,xn)是n元函数符号， t1,t2,t3,…,tn是项，则f(t1,t2,t3,…,tn)是项； 4）只有有限次使用1）～3）产生的符号串才是项。 * 计算机学院 * 定义2.7 　设P(x1,x2,x3,...xn)是n元谓词，t1,t2,t3,...tn是项,则P(t1,t2,t3,...tn)是原子谓词公式，简称原子公式。 例2.1复合函数f(g(f(a),g(a,x))) 是一个项 * 计算机学院 * 满足下列条件的表达式，称为合适公式,简称公式。 1）原子公式是合适公式； 2）若G，H是合适公式，则(～G)、(～H)、（G?H）、(G∨H)、(G∧H)、(G→H)、(G?H)也是合适公式； 3）若G是合适公式，x是个体变元，则(?x)G、(?x)G也是合适公式； 4）仅仅通过有限次使用1)-3)产生的表达式才是合适公式。 定义2.8 * 计算机学院 * 例2.2 (P(x)→(Q(x,y)∨┐R(x,a,f(z)))) (P(x)∨R(y)) (?x)(P(x)) 等都是公式。 而 (?x)(P(x)→R(x) (?x)∨P(x)(?y) 等则不是公式，前者括号不匹配，后者量词无辖域。 * 计算机学院 * 二、公式的解释 定义2.9 一个定义在论域D上的公式G的每一个解释（指派）I由如下三部分组成： 1、G中的每个常量符号,指定D中的一个元素； 2、G中的每个n元函数符号,指定Dn到D的一个具体的函数； 3、G中的每个n元谓词符号,指定Dn到{0,1}的一个具体的谓词。 * 计算机学院 * 注：定义中所谓指定一个具体函数，即是对每组可能的变量值给出函数的对应值；所谓指定一个具体的谓词，就是对每组可能的客体变元取值给出谓词的对应值，1表示逻辑真，0表示逻辑假。 * 计算机学院 * 含有量词的公式的解释 对于含有量词的公式的解释，需要根据量词的逻辑意义来决定公式的值。 设论域 D={a1,a2, …，an} 1）（?x)P(x) ? P(a1) ∧ P(a2) ∧…∧P(an) 表示公式（?x)P(x)值为1“当且仅当”对论域D中每个元素a， P(a)的值为1。 2）（?x)P(x) ? P(a1) ∨ P(a2) ∨…∨P(an) 表示公式（?x)P(x)值为0“当且仅当”对论域D中每个元素a，P(a)的值为0（或在论域D中至少存在一个元素a，使P(a)的值为1）。 * 计算机学院 * 例2.3 设公式：(?x)(?y)(P(x,y)→Q(x,y))。在如下给定的解释下,判断该公式的真值。 1)、解释I为： ①.个体域为N+(严格大于0的整数)； ②.P(x,y)指定为：“y≥x”； ③.Q(x,y)指定为：“y≥1”。 则原公式的真值为“真”。因确能找到一个x（=1）∈N+，使得对任意y,都有y≥x和y≥1。 此时蕴涵公式的前件为真，后件也为真。所以，整个公式为真。 在此解释下，原公式变成下述命题：存在一个正整数x，使对任意的正整数y，如y≥x，则y≥1。 显然，该命题是正确的。 * 计算机学院 * 例2.3（续1） 2)、解释I为： ①.个体域为N； ②.P(x,y)指定为：“xy＝0”； ③.Q(x,y)指定为：“x