前言
离散数学课程的主要内容：
- 基础：逻辑和证明
- 基本结构（包括集合、函数、序列、求和与矩阵）
- 计数
- 高级计数
- 关系
- 图
- 树
- 布尔代数
学习该课程的目的：
- 为学习计算机后继课程，如数据结构、编译原理、操作系统、数据库原理、形式语言及自动机。软件工程与方法学、计算机网络和人工智能、高级程序设计语言等，提供必要的数据基础；为阅读计算机文章作充分的数学准备
数理逻辑：人工智能、数据库、形式语言及自动机、高级程序设计语言
集合论：信息结构与检索、数据结构
布尔代数等：开关理论、逻辑设计和程序理论、语法分析
图论：可计算性理论、计算机网络、数据结构
- 通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，获得解决实际问题的能力，为以后的软、硬学习和研究开发工作，打下坚实的数学基础。
基础：逻辑和证明
命题逻辑
摘要
- 命题
- 联结词
- 否定联结词
- 合取联结词
- 析取联结词
- 条件语句：逆命题、逆否命题、反命题
- 双条件语句
- 真值表
命题
- 命题：是一个陈述句（即陈述事实的语句），它或者或假，但不能既真又假。即：命题是能够判断真假的陈述句。
- 原子命题：不能分解为更简单的陈述句
说明：
只有具有确定真值得陈述句才是命题。
一切没有判断内容的句子，无所谓是非的句子，如：祈使句、感叹句、疑问句等都不是命题
因为命题只有两种真值，所以“命题逻辑”又称“二值逻辑”
“具有确定真值”是指客观上的具有，有我们是否知道它的真值是两回事
比如：其他星球上有生命
命题逻辑
命题构造
- 命题变元：p，q，r，s……
- 一个命题是真命题，用T表示
- 一个命题是加盟命题，用F表示
- 复合命题：由原子命题用逻辑运算符组合而来
- 否定联结词：┐
- 合取联结词：∧
- 析取联结词：∨
- or 联结词：⊕
- 条件联结词：→
- 双条件联结词：↔
复合命题——联结词
否定联结词（逻辑非）
令p为一命题，则p的否定记作┐p
p ┐p T F F T 合取联结词（逻辑与）
令p和q为命题，p、q的合取记作p∧q
p q p∧q T T T T F F F T F F F F 析取联结词（逻辑或）
令p和q为命题，p、q的析取记作p∨q
p q pVq T T T T F T F T T F F F 联结词 or （or有两种不同的含义）
兼或（inclusive or）
例如：修过计算机科学或高数的学生可以修这门课
这就是析取的含义，p v q为真，只要两个命题之一为真或两者均为真即可。
异或（exclusive or）【相异为真】
例如：套餐含汤或饮料
这就是异或（XOR）的含义。p⊕q为真，则两个命题只有一个为真，但不能同事为真
两个命题异或的真值表
p q p⊕q T T F T F T F T T F F F 条件联结词（如果p，则q）
p（前件） q（后件） p→q T T T T F F F T T F F T 前提条件为假，结果必为真。例如：
- 如果月亮是绿色奶酪做的，我比比尔盖茨更有钱
- 如果月亮是绿色奶酪做的，那么我就得靠救济生活
- 如果1+1=3，那么猪会飞。
在条件语句p→q中，在前件之间不需要有任何联系。p→q只依赖于p和q的真值
逆命题、逆否命题、反命题
- q→p 是p→q的逆命题
- ┐q→┐p 是p→q的逆否命题
- ┐p→┐q 是p→q的反命题
双条件联结词【相同为真】（与异或相反）
p q p↔q T T T T F F F T F F F T 双条件的表达方式
- p是q的充分必要条件
- 如果p那么q，反之亦然
- p当且仅当q
等价命题
如果两个命题总是有相同的真值，他们就是等价的
例：用真值表说明条件语句等价于逆否命题
| p | q | ┐p | ┐q | p→q | ┐q→┐p |
|---|---|---|---|---|---|
| T | T | F | F | T | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
问题：有n个命题变元的真值表有多少行
解：2^n。我们可以构造的命题数量（不相等）为2^2^n个
优先级
| Operator | Precedence |
|---|---|
| ┐ | 1 |
| ∧ | 2 |
| ∨ | 3 |
| → | 4 |
| ↔ | 5 |
命题逻辑的应用
摘要
- 语句翻译
- 系统规范说明
- 布尔搜索
- 逻辑谜题
- 逻辑电路
语句翻译
汉语常有二义性，为了在数学上避免歧义，需要翻译成由命题变量和逻辑联结词组成的表达式
如何翻译成正确的命题公式
命题演算的合式公式Wff