西安电子科技大学考研复试科目-离散数学01命题逻辑a



西安电子科技大学计算机学院
数 学 离 散
毛立强 主讲
西安电子科技大学计算机学院 毛立强
1
lqmao@mail.xidian.edu.cn
课程信息
教材:
离散数学,方世昌,西电出版社 离散数学习题解答,孙学红,秦伟良,西电出版社
参考书:
离散数学,左孝凌等,上海科学技术文献出版社
西安电子科技大学计算机学院 毛立强
2
lqmao@mail.xidian.edu.cn
课程信息
54学时,27次课 作业与辅导: 考试:闭卷,与平时成绩加权
西安电子科技大学计算机学院 毛立强
3
lqmao@mail.xidian.edu.cn
课程信息
离散数学是计算机相关专业的重要基础课程。
操作系统 数据结构 编译原理 算法分析 数字电路 数据库系统 人工智能
4
……
西安电子科技大学计算机学院 毛立强
lqmao@mail.xidian.edu.cn
课程信息
离散数学是现代数学的一个分支,以离散对象的结 构和相互关系为研究对象。 主要包括数理逻辑、集合论、代数结构和图论四部 分 通过学习本课程,掌握基本的离散信息的组织和管 理方法,了解计算机科学的部分理论基础。 强调逻辑性、抽象性,注重概念、方法与应用。
西安电子科技大学计算机学院 毛立强
5
lqmao@mail.xidian.edu.cn
第一章 数理逻辑(mathematical logic)
逻辑学是一门研究推理规律的科学;数理逻辑就是 用数学方法研究推理规律,这里的“数学方法”是指 引入一套符号体系的方法,所以数理逻辑又称为“符 号逻辑”。 传统的数理逻辑包括“四论一演算”:递归论、公理 化集合论、模型论和证明论,逻辑演算,目前新提 出了很多新的逻辑,如多逻辑、模态逻辑、时序逻 辑、算法逻辑、程序逻辑等等。 本课程主要学习命题逻辑(proposition logic)和谓 词逻辑(predication logic) 。
西安电子科技大学计算机学院 毛立强
6
lqmao@mail.xidian.edu.cn
第一章 数理逻辑

  1.1 命题
  1.2 重言式
  1.3 范式
  1.4 联结词的扩充与规约
  1.5 推理规则和证明方法
  1.6 谓词和量词
  1.7 谓词演算的永真公式
  1.8 谓词演算的推理规则
西安电子科技大学计算机学院 毛立强
7
lqmao@mail.xidian.edu.cn
命题及其表示法
命题 断言是一陈述语句。一个命题(proposition) 是一个或真或假而不能两者都是的断言。如果命题 是真, 我们说它的真值(truth value)为真 (T),如果命题是假, 我们说它的真值是假 (F)。
西安电子科技大学计算机学院 毛立强
8
lqmao@mail.xidian.edu.cn
例 1 下述都是命题: ; (a) 今天下雪 ; (b)能整除7的正整数只有1和7本身; (c) 2 是偶数而 3 是奇数; (d) 李自成起义那天, 杭州下雨; (e) 较大的偶数都可表示为两个质数之和。 以上命题, (a)的真值取决于今天的天气, (b)和(c)是真, (d) 已无法查明它的真值, 但它是或真或假的, 将它归属于命题。 (e)目前尚未确定其真假, 但它是有真值的, 应归属于命题。
西安电子科技大学计算机学院 毛立强
9
lqmao@mail.xidian.edu.cn
例 2 下述都不是命题: ; (a) x+y>
  4。 (b) x=
  3。 (c) 真好啊! (d) 你去哪里?
(a)和(b)是断言, 但不是命题, 因为它的真值取决于x和y的 值。 (c)和(d)都不是断言, 所以不是命题。
西安电子科技大学计算机学院 毛立强
10
lqmao@mail.xidian.edu.cn
例 3 一个人说:“我正在说谎”。 他是在说谎还是在说真话呢? 如果他讲真话, 那么他所说的 是真, 也就是他在说谎。 我们得出结论如果他讲真话, 那么他是 在说谎。另一方面, 如果他是说谎, 那么他说的是假; 因为他承认 他是说谎, 所以他实际上是在说真话, 我们得出结论如果他是说 谎, 那么他是讲真话。 从以上分析, 我们得出他必须既非说谎也不是讲真话。这样, 断言“我正在说谎”事实上不能指定它的真假, 所以不是命题。 这 种断言叫悖论(paradox) 。
11
西安电子科技大学计算机学院 毛立强
lqmao@mail.xidian.edu.cn
练习: 判断下列语句是否为命题。 (
  1)雪是黑的。 (
  2)
  1+1
  01=110 (
  3)别的星球上有生物。 (
  4)下课吧? (
  5)下课!
西安电子科技大学计算机学院 毛立强
12
lqmao@mail.xidian.edu.cn
若一个命题已不能分解成更简单的命题, 则这个命题叫原 子命题或本原命题。 例 1 中(a) , (b) , (d) , (e)都是本原命题, 但(c) 不是, 因为它可写成“2 是偶数”和“3 是奇数”两个命题。 命题和本原命题常用大写字母P , Q , R表示。 如用P表示 “4 是质数”, 则记为 ; P: 4 是质数。 表示命题的符号称为命题标识符。一个命题标识符如果表示确 定的命题,就称为命题常元;如果表示任意命题,就称为命题 变元。命题变元不是命题。可以对命题变元进行指派。
西安电子科技大学计算机学院 毛立强
13
lqmao@mail.xidian.edu.cn
命题联结词
命题和原子命题常可通过一些联结词构成新命题, 这种新命题 叫复合命题。例如 ; P : 明天下雪, Q : 明天下雨 是两个命题, 利用联结词“不”, “并且”, “或”等可分别构成新命 题: “非P” “明天不下雪”; “P并且Q” “明天下雪并且明天下雨”; “明天下雪或者明天下雨”等。“P或者Q”
西安电子科技大学计算机学院 毛立强
14
lqmao@mail.xidian.edu.cn
在代数式x+3 中, x , 3 叫运算对象, +叫运算符, x+3 表示运算结果。在命题演算中, 也用同样术语。联 结词就是命题演算中的运算符, 叫逻辑运算符或叫逻 辑联结词(logic connective) 。常用的有以下 5 个:否定、合取、析取、条件、双条件
西安电子科技大学计算机学院 毛立强
15
lqmao@mail.xidian.edu.cn

  1. 否定 ? 设P为一命题,P的否定(negation)是一个新的命题,记做?P, 称为“非P”。如果P为T,则?P为F;如果P为F,则?P为T。所以否 定词可以用下表定义。
P F T
16
?P T F
西安电子科技大学计算机学院 毛立强
lqmao@mail.xidian.edu.cn
这张表叫真值表, 定义运算符的真值表, 指明如何用运算对象 的真值, 来决定一个应用运算符的命题的真值。 真值表的左边列 出运算对象的真值的所有可能组合, 结果命题的真值列在最右边 的一列。为了便于阅读, 我们通常用符号T(true)或 1 代表真, 符号 F(false)或 0 代表假。 一般在公式中采用T和F, 在真值表中采用 1 和
  0。 这样, 以上真值表可写成
P 0 1
17
?P
1 0 西安电子科技大学计算机学院 毛立强
lqmao@mail.xidian.edu.cn
例4 (a) P: 4 是质数。
  ? P: 4 不是质数。 或 4 是质数, 不是这样。 (b) Q:这些书都是刚刚出版的。 ?Q:这些书不都是刚刚出版的。(表示成“这些书都 不是刚刚出版的”是错误的)
西安电子科技大学计算机学院 毛立强
18
lqmao@mail.xidian.edu.cn
例5 在大多数编程语言中,“非”的定义和“否定”联结词定 义相同。例如在Java语言中,(逻辑)“非”记做!,表达 式 !(x<1
  00)为真当且仅当变量x不小于1
  00,也就是大于 等于1
  00。
西安电子科技大学计算机学院 毛立强
19
lqmao@mail.xidian.edu.cn

  2. 合取∧ 如 果 P 和 Q 是 命 题 , 那 么 “ P 并 且 Q” 是 一 个 复 合 命 题 , 记 做 P∧Q,称为P和Q的合取(conjunction)。当且仅当P、Q同时 为T时,P∧Q为T,否则,P∧Q为F。
P 0 0 1 1 Q 0 1 0 1
20
P ∧Q 0 0 0 1
西安电子科技大学计算机学院 毛立强
lqmao@mail.xidian.edu.cn
例 6 P: 王华的成绩很好, Q: 王华的品德很好。P∧Q: 王华的 成绩很好并且品德很好。 注意:“合取”与汉语中的“与”意义相近,但不完全相同。 如:P: 今天下雨, Q: 明天下雨。P∧Q: 今天和明天都下雨。 P: 我们去看电影, Q: 地球是圆的。P∧Q:我们去看电影并且 地球是圆的。 实际很少这样表达,但在数理逻辑中是允许的。
西安电子科技大学计算机学院 毛立强
21
lqmao@mail.xidian.edu.cn
例7 在大多数编程语言中,“与”的定义与“合取”定义相同。例 如Java语言中,(逻辑)“与”记做&&,表达式 x<10 && y>1 为 真当且仅当变量x小于10并且变量y大于
  1。
西安电子科技大学计算机学院 毛立强
22
lqmao@mail.xidian.edu.cn

  3. 析取∨ 如果P和Q是命题,那么“P或Q”是一个复合命题,记做P∨Q, 称为P和Q的析取(disjunction)。当且仅当P、Q至少有一个为T 时,P∨Q为T,否则,P∨Q为F。
P 0 0 1 1 Q 0 1 0 1
23
P∨Q 0 1 1 1 西安电子科技大学计算机学院 毛立强
lqmao@mail.xidian.edu.cn
例8 (a) P: 今晚我写字, Q: 今晚我看书。 P∨Q: 今晚我写字或看书 “或”字常见的含义有两种: 一种是“可兼或”, 如上例中的 或, 它不排除今晚既看书又写字这种情况。一种是“排斥或”, 例如“人固有一死, 或重于泰山, 或轻于鸿毛”中的“或”, 它表 示非此即彼, 不可兼得。 运算符∨表示可兼或, 排斥或以后 用另一符号表达。 (b)她今年30岁或者40岁。 表示近似,不能用“析取”联结词表达。
西安电子科技大学计算机学院 毛立强
24
lqmao@mail.xidian.edu.cn
例9 在大多数编程语言中,“兼或”的定义与析取定义相 同。例如Java语言中,(逻辑)“或”记做||,表达式 x<10 || y>1 为真当且仅当变量x小于10或者变量y大于1或者两者都 为真。
西安电子科技大学计算机学院 毛立强
25
lqmao@mail.xidian.edu.cn
例 10
Web搜 索 许多Web搜索引擎(如Google、
Yahoo)都允许用户输入关键词,然后由搜索引擎与网页进 行 匹 配 。 例 如 , 输 入 mathematics 会 产 生 一 个 包 含 mathematics的列表。有些搜索引擎允许用户使用操作符 AND、OR和NOT以及括号进行关键词的组合,这样可以实 现更复杂的搜索。例如,为了搜索包含关键词“discrete”和 “ mathematics” 的 网 页 , 用 户 应 该 输 入 discrete AND mathematics 。 如 果 搜 索 包 含 关 键 词 “ discrete” 和 “mathematics”或关键词“finite”和“mathematics”的网页,用 户应该输入(discrete OR finite)AND mathematics。
西安电子科技大学计算机学院 毛立强
26
lqmao@mail.xidian.edu.cn
 

相关内容

西安电子科技大学考研复试科目-离散数学01命题逻辑a

  西安电子科技大学计算机学院数 学 离 散毛立强 主讲西安电子科技大学计算机学院 毛立强1lqmao@mail.xidian.edu.cn课程信息教材:离散数学,方世昌,西电出版社 离散数学习题解答,孙学红,秦伟良,西电出版社参考书:离散数学,左孝凌等,上海科学技术文献出版社西安电子科技大学计算机学院 毛立强2lqmao@mail.xidian.edu.cn课程信息54学时,27次课 作业与辅导: 考试:闭卷,与平时成绩加权西安电子科技大学计算机学院 毛立强3lqmao@mail.xidian.e ...

西安电子科技大学考研复试科目-离散数学01命题逻辑e

  西安电子科技大学计算机学院数 学 离 散毛立强 主讲西安电子科技大学计算机学院 毛立强1lqmao@mail.xidian.edu.cn回顾对偶及对偶原理 范式:主合取范式和主析取范式及其求解西安电子科技大学计算机学院 毛立强2lqmao@mail.xidian.edu.cn在数学和其他自然科学中,经常要进行推理(reasoning), 即从某些前提出发,看能得到什么样的结论,其中有一些推 理,我们只需要分析这些前提的真值和它们之间的联结词,就 可以得到结论。在实际应用中,通常都是把某一学科中的 ...

西安电子科技大学考研复试科目-离散数学01命题逻辑d

  西安电子科技大学计算机学院数 学 离 散毛立强 主讲西安电子科技大学计算机学院 毛立强1lqmao@mail.xidian.edu.cn回顾命题公式的蕴含关系及其证明 联结词的扩充与归约西安电子科技大学计算机学院 毛立强2lqmao@mail.xidian.edu.cn对偶与范式定义 设有命题公式A, 其中仅有联结词∧, ∨, ?。在A中将∧, ∨分别换以∨, ∧ ,如果有常元F和T,也互相替换, 所得公式记为 A*,则A*称为A的对偶公式。 对A *采取同样方法, 又得A, 所以A也是A*的对 ...

西安电子科技大学考研复试科目-离散数学01命题逻辑c

  西安电子科技大学计算机学院数 学 离 散毛立强 主讲西安电子科技大学计算机学院 毛立强1lqmao@mail.xidian.edu.cn回顾 命题联结词:条件、双条件 命题公式及其翻译 重言式 命题公式的等价关系西安电子科技大学计算机学院 毛立强2lqmao@mail.xidian.edu.cn例1 证明在Java语言中,表达式 x<10 || x>20 和 !(x>=10 && x<=20) 是等价的。 证明 设P:x>=10,Q:x<=20 ...

西安电子科技大学考研复试科目-离散数学01命题逻辑b

  西安电子科技大学计算机学院数 学 离 散毛立强 主讲西安电子科技大学计算机学院 毛立强1lqmao@mail.xidian.edu.cn回顾:命题概念及其判断 命题联结词:否定、合取、析取西安电子科技大学计算机学院 毛立强2lqmao@mail.xidian.edu.cn4. 条件→ 如果P和Q是命题,那么“如果P,则Q”是一个复合命题,记做 P→Q ,称为P和Q的条件命题(conditional proposition)。当且仅 当P为T,Q为F时, P→Q为F,否则, P→Q为T。这里,称P ...

西安电子科技大学考研复试科目-离散数学05无限集合b-08图论a

  西安电子科技大学计算机学院数 学 离 散毛立强 主讲西安电子科技大学计算机学院 毛立强1lqmao@mail.xidian.edu.cn基数基数的概念 基数的比较西安电子科技大学计算机学院 毛立强2lqmao@mail.xidian.edu.cn基数的概念任一无限集合必与其某一真子集等势。 证明:设任一无限集合M,其必含有可数子集,设为A= {a1,a2,...,an,...},令B=M-A,可以定义集合M到其一个真子集 的函数f:M→M-{a1},使得f(an)=an+1 (n=1,2,…)且 ...

电子科技大学2011年研究生复试分数线公布

  电子科技大学 2011 年研究生复试分数线公布电子科技大学日前公布 2011 年硕士研究生入学考试初试成绩基 本要求,详情如下:根据教育部有关文件精神,结合我校实际情况,经校研究生招生 领导小组研究决定, 我校按照不同考试方式和不同学科分别确定初试 成绩基本要求。 各学院根据名额和考试成绩等情况确定本学院初试成 绩基本要求 (不低于学校基本要求) 并以此确定入围复试考生名单。 , 我校将按照德、智、体全面衡量、择优录取、保证质量、宁缺毋滥的 精神和公开、公正、公平的原则进行复试与录取工作。我校复 ...

杭州电子科技大学2011年硕士研究生复试笔试科目内容,专业、领域名称

  附件2 附件2: 领域名称序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40理学院 学院杭州电子科技大学专业、 领域 专业、领域名称 代码机械制造及其自动化 机械电子工程 机械设计及理论 机械工程领域 工业工程领域 国际贸易学 统计学 资产评估硕士 会计学 会计硕士 管理科学与工程 企业管理 旅游管理 技术经济及管理 工业 ...

电子科技大学2010新生指南

  【新生须知】 新生须知】 入学前准备: 新生入学后,学校将安排英语摸底考试,其中包括听力测试,请同学们做好复习准备。为更 好的了解学生招生相关信息,请填写《电子科技大学 2010 年新生报考情况调查表》 ,并在开 学后交所在学院年级辅导员报到: 新生报到时间:8月26日至8月27日;新生报到地点:电子科技大学清水河校区学生活动 中心 清水河校区地址:成都市高新西区西源大道2006号(邮编:611731) 新生报到必须携带以下证件和物品 a.录取通知书 b.身份证 c.本人中学学籍档案(由 省、市 ...

西安电子科技大学2011年硕士研究生招生计划

  西安电子科技大学2011 年硕士研究生招生专 业 目 录西安电子科技大学研究生招生办公室二○一?年七月招生简章一、培养目标 以学生为本,培养知识结构合理、政治思想坚定、具有国际视野和竞争能力、具有创新精神 的优秀人才是学校人才培养的目标。 报名及入学考试时间 二、报名及入学考试时间 网上报名时间一般安排在 10 月,考生登录中国研究生招生信息网,按网站的提示和要求如 实填写或修改本人报名信息。 现场确认报名时间一般安排在 11 月 10 日-14 日,具体安排请查阅西安电子科技大学研究生 招生信 ...

热门内容

高端白酒国际化竞争推动战略营销转型

  高端白酒:国际化竞争推动战略营销转型帝亚吉欧即将间接控股中国新兴高档白酒品牌水井坊(600779,股吧),可以预见,洋酒品 牌在中国市场还会有更大的营销投入和更广泛的战略布局, 面对竞争对手的全方位渗透, 中 国高端白酒品牌应该在哪些方面推动转型?2010 年 3 月 1 日,帝亚吉欧旗下全资子公司 DHHBV(Diageo Highlands Holding B.V.) 与成都盈盛投资控股有限公司签订了股权转让协议.如股权转让经过相关部门批准得以完 成,帝亚吉欧将持有全兴集团共 53\%的股权 ...

毕 业 论 文

  毕 业 论 文论文题目: 学生姓名: 学生学号: 系 专 别: 业: 女性旅游消费心理研 乔玉洁 05080129 经管系 旅游管理 王景山 称: 教授 2007 年 12 月 5 日 目 录指导教师: 职 日期:一、研究女性旅游消费者的心理意义. 1 (一)要树立关注女性旅游消费者心理需求的营销观念. 1 (二)研究女性旅游消费者心理活动对其购买行为的影响. 1 (三)要从女性旅游消费者心理感应的角度来塑造旅游产品的形象. 1 二、女性旅游消费者的心理分析. 2 (一)为什么要细心观察和了解女 ...

2011年中考作文热点23爱国篇

  2011 年中考作文热点(23) 爱国篇 年中考作文热点( ) :爱国篇 :【成语典故 成语典故】从民族英雄戚继光抗击倭寇,到郑成功勇逐荷兰殖民者光复台湾;从邓 成语典故 世昌勇撞日军旗舰,到三元里人民抗英斗争;从义和团抗击八国联军,到狼牙山五壮士抗 击日军,等等事迹,反映了中华民族爱国主义传统代代相承。从贾谊的“国而忘家,公而忘 私”,到范仲淹的“先天下之忧而忧,后天下之乐而乐”;从顾炎武的“天下兴亡,匹夫有责”, 到林则徐的“苟利国家生死以,岂因祸福避趋之”;从孙中山第一个喊出“振兴中华”, ...

精简版求职简历表格

  个 人 求 职 简 历姓名 年龄 所在城市 学历 婚姻状况 籍贯 毕业学校 姓名 家庭成员 性别 出生日期 从事行业 民族 身份证 户口所在地 计算机能力 成员关系 职务 工作单位工作时间 工作经历公司名称职位名称所属部门教育情况时间学校学历培训经历培训时间培训机构培训内容项目1、 2、 3、 4、 5、 6、 7、 注: 8 、项目经验开发其它项目9、 10、职业技能个 人 求 职 简 历语言 语言能力 水平个人荣誉自我评价相关证书手 联系方式机电子邮箱 QQ 号码个人主页 联系地址 ...

西北师范大学2008年普通专升本招生汉语言文学专业

  年普通专升本招生汉语言文学 汉语言文学专业 西北师范大学 2008 年普通专升本招生汉语言文学专业 考试大纲(试行) 一、考试目的 全面考核普通高校专科(含高职)应届毕业生汉语言文学核心课 程是否达到教学大纲所规定的目标。汉语言文学专业设置的核心课程 主要有:古代汉语、现代汉语、语言学概论、中国古代文学、中国现 当代文学、外国文学、文学理论、写作学。甘肃省普通高等学校专升本招生汉语言文学专业的考试,侧重考核古代汉语、现代汉语、中国古代文学史、中国现代文学四门课程的学习是否达到了教学大纲 所规定的 ...