离散数学笔记
离散数学个人笔记
1.命题逻辑
1.1 概念
命题：具有唯一真值的陈述句
原子命题：不可分解的命题
复合命题：命题可以分解。原子命题+逻辑联结词
1.2 联结词
| 名称 | 符号 | 定义规则 | 真值表 |
|---|---|---|---|
| 否定 | ¬ | 否定一个命题 (p)，即将其真假值取反。 | | (p) | ¬(p) | | T | F | | F | T | |
| 合取 | ∧ | (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) | | T | T | T | | T | F | T | | F | T | T | | F | F | F | |
| 蕴含 | → | (p → q) 表示“如果 (p)，那么 (q)”。只有当 (p) 为真且 (q) 为假时为假。 | | (p) | (q) | (p → q) | | T | T | T | | T | F | F | | F | T | 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 | T | |
| 异或 | ⊕ | (p ⊕ q) 表示“(p) 和 (q) 的真假值不同”。 | | (p) | (q) | (p ⊕ q) | | T | T | F | | T | F | T | | F | T | T | | F | F | F | |
1.3 公式
成真指派：若指定的一种指派使假题的值为真，则称这组值为命题的成真指派
成假指派：若指定的一种指派使命题的值为假，则称这组值为命题的成假指派
公式类型：永真式（重言式）、可满足式、永假式（矛盾式）
1.4 逻辑等值演算
以下是离散数学中基本等值式的内容，使用 Markdown 格式编写。等值式在命题逻辑中非常重要，用于简化逻辑表达式或证明逻辑等价。
基本等值式
在离散数学中，基本等值式定义了逻辑运算之间的关系。这些等值式通过运算性质展示命题之间的逻辑等价，是逻辑推理和运算简化的基础。
1. 双重否定律 (Double Negation Law)
[
\neg(\neg p) \equiv p
]
否定一个命题两次后，结果与原命题相等。
2. 幺元律 (Identity Law)
[
p \land \text{True} \equiv p
]
[
p \lor \text{False} \equiv p
]
- "与 True 合取"等于原命题。
- "与 False 析取"等于原命题。
3. 零元律 (Domination Law)
[
p \land \text{False} \equiv \text{False}
]
[
p \lor \text{True} \equiv \text{True}
]
- "与 False 合取"永远为 False。
- "与 True 析取"永远为 True。
4. 交换律 (Commutative Law)
[
p \land q \equiv q \land p
]
[
p \lor q \equiv q \lor p
]
逻辑运算中的合取（(\land)）和析取（(\lor)）是可交换的。
5. 结合律 (Associative Law)
[
(p \land q) \land r \equiv p \land (q \land r)
]
[
(p \lor q) \lor r \equiv p \lor (q \lor r)
]
逻辑运算的合取和析取可以改变括号的分组顺序而不影响结果。
6. 分配律 (Distributive Law)
[
p \land (q \lor r) \equiv (p \land q) \lor (p \land r)
]
[
p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)
]
类似于代数中的分配律，逻辑合取和析取运算可以分配。
7. 吸收律 (Absorption Law)
[
p \lor (p \land q) \equiv p
]
[
p \land (p \lor q) \equiv p
]
通过吸收操作简化表达式。
8. 德摩根律 (De Morgan's Laws)
[
\neg(p \land q) \equiv (\neg p) \lor (\neg q)
]
[
\neg(p \lor q) \equiv (\neg p) \land (\neg q)
]
否定合取等于否定两个命题并通过析取连接，否定析取等于否定两个命题并通过合取连接。
9. 双条件定义 (Biconditional Definition)
[
p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)
]
一个双条件等于两个命题均为真或均为假的情况。
10. 蕴含定义 (Implication Definition)
[
p \to q \equiv \neg p \lor q
]
(p \to q) 表示 "如果 (p)，则 (q)"，其等价于"(\neg p) 或 (q)"。
总结
基本等值式是逻辑代数的核心部分，帮助我们简化复杂的逻辑表达式。以下是一些重要的等值式：
- 双重否定律
- 幺元律
- 零元律
- 交换律
- 结合律
- 分配律
- 吸收律
- 德摩根律
- 双条件定义
- 蕴含定义
通过这些等值式，可以高效地进行逻辑推导、化简或证明。
Markdown 代码示例
以下是上述内容的 Markdown 格式代码：
# **基本等值式**
在离散数学中，基本等值式定义了逻辑运算之间的关系。这些等值式通过运算性质展示命题之间的逻辑等价，是逻辑推理和运算简化的基础。
---
## **1. 双重否定律 (Double Negation Law)**
\[
\neg(\neg p) \equiv p
\]
否定一个命题两次后，结果与原命题相等。
---
## **2. 幺元律 (Identity Law)**
\[
p \land \text{True} \equiv p
\]
\[
p \lor \text{False} \equiv p
\]
- "与 True 合取"等于原命题。
- "与 False 析取"等于原命题。
---
## **3. 零元律 (Domination Law)**
\[
p \land \text{False} \equiv \text{False}
\]
\[
p \lor \text{True} \equiv \text{True}
\]
- "与 False 合取"永远为 False。
- "与 True 析取"永远为 True。
---
## **4. 交换律 (Commutative Law)**
\[
p \land q \equiv q \land p
\]
\[
p \lor q \equiv q \lor p
\]
逻辑运算中的合取（\(\land\)）和析取（\(\lor\)）是可交换的。
---
## **5. 结合律 (Associative Law)**
\[
(p \land q) \land r \equiv p \land (q \land r)
\]
\[
(p \lor q) \lor r \equiv p \lor (q \lor r)
\]
逻辑运算的合取和析取可以改变括号的分组顺序而不影响结果。
---
## **6. 分配律 (Distributive Law)**
\[
p \land (q \lor r) \equiv (p \land q) \lor (p \land r)
\]
\[
p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)
\]
类似于代数中的分配律，逻辑合取和析取运算可以分配。
---
## **7. 吸收律 (Absorption Law)**
\[
p \lor (p \land q) \equiv p
\]
\[
p \land (p \lor q) \equiv p
\]
通过吸收操作简化表达式。
---
## **8. 德摩根律 (De Morgan's Laws)**
\[
\neg(p \land q) \equiv (\neg p) \lor (\neg q)
\]
\[
\neg(p \lor q) \equiv (\neg p) \land (\neg q)
\]
否定合取等于否定两个命题并通过析取连接，否定析取等于否定两个命题并通过合取连接。
---
## **9. 双条件定义 (Biconditional Definition)**
\[
p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)
\]
一个双条件等于两个命题均为真或均为假的情况。
---
**蕴含定义**
\[
p \to q \equiv \neg p \lor q
\]
\(p \to q\) 表示 "如果 \(p\)，则 \(q\)"，其等价于"\(\neg p\) 或 \(q\)"。
## 2.谓词逻辑
## 3.集合与关系
## 4.函数
## 5.图
## 6.树
## 7.代数系统