Propositional Logic and Logic Connectives

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

Definition 1. Truth table of connectives.

这里需要一幅图：

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

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

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

  • [ ⁣[p] ⁣]J=J(p)[\![p]\!]_{\mathcal{J}} = \mathcal{J}(p) for atomic propositions. 就是用真值指派本身定义。
  • [ ⁣[ϕ∧ψ] ⁣]J=[ ⁣[∧] ⁣]([ ⁣[ϕ] ⁣]J,[ ⁣[ψ] ⁣]J)[\![\phi \land \psi]\!]_{\mathcal{J}} = [\![\land ]\!] ([\![\phi]\!]_{\mathcal{J}}, [\![\psi]\!]_{\mathcal{J}})
  • [ ⁣[ϕ∨ψ] ⁣]J=[ ⁣[∨] ⁣]([ ⁣[ϕ] ⁣]J,[ ⁣[ψ] ⁣]J)[\![\phi \lor \psi]\!]_{\mathcal{J}} = [\![\lor ]\!] ([\![\phi]\!]_{\mathcal{J}}, [\![\psi]\!]_{\mathcal{J}})
  • [ ⁣[¬ϕ] ⁣]J=[ ⁣[¬] ⁣]([ ⁣[ϕ] ⁣]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 [ ⁣[ϕ] ⁣]J=[ ⁣[ψ] ⁣]J[\![\phi]\!]_{\mathcal{J}} = [\![\psi]\!]_{\mathcal{J}} for any truth assignment J\mathcal{J}.

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

Example 5. p≡¬¬pp \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,FT, F 表示恒为真或者恒为假的命题。注意，这里并不是表示命题和真值逻辑等价。

  • ϕ∨(¬ϕ)≡T\phi \lor ( \lnot \phi ) \equiv T
  • ϕ∧(¬ϕ)≡F\phi \land (\lnot\phi)\equiv F

Theorem 8 (Laws of logical constants).

  • ϕ∧T≡ϕ\phi \land T \equiv \phi
  • ϕ∨F≡ϕ\phi \lor F \equiv \phi
  • ϕ∨T≡T\phi \lor T \equiv T
  • ϕ∧F≡F\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 ϕ1≡ϕ2\phi_{1}\equiv\phi_{2} and ψ1≡ψ2\psi_{1}\equiv\psi_{2} then ϕ1∧ψ1≡ϕ2∧ψ2\phi_{1}\land\psi_{1}\equiv\phi_{2}\land\psi_{2}.
  • If ϕ1≡ϕ2\phi_{1}\equiv\phi_{2} and ψ1≡ψ2\psi_{1}\equiv\psi_{2} then ϕ1∨ψ1≡ϕ2∨ψ2\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 J\mathcal{J}, [ ⁣[ϕ] ⁣]J=T[\![\phi]\!]_{\mathcal{J}}= T for any ϕ∈Ψ\phi \in \Psi implies [ ⁣[ψ] ⁣]J=T[\![\psi]\!]_{\mathcal{J}}=T.
We will write ⊨ψ,ϕ⊨ψ,ϕ1,ϕ2,…,ϕn\models \psi, \phi \models \psi, \phi_1, \phi_2, \ldots ,\phi_{n} and Φ,ϕ1,ϕ2,…ϕn⊨ψ\Phi, \phi_1, \phi_2, \ldots \phi_{n} \models \psi to represent ∅⊨ψ,{ϕ}⊨ψ,{ϕ1,ϕ2,…,ϕn}⊨ψ\varnothing \models \psi, \{ \phi \}\models \psi , \{ \phi_1, \phi_2, \ldots ,\phi_{n} \}\models \psi and Φ∪{ϕ1,ϕ2,…,ϕn}⊨ψ\Phi \cup \{ \phi_1, \phi_2, \ldots ,\phi_{n} \} \models \psi.

Example 14. Φ={p,q},ψ=p∧q,Φ⊨ψ\Phi=\{p,q\},\psi=p\land q,\Phi\models\psi

Example 15. Φ={p∧q},ψ=p,Φ⊨ψ\Phi=\{p\land q\},\psi=p,\Phi\models\psi

Example 16. Φ={p∧q},ψ=q,Φ⊨ψ\Phi=\{p\land q\},\psi=q,\Phi\models\psi

Example 17. Φ={p∨q,¬p∨r},ψ=q∨r,Φ⊨ψ\Phi=\{p\lor q,\lnot p\lor r\},\psi=q\lor r,\Phi\models\psi

Example 18. Φ={p,q},ψ=p∨q,Φ⊨ψ\Phi = \{ p, q\} , \psi = p\lor q, \Phi \models \psi

Example 19. Φ={p},ψ=p∨q,Φ⊨ψ\Phi = \{ p\} , \psi = p\lor q, \Phi \models \psi

Example 20. Φ={p},ψ=p∧q,Φ≠ψ\Phi = \{ p\} , \psi = p\land q, \Phi \neq \psi

Example 21. Φ={p}, ψ=q, Φ≠ψ\Phi=\{p\},~\psi=q,~\Phi\neq\psi

Example 22. Φ={ }, ψ=p∨ ¬p, Φ⊨ψ\Phi=\{~\},~\psi=p\lor~\lnot p,~\Phi\models\psi

Example 23. Φ={},ψ=p∧¬p,Φ≠ψ\Phi = \{ \begin{array} { c } \} , \psi = p\land \lnot p, \end{array} \Phi \neq \psi

Example 24. Φ={ }, ψ=p, Φ≠ψ\Phi=\{~\},~\psi=p,~\Phi\neq\psi

Example 25. Φ={p,¬p},ψ=q,Φ⊨ψ\Phi=\{p,\lnot p\},\psi=q,\Phi\models\psi

Example 26. Φ={p∧¬p},ψ=q,Φ⊨ψ\Phi = \{ p\land \lnot p\} , \psi = q, \Phi \models \psi

Example 27. Φ={p,¬p},ψ=q∧¬q,Φ⊨ψ\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 Φ,ϕ1⊨ψ\Phi,\phi_1\models\psi and Φ,ϕ2⊨ψ\Phi,\phi_2\models\psi,then Φ,ϕ1∨ϕ2⊨ψ\Phi,\phi_1\lor\phi_2\vDash\psi

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

Theorem 30 (Contrapositive（逆否律）).

  • If Φ,¬ϕ1⊨ϕ2\Phi,\neg\phi_{1}\models\phi_{2}, then Φ,¬ϕ2⊨ϕ1\Phi,\neg\phi_{2}\models\phi_{1}
  • If Φ,ϕ1⊨¬ϕ2\Phi, \phi_{1}\models \neg \phi_{2}, then Φ,ϕ2⊨¬ϕ1\Phi, \phi_{2}\models \neg \phi_{1}
  • If Φ,ϕ1⊨ϕ2\Phi, \phi_{1}\models \phi_{2}, then Φ\Phi, ¬ϕ2⊨¬ϕ1\neg \phi_{2}\models \neg \phi_{1}
  • If Φ,¬ϕ1⊨¬ϕ2\Phi, \neg\phi_1\models\neg\phi_2, then Φ,ϕ2⊨ϕ1\Phi,\phi_2\models\phi_1

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