【例1.4】 • 在香港购物可以用港币 或人民币支付。 • 他是中国籍或美国籍。 • 他只能是中国籍或美国 籍。
排斥或 p 0 0 1 1 q 0 1 (p∧¬ q)∨(¬ p∧q)
蕴涵（条件）联结词 implication
表1.4 p 0 0 1 1 q 0 1 0 1 p→q 1 1 0 1
——
第一章 命题逻辑 基本概念
1.1 1.2 命题与联结词 命题公式及其赋值
1.1
命题与联结词
如果火车晚点，而且车站没有出租车，那 么John 参加会议就会迟到。 逻辑研究推理的规律 John没有迟到，火车的确是晚点了。 推理由一系列的陈述句组成 因此，车站有出租车。
If the train arrives late and there are no taxis at the station, then John is late for his meeting. John is not late for his meeting. The train did arrive late. Therefore, there were taxis at the station.
定义1.2 • 设p和q均为命题，则p和q的合取式是一 个复合命题，记作p∧q，读作“p与q” 或“p合取q”。 • 当且仅当p和q均为1时，p∧q的才为1。 • 联结词“∧”也是逻辑运算，它是二元 逻辑运算。
p 0 0 1 1
表1.2 q p∧q 0 0 1 0 0 0 1 1
合取联结词与自然语言的对应
• 天下皆知美之为美也，恶已；皆知善，此其 不善已。有无相生；难易相成；长短相较； 高下相倾；音声相和；先后相随。是以圣人 居无为之事，行不言不教„„
《道德经》
以二元论为基础的逻辑是有局限的。
复杂的命题
【例1.1C】 复杂的命题： • （1）4是偶数且是2的倍数。 • （2）北京不是个小城市。 • （3）小王或小李考试得第一。 • （4）如果你努力，则你能成功。 • （5）三角形是等边三角形，当且仅当 三内角相等。
这门课的内容
数理逻辑 集合论 代数结构（抽象代数） 组合数学 图论 初等数论
这门课的考核
• 平时成绩 • 期末考试 • 优秀率 • 不及格率 • 重修的及格率 10分 90分 15％左右 15％
23％
学习方法
内容覆盖广 概念抽象
仔细阅读教材
深入思考
认真练习
坚持
自主
交流
第一部分 数理逻辑
进入20世纪，数理逻辑得到快速发展 源于20世纪最伟大的数学家希尔伯特 （David Hilbert，1862-1943）倡导的
数学的公理化运动
哥德尔（Kurt Godel, 1906-1978）是 亚理士多德和莱布尼兹以来最伟大的逻 辑学家
数理逻辑与计算机科学
• 程序 ＝ 算法＋数据 • 算法 ＝ 逻辑＋控制
“任何科学都需要思维，逻辑是思维的规范，推理是思维的 法则。” (陆汝钤，1996)
数理逻辑与计算机科学
• 假如我早年在数理逻辑上下点功夫，就不会 出那么多错误，不少东西数理逻辑上早就讲 过了； • 假如我年轻20岁，一定回去学数理逻辑。 1972年图灵奖得主、荷兰计算机学家 Dijkstra （迪克斯特拉）
Discrete Mathematics and Its Application
教材与参考书
• 《离散数学》
屈婉玲、耿素云、张立昂编著 高等教育出版社，2008年
教材与参考书
• 《离散数学学习指导与习题解析》
屈婉玲、耿素云、张立昂 高等教育出版社
这门课的作用
• 计算机相关的专业基础课 • 培养逻辑思维和分析、解决 问题能力 • 后续课程的基础 • 培养数学素养
联结词的符号化
• 联结词： ¬，∧，∨，→，↔ • 复合命题： p∧q， p∨q
形式语言
不同于自然语言， 这些符号的含义需要严格定义
否定(negation ) 联结词
表1.1 p 0 ¬p 1
定义1.1 • 设p为任一命题，复合命题“非p” （p的否定）称为p的否定式，记作 ¬p。 • ¬为否定联结词。¬p为真，当且仅当 p为假。 • 联结词“¬”也是逻辑运算，它是一 元运算。
（假命题） （真命题）
真值未知，但惟一
不是命题的例子
【例1.1B】 下列语句不是命题： • （1）好棒啊！ • （2）你好吗？ 真值不定 • （3）请勿吸烟。 • （ 4） x＞3 （命题变元） • （5）x大于y，其中x和y是任意的两个数。 • （6）我正在说谎。（说谎者悖论） 二分法，出现矛盾
二元论、二分法与二进制
• 认识世界的方法论：阴与阳、正与反、 天与地、物质与精神 • 易有太极，是生两仪，两仪生四象，四 象生八卦 • 谋略思想：奇正、虚实 • 人生哲学：进退、取舍、加减 • 现代计算的基础
• 道可道，非常道。名可名，非常名。无名， 万物之始也；有名，万物之母也。„„此二 者，同出而异名，同谓之玄，玄之又玄，众 妙之门。 • 道生一，一生二，二生三，三生万物
构造性（结构化）方法
• 简单命题（原子命题） 简单陈述句，不能分解
atomic or indecomposable
• 复合命题 原子命题通过联结词联结而 成的命题
符号化（symbolic）方法
• 命题： 用p、q、r、pi、qi、ri等符号表示 • 真值： “1”表示真，“0”表示假
如 p：4是偶数。 p的真值为1。 q：煤是白的。 r：《几何原本》的作者是欧几里德。
定义1.4 • 设p和q均为命题，则p和q的蕴涵式是一个复合 命题，记作p→q ，读作“如果p，则q”。 • p为前件（antecedent）； • q为后件（consequent）。 • 当且仅当p为1和q为0时， p→q的才为0。 • p为q的充分条件，q为p的必要条件。
蕴涵定义的合理性
【例1.5A】 • 商家承诺：7日内，包退保换
• • • •
诚信 不诚信 诚信 诚信
1 1 0 0
1 0 1 0
蕴涵定义的合理性
• 【例1.5B】 • 同学约定：再过20年，同学再相会
• • • •
可信 不可信 可信 可信
1 1 0 0
1 0 1 0
蕴涵联结词与自然语言的对应
• p→q的逻辑关系是：p是q的充分条件，q是p 的必要条件。 • 存在不同的叙述方式： • p仅当q（仅当q，则p） • 只有q才p • 只要p，就q • 除非q，否则非p（除非q，则p） • 非p，除非q • 因为p，所以q
Mathematical Logics
@ 命题逻辑
基本概念 等值演算 推理
Propositional Logic
@ 谓词逻辑
基本概念 等值演算 推理
Predicate Logic
什么是数理逻辑？
• 研究推理的数学分支 • 研究“数学思维”的数学模型 • 逻辑的数学化、数学的逻辑化
什么是逻辑？
• 逻辑（Logics）是关于推理的科学 • 研究思维形式及其规律 • 包括形式逻辑与辩证逻辑 • 概念、判断、推理是思维的基本形式
这门课的特点
• 研究离散量的结构 及其相互关系的学科 • 离散——连续 有限——无穷
马致远 《天净沙· 秋思》 李煜 《虞美人》 春花秋月何时了，往事知多少。 小楼昨夜又东风，故国不堪回首 月明中。 雕栏玉砌应犹在，只是朱颜改。 问君能有几多愁，恰似一江春水 向东流。
枯藤．老树．昏鸦， 小桥．流水．人家， 古道．西风．瘦马， 夕阳西下． 断肠人在天涯。
符号化方法与形式语言
• 命题： 用p、q、r、pi、qi、ri等符号表示 如果火车晚点，而且车站没有出租车， 那么John参加会议就会迟到。 John没有迟到，火车的确是晚点了。 因此，车站有出租车。
半形式化： If p and not q, then r. Not r. p. Therefore, q.
Logic has been called “the calculus of computer science” Logic plays a similar role in computer science to that played by calculus in the physical sciences and traditional engineering disciplines. (M. Vardi, 2007)
蕴涵定义的例子
【例1.6】符号化命题 • （1）只要天下雨，我就回家。 • （2）只有天下雨，我才回家。 • （3）除非天下雨，否则我不回家。 • （4）仅当天下雨，我才回家。
解 设p：天下雨。q：我回家。 p是充分条件： p→q p是必要条件： q→p
练习
符号化命题
（1）他们每天通电话，除非发生意外。 （2）他每天都练功，除非是大年初一。 （3）只要别人有困难，老王就帮助别 人，除非困难解决了。 （4）要想人不知，除非己莫为。
逻辑学的发展
• 二千年前的古希腊、中国、印度， 逻辑已非常发达
• 亚理士多德（Aristotle，B.C. 384-B.C. 322）提出“演绎法”， 形式逻辑的开山鼻祖
逻辑学的发展 ——数理逻辑
• 1666年，莱布尼兹 （Gottfried Wilhelm von Leibniz， 1646-1716） 发明了一套逻辑运算符号， 创建了数理逻辑
1
0
否定联结词与自然语言的对应
【例1.2】 • (1)p： 4是偶数。 其真值为1。 • ¬p ：4不是偶数。其真值为0。 • (2)q： 这些都是学生。 • ¬q ：这些不都是学生。 • 一般地，自然语言中的“不”、“无 ”、“没有”、“并非”等词均可符 号化为“否定联结词”
合取(conjunction) 联结词