递推公式及其求解
生成函数及应用
2014-6-15







Preface
知识点
图 与 树 无向图与有向图
树 生成树 遍历策略 欧拉回路与哈密顿回路
（6）
CS


CE


ห้องสมุดไป่ตู้SE


IT


代数 结构
数论
布尔代数
计算机工程中的逻辑应用 分解因式,素数性质 最大公约数最小公倍数 欧几里得算法 同余算术,中国剩余定理
2014-6-15
§1.1 Propositional Logic
The proposition p q is called the disjunction of p and q .
PQ truth table
(8)
P T T F F
2014-6-15
Q T F T F
PQ T T T F
2014-6-15
算法设计与分析、计算复杂性、编码
人工智能、形式语义学 数字电路设计、密码学、软件形式化方法
Chapter 1
The Foundations: Logic and Proof
2014-6-15
Seven Muddy children problem
2014-6-15
Seven Muddy children problem
离散数学成绩的评定
平时（10%）+ 闭卷笔试（90%）
About Mathematics
Mathematics and its Application? What is the Mathematics character?
2014-6-15
About Mathematics
阶 段 计算 对象 中学数学 数学分析 离散数学 形式语言与自动机
Actual situation: Ten students in a classroom,and seven students get mud on their foreheads. Teacher came into the classroom and said, 1 at least one of you has a muddy forehead. 2 Do you know whether you have a muddy forehead? Put up your hands if you know. 3 Teacher asked six times.no one put up his hands. 4 What happen when the seventh times. why?




2014-6-15
Preface
离散数学 集合 关系 其他专业课程
（7）
形式语言、编译技术、计算复杂性、软件形式化方法 关系数据库
函数
图 树
算法设计与分析、软件形式化方法
数据结构、网络技术、算法设计与分析、人工智能 数据结构、网络技术、算法设计与分析
计数技术
数理逻辑 代数结构
F
§1.1 Propositional Logic
（5）implication （conditional ）
(11)
Definition: Let p and q be arbitrary propositions. The implication pq is the compound proposition that is false when p is true and q is false, and is true otherwise.
2014-6-15
§1.1 Propositional Logic
1.1.2 Propositions
1.1.2.1 Proposition
(2)
A statement that contains no connectives is called a simple statement or an atomic statement ,or atomic proposition.
§1.1 Propositional Logic
（4）exclusive or
(9)
Definition: Let p and q be arbitrary propositions. The exclusive or of p and q , denoted by p q, is the compound proposition that is true when exactly one of p and q is true and is false otherwise.
2014-6-15



Preface
知识点
证 明 技 巧 命题逻辑推理系统 形式证明结构 证明方法：直接,反例,逆反式, 反证法,数学归纳法与强归 纳法 组合计数公式 二项式定理与组合恒等式 容斥原理
（5）
CS

CE

SE

IT

计 数 基 础


集合及其运算 关系及其性质 函数的满射、单射、复 合、求逆 鸽巢原理
基数和可数性



Preface
基 本 逻 辑 知识点 命题逻辑 CS CE SE
（4） IT
范式（合取式、析取式）
永真性
谓词逻辑 假言推理与否定式推理








谓词逻辑局限性
2014-6-15
§1.1 Propositional Logic
1.1.2 Propositions
1.1.2.2 Connectives and Compound Propositions
(3)
（1）negation
Definition:
Let p be an arbitrary proposition,the statement “It is not the case that p” is another proposition,called the negation of p.
教材：《Discrete Mathematics and Its Applications》 (英文Sixth Edition), Kenneth H.Rosen著，机械工业出版社；
《离散数学》，左孝凌著，上海科技文献出版社； 《离散数学》，耿素云、屈婉玲著，高等教育出版社； 《离散数学及其应用》，傅彦、顾小丰著，电子工业出版社； 《 Discrete Mathematical Structures》（ 英 文 Fourth Edition），B Kolman, Robert C. Busby, Sharon Ross著，高等教育出版社；
§1.1 Propositional Logic
（3）disjunction
(7)
Definition: Let p and q be arbitrary propositions. The proposition “p or q” denoted p q is the compound proposition that is false when both p and q are false and is true otherwise.
离散系统建模及性质分析
（2）
应用
数 论
代 数 结 构
函数 关系 集 合
树 图
计 数 技 术
离 散 概 率
概念 工具 方法 基础
证 明 技 巧 基 本 逻 辑
2014-6-15
Preface
知识点 函 数 关 系 集 合
2014-6-15
（3） CS CE SE IT
2014-6-15
§1.1 Propositional Logic
（1）negation
(4)
The negation of p is denoted by p. The proposition p is read “not p”.
Truth Table
P T F
P F T
2014-6-15
(13) p 蕴含 q p 仅当 q q 的充分条件是 p q 每当 p q 是 p 的必要 条件 q 是从 p 中推 出
p is sufficient p 是 q 的充分 for q 条件 q if p q when p a necessary condition for p is q
2014-6-15
2014-6-15
§1.1 Propositional Logic
The proposition p q is called the conjunction of p and q .
PQ truth table
(6)
P T T F F
Q T F T F
PQ T F F F
2014-6-15
.
PQ truth table
P T T F F
2014-6-15
Q T F T F
PQ T F T T
§1.1 Propositional Logic
If p,then q If p,q 如果 p，那么 q 如果 p，则 q p implies q p only if q a sufficient condition for q is p q whenever p q is necessary for p q follows from p
Discrete structures