离散数学第2章谓词逻辑

《离散数学第2章谓词逻辑》由会员分享，可在线阅读，更多相关《离散数学第2章谓词逻辑（113页珍藏版）》请在金锄头文库上搜索。

1、1,第二章 谓词逻辑,1 谓词的概念与表示法 2 命题函数与量词 3 谓词公式与翻译 4 变元的约束 5 谓词演算的等价式与蕴含式 6 前束范式 7 谓词演算的推理理论,2,1 谓词的概念与表示法,1. 谓词的提出 在研究命题逻辑中，原子命题是命题演算中最基本的单位，不再对原子命题进行分解，这样会产生两大缺点： （1）不能研究命题的结构、成分和内部逻辑的特征； （2）也不可能表达二个原子命题所具有的共同特征，甚至在命题逻辑中无法处理一些简单又常见的推理过程。,3,1 谓词的概念与表示法,命题逻辑的局限： 1. 命题作为最小的基本单元。例 P: 王红是个大学生。Q: 黎明是个大学生。 2. 命题

2、逻辑在推证中的局限。,4,1 谓词的概念与表示法,例：苏格拉底论证是正确的，但不能用命题逻辑的推理规则推导出来。 所有的人都是要死的， P 苏格拉底是人， Q所以苏格拉底是要死的。 R 则有 P，QR 然而，(PQ)R并不是永真式，故上述推理形式 是错误的。,5,1 谓词的概念与表示法,2. 谓词的概念在命题逻辑中，命题是具有真假意义的陈述句。从语法上分析，一个陈述句由主语和谓语两部分组成。在谓词逻辑中，为揭示命题内部结构及其不同命题的内部结构关系，对命题进行分析，并且把主语称为个体或客体，把谓语称为谓词。,定义：在反映判断的句子中，用以刻划客体的性质或关系的即是谓词。,6,1 谓词的概念与表

3、示法,客体，是指可以独立存在的事物，它可以是具体的，也可以是抽象的，如张明，计算机，精神等。 表示特定的个体，称为客体常元，以a，b，c或带下标的ai，bi，ci表示； 表示不确定的个体，称为客体变元，以x，y，z或xi，yi，zi表示。,7,1 谓词的概念与表示法,谓词，当与一个个体相联系时，它刻划了个体性质；当与两个或两个以上客体相联系时，它刻划了客体之间的关系。 表示特定谓词，称为谓词常元， 表示不确定的谓词，称为谓词变元，都用大写英文字母，如P，Q，R，或带下标来表示。,8,1 谓词的概念与表示法,他是三好学生。 7是质数。 每天早晨锻炼是好习惯。5大于3。 哥白尼指出地球绕着太阳转。

4、,9,1 谓词的概念与表示法,3.谓词的表示 用大写字母表示谓词。 用大写字母右侧括号内的小写字母表示客体。 例： A：是个大学生。 b：张三。 e：李四。A(c)：张三是个大学生。A(e)：李四是个大学生。 注意：用谓词表达命题，必须包括客体和谓词字母两部分。,10,1 谓词的概念与表示法,例：武汉位于北京和广州之间。武汉、北京和广州是三个个体，而“位于和之间”是谓词，它刻划了武汉、北京和广州之间的关系。设P：位于和之间，a：武汉，b：北京，c：广州，则P(a，b，c)：武汉位于北京和广州之间。,11,注意： 1. 若谓词字母联系着一个客体，则称作一元谓词；若谓 词字母联系着二个客体，则称作

5、二元谓词；若谓词字母联系着n个客体，则称作n元谓词。一元谓词表达客体的性质，多元谓词表达客体间关系。,2. 客体的次序必须是有规定的。例：河南省北接河北省。n L b 写成二元谓词为：L(n,b)，但不能写成L(b,n) 。,1 谓词的概念与表示法,12,1 谓词的概念与表示法,3. 单独一个谓词，不是完整的命题。把谓词字母后填以客体所得的式子称为谓词填式。如H(a，b) 4. 谓词中通常只写客体变元，因此不是命题，仅当所有客体变元做出具体指定时，谓词才成为命题，才有真值。,13,第二章 谓词逻辑,1 谓词的概念与表示法 2 命题函数与量词 3 谓词公式与翻译 4 变元的约束 5 谓词演算的等

6、价式与蕴含式 6 前束范式 7 谓词演算的推理理论,14,2 命题函数与量词,1. 命题函数客体在谓词表达式中可以是任意的名词。 例：C“总是要死的。”j：张三；t：老虎；e：桌子。则C(j), C(t), C(e)均表达了命题。 在上面的例子中，C：表示“总是要死的”；x：表示变元（客体变元），则C(x)表示“x总是要死的”，则称C(x)为命题函数。,15,2 命题函数与量词,定义1: 由一个谓词和一些客体变元组成的表达式，称为简单命题函数。n元谓词，就是有n个客体变元的命题函数。定义2: 由一个或n个简单命题函数以及逻辑联结词组成的表达式，称为复合命题函数。（谓词表达式）,16,2 命题函

7、数与量词,例：S(x)： x学习很好。W(x)： x工作很好。 谓词表达式： S(x)： x学习不是很好。S(x) W(x)： x的学习和工作都很好。S(x) W(x)：若x学习很好，则x的工作很好。,17,2 命题函数与量词,讨论： （a）当简单命题函数仅有一个客体变元时，称为一元简单命题函数； （b）若用任何客体去取代客体变元之后，则命题函数就变为命题； （c）命题函数中客体变元的取值范围对是否成为命题及命题的真值有影响。,18,2 命题函数与量词,例：Q(x，y)：x比y重。当x，y指人或物时，是一个命题。当x，y指实数时，不是一个命题。 例：R(x)：x是大学生。,个体域：在命题函数中

8、，客体变元的取值范围（讨论范围）叫个体域或论述域。 全总个体域：把各种个体域综合在一起作为论述范围的域。,19,2 命题函数与量词,例：P(x)表示x是质数。这是一个命题函数。其值取决于个体域。将命题函数转化为命题，有两种方法：(1) 将x取定一个值。如：P(4)，P(5)(2) 将谓词量化。如：(x)P(x)，(x)P(x),个体域的给定形式有二种： (1)具体给定。如：j, e, t (2)全总个体域/任意域：所有的个体从该域中取得。,20,2.量词 （1）全称量词 符号： 读作：“所有的”，“任一个”，“对一切”，“每一个”。 例：“所有的都是苹果”可写成： xA(x) 或 (x)A(x

9、),2 命题函数与量词,21,2 命题函数与量词,几种形式的读法： (x)P(x)： “对所有的x，x是”； (x)P(x)： “对所有x，x不是”； (x)P(x)： “并不是对所有的x，x是”； (x) P(x)：“并不是所有的x，x不是”。,22,2 命题函数与量词,例：所有的人都是要呼吸的。设M(x)：x是人。H(x)：x要呼吸。(x) (M(x) H(x),例：每个学生都要参加考试。设P(x)：x是学生。Q(x)：x要参加考试。(x) (P(x) Q(x),例：任何整数或是正的或是负的。设I(x)：x是整数。R(x)：x是正数。 N(x)：x是负数。(x) ( I(x) R(x) N

10、(x) ),23,例：将“对于所有的x和任何的y，如果x高于y，那么y不高于x”写成命题表达形式。,2 命题函数与量词,解： G(x，y)：x高于y(x) (y) (G(x，y) G(y，x),24,2 命题函数与量词,（2）存在量词符号： 读作：“存在一个”，“对于一些”，“对于某些”， “至少存在一个”，“这里存在着这样的”等等。几种形式的读法：(x) A(x) ：存在一个x，使x是；(x)A(x) ：存在一个x,，使x不是；(x) A(x) ：不存在一个x,，使x是；(x)A(x) ：不存在一个x， 使x不是。,25,例：存在一个人。设M(x)：x是人；(x) M(x),例：某个人很聪明

11、。设C(x)：x是很聪明；(x) (M(x) C(x),例：某些实数是有理数。设R1(x)：x是实数 R2(x)：x是有理数。 (x)(R1(x) R2(x),2 命题函数与量词,26,2 命题函数与量词,（3）存在唯一量词符号： ！表示：“恰有一个”，“存在唯一一个”等。,27,2 命题函数与量词,注意： （1）论述域不同，由量词确定的表达式也不同。 （2）在命题函数中，个体域可以限定，也可不限定。不限定即使用全总个体域。 （3）采用全总个体域时，谓词表达式中用特性谓词来限定客体变元的取值范围。,特性谓词：在全总个体域中，将每个客体变元的变化范围加以限制的谓词。,28,2 命题函数与量词,例

12、：所有的人都是会死的。设M(x)：x是人。S(x)：x是会死的。个体域约定为人类：(x) (S(x)全总个体域： (x) ( M(x) S(x) ),例：有一些人是不怕死的。设M(x)：x是人。F(x)：x是不怕死的。个体域约定为人类：(x) (F(x)全总个体域： (x) ( M(x) F(x) ),用法：对全称量词，特性谓词作前件；对存在量词，特性谓词作合取项。,29,第二章 谓词逻辑,1 谓词的概念与表示法 2 命题函数与量词 3 谓词公式与翻译 4 变元的约束 5 谓词演算的等价式与蕴含式 6 前束范式 7 谓词演算的推理理论,30,1.谓词公式 原子谓词公式：不出现命题联结词和量词的

13、谓词表达式称为原子谓词公式，并用P(x1xn)来表示。其中：P称为n元谓词， x1xn称为客体变元，当n=0时称为零元谓词公式。,3 谓词公式与翻译,31,3 谓词公式与翻译,定义2-3.1：（谓词公式的归纳法定义） （1）原子谓词公式是谓词公式； （2）若A是谓词公式，则A也是谓词公式； （3）若A, B都是谓词公式，则(AB), (AB), (A B), (AB)都是谓词公式；（4）若A是谓词公式，x是任何变元，则(x)A, (x)A也都是谓词公式； （5）只有按-所求得的那些公式才是谓词公式（谓词公式又简称“公式”）。,32,3 谓词公式与翻译,例1：并非每个实数都是有理数。设R(x)：

14、x是实数。 Q(x) ：x是有理数。符号化： (x) (R(x) Q(x) )或：(x) (R(x) Q(x) )例2：没有不犯错误的人。设M(x)：x是人。 F(x) ：x犯错。描述：只要是人，必然犯错。 (x) (M(x) F(x) )或：存在不犯错误的人是不可能的。 (x) (M(x) F(x) ),33,3 谓词公式与翻译,例3：尽管有人聪明，但未必一切人都聪明。设M(x)：x是人。 P(x) ：x聪明。(x) (M(x) P(x) ) (x) (M(x) P(x) )例4：某些人对某些食物过敏。设F(x,y)：x对y过敏。M(x)：x是人。 G(y)：y是食物。(x) (y) (M(

15、x) G(y) F(x,y),34,3 谓词公式与翻译,例5：凡是实数不是大于0，就是等于0或者小于0。设R(x)：x是实数。 P(x,0)：x大于0。 Q(x,0)：x等于0。 S(x,0)：x小于0。(x) (R(x) ( P(x,0) Q(x,0) S(x,0) ) ) 例6：发光的不都是金子。设L(x)：x是发光的。 G(x) ：x是金子。(x) (L(x) G(x) )或 (x) (L(x) G(x) ),35,例7：试将苏格拉底论证符号化：“所有的人总是要死的。因为苏格拉底是人，所以苏格拉底是要死的。”解：设M(x)：x是人；D(x)：x是要死的；s：苏格拉底 写成符号形式： (x) (M(x) D(x)， M(s) D(s),3 谓词公式与翻译,36,3 谓词公式与翻译,例8：用谓词公式写出下式。任给小正数，则存在一个正数，使得当 0|x-a| 时有|f(x)-b| 。此时即称lim f (x)=b。 解：设P(x,y)：x大于yQ(x,y)：x小于ylim f (x)=b 可表示为： () () (x) ( ( ( P(,0) P(,0) ) Q(|x-a|, ) P(|x-a|,0) ) Q(|f(x)-b|, ) ),