### 2. 命题逻辑中的符号：

• ¬: 命题的否定，p的否定与p的真值相反；
• ∨: 两个命题的或符号；
• ∧: 两个命题的与符号；
• →: 蕴含符号，如果p则q，表示成 p→q
• ⊤：特殊符号，表示真
• ⊥：特殊符号，表示假

### 3. 自然演绎 Natural deduction

φ1, φ2, …, φn ⊢ ψ.

#### 3.1 自然演绎中的规则

$\frac{\phi\ \ \ \ \psi}{\phi \land \psi}\land_i$

$\frac{\phi\ \land\ \psi}{\phi}, \ \ \ \ \frac{\phi\ \land\ \psi}{\psi}$

$\frac{\neg\neg\phi}{\phi}\neg\neg e, \ \ \ \ \frac{\phi}{\neg\neg\phi}\neg\neg i$

$\frac{\phi \ \ \ \ \phi \rightarrow \psi}{\phi} \rightarrow e$

$\frac{\phi \rightarrow \psi \ \ \ \ \ \neg\psi }{\neg\phi} MT$

$\frac{\phi }{\phi \lor \psi } , \ \ \ \ \frac{\psi}{\phi \lor \psi}$

#### 3.2 直觉主义逻辑 VS 经典逻辑

$\frac{}{\phi \lor \neg\phi } LEM, \ \ \ \ \frac{\neg\neg\phi}{\phi}\neg\neg e,$

1. 假设$b^{b}$是有理数。因此命题中，选择$a$$\sqrt{2}$，则$a^{b}$等于$b^{b}$，是个有理数，得证。
2. 假设$b^{b}$是无理数。因此我们选择$a$$\sqrt{2}^{\sqrt{2}}$（因为$b^{b}$是无理数，令$b=2$），因此$a^{b}=\sqrt{2}^{\sqrt{2}^{\sqrt{2}}} = \sqrt{2}^{(\sqrt{2} \times \sqrt{2})} = \sqrt{2}^2 = 2$，是有理数。$((x^y)^z = x^{(x\cdot z)})$

### 4 命题逻辑语法

$\phi ::= p\ |\ (\neg\phi)\ |\ (\phi \land \phi)\ |\ (\phi \lor \phi)\ |\ (\phi \rightarrow \phi)$

p ¬p p q p∨q
1 0 1 0 1
0 1 0 1 1
0 0 0
1 1 1
p q p∧q p q p→q
1 0 0 1 0 0
0 1 0 0 1 1
0 0 0 0 0 1
1 1 1 1 1 1

### 6. 命题逻辑的可靠性（soundness）

$\phi_1, \phi_2, …, \phi_n \vdash \psi$ 如果成立，表示可以通过推演系统，由前提$\phi_1, \phi_2, ..., \phi_n$，推演得到结论 $\psi$ 。但是，我们有证据表明，通过真值表的语义，也能得到相同的结论吗？

$\phi_1, \phi_2, ..., \phi_n\models \psi$

### 7. 命题逻辑的完备性（Completeness）

• step1：证明 $\models \phi_1 \rightarrow ( \phi_2 \rightarrow ( \phi_3 \rightarrow ( ... (\phi_n \rightarrow \psi)...)) )$ 成立；
• step2：证明 $\vdash \phi_1 \rightarrow ( \phi_2 \rightarrow ( \phi_3 \rightarrow ( ... (\phi_n \rightarrow \psi)...)) )$ 成立；
• step3：证明 $\phi_1, \phi_2, …, \phi_n \vdash \psi$ 成立

$\phi_1, \phi_2, ..., \phi_n \vdash \psi\ is\ valid\ iff\ \phi_1, \phi_2, ..., \phi_n \models \psi\ holds.$

### 8. 命题逻辑的可满足性（Satisfiability）

• $L ::= p\ |\ \neg p$
• $D ::= L\ |\ L\ \lor D$
• $C ::= D\ |\ D\land C$