用户: Eli/数理逻辑

数理逻辑
2022 年春季学期 2-4 2-5 冯琦

1句法

句法: 用什么造句? 如何造句? 何谓正确语句?

符号

逻辑符号: $(,\neg ,\to ,).$
语句符号: $A_n,n\in \mathbb{N}$.
上述资料记为 $\Sigma$.

造句

令 ${\Sigma }^{\ast }$ 是 $\Sigma$ 上的所有的有限序列 (包括空语句) 的全体.

定义 1.1 (准语言). $L\subset \Sigma$ 是一个准语言, 若
(1) $\forall n\in \mathbb{N}$, $A_n\in L$;
(2) 若 $\phi \in L$, 则 $(\neg \phi )\in L$;
(3) 若 $\phi ,\psi \in L$, 则 $(\phi \to \psi )\in L$.

定义 1.2. 令 ${\mathcal{L}}_0$ 为 (包含关系下) 最小的准语言.

用 “根塔” 可以证明 ${\mathcal{L}}_0$ 中的语言均可由 (1) (2) (3) 经过有限次组合得到.

可读性

引理 1.3 (可读性). 设 $\phi \in {\mathcal{L}}_0$, 则以下三者必居其一:
(1) $\phi \in \{A_n|n\in \mathbb{N}\}$;
(2) $\exists \psi \in {\mathcal{L}}_0$ 使得 $\phi$ 是 $(\neg \psi )$;
(3) $\exists {\psi }_1,{\psi }_2\in {\mathcal{L}}_0$, 使得 $\phi$ 是 $({\psi }_1\to {\psi }_2)$.

引理 1.4 (唯一可读性). 上述引理中 (1) (2) (3) 只居其一, 且分解方式是唯一的.

引理 1.5 (“电话号码” 原理). 任何真确语句的真前缀都不是真确语句.

2真假赋值法

真假赋值法: 何谓真、假? 怎样区分永真 (绝对真理) 、永假、可真可假? 什么是逻辑推论 (相对真理) ?

定义 2.1. 一个真假赋值就是一个函数 $\nu :\{A_n|n\in \mathbb{N}\}\to \{0,1\}$.

定义 2.2 (规范函数). $H_{\neg }:\{0,1\}\to \{0,1\}$ 满足 $H_{\neg }(x)=1-x$.
$H_{\to }:\{0,1{\}}^2\to \{0,1\}$ 满足 $H_{\to }(1,0)=0$, 其余均为 $1$.

定理 2.3 (唯一扩展定理). 真假赋值 $\nu$ 可以唯一地扩展到 $\bar{\nu }:{\mathcal{L}}_0\to \{0,1\}$, 满足:
(1) $\forall n\in \mathbb{N}$, $\bar{\nu }(A_n)=\nu (A_n)$.
(2) $\phi \in {\mathcal{L}}_0$, 则 $\bar{\nu }((\neg \phi ))=H_{\neg }(\bar{\nu }(\phi ))$.
(3) ${\phi }_1,{\phi }_2\in {\mathcal{L}}_0$, 则 $\bar{\nu }(({\phi }_1,{\phi }_2))=H_{\to }(\bar{\nu }({\phi }_1),\bar{\nu }({\phi }_2))$.

定义 2.4 (逻辑推论). $\Gamma \subset {\mathcal{L}}_0$, $\phi \in {\mathcal{L}}_0$ 称 $\Gamma$ 的逻辑推论, 若任意 $\nu$ 满足 $\Gamma$, 有 $\nu$ 满足 $\phi$. 记为 $\Gamma \models \phi$.

例子有 $\{A,(A\to B)\}\models B$.

3演绎推理法

演绎推理法: 如何从已知真语句出发获得新的真语句? 可靠性、有效性? 形式推理

逻辑公理

设 $A,B,C$ 是 ${\mathcal{L}}_0$ 中的语句.
(I.1) $(A\to A)$ (同一律) ;
(I.2) $(((\neg A)\to A)\to A)$ (第一归谬律) ;
(II.1) $(A\to (B\to A))$ (第一宽容律) ;
(II.2) $(A\to ((\neg A)\to B))$ (第二宽容律) ;
(II.3) $((\neg A)\to (A\to B))$ (第三宽容律) ;
(II.4) $(A\to ((\neg B)\to (\neg (A\to B))))$ (合取律) ;
(III) $((A\to (B\to C))\to ((A\to B)\to (A\to C)))$ (蕴含分配律) .

推理法则

对任意的 $A,B\in {\mathcal{L}}_0$, 由 $A$ 和 $(A\to B)$ 推导出 $B$.

定义 3.1 (论证). 设 $\Gamma \subset {\mathcal{L}}_0$, $<B_1,\cdots ,B_m>$ 是 ${\mathcal{L}}_0$ 中语句的一个有限序列. 称 $<B_1,\cdots ,B_m>$ 是一个 $\Gamma$-论证, 若任意 $1\le i\le m$, 以下三者必居其一:
(1) $B_i$ 是一个逻辑公理;
(2) $B_i\in \Gamma$;
(3) 在 $B_i$ 之前有 $B_j,B_k$, 使得 $j<k$, 且 $B_k$ 是 $(B_j\to B_i)$.

定义 3.2 (定理). $B$ 是 $\Gamma$ 的一个定理, 若存在一个 $\Gamma$-论证 $<B_1,\cdots ,B_m>$, 使得 $B_m$ 是 $B$. 记为 $\Gamma ⊢B$.