(1.4.1)--ch2—第一讲离散数学离散数学.pdf

《(1.4.1)--ch2—第一讲离散数学离散数学.pdf》由会员分享，可在线阅读，更多相关《(1.4.1)--ch2—第一讲离散数学离散数学.pdf（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学 Discrete Mathematics 命题逻辑的局限性命题逻辑的局限性 例例1.令令P：小张是大学生：小张是大学生.Q：小李是大学生：小李是大学生.命题命题P与与Q中的谓语是相同的中的谓语是相同的(是大学生是大学生),只是主语不同只是主语不同.从符号从符号P、Q中中不能归纳出他们都是大学生的共性不能归纳出他们都是大学生的共性.命题逻辑的局限性之一命题逻辑的局限性之一:无法表达原子命题之间所具有的无法表达原子命题之间所具有的共同特点共同特点.命题逻辑的局限性之二命题逻辑的局限性之二:不能揭示某些有效的论证不能揭示某些有效的论证 例如：著名的苏格拉底三段论：例如：著名的苏格拉

2、底三段论：所有的人都是要死的所有的人都是要死的.苏格拉底是人苏格拉底是人.所以苏格拉底是要死的所以苏格拉底是要死的.苏格拉底苏格拉底(前前469-前前399)古希腊唯心古希腊唯心 主义哲学家主义哲学家.P Q R PQ R 判断判断 PQ R 是否重言式？是否重言式？PQ R 显然这是正确的推理显然这是正确的推理,但在命题逻辑中却无法但在命题逻辑中却无法得到证明得到证明.第二章第二章 谓词逻辑谓词逻辑 谓词逻辑谓词逻辑 谓词逻辑基本概念谓词逻辑基本概念 谓词公式谓词公式 谓词公式标准型谓词公式标准型(前束范式前束范式)谓词公式间的关系谓词公式间的关系 谓词逻辑推理理论谓词逻辑推理理论 逻辑等价

3、逻辑等价 逻辑蕴含逻辑蕴含 原子命题原子命题 2-1 谓词的概念与表示谓词的概念与表示 人总是要死的人总是要死的.人人 是要死的是要死的 客体客体 谓词谓词 客体客体 谓词谓词 张三张三比比李四李四高高.比比高高 张三张三、李四李四 一切可以独立存在的、具体的一切可以独立存在的、具体的或抽象的事物或抽象的事物(句子中的主语、句子中的主语、宾语等宾语等).说明客体的性质、特征或说明客体的性质、特征或客体之间的关系的词客体之间的关系的词.客体客体 谓词谓词 第二章第二章 谓词逻辑谓词逻辑 客体和谓词的分类及表示客体和谓词的分类及表示 客体常元客体常元:表示具体或特定的客体表示具体或特定的客体.常用

4、小写字母常用小写字母a，b，c 或或 ai，bi，ci 表示表示.客体变元客体变元:表示抽象或泛指的客体表示抽象或泛指的客体.常用小写字母常用小写字母 x，y，z或或 xi，yi，zi 表示表示.谓词谓词变元变元:表示抽象的、泛指的性质或关系的谓词表示抽象的、泛指的性质或关系的谓词.谓词谓词常元常元:表示具体性质或关系的谓词表示具体性质或关系的谓词.常用大写的英文字母常用大写的英文字母 F,G,H 等表示等表示.注意：注意：单独谓词和客体不是命题单独谓词和客体不是命题,必须在谓词字母后填以必须在谓词字母后填以客体客体,称这样得到的式子为称这样得到的式子为谓词填式谓词填式.定义定义1.一个原子命

5、题用一个谓词和一个原子命题用一个谓词和n个个有次序的客体常元有次序的客体常元 a1,a2,an 表示成表示成 P(a1,a2,an)的形式的形式,称为该称为该原子命题原子命题的谓词形式的谓词形式.例如例如,用用A表示表示“是个是个劳动模范劳动模范”,b 表示表示“张明张明”则则张明是个劳动模范张明是个劳动模范:A(b)用用 B 表示表示“大于大于”则则4大于大于3:B(4,3).说明说明:n=1,称称P为为一元谓词；一元谓词；n=2,称称P为为二元谓词二元谓词,以此类推以此类推.n=0,称称P为为0元谓词元谓词,0元谓词是命题元谓词是命题.说明说明 1.谓词中谓词中客体词的顺序十分重要客体词的

6、顺序十分重要,不能随意变更不能随意变更.如令如令 F(x,y):x是是 y 的父亲；的父亲；若命题若命题F(b,c)为真为真,则命题则命题 F(c,b)为假为假.2.在谓词填式中在谓词填式中,若客体确定若客体确定,则则A(a1,an)就变成了命题就变成了命题.2-2.1 命题函数命题函数 2-2 命题函数与量词命题函数与量词 定义定义1.若表达式若表达式 P(x1,x2,xn)中中,P 是某个谓词是某个谓词,x1,x2,xn是是n个客体变元个客体变元,则则P(x1,x2,xn)称为称为简单命题函数简单命题函数.n元谓词就是有元谓词就是有n个客体变元的命题函数个客体变元的命题函数.定义定义2.由

7、由一个或多个简单命题函数一个或多个简单命题函数以及逻辑联结词组合以及逻辑联结词组合 而成的而成的表达式表达式 称为称为复合命题函数复合命题函数.例例.设设 S(x):x是奇数是奇数;W(x):x是素数是素数 S(x):x不是奇数不是奇数;S(x)W(x):x既是奇数又是素数既是奇数又是素数;简单命题函数简单命题函数 复合命题函数复合命题函数 逻辑联结词逻辑联结词 ,的意义与命题逻辑中的解释一致的意义与命题逻辑中的解释一致.注意注意:(1)命题函数不是命题命题函数不是命题.只有其中的客体变元用特定的客只有其中的客体变元用特定的客 体或客体常元替代时才是命题体或客体常元替代时才是命题.(2)命题函

8、数中命题函数中,客体变元在哪些范围内取特定的值客体变元在哪些范围内取特定的值,对是对是否成为命题及命题的真值极有影响否成为命题及命题的真值极有影响.定义定义3.在命题函数中在命题函数中,客体变元的取值范围称为客体变元的取值范围称为个体域个体域(论域论域).定义定义4.宇宙间的所有客体聚集在一起所构成的个体域称为宇宙间的所有客体聚集在一起所构成的个体域称为全总个体域全总个体域(全总论域全总论域).例例1.将下列命题将下列命题用用0 0元谓词元谓词符号化符号化.(1)2是素数且是偶数是素数且是偶数.(2)如果如果2大于大于3,则则2大于大于4.(3)如果如果张明比李民高张明比李民高,李民比赵亮高李

9、民比赵亮高,则张明比赵亮高则张明比赵亮高.解解:(1)设设F(x):x是素数是素数.G(x):x是偶数是偶数.则命题符号化为：则命题符号化为：F(2)G(2)(2)设设L(x,y):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)2-2.2 量词量词(Quantifiers)量词量词:分为全称量词分为全称量词()和存在量词和存在量词()全称量词全称量词 符号符号“”称为称为全称量词全称量词，用来表达，用来表达“所有所有”、“

10、一切一切”、“凡凡”、“每一个每一个”、“任意任意”等词语等词语.x 表示对个体域里的所有客体表示对个体域里的所有客体;(x)P(x)表示个体域里的所有客体具有性质表示个体域里的所有客体具有性质P.存在量词存在量词(The Existential Quantifiers)符号符号“”称为称为存在量词存在量词,用来表达用来表达“存在一些存在一些”、“某个某个”“至少有一个至少有一个”、“对于一些对于一些”等词语等词语.x 表示存在个体域中的客体表示存在个体域中的客体.(x)P(x)表示存在着个体域里的客体具有性质表示存在着个体域里的客体具有性质P.例例2.(1)所有的所有的老虎都要吃人老虎都要吃

11、人.(2)每一个每一个大学生都会说英语大学生都会说英语.(3)所有的所有的人都长着黑头发人都长着黑头发.(4)有一些有一些人登上过月球人登上过月球.(5)有一些有一些自然数是素数自然数是素数.(x)P(x)x 老虎老虎 (x)Q(x)x大学生大学生 (x)R(x)x人人 (x)S(x)x人人 (x)T(x)x自然数自然数 P(x)：x 会吃人会吃人 则有则有:所有的所有的x,P(x)x 老虎老虎 Q(x)：x会说英语会说英语 则有则有:每一个每一个x,Q(x)x大学生大学生 R(x)：x长着黑头发长着黑头发 则有则有:所有的所有的x,R(x)x人人 S(x)：x登上过月球登上过月球 则有则有:

12、有一些有一些x,S(x)x人人 T(x):x是素数是素数 则有则有:有一些有一些 x,T(x)x自然数自然数 1.从从书写上书写上十分不便十分不便,总要特别注明个体域总要特别注明个体域;2.无法清晰无法清晰表达不同的个体域：在同一个比较复杂的表达不同的个体域：在同一个比较复杂的句子中句子中,对于不同命题函数中的客体可能属于不同的个体对于不同命题函数中的客体可能属于不同的个体域域,此时此时无法清晰无法清晰表达表达;如例如例(1)和和(4)的合取的合取 (x)P(x)(x)R(x)x人人 x老虎老虎(1)所有的所有的老虎都要吃人老虎都要吃人;(x)P(x)(4)有一些有一些人登上过月球人登上过月球

13、;(x)R(x)不便之处不便之处 3.若个体域的注明不清楚若个体域的注明不清楚,将造成将造成无法确定其真值无法确定其真值.即即对于对于同一个同一个n元谓词元谓词,不同的个体域有可能带来不同的真值不同的个体域有可能带来不同的真值.例如例如 对于语句对于语句“(x)(x+6=5)”可表示为：可表示为：“有一些有一些x,使得使得 x+6=5”.该语句在下面两种个体域下有不同的真值：该语句在下面两种个体域下有不同的真值：(1)在实数范围内时在实数范围内时,确有确有x=-1使得使得x+6=5,因此因此,(x)(x+6=5)为真为真;(2)在正整数范围内时在正整数范围内时,则找不到任何则找不到任何x,使得

14、使得x+6=5为真为真,所以所以,(x)(x+6=5)为假为假.不便之处的根源不便之处的根源 因为需要因为需要额外额外特别标注出每个谓词的特别标注出每个谓词的个体域所致个体域所致！所有的所有的老虎都要吃人。老虎都要吃人。(x)P(x)x 老虎老虎 全总个体域全总个体域 老虎集合老虎集合 用谓词指出客体变元的用谓词指出客体变元的 取值范围。取值范围。U(x)如何与如何与(x)P(x)结合才符合逻辑呢结合才符合逻辑呢？U(x):x是老虎是老虎 x老虎老虎 所有的所有的老虎都要吃人；老虎都要吃人；(x)P(x)x老虎老虎 在全总个体域中在全总个体域中,表示特殊个体域中客体的谓词表示特殊个体域中客体的

15、谓词.用来限定用来限定(或者约束或者约束)客体变元的取值范围客体变元的取值范围.全总个体域全总个体域 老虎集合老虎集合 特性谓词特性谓词 例例.符号化符号化“所有的所有的老虎都要吃人老虎都要吃人”这个命题这个命题.含义含义:对于任意的对于任意的x(全总论域全总论域),如果如果x是老虎是老虎,则则x会吃人会吃人.若若P(x):x会吃人会吃人.U(x):x是老虎是老虎.则符号化的正确形式应该是则符号化的正确形式应该是 (x)(U(x)P(x)若符号化为若符号化为(x)(U(x)P(x)它的含义是：它的含义是：“对于任意的对于任意的x,x是老虎是老虎,并且并且x会吃人会吃人”，与原命题与原命题“所有

16、的老虎都要吃人所有的老虎都要吃人”的逻辑含义不符的逻辑含义不符.P U P包含包含U(x)(U(x)P(x)特性谓词的例子特性谓词的例子 有一些有一些大学生吸烟大学生吸烟.它的含义是它的含义是:存在一些存在一些 x,x 是大学生是大学生,且且 x 吸烟吸烟.S(x):x吸烟吸烟;U(x):x是大学生是大学生.则符号化的正确形式应该是则符号化的正确形式应该是 (x)(U(x)S(x)若符号化为若符号化为(x)(U(x)S(x)它的含义是它的含义是:存在一些存在一些x,若若x是大学生是大学生,则则x吸烟吸烟.与原命题与原命题“有一些大学生吸烟有一些大学生吸烟”的逻辑含义不符的逻辑含义不符.U S(

17、x)(U(x)S(x)特性谓词的例子特性谓词的例子 例例3.(1)所有的所有的人都是要呼吸的人都是要呼吸的;(2)每个每个学生都要参加考试学生都要参加考试;(3)任何任何整数或是正的或是负的整数或是正的或是负的.解解.(1)当个体域为当个体域为人类集合人类集合时：时：则则(1)符号化为符号化为:(x)F(x)令令F(x):x 呼吸呼吸 当个体域为当个体域为全总个体域全总个体域时：时：令令M(x):x 是人是人 则则(1)符号化为符号化为:(x)(M(x)F(x)(2)当个体域为当个体域为全体学生的集合全体学生的集合时：时：则则(2)符号化为符号化为:(x)P(x)令令P(x):x 要参加考试要

18、参加考试 当个体域为当个体域为全总个体域全总个体域时：时：令令S(x):x 是学生是学生 则则(2)符号化为符号化为:(x)(S(x)P(x)(3)当个体域为当个体域为全体整数的集合全体整数的集合时：时：则则(3)符号化为符号化为:(x)(P(x)N(x)令令P(x):x 是正的，是正的，N(x):x 是负的是负的 当个体域为当个体域为全总个体域全总个体域时：时：令令I(x):x 是整数是整数 则则(3)符号化为符号化为:(x)(I(x)(P(x)N(x)例例4.(1)存在一个整数是质数存在一个整数是质数.(2)有一些人是聪明的有一些人是聪明的.解解:则则(1)符号化为符号化为:(x)(Z(x

19、)P(x);(2)M(x):x是人是人,R(x):x是聪明的是聪明的 则则(2)符号化为符号化为:(x)(M(x)R(x);(1)Z(x):x是整数，是整数，P(x):x是质数是质数,.将命题函数将命题函数命题的方法命题的方法 1)将变元取定具体的值将变元取定具体的值,如如 P(a),P(b).2)将谓词量化将谓词量化.如如(x)P(x),(x)P(x).使用使用量词时应注意的问题量词时应注意的问题 (1)在不同的个体域在不同的个体域,同一命题的符号化形式可能相同也可同一命题的符号化形式可能相同也可 能不同能不同.(2)在不同的个体域在不同的个体域,同一命题的真值可能相同也可能不同同一命题的真

20、值可能相同也可能不同.(3)约定以后如不指定个体域约定以后如不指定个体域,默认为全总个体域默认为全总个体域.对每个客体对每个客体 变元的变化范围变元的变化范围,用用特性谓词特性谓词加以限制加以限制.对于对于全称量词全称量词(x),刻划其对应个体域的特性谓词作为刻划其对应个体域的特性谓词作为 条件式之前件条件式之前件加入加入.对于对于存在量词存在量词(x),刻划其对应个体域的特性谓词作为刻划其对应个体域的特性谓词作为 合取式之合取项合取式之合取项加入加入.2-3 谓词公式与翻译谓词公式与翻译(Predicate formulae)原子公式原子公式:A(x1,x2.xn)称为谓词演算的称为谓词演算

21、的原子公式原子公式.其中其中 定义定义2-3.1 谓词演算的谓词演算的合式公式合式公式,可由下述各条组成可由下述各条组成:(1)原子公式是合式公式原子公式是合式公式;(2)若若A 是合式公式是合式公式,则则(A)也是合式公式也是合式公式;(3)若若A,B是合式公式是合式公式,则则(AB),(AB),(AB),(AB)都是合式公式都是合式公式;(4)若若A是合式公式是合式公式,x是是A中出现的任何变元中出现的任何变元,则则(x)A(x),(x)A(x)都是合式公式都是合式公式;(5)只有有限次应用只有有限次应用(1)(4)得到的公式是得到的公式是合式公式合式公式.A是谓词是谓词,x1,x2.xn

22、 是客体变元、客体常元、或任意是客体变元、客体常元、或任意 n元函数元函数.称谓词合式公式为谓词公式称谓词合式公式为谓词公式,在不引起混淆时在不引起混淆时,甚至可将甚至可将 谓词公式的括号同样可省略谓词公式的括号同样可省略,其规则与命题公式的括号省其规则与命题公式的括号省 略相同略相同,即最外层括号可省略即最外层括号可省略.但是但是,量词后面的括号是不能量词后面的括号是不能 省略的省略的.谓词合式公式是按上述规则由原子公式、联结词、谓词合式公式是按上述规则由原子公式、联结词、量词、圆括号所组成的符号串量词、圆括号所组成的符号串.注：注：2.谓词公式的翻译谓词公式的翻译 把每个原子命题分解成个体

23、、谓词和量词把每个原子命题分解成个体、谓词和量词,在全总论域在全总论域 中讨论时中讨论时,要给出特性谓词要给出特性谓词 正确理解给定命题正确理解给定命题,必要时把命题改叙必要时把命题改叙,使其中每个原子使其中每个原子 命题及原子命题之间的关系能明显表达出来命题及原子命题之间的关系能明显表达出来 找出恰当量词找出恰当量词.同时同时,应注意全称量词应注意全称量词(x)后跟条件式，后跟条件式，存在量词存在量词(x)后跟合取式后跟合取式 用恰当的联结词把给定命题表示出来用恰当的联结词把给定命题表示出来 把一个文字叙述的命题把一个文字叙述的命题,用谓词公式表示出来用谓词公式表示出来,称为谓词逻称为谓词逻

24、 辑的翻译或符号化辑的翻译或符号化;反之亦然反之亦然.一般说来一般说来,符号化的步骤如下符号化的步骤如下:例例1.并非每个实数都是有理数并非每个实数都是有理数;用谓词公式表示下列命题用谓词公式表示下列命题 解解:R(x):x是实数是实数,Q(x):x是有理数是有理数,则命题可表示为则命题可表示为:(x)(R(x)Q(x)例例2.没有不犯错误的人没有不犯错误的人;解解:F(x):x是人是人,M(x):x 犯错误犯错误;则命题可表示为则命题可表示为:(x)(F(x)M(x)例例3.尽管有人聪明尽管有人聪明,但未必一切人都聪明但未必一切人都聪明;解解:M(x):x是人是人,P(x):x 聪明聪明;则

25、命题可表示为则命题可表示为:(x)(M(x)P(x)(x)(M(x)P(x)例例4.张强把一本新买到的离散数学书送给了李林张强把一本新买到的离散数学书送给了李林 解解:N(x):x是新的是新的,B(x):x是买到的是买到的 令令 P(x):x是新买到的是新买到的 则原命题可表示成则原命题可表示成:则原命题可符号化为则原命题可符号化为:令令 c:张强张强,l:李林李林,d:离散数学书离散数学书 G(y,z,w):y 把把z 送给了送给了w G(c,d,l)N(d)B(d).G(c,d,l)P(d)例例5.lim f(x)=b的定义的定义:任给正数任给正数 ,则存在正数则存在正数 ,xa 使得当使

26、得当0|x-a|时时,都有都有:|f(x)-b|.解解:设设 P(x,y)表示“表示“x大于大于y”,Q(x,y)表示表示“x小于小于y”,故故 lim f(x)=b 可定义为可定义为:()(P(,0)()(P(,0)(x)(Q(|x-a|,)P(|x-a|,0)Q(|f(x)-b|,)练习练习.将下列命题符号化将下列命题符号化 (1)没有不能表示成分数的有理数没有不能表示成分数的有理数.(2)所有运动员都钦佩某些教练所有运动员都钦佩某些教练.(3)有的兔子比所有乌龟跑得快有的兔子比所有乌龟跑得快 解解:(1)令令D(x):x 是有理数是有理数;F(x):x 能表示成分数能表示成分数.则符号化

27、为则符号化为:(x)(D(x)F(x)或或(x)(D(x)F(x)(2)令令L(x):x 是运动员是运动员;J(y):y是教练是教练;A(x,y):x 钦佩钦佩 y (x)(L(x)(y)(J(y)A(x,y)(x)(P(x)(y)(Q(y)R(x,y)则符号化为则符号化为:(3)令令P(x):x 是兔子是兔子;Q(y):y是乌龟是乌龟;R(x,y):x 比比 y 跑得快跑得快 则符号化为则符号化为:小结小结 客体和谓词、一元谓词、客体和谓词、一元谓词、n元谓词、命题函数、元谓词、命题函数、全称量词和存在量词等概念。全称量词和存在量词等概念。重点掌握重点掌握:一元谓词和一元谓词和n 元谓词的概念元谓词的概念 全称量词和存在量词及量化命题的符号化全称量词和存在量词及量化命题的符号化.基本概念基本概念:命题命题 量词量词 客体客体 谓词谓词 全称量词全称量词 存在量词存在量词 客体常元客体常元 客体变元客体变元 谓词常元谓词常元 谓词变元谓词变元 个体域个体域 全总体域全总体域 取值范围取值范围 特殊特殊 简单命题函数简单命题函数 联结词联结词 复合命复合命 题函数题函数 分解分解 分解分解 分解分解