离散数学离散第一章

1、广东工业大学计算机学院1广东工业大学计算机学院2主要内容主要内容l 第一章：第一章：命题逻辑基本概念命题逻辑基本概念l 第二章：第二章：命题逻辑等值演算命题逻辑等值演算l 第三章：第三章：命题逻辑推理理论命题逻辑推理理论l 第四章：第四章：一阶逻辑基本概念一阶逻辑基本概念l 第五章：第五章：一阶逻辑等值演算与推理一阶逻辑等值演算与推理第一部分第一部分 数理逻辑数理逻辑广东工业大学计算机学院3第一章第一章 命题逻辑的基本概念命题逻辑的基本概念主要内容主要内容l 1.1 命题与联结词命题与联结词命题及其分类命题及其分类联结词与复合命题联结词与复合命题l 1.2 命题公式及其赋值命题公式及其赋值广东

2、工业大学计算机学院4命题与真值命题与真值 命题命题：判断结果惟一的陈述句。：判断结果惟一的陈述句。 命题的真值命题的真值：判断的结果。：判断的结果。 真值的取值真值的取值：真与假。：真与假。 真真命题与命题与假假命题：真值为命题：真值为真真( (假假) )的命题的命题注意：注意：1. 1. 感叹句、祈使句、疑问句都感叹句、祈使句、疑问句都不是不是命题命题2. 2. 陈述句中的陈述句中的悖论悖论不是命题。不是命题。3. 3. 判断结果不惟一确定的不是命题。判断结果不惟一确定的不是命题。 1.1 命题与联结词命题与联结词广东工业大学计算机学院5例例1 1 下列句子中那些是命题？下列句子中那些是命题

3、？ (1) 是有理数是有理数. (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室吗？你去教室吗？ (5) 这个苹果真大呀！这个苹果真大呀！ (6) 请不要讲话！请不要讲话！ (7) 2034年中国勇夺世界杯年中国勇夺世界杯. (8) 我正在说假话我正在说假话.2 假命题假命题命题概念命题概念 真命题真命题不是命题。真值无法确定不是命题。真值无法确定 不是命题不是命题 。疑问句。疑问句不是命题。感叹句不是命题。感叹句不是命题。祈使句不是命题。祈使句命题，但真值现在不知道命题，但真值现在不知道不是命题。不是命题。悖论：悖论：由真能推出假，又由假能推出真，从由真能推出假，又由

4、假能推出真，从而既不能为真，又不能为假的陈述句而既不能为真，又不能为假的陈述句广东工业大学计算机学院6l 命题分类：简单命题（也称原子命题）与复合命题命题分类：简单命题（也称原子命题）与复合命题简单命题符号化（本书定义）：简单命题符号化（本书定义）：l 1. 用用小写英文字母小写英文字母 p, q, r, , pi, qi, ri (I 1)表示简单命表示简单命题题l 2. 用用“1”表示真，用表示真，用“0”表示假表示假 例如：例如：令令 p： 是有理数，则是有理数，则 p 的真值为的真值为0， q：2 + 5 = 7，则，则 q 的真值为的真值为1 2命题分类命题分类广东工业大学计算机学院

5、71. 否定、合取、析取联结词否定、合取、析取联结词定义定义1.3 设设p, q为两个命题，复合命题为两个命题，复合命题“p或或q”称作称作p与与q的的析取式析取式，记作，记作pq，称作称作析取联结词析取联结词. 规定：规定： pq为假当且仅当为假当且仅当p与与q同时为假同时为假.定义定义1.1 设设 p为命题，复合命题为命题，复合命题“非非p”(或或“p的否定的否定”)称称为为p的的否定式否定式，记作，记作 p，符号，符号 称作称作否定联结词否定联结词. 规定：规定： p 为真当且仅当为真当且仅当p为假为假.定义定义1.2 设设p,q为两个命题，复合命题为两个命题，复合命题“p并且并且q”(

6、或或“p与与 q”)称为称为p与与q的的合取式合取式，记作，记作pq，称作称作合取联结词合取联结词. 规定：规定： pq为真当且仅当为真当且仅当p与与q同时为真同时为真.广东工业大学计算机学院8例例2 将下列命题符号化将下列命题符号化. (1) 吴颖既用功又聪明吴颖既用功又聪明. (2) 吴颖不仅用功而且聪明吴颖不仅用功而且聪明. (3) 吴颖虽然聪明，但不用功吴颖虽然聪明，但不用功. (4) 张辉与王丽都是三好生张辉与王丽都是三好生. (5) 张辉与张辉与王丽是同学王丽是同学.合取联结词的实例合取联结词的实例 (1) p q解解 令令p:吴颖用功吴颖用功, q:吴颖聪明吴颖聪明 (2) p

7、q (3) p q设设p:张辉是三好生张辉是三好生, q:王丽是三好生王丽是三好生(4) p q(5) p: 张辉与张辉与王丽是同学王丽是同学(1)(3) 说明描述合取式的灵活性与多样性说明描述合取式的灵活性与多样性(4)(5) 要求分清要求分清 “与与” 所联结的成分所联结的成分广东工业大学计算机学院9例例3 将下列命题符号化将下列命题符号化(1) 2 或或 4 是素数是素数.(2) 2 或或 3 是素数是素数.(3) 4 或或 6 是素数是素数.(4) 小元只能拿一个苹果或一个梨小元只能拿一个苹果或一个梨.(5) 王小红生于王小红生于 1975 年或年或 1976 年年.析取联结词的实例析

8、取联结词的实例解：解：(1) 令令p:2是素数是素数, q:4是素数是素数, p q解：解：(2) 令令p:2是素数是素数, q:3是素数是素数, p q解：解：(3) 令令p:4是素数是素数, q:6是素数是素数, p q解：解：(4) 令令p:小元拿一个苹小元拿一个苹果果, q:小元拿一个梨小元拿一个梨 (pq) ( p q)解：解：(5) p:王小红生于王小红生于 1975 年年, q:王小红生于王小红生于1976 年年, (pq) ( p q) 或或 p q相容或相容或排斥或排斥或广东工业大学计算机学院10定义定义1.4 设设p, q为两个命题，复合命题为两个命题，复合命题“如果如果p

9、, 则则q”称作称作p与与q的的蕴涵式蕴涵式，记作，记作pq，并称，并称p是蕴涵式的是蕴涵式的前件前件，q为蕴涵式的为蕴涵式的后后件件，称作称作蕴涵联结词蕴涵联结词. 规定：规定：pq为假当且仅当为假当且仅当p为真为真q为假为假.2. 蕴涵联结词蕴涵联结词(1) pq 的逻辑关系：的逻辑关系：q为为 p 的必要条件的必要条件(2) “如果如果 p, 则则 q” 有很多不同的表述方法：有很多不同的表述方法： 若若p，就，就q 只要只要p，就，就q p仅当仅当q 只有只有q 才才p 除非除非q, 才才p 或或 除非除非q，否则非，否则非p， (3) 当当 p 为假时，为假时，pq恒为真，称为恒为真

10、，称为空证明空证明 (4) 常出现的错误：不分常出现的错误：不分充分与必要条件充分与必要条件广东工业大学计算机学院11例例4 设设 p：天冷，：天冷，q：小王穿羽绒服，将下列命题符号化：小王穿羽绒服，将下列命题符号化(1) 只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服.(2) 因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服.(3) 若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷.(4) 只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服.(5) 除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服.(6) 除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷.(7) 如果天不冷，

11、则小王不穿羽绒服如果天不冷，则小王不穿羽绒服.(8) 小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.(9) 只要小王穿羽绒服，天就冷只要小王穿羽绒服，天就冷.蕴涵联结词的实例蕴涵联结词的实例pq注意：注意： pq 与与 qp 等值（真值表相同）等值（真值表相同）pqpqqpqppqqpqpqp广东工业大学计算机学院12定义定义1.5 设设 p, q为两个命题，复合命题为两个命题，复合命题“p当且仅当当且仅当q”称作称作p与与q的的等价式等价式，记作，记作pq，称作称作等价联结词等价联结词. 规定：规定：pq为真当且仅当为真当且仅当p与与q同时为真或同时为假同时为真或同时为假.pq 的逻

12、辑关系：的逻辑关系：p与与q互为充分必要条件互为充分必要条件3. 等价联结词等价联结词例例5 5 求下列复合命题的真值求下列复合命题的真值(1) 2 + 2 4 当且仅当当且仅当 3 + 3 6. (2) 2 + 2 4 当且仅当当且仅当 3 是偶数是偶数.(3) 2 + 2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起.(4) 2 + 2 4 当且仅当当且仅当 美国位于非洲美国位于非洲.(5) 函数函数 f (x) 在在 x0 可导的充要条件是可导的充要条件是 它在它在 x0 连续连续. 10010广东工业大学计算机学院13l 本小节中本小节中p, q, r, 均表示命题均表示命题.l

13、 联结词集为联结词集为 , , , , 。运算顺序：。运算顺序： , , , , , 同级按先出现者先运算同级按先出现者先运算.l p, p q, p q, p q, p q为基本复合命题为基本复合命题. 其中要特其中要特别注意理解别注意理解pq的涵义的涵义. 反复使用反复使用 , , , , 中的联中的联结词组成更为复杂的复合命题结词组成更为复杂的复合命题. 其定义见其定义见P7.例：例：设设 p: 是无理数，是无理数，q: 3是奇数，是奇数， r: 苹果是方的，苹果是方的， s: 太阳绕地球转太阳绕地球转 则复合命题则复合命题 (pq) (rs) p) 是？是？. 2小结小结假命题假命题广

14、东工业大学计算机学院141.2 命题公式及其赋值命题公式及其赋值1. 1. 命题变项与合式公式命题变项与合式公式l 命题变项命题变项l 合式公式合式公式l 合式公式的层次合式公式的层次2. 2. 公式的赋值公式的赋值l 公式赋值公式赋值l 公式类型公式类型l 真值表真值表广东工业大学计算机学院15命题变项与合式公式命题变项与合式公式 命题常项（命题常元）：命题常项（命题常元）：即简单命题，其真值是确定的。即简单命题，其真值是确定的。 命题变项（命题变元）：命题变项（命题变元）：可取值为可取值为1（真）或者（真）或者0（假）的变元（假）的变元 常项与变项均用常项与变项均用 p, q, r, ,

15、pi, qi, ri, , 等表示等表示. l 定义定义1.6 合式公式合式公式（简称公式）的递归定义（简称公式）的递归定义(P8)： (1) 单个命题变项和命题常项是合式公式单个命题变项和命题常项是合式公式, 称作称作原子命题公式原子命题公式 (2) 若若A是合式公式，则是合式公式，则 ( A)也是也是合式公式合式公式 (3) 若若A, B是合式公式，则是合式公式，则(A B), (A B), (AB), (AB)也是也是合合式公式式公式 (4) 只有有限次地应用只有有限次地应用(1) (3)形成的符号串才是形成的符号串才是合式公式合式公式广东工业大学计算机学院16命题变项与合式公式的补充说

16、明命题变项与合式公式的补充说明定义定义1.6 合式公式合式公式几点补充说明：几点补充说明：1. 定义使用了定义使用了递归方式递归方式，这种方式类似于汉诺塔问题的描述，这种方式类似于汉诺塔问题的描述，是一种常见的定义方式是一种常见的定义方式2. 定义中使用定义中使用A、B等符号表示任意的合式公式，称作等符号表示任意的合式公式，称作元语言符元语言符号号。 p, p q, p q, p q,等称作等称作对象语言符号对象语言符号。对象语言对象语言是指是指用来描述研究对象的语言。用来描述研究对象的语言。 元语言元语言和和对象语言对象语言的关系：的关系：元语言元语言用于描述用于描述对象语言对象语言。3.

17、( A)、(A B)等公式单独出现时，外层括号可省去。等公式单独出现时，外层括号可省去。广东工业大学计算机学院17合式公式的层次合式公式的层次定义定义1.7 (1) 若公式若公式A是单个命题变项，则称是单个命题变项，则称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, 其

18、中其中B,C 的层次及的层次及 n 同同(b)； (e) A=BC, 其中其中B,C 的层次及的层次及 n 同同(b). (3) 若公式若公式A的层次为的层次为k, 则称则称A为为k层公式层公式. 例如例如 公式公式 A=p, B= p, C= pq, D= (pq)r, E=( p q) r) ( r s) 分别为分别为0层，层，1层，层，2层，层，3层，层，4层公式层公式.广东工业大学计算机学院18定义定义1.8 设设p1, p2, , pn是出现在公式是出现在公式A中的全部命题变项中的全部命题变项, 给给p1, p2, , pn各指定一个真值各指定一个真值, 称为对称为对A的一个的一个赋

19、值赋值或或解释解释. 若使若使A为为1, 则称这组值为则称这组值为A的的成真赋值成真赋值; 若使若使A为为0, 则称这组则称这组值为值为A的的成假赋值成假赋值.几点说明：几点说明：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个赋值个赋值. 公式赋值公式赋值例如：例如： 对于公式对于公式

20、(pq)r：成真赋值：成真赋值：000, 010, 101, 110成假赋值：成假赋值：001, 011, 100, 111广东工业大学计算机学院19定义定义1.9 将命题公式将命题公式A在所有赋值下取值的情况列成表在所有赋值下取值的情况列成表, 称作称作A的的真值表真值表.构造真值表的步骤构造真值表的步骤:(1) 找出公式中所含的全部命题变项找出公式中所含的全部命题变项p1, p2, , pn(若无下角标若无下角标 则按字母顺序排列则按字母顺序排列), 列出列出2n个全部赋值个全部赋值, 从从000开始开始, 按按 二进制加法二进制加法, 每次加每次加1, 直至直至111为止为止. (2)

21、按从低到高的顺序写出公式的各个层次按从低到高的顺序写出公式的各个层次.(3) 对每个赋值依次计算各层次的真值对每个赋值依次计算各层次的真值, 直到最后计算出公式直到最后计算出公式 的真值为止的真值为止.真值表真值表广东工业大学计算机学院20例例6. 写出下列公式的真值表写出下列公式的真值表, 并求它们的成真赋值和成假赋值并求它们的成真赋值和成假赋值: (1) (p q) r真值表举例真值表举例p q rp q r (p q)r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 00111111 10101010 11101010 成真赋值成真赋值成假赋值成假赋值

22、广东工业大学计算机学院21(2) B (qp) qp成真赋成真赋值值:00, 01, 10, 11; 无成假赋值无成假赋值p q qp(qp) q(qp) qp0 00 11 01 1101100011111真值表举例真值表举例(续续1)广东工业大学计算机学院22(3) C ( p q) q的真值表的真值表成假赋值成假赋值:00, 01, 10, 11; 无成真赋值无成真赋值p q p p q ( p q) ( p q) q0 00 11 01 11100110100100000真值表举例真值表举例(续续2)广东工业大学计算机学院23哑元哑元哑元：哑元：设公式设公式A，B中含有命题变项中含有命

23、题变项p1, p2, , pn。A或者或者B不不全含全含这些命题变项，比如这些命题变项，比如A中不含中不含pi, 则称这些命题变项为则称这些命题变项为A的哑元。的哑元。特点：特点：A的取值与哑元无关。的取值与哑元无关。例：例：存在下列公式：存在下列公式： (1) p q (2) q r (3) ( p q) (q r) p则在这些公式中：则在这些公式中：对于公式对于公式(1)，r是哑元。是哑元。对于公式对于公式(2)，p是哑元。是哑元。对于公式对于公式(3)没有哑元。没有哑元。广东工业大学计算机学院24公式的类型公式的类型定义定义1.10 设设A为任一命题公式为任一命题公式.(1) 若若A在它

24、的任何赋值下均为真在它的任何赋值下均为真, 则称则称A为为重言式重言式或或永真式永真式;(2) 若若A在它的任何赋值下均为假在它的任何赋值下均为假, 则称则称A为为矛盾式矛盾式或或永假式永假式;(3) 若若A不是矛盾式不是矛盾式, 则称则称A是是可满足式可满足式.例：例：判断各式的类型判断各式的类型 (p q) r, (qp) qp, ( p q) q 分别为非重言式的可满足式分别为非重言式的可满足式, 重言式重言式, 矛盾式矛盾式.注意：注意：重言式是可满足式，但反之不真重言式是可满足式，但反之不真.真值表的用途真值表的用途: 求出公式的全部成真赋值与成假赋值求出公式的全部成真赋值与成假赋值

25、, 判断公判断公式的类型式的类型广东工业大学计算机学院25第一章第一章 小结小结主要内容主要内容l 命题、真值、简单命题与复合命题、命题符号化命题、真值、简单命题与复合命题、命题符号化l 联结词联结词 , , , , 及复合命题符号化及复合命题符号化l 命题公式及层次命题公式及层次l 公式的类型公式的类型l 真值表及应用真值表及应用基本要求基本要求l 深刻理解各联结词的逻辑关系深刻理解各联结词的逻辑关系, 熟练地将命题符号化熟练地将命题符号化l 会求复合命题的真值会求复合命题的真值l 深刻理解合式公式及重言式、矛盾式、可满足式等概念深刻理解合式公式及重言式、矛盾式、可满足式等概念l 熟练地求公

26、式的真值表，并用它求公式的成真赋值与成假熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型赋值及判断公式类型广东工业大学计算机学院261. 将下列命题符号化将下列命题符号化 (1) 豆沙包是由面粉和红小豆做成的豆沙包是由面粉和红小豆做成的. (2) 苹果树和梨树都是落叶乔木苹果树和梨树都是落叶乔木. (3) 王小红或李大明是物理组成员王小红或李大明是物理组成员. (4) 王小红或李大明中的一人是物理组成员王小红或李大明中的一人是物理组成员.提示：提示：分清复合命题与简单命题分清复合命题与简单命题分清相容或与排斥或分清相容或与排斥或 解：解： (1) 是简单命题是简单命题 (2) 是合取式是合取式 (3) 是析取式（相容或）是析取式（相容或）(4) 是析取式（排斥或）是析取式（排斥或）练习练习1pp qp q(pq) ( p q)广东工业大学计算机学院271. 将下列命题符号化将下列命题符号化 (5) 由于交通阻塞，他迟到了由于交通阻塞，他迟到了. (6) 如果交通不阻塞，他就不会迟到如果交通不阻塞，他就不会迟到. (7) 他没迟到，所以交通没阻塞他没迟到，所以交通没阻塞. (8) 除非交通阻塞，否则他不会迟到除非交通阻塞，否则他不会迟到. (9) 他迟