命题逻辑等值演算 ¶

等值式 ¶

等值式的定义 ¶

设 \(A\)、\(B\) 为两个命题公式，若 \(A\) 和 \(B\) 构成的等价式 \(A \leftrightarrow B\) 为重言式，则称 \(A\) 和 \(B\) 等值，记作 \(A \Leftrightarrow B\)。

常见等值式 ¶

双重否定律

\[ P \Leftrightarrow \neg \neg P \]
幂等律

\[ P \Leftrightarrow P \wedge P \]

\[ P \Leftrightarrow P \vee P \]
交换律

\[ P \wedge Q \Leftrightarrow Q \wedge P \]

\[ P \vee Q \Leftrightarrow Q \vee P \]
结合律

\[ (P \wedge Q) \wedge R \Leftrightarrow P \wedge (Q \wedge R) \]

\[ (P \vee Q) \vee R \Leftrightarrow P \vee (Q \vee R) \]
分配律

\(\vee\) 对 \(\wedge\) 分配:

\[ P \wedge (Q \vee R) \Leftrightarrow (P \wedge Q) \vee (P \wedge R) \]

\(\wedge\) 对 \(\vee\) 分配:

\[ P \vee (Q \wedge R) \Leftrightarrow (P \vee Q) \wedge (P \vee R) \]
德摩根律

\[ \neg (P \wedge Q) \Leftrightarrow \neg P \vee \neg Q \]

\[ \neg (P \vee Q) \Leftrightarrow \neg P \wedge \neg Q \]
吸收律

\[ P \wedge (P \vee Q) \Leftrightarrow P \]

\[ P \vee (P \wedge Q) \Leftrightarrow P \]
零律

\[ P \wedge \bot \Leftrightarrow \bot \]

\[ P \vee \top \Leftrightarrow \top \]
同一律

\[ P \wedge \top \Leftrightarrow P \]

\[ P \vee \bot \Leftrightarrow P \]
排中律

\[ P \vee \neg P \Leftrightarrow \top \]
矛盾律

\[ P \wedge \neg P \Leftrightarrow \bot \]
蕴含等值式

\[ P \rightarrow Q \Leftrightarrow \neg P \vee Q \]
等价等值式

\[ P \leftrightarrow Q \Leftrightarrow (P \rightarrow Q) \wedge (Q \rightarrow P) \]
假言易位

\[ P \rightarrow Q \Leftrightarrow \neg Q \rightarrow \neg P \]
等价否定等值式

\[ P \leftrightarrow Q \Leftrightarrow \neg P \leftrightarrow \neg Q \]
归谬论

\[ (P \rightarrow Q) \wedge (P \rightarrow \neg Q) \Leftrightarrow \neg P \]

范式 ¶

析取范式与合取范式 ¶

文字: 命题变元及其否定
简单析取式: 由有限个文字构成的析取式，如 \(P \vee Q \vee \neg R\)
简单合取式: 由有限个文字构成的合取式，如 \(P \wedge Q \wedge \neg R\)
析取范式: 由有限个简单合取式构成的析取式，如 \((P \wedge Q \wedge \neg R) \vee (R \wedge \neg S)\)
合取范式: 由有限个简单析取式构成的合取式，如 \((P \vee Q \vee \neg R) \wedge (R \vee \neg S)\)

主合取范式与主析取范式 ¶

极小项
- 首先是一个简单合取式
- 每个命题变元及其否定在该合取式中只出现一次
- 命题变元或其否定按照下标递增排列
极大项
- 首先是一个简单析取式
- 同极小项

含 \(p, q\) 的极小项与极大项

极小项			极大项
公式	成真赋值	名称	公式	成假赋值	名称
\(\neg p \wedge \neg q\)	\(0\) \(0\)	\(m_0\)	\(p \vee q\)	\(0\) \(0\)	\(M_0\)
\(\neg p \wedge q\)	\(0\) \(1\)	\(m_1\)	\(p \vee \neg q\)	\(0\) \(1\)	\(M_1\)
\(p \wedge \neg q\)	\(1\) \(0\)	\(m_2\)	\(\neg p \vee q\)	\(1\) \(0\)	\(M_2\)
\(p \wedge q\)	\(1\) \(1\)	\(m_3\)	\(\neg p \vee \neg q\)	\(1\) \(1\)	\(M_3\)

含 \(p, q, r\) 的极小项与极大项

极小项			极大项
公式	成真赋值	名称	公式	成假赋值	名称
\(\neg p \wedge \neg q \wedge \neg r\)	\(0\) \(0\) \(0\)	\(m_0\)	\(p \vee q \vee r\)	\(0\) \(0\) \(0\)	\(M_0\)
\(\neg p \wedge \neg q \wedge r\)	\(0\) \(0\) \(1\)	\(m_1\)	\(p \vee q \vee \neg r\)	\(0\) \(0\) \(1\)	\(M_1\)
\(\neg p \wedge q \wedge \neg r\)	\(0\) \(1\) \(0\)	\(m_2\)	\(p \vee \neg q \vee r\)	\(0\) \(1\) \(0\)	\(M_2\)
\(\neg p \wedge q \wedge r\)	\(0\) \(1\) \(1\)	\(m_3\)	\(p \vee \neg q \vee \neg r\)	\(0\) \(1\) \(1\)	\(M_3\)
\(p \wedge \neg q \wedge \neg r\)	\(1\) \(0\) \(0\)	\(m_4\)	\(\neg p \vee q \vee r\)	\(1\) \(0\) \(0\)	\(M_4\)
\(p \wedge \neg q \wedge r\)	\(1\) \(0\) \(1\)	\(m_5\)	\(\neg p \vee q \vee \neg r\)	\(1\) \(0\) \(1\)	\(M_5\)
\(p \wedge q \wedge \neg r\)	\(1\) \(1\) \(0\)	\(m_6\)	\(\neg p \vee \neg q \vee r\)	\(1\) \(1\) \(0\)	\(M_6\)
\(p \wedge q \wedge r\)	\(1\) \(1\) \(1\)	\(m_7\)	\(\neg p \vee \neg q \vee \neg r\)	\(1\) \(1\) \(1\)	\(M_7\)

\(m\) 和 \(M\) 的下标由成真赋值决定，与各个成真赋值的十进制数一一对应。

主析取范式: 所有简单合取式都是极小项的合取范式，如 \((p \wedge q) \vee (\neg p \wedge q)\)（\(m_1 \vee m_3\)）
主合取范式: 所有简单析取式都是极大项的析取范式，如 \((p \vee q) \wedge (\neg p \vee q)\)（\(M_0 \wedge M_2\)）

求主析取范式与主合取范式的方法一般有两种: 真值表法和等值演算法。

联结词完备集 ¶

设 \(S\) 是一个联结词集合，如果任一命题公式都可以由 \(S\) 中的联结词构成，则称 \(S\) 是联结词完备集。

与非联结词（\(\downarrow\)）: \(p \downarrow q \Leftrightarrow \neg (p \wedge q)\)
或非联结词（\(\uparrow\)）: \(p \uparrow q \Leftrightarrow \neg (p \vee q)\)
常见的联结词完备集
- \(S_1 = \{ \neg, \wedge, \vee \}\)
- \(S_2 = \{ \neg, \wedge, \vee, \rightarrow \}\)
- \(S_3 = \{ \neg, \wedge, \vee, \rightarrow, \leftrightarrow \}\)
- \(S_4 = \{ \neg, \wedge \}\)
- \(S_5 = \{ \neg, \vee \}\)
- \(S_6 = \{ \neg, \rightarrow \}\)
- \(S_7 = \{ \downarrow \}\)
- \(S_8 = \{ \uparrow \}\)
综合来看，只要联结词中包含 \(\neg\)、\(\wedge\)（后面三个通过等值演算均可以化作包含 \(\neg\)、\(\wedge\) 的命题公式），那么该联结词集合就是联结词完备集。