《邱婉玲耿素云离散数学ch》由会员分享,可在线阅读,更多相关《邱婉玲耿素云离散数学ch(33页珍藏版)》请在金锄头文库上搜索。
1、1,2,主要内容 命题逻辑基本概念 命题逻辑等值演算 命题逻辑推理理论 一阶逻辑基本概念 一阶逻辑等值演算与推理,第一部分 数理逻辑,3,第一章 命题逻辑的基本概念,主要内容 命题与联结词 命题及其分类 联结词与复合命题 命题公式及其赋值,4,命题与真值 命题:判断结果惟一的陈述句 命题的真值:判断的结果 真值的取值:真与假 真命题与假命题 注意: 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论,判断结果不惟一确定的不是命题,1.1 命题与联结词,5,例1 下列句子中那些是命题? (1) 是有理数. (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室吗? (5) 这个苹
2、果真大呀! (6) 请不要讲话! (7) 2050年元旦下大雪.,假命题,命题概念,真命题,不是命题,不是命题,不是命题,不是命题,命题,但真值现在不知道,6,命题分类:简单命题(也称原子命题)与复合命题 简单命题符号化 用小写英文字母 p, q, r, , pi, qi, ri (i1)表示简单命题 用“1”表示真,用“0”表示假 例如,令 p: 是有理数,则 p 的真值为0, q:2 + 5 = 7,则 q 的真值为1,命题分类,7,否定、合取、析取联结词,定义1.3 设p, q为两个命题,复合命题“p或q”称作p与q的析取式,记作pq,称作析取联结词. 规定pq为假当且仅当p与q同时为假
3、.,定义1.1 设 p为命题,复合命题“非p”(或“p的否定”)称为p的否定式,记作p,符号称作否定联结词. 规定p 为真当且仅当p为假.,定义1.2 设p,q为两个命题,复合命题“p并且q”(或“p与 q”)称为p与q的合取式,记作pq,称作合取联结词. 规定pq为真当且仅当p与q同时为真.,8,例2 将下列命题符号化. (1) 吴颖既用功又聪明. (2) 吴颖不仅用功而且聪明. (3) 吴颖虽然聪明,但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学.,合取联结词的实例,9,解 令p:吴颖用功, q:吴颖聪明 (1) pq (2) pq (3) pq (4) 设p:张辉是
4、三好生, q:王丽是三好生 pq (5) p:张辉与王丽是同学 (1)(3) 说明描述合取式的灵活性与多样性 (4)(5) 要求分清 “与” 所联结的成分,合取联结词的实例,10,例3 将下列命题符号化 (1) 2 或 4 是素数. (2) 2 或 3 是素数. (3) 4 或 6 是素数. (4) 小元元只能拿一个苹果或一个梨. (5) 王小红生于 1975 年或 1976 年.,析取联结词的实例,11,解 (1) 令p:2是素数, q:4是素数, pq (2) 令p:2是素数, q:3是素数, pq (3) 令p:4是素数, q:6是素数, pq (4) 令p:小元元拿一个苹果, q:小元
5、元拿一个梨 (pq)(pq) (5) p:王小红生于 1975 年, q:王小红生于1976 年, (pq)(pq) 或 pq (1)(3) 为相容或 (4)(5) 为排斥或, 符号化时(5)可有两种形式,而(4)则不能,析取联结词的实例,12,定义1.4 设p, q为两个命题,复合命题“如果p, 则q”称作p与q的蕴涵式,记作pq,并称p是蕴涵式的前件,q为蕴涵式的后件,称作蕴涵联结词. 规定:pq为假当且仅当p为真q为假.,蕴涵联结词,(1) pq 的逻辑关系:q为 p 的必要条件 (2) “如果 p, 则 q” 有很多不同的表述方法: 若p,就q 只要p,就q p仅当q 只有q 才p 除
6、非q, 才p 或 除非q,否则非p, (3) 当 p 为假时,pq恒为真,称为空证明 (4) 常出现的错误:不分充分与必要条件,13,例4 设 p:天冷,q:小王穿羽绒服,将下列命题符号化 (1) 只要天冷,小王就穿羽绒服. (2) 因为天冷,所以小王穿羽绒服. (3) 若小王不穿羽绒服,则天不冷. (4) 只有天冷,小王才穿羽绒服. (5) 除非天冷,小王才穿羽绒服. (6) 除非小王穿羽绒服,否则天不冷. (7) 如果天不冷,则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候.,蕴涵联结词的实例,pq,注意: pq 与 qp 等值(真值相同),pq,pq,qp,qp,pq,qp,qp,
7、14,定义1.5 设 p, q为两个命题,复合命题“p当且仅当q”称作p与q的等价式,记作pq,称作等价联结词. 规定pq为真当且仅当p与q同时为真或同时为假. pq 的逻辑关系:p与q互为充分必要条件,等价联结词,例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 连续.,1,0,0,1,0,15,本小节中p, q, r, 均表示命题.,联结词集为,
8、, , , ,p, pq, pq, pq, pq为基本复合命题. 其中要特别注意理解pq的涵义. 反复使用, , , , 中的联结词组成更为复杂的复合命题. 设 p: 是无理数,q: 3是奇数, r: 苹果是方的, s: 太阳绕地球转 则复合命题 (pq) (rs) p) 是假命题.,小 结,联结词的运算顺序:, , , , , 同级按先出现者先运算.,16,1.2 命题公式及其赋值,命题变项与合式公式 命题变项 合式公式 合式公式的层次 公式的赋值 公式赋值 公式类型 真值表,17,命题变项与合式公式,命题常项 命题变项(命题变元) 常项与变项均用 p, q, r, , pi, qi, ri
9、, , 等表示.,定义1.6 合式公式(简称公式)的递归定义: (1) 单个命题变项和命题常项是合式公式, 称作原子命题公式 (2) 若A是合式公式,则 (A)也是 (3) 若A, B是合式公式,则(AB), (AB), (AB), (AB)也是 (4) 只有有限次地应用(1)(3) 形成的符号串才是合式公式,几点说明: 归纳或递归定义, 元语言与对象语言, 外层括号可以省去,18,合式公式的层次,定义1.7 (1) 若公式A是单个命题变项,则称A为0层公式. (2) 称 A 是 n+1(n0) 层公式是指下面情况之一: (a) A=B, B 是 n 层公式; (b) A=BC, 其中B,C
10、分别为 i 层和 j 层公式, 且 n=max(i,j); (c) A=BC, 其中 B,C 的层次及 n 同(b); (d) A=BC, 其中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=(pq) r) (rs) 分别为0层,1层,2层,3层,4层公式.,19,定义1.8 设p1, p2, , pn是出现在公式A中的全部命题变项, 给p1, p2, , pn各指定一个真值, 称为对A的一个赋值或解释. 若使A为1, 则称这组值为A的
11、成真赋值; 若使A为0, 则称这组 值为A的成假赋值. 几点说明: A中仅出现 p1, p2, , pn,给A赋值=12n是指 p1=1, p2=2, , pn=n, i=0或1, i之间不加标点符号 A中仅出现 p, q, r, , 给A赋值123是指 p=1, q=2 , r=3 含n个命题变项的公式有2n个赋值. 如 000, 010, 101, 110是(pq)r的成真赋值 001, 011, 100, 111是成假赋值.,公式赋值,20,定义1.9 将命题公式A在所有赋值下取值的情况列成表, 称作 A的真值表. 构造真值表的步骤: (1) 找出公式中所含的全部命题变项p1, p2,
12、, pn(若无下角标 则按字母顺序排列), 列出2n个全部赋值, 从000开始, 按 二进制加法, 每次加1, 直至111为止. (2) 按从低到高的顺序写出公式的各个层次. (3) 对每个赋值依次计算各层次的真值, 直到最后计算出公式 的真值为止.,真值表,21,例6 写出下列公式的真值表, 并求它们的成真赋值和成假 赋值: (1) (pq) r (2) (qp) qp (3) (pq) q,真值表,22,(1) A = (pq) r,成真赋值:000,001,010,100,110; 成假赋值:011,101,111,真值表1,23,(2) B(qp)qp,成真赋值:00,01,10,11
13、; 无成假赋值,真值表2,24,(3) C (pq)q的真值表,成假赋值:00,01,10,11; 无成真赋值,真值表3,25,公式的类型,定义1.10 (1) 若A在它的任何赋值下均为真, 则称A为重言式或永真式; (2) 若A在它的任何赋值下均为假, 则称A为矛盾式或永假式; (3) 若A不是矛盾式, 则称A是可满足式. 由例1可知, (pq) r, (qp) qp, (pq) q 分别为非重言式的可满足式, 重言式, 矛盾式. 注意:重言式是可满足式,但反之不真. 真值表的用途: 求出公式的全部成真赋值与成假赋值, 判断公式的类型,26,第一章 习题课,主要内容 命题、真值、简单命题与复
14、合命题、命题符号化 联结词, , , , 及复合命题符号化 命题公式及层次 公式的类型 真值表及应用 基本要求 深刻理解各联结词的逻辑关系, 熟练地将命题符号化 会求复合命题的真值 深刻理解合式公式及重言式、矛盾式、可满足式等概念 熟练地求公式的真值表,并用它求公式的成真赋值与成假赋值及判断公式类型,27,1. 将下列命题符号化 (1) 豆沙包是由面粉和红小豆做成的. (2) 苹果树和梨树都是落叶乔木. (3) 王小红或李大明是物理组成员. (4) 王小红或李大明中的一人是物理组成员. (5) 由于交通阻塞,他迟到了. (6) 如果交通不阻塞,他就不会迟到. (7) 他没迟到,所以交通没阻塞.
15、 (8) 除非交通阻塞,否则他不会迟到. (9) 他迟到当且仅当交通阻塞.,练习1,28,提示: 分清复合命题与简单命题 分清相容或与排斥或 分清必要与充分条件及充分必要条件 答案: (1) 是简单命题 (2) 是合取式 (3) 是析取式(相容或)(4) 是析取式(排斥或) 设 p: 交通阻塞,q: 他迟到 (5) pq, (6) pq或qp (7) qp 或pq, (8) qp或pq (9) pq 或pq 可见(5)与(7),(6)与(8) 相同(等值),练习1解答,29,2. 设 p : 2是素数 q : 北京比天津人口多 r : 美国的首都是旧金山 求下面命题的真值 (1) (pq)r (2) (qr)(pr) (3) (qr)(pr) (4) (qp)(pr)(rq),0,练习2,1,0,0,30,3. 用真值表判断下面公式的类型 (1) pr(qp) (2) (pq) (qp) r (3) (pq) (pr),练习3,31,练习3解答,(1) pr(qp),矛盾式,32,练习3解答,(2) (pq) (qp) r,永真式,33,练习3解答,(3)