第2章谓词逻辑(02).ppt

《第2章谓词逻辑(02).ppt》由会员分享，可在线阅读，更多相关《第2章谓词逻辑(02).ppt（64页珍藏版）》请在三一办公上搜索。

1、离 散 数 学,戎 玫,第2章 谓词逻辑,2.1 个体、谓词与量词2.2 谓词公式2.3 谓词演算的等价式与蕴含式2.4 前束范式2.5 谓词逻辑的推理理论,2.1.1 个体,苏格拉底推论所有的人总是要死的苏格拉底是人苏格拉底总是要死的将原子命题进一步细分，分解出个体、谓词和量词，以表达个体与总体的内在联系和数量关系，即谓词逻辑研究的内容。,2.1 个体、谓词与量词,2.1.1 个体,考察下面的三个原子命题：李玲是优秀共产党员。张华比李红高。小高坐在小王和小刘的中间。个体是指所研究对象中可以独立存在的具体的或抽象的客体。个体常用小写英文字母或小写英文字母带下标表示，叫做个体标识符。表示具体或特

2、定个体的标识符称个体常元。例如：李玲、张华可如下表示：a：李玲 b：张华,2.1.1 个体,将表示任意个体或泛指某类个体的标识符称为个体变元，常表示为x、y、z、等或这些英文字母带下标。个体变元的变化范围称为个体域或论域。个体域可以是有穷集合，也可以是无穷集合，包含任意个体域的个体域称为全总个体域，它是由宇宙间一切对象组成的集合。在本课程中，如无特别说明，所采用的都是全总个体域。,2.1.2谓 词,刻划个体性质或几个个体关系的模式叫做谓词。谓词常用大写英文字母表示，叫做谓词标识符。例如可以用F，G，H表示前面三个命题中谓词：F：是优秀共产党员。可以分解成为个体“李玲”和“是优秀共产党员”两部分

3、。“是优秀共产党员”是用来描述个体“李玲”的性质；G：比高。H：坐在和的中间。,2.1.2谓 词,把与一个个体相关联的谓词叫做一元谓词。把与两个个体相关联的谓词叫做二元谓词。把与三个个体相关联的谓词叫做三元谓词。一般的，把与n个个体相关联的谓词叫做n元谓词。F是一元谓词；G是二元谓词；H是三元谓词；,2.1.2谓 词,设F是一元谓词，a是个体常元，用F(a)表示个体常元a具有性质F；设G是二元谓词，a,b是个体常元，用G(a,b)表示个体常元a和b具有关系G；于是上面三个命题就表示为：F(a)：李玲是优秀共产党员。G(b,c)：张华比李红高。H(d,e,f)：小高坐在小王和小刘的中间。将谓词后

4、面填上相关联的个体常元所得的式子叫做谓词填式。F(a)，G(b,c)，H(d,e,f)都是谓词填式。谓词填式表示的是命题。,2.1.2谓 词,类似的，用F(x)表示个体变元x具有性质F，F(x)叫做一元命题函数；用G(x,y)表示个体变元x和y具有关系G，G(x，y)叫做二元命题函数；用P(x1,x2,xn)(n1)表示个体变元x1,x2,xn具有关系P。P(x1,x2,xn)为n元命题函数。命题函数没有确定的真值，它不是命题。只要用个体常元取代所有的个体变元，就得到了命题。,2.1.2谓 词,例，H(x,y)：x+y0，此命题函数是否为命题？令 a：5,b：7 H(a,b)是否为命题？真值？

5、用个体常元取代命题函数的所有个体变元所得到的表达式就是谓词填式，谓词填式也叫做0元命题函数。F(a)，G(b,c)，H(d,e,f)都是0元命题函数，它们都是命题。命题逻辑中的命题均可以表示为谓词逻辑中的0元命题函数(谓词填式)，命题成为命题函数的特例。,2.1.2谓 词,【例2.1】将下列命题符号化，并讨论它们的真值。2与3都是偶数。如果5大于3，则2大于6。,解：设F(x)：x是偶数。a：2，b：3 该命题符号化为：F(a)F(b)F(b)表示3是偶数，它是个假命题。所以F(a)F(b)为假。,设G(x,y)：x大于y a：5，b：3，c：2，d：6 该命题符号化为：G(a,b)G(c,d

6、)G(a,b)表示5大于3，它是真命题。G(c,d)表示2大于6，这是个假命题。所以G(a,b)G(c,d)为假。,2.1.3 量词,量词分两种：全称量词全称量词符号化为“”。即“一切的”，“所有的”，“每一个”等。用(x)，(y)等表示个体域里的所有个体，(x)F(x)表示个体域中的所有个体都有性质F。存在量词存在量词符号化为“”。即“存在”，“有一个”，“有些”等。用(x)，(y)等表示个体域里有些个体，用(x)F(x)表示在个体域中存在个体具有性质F。全称量词与存在量词统称为量词。,2.1.3 量词,【例2.2】个体域是人类集合，对下列命题符号化。凡人要死。有的人是研究生。解：令F(x)

7、：x要死。命题“凡人要死。”符号化为：(x)F(x)令G(x)：x是研究生。命题“有的人是研究生。”符号化为：(x)G(x)在命题函数前加上量词(x)和(x)分别叫做个体变元x被全称量化和存在量化。如果对命题函数中所有命题变元进行全称量化或存在量化，该函数就变成了命题。,2.1.3 量词,【例2.3】对下列命题符号化，并在，三个个体域中考察命题的真值。命题：所有数小于5。至少有一个数小于5。个体域：-1，0，1，2，4 3，-2，7，8 15，20，24,解：设L(x)：x小于5。“所有数小于5。”符号化为：(x)L(x)在个体域，中，它们的真值分别为：真，假，假。“至少有一个数小于5。”符号

8、化为：(x)L(x)在个体域，中，它们的真值分别为：真，真，假。,2.1.3 量词,设个体域为D=-2,3,6，谓词P(x)：x3，G(x)：x5，R(x)：x7，求下列各谓词公式的真值。1、(x)(P(x)G(x)。2、(x)(R(x)P(x)G(5)3、(x)(P(x)G(x)解：,2.1.3 量词,命题函数中的个体变元量化以后变成命题，其真值与个体域的选择有关，为了统一我们使用全总个体域，而对于其它个体域用一个谓词来表示，即特性谓词。特性谓词：用一个谓词来表示除全总个体域外的特殊的个体域。特性谓词加入的方法为：对全称量词，特性谓词作为条件命题的前件加入。对存在量词，特性谓词作为合取项加入

9、。,2.1.3 量词,【例2.4】对下列命题在，两个个体域中符号化。命题：所有老虎是要吃人。存在一个老虎要吃人。个体域：所有老虎组成的集合。全总个体域。解：设A(x)：x是要吃人的。个体域为所有老虎的集合。符号化为(x)A(x)符号化为(x)A(x)个体域为全总个体域。设特性谓词T(x)：x是老虎。符号化为(x)(T(x)A(x)符号化为(x)(T(x)A(x),特性谓词的位置和描述,(1)在全称量词下的特性谓词例：所有的北京人均去过天安门符号：P(x)：x是北京人 Q(x)：x去过天安门正确符号：(x)(P(x)Q(x)字面翻译为：全总个体域中任一个x，如果x是北京人，则他就去过天安门。这是

10、符合原句的。如果在全称量词下，我们把特性作为合取式一项:(x)(P(x)Q(x)则该命题变成了假命题（矛盾式）。,特性谓词的位置和描述,(1)在全称量词下的特性谓词例：凡人要死符号：P(x)：x是人 D(x)：x是要死的正确符号：(x)(P(x)D(x)如果描述为：(x)(P(x)D(x)字面翻译为：“全总个体域中每一个x，x是人并且x会死。”这显然是假命题。因为我们只要取一个不是人的个体xo。则P(xo)是假命题，则P(xo)D(xo)是假命题，则(x)(P(x)D(x)就是假命题。,特性谓词的位置和描述,(2)在存在量词下的特性谓词例：有一个南京人他去过北京符号：N(x)：x是南京人 P(

11、x)：x去过北京正确描述：(x)(N(x)P(x)存在量词下，特性谓词作合取式的一项。如果存在量词下，我们将特性谓词作为蕴涵的前体，这样会导致原来的命题变成了永真式。,特性谓词的位置和描述,(2)在存在量词下的特性谓词例：有一个人他去过太阳。符号：P(x)：x是人 Q(x)：x去过太阳 正确描述：(x)(P(x)Q(x)存在量词下，特性谓词作合取式的一项。如果描述为：(x)(P(x)Q(x),2.1.3 量词,有些自然数是素数。金子是闪光的，但闪光的并不都是金子。所有运动员都钦佩某些教练员。解：设N(x)：x是自然数。P(x)：x是素数。(x)(N(x)P(x)解：设G(x)：x是金子。S(x

12、)：x是闪光的。(x)(G(x)S(x)(x)(S(x)G(x)解：设L(x)：x是运动员。C(x)：x是教练员。A(x,y)：x钦佩y。(x)(L(x)(y)(C(y)A(x，y),实例,例1：所有演员均佩服一些教师例2：所有的病人均相信一些医生，而所有的病人均不相信一切骗子。P(x)：x是演员 Q(x)：x是教师 R(x,y)：x佩服y描述为：(x)(P(x)(y)(Q(y)R(x，y)P(x)：x是病人 Q(x)：x是医生 R(x)：x是骗子 S(x,y)：x相信y描述为：(x)(P(x)(y)(Q(y)S(x，y)(x)(P(x)(y)(R(y)S(x，y),2.2.1 谓词公式,定义

13、2.2.1 按下列规则构成的表达式称为谓词演算的合式公式，简称谓词公式。谓词演算的原子公式是合式公式。若A是合式公式，则A是合式公式。若A和B是合式公式，则(AB)，(AB)，(AB)和(AB)是合式公式。如果A是合式公式，x是A中出现的任意个体变元，则(x)A，(x)A是合式公式。只有有限次地应用、所得的公式是合式公式。,2.2.1 谓词公式,谓词公式也有以下约定：最外层的括号可以省略。如果按、在运算中的优先级别，省略括号后不改变原来的运算次序，可以省略括号，但量词后面括号不能省略。,2.2.1 谓词公式,【例2.5】并非每个实数都是有理数。解：设R(x)：x是实数 Q(x)：x是有理数 该

14、命题符号化为：(x)(R(x)Q(x)【例2.6】没有不犯错误的人。解：设M(x)：x是人 F(x)：x犯错误 符号化为：(x)(M(x)F(x)【例2.7】并不是所有的兔子都比所有的乌龟跑得快。解：设F(x)：x是兔子。G(x)：x是乌龟。H(x,y)：x比y跑得快。该命题符号化为：(x)(y)(F(x)G(y)H(x,y),多个量词同时出现时，不能随意颠倒它们的顺序。颠倒后会改变原命题的含义。例如：对任意的x，存在着y，使得xy5。取个体域为实数集，用H(x，y)表示xy5，这个命题符号化为：(x)(y)H(x，y)如果将量词的顺序颠倒：(x)(y)H(x，y),2.2.2约束变元与自由变

15、元,定义2.2.2 如果A是谓词公式B的一部分且是谓词公式，则称A是B的子公式。定义2.2.3 紧接量词以后的最小子公式叫做该量词的辖域或作用域。定义2.2.4 量词(x)和(x)中的x叫做该量词的指导变元或作用变元。定义2.2.5 量词(x)和(x)的辖域内x的一切出现叫约束出现，x叫做约束变元；约束变元以外的其它变元的出现叫自由出现，自由出现的变元叫自由变元。,2.2.2约束变元与自由变元,【例2.10】说明下列各式量词的辖域，找出约束变元和自由变元。(x)P(x)Q(y)(x)(P(x)(y)Q(x,y)(x)P(x)(y)Q(x,y)(x)(y)(P(x,y)Q(y,z)(x)R(x,

16、y)解：(x)的辖域为P(x)，x是约束变元，y是自由变元。(x)的辖域为P(x)(y)Q(x,y)，(y)的辖域为Q(x,y)，x和y都是约束变元，无自由变元。(x)的辖域为P(x)，(y)的辖域为Q(x,y)，P(x)中的x和Q(x,y)中的y是约束变元，Q(x,y)中的x是自由变元。(x)的辖域为(y)(P(x,y)Q(y,z)，(y)的辖域为P(x,y)Q(y,z)，(x)的辖域为R(x,y)，(P(x,y)Q(y,z)中的x、y是约束变元，z是自由变元，R(x,y)中的y是自由变元。,2.2.2约束变元与自由变元,换名规则：对约束变元可以换名，其更改变元名称的范围是量词的指导变元，以

17、及该量词辖域中的所有该变元，公式的其余部分不变。换名时一定要更改成辖域中没有出现的变元名，最好是公式中没有的变量名。代入规则是：对于谓词公式中的自由变元可以代入，代入时需对公式中该变元自由出现的每处进行。代入的变元与原公式中其他变元的名称不能相同。,2.2.2约束变元与自由变元,【例2.11】对(x)(y)(P(x,y)Q(y,z)(x)R(x,y)中的约束变元y换名。解：用u置换约束变元y。换名后为：(x)(u)(P(x,u)Q(u,z)(x)R(x,y)不能换成：(x)(u)(P(x,u)Q(y,z)(x)R(x,y)也不能换成：(x)(z)(P(x,z)Q(z,z)(x)R(x,y)【例

18、2.12】对(x)(P(y)R(x,y)(y)Q(y)中的自由变元y进行代入。解：用z代换y，代入后为：(x)(P(z)R(x,z)(y)Q(y)不能换成：(x)(P(x)R(x,x)(y)Q(y)或(x)(P(z)R(x,y)(y)Q(y),2.2.2 约束变元与自由变元,自然数有以下三条公理：1、每个数都有唯一的一个数是它的后继数。2、没有一个数使数1是它的后继数。3、每个不等于1的数都有唯一的一个数是它的直接先驱数。解：设N(x)：x是自然数。S(x,y)：y是x的后继(x是y的先驱)。1、(x)(N(x)(y)(N(y)S(x，y)(z)(zy)N(z)S(x,z)2、(x)(N(x)

19、S(x,1)3、(x)(N(x)S(x,2)(y)(N(y)S(y，x)(z)(zy)N(z)S(z,x),2.3谓词演算的等价式与蕴含式,定义2.3.1 设A是谓词公式，如果对A的任何赋值，A都为真，则称A是有效的或永真的。定义2.3.2 设A是谓词公式，如果对A的任何赋值，A都为假，则称A是不可满足的或永假的。定义2.3.3 设A是谓词公式，如果至少有一组赋值使A为真，则称A是可满足的。定义2.3.4 设A、B是任意两个谓词公式，对A、B的任何赋值，若其真值相同，则称A与B是等价的，记作AB；若AB是有效的，则称A蕴含B，记作AB。,2.3谓词演算的等价式与蕴含式,1命题逻辑中的等价式的推

20、广 命题演算中的所有等价式都是谓词演算中的等价式。命题逻辑中的等价式的推广 在命题逻辑中，重言式的同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式(定理1.4.2)。在谓词逻辑中可以推广为：在永真的谓词公式中，命题变元出现的每一处都用同一谓词公式置换，其结果仍是永真式。,2.3谓词演算的等价式与蕴含式,2消去量词等价式 设个体域为有限集a1，a2，an，A(x)是含自由变元x的任意谓词公式，有下列等价式成立：(x)A(x)A(a1)A(a2)A(an)(x)A(x)A(a1)A(a2)A(an)例：(x)(F(x)G(x)个体域D2,3 F(2)G(2)F(3)G(3)例：(x)(F

21、(x)G(x)个体域D2,3,2.3谓词演算的等价式与蕴含式,3量词否定等价式 设A(x)是含自由变元x的任意谓词公式。则(x)A(x)(x)A(x)(x)A(x)(x)A(x)约定，量词之前的否定联结词，不是否定该量词，而是否定该量词及其辖域。,2.3谓词演算的等价式与蕴含式,4量词作用域的扩展与收缩等价式 设A(x)是含自由变元x的任意谓词公式。B是不含变元x的谓词公式，则(x)(A(x)B)(x)A(x)B(x)(A(x)B)(x)A(x)B(x)(A(x)B)(x)A(x)B(x)(A(x)B)(x)A(x)B 利用上述四式可以得到以下四式：(x)(A(x)B)(x)A(x)B(x)(

22、A(x)B)(x)A(x)B(x)(BA(x)B(x)A(x)(x)(BA(x)B(x)A(x),2.3谓词演算的等价式与蕴含式,5量词分配等价式 设A(x)和B(x)是含自由变元x的任意谓词公式，则(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)前者可以理解为：“所有的x有性质A和性质B”和“所有的x有性质A且所有的x有性质B”是等同的。后者可以利用前者来证明。,2.3谓词演算的等价式与蕴含式,6量词与联结词的蕴含式 设A(x)和B(x)是含自由变元x的任意谓词公式。(x)A(x)(x)B(x)(x)(A(x)B(x)(x)(A(x)B

23、(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x),2.3谓词演算的等价式与蕴含式,7多个量词的使用 约定：(x)(y)A(x,y)表示(x)(y)A(x,y)多个量词相连时，同名量词是无序的，即改变它们的次序，命题真值不变。异名量词是有序的，即改变它们的次序，命题真值发生变化。对后者作如下的说明：令A(x,y)表示x+y=10，个体域为整数集合I。(x)(y)A(x,y)表示对任一整数x，存在整数y，使x+y=10。这是一个真命题。(y)(x)A(x,y)表示存在整数y，对任一整数x，有x+y=10。这是

24、一个假命题。,2.3谓词演算的等价式与蕴含式,因为同名量词是无序的，所以有：(x)(y)A(x,y)(y)(x)A(x,y)(x)(y)A(x,y)(y)(x)A(x,y)异名量词有下列的蕴含关系：(y)(x)A(x,y)(x)(y)A(x,y)(x)(y)A(x,y)(y)(x)A(x,y)具有两个量词的谓词公式还有下列的蕴含式：(x)(y)A(x,y)(y)(x)A(x,y)(y)(x)A(x,y)(x)(y)A(x,y)(x)(y)A(x,y)(y)(x)A(x,y)(y)(x)A(x,y)(x)(y)A(x,y),2.4前束范式,定义2.4.1一个公式，如果量词均在全式的开头，它们的作

25、用域延伸到整个公式的末尾，则称为前束范式。根据这个定义前束范式可表示成如下形式：(v1)(v2)(vn)A 其中：是或 vi是个体变元，i=1,n A是不含量词的谓词公式例如：(x)(y)(F(x)G(y)L(x,y)(y)(x)(z)(H(x,y)F(x)L(x,z)都是前束范式。(x)F(x)(y)(G(y)L(x,y)(y)(x)(H(x,y)F(x)(z)L(x,z)不是前束范式。,2.4前束范式,定理2.4.1 任何谓词公式,都可以化成与其等价的前束范式。【例2.16】求公式(x)F(x)(x)G(x)的前束范式。解：(x)F(x)(x)G(x)(x)F(x)(x)G(x)(x)F(

26、x)(x)G(x)(x)(F(x)G(x)(前束范式)(x)(F(x)G(x)(前束范式)【例2.17】把公式(y)G(x,y)(x)F(x,y)化为等价的前束范式。解：(y)G(x,y)(x)F(x,y)(t)G(x,t)(s)F(s,y)(t)(s)(G(x,t)F(s,y),2.4前束范式,定义2.4.2一个谓词公式A，如果具有如下形式称为前束合取范式。(v1)(v2)(vn)(A11A12 A1l1)(A21A22 A2l2)(Am1Am2 Amlm)其中：是或 vi是个体变元，i=1,n Aij是原子公式或其否定。例如(x)(y)(z)(F(x)H(x,y)G(x)(F(x)L(x,

27、z)是前束合取范式。,2.4前束范式,定理2.4.2 每个谓词公式都可化为与其等价的前束合取范式。【例2.18】将(x)F(x)(x)G(x)(x)(F(x)G(x)化为与其等价的前束合取范式。解：(x)F(x)(x)G(x)(x)(F(x)G(x)(x)(F(x)G(x)(y)(F(y)G(y)(x)(y)(F(x)G(x)(F(y)G(y)(x)(y)(F(x)G(x)(F(y)G(y)(x)(y)(F(x)G(x)(F(y)G(y)(x)(y)(F(x)F(y)G(y)(G(x)F(y)G(y),2.4前束范式,定义2.4.3一个谓词公式A，如果具有如下形式称为前束析取范式。(v1)(v

28、2)(vn)(A11A12 A1l1)(A21A22 A2l2)(Am1Am2 Amlm)其中：是或 vi是个体变元，i=1,n Aij是原子公式或其否定。定理2.4.3 每一个谓词公式A都可以化为与它等价的前束析取范式。,2.5谓词逻辑的推理理论,在谓词演算中，C是一组前提A1，A2，An的有效结论，定义为A1A2AnC。谓词推理有以下的规则：全称指定规则(US规则)(x)A(x)A(c)此式成立的条件是：c是个体域中任一个体。用c取代A(x)中x时，一定在x出现的所有地方进行取代。全称指定规则说明：若个体域中的所有个体都满足谓词A，则个体域中任一个体c也满足谓词A。它体现了在逻辑推理中由一

29、般到特殊的推导方法。,2.5谓词逻辑的推理理论,全称推广规则(UG规则)A(y)(x)A(x)此式成立的条件是：y是个体域中任一个体且对y，A(y)为真。x是不出现在A(y)中的个体变元。例如，个体域为实数集合R，G(x,y)表示xy，设A(y)(x)G(x,y)，显然A(y)满足条件，一定能推出(z)A(z)(z)(x)G(x,z)(z)(x)(xz)，这是一个真命题。若推成(x)A(x)(x)(x)G(x,x)(x)(x)(xx)，就产生了错误，原因是违背了条件。,2.5谓词逻辑的推理理论,存在指定规则(ES规则)(x)A(x)A(c)此式成立的条件是：c是个体域中的某个确定的个体，而不是

30、个体变元。c是不出现在A(x)中的个体。例如，设个体域为整数集合I，A(x)表示x是奇数，B(x)表示x是偶数。以下两个推理是对的：(x)A(x)A(c)，(x)B(x)B(d)，因此有下列推理成立：(x)A(x)(x)B(x)A(c)B(d)而下列推理是错误的：(x)A(x)(x)B(x)A(c)B(c)错误的原因是违背了条件。,2.5谓词逻辑的推理理论,存在推广规则(EG规则)A(c)(x)A(x)此式成立的条件是：c是个体域中确定的个体。x不能是出现在A(c)中的个体变元。存在推广规则说明：对于个体域中的某个个体c满足谓词A，当然有(x)A(x)。,2.5谓词逻辑的推理理论,【例2.19

31、】证明苏格拉底论证：凡人要死。苏格拉底是人，苏格拉底要死。设：H(x)：x是人。M(x)：x是要死的。s：苏格拉底。本题要证明：(x)(H(x)M(x)H(s)M(s)证明：(x)(H(x)M(x)P H(s)M(s)US H(s)P M(s)T假言推理,2.5谓词逻辑的推理理论,【例2.20】证明(x)(H(x)M(x)，(x)H(x)(x)M(x)证明：(x)H(x)P H(c)ES(x)(H(x)M(x)P H(c)M(c)US M(c)T假言推理(x)M(x)EG,2.5谓词逻辑的推理理论,若把,写在,的前面，得到如下的推理：(x)(H(x)M(x)P H(c)M(c)US(x)H(x

32、)P H(c)ES M(c)T假言推理(x)M(x)EG这个推理在逻辑上是错误的。因为中的c为个体域中一个个体，用ES规则由推到不能选择中的c，因为它要选的个体和中的个体c不一定是同一个个体，故推理是错误的。,2.5谓词逻辑的推理理论,【例2.21】证明(x)(A(x)B(x)，(x)A(x)(x)B(x)证明：用直接法证明。(x)(A(x)B(x)P A(s)B(s)US(x)A(x)P A(s)US B(s)T析取三段论(x)B(x)EG,2.5谓词逻辑的推理理论,用归谬法证明。(x)B(x)P(附加前提)(x)B(x)T量词否定等价式 B(s)US(x)(A(x)B(x)P A(s)B(

33、s)US A(s)T析取三段论(x)A(x)P A(s)US A(s)A(s)(矛盾)T合取引入,2.5谓词逻辑的推理理论,【例2.22】用CP规则证明：(x)(F(x)G(x)(x)F(x)(x)G(x)原题可改写成：(x)(F(x)G(x)(x)F(x)(x)G(x)证明：(x)F(x)P(附加前提)(x)F(x)T量词否定等价式 F(c)ES(x)(F(x)G(x)P F(c)G(c)US G(c)T析取三段论(x)G(x)EG(x)F(x)(x)G(x)CP,2.5谓词逻辑的推理理论,【例2.23】设个体域为全总个体域。证明推理：学术会的成员都是工人并且是专家。有些成员是青年人。所以有

34、的成员是青年专家。首先将命题符号化：F(x)：x是学术会成员。G(x)：x是专家。H(x)：x是工人。R(x)：x是青年人。本题要证明：(x)(F(x)G(x)H(x),(x)(F(x)R(x)(x)(F(x)R(x)G(x),2.5谓词逻辑的推理理论,证明：(x)(F(x)R(x)P F(c)R(c)ES F(c)T化简律(x)(F(x)G(x)H(x)P F(c)G(c)H(c)US|G(c)H(c)T假言推理 R(c)T化简律 G(c)T化简律 F(c)R(c)G(c)T合取引入(x)(F(x)R(x)G(x)EG,例,在一阶逻辑中构造下面推理的证明。大熊猫都产在中国。欢欢是大熊猫，所以

35、，欢欢产在中国。有理数都是实数，有的有理数是整数。因此，有的实数是整数。,等价式,(x)A(x)(x)A(x)(x)A(x)(x)A(x)(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B)(x)A(x)B(x)(A(x)B)(x)A(x)B(x)(A(x)B)(x)A(x)B(x)(A(x)B)(x)A(x)B(x)(A(x)B)(x)A(x)B(x)(A(x)B)(x)A(x)B(x)(BA(x)B(x)A(x)(x)(BA(x)B(x)A(x),蕴涵式及推理规则,(x)A(x)(x)B(x)(x)(A(x)B(x)(

36、x)(A(x)B(x)(x)A(x)(x)B(x)全称指定规则(US规则)(x)A(x)A(c)全称推广规则(UG规则)A(y)(x)A(x)存在指定规则(ES规则)(x)A(x)A(c)存在推广规则(EG规则)A(c)(x)A(x),命题定律,1.双重否定律 A A 2.交换律 AB BA，AB BA 3.结合律(AB)C A(BC)(AB)C A(BC)4.分配律 A(BC)(AB)(AC)A(BC)(AB)(AC)5.德摩根律(AB)AB(AB)AB 6.吸收律 A(AB)A A(AB)A 8.零律 A11，A00 9.同一律 A0A，A1A 12.条件等价式 AB AB 13.双条件等价式 AB(AB)(BA)14.假言易位式 AB BA 15.双条件否定等价式 AB AB,蕴含式,1.附加律 AAB，B AB 2.化简律 AB A，AB B 3.假言推理 A(AB)B 4.拒取式 B(AB)A 5.析取三段论 A(AB)B，B(AB)A 6.假言三段论(AB)(BC)(AC)7.等价三段论(AB)(BC)(AC)8.构造性二难(AC)(AB)(CD)BD(AA)(AB)(AB)B 9.破坏性二难(BD)(AB)(CD)(AC),常用推理方法：真值表法直接证明法间接证明法：CP规则、归谬法,