第1章命题逻辑基本概念

1、12课课 时：时：72学学 分：分：主讲教师：主讲教师： 李莹李莹联系方式：联系方式：tel:q: 378445041平时成绩平时成绩 （书面作业、考勤（书面作业、考勤 30%）期末考试（期末考试（70%）3学科简介学科简介 离散数学是以研究离散数学是以研究离散量的结构和相互间关系离散量的结构和相互间关系为为主要目标的学科。主要目标的学科。 离散数学通常研究的领域包括：数理逻辑、集合离散数学通常研究的领域包括：数理逻辑、集合论、代数结构、组合数学、图论和数论等。论、代数结构、组合数学、图论和数论等。l 数理逻辑：包括命题逻辑和谓词逻辑（教材第一、数理逻辑：包括命题逻辑

2、和谓词逻辑（教材第一、二、三、四、五章）二、三、四、五章）l 集合论：包括集合、关系和函数（教材第六、七、集合论：包括集合、关系和函数（教材第六、七、八章）八章）l 图论：包括图的基本概念，几种特殊的图（第十图论：包括图的基本概念，几种特殊的图（第十四至十八章）四至十八章）4 数理逻辑数理逻辑是用数学的方法来研究推理规律的科是用数学的方法来研究推理规律的科学。学。这里所指的数学方法，就是引进一套符号体系这里所指的数学方法，就是引进一套符号体系的方法，所以数理逻辑又称作的方法，所以数理逻辑又称作符号逻辑符号逻辑，它是从量，它是从量的侧面来研究思维规律的。它探索出一套完整的推的侧面来研究思维规律的

3、。它探索出一套完整的推理规则，这些规则用数学语句准确定义，按照这些理规则，这些规则用数学语句准确定义，按照这些规则可以确定任何特定的论证是否有效，这些规则规则可以确定任何特定的论证是否有效，这些规则可应用于各个领域，本课程介绍的是数理逻辑基本可应用于各个领域，本课程介绍的是数理逻辑基本的内容：的内容：命题逻辑和谓词逻辑。命题逻辑和谓词逻辑。第一部分第一部分 数理逻辑数理逻辑5主要内容主要内容l 命题逻辑基本概念命题逻辑基本概念l 命题逻辑等值演算命题逻辑等值演算l 命题逻辑推理理论命题逻辑推理理论l 一阶逻辑基本概念一阶逻辑基本概念l 一阶逻辑等值演算与推理一阶逻辑等值演算与推理第一部分第一部

4、分 数理逻辑数理逻辑6第一章第一章 命题逻辑的基本概念命题逻辑的基本概念 命题逻辑是谓词逻辑的基础，命题逻辑是研究命题逻辑是谓词逻辑的基础，命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导由命题为基本单位构成的前提和结论之间的可推导关系。关系。 主要内容主要内容l 命题与联结词命题与联结词 命题及其分类命题及其分类 联结词与复合命题联结词与复合命题l 命题公式及其赋值命题公式及其赋值7教学内容与要求教学内容与要求l 了解命题，深刻理解各联结词的逻辑关系了解命题，深刻理解各联结词的逻辑关系, , 熟练熟练地将命题符号化地将命题符号化l 会求复合命题的真值会求复合命题的真值l 深刻理解合

5、式公式及重言式、矛盾式、可满足式深刻理解合式公式及重言式、矛盾式、可满足式等概念等概念l 熟练地求公式的真值表，并用它求公式的成真赋熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型值与成假赋值及判断公式类型81.1.1 命题命题l命题：一个具有真假意义的陈述句被称为命题。命题：一个具有真假意义的陈述句被称为命题。 命题的真值：作为陈述句所表达的判断结果。命题的真值：作为陈述句所表达的判断结果。 真值的取值：真与假真值的取值：真与假 1.1 命题与联结词命题与联结词9例例1 下列句子中那些是命题？下列句子中那些是命题？ (1) 是有理数。是有理数。 (2) 2 + 5 = 7

6、 (3) x + 5 3 (4) 你去教室吗？你去教室吗？ (5) 这个苹果真大呀！这个苹果真大呀！ (6) 请不要讲话！请不要讲话！ (7) 2050年元旦下大雪。年元旦下大雪。 (8) 我正在说谎。我正在说谎。2 假命题假命题命题概念命题概念 真命题真命题不是命题不是命题 不是命题不是命题 不是命题不是命题不是命题不是命题命题，但真值现在不知道命题，但真值现在不知道悖论，不是命题悖论，不是命题 10命题概念命题概念注意：注意：命题是具有命题是具有唯一唯一真值的陈述句。真值的陈述句。感叹句、祈使句、疑问句都不是命题。感叹句、祈使句、疑问句都不是命题。陈述句中的悖论，判断结果不惟一确定的不是命

7、题。陈述句中的悖论，判断结果不惟一确定的不是命题。11l命题分类：命题分类：(1)按真值分为：真命题和假命题按真值分为：真命题和假命题(2)按结构分为：简单命题（也称原子命题）与复合按结构分为：简单命题（也称原子命题）与复合命题命题简单命题：不能被分解成更简单的命题简单命题：不能被分解成更简单的命题复合命题：由简单命题通过联结词联结而成的命复合命题：由简单命题通过联结词联结而成的命题题 命题分类命题分类12l简单命题符号化简单命题符号化(1)用小写英文字母用小写英文字母 p, q, r, , pi, qi, ri (i 1)表示简单命表示简单命题题(2)用用“1”表示真，用表示真，用“0”表示

8、假表示假 例如，令例如，令 p： 是有理数，则是有理数，则 p 的真值为的真值为0， q：2 + 5 = 7，则，则 q 的真值为的真值为1 2命题分类命题分类13例例2 以下都是复合命题以下都是复合命题 (1)3不是奇数。不是奇数。 (2)小明在一边数数，一边踢毽子。小明在一边数数，一边踢毽子。 (3)如果下周日下雪，那么我就去滑雪。如果下周日下雪，那么我就去滑雪。 (4)如果下周日不下雨并且没有考试，那么我去海边如果下周日不下雨并且没有考试，那么我去海边玩。玩。 (5)这次演讲比赛，我们班将由赵明或者张强参加。这次演讲比赛，我们班将由赵明或者张强参加。145种逻辑联结词种逻辑联结词l否定词

9、否定词“并非并非”l合取词合取词“并且并且”l析取词析取词“或者或者”l蕴含词蕴含词“如果如果，那么，那么”l等价词等价词“当且仅当当且仅当” 1.1.2 逻辑逻辑联结词联结词15否定联结词否定联结词定义定义 设设 p为命题，复合命题为命题，复合命题“非非p”(或或“p的否的否定定”)称为称为p的的否定式否定式，记作，记作 p，符号，符号 称作称作否定联否定联结词结词。规定：规定： p 为真当且仅当为真当且仅当p为假。为假。16例例3 将下列命题符号化将下列命题符号化 (1) 今天下午没有篮球比赛。今天下午没有篮球比赛。 令令p:今天下午有篮球赛今天下午有篮球赛, p (2) 我不去看电影。我

10、不去看电影。 令令p:我去看电影我去看电影, p (3) 我并非团员。我并非团员。 令令p:我是团员我是团员, p 否定联结词的实例否定联结词的实例17 (4) 不是所有的素数都是奇数。不是所有的素数都是奇数。 令令p:所有的素数都是奇数，所有的素数都是奇数， p (5) 所有的素数都不是奇数。所有的素数都不是奇数。 令令p:有些素数是奇数有些素数是奇数, p 否定联结词的实例否定联结词的实例18合取联结词合取联结词定义定义 设设p,q为两个命题，复合命题为两个命题，复合命题“p并且并且q”(或或“p与与 q”)称为称为p与与q的的合取式合取式，记作，记作p q， 称作称作合取联结词合取联结词

11、。规定：规定：p q为真当且仅当为真当且仅当p与与q同时为真。同时为真。19例例4 将下列命题符号化将下列命题符号化 (1) 吴颖既用功又聪明。吴颖既用功又聪明。 (2) 吴颖不仅用功而且聪明。吴颖不仅用功而且聪明。 (3) 吴颖虽然聪明，但不用功。吴颖虽然聪明，但不用功。解解 令令p:吴颖用功吴颖用功, q:吴颖聪明吴颖聪明 (1) p q (2) p q (3) p q (1)(3) 说明描述合取式的灵活性与多样性说明描述合取式的灵活性与多样性合取联结词的实例合取联结词的实例20 (4) 张辉与王丽都是三好生。张辉与王丽都是三好生。 设设p:张辉是三好生张辉是三好生, q:王丽是三好生王丽

12、是三好生 p q (5) 张辉与王丽是同学。张辉与王丽是同学。 设设 p:张辉与张辉与王丽是同学王丽是同学 (4)(5) 要求分清要求分清 “与与” 所联结的成分所联结的成分合取联结词的实例合取联结词的实例21析取联结词析取联结词定义定义 设设p, q为两个命题，复合命题为两个命题，复合命题“p或或q”称作称作p与与q的的析取式析取式，记作，记作p q， 称作称作析取联结词。析取联结词。 规定：规定：p q为假当且仅当为假当且仅当p与与q同时为假。同时为假。22例例5 将下列命题符号化将下列命题符号化 (1) 2 或或 4 是素数。是素数。 令令p:2是素数是素数, q:4是素数是素数, p

13、q (2) 张静爱唱歌或者爱听音乐。张静爱唱歌或者爱听音乐。 令令p:张静爱唱歌张静爱唱歌, q:张静爱听音乐张静爱听音乐, p q 析取联结词的实例析取联结词的实例(1)(2) 为相容或为相容或 23 (3) 小元元只能拿一个苹果或一个梨。小元元只能拿一个苹果或一个梨。 令令p:小元元拿一个苹果小元元拿一个苹果, q:小元元拿一个梨小元元拿一个梨 (pq) ( p q) (4) 王小红生于王小红生于 1975 年或年或 1976 年。年。 令令p:王小红生于王小红生于 1975 年年, q:王小红生于王小红生于1976 年年, (pq) ( p q) (3)(4) 为排斥或为排斥或析取联结词

14、的实例析取联结词的实例24蕴涵联结词蕴涵联结词定义定义 设设p, q为两个命题，复合命题为两个命题，复合命题“如果如果p, 则则q”称称作作p与与q的的蕴涵式蕴涵式，记作，记作pq，并称，并称p是蕴涵式的是蕴涵式的前前件件，q为蕴涵式的为蕴涵式的后后件件，称作称作蕴涵联结词蕴涵联结词。规定：规定：pq为假当且仅当为假当且仅当p为真为真q为假。为假。25蕴涵联结词蕴涵联结词(1) pq 的逻辑关系：的逻辑关系：q为为 p 的必要条件的必要条件(2) “如果如果 p, 则则 q” 有很多不同的表述方法：有很多不同的表述方法： 若若p，就，就q 只要只要p，就，就q p仅当仅当q 只有只有q 才才p

15、 除非除非q, 才才p 或或 除非除非q，否则非，否则非p， (3) 当当 p 为假时，称为空证明，认为为假时，称为空证明，认为pq为真为真(4) 常出现的错误：不分充分与必要条件常出现的错误：不分充分与必要条件26例例6 设设 p:天冷，天冷，q:小王穿羽绒服，将下列命题符号化小王穿羽绒服，将下列命题符号化 (1) 只要天冷，小王就穿羽绒服。只要天冷，小王就穿羽绒服。 (2) 因为天冷，所以小王穿羽绒服。因为天冷，所以小王穿羽绒服。 (3) 若小王不穿羽绒服，则天不冷。若小王不穿羽绒服，则天不冷。 (4) 只有天冷，小王才穿羽绒服。只有天冷，小王才穿羽绒服。 (5) 除非天冷，小王才穿羽绒服

16、。除非天冷，小王才穿羽绒服。 (6) 除非小王穿羽绒服，否则天不冷。除非小王穿羽绒服，否则天不冷。 (7) 如果天不冷，则小王不穿羽绒服。如果天不冷，则小王不穿羽绒服。 (8) 小王穿羽绒服仅当天冷的时候。小王穿羽绒服仅当天冷的时候。蕴涵联结词的实例蕴涵联结词的实例pq注意：注意： pq 与与 qp 等值（真值相同）等值（真值相同）pq q pqpqppq pqqp27 在自然语言中，在自然语言中，“如果如果p，则则q”中的前件与后件中的前件与后件往往具有某种内在联系。而数理逻辑中的往往具有某种内在联系。而数理逻辑中的p、q可可以无任何内在联系。以无任何内在联系。 例如：因为例如：因为23，所

17、以，所以1+1=228定义定义 设设 p, q为两个命题，复合命题为两个命题，复合命题“p当且仅当当且仅当q”称作称作p与与q的的等价式等价式，记作，记作pq，称作称作等价联结词等价联结词。等价联结词等价联结词规定：规定：pq为真当且仅当为真当且仅当p与与q同时为真或同时为假。同时为真或同时为假。29等价联结词等价联结词例例7 求下列复合命题的真值求下列复合命题的真值(1) 2 + 2 4 当且仅当当且仅当 3 + 3 6。(2) 2 + 2 4 的充要条件是的充要条件是3 是偶数。是偶数。(3) 2 + 2 4 当且仅当当且仅当 太阳从东方升起。太阳从东方升起。(4) 2 + 2 4，则美国

18、位于非洲；反之亦然。，则美国位于非洲；反之亦然。101030l 联结词集为联结词集为 , , , , ， p, p q, p q, pq, pq为基本复合命题。其中要特别注意理解为基本复合命题。其中要特别注意理解pq的涵义。的涵义。 反复使用反复使用 , , , , 中的联结词组中的联结词组成更为复杂的复合命题成更为复杂的复合命题 关于联结词关于联结词l 联结词的运算顺序：联结词的运算顺序： , , , , , 同级按先出现同级按先出现者先运算者先运算.31l 掌握联结词的逻辑涵义掌握联结词的逻辑涵义,能正确能正确对命题进行符号化对命题进行符号化l 掌握各种联结词的运算法则掌握各种联结词的运算

19、法则,能正确能正确进行逻辑运算进行逻辑运算能力要求能力要求32课堂练习课堂练习练习练习1 符号化下列命题符号化下列命题 (1)我们不能既划船又跑步。我们不能既划船又跑步。 (2)如果你来了，那么他唱不唱将看你是否伴奏而定。如果你来了，那么他唱不唱将看你是否伴奏而定。 (3)假如上午不下雨，我去看电影，否则就在家里读假如上午不下雨，我去看电影，否则就在家里读书或看报。书或看报。33练习练习2 设设p: 2+3=5 q: 大熊猫产在中国。大熊猫产在中国。 r: 太阳从西方升起。太阳从西方升起。判断下列命题的真假。判断下列命题的真假。(1)(pq)r(2)(r(p q)p(3) r( pq r)(4

20、)(p qr)( pq)r) 34答案答案练习练习1 符号化下列命题符号化下列命题 (1)我们不能既划船又跑步。我们不能既划船又跑步。 令令p:我们划船，我们划船，q:我们跑步我们跑步 (p q) (2)如果你来了，那么他唱不唱将看你是否伴奏而定。如果你来了，那么他唱不唱将看你是否伴奏而定。 令令p:你来了，你来了，q:他唱歌，他唱歌，r:你伴奏你伴奏 p(qr)35 (3)假如上午不下雨，我去看电影，否则就在家里读假如上午不下雨，我去看电影，否则就在家里读书或看报。书或看报。 令令p:上午下雨，上午下雨，q:我去看电影，我去看电影，r:我在家读书，我在家读书， s:我在家看报我在家看报 (

21、pq) (pr s)36练习练习2 设设p: 2+3=5 q: 大熊猫产在中国。大熊猫产在中国。 r: 太阳从西方升起。太阳从西方升起。判断下列命题的真假。判断下列命题的真假。(1)(pq)r(2)(r(p q)p(3) r( pq r)(4)(p qr)( pq)r) 0001371.2 命题公式及其赋值命题公式及其赋值命题变项与合式公式命题变项与合式公式l命题常项和命题变项命题常项和命题变项l合式公式合式公式l合式公式的层次合式公式的层次公式的赋值公式的赋值l公式赋值公式赋值l真值表真值表l公式类型公式类型38命题常项与命题变项命题常项与命题变项l命题常项（命题常元）：即真傎确定的命题命题

22、常项（命题常元）：即真傎确定的命题l命题变项（命题变元）：即代表命题的变量命题变项（命题变元）：即代表命题的变量,其真其真值不确定值不确定l常项与变项均用常项与变项均用 p, q, r, , pi, qi, ri, , 等表示等表示 例例 p:2+3=5 q:3小于小于2 命题命题r p r q r 注意：命题常项和命题变项的区别。注意：命题常项和命题变项的区别。39合式公式合式公式l 将命题项用联结词和圆括号按一定的逻辑关系联结将命题项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为合式公式起来的符号串称为合式公式定义定义1.6 合式公式合式公式（简称公式）的递归定义：（简称公式）的递归

23、定义： (1) 单个命题变项和命题常项是合式公式单个命题变项和命题常项是合式公式, 称作称作原子命原子命题公式题公式 (2) 若若A是合式公式，则是合式公式，则 ( A)是合式公式是合式公式 (3) 若若A, B是合式公式，则是合式公式，则(A B), (A B), (AB), (AB)是合式公式是合式公式 (4) 只有有限次地应用只有有限次地应用(1)(3) 形成的符号串是合式公形成的符号串是合式公式式40例如，例如，(pq) (qr)(st) p(pq) (pq)( q)，(pq 不是合式公式不是合式公式41合式公式的层次合式公式的层次定义定义1.7(1) 若公式若公式A是单个命题变项，则

24、称是单个命题变项，则称A为为0层公式；层公式；(2) 称称 A 是是 n+1(n0) 层公式是指下面情况之一：层公式是指下面情况之一： (a) A= B, B 是是 n 层公式；层公式； (b) A=B C, 其中其中B,C 分别为分别为 i 层和层和 j 层公式，层公式， 且且 n=max(i,j)； (c) A=B C, 其中其中 B,C 的层次及的层次及 n 同同(b)； (d) A=BC, 其中其中B,C 的层次及的层次及 n 同同(b)； (e) A=BC, 其中其中B,C 的层次及的层次及 n 同同(b)。 (3) 若公式若公式A的层次为的层次为k, 则称则称A为为k层公式层公式。

25、42合式公式的层次合式公式的层次例如例如 公式公式 A=p, B= p, C= pq, D= (pq)r, E=( p q) r) ( r s) 分别为分别为0层，层，1层，层，2层，层，3层，层，4层公式。层公式。43定义定义1.8 设设p1, p2, , pn是出现在公式是出现在公式A中的全部命题变项，中的全部命题变项，给给p1, p2, , pn各指定一个真值，称为对各指定一个真值，称为对A的一个的一个赋值赋值或或解释解释。若使。若使A为为1，则称这组值为，则称这组值为A的的成真成真赋值赋值；若使；若使A为为0，则称这组值为，则称这组值为A的的成假赋值成假赋值。公式赋值公式赋值44几点说

26、明：几点说明：l A中仅出现中仅出现 p1, p2, , pn，给，给A赋值赋值 = 1 2 n是是指指p1= 1, p2= 2, , pn= n, i=0或或1, i之间不加标之间不加标点符号点符号l A中仅出现中仅出现 p, q, r, , 给给A赋值赋值 1 2 3是指是指 p= 1, q= 2 , r= 3 l 含含n个命题变项的公式有个命题变项的公式有2n个赋值个赋值 如如 000, 010, 101, 110是是 (pq)r的成真赋值的成真赋值 001, 011, 100, 111是成假赋值是成假赋值公式赋值公式赋值45定义定义1.9 将命题公式将命题公式A在所有赋值下取值的情况列

27、成在所有赋值下取值的情况列成表表, 称作称作A的的真值表真值表。构造真值表的步骤：构造真值表的步骤：(1) 找出公式中所含的全部命题变项找出公式中所含的全部命题变项p1, p2, , pn(若若无下角标则按字母顺序排列无下角标则按字母顺序排列), 列出列出2n个全部赋值个全部赋值, 从从000开始开始, 按二进制加法按二进制加法, 每次加每次加1, 直至直至111为止；为止； (2) 按从低到高的顺序写出公式的各个层次；按从低到高的顺序写出公式的各个层次；(3) 对每个赋值依次计算各层次的真值对每个赋值依次计算各层次的真值, 直到最后计直到最后计算出公式的真值为止。算出公式的真值为止。真值表真值表46例例6 写出下列公式的真值表写出下列公式的真值