离散数学复习笔记¶
信息安全原理与数学基础 — 离散数学部分 考试大纲与复习笔记
考试大纲¶
- 命题逻辑 - 逻辑联接词集功能完备性 - 真值表 - 逻辑等价式、逻辑蕴涵式 - 代入原理、替换原理 - （主）合取范式、（主）析取范式
- 谓词逻辑 - 谓词演算的永真式
- 公理化集合论 - 集合基本运算、归纳定义、有序组、笛卡尔积 - 关系、关系矩阵、函数 - 等价关系、等价类、划分 - 序关系、哈斯图
- 图论 - 图的同构、欧拉图、哈密尔顿图 - 二分图、匹配算法
- 抽象代数 - 代数结构、同态 - 群、环、域
- 语言分析 - 有限状态自动机 - 图灵机、停机问题
Lec 4: 前置知识¶
1. 命题 (Proposition)¶
- 定义：对确定的对象作出判断的陈述句
- 悖论（自相矛盾）不能作为命题
- 命题非真即假，不能兼有之，也不能不真不假
- 真值：
- 真（true）用 1 表示
- 假（false）用 0 表示
排中律¶
任一事物在同一时间里具有某属性或者不具有某种属性，而无其他可能。只适用于有限事物，不能推广到无穷事物。
- 原子命题（atom proposition）：不含有逻辑联结词的命题
- 复合命题（compound proposition）：包含了原子命题和逻辑联结词的命题
2. 逻辑联结词 (Logical Connectives)¶
连接命题，对真值进行运算的词：
| 逻辑词 | 说明 | 符号 | 优先级 |
|---|---|---|---|
| 否定词 (negation) | 非 (not) | \(\lnot\) | 1 |
| 合取词 (conjunction) | 并且 (and) | \(\land\) | 2 |
| 析取词 (disjunction) | 或 (or) | \(\lor\) | 2 |
| 蕴涵词 (implication) | 如果…那么… (if…then…) | \(\to\) | 3 |
| 双向蕴涵词 (two-way implication) | 当且仅当 (iff) | \(\leftrightarrow\) | 4 |
- 只有 \(p\) 为真且 \(q\) 为假时，\(p \to q\) 才为假
- 在 \(p\) 和 \(q\) 的真值相同时，\(p \leftrightarrow q\) 为真
3. 命题公式 (Proposition Formula)¶
3.1 基本概念¶
- 命题常元（proposition constants）：由真值 T、F 和表示具体命题的 \(p,q,r,s\) 等组成
- 命题变元（proposition variables）：以 1、0 为取值范围的变量，也用 \(p,q,r,s\) 等表示
- 命题公式（proposition formula）：由命题常元、变元和联结词组成的形式更为复杂的命题
- 命题常元和命题变元是命题公式，称作原子公式
- 如果 \(A,B\) 是命题公式，那么 \(\lnot A, A\land B, A\lor B, A\to B, A\leftrightarrow B\) 也是命题公式
- 只有有限步引用上述两条所组成的符号串是命题公式
3.2 成真赋值和成假赋值¶
- 公式 \(A\) 对赋值 \(\alpha\) 为真 \(\to\) \(\alpha\) 是 \(A\) 的成真赋值，记作 \(\alpha(A) = 1\)
- 公式 \(A\) 对赋值 \(\alpha\) 为假 \(\to\) \(\alpha\) 是 \(A\) 的成假赋值，记作 \(\alpha(A) = 0\)
3.3 公式分类¶
| 类型 | 定义 |
|---|---|
| 重言式/永真式 (tautology) | 所有赋值都是成真赋值 |
| 矛盾式/永假式 (contradiction) | 所有赋值都是成假赋值 |
| 可满足式 (contingency) | 至少有一个成真赋值 |