离散数学---谓词逻辑.ppt

1、第二章 谓词逻辑,数理逻辑,命题逻辑：从语句来讲是不可再分,谓词逻辑：将命题再细分,在命题逻辑中，命题演算的基本单位是命题，不再对原子命题进行分解，故无法研究命题语句的结构、成份和内在的逻辑特征。 如果任何两个原子命题具有一些共同特征，那么欲表达这些共同特征，显然是不可能的事。这就使得在命题逻辑中，甚至无法处理一些简单而又常见的推理过程。 在命题的研究中，基于谓词分析的逻辑，称为谓词逻辑。 谓词逻辑是命题逻辑的扩充和发展。,本章重点,1.谓词公式 2.自然语言表述和谓词公式表示间的相互转化 3.基于谓词公式的推理,例子：我班有人能考上研究生。我班所有人都能考上研究生。,经典例子,苏格拉底三段论

2、: 1)所有人都要死； 2)苏格拉底是人； 3)所以苏格拉底是要死的。,设P:所有人都要死； Q:苏格拉底是人； R: 苏 格拉底是要死的。 则 前提：P,Q 结论：R 显然PQ R 不是永真式。,引入谓词,引入原因： 1)克服原子命题的不可再分在性，将主语和谓语分开； 2)原子命题不能描述数量关系。,一、基本三要素,个体与个体域：克服原子命题底不可再分性，可分为主语和谓语；个体：不依赖于人们的主观而独立存在的客观实体;是独立存在的客体，可以是具体事物也可以是抽象概念。个体域（D）：个体取值的范围。 全总个体域。 谓词：用于刻画个体的性质或者个体间的关系；谓词部分 量词(、) 量词的辖域（作用

3、域）,例如,“猫是动物”一句中的“是动物”就是一个谓词，而“猫”是客体。 “3 大于 2”中“大于”是一个谓词。3和2是客体。,张三比李四高。 用H（x,y）表示x比y高。 a:张三 b:李四 H（a,b）：张三比李四高 H（b,a）：李四比张三高,谓词,只涉及一个客体的谓词称为一元谓词，涉及两个客体的谓词称为二元谓词，涉及n个客体的谓词称为n元谓词。 一般，如A表示谓词符号，用Xi表示第i个客体变项，则n元谓词表示为A(x1,xn)。,谓词常项和谓词变项,谓词常项：表示某个确定判定的谓词称为谓词常项。如上述两个谓词是动物、大于。 谓词变项：尚未确定的谓词称为谓词变项。例如用 P（3，2）记一

4、个谓词变项，可以表示 “3 大于 2”、“3 小于 2”等等。 n 元谓词： 在一个命题中，若有 n 个客体名称与谓词相联系，则称该谓词为 n 元谓词。如上述“是动物”为一元谓词，因为只有“猫”这一个客体与之相联系。而命题“3 大于 2”中的谓词“大于”与两个客体联结，是一个二元谓词。,谓词与命题的关系,一般来说，谓词不是命题，它的真值无法确定； 为了使得它成为命题，必须： 指定某一谓词常项代替P； 指定n个个体常项a1,a2,.,an分别代替n个个体变项x1,x2,.,xn。 例如：L（x，y）是一个2元谓词，它不是命题；当令L（x，y）表示“x大于y”后，该谓词中的谓词部分便成了常项，但是

5、它不是命题；当取a为2，b为3时，L（a，b）才是命题，并且是假命题。 c为2，d为0时，L（c，d）是真命题。 有时将不带个体变项的谓词称为0元谓词。 0元谓词中的谓词的意义确定后， 0元谓词是命题。,使用谓词注意：,（1） n元谓词中，客体变项的次序很重要 。 例：F（x,y）表示x是y的父亲， a:张三，b:张小明。 F（a,b）表示张三是张小明的父亲。 F（b,a）表示张小明是张三的父亲。 （2） 在讨论一个问题是必须先确定好个体域D。 如不作限制，表示宇宙一切事物组成的个体，成为全总个体域。 （3） 同一个n元谓词，取不同的个体，真假会不同。 A（x）：x是大学生。 A（a） 真值可

6、能为真，而A（b）真值可能为假。 （4） 对于同一谓词，个体域D不同，真值可能也不同。 例：对于A（x），x是大学生。 如D=大学生全体，A（x）是重言式。 如D=学生全体，A（x）是仅可满足式。 如D=老鼠全体，A（x）是永假式。,量词,：有一个，存在，一些，some ：所有的，全体，任意的，every，all 量词的使用：一个量词后面紧跟着一个个体变元，不单独使用。 xP(x)，yQ(y)，xy P(x,y)等。,xA(x)，xA(x),例如：D=全班同学的集合。A(x):今天x迟到了。 xA(x) 表示今天x迟到了。xD，从而x指同学。 xA(x)表示今天有同学迟到了。 xA(x)就表示

7、为今天所有的同学都迟到了。,显然，当D为有限集合时，D=a1,a2,an xP(x)=P(a1)P(a2)P(an) xP(x)=P(a1)P(a2)P(an),二、将命题用0元谓词符号化,例如：2是素偶数。 如果2大于3，则2大于4。,解题步骤：1）找出个体词、量词和谓词； 2）符号化谓词和个体词； 3）使用符号化的谓词和个体词以及联接词进行命题符号化。,带量词命题的符号化,例如：所有人都是要死的。 有些人长寿。,由于量词和个体域之间有紧密的联系，在考虑命题符号化问题时，必须先明确个体域。（没有特别声明则是全总个体域）,设F（x）：x是要死的。G（x）：x长寿。 一、考虑个体域D为人类的集合

8、 1符号化为xF(x) 2符号化为 xG(X) 二、考虑个体域D为全总个体域 如果1符号化为xF(x) 2符号化为 xG(X),例如：1.所有人都是要死的。 2.有些人长寿。,这时将命题转换为： 1.对所有个体而言，如果它是人，则它是要死的。 2.存在这样的个体，它是人并且长寿。,从而加入谓词：H(x):x是人。称为特性谓词。 这样原命题符号化为： 1. x（H(x) F(x) ) 2. x (H(x ) G (X),1.所有人都是要死的。2.有些人长寿。(续),如果1符号化为：x（H(x) F(x) ) 2符号化为：x (H(x ) G (X) 显然是错的。,F（x）：x是要死的。G（x）：

9、x长寿。 H(x):x是人,一般而言，在使用全称量词时，特性谓词总是作为蕴涵式的前件；在使用存在量词时，特性谓词总是作为一个合取式的合取项。,1.所有人都是要死的。2.有些人长寿。(续),设A(x):x犯错。 原命题可以化为：所有人都要犯错误；对所有的x，x是要犯错的。 符号化为：xA(x) 也可以化为：没有不犯错的人；不存在这样的x，x不犯错。符号化为： xA(x),例1.没有不犯错误的人。D=人的集合,例2 在一阶逻辑中将下面命题符号化 （1）凡有理数均可表示成分数 （2）有的有理数是整数 要求： 1）个体域为有理数集合 2）个体域为实数集合 3）个体域为全总个体域,例3 将下列命题符号化

10、 （1）对所有x，均有x2-1=(x+1)(x-1) （2）存在x，使得:x+5=2 要求： 1）个体域为自然数集合 2）个体域为实数集合,例4 ：在一阶逻辑中将下面命题符号化 （1）凡偶数均能被2整除 （2）存在着偶素数 （3）没有不吃饭的人 （4）素数不全是奇数,例5.对任意的x都存在y，使得x +y=2。D=实数集合,设F(x,y)：x+y=2。 xy F(x,y)，是真命题。 反之， yxF(x,y)表示：存在y，对任意的x都有x +y=2。假命题。 量词不能随便交换位置。,例6.任意大于等于4的偶数，都可以表示成两个素数之和。,谓词有：x是偶数；x4；x是素数；x=y+z 从而定义谓词： P(x):x是偶数；Q(x):x4； R(x):x是素数；S(x,y,z):x=y+z 对任意的x，如果x4，并且x是偶数，那么存在y和z，y是素数，z是素数，并且x=y+z。 x(Q(x) P(x) y z(R(y)R(z) S(x,y,z),例7：所有的金属都溶解于某种液体中。,F(x,y):x溶解于y中。 a:金属；b：液体； ab(F(x,y),正确的解法： F(x,y):x溶解于y中。 G(x