离散数学-数理逻辑.ppt
《离散数学-数理逻辑.ppt》由会员分享,可在线阅读,更多相关《离散数学-数理逻辑.ppt(86页珍藏版)》请在三一文库上搜索。
1、1,离 散 数 学,杨 敏 武汉大学国际软件学院,2,教材与参考资料,教材: 离散数学 (第2版),屈婉玲、耿素云、张立昂编,清华大学出版社 参考资料: 离散数学,刘玉珍、刘咏梅编,武汉大学出版社 Discrete Mathematical Structures(Sixth Edition), Bernard Kolman, Fobert C. Busby and Sharon Ross ,高等教育出版社有影印版、译本 Discrete Mathematics and Its Applications(Sixth Edition),美Kenneth H. Rosen,机械工业出版社影印版、译
2、本,3,课程主要内容,数理逻辑 集合论 图论 代数系统*,4,目的、意义和要求,研究内容:离散量的结构及其相互间的关系。 意义:计算机科学的理论基础。 目的:打基础 必备的数学知识 培养抽象思维能力、逻辑推理能力 教学内容: 第1-7 章重点 第9、14章备选 第8、11章自学 第10、12、13章不要求,5,学习要求,1、课堂要求: 按时上课 认真听讲 2、课外要求: 复习(每次课后,安排半个小时) 认真、按时完成作业(每次课后,安排1个小时),6,学习考查方法,1、出勤率:10% 不定期检查出勤情况 2、作业完成情况:10% 对作业完成情况进行登记 3、课堂测验 + 期中考试:20% 共
3、5 次 4、期末考试(闭卷):60%,7,第一篇 数理逻辑 第1章 导 论,数理逻辑的概念 数理逻辑的发展简史 数理逻辑的地位和作用,8,(1)定义,1.1 数理逻辑的概念,数理逻辑是采用数学方法研究抽象思维推理规律(形式推理)的一门科学。 命题逻辑是数理逻辑的基本组成部分之一 推理的基本要素是命题 把命题作为基本单位来分析,符号化,研究公式间的关系,推导、演算,9,(2)方法,引入一套数学符号系统来进行研究,强调推理过程中前提和结论之间的形式关系。,例:A、B、C、D4人做百米竞赛,观众甲、乙、丙预报比赛结果的名次为: 甲:C第一,B第二 乙:C第二,D第三 丙:A第二,D第四 比赛结束后发
4、现甲乙丙每人报告的情况都各对一半,试问实际名次如何?,1.引入pi,qi,ri,si分别表示“A排名第i,B排名第i ,C排名第i ,D排名第i” 2. 给出个命题之间的关系 (1)(r1 q2) (r1 q2) 1 (2)(r2 s3) (r2 s3) 1 (3)(p2 s4) (p2 s4) 1 3.通过演算规则,得出结果,10,(3)内容,谓词逻辑,命题逻辑,11,(4)分支,模型论,证明论,公理集合论,递归论,12,1.2 数理逻辑的发展简史,创立阶段,起源阶段,完善阶段,发展历史,13,起源阶段,德国数学家、哲学家 G.Leibniz(16461716),提出建立一种普遍的符号语言,
5、利用符号语言进行思维演算的设想。,14,创立阶段,英国数学家 G.Bool于1847年发表逻辑的数学分析,创建一套表示逻辑推理的基本符号以及符号的运算规律,建立了布尔代数。,德国数学家 G.Frege于1879年在概念的演算一书中引进谓词符号和量词符号,创建第一个比较严格的逻辑演算系统。,15,完善阶段,英国逻辑学家 A.N.Witehead和B.Russel于1910将当时的数理逻辑写入了数学原理中,使数理逻辑成为了一门专门的学科。,20 世纪 30 年代,由于众多科学家的努力,衍生出许多新的分支,如:直觉主义逻辑、多值逻辑、组合逻辑等。,16,1.3 数理逻辑的地位和作用,1、计算机科学的
6、重要的理论基础之一; 2、对数学、计算机科学、人工智能、语言学、控制论等诸多学科产生深远的影响。 3、在计算机科学中的应用:软件、硬件设计,17,第2章 命题逻辑,2.1 命题逻辑基本概念 2.2 命题逻辑等值演算 2.3 范式 2.4 命题逻辑推理理论,18,2.1 命题逻辑基本概念,2.1.1 命题与联结词 命题与真值(简单命题, 复合命题) 联结词(, , , , ) 2.2.2 命题公式及其分类 命题公式及其赋值 真值表 命题公式的分类,19,2.1.1 命题与联结词,1、命题及相关概念 (1)命题的定义,两者必居其一且只居其一 二值逻辑,命题定义的理解:从两个方面把握这个概念(1)陈
7、述句; (2)真值唯一性(注意:真值可能目前还不知道答案)。,命题:一个具有真假意义的陈述句。,什么是真值:只包含真/假两个值的量。 T/1真 F/0假,20,注意:(1) 感叹句、祈使句、疑问句都不是命题 (2)陈述句中的悖论以及判断结果不唯一确定的也不是命题,21,中国的首都在北京。 1+1=10 请开门! x+y=1 明年10月1日是晴天。 本命题是假的。 李红既学英语又学日语。,例1 判断下列个自然语言是否是命题,22,(2)几个基本概念 真命题与假命题 命题变元与命题常元,真命题: 真值为真的命题 假命题: 真值为假的命题,若p即可以表示真命题,又可以表示假命题,则称p为命题变元。
8、T永远表示真命题,F表示假命题,称T和F为命题常元。,23,例2,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(1),(2),(5)是命题, (3),(4),(6)(8)都不是命题,真值确定, 但未知,下列句子中哪些是命题?并指出命题的真值。 (1) 北京是中华人民共和国的首都. (2) 2 + 5 8. (3) x + 5 3. (4) 你会开车吗? (5) 2050年元旦北京是晴天. (6) 这只兔子跑得真快呀! (7) 请关上门! (8) 我正在说谎话.,24,(1)简单命题与复合命题 (2)联结词的定义 (3)联结词的优先级,2.联接词,25,(1)简单命题与复合命题,简
9、单命题(原子命题):简单陈述句构成的命题。 简单命题的符号化:用p, q, r, ,pi,qi,ri (i1)表示 用“1”表示真,用“0”表示假 复合命题:由简单命题通过联结词联结而成的陈述句。 例如 如果明天天气好, 我们就出去郊游 设p:明天天气好, q:我们出去郊游, 如果p, 则q 又如 张三一面喝茶一面看报 设p:张三喝茶, q:张三看报, p并且q,26,(2)联结词的定义,否定词(),定义2.1 设p为命题,复合命题 “非p”(或 “p的否定”)称为p的否定式,记作p,符号称作否定联结词, 并规定p为真当且仅当 p为假。,例如 p:2是合数, p: 2不是合数。 p为假, p为
10、真。,27,合取词( ),定义2.2 设p,q为二命题, 复合命题“p并且q”(或“p与q”)称为p与q的合取式, 记作pq, 称作合取联结词, 并规定 pq为真当且仅当 p与q同时为真.,例如 p:2是偶数, q: 2是素数, pq: 表示的含义是2是偶素数。 因为p为真, q也为真,所以 pq为真。,28,例3 将下列命题符号化.,解:记 p:王晓用功, q:王晓聪明,(1) pq,(2) pq,(3) qp,(4) 记 r: 张辉是三好生, s: 王丽是三好生, rs,(5) 简单命题, 记 t: 张辉与王丽是同学,(1) 王晓既用功又聪明. (2) 王晓不仅聪明,而且用功. (3) 王
11、晓虽然聪明,但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学.,29,析取词(),定义2.3 设 p、q为命题,复合命题“p或q”称作p与q的析取式,记作pq, 称作析取联结词, 并规定pq为假当且仅当p与q同时为假。,例如 张三和李四至少有一人会英语 设 p:张三会英语, q:李四会英语, 符号化为pq。,30,相容或与排斥或,析取词表示的是相容或,即 p 和 q 均为真时 (p q)亦为真,而与之对应的还有一个是排斥或,它表示的含义是p 和 q 不能同时为真。,例如 这件事由张三和李四中的一人去做 设 p:张三做这件事, q:李四做这件事 应符号化为 (p q) (p
12、q),31,例4 将下列命题符号化,并指出其真值,解:记 p:2是素数, q:3是素数, r:4是素数, s:6是素数,(1) pr,(2) pq,(3) rs,(4) 记t:元元拿一个苹果,u:元元拿一个梨,真值:1,真值: 1,真值: 0,(tu)(tu),(5) 记v:王晓红生于1975年,w:王晓红生于1976年,(vw)(vw),又可形式化为 vw,(1) 2或4是素数. (2) 2或3是素数. (3) 4或6是素数. (4) 元元只能拿一个苹果或一个梨. (5) 王晓红生于1975年或1976年.,32,蕴涵词( ),定义2.4 设 p,q为二命题, 复合命题 “如果p,则q” 称
13、作p与q的蕴涵式, 记作pq, 并称p是蕴涵式的前件, q为蕴涵式的后件. 称作蕴涵联结词, 并规定, pq为假当且仅当 p为真且q为假.,例如 如果明天天气好, 我们就出去郊游 设p:明天天气好, q:我们出去郊游, 形式化为 pq,33,蕴涵词的其它表述方式,pq 的逻辑关系: q为p的必要条件, p为q的充分条件。 “如果p,则q” 的多种表述方式: 若p,就q 只要p,就q p仅当q 只有q 才p 除非q, 才p 除非q, 否则非p 当p为假时,pq为真(不管q为真, 还是为假),34,例5 设p:天冷, q:小王穿羽绒服,将下列命题符号化,注意: pq 与 qp 等值(真值相同),p
14、q,pq,qp 或 pq,pq,qp,qp,pq 或 qp,qp,(1) 只要天冷,小王就穿羽绒服. (2) 因为天冷,所以小王穿羽绒服. (3) 若小王不穿羽绒服,则天不冷. (4) 只有天冷,小王才穿羽绒服. (5) 除非天冷,小王才穿羽绒服. (6) 除非小王穿羽绒服,否则天不冷. (7) 如果天不冷,则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候.,35,等价词( ),定义2.5 设p, q为命题, 复合命题 “p当且仅当q”称作p与q的等价式, 记作pq, 称作等价联结词. 并规定pq为真当且仅当 p与q同时为真或同时为假。,pq 的逻辑关系: p与q互为充分必要条件 例如
15、这件事张三能做好, 且只有张三能做好 设p:张三做这件事, q:这件事做好了 形式化为: pq,36,例6 求下列复合命题的真值:,1,0,1,1,(1) 2+24 当且仅当 3+36. (2) 2+24 当且仅当 3是偶数. (3) 2+24 当且仅当 太阳从东方升起. (4) 2+25 当且仅当 美国位于非洲.,37,分析找出 简单命题,用字母表示 简单命题,用联接词联接命题符号,命题符号化的一般规则,38,分析找出 简单命题,用字母表示 简单命题,用联接词联接命题符号,解 令 p: 我上街 q: 我累 r: 我去书店看看 则可符号化为:(pq)r,例7 将下列命题符号化: 如果我上街并且
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 数理逻辑
链接地址:https://www.31doc.com/p-2120364.html