前言
数理逻辑部分包括以下章节：
- 第2章：命题逻辑
- 第3章：一阶谓词逻辑
其核心思路是，如何用数学表达式将现实中的命题抽象化，从而用于描述事物（在数学中，就是用于描述集合）。
数学家先提出了命题逻辑，但显然命题逻辑不能描述所有的事实。例如：
所有的金属是导体，因为铜是金属，所以铜是导体。
因此又有了加入谓词和量词的一阶谓词逻辑。
命题逻辑
基本概念
命题：能够判断真假的陈述句
连接词：
合取式：$A\land B$
析取式：$A\lor B$
否定式：$\neg A$
蕴含式：$A\rightarrow B$ （记住规则，假命题可以推出所有命题）
等价式：$A\leftrightarrow B$
与非式：$A\uparrow B = \neg (A \land B)$
或非式：$A\downarrow B=\neg (A \lor B)$
命题公式：
由命题变元和命题常元以及连接词按照一定规则形成的公式，也称合式公式或公式。
命题公式分类
- 永真式：也叫重言式，在各种赋值下取值均为真（一定是可满足式）
- 永假式：也叫矛盾式，在各种赋值下取值均为假
- 可满足式：若A不是矛盾式，则其为可满足式（等价定义：A至少存在一个成真赋值）
等值演算
等值演算：
🤔 重点看一下分配律、德摩根律和蕴含等值式，求析取范式、合取范式会常用到
置换规则：若$A\Leftrightarrow B$，则$\Phi(B)\Leftrightarrow \Phi(A)$
🤔 置换规则的重要性会在一阶谓词逻辑中的求前束范式以及逻辑推理中体现，与之相关的是换名规则，不需要定义上的掌握，但需要明白怎么使用。
联结词完备集
真值函数
称$F:\lbrace0,1\rbrace^n\rightarrow \lbrace0,1\rbrace$为$n$元真值函数
特征
- $n$元真值函数共有$2^{2^n}$个
- 每个命题公式对应一个真值函数
- 每个真值函数对应无穷个命题公式
🤔 可以Recall一下集合运算和函数关系
联结词完备集
设$S$是一个联结词集合，如果任何$n(n\ge 1)$元真值函数都可以由仅含$S$中的联结词构成的公式表示，则称$S$是联结词完备集
定理
- $S=\lbrace\neg,\land,\lor\rbrace$是联结词完备集
- 推论：$S=\lbrace\neg,\land\rbrace,\quad S=\lbrace\neg,\lor\rbrace\quad S=\lbrace\neg,\rightarrow\rbrace$
- $\lbrace\uparrow\rbrace,\lbrace\downarrow\rbrace$都是联结词完备集
范式
析取范式与合取范式
定义：
- 命题变量及其否定统称作文字，仅由有限个文字构成的析/合取式称作简单析/合取式
- 由有限个简单合取式构成的析取式称为析取范式（与或）
- 由有限个简单析取式构成的合取式称为合取范式（或与）
定理：
🤔 用脑子想想就知道了，范式为永真式和永假式的时候，里面的简单式是啥情况
求范式顺序：
- 消去联结词$\rightarrow,\leftrightarrow$
- 否定号的消去（双重否定律）或内移（德摩根定律）
- 利用分配律
极大项和极小项
🤔 还记得偏序关系吗，那里的叫极大元和极小元，不要忘记。
极大项：取所有命题变元的简单析取式
极小项：取所有命题变元的简单合取式
$n$个变元有$2^n$个极大项（极小项），每个极大项有唯一成假赋值，每一个极小项有唯一成真赋值
极大项和极小项之间有对应关系（德摩根律证明）：
$$
\neg m_i\Leftrightarrow M_i \ ,\quad \neg M_i\Leftrightarrow m_i
$$
🤔 这个很重要，可以用于求主析取和主合取
主析取范式与主合取范式
定义：若由n个命题变项构成的析\合取范式中所有的简单合\析取式都是极小\大项，则称其为主析\合取范式
定理：任意命题公式都存在着与之等值的主析取范式和主合取范式
求主范式步骤：
- 求析\合取范式
- 展开（乘一\加零）
用途：
- 求取成真赋值和成假赋值
- 判断公式类型
🤔 若方便求主合取范式，但要求主析取范式，则可以通过上面的对应关系转化。
例：若3阶公式的主合取范式为：$\prod(1,2,3,4,5)=M_1\land M_2\land M_3\land M_4\land M_5$
则其主析取范式为：$\sum(0,6,7)=m_0\lor m_6 \lor m_7$
推理
推理的形式结构
称
$$
(A_1\land A_2\land \ldots\land A_k)\rightarrow B
$$
为由前提$A_1,A_2\ldots A_k$推结论$B$的推理的形式结构
当推理正确（重言式）时，记为
$$
(A_1\land A_2\land \ldots\land A_k)\Rightarrow B
$$
判断推理正确的方式：
- 真值表法
- 等值演算法
- 主析取范式法
🤔 主析取范式由极小项析取组成，而极小项给出了唯一的成真赋值
推理定律
推理规则
证明方法
附加前提证明法
定义：当推理的结论为蕴含式$A\rightarrow B$时，把$A$加入推理的前提，把$B$作为推理的结论。$A$即为附加前提。
即，把证明推理
$$
(A_1\land A_2\land \ldots\land A_k)\rightarrow (C\rightarrow B)
$$
转换成证明推理
$$
(A_1\land A_2\land \ldots\land A_k\land C)\rightarrow B
$$
归谬法
定义：把结论的否定加入前提，而要推出矛盾（以0为结论）。
即，把证明推理
$$
(A_1\land A_2\land \ldots\land A_k)\rightarrow B
$$
转换成证明推理
$$
(A_1\land A_2\land \ldots\land A_k\land \neg B)\rightarrow 0
$$
归结证明法
归结规则
显然有
$$
(L\lor C_1)\land(\neg L \lor C_2)\Rightarrow C_1\lor C_2
$$
$L$是一个变元，$C_1$和$C_2$是简单析取式。称上式为归结定律
$$
\ \ L\lor C_1 \
\underline{\neg L\lor C_2}\
\ C_1\lor C_2 \
$$
基本思想：采用归谬法，把结论的否定引入前提。若推出空简单析取式（推出0），则证明推理正确。
步骤
- 把结论的否定引入前提
- 把所有前提化成合取范式，将其中的所有简单析取式作为前提
- 应用归结规则进行推理
- 若推出空简单析取式（推出0），则证明推理正确
一阶谓词逻辑
基本概念
个体词
可以独立存在的具体或抽象的客体，分个体常元和个体变元
- 个体域：个体变项的取值范围
- 全总个体域：宇宙一切事物
谓词
刻画个体值性质及个体词间的关系，分谓词常元和谓词变元
- n元谓词：$P(x_1,x_2,\ldots,x_n)$，值为0或1
- 0元谓词：不带个体变项的谓词
- 特性谓词：将个体词与其他事物区别开来的谓词，$M(x)$
量词
表示个体间的数量关系
全称量词：$\forall$
存在量词：$\exists$
符号化
全称量词用蕴含，存在量词用合取。
一阶逻辑公式与分类
一阶语言字母表$\mathscr{L}$
- 个体常项：$a,b,c,\ldots,a_i,b_i,c_i,\ldots,i\ge1$
- 个体变项：$x,y,z,\ldots,x_i,y_i,z_i,\ldots,i\ge1$
- 函数符号：$f,g,h,\ldots,f_i,g_i,h_i,\ldots,i\ge1$
- 谓词符号：$F,G,H,\ldots,F_i,G_i,H_i,\ldots,i\ge1$
- 量词符号：$\forall,\exists$
- 联结词符号：$\neg,\land,\lor,\rightarrow,\leftrightarrow$
- 括号与逗号：$(),,$
公式
- 称$R(x_1,x_2,\ldots,x_n)$为原子公式（谓词+项）
- 单一的原子公式或原子公式的各种组合称为合式公式（谓词公式），简称公式
辖域
- 在公式 $\forall xA$ 和 $\exists xA$ 中，称 $x$ 为指导变元，$A$ 为相应量词的辖域
- 在 $\forall x$ 和 $\exists x$ 的辖域中，$x$ 的所有出现都成为约束出现，$A$ 中不是约束出现的其他变项均称为是自由出现的
- 若公式 $A$ 中不含自由出现的个体变项，则称 $A$ 为封闭的公式，简称闭式
等值演算
一阶谓词逻辑中的等值演算包括：
- 消去量词等值式
- 量词否定等值式（存在不=不全是，全是不=不存在）
- 辖域收缩扩张等值式（只有蕴含式的前键会发生存在任意变化）
- 量词分配等值式（只有存在对析取，任意对合取有分配率）
置换规则和换名规则
换就完了
前束范式
定义：前面只能是量词的公式
定理：一阶逻辑任何公式都能化为前束范式
求的时候消+换即可。
