古典論理
classical logic、標準論理、standard logic
古典命題論理 (classical propositional logic)
公理、始式 :$ \frac{}{A\vdash A}(I)
Cut :$ \frac{\Gamma\vdash\Delta,D\quad D,\Pi\vdash\Lambda}{\Gamma,\Pi\vdash\Delta,\Lambda}(Cut)
構造規則
弱化 (增 W) (weakening) :$ \frac{\Gamma\vdash\Delta}{D,\Gamma\vdash\Delta}(WL),$ \frac{\Gamma\vdash\Delta}{\Gamma\vdash\Delta,D}(WR) 轉置 (換 P) (permutation) :$ \frac{\Gamma,C,D,\Pi\vdash\Delta}{\Gamma,D,C,\Pi\vdash\Delta}(PL),$ \frac{\Gamma\vdash\Delta,C,D,\Lambda}{\Gamma\vdash\Delta,D,C,\Lambda}(PR) 縮約 (減 C) (contraction) :$ \frac{D,D,\Gamma\vdash\Delta}{D,\Gamma\vdash,\Delta}(CL),$ \frac{\Gamma\vdash\Delta,D,D}{\Gamma\vdash\Delta,D}(CR) 論理規則
$ \neg:$ \frac{\Gamma\vdash\Delta,D}{\neg D,\Gamma\vdash\Delta}(\neg L),$ \frac{D,\Gamma\vdash\Delta}{\Gamma\vdash\Delta,\neg D}(\neg R)
$ \land:$ \frac{C,\Gamma\vdash\Delta}{C\land D,\Gamma\vdash\Delta}(\land L_1),$ \frac{D,\Gamma\vdash\Delta}{C\land D,\Gamma\vdash\Delta}(\land L_2),$ \frac{\Gamma\vdash\Delta,C\quad\Gamma\vdash\Delta,D}{\Gamma\vdash\Delta,C\land D}(\land R)
$ \lor:$ \frac{C,\Gamma\vdash\Delta\quad D,\Gamma\vdash\Delta}{C\lor D,\Gamma\vdash\Delta}(\lor L),$ \frac{\Gamma\vdash\Delta,C}{\Gamma\vdash\Delta,C\lor D}(\lor R_1),$ \frac{\Gamma\vdash\Delta,D}{\Gamma\vdash\Delta,C\lor D}(\lor R_2)
$ \to:$ \frac{\Gamma\vdash\Delta,C\quad D,\Pi\vdash\Lambda}{C\to D,\Gamma,\Pi\vdash\Delta,\Lambda}(\to L),$ \frac{C,\Gamma\vdash\Delta,D}{\Gamma\vdash\Delta,C\to D}(\to R)
眞理の木 (truth tree)
意味論
眞理値表
table:眞理値表
A B A∧B A∨B A→B ¬A
T T T T T F
T F F T F
F T F T T T
F F F F T
Karnaugh 圖 (Karnaugh map)
Veitch 圖
二分決定圖 (binary decision diagram; BDD)