《安全监理表格》PPT课件.ppt
第第9章谓词逻辑基础章谓词逻辑基础考察这样两个命题：考察这样两个命题：P:张天是大学生张天是大学生Q:王夜是大学生王夜是大学生在命题逻辑中不能统一表示在命题逻辑中不能统一表示为统一表示引入为统一表示引入谓词逻辑谓词逻辑9.1谓词逻辑的基本概念谓词逻辑的基本概念9.1.1 个体、谓词、谓词表达式个体、谓词、谓词表达式一个原子命题主要是由主语和谓一个原子命题主要是由主语和谓语组成。语组成。主语主语就是论述的对象称就是论述的对象称为为个体个体。个体可是具体的，或抽象的个体可是具体的，或抽象的常用常用a，b，c等表示等表示个体可是个体可是一个对象，一个对象，或或多个对象多个对象当个体是当个体是一个对象一个对象时时谓语表示谓语表示它的性质它的性质当个体是当个体是多个对象多个对象时时谓语表示谓语表示它们之间的关系它们之间的关系谓语称为谓语称为谓词谓词常用常用P,Q,R,A,B等表示等表示也常用英文单词来表示也常用英文单词来表示GREAT:大于大于;BETWEEN:位于位于之间之间当一个个体当一个个体a具有性质具有性质P时，就表时，就表示为示为P(a)。这时称。这时称P为为一元谓词一元谓词设设P：是大学生：是大学生a:张天张天b:王夜王夜则两个命题可分别表示为则两个命题可分别表示为P(a)，P(b)设设R：大于：大于则则 2大于大于3可表示为可表示为R(2,3)这时称这时称R为为二元谓词二元谓词命题：武汉位于北京和广州之间命题：武汉位于北京和广州之间设设B:位于位于和和之间之间w:武汉武汉 b:北京北京 g:广州广州则命题可表示为则命题可表示为B(w,b,g)这时称这时称W为为三元谓词三元谓词注意：当谓词涉及多个个体时注意：当谓词涉及多个个体时千万不能随意交换个体顺序千万不能随意交换个体顺序如上述如上述R(3,2)表示表示3大于大于2R(2,3)表示表示2大于大于3把语句写成如上形式把语句写成如上形式P(a),R(2,3),B(w,b,g)等就称为等就称为谓词表达式谓词表达式。例例 将下列语句写成谓词表达形式将下列语句写成谓词表达形式(1)苏格拉底是要死的。苏格拉底是要死的。设设D:是要死的是要死的s:苏格拉底苏格拉底则语句写成谓词表达式为则语句写成谓词表达式为D(s)(2)3+5=8设设ADD:+=则写成谓词表达式为则写成谓词表达式为ADD(3,5,8)个体常元个体常元代表一个确切的个体代表一个确切的个体个体变元个体变元代表任意个体的个体代表任意个体的个体例如例如设设D:是要死的是要死的s:苏格拉底苏格拉底s:某块石头某块石头D(s)为真为真D(s)为假为假当谓词表达式随个体变元的取值当谓词表达式随个体变元的取值不同而真值也不同时不同而真值也不同时该谓词表达式不再该谓词表达式不再是命题是命题，称为，称为命题函数命题函数9.1.2 命题函数与个体域命题函数与个体域简单命题函数简单命题函数由一个特定谓词由一个特定谓词P和和n个个体变元个个体变元x1,x2,xn组成的组成的P(x1,x2,xn)的表达式。的表达式。简单命题函数可用所有的命题联简单命题函数可用所有的命题联接词组成复合命题函数。接词组成复合命题函数。A(x):x 学习数据结构课程学习数据结构课程B(x):x 学习计算机数学基础学习计算机数学基础则则A(x)B(x):表示表示x学习数据结学习数据结构和计算机数学基础课程构和计算机数学基础课程A(x)B(x):表示若表示若x学习数据结学习数据结构，则他必学习计算机数学基础构，则他必学习计算机数学基础个体域个体域个体变元的变化范围个体变元的变化范围全总域全总域讨论对象遍及一切个体时，讨论对象遍及一切个体时，个体域特称为个体域特称为全总域全总域例例x是小于是小于100的质数的质数设设L(x,100)：x小于小于100P(x)：x是质数是质数则可表示为则可表示为L(x,100)P(x)y是非负实数当且仅当是非负实数当且仅当y大于等于大于等于0设设NN(y)：y是非负的是非负的E(y,0)：y等于等于0G(y,0)：y大于大于0则可表示为则可表示为NN(y)E(y,0)G(y,0)9.1.3 量词与辖域量词与辖域 谓词逻辑区别于命题逻辑还有谓词逻辑区别于命题逻辑还有一点更重要的是要讨论量词一点更重要的是要讨论量词,即指即指“所有所有,一切一切,任一个任一个,有有,某些某些,存存在在”分别用符号分别用符号 和和 来表示来表示所有所有,一切一切,任一个任一个为为全称量词全称量词用符号用符号 表示表示.有有,某些某些,存在存在为为存在量词存在量词用符号用符号 表示表示.x P(x)表示个体域中所有的个体表示个体域中所有的个体都满足谓词都满足谓词P x P(x)表示个体域中有个体满足表示个体域中有个体满足谓词谓词P设设 M(x)：x是人是人B(x)：x是勇敢的是勇敢的则则 x(M(x)B(x)表示为表示为有的个体是人且是勇敢的有的个体是人且是勇敢的或或有人勇敢有人勇敢则则 x M(x)B(x)表示为表示为若个体是人，则必定勇敢若个体是人，则必定勇敢设设L(x,2)：x小于小于2则则 x(L(x,2)L(x,2)表示为表示为所有个体或者小于所有个体或者小于2或者不小于或者不小于2则则 x(L(x,2)表示为表示为有的个体不小于有的个体不小于2量词的量词的辖域辖域 每个量词会有一个量化范围，每个量词会有一个量化范围，即对哪个谓词中的个体变元是全即对哪个谓词中的个体变元是全称的，哪个又是存在的。称的，哪个又是存在的。x P(x)量词量词 x的辖域是的辖域是P(x)x(M(x)B(x)量词量词 x的辖域为的辖域为M(x)B(x)xM(x)D(x)量词量词 x的辖域为的辖域为M(x)约束变元约束变元量词中的变元量词中的变元量词辖域中的相应变元量词辖域中的相应变元自由变元自由变元不是约束变元的不是约束变元的 x M(x)D(x)xM(x)中的中的x是是约束变元约束变元D(x)中的中的x是是自由变元自由变元注意：注意：为避免为避免x在同一公式中的变元不同在同一公式中的变元不同特对特对约束变元约束变元或或自由变元自由变元作更改作更改 x M(x)D(x)可改为可改为 x M(x)D(y)或或 y M(y)D(x)例例 确定下列量词的辖域，约束确定下列量词的辖域，约束变元与自由变元，并对约束变元变元与自由变元，并对约束变元或自由变元作适当的更改。或自由变元作适当的更改。(1)x(P(x)x B(x)解：解：x的辖域是的辖域是 P(x)x B(x)x的辖域是的辖域是B(x)x是约束变元是约束变元 x(P(x)x B(x)可改为可改为 y(P(y)xB(x)或或 x(P(x)y B(y)(2)x(P(x)y R(x,y)Q(x,z)解：解：x的辖域是的辖域是P(x)y R(x,y)y的辖域是的辖域是R(x,y)x(P(x)y R(x,y)中的中的x,y是约束是约束变元变元Q(x,z)中的中的x,z为自由变元为自由变元 x(P(x)yR(x,y)Q(x,z)可改为可改为 u(P(u)y R(u,y)Q(x,z)或或 x(P(x)y R(x,y)Q(t,z)注意：注意：全部被量化全部被量化的命题函数，的命题函数，在给定的个体域中有确定的真值在给定的个体域中有确定的真值因而是因而是命题命题如如 x P(x)x(P(x)y R(x,y)对于被量化的命题函数，在有限对于被量化的命题函数，在有限的个体域中可将量词消去，用枚的个体域中可将量词消去，用枚举的方法有如下等价式：举的方法有如下等价式：设个体域设个体域D=a1,an xP(x)P(a1)P(an)xP(x)P(a1)P(an)例例 设个体域为设个体域为a,b，消除以，消除以下下谓词中的量词。谓词中的量词。(1)x(P(x)Q(x)(2)x y R(x,y)解：解：(1)x(P(x)Q(x)(P(a)Q(a)(P(b)Q(b)(2)x y R(x,y)x(R(x,a)R(x,b)(R(a,a)R(a,b)(R(b,a)R(b,b)例例 求下式的真值求下式的真值 x(P(x)Q(x)其中个体域其中个体域D=1,2P(x):x=1,Q(x):x=2解：解：x(P(x)Q(x)(P(1)Q(1)(P(2)Q(2)(1 0)(0 1)1 1 19.1.4 谓词公式及语句的形式化谓词公式及语句的形式化 与命题公式相同，在谓词逻辑中与命题公式相同，在谓词逻辑中一个合法的符号串即为一个谓词一个合法的符号串即为一个谓词公式。公式。定义定义 归纳定义谓词公式归纳定义谓词公式,谓词公谓词公式又称合式公式，简称公式。式又称合式公式，简称公式。(1)谓词公式是公式谓词公式是公式,命题常元是命题常元是公公式式(看作零元谓词看作零元谓词),常称原子公式常称原子公式(2)如果如果A,B是公式是公式,x为任一变元为任一变元,那么那么(A),(AB),(xA),(xA),(AB),(AB),(AB)都是公式都是公式(3)只有有限步使用只有有限步使用(1)，(2)条款条款所所形成的符号串是公式。形成的符号串是公式。语句形式化过程的主要步骤是：语句形式化过程的主要步骤是：(1)准确地从语句中提取谓词。表准确地从语句中提取谓词。表示性质的谓语用一元谓词表示，示性质的谓语用一元谓词表示，表示关系的谓语用二元或更多元表示关系的谓语用二元或更多元数的谓词来表示。数的谓词来表示。(2)准确地使用量词和确定量词的准确地使用量词和确定量词的辖域，当辖域中多于一个谓词时辖域，当辖域中多于一个谓词时必须注意括号的使用。必须注意括号的使用。例例 把下列语句形式化把下列语句形式化有一个大于有一个大于10的偶数的偶数解：首先定义如下谓词解：首先定义如下谓词E(x)：x是偶数是偶数G(x,y)：x大于大于y则语句形式化为则语句形式化为 x(E(x)G(x,10)任何整数都是实数任何整数都是实数解：首先定义如下谓词解：首先定义如下谓词I(x)：x是整数是整数R(x)：x是实数是实数则语句形式化为则语句形式化为 x(I(x)R(x)不管黑猫不管黑猫,白猫抓住老鼠就是好猫白猫抓住老鼠就是好猫解：首先定义如下谓词解：首先定义如下谓词B(x)：x是黑猫是黑猫W(x)：x是白猫是白猫H(x)：x是抓住老鼠的猫是抓住老鼠的猫G(x)：x是好猫是好猫则语句形式化为则语句形式化为 x(H(x)(B(x)W(x)G(x)
