离散数学-ch1课件

1、Northeast Petroleum University,计算教程 2001,Northeast Petroleum University,Overview of the CS Body of Knowledge,Discrete structures (DS) Programming Fundamentals(PF) Algorithms and Complexity (AL) Architecture and Organization (AR) Operating Systems(OS) Net-Centric Computing (NC) Programming Langurages

2、(PL) Human-Computer Interaction(HC) Graphics and Visual Computing(GV) Intelligent Systems(IS) Information Management(IM) Social and Professional Issues(SP) Software Engineering (SE) Computational Science and Numerical Methods(CN),Northeast Petroleum University,Discrete Structures(43 core hours),DS1.

3、Functions, relations, and sets (6) DS2.Basic logic (10) DS3.Proof techniques (12) DS4.Basics of counting(5) DS5.Graphs and trees(4) DS6.Discrete probability(6),Northeast Petroleum University,Advanced courses,CS301.Combinatorics CS302.Probability and Statistics CS303.Coding and Information Theory,Nor

4、theast Petroleum University,课程地位,核心基础课程 后继课程: 数据结构, 操作系统, 数据库, 编译原 理、人工智能、形式语言与自动机等。 打好编程基础 有助于理解算法精髓，将算法转变为程序代码。 提高抽象思维能力,Northeast Petroleum University,课程内容,1. 数理逻辑,3. 代数结构,4. 组合数学,5. 图论,6. 初等数论,Northeast Petroleum University,主要内容 命题逻辑基本概念 命题逻辑等值演算 命题逻辑推理理论 一阶逻辑基本概念 一阶逻辑等值演算与推理,第一部分 数理逻辑,全书共150个定义

5、，81个定理，152道例题。,Northeast Petroleum University,第一章 命题逻辑的基本概念,主要内容 命题、联结词、复合命题 命题公式、赋值、命题公式类型,本章与后续各章的关系 本章是后续各章的准备和前提,本章特点 概念多(10个定义), 理论少(没有定理)。,Northeast Petroleum University,1.1 命题与联结词,例1 下列句子中那些是命题？ (1) 是有理数. (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室吗？ (5) 这个苹果真大呀！ (6) 请不要讲话！ (7) 2050年元旦下大雪. (8) 人能活千岁

6、. (9) 火星上有水. (10) 我正说假话.,假命题,真命题,不是命题,不是命题,不是命题,不是命题,命题，但真值现在不知道,假命题,是命题,不是命题,一. 命题与真值,Northeast Petroleum University,1.1 命题与联结词,二. 命题分类,三. 简单命题符号化,例2 先将下列命题符号化，再写出这些陈述。 (1) 2是偶数是不对的； (2) 2是偶素数； (3) 2或3是素数； (4) 如果2是素数，则3也是素数； (5) 2是素数当且仅当3也是素数。,简单命题: 由简单句构成, 不能再分解成更简单的命题。 复合命题: 由简单命题和联结词构成。,用小写英文字母

7、p, q, r, , pi, qi, ri (i1)表示简单命题 用“1”表示真，用“0”表示假,Northeast Petroleum University,1. 否定联结词,2. 合取联结词,四. 命题联结词：否定,合取,析取,蕴涵,等价,1.1 命题与联结词,例3 将下列命题符号化. (1) 吴颖既用功又聪明. (2) 吴颖不仅用功而且聪明. (3) 吴颖虽然聪明但不用功. (4) 吴颖与王丽都是三好生. (5) 吴颖与王丽是同学.,Northeast Petroleum University,1.1 命题与联结词,3. 析取联结词,例4 将下列命题符号化 (1) 2 或 3 是素数.

8、(2) 小王拿苹果或拿梨. (3) 小王只能拿苹果或拿梨. (4) 小王生于1975 年或 1976年.,Northeast Petroleum University,4. 蕴涵联结词,1.1 命题与联结词,(3) 常出现的错误: 不分充分与必要条件,Northeast Petroleum University,例5 设 p：天冷，q：小王穿羽绒服，将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 如果天不冷，则小王不穿羽绒服. (5) 只有天冷，小王才穿羽绒服. (6) 除非天冷，小王才穿羽绒服. (7)

9、 小王穿羽绒服仅当天冷的时候. (8) 除非小王穿羽绒服，否则天不冷.,pq,pq,qp,qp,qp,pq, pq,qp,1.1 命题与联结词,Northeast Petroleum University,例6 设 p: 3+3=6; q: 雪是白色的; r: a能被4整除; s: a能被2整除. 将下列命题符号化，并指出真值。 (1) 如果3+36，则雪是白的。 (2) 如果3+36，则雪是白的。 (3) 如果3+36，则雪不是白的。 (4) 如果3+36，则雪不是白的。 (5) 只要a能被4整除，则a一定能被2整除。 (6) a能被4整除，仅当a能被2整除。 (7) 除非a能被2整除，a才

10、能被4整除。 (8) 除非a能被2整除，否则a不能被4整除。 (9) 只有a能被2整除，a才能被4整除。 (10) 只有a能被4整除，a才能被2整除。,1.1 命题与联结词,pq, pq,p q, p q,rs,rs,rs,rs,rs,sr,真值:1,真值:1,真值:0,真值:1,真值:1,真值:1,真值:1,真值:1,真值:1,与a有关,Northeast Petroleum University,5. 等价联结词,1.1 命题与联结词,例7 令p:2+2=4; q:3+3=6; r:3是偶数; s:日出东方; t:驼鸟会飞; u: f (x) 在 x0 可导; v: f (x) 在 x0连

11、续. 将下列复合命题符号化，并指出真值。 (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 连续.,p q 1,p r 0,u v 0,p s 1,p t 0,联结词运算顺序: , , , , , 同级按出现顺序运算.,Northeast Petroleum University,命题变项与合式公式 合式公式的层次 公式赋值 公式真值表 公式的类型,1.2 命题公式及其赋值,Northeast Petrol

12、eum University,2. 合式公式,3. 合式公式层次,例如: A=p B=p C=pq D=(pq)r E=(pq) r) (rs),0 层,1.2 命题公式及其赋值,1 层,2 层,3 层,4 层,(1) 单个命题变项和命题常项是合式公式, 称作原子命题公式 (2) 若A是合式公式，则 (A)也是 (3) 若A, B是合式公式，则(AB), (AB), (AB), (AB)也是 (4) 只有有限次地应用(1)(3) 形成的符号串才是合式公式,1. 命题常项与命题变项,(1) 若公式A是单个命题变项，则称A为0层公式. (2) 称 A 是 n+1(n0) 层公式是指下面情况之一：

13、(a) A=B, B 是 n 层公式； (b) A=BC, A=BC, A=BC, A=BC, 其中B,C 分别为i 层和 j 层公式，且 n=max(i,j)； (3) 若公式A的层次为k, 则称A为k层公式.,Northeast Petroleum University,4 赋值或解释,1.2 命题公式及其赋值,几点说明：,(1) A中仅出现 p1, p2, , pn，给A赋值=12n是指 p1=1, p2=2, , pn=n .,(2) 含n个命题变项的公式有2n个赋值. 举例：(pq)r,成真赋值: 000, 010, 101, 110 成假赋值: 001, 011, 100, 111

14、.,A中仅出现 p, q, r, , 给A赋值 123 是指 p=1, q=2 , r=3 ,设p1, p2, , pn是出现在公式A中的全部命题变项, 给p1, p2, , pn各指定一个真值, 称为对A的一个赋值或解释. 若使A为1, 则称这组值为A的成真赋值; 若使A为0, 则称这组值为A的成假赋值.,Northeast Petroleum University,5 真值表 将命题公式A在所有赋值下取值的情况列成表, 称A的真值表.,构造真值表的步骤: (1) 找出公式中所含的全部命题变项p1, p2, , pn(若无下角标 则按字母顺序排列), 列出2n个全部赋值, 从000开始, 至

15、 111为止. (2) 按从低到高的顺序写出公式的各个层次. (3) 对每个赋值依次计算各层次的真值, 直到最后计算出公式 的真值为止.,1.2 命题公式及其赋值,Northeast Petroleum University,例8 写出下列公式的真值表, 并求它们的成真赋值和成假赋值. (1) (pq) r (2) (qp) qp (3) (pq) q,1.2 命题公式及其赋值,Northeast Petroleum University,(1) A = (pq) r,成真赋值:000,001,010,100,110; 成假赋值:011,101,111,1.2 命题公式及其赋值,Northea

16、st Petroleum University,(2) B(qp)qp,成真赋值:00,01,10,11; 无成假赋值,1.2 命题公式及其赋值,Northeast Petroleum University,(3) C (pq)q的真值表,成假赋值:00,01,10,11; 无成真赋值,1.2 命题公式及其赋值,Northeast Petroleum University,6 公式类型(重言式, 矛盾式, 可满足式),1.2 命题公式及其赋值,(1) 若A在它的任何赋值下均为真, 则称A为重言式或永真式; (2) 若A在它的任何赋值下均为假, 则称A为矛盾式或永假式; (3) 若A不是矛盾式,

17、 则称A是可满足式.,由上例可知, (pq) r, (qp) qp, (pq) q 分别为非重言式的可满足式, 重言式, 矛盾式. 注意：重言式是可满足式，但反之不真.,Northeast Petroleum University,(1) 求出公式的全部成真赋值与成假赋值 (2) 判断公式的类型: 末列全1(重言)全0(矛盾)其他可满足,7 真值表的用途,例1.10:下列公式哪些真值表相同？ (1) pq；(2) qr；(3) (pq)(pr)p)； (4) (qr)(pp),例1.9: 下列公式哪些真值表相同？ (1) pq；(2) pq；(3) (pq)；(4) (pq)(qp)； (5)

18、 qp,1.2 命题公式及其赋值,Northeast Petroleum University,第一章 小结,命题、真值 简单命题及符号化 联结词, , , , 复合命题及符号化 命题公式及层次 公式的类型 真值表及应用,Northeast Petroleum University,1. 将下列命题符号化 (1) 豆沙包是由面粉和红小豆做成的. (2) 苹果树和梨树都是落叶乔木. (3) 王小红或李大明是物理组成员. (4) 王小红或李大明中的一人是物理组成员. (5) 由于交通阻塞，他迟到了. (6) 如果交通不阻塞，他就不会迟到. (7) 他没迟到，所以交通没阻塞. (8) 除非交通阻塞，

19、否则他不会迟到. (9) 他迟到当且仅当交通阻塞.,巩固练习1,Northeast Petroleum University,提示：分清复合命题与简单命题 分清相容或与排斥或 分清充分与必要条件及充分必要条件,巩固练习1 (续),解答：(1) 是简单命题p 设 p: 苹果树是落叶乔木，q:梨树是落叶乔木 (2) pq 设 p: 王小红是物理组成员，q:李大明是物理组成员 (3) pq (4) (pq)(pq) 设 p: 交通阻塞，q: 他迟到 (5) pq (6) pq (7) qp (8) qp (9) qp,Northeast Petroleum University,巩固练习2,2. 设

20、 p : 2是素数 q : 北京比天津人口多 r : 美国的首都是旧金山 求下面命题的真值 (1) (pq)r (2) (qr)(pr) (3) (qr)(pr) (4) (qp)(pr)(rq),0,1,0,0,Northeast Petroleum University,巩固练习3,3. 用真值表判断下面公式的类型 (1) pr(qp) (2) (pq) (qp) r (3) (pq) (pr),Northeast Petroleum University,巩固练习3 (续),(1) pr(qp),矛盾式,Northeast Petroleum University,巩固练习3 (续),(2) (pq) (qp) r,重言式,Northeast Petroleum University,巩固练习3 (续),(3) (pq) (pr),非永真式的可满足式,Northeast Petroleum University,习题一(部分习题解答),pq,(p q)(pq)或pq,pq,pq,pq,pq,qp,qp,(pq)r,(pq