Lec 5: 逻辑等价、蕴涵与范式¶

1. 逻辑等价与逻辑蕴含¶

当命题公式 \(A \leftrightarrow B\) 是重言式时，称 \(A\) 逻辑等价于 \(B\)，记作 \(A \equiv B\)。

定律	公式
双重否定律	\(\lnot\lnot A \equiv A\)
幂等律	\(A \lor A \equiv A\), \(A \land A \equiv A\)
交换律	\(A \lor B \equiv B \lor A\), \(A \land B \equiv B \land A\)
结合律	\((A \lor B) \lor C \equiv A \lor (B \lor C)\), \((A \land B) \land C \equiv A \land (B \land C)\)
分配律	\(A \land (B \lor C) \equiv (A \land B) \lor (A \land C)\), \(A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)\)
德摩根律	\(\lnot(A \lor B) \equiv \lnot A \land \lnot B\), \(\lnot(A \land B) \equiv \lnot A \lor \lnot B\)
吸收律	\(A \lor (A \land B) \equiv A\), \(A \land (A \lor B) \equiv A\)
蕴涵等值式	\(A \to B \equiv \lnot A \lor B\)
等价等值式	\(A \leftrightarrow B \equiv (A \to B) \land (B \to A)\)
零律	\(A \lor T \equiv T\), \(A \land F \equiv F\)
同一律	\(A \lor F \equiv A\), \(A \land T \equiv A\)
排中律	\(A \lor \lnot A \equiv T\)
矛盾律	\(A \land \lnot A \equiv F\)
假言易位	\(A \to B \equiv \lnot B \to \lnot A\)
归谬论	\(A \to B \land A \to \lnot B \equiv \lnot A\)
等价等值式2	\(A \leftrightarrow B \equiv (A \land B) \lor (\lnot A \land \lnot B)\)

当命题公式 \(A \to B\) 是重言式时，称 \(A\) 逻辑蕴涵 \(B\)，记做 \(A \models B\)。

蕴涵式	说明
\(A \models A \lor B\)	附加律
\(A \land B \models A\)	化简律
\(A \land (A \to B) \models B\)	假言推理
\((A \to B) \land \lnot B \models \lnot A\)	拒取式
\(\lnot A \land (A \lor B) \models B\)	析取三段论
\((A \to B) \land (B \to C) \models A \to C\)	假言三段论
\((A \to B) \land (C \to D) \models (A \land C) \to (B \land D)\)
\((A \leftrightarrow B) \land (B \leftrightarrow C) \models A \leftrightarrow C\)