(理解大于識記, 這么多公式我是記不住)

命題邏輯

$P$	$Q$	$?P$ 否定/非	$P\wedge Q$ 合取/與	$P\vee Q$ 析取/或	$P\to Q$ 蘊含	$P?Q$ 等價
0	0	1	0	0	1	1
0	1	1	0	1	1	0
1	0	0	0	1	0	0
1	1	0	1	1	1	1

$P\to Q$ 的自然語言
充分條件: 如 $P$ 則 $Q$, 只要 $P$ 就 $Q$.
必要條件: $P$ 僅當 $Q$, 只有 $Q$ 才 $P$, 除非 $Q$ 才 $P$, 除非 $Q$ 否則 $?P$.

永真公式(重言); 永假公式(矛盾); 可滿足公式.

聯結詞完備集: { S , ∧ , ∨ , ? } \{S,\wedge,\vee,\neg\} {S,∧,∨,?}; { S , ∧ , ? } \{S,\wedge,\neg\} {S,∧,?}; { S , ∨ , ? } \{S,\vee,\neg\} {S,∨,?}.

析取式(子句): 有限個變元的析取.
合取式(短語): 有限個變元的合取.
析取范式: 有限個短語的析取.
合取范式: 有限個子句的合取.
化簡: ①取代等價蘊含; ②De MoRGen和雙重否定律去掉多余否定; ③分配律進一步化簡.

最簡式: 變元及否定存在且只存在一個, 變元間次序唯一.
極小項(最簡合取式); 極大項(最簡析取式); $n$ 個變元各有 $2^n$ 個極小項和極大項.
全部極小項的析取永真, 全部極大式的合取永假.
主析取范式: 有限個極小式的析取.
主合取范式: 有限個極大式的合取.
求主范式方法: ①化簡; ②補項并分配律: 求主析取補 $(?P\vee P)$, 求主合取補 $(?P\wedge P)$; ③剩余極小項析取(極大項合取)的否定即得主合取(主析取) - 即主范式項數和為 $2^n$.

等價公式: 交換律, 結合律, 分配律, 雙重否定律, De MoRGan 律.
冪等律: $G\wedge G=G$, $G\vee G=G$.
吸收律: $G\vee (G\wedge H)=G$, $G\wedge (G\vee H)=G$.
同一律: $G\wedge 0=G$, $G\vee 1=G$.
零律: $G\wedge 1=1$, $G\vee 0=0$.
排中律: $G\vee ?G=1$.
矛盾律: $G\wedge ?G=0$.
等價: $G?H=(G\to H)\wedge (H\to G)$.
蘊含: $G\to H=?G\vee H$.
假言易位: $G\to H=?H\to ?G$.
等價否定: $G?H=?G??H$.
歸謬: $(G\to H)\wedge (G\to ?H)=?G$.
代入: 永真公式中某一變元永相同公式代入仍為永真.
替換: 原公式與其中出現的子公式被恒等公式替換后得到的新公式等價.
反演: 反演公式為原公式否定; 交換 $\vee$ 和 $\wedge$, $0$ 和 $1$, 所有變元取反.
對偶: 等價公式各自的對偶公式仍等價; 交換 $\vee$ 和 $\wedge$, $0$ 和 $1$.
異或: $A\bar{\wedge }B=?(A?B)$.
蘊含否定: $A\nrightarrow B=?(A\to B)$.
與非: $A\uparrow B=?(A\wedge B)$.
或非: $A\downarrow B=?(A\vee B)$.

形式推理 $G_1,G_2,...,G_n?H$ 有效(成立, 不一定有真實性)當且僅當 ${?}_{i=1}^n{G}_i\to H$ 永真.
簡化規則: $G\wedge H?G,H$.
添加規則: $G?G\vee H$; $H?G\vee H$.
$?G?G\to H$; $H?G\to H$; $?(G\to H)?G,?H$; $G,H?G\wedge H$.
選言三段論: $?G,G\vee H?H$; $?G,G\bar{\vee }H?H$.
肯定前件: $G,G\to H?H$.
否定后件: $?H,G\to H??G$.
假言三段論: $G\to H,H\to I?G\to I$.
二難推論: $G\wedge H,G\to I,H\to I?I$.
演繹法: 規則 P(前提引用); 規則 T(邏輯結果引用); 規則 CP(附加前提).
反證法: $G_1,G_2,...,G_n,?H$ 不一致(不相容), 即 ${?}_{i=1}^n{G}_i\wedge ?H$ 永假(矛盾)時, 形式推理有效.