左孝凌离散数学2.1谓词概念与表示-2.2命题函数与量词ppt课件

1、2.1谓词的概念与表示(Predicate and its expression)2.2命题函数与量词(Propositional functions & Quantifiers)2.3谓词公式与翻译(Predicate formulae)2.4变元的约束(Bound of variable)2.5谓词演算的等价式与蕴含式(Equivalences & implications of predicate calculus)2.6前束范式(Prenex normal form)2.7谓词演算的推理理论(Inference theory of predicate calculus)

2、 著名的苏格拉底三段论著名的苏格拉底三段论所有的人都是要死的P，苏格拉底是人Q， 前提：P Q所以苏格拉底总是要死的R结论：R PQ R或或(P Q) R T命题逻辑命题逻辑R所有的人都是要死的,前提：所有A都要B苏格拉底是人， 前提：C是A所以苏格拉底总是要死的结论：C是要B 所有所有A都要都要BC是是A谓词逻辑谓词逻辑RC要要B命题逻辑的局限性：命题逻辑的局限性：缘由：在命题逻辑中，命题是命题演算的基本单位，原子命题不再进行分解，因而无法研究命题的内部结构、成分及命题之间的内在联系,因而不能将命题之间的内在联系和数量关系反映出来。解决办法：将命题进行分解。原子命题客体谓词独立存在的具独立存

3、在的具体事物的或抽体事物的或抽象的概念象的概念刻画客体的刻画客体的性质、特征性质、特征或关系或关系谓词逻辑谓词逻辑人总是要人总是要死的死的人人是要死的是要死的客体客体谓词谓词在谓词逻辑中，可将原子命题划分为客体和谓词两部分在谓词逻辑中，可将原子命题划分为客体和谓词两部分例如，电子计算机、李明、玫瑰花、黑板、实数、中国、思想、唯物主义等是个大学生）大于绕着转位于与之间客体谓词表示方法：谓词用大写字母，客体用小写字母例1、采用谓词表示下列命题1) 地球绕着太阳转； 2济南位于北京与南京之间；3张三是大学生，李四是工人解：1设：L:绕着转，a：地球；b：太阳 即，L(a，b) 2设：L：位于与之间，

4、a：济南；b：北京；c：南京 即L(a，b，c) 3设：A：是，a：张三，b：李四，s：大学生，w：工人 即A(a，s)，A(b,w)一、基本概念一、基本概念 n元谓词 ：A是谓词，a1，a2，an是客体的名称，则A(a1，a2，an)是n元谓词，这里n个客体需要插入固定的位置 例2、张三高于李四 解：H：高于，a：张三，b：李四 即H(a,b)注：在多元谓词表达式中，客体字母出现的先后次序与事先约定有关,一般不可以随意交换位置，如H(a,b) H(b,a)一、基本概念一、基本概念8 定义：由一个谓词H和n个客体变元组成的表达式H(x1, x2 , , xn)称为n元简单命题函数. 客体变元：

5、常用小写英文字母x,y,z, 表示 客体常元：表示具体或特定的客体，常用小写英文字母a,b,c, 表示 注： H(x1, x2 , , xn) 本身并不是一个命题.只有用特定的客体取代客体变元x,y,z后，它们才成为命题。 n元谓词：即有n个客体变元的命题函数. 当n=0时,称为0元谓词，0元谓词是一个命题. 2.2命题函数与量词二、命题函数二、命题函数比对：比对：1命题逻辑中的命题变元命题逻辑中的命题变元A和命题常量和命题常量A：人是会死的）：人是会死的）2谓词逻辑中谓词逻辑中 命题函数命题函数H(x1, x2 , , xn)将客体变元特别制定为客体常元后将客体变元特别制定为客体常元后Ha,

6、b,c，），）9复合命题函数:由一个或几个简单命题函数以及逻辑联结词组合而成的表达式.例3:若x的学习好,则x的工作好 设S(x):x学习好；W(x):x工作好， 则有 S(x) W(x) 另外：S(x)表示“x学习不是很好”。 S(x)W(x)表示“x的学习，工作都很好”。例4:将下列命题用谓词符号化.(1) 2是素数且是偶数.(2) 如果2大于3,则2大于4.(3) 如果张明比李民高, 李民比赵亮高,则张明比赵亮高. 2.2命题函数与量词二、命题函数二、命题函数10 解:(1) 设F(x): x是素数. G(x): x是偶数. 则命题符号化为： F(2)G(2) (2) 设L(x,y) ：

7、x大于y. 则命题符号化为： L(2,3) L(2,4) (3) 设 H(x,y): x比y高. a:张明 b:李民 c：赵亮 则命题符号化为： H(a,b)H(b ,c)H(a,c) 另：H(a,b)表示“张明不比李民长得高”。 2.2命题函数与量词11 个体域：在命题函数中，客体变元的论述范围称作个体域。 全总个体域:把各种个体域综合在一起作为论述范围的域所有个体域的并称为全总个体域。 阐明： 1)命题函数不是一个命题，只有其中的个体变元用特定个体或个体常元替代时，才能成为一个命题。 2)但是客体变元在哪些范围内取特定的值，对命题函数是否成为命题及命题的真值极有影响。 2.2命题函数与量词

8、二、命题函数二、命题函数P57-P57-例例4 R(x)4 R(x)表示表示“x“x是个大学生是个大学生”如果如果x x的讨论范围为某大学里班级的学生，则的讨论范围为某大学里班级的学生，则R(x)R(x)是永真式。是永真式。如果如果x x的讨论范围为某中学里班级的学生，则的讨论范围为某中学里班级的学生，则R(x)R(x)是永假式。是永假式。如果如果x x的讨论范围为一个剧场中的观众，观众中有的讨论范围为一个剧场中的观众，观众中有大学生也有非大学生，那么，对某些观众，大学生也有非大学生，那么，对某些观众，R(x)R(x)为真，对另一些观众，为真，对另一些观众，R(x)R(x)为假。为假。若x，y

9、，z 地面上的房子，且P(x,y)：x距离y 10米，则这个式子表示“x距离y10米且y距离z10米则x距离z10米”。这个命题的真值将由x，y，z的具体位置而定，它可能为T，也可能为F。 xyzxyzP57-P57-例例5 5若若x x，y y，z Rz R实数），且实数），且P(x,y)P(x,y)：x x小于小于y y，则这个式子表，则这个式子表示示“若若x x小于小于y y且且y y小于小于z z，则，则x x小于小于z”z”。这是一永真式。这是一永真式。 假设假设 x，y，z 人，且人，且P(x,y)解释为：解释为：x为为y的儿子，则这个式子表示的儿子，则这个式子表示“若若x为为y的

10、儿子且的儿子且y是是z的儿子则的儿子则x是是z的儿子的儿子”。这是一个永假式。这是一个永假式。( ( , )( , )(,)P x yP y zP X ZP(x,z)一元谓词一元谓词P Px x表示客体的性质；表示客体的性质；n nn n 2 2元谓元谓词表示客体之间的关系。词表示客体之间的关系。n n元谓词元谓词P Px1x1，x2x2，xnxn是以客体变元的个体是以客体变元的个体域为定义域，以域为定义域，以0,1(F,T)0,1(F,T)为值域的为值域的n n元函数。元函数。n n元谓词不是命题，只有将其中的客体变元替换为元谓词不是命题，只有将其中的客体变元替换为n n个客体常元才能成为命

11、题。个客体常元才能成为命题。例：例：A(x,y):x A(x,y):x y y当当a=3a=3，b=4b=4时，时，A(aA(a，b)b)：3 3 4 4 为为T T当当a=5a=5，b=1b=1时，时，A(aA(a，b)b)：5 5 1 1 为为F F当当a=2a=2时，时，A(2A(2，y) y)不是命题。不是命题。当当n=0n=0时，称为时，称为0 0元谓词，是命题元谓词，是命题命题函数是否能成为命题及命题的真值与客体变元命题函数是否能成为命题及命题的真值与客体变元的取值范围有关。的取值范围有关。阐明阐明15 量词：全称量词()和存在量词() 1.全称量词：用来表达“一切”、“一切”、“

12、凡”、“每一个”、“恣意等词，用符号“” 表示，表示对个体域里的所有个体()表示个体域里的所有个体具有性质F. 符号“”称为存在量词. 2.2命题函数与量词三、量词三、量词16P58-例：在谓词逻辑中将下列命题符号化.（1凡是人都呼吸。 （2每个学生都要参加考试。 (3) 任何整数或是正的或是负的。解: (1) 当个体域为人类集合时： 令F(x): x呼吸。那么1符号化为xF(x) 当个体域为全总个体域时： 令M(x): x是人。那么1符号化为 x(M(x) F(x). 2.2命题函数与量词17(2) 当个体域为全体学生的集合时： 令P(x): x要参加考试。那么2符号化为xP(x). 当个体

13、域为全总个体域时： 令S(x): x是学生。那么2符号化为 x(S(x) P(x). (3) 当个体域为全体整数的集合时： 令P(x): x是正的。N(x): x是负的。那么3符号化为 x(P(x)N(x) . 当个体域为全总个体域时： 令I(x): x是整数。那么3符号化为 x(I(x)(P(x)N(x). 2.2命题函数与量词182.存在量词:用来表达“有一个”、“有的”、“存在着”、“至少有一个”、 “存在一些等词，用符号“” 表示 表示存在个体域里的个体， ()表示存在个体域里的个体具有性质F.符号“”称为存在量词.例4：在谓词逻辑中将下列命题符号化.（1一些数是有理数。 （2有些人活

14、百岁以上。 三、量词三、量词 2.2命题函数与量词19解: (1)令Q(x): x是有理数。那么1符号化为Q(x)。 （2当个体域为人类集合时： 令G(x): x活百岁以上。那么2符号化为xG(x)。 当个体域为全总个体域时： 令M(x): x是人。那么2符号化为 x(M(x) G(x) 2.2命题函数与量词20 3.特性谓词:限定客体变元变化范围的谓词，称作特性谓词。 例：“有些人没有来上课” 要求：1个体域为全总个体域，2个体域为人 解： 1设M(x)：x是人，C(x)：x没来上课 则命题符号化为：（x）(M(x) C(x) 2)设C(x)：x没来上课 则命题符号化为：（xC(x) 这里M

15、(x)称作特性谓词，用来限定客体的取值范围 三、量词三、量词 2.2命题函数与量词21如果没有给出个体域，都应该以全总个体域为个体域。如果没有给出个体域，都应该以全总个体域为个体域。引入特性谓词后，使用全称量词与存在量词符号化的形式引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的，普通：是不同的，普通：全称量词全称量词( x)：特性谓词作为条件式的前件：特性谓词作为条件式的前件 例：所有的人都是要呼吸的例：所有的人都是要呼吸的 M(x)：x是人是人 H(x):x要呼吸要呼吸 命题符号化为：命题符号化为： ( x)(M(x) H(x). 存在量词（存在量词（ x） ：特性谓词作为合取项

16、：特性谓词作为合取项例：有些人没有来上课例：有些人没有来上课 M(x)：x是人是人 C(x):x没来上课没来上课命题符号化为：命题符号化为： （ x）(M(x) C(x)量词使用小结量词使用小结 2.2命题函数与量词22多个量词同时出现时，不能任意颠倒次序多个量词同时出现时，不能任意颠倒次序 例：例：“对任意的对任意的x,存在存在y, 使得使得x+y=5”, 个体域为个体域为R, 则该命题符号化为则该命题符号化为: ( x)( y)H(x,y).其中其中H(x,y): x+y=5. 为真为真而而 ( y)( x)H(x,y)表示表示“某个些数某个些数y与任意与任意其其 他数的和为他数的和为5” 完全不同的命题，真值为假完全不同的命题，真值为假使一个命题函数成为命题，有两种方法：使一个命题函数成为命题，有两种方法：对客体变元进行指派。对客体变元进行指派。如：如：P(x)：x是素数，则是素数，则P(5)为为T,P(4)为为F对命题函数进行量化对命题函数进行量化如：如：P(x)：x是素数，那么：（是素数，那么：（ xP(x)为为T, （ xP(x)为为F量词使用小结量词使用小结 2.2命题函数与量词23练习练习 例6：在谓词逻辑中将下列命题符号化.（1所有的人都长头发。（2有的人吸烟。（3没有人登上过木星。（4清华大学的学生未必都是高素质的。 24解：令M