离散数学笔记（1）——命题逻辑（1）

wzf2000
2019年9月10日

离散数学笔记（1）——命题逻辑（1）

命题逻辑

命题

非真即假，不可兼（$T/F$）

原子命题与复合命题

复合命题 = 原子命题 + 联结词

一些对应的真值

命题公式

命题常量即命题

命题变元：用大写英文字母表示任何命题，称这些字母为命题变元

对命题变元作指派(给命题变元一个解释)：将一个常值命题赋予命题变元的过程，或者是直接赋给命题变元真值 $T$ 或 $F$ 的过程。

合式公式

(1)单个命题变元是个合式公式。

(2)若 $A$ 是合式公式，则 $\lnot A$ 是合式公式。

(3)若 $A$ 和 $B$ 是合式公式，则 $(A \land B)$，$(A \lor B)$，$(A \rightarrow B)$ 和 $(A \leftrightarrow B)$ 都是合式公式。

(4)当且仅当有限次地应用(1)，(2)，(3)所得到的含有命题变元、联结词和括号的符号串是合式公式。

运算次序优先级：$\lnot , \land , \lor , \rightarrow , \leftrightarrow$

相同的运算符按从左至右次序计算，否则要加上括号，括号最外层圆括号可省去。

命题符号化（翻译）

所谓命题符号化，就是用命题公式的符号串来表示给定的命题。

命题符号化的方法：

1. 明确给定命题的含义。

2. 对复合命题，找联结词，分解出各个原子命题。

3. 设原子命题符号，并用逻辑联结词联结原子命题符号，构成给定命题的符号表达式。

重言式（永真式）与矛盾式（永假式）

不论对 $P_1,\cdots,P_n$ 做任何指派，一个命题公式都是真（假），就称为重言式（矛盾式）。

若 $A$ 是永真式，则 $A$ 的置换式也是永真式。

置换式：用合式公式代替 $P_i$ 得到的新的命题公式。

等价公式

不论对 $P_1,\cdots,P_n$ 做任何指派，两个命题公式 $A$ 和 $B$ 真值总是相同，那么称 $A$ 和 $B$ 是逻辑等价，记为 $A=B$ 或者 $A \Leftrightarrow B$。

等价定理：$A \Leftrightarrow B$ 当且仅当 $A \leftrightarrow B$ 为永真式。

常见等价公式：略

$P \rightarrow Q \Leftrightarrow \lnot P \lor Q$

$P \rightarrow Q \Leftrightarrow \lnot Q \rightarrow \lnot P$

$P \leftrightarrow Q \Leftrightarrow (P \rightarrow Q) \land (Q \rightarrow P)$

置换定律：等价的置换还等价

重言蕴涵式

重言式 $A \rightarrow B$ 是个永真式，则称 $A$ 永真蕴涵 $B$，记作 $A \Rightarrow B$。

证明 $1$：假设前件为真，推出后件为真。

证明 $2$：假设后件为假，推出前件为假。

 离散数学 笔记