Propositional Logic

Propositional Logic and Logic Connectives

• 首先是引入了三个逻辑连接词 $\land , \lor , \lnot$。
  • 优先级：$\lnot , \land , \lor$
• 然后还有原子命题：$p, q, r$。
• 利用逻辑连接词、原子命题还有适当的括号，就能构成复合命题。

Definition 1. Truth table of connectives.

这里需要一幅图：

Defination 2. Suppose $\Sigma$ is the set of propositional variables. A mapping $\mathcal{J}:\Sigma \to \{ T, F \}$ called a truth assignment (真值指派).

例如 $\Sigma = \{ p, q, r \}$, $\mathcal{J}(p) = T, \mathcal{J}(q) = F, \mathcal{J}(r) = F$。在没有真值指派的情况下，原子命题的真与假没有意义。

Definition 3. Suppose $\Sigma$ is the set of propositional variables and $\mathcal{J}:\Sigma \to \{ T, F \}$ is a truth assignment. The truth value of compound proposition $\phi$ on $\mathcal{J}$ (written as $[\![\phi]\!]_{\mathcal{J}}$ ), is defined recursively as follows:

• $[\![p]\!]_{\mathcal{J}} = \mathcal{J}(p)$ for atomic propositions. 就是用真值指派本身定义。
• $[\![\phi \land \psi]\!]_{\mathcal{J}} = [\![\land ]\!] ([\![\phi]\!]_{\mathcal{J}}, [\![\psi]\!]_{\mathcal{J}})$
• $[\![\phi \lor \psi]\!]_{\mathcal{J}} = [\![\lor ]\!] ([\![\phi]\!]_{\mathcal{J}}, [\![\psi]\!]_{\mathcal{J}})$
• $[\![\lnot \phi]\!]_{\mathcal{J}} = [\![\lnot ]\!] ([\![\phi]\!]_{\mathcal{J}})$

where $[\![\land ]\!], [\![\lor ]\!]$ and $[\![\lnot ]\!]$ represents truth tables of $\land , \lor$ and $\lnot$.

• 以上定义了复合命题在真值指派上的真值。这里强调了复合命题就是符合了某些语法（原子命题和逻辑连接词的特定组合）的一串符号，不要把它看成真值。
• 想要知道复合命题在任意真值指派下的真值，使用真值表是可行的办法。

Logical Equivalence

Definition 4. $\phi$ is a logically equivalent (逻辑等价) to $\psi$, written as $\phi \equiv \psi$, if $\phi$’s truth value and $\psi$’s truth value are the same under any situation. In other words, $\phi\equiv \psi$ if $[\![\phi]\!]_{\mathcal{J}} = [\![\psi]\!]_{\mathcal{J}}$ for any truth assignment $\mathcal{J}$.

• 注意，逻辑等价并不说明两个命题是同一个命题。两个命题只是从真值的角度区分不了，但是从语法形式的角度可以区分。
• 证明逻辑等价可以使用真值表说明，如果在所有真值指派下两个命题真值相等，那么逻辑等价。

Example 5. $p \equiv \lnot \lnot p$

Theorem 6

• $\lnot ( \lnot \phi ) \equiv \phi$ (Double Negation)
• $\phi \lor \phi \equiv \phi$, $\phi \land \phi \equiv \phi$ (Idempotent Laws, 幂等律)
• $\phi \lor \psi \equiv \psi \lor \phi$, $\phi \land \psi \equiv \psi \land \phi$ (Commutative Laws, 交换律)
• $( \phi \lor \psi ) \lor \chi \equiv \phi \lor ( \psi \lor \chi )$,
  $( \phi \land \psi ) \land \chi \equiv \phi \land ( \psi \land \chi )$ (Associative Laws, 结合律)
• $\phi\lor(\psi\land\chi)\equiv(\phi\lor\psi)\land(\phi\lor\chi)$
  $\phi \land ( \psi \lor \chi ) \equiv ( \phi \land \psi ) \lor ( \phi \land \chi )$ ( Distributive Laws,分配律)
• $\lnot ( \phi \land \psi ) \equiv ( \lnot \phi ) \lor ( \lnot \psi )$,
  $\lnot ( \phi \lor \psi ) \equiv ( \lnot \phi ) \land ( \lnot \psi )$ (De Morgan’s Laws)

Theorem 7 (Negation Laws)
有一些命题在任意的真值指派上都为真或者都为假，那么在逻辑等价的推理的时候会用 $T, F$ 表示恒为真或者恒为假的命题。注意，这里并不是表示命题和真值逻辑等价。

• $\phi \lor ( \lnot \phi ) \equiv T$
• $\phi \land (\lnot\phi)\equiv F$

Theorem 8 (Laws of logical constants).

• $\phi \land T \equiv \phi$
• $\phi \lor F \equiv \phi$
• $\phi \lor T \equiv T$
• $\phi \land F \equiv F$

Theorem 9 (Absorption Laws).

• $\quad\phi\lor(\phi\land\psi)\equiv\phi$
• $\quad\phi\land(\phi\lor\psi)\equiv\phi$

Theorem 10 (Transitivity(传递性))
If $\phi\equiv\psi$ and $\psi\equiv\chi$,then $\phi\equiv\chi$.

Theorem 11 (Congruence Property(算子对于逻辑等价的保持)).

• If $\phi\equiv\psi$ then $\lnot\phi\equiv\lnot\psi$.
• If $\phi_{1}\equiv\phi_{2}$ and $\psi_{1}\equiv\psi_{2}$ then $\phi_{1}\land\psi_{1}\equiv\phi_{2}\land\psi_{2}$.
• If $\phi_{1}\equiv\phi_{2}$ and $\psi_{1}\equiv\psi_{2}$ then $\phi_{1}\lor\psi_{1}\equiv\phi_{2}\lor\psi_{2}$.

Theorem 12 (Reflexivity(自反性)). $\phi\equiv\phi$.

Consequence Relation

Definition 13. Suppose $\Phi$ is a set of propositions and $\psi$ is one single proposition. We say that $\psi$ is a consequence (语义后承) of $\Psi$, written as $\Psi \models \phi$, if $\Psi$’s being all true implies that $\psi$ is also true. In other words, $\Psi \models \psi$ if for any truth assignment $\mathcal{J}$, $[\![\phi]\!]_{\mathcal{J}}= T$ for any $\phi \in \Psi$ implies $[\![\psi]\!]_{\mathcal{J}}=T$.
We will write $\models \psi, \phi \models \psi, \phi_1, \phi_2, \ldots ,\phi_{n}$ and $\Phi, \phi_1, \phi_2, \ldots \phi_{n} \models \psi$ to represent $\varnothing \models \psi, \{ \phi \}\models \psi , \{ \phi_1, \phi_2, \ldots ,\phi_{n} \}\models \psi$ and $\Phi \cup \{ \phi_1, \phi_2, \ldots ,\phi_{n} \} \models \psi$.

Example 14. $\Phi=\{p,q\},\psi=p\land q,\Phi\models\psi$

Example 15. $\Phi=\{p\land q\},\psi=p,\Phi\models\psi$

Example 16. $\Phi=\{p\land q\},\psi=q,\Phi\models\psi$

Example 17. $\Phi=\{p\lor q,\lnot p\lor r\},\psi=q\lor r,\Phi\models\psi$

Example 18. $\Phi = \{ p, q\} , \psi = p\lor q, \Phi \models \psi$

Example 19. $\Phi = \{ p\} , \psi = p\lor q, \Phi \models \psi$

Example 20. $\Phi = \{ p\} , \psi = p\land q, \Phi \neq \psi$

Example 21. $\Phi=\{p\},~\psi=q,~\Phi\neq\psi$

Example 22. $\Phi=\{~\},~\psi=p\lor~\lnot p,~\Phi\models\psi$

Example 23. $\Phi = \{ \begin{array} { c } \} , \psi = p\land \lnot p, \end{array} \Phi \neq \psi$

Example 24. $\Phi=\{~\},~\psi=p,~\Phi\neq\psi$

Example 25. $\Phi=\{p,\lnot p\},\psi=q,\Phi\models\psi$

Example 26. $\Phi = \{ p\land \lnot p\} , \psi = q, \Phi \models \psi$

Example 27. $\Phi = \{ p, \lnot p\} , \psi = q\land \lnot q, \Phi \models \psi$

Theorem 28. $\phi,\psi\models\phi\land\psi$ ($\land $-Introduction)

$\phi\land\psi\models\phi$($\land$-Elimination-1)
$\phi\land\psi\models\psi$($\land$-Elimination-2)
$\phi\models\phi\lor\psi$ ($\lor$-Introduction-1)
$\psi\models\phi\lor\psi$ ($\lor$-Introduction-2)

Theorem 29 ($\lor$-Elimination).If $\Phi,\phi_1\models\psi$ and $\Phi,\phi_2\models\psi$,then $\Phi,\phi_1\lor\phi_2\vDash\psi$

Proof.
Suppose $(1)[\![\phi]\!]_{\mathcal{J}}=\mathbf{T}$ for any $\phi\in\Phi;(2)[\![\phi_{1}\lor\phi_{2}]\!]_{\mathcal{J}}=\mathbf{T}.$
Case analysis. at least one of the following holds: $[\![\phi_1]\!]_\mathcal{J}=\mathbf{T},[\![\phi_2]\!]_\mathcal{J}=\mathbf{T}$
Qed.

Theorem 30 (Contrapositive（逆否律）).

• If $\Phi,\neg\phi_{1}\models\phi_{2}$, then $\Phi,\neg\phi_{2}\models\phi_{1}$
• If $\Phi, \phi_{1}\models \neg \phi_{2}$, then $\Phi, \phi_{2}\models \neg \phi_{1}$
• If $\Phi, \phi_{1}\models \phi_{2}$, then $\Phi$, $\neg \phi_{2}\models \neg \phi_{1}$
• If $\Phi, \neg\phi_1\models\neg\phi_2$, then $\Phi,\phi_2\models\phi_1$

proof.
Only prove the first statement here.
Suppose (1) $[\![\phi]\!]_{\mathcal{J}}=T$ for any $\phi \in \Phi$; (2) $[\![\lnot \phi_2]\!]_{\mathcal{J}}=T$.
Now, in order to achieve $[\![\phi_1]\!]_{\mathcal{J}}=T$, we prove it by contradiction.
Assume $[\![\phi_1]\!]_{\mathcal{J}}=F$. Thus $[\![\lnot \phi]\!]_{\mathcal{J}}=T$. So $[\![\phi_2]\!]_{\mathcal{J}}=T$ (According to $\Phi,\neg\phi_{1}\models\phi_{2}$ and (1)), which contradicts with (2).
Qed.