第2章 谓词演算

1、第二章 谓词演算1§2.1谓词演算的基本概念1§2.1.1 谓词和个体1§2.1.2 量词2§2.1.3 谓词演算公式3§2.1.4 自由变元与约束变元3§2.2 谓词演算的关系式4§2.2.1 基本定义4§2.2.2 关系式5§2.3 前束范式6§2.4 谓词演算的推理6第二章 谓词演算§2.1谓词演算的基本概念命题演算的基本研究单位是原子命题，在命题演算中，原子命题不能再分解了，比较合适研究命题之间的关系，但原子命题可以进一步分解的。著名的三段论：Ø 所有人都是要死的。&

2、#216; 张三是人。Ø 故张三是要死的。如果使用命题演算是无法证明这个论断的正确的。但我们发现这三个命题其实还有内在联系的，这就要继续分解§2.1.1 谓词和个体命题“张三是人”的“是人”就是谓词，“张三”就是个体。一元谓词：可以与一个个体相连的谓词叫一元谓词。多元谓词：可以与多个个体相连的谓词叫多元谓词。如“.与.是兄弟”就是二元谓词。 “.位于.与.之间”就是三元谓词。个体域：个体的一定变化范围。个体变元：以某个个体域为变域的变元。一般用小写字母表示。谓词命名式（谓词变项）：F(x1，x2，xn)，其中x1，x2，xn为n个个体。注：谓词命名式就是一个函数，个体域为定

3、义域，值域是T和F。定义2.1.1 由一个谓词字母和n个个体变元组成的表达式F(x1，x2，xn)称为命题函数。例1 王强是大学生，李华也是大学生。令：F(x)：x是大学生，a：王强，b：李华。则上述可表示为逻辑式：F(a)ÙF(b)例2 中国代表团访问朝鲜。令：F(x,y)：x访问y，a：中国代表团，b：朝鲜则全式为：F(a,b)例3 这座大楼建成了。令：F(x)：x建成了，G(x)：x是大的，H(x)：x是楼房，a：这座则全式为：F(a)Ù G(a) ÙH(a)例4 这个人正在看那本白皮面的书。令：F(x，y)：x正在看y，G(x)：x是人，H(y)：y是白皮

4、面的，U(y)：y是书，a：这个，b：那个则全式为：F(a，b)ÙG(a)ÙH(b)ÙU(b)例5 如果你进去，我出来。令：F(x)：x进去，G(x)：x出来，a：你，b：我则全式为：F(a)®G(b)表示谓词公式的一般准则：名词：专名一般为个体，如张三、朝鲜。 通名一般为谓词，如人、楼房。代名词：人称代词（你、我、他）、指示代词（这个、那个）是个体。 其他代词（如何、每个、有些、一些）为量词（见后）。形容词：一般为谓词。数词：一般为量词（见后）。动词：一般为谓词，如来、去、见、读、给。副词：与所修饰的动词合并为谓词，不再分解。前置词：一般是命题联结词&

5、#167;2.1.2 量词全称量词："x，表示“所有的x”或“任意的x”。如：令：A(x)：x是人，B(x)：x有两只手则“每个人有两只手”表示为：("x)A(x)®B(x)存在量词：$x，表示“存在x”或“有x”。如令：A(x)：x是人，B(x)：x很聪明。则“有人很聪明”就表示为：($x)A(x)ÙB(x)例6 没有不犯错误的人。解：令N(x)：x是人，F(x)：x犯错误，则此语句表示为：¬($x)(N(x)Ù¬F(x)例7 每个人都有一些缺点。解：令F(x，y)：x都有y，M(x)：x是人，G(y)：y是缺点，则此语句

6、表示为：("x)($y)M(x)®G(y)ÙF(x，y)例8 尽管有人聪明，但未必一切人都聪明。解：令F(x)：x聪明，M(x)：x是人，则此语句表示为：($x)M(x)ÙF(x)Ù¬("x) M(x)®F(x)§2.1.3 谓词演算公式如果P(x1，x2，xn)中没有联结词和量词就称其为谓词演算原子式，其中P为谓词，x1，x2，xn为个体变元。定义2.1.2 谓词演算公式（简称公式）产生规则：1) 每个原子公式都是公式。2) 若A是公式，则¬A是公式。3) 若A、B是公式，则(AÙB

7、)，(AÚB)，(A®B)，(AB)也都是公式。4) 若A是公式，x是任一变元且在A中不出现("x)或($x)，则("x)A或($x)A也是公式。5) 只有按上述四个规则有限步得到的符号串才是公式。u 谓词演算公式是一个按上述规则由原子公式、命题联结词、量词及括号组成的字符串。如：("x)P(x) Ö("x)P(x)ÚR(y) Ö($y)("x)F(x，y)®("x)P(x) Ö("x)( $x)P(x) ´u 量词后面若有括号不能省略。u 命题

8、演算公式是谓词演算公式的一个特例。§2.1.4 自由变元与约束变元Ø 量词("x)、( $x)中，"、$后面紧跟的变元是量词的指导变元或作用变元。Ø 紧跟量词后面的最小公式是量词的作用域或辖域。定义2.1.3 在谓词公式中若出现量词，则与前面量词的指导变元相同且出现在量词作用域内的变元叫约束变元，否则叫自由变元。例9 说明以下公式的作用域和变元的约束情况。1) ("x)P(x)®Q(x)2) ("x)P(x)® ( $y)R(x，y)3) ("x) ("y)P(x，y)ÙQ(

9、x，y)Ù($x)P(x，y)4) ("x)P(x)Ù($z)Q(x，z)®($y)R(x，y)ÚQ(x，y)u 对于P(x1，x2，xn)，若有k个变元进行约束，则成为n-k元谓词，如果没有自由变元，就是一个命题。u 为了避免由于变元的约束与自由同时出现引起概念混乱，可对约束变元改名，改名规则如下：1) 对于约束变元可以改名。范围是量词中的指导变元以及量词作用域中出现的该变元，公式其余部分不变。2) 改名时所用名称要在作用域中没有出现的变元名称。例10 ("x)P(x，y)ÚQ(x，z)可改为：("u)P(u，y

10、)ÚQ(u，z)。u 自由变元名称也可更改，这种更改叫代人。代人规则：1) 代人时，需对公式中出现该自由变元的每一处都进行更改。2) 代人的变元与原公式中所有变元的名称不能相同。例11 ($x)P(y)ÙR(x，y) 可代人为：($x)P(z)ÙR(x，z)§2.2 谓词演算的关系式§2.2.1 基本定义当个体变元和谓词变元用确定的个体和谓词取代，就称作谓词公式赋值，此时就称为具有真值T和F的命题。定义2.2.1 谓词公式G在个体域D上的一个解释（指派）I，是对给定个体域（非空）D，并对公式G中谓词变元、自由变元（也叫命题变元、个体变元）做如下

11、指定组成：1) 对每个n元谓词变元，指定一个定义在D上的谓词（常元）。2) 对每个个体变元，指定D中的一个个体。定义2.2.2 设G为任意谓词公式，E是论述域。如果G对E上的所有解释I均取真值T，则称G在E上永真。若E是全总个体域，则称G永真。定义2.2.3 设G为任意谓词公式，E是论述域。如果G对E上的所有解释I均取真值F，则称G在E上永假。若E是全总个体域，则称G永假。定义2.2.4 设G为任意谓词公式，E是论述域。如果G对E上的所有解释I至少有一个取真值T，则称G在E上可满足。若E是全总个体域，则称G可满足。定义2.2.5 设A和B为任意谓词公式，E是论述域。如果对E上的每一解释I，A与

12、B真值相同，则称A与B在E上等价。若E是全总个体域，则称A与B等价，表示为：AÛB。类似地，可定义AÞB。§2.2.2 关系式与命题演算一样，我们需要建立一些基本的等价关系和蕴含关系。1、 将命题公式推广为谓词公式表1.6.1（蕴含关系）、表1.6.2（等价关系）均可应用到谓词公式。如：("x)R(x)®($x)S(x)Û¬ ("x)R(x)Ú ($x)S(x)2、确定一些含有量词的基本公式增加的等价、蕴含关系表2.2.1E23($x)AxÚBxÛ$xAxÚ$xB(x)量词分

13、配率E24("x)AxÙBxÛ"xAxÙ"xB(x)E25¬($x)A(x)Û("x)¬A(x)量词转换率E26¬("x)A(x)Û($x)¬A(x)E27("x)AÚBxÛAÚ"xB(x)量词辖域扩张率E28($x)AÙBxÛAÙ$xB(x)量词辖域收缩率I15"xAxÚ"xB(x)Þ ("x)AxÚBxI16($x

14、)AxÙBxÞ$xAxÙ$xB(x)E29("x)A(x)®BÛ($x)A(x)®BE30($x)A(x)®BÛ("x)A(x)®BE31A®("x)B(x)Û("x) A®B(x)E32A®($x)B(x)Û($x) A®B(x)例6 求证("x)("y)(P(x)®Q(y)Û($x)P(x)®("y)Q(y)证明：("x)("

15、;y)(P(x)®Q(y) Û("x)("y)(¬P(x)ÚQ(y) Û("x) (¬P(x)Ú ("y)Q(y) Û("x) ¬P(x)Ú ("y)Q(y) Û¬ ($x) P(x)Ú ("y)Q(y) Û($x)P(x)®("y)Q(y)3、含多个量词的等价和蕴含式只考虑两个量词情况，其它情况类推。例如：P(x，y)：x与y同姓；x的论述域为甲班同学，y的论述域为

16、乙班同学。("x)("y)(P(x，y)：甲班与乙班所有同学同姓。("y)("x)(P(x，y)：乙班与甲班所有同学同姓。($x)($y)(P(x，y)：甲班与乙班有同学同姓。($y)($x)(P(x，y)：乙班与甲班有同学同姓。($y)("x)(P(x，y)：存在一个乙班同学，甲班的所有同学与TA同姓Ø ("x)("y)(P(x，y)Û ("y)("x)(P(x，y)Ø ($x)($y)(P(x，y)Û ($y)($x)(P(x，y)Ø ("x

17、)("y)(P(x，y)Þ ($y)("x)(P(x，y)Ø ("y)("x)(P(x，y)Þ($x)("y)(P(x，y)Ø ($x)("y)(P(x，y)Þ("y)($x) (P(x，y)Ø ($y)("x)(P(x，y)Þ ("x)($y) (P(x，y)Ø ("x)($y) (P(x，y)Þ ($y)($x) (P(x，y)Ø ("y)($x) (P(x，y)Þ ($x

18、)($y) (P(x，y)§2.3 前束范式与命题演算一样，谓词演算也要进行公式的规范即化为前束范式。定义2.3.1 谓词公式G称为前束范式，G为形式：(Q1x1)(Qnxn)M，其中，(Qixi)是$xi或是"xi，xi（i=1n）是个体变元，M是不含量词的公式，且只含¬，Ù，Ú；(Q1x1)(Qnxn)称为首标。定理2.3.1 对任意公式G，都存在一个与其等价的前束范式。u 一般情况下，一个公式的前束范式不是唯一的。例1 将("x)P(x)Ú($y)R(y)®("x)F(x)化为具有前束范式的形式。例

19、2 将("x)(P(x)Ú("z)Q(z，y)®¬("y)R(x，y) 化为具有前束范式的形式。（注意约束变元和自由变元）§2.4 谓词演算的推理除命题演算的推理规则可以使用外，谓词演算的推理规则由于增加了量词，所以增加了如下规则：1) US（全称指定）规则：("x)P(x)ÞP(c) 。2) UG（全称推广）规则：P(c) Þ("x)P(x)，即如果能证明每一个客体c断言P(c)都成立，则("x)P(x)成立。3) ES(存在指定)规则：($x)P(x)ÞP(c)

20、 。4) EG(存在推广)规则：P(c) Þ($x)P(x) 。例1 求证("x)H(x)®M(x)ÙH(s)ÞM(s)（著名的三段论）。证明：(1) ("x)H(x)®M(x) 前提(2) H(s)®M(s) US，(1)(3) H(s) 前提(4) M(s) (2)、(3)、I例5 求证 ("x)P(x)ÚQ(x)Þ("x)P(x)Ú($x)Q(x)证明：反证法，假设¬("x)P(x)Ú($x)Q(x)成立。(1) ¬("x)P(x)Ú($x)Q(x) 假设(2) ¬("x)P(x)Ù ¬ ($x)Q(x) (1)、E(3) ¬("x)P(x) (2)、I(4) ($x)¬P(x) (3)、E(5) ¬ ($x)Q(x) (2)、I(6) ("x)¬Q(x) (5)、E(7) ¬P(c) (4)、ES(8) ¬Q(c) (6)、US(