离散数学PowerPoint 演示文稿12.ppt

1、,克拉玛依职业技术学院 制作人:卢自娟 2007年9月10日,离散数学基础,第一部分 数理逻辑,引言 数理逻辑主要包括两部分的 内容,命题逻辑和一阶逻辑.命题逻 辑是研究由命题为基本单位构成的 前提和结论之间的可推导关系. 一 阶逻辑又称谓词逻辑.,案例 :,一个公安人员审查一件盗窃案,已知下列事实:(1) 甲或乙盗窃了 DVD (2) 若甲盗窃了DVD,则作案时间不能发 生在午夜前; (3)若乙的证词正确,则午夜时灯光未灭; (4)若乙的证词不正确,则作案时间发生在午夜前; (5)午夜时屋里灯灭了.试问:盗窃DVD的是甲还是乙,主要内容,.1 命题与联结词 .2 命题公式与赋值 .3 等值演

2、算 .4 析取范式与合取范式 .5命题逻辑的推理理论,1.1 命题与联结词,. 命题的概念 所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命题。命题仅有两种可能的真值真和假，且二者只能居其一真用1或T表示，假用0或F表示。由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。,例1.1 判断下列句子中哪些是命题.,(1) 2是素数. (2) x+y9. (3) 太阳从西方升起. (4) 乌鸦是黑色的. (5) 这个男孩多勇敢啊! (6) 明年中秋节的晚上是晴天. (7) 您贵姓? (8) 请把门开开! (

3、9) 地球外的星球上也有生物,如果一陈述句再也不能分解成更为简单的语句，由它构成的命题称为原子命题.原子命题是命题逻辑的基本单位。 命题分为两类，第一类是原子命题，原子命题用大写英文字母P，Q，R及其带下标的Pi，Qi，Ri，表示。 例: p: 2是素数 ; q :乌鸦是黑色的. 第二类是复合命题，它由原子命题、命题联结词和圆括号组成。,. 命题联结词,定义1.1 设P表示一个命题，由命题联结词l和命题P连接成lP，称lP为P的否定式复合命题， lP读“非P”。称l为否定联结词 (否定联结词“l”的定义可由表1.1.1表示之).,例: P: 10是素数 真值为F lp: 10不是素数 真值为T

4、 Q: 5是素数 真值为T lQ 5不是素数 真值为F 由于“否定”修改了命题，它是对单个命题进行操作，称它为一元联结词.,定义1.2 设P和Q为两个命题,由命题联结词将P和Q连接成PQ,称PQ为命题P和Q的合取式复合命题，PQ读做“P与Q” , 或“P且Q”。 称为合取联结词.,自然语言中,既又,不但而且 虽然但是 等都可以符号化为,例1.3 将下列命题符号化. (1)张路即聪明又用功. (2)张路不仅聪明,而且用功. (3)张路虽然不太聪明,但他很用功. (4)张路不是不聪明,而是不用功, 解 设 P:张路聪明,Q:张路用功. 则(1)到(4)分别符号化PQ， PQ lPQ ，l（lP）l

5、Q,定义.1.3 设P和Q为两个命题，由命题联结词把P和Q连接成PQ，称PQ为命题P和Q的析取式复合命题，PQ读做“P或Q”。称为析取联结词。,自然语言中的“或”有二义性，有时具有相容性，有时具有排斥性，注意区分,例1.3 将下列命题符号化 (1)谢丹生于1972年或1973年. (2)吕小洲学过德语或法语 (3)派老王或老李中的一人到上海开会. 分析: 上述例题(1) (3)的或为排斥或,而(2)中的或为可兼或.,解 设：谢丹生于1972年 S: 谢丹生于1973年 Q: 吕小洲学过德语 ：吕小洲学过法语 ：派老王到上海开会 ：派老李到上海开会,则: (1) 可符号化为RS ; (2)可符号

6、化为QM ; (3)可符号化为(NlH)(lNH),定义1.1.4设P和Q为两个命题 ，由命题联结词把P和Q 连接成 PQ，称PQ为命题P和Q的条件式复 合命题 , 简称条件命题PQ 读做 “P条件Q”或者 “若P则Q”。称为条件联结词 或蕴涵联结词,自然语言中, “只要就”，“仅当”，“只有才”等都可以符号化 为PQ的形式 自然语言中, “如果则”中的与 往往有某种内在的联系，而在数 理逻辑中，与不一定有联系 在数学和其他自然科学中，“如果 则”表示的前件为真，后件为 真的推理关系，但数理逻辑中不同,例1. 将下列命题符号化 (1)若3+3=6，则地球是运动的. (2)只要a是4的倍数,a就

7、是2的倍数. (3) a是4的倍数,仅当a是2的倍数 (4)只有a是2的倍数, a才是4的倍数 解设：3+3=6：地球是运动的 ：a是4的倍数： a是2的倍数 则 (1)可符号化为PQ (2)_ (4)可符号化为RS,定义.1.5令P与Q是两个命题，由命题联结词把P和Q连接成P Q，称P Q为命题P和Q的双条件式复合命题，简称双条件命题，P Q读做“P当且仅当Q”，称为双条件联结词。,例1. 将下列命题符号化 (1)2+3=5当且仅当是有理数； 解设：2+3=5：是有理数 则(1)可符号化为P Q (2)A,B两角相等当且仅当他们是同位角 解设：A,B两角相等： ：A,B是同位角 则(2)可符

8、号化为P Q,例1.6 将下列命题符号化,并求其真值 (1) 如果是合数则是素数，并且如果是素数，则它不能被整除 解设:是合数: 4是素数， R: 4能被2正整除 则(1) 符号化为(PQ)(QR) 因为(00)(01),其真值为1,(2) 如果2+35当且仅当5是合数,则4和 7都是无理数 解设:2+35: 5是合数， R: 4是无理数, S: 7是无理数 (2) 符号化为(P Q) (RS) 因为把个自的真值代入上式得 (0 0)(00) 计算其真值为0,强调： 复合命题的真值只取决于各原子命题的真值，而与它们的内容、含义无关，与原子命题之间是否有关系无关，理解和掌握这一点是至关重要的,1

9、. 命题公式与赋值,. 命题变元 在命题逻辑中，命题又有命题常元和命题变元之分。一个确定的具体的命题，称为命题常元；一个不确定的泛指的任意命题，称为命题变元。,命题变元不是命题，只有用一个特定的命题取代才能确定它的真值：真或假。这时也说对该命题变元指派真值。 命题常元和命题变元均可用字母P等表示。由于在命题逻辑中并不关心具体命题的涵义，只关心其真值，因此，可以形式地定义它们如下：,定义.以真或1、假或0为其变域的变元，称为命题变元；真或1、假或0称为命题常元。,2.合式公式 通常把含有命题变元的断言称为命题公式.但这没能指出命题公式的结构, 因为不是所有由命题变元、联结词和括号所组成的字符串都

10、能成为命题公式。常使用归纳定义命题公式，以便构成的公式有规则可循。由这种规定产生的公式称为合式公式。,定义. 合式公式是由下列规则生成的公式： 单个命题变项(或常项)是合式公式。 若A是一个合式公式，则(lA)也是一 个合式公式。 若A、B是合式公式,(AB)、(AB)、 (AB)和(A B)都是合式公式。,只有有限次使用、和生成的公 式才是合式公式(也称公式)。 符号集, ,运算优级：,高,低,当合式公式比较复杂时，常常使用很 多圆括号，为了减少圆括号的使用量 可作以下约定： 规定联结词的优先级由高到低的次序为：l、 相同的联结词按从左至右次序计算时，圆括号可省略。 最外层的圆括号可以省略。

11、,3. 命题赋值 定义.7 设 是出现在 公式A中的全部命题变项,给 各指定一个真值, 称为对A的一个赋值 或解释. 若指定的一组值使A的值为1, 则称这组值为A的成真赋值.若使A的值 为0,则称这组值为A的成假赋值.,定义1.8 对于公式中命题变元的每一种可能的真值指派，以及由它们确定出的公式真值所列成的表，称为该公式的真值表。 含n(n1)个命题变项的公式 A共 有 个赋值.,例1.7 求下列命题公式的真值表(1) (plq)r,(2) (p(qp) r,(3) l (pq) qr(记为A),定义1.9 设为一命题公式,() 若在它的各种赋值下取值均为真，则称为永真式（或重言式）； ()

12、若在它的各种赋值下取值均为假，则称为永假式（或矛盾式）； () 若不是永假式，则称是可满足的；,练习与作业,.求下列命题公式的真值表 (1) l (qp) (2) lpq (3) l qlp 思考：比较上述三题与 pq 真值表 .将下列命题符号化 (1)王威是100米冠军,又是200米冠军. (2)虽然天气很冷，老王还是来了 (3)他一边吃饭,一边看电视. (4) 如果天下大雨,他就乘公共汽车上班 (5) 只有天下大雨,他才乘公共汽车上班 (6)除非天下大雨,否则他不乘公共汽车上班 (7)不经一事,不长一智. ,1.3 等值演算,1.等价式定义 定义1.10 设A和B是两个命题公式，如果A、B

13、在其任意指派下，其真值都是相同的，则称A和B是等价的，或逻辑相等，记作AB，读作A等价B，称AB为等价式。,若公式A和B的真值表是相同的，则A和B等价。因此，验证两公式是否等价，只需做出它们的真值表即可。 注意和的区别与联系 联系：A B当且仅当AB是永真式 有时也称A B是永真双条件式。 ,区别：是逻辑联结词，属于目标语言中的符号，它出现在命题公式中；不是逻辑联结词，表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号。,2.基本等价式命题定律,3.两种规则,代入规则: 在一个永真式A中，任何一个原子命题变元R出现的每一处， 用另一个公式代入，所得公式B仍是永真式。称为代入规则

14、。 例 矛盾式 AA0 可用p 代 入得 pp0 ,也可用pq代得 (pq)(pq) 0,替换规则: 设(A)是含公式A的命题公式A,AB,则可用B替换(A)中的A, 得到(B)，则(A) (B) . 例 在演算中出现p (q r),则可用 q r替换q r,保证p (q r) p (q r),代入和替换有两点区别： 代入是对原子命题变元而言的，而替换可对命题公式实行。 代入必须是处处代入，替换则可部分替换，亦可全部替换。,例1.8 验证下列等值式 (1) (p q) r (q p) r 解 (p q) r (p q) r (蕴涵等值式) (p q) r (蕴涵等值式) (p q) r (德.

15、摩根律) ( q p ) r (交换律),(2) ( p q) r (pr) (qr) 解 ( p q) r ( p q) r (蕴涵等值式) ( p q) r (德.摩根律) ( p r ) ( q r) (分配律) ( p r ) (q r) (蕴涵等值式),例1.9 用等值演算法判断公式类型 (1) (p q) p q) r 解 原式( p q)p q)r ( p q)p ) q)r ( p q)p ) qr q p qr 0 说明(1)中公式为矛盾式,(2) p (p q) p ) q) 解 原式p(p q)p)q) p (p q p)q) p ( q q) p 1 p (2)为可满足式.,(3) (p q) q p 解 原式 ( p q) q p ( p q) q) p ( p q) q p ( p q) q p (p q) q p (p q p )( q q p) 1 (3)为永真式.,n元真值函数: n个命题变项 能并且只能生成 个真值