命题逻辑的基本概念¶
命题是一个非真即假的陈述句。
- 命题不可能非真非假，也不可能既真又假
- 命题的真假性可以待定
命题的真假可以用True或False表示，也可以用1或0表示
命题可以通过与、或、非等逻辑联结词连接，得到复合命题
当不指定命题的具体内容时，称该命题为命题变项，对应的具体命题称为该命题变项的一个解释。命题变项的解释可以是任意命题。
逻辑联结词¶
命题逻辑中常用的逻辑联结词为与（\(\land\)，合取）、或（\(\lor\)，析取）、非（\(\lnot\)，否定）、蕴含（\(\rightarrow\)）、双蕴含（\(\leftrightarrow\)）等。除\(\lnot\)为一元运算符以外，其余逻辑运算符均为二元运算符。这些运算符的真值表如下所列：
- 与
| \(P\) | \(Q\) | \(P\land Q\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
- 或
| \(P\) | \(Q\) | \(P\lor Q\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
- 非
| \(P\) | \(\lnot P\) |
|---|---|
| 0 | 1 |
| 1 | 0 |
- 蕴含
| \(P\) | \(Q\) | \(P\rightarrow Q\) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
- 双蕴含
| \(P\) | \(Q\) | \(P\leftrightarrow Q\) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
此外，如下逻辑联结词也较为常用：
- 与非：\(A\uparrow B = \lnot (A\land B)\)
- 或非：\(A\downarrow B = \lnot (A\lor B)\)
- 异或：\(A\overline \lor B = (A\lor B)\land (\lnot A\lor \lnot B)\)
合式公式¶
合式公式（简称公式）按照如下规则定义如下：
- 简单命题是合式公式
- 若\(A\)为合式公式，\(\lnot A\)为合式公式
- 若\(A, B\)为合式公式，\(A\land B, A\lor B, A\rightarrow B, A\leftrightarrow B\)均为合式公式
- 当且仅当经过有限次应用前三条规则所得到的公式称为合式公式
合式公式中运算符的优先级排列如下：
\[
\lnot > \land > \lor > \rightarrow > \leftrightarrow
\]
如果合式公式中的所有命题变项在任意解释下都为真，称合式公式为重言式或永真式。如果合式公式在某个解释下为真，称合式公式可满足。如果合式公式中的所有命题变项在任意解释下都为假，称合式公式为矛盾式或永假式。两个重言式使用\(\land, \lor, \rightarrow, \leftrightarrow\)连接后得到的合式公式仍为重言式。
重言式的代入规则¶
若\(A\)为重言式，将\(A\)中的所有命题变项\(C\)替换为合式公式\(D\)，则替换后的合式公式仍为重言式。记作\(\frac CD\)
- 代入规则只能对公式中的命题变项进行替代，而不能替代公式中的一个复合命题
- 对公式中的某个命题变项进行代入时，必须代入公式中出现的所有命题变项