数理逻辑
2019-03-13

第一讲 命题逻辑

定义1.1

命题符:$P_0,P_1,P_2…P_n,n\in\mathbb{N}$,记$PS={P_n|n\in\mathbb{N}}$.本书中,命题符之集$PS$为可数无穷集,即$|PS|=\aleph_0$

定义1.3

所有命题的集合$PROP$是满足以下条件的最小集合

1. $PS\subseteq PROP$
2. 若$A\in PROP$,则$C_{\lnot}(A)\in PROP$
3. 若$A,B\in PROP$,则$C_{\wedge(A,B)},C_{\vee}(A,B)$和$C_{\to}(A,B)\in PROP$

引理 1.5

$A\in PROP$等价于存在有穷序列$A_0,A_1…A_n$使$A$为$A_n$且对任何$i\le n$

1. $A_i\in PS$
2. 或 存在$k < i$使$A_i$为$(\lnot A_k)$
3. 或 存在$k,j < i$使$A_i$为$(A_k\ast A_l)$,这里$\ast$为$\wedge,\vee,\to$之一

命题 1.9

1. $v$满足$A$,记为$v\models A$,指$\hat{v}(A)=T$
2. $A$为永真式,记为$\models A$,指对任何$v$有$\hat{v}(A)=T$
3. $A$可满足,指有$v$使$v\models A$
4. 设$\Gamma$为命题集,$A$为$T$的语义结论,记为$\Gamma\models A$,指对所有$v$,若对任何$B\in\Gamma$有$\hat{v}(B)=T$则$\hat{v}=T$

定义 1.13

设$A,B$为命题$A$与$B$逻辑等价,记为$A\simeq B$,指对任何赋值$v,v\models A$ iff $v\models B$

第八讲 命题逻辑的永真推理系统

公理
A01	$A\to A$
A02	$(A\to(B\to C))\to(B\to(A\to C))$
A03	$(A\to B)\to((B\to C)\to(A\to C))$
A04	$(A\to(A\to B))\to(A\to B)$
A05	$(A\to\lnot B)\to(B\to\lnot A)$
A06	$(\lnot\lnot A)\to A$
A07	$(A\wedge B)\to A$
A08	$(A\wedge B)\to B$
A09	$A\to(B\to(A\wedge B))$
A10	$A\to(A\vee B)$
A11	$B\to(A\vee B)$
A12	$(A\to C)\to((B\to C)\to((A\vee B)\to C))$
T13	$(A\to B)\to((C\to A)\to(C\to B))$
T14	$(A\to B)\to([D\to(C\to A)]\to[D\to(C\to B)])$
T15	$\vdash A\to(B\to A)$
T16	$\vdash[C\to(B\to A)]\to[(C\to B)\to(C\to A)]$
T17	$\vdash(\lnot A\to\lnot B)\to(B\to S)$
T18	$\vdash A\to \lnot\lnot A$
T19	$\vdash(A\to B)\to(\lnot B\to\lnot A)$
T20	$\vdash A\vee\lnot A$
T21	$A,\lnot A\vdash\lnot B$
T22	$A,\lnot A\vdash B$
T23	$(B\to\lnot B)\to\lnot B$
T24	$\vdash(A\to(C\wedge\lnot C)\to\lnot A$
T25	$(B\vee A)\to(\lnot A\to B)$
T26	$(A\to B)\to(B\vee\lnot A)$
T27	$(A\vee B)\to(B\vee A)$
T28	$(A\to(B\to C))\to((A\wedge B)\to C)$
T29	$(C\vee A)\to((C\vee B)\to(C\vee(A\wedge B)))$
T30	$(C\vee A)\to[(B\to C)\to((A\to B)\to C)]$
T31	$(A\to(C\vee B))\to(C\vee(A\to B))$

定理 8.3(推理定理)

若$\Gamma,C\vdash A$,则$\Gamma\vdash C\to A$,这里$\Gamma,C$为$\Gamma\cup\{C\}$的简写