离散数学笔记

写在前面

离散数学好像只学第1,2,5部分

第1部分 数理逻辑

第1章 命题逻辑的基本概念

1.1 命题与连接词

命题是判断结果唯一的陈述句
判断结果称为命题的真值，真值只取两个值：真或假
真值为真的命题称作真命题，真值为假的命题称作假命题

不能被分解成更简单的命题称作简单命题或原子命题
由简单命题通过联结词联结而成的命题称作复合命题

由真能推出假、又由假能推出真，从而既不为真也不能为假的陈述句称作悖论，悖论不是命题

定义1.1 设$p$为命题，复合命题“非$p$”（或$p$的否定）称作$p$的否定式，记作$\neg p$，符号$\neg$是否定联结词，$\neg p$为真当且仅当$p$为假
定义1.2 设$p,q$为两个命题，复合命题“$p$并且$q$”（或$p$与$q$）称为$p$与$q$的合取式，记作$p\land q$. $\land$称作合取联结词，$p\land q$为真，当且仅当$p$与$q$同时为真
定义1.3 设$p,q$为两个命题，符合命题$p$或$q$称作$p$与$q$的析取式，记作$p\lor q$. $\lor$称作析取联结词. 规定$p\lor q$为假当且仅当$p$与$q$同时为假

相容或 $p\lor q$
排斥或 $(\neg p\land q)\lor (p\land \neg q)$

定义1.4 设$p,q$为两个命题，复合命题“如果$p$，则$q$”称为$p$与$q$的蕴含式，记作$p\to q$，并称$p$是蕴含式的前件，$q$为蕴含式的后件. $\to$称作蕴含联结词，并规定$p\in q$为假当且仅当$p$为真$q$为假
$p\to q$的逻辑关系为$q$是$p$的必要条件

自然语言里，$q$是$p$的必要条件的叙述方式

• 只要$p$，就$q$
• 因为$p$，所以$q$
• $p$仅当$q$
• 只有$q$，才$p$
• 除非$q$才$p$

定义1.5 设$p,q$为两个命题，复合命题“$p$仅当$q$”称作$p$与$q$的等价式，记作$p \leftrightarrow q$，$\leftrightarrow$称作等价联结词. 规定$p\leftrightarrow q$为真，当且仅当$p$与$q$同时为真或同时为假
$p\leftrightarrow q$的逻辑关系为$p$与$q$互为充分必要条件

优先顺序为$(),\neg,\land,\lor,\to,\leftrightarrow$

1.2 命题公式及其赋值

简单命题是命题逻辑中最基本的研究单位，其真值是确定的，又称作命题常项或命题常元.
取值1（真）或0（假）的变元称作命题变项或命题变元
可以用命题变项表示真值可以变化的陈述句，命题变项不是命题.
将命题变项用联结词和圆括号按照一定的逻辑关系联结起来的符号串称作合式公式

定义1.6 (1) 单个命题变项是合式公式，并称为原子命题公式
(2) 若$A$是合式公式，则$(\neg A)$是合式公式
(3) 若$A,B$是合式公式，则$(A\land B),(A\lor B),(A\to B),(A\leftrightarrow B)$是合式公式
(4) 有限次地应用(1)-(3)形成的符号串是合式公式

定义1.6采用的是归纳定义或递归定义的方式
其中$A,B$用它们表示任意的合式公式，称作元语言符号，而某个具体的公式称作对象语言符号

定义1.7 (1) 若公式$A$是单个的命题变项，则称$A$为0层公式
(2) 称$A$是$n+1(n\geqslant 0)$层公式是指下面情况之一
(a) $A=\neq B$, $B$是$n$层公式
(b) $A=B\land C$, 其中$B$和$C$分别为$i$和$j$层公式，且$n=\max \{i,j\}$
(c) $A=B\lor C$, 其中$B,C$的层级及$n$同(b)
(d) $A=B\to C$, 其中$B,C$的层级及$n$同(b)
(e) $A=B\leftrightarrow C$, 其中$B,C$的层级及$n$同(b)
(3) 若公式$A$的层次为$k$，则称$A$是$k$层公式

定义1.8 设$p_1,p_2,\cdots, p_n$是出现在公式$A$中的全部命题变项，给$p_1,p_2,\cdots,p_n$各指定一个真值，称为对$A$的一个赋值或解释.
若指定的一组真值使$A$为1，则称这组值为$A$的成真赋值；若使$A$为0，则称这组值为$A$的成假赋值.

赋值按下标顺序或字母顺序依次赋值

定义1.9 将命题公式$A$在所有赋值下取值情况列成表，称作$A$的真值表.

定义1.10 设$A$为任一命题公式
(1) 若$A$在它的各种赋值下取值均为真，则称$A$为重言式或永真式.
(2) 若$A$在它的各种赋值下取值均为假，则称$A$为矛盾式或永假式.
(3) 若$A$不是矛盾式，则称$A$为可满足式.
重言式一定为可满足式

设公式$A,B$中共含有命题变项$p_1,p_2,\cdots,p_n$，而$A$或$B$不全含这些命题变项，则称$A$中不含的命题变项为$A$的哑元，即$A$的取值与哑元无关.

第2章 命题逻辑等值演算

2.1 等值式

定义2.1 设$A,B$是两个命题公式，若$A,B$构成的等价式$A\leftrightarrow B$为重言式，则称$A$与$B$是等值的，记作$A\Leftrightarrow B$.

常用的等值式模式

1. 双重否定律 $A\Leftrightarrow \neg \neg A$.
2. 幂等式 $A\Leftrightarrow A\lor A, A\Leftrightarrow A\land A$.
3. 交换律 $A\lor B\Leftrightarrow B\lor A,A\land B\Leftrightarrow B\land A$.
4. 结合律 $(A\lor B)\lor C\Leftrightarrow A\lor (B\lor C), (A\land B)\land C\Leftrightarrow A\land (B\land C)$.
5. 分配律 $A\lor (B\land C)\Leftrightarrow (A\lor B)\land (A\lor C), A\land (B\lor C)\Leftrightarrow (A\land B)\lor (A\land C)$.
6. 德摩根律 $\neg (A\lor B)\Leftrightarrow \neg A\land \neg B,\neg (A\land B)\Leftrightarrow \neg A\lor \neg B$.
7. 吸收律 $A\lor (A\land B)\Leftrightarrow A, A\land (A\lor B)\Leftrightarrow A$.
8. 零律 $A\lor 1\Leftrightarrow 1,A\land 0\Leftrightarrow 0$.
9. 同一律 $A\lor 0\Leftrightarrow A, A\land 1\Leftrightarrow A$.
10. 排中律 $A\lor \neg A\Leftrightarrow 1$.
11. 矛盾律 $A\land \neg A\Leftrightarrow 0$.
12. 蕴涵等值律 $A \to B\Leftrightarrow \neg A\lor B$.
13. 等价等值律 $A\leftrightarrow B\Leftrightarrow (A\to B)\land (B\to A)$.
14. 假言易位律 $A\to B\Leftrightarrow B\to \neg A$.
15. 等价否定等值式 $A\leftrightarrow B\Leftrightarrow \neg A\leftrightarrow \neg B$.
16. 归谬论 $(A\to B)\land (A\to \neg B)\Leftrightarrow \neg A$.

代入实例
由一直的等值式推演出另外一些等值式的过程称作等值演算.

置换规则 设$\Phi (A)$是含公式$A$的命题公式，$\Phi (B)$是用公式$B$置换$\Phi (A)$中$A$的所有出现后得到的命题公式. 若$B \Leftrightarrow A$，则$\Phi (A)\Leftrightarrow \Phi (B)$.

2.2 析取范式与合取范式

定义2.2 命题变项及其否定统称作文字. 仅由有限个文字构成的析取式称作简单析取式. 仅由有限个文字构成的合取式称作简单合取式.

定理2.1 (1) 一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式
(2) 一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式

定义2.3 由有限个简单合取式的析取构成的命题公式称作析取范式. 由有限个简单析取式的合取构成的命题公式称作合取范式. 析取范式与合取范式统称作范式.

定理2.2 (1) 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式
(2) 一个合取范式是重言式当且仅当它的每个简单析取范式都是重言式.

定理2.3(范式存在定理) 任一命题公式都存在与之等值的析取范式与合取范式

定义2.4 在含有$n$个命题变项的简单合取式(简单析取式)中，若每个命题变项和它的存在的否定式恰好出现一个且仅出现一次，而且命题变项或它的否定式按照下标从小到大或按照字典顺序排列，称这样的简单合取式(简单析取式)为极小项(极大项).

每个极小项都有且仅由一个成真赋值，每个极大项只有一个成假赋值.

定理2.4 设$m_i$与$M_i$是命题变项含$p_1,p_2,\cdots,p_n$的极小项和极大项，则$\neg m_i\Leftrightarrow M_i,\neg M_i\Leftrightarrow m_i$.
定义2.5 所有简单合取式(简单析取式)都是极小项(极大项)的析取范式(合取范式)称为主析取范式(主合取范式).
定理2.5 任何命题公式都存在与之等值的主析取范式和主合取范式，并且是唯一的.

2.3 联结词的完备集

貌似这部分选修…

第3章 命题逻辑的推理理论

3.1 推理的形式结构

数理逻辑的主要任务是用数学的方法研究推理，所谓推理是指从前提除法推出结论的思维过程，而前提是已知的命题公式集合，结论是从前提出发应用推理规则推出的命题公式

定义3.1 设$A_1,A_2,\cdots,A_k$和$B$，若对于$A_1,A_2,\cdots,A_k$和$B$中出现的命题变项的任意一组赋值，或者$A_1\land A_2\land \cdots\land A_k$为假，或者当$A_1\land A_2\land \cdots\land A_k$为真时$B$也为真，则称由前提$A_1,A_2,\cdots,A_k$推出结论$B$的推理是有效的或正确的，并称$B$为有效的结论. $B$不一定是正确的.
由推理$\Gamma $推出$B$的推理记为$\Gamma \vdash B$. 若推理是正确的，则记为$\Gamma \vDash B$否则记$\Gamma \nvDash B$为推理形式结构.

定理3.1 命题公式$A_1,A_2,\cdots,A_k$推出$B$的推理正确当且仅当$A_1\land A_2\land \cdots \land A_k\to B$为重言式.
判断是否为重言式的方法 1. 真值表法 2. 等值演算法 3. 主析取范式法

有一些重要的重言蕴含式，称作推理定律.

1. 附加律 $A\Rightarrow (A\lor B)$
2. 化简律 $(A\land B)\Rightarrow A$
3. 假言推理 $(A\to B)\land A \Rightarrow B$
4. 拒取式 $(A\to B)\land \neg B\Rightarrow \neg A$
5. 析取三段论 $(A\lor B)\land \neg B\Rightarrow A$
6. 假言三段论 $(A\to B)\land (B\to C)\Rightarrow (A\to C)$
7. 等价三段论 $(A\leftrightarrow B)\land (B\leftrightarrow C)\Rightarrow (A\leftrightarrow C)$
8. 构造性二难 $(A\to B)\land (C\to D)\land (A\lor C)\Rightarrow (B\lor D), (A\to B)\land (\neg A \to B)\Rightarrow B$
9. 破坏性二难 $(A\to B)\land (C\to D)\land (\neg B\lor \neg D)\Rightarrow (\neg A\lor \neg C)$

3.2 自然推理系统$P$

定义3.2 一个形式系统$I$由下面4个部分组成.
(1) 非空的字母表$A(I)$.
(2) $A(I)$中符号构成的合式公式集$E(I)$.
(3) $E(I)$中一些特殊的公式组成的公理集$A_X(I)$.
(4) 推理规则集$R(I)$.
将$I$记为4元组$$. 其中$$是$I$的形式语言系统，而$$为$I$的形式演算系统.

形式系统一般分为两类. 一类是自然推理系统，他的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，最后得到的命题公式是推理的结论。另一类是公理推理系统，它只能从若干条给定的公理出发，应用系统中的推理规则进行推理演算，得到的结论是系统中的重言式，称为系统中的定理。

定义3.3 自然推理系统$P$定义如下.

1. 字母表
   (1) 命题变项符号: $p,q,r,\cdots, p_i,q_i,r_i,\cdots(i\geqslant 1)$.
   (2) 联结词符号: $\neg ,\land ,\lor ,\to ,\leftrightarrow$.
   (3) 括号与逗号: $(,),,.$
2. 合式公式 同定义1.6
3. 推理规则
   (1) 前提引入规则: 在证明的任何步骤都可以引入前提
   (2) 结论引入规则: 在证明的任何步骤所得到的结论都可以作为后继证明的前提
   (3) 置换规则: 在证明的任何步骤，命题公式中的子公式都可以用等值的公式置换，得到公式序列的又一个公式
   由9条推理定律和结论引入规则可以导出以下各条推理规则
   (4) 假言推理规则(或分离规则): 若证明的公式序列中已出现过$A\to B$和$A$，则由假言推理定律$(A\to B)\land A \Rightarrow B$可知，$B$是$A\to B$和$A$的有效结论. 图示 $$\begin{matrix} A\to B\\ A\\ \hline \therefore B \end{matrix}$$ (5) 附加规则: $$\begin{matrix} A\\\hline \therefore A\lor B \end{matrix}$$ (6) 化简规则 $$\begin{matrix} A\land B\\\hline \therefore A \end{matrix}$$ (7) 拒取式规则 $$\begin{matrix} A\to B\\ \neg B\\\hline \therefore \neg A \end{matrix}$$ (8) 假言三段论规则 $$\begin{matrix} A\to B\\ B\to C\\ \hline \therefore A\to C \end{matrix}$$

…就是符号表示一下，不打了，一共到12

设前提$A_1,A_2,\cdots,A_k,$结论$B$和公式序列$C_1,C_2,\cdots,C_l$. 如果每一个$i(i=1,2,\cdots ,l)$,$C_i$是某个$A_j$或者可由序列中前面的公式应用推理规则得到，并且$C_l=B$，则称公式序列$C_1,C_2,\cdots,C_l$是由$A_1,A_2,\cdots,A_k$推出$B$的证明.

附加前提证明法： 推理形式结构 $(A_1\land A_2\land \cdots \land A_k)\to (A\to B)$，可以改写成$(A_1\land A_2\land \cdots \land A_k\land A)\to B$.
拆开可得到两式等值，若能证明后式为重言式则前式为重言式，称作附加前提证明法，$A$称作附加前提

将结论的否定式作为前提引入并推出矛盾式的证明方法称作归谬法

3.3 消解证明法

消解证明法是根据归谬法的思想吗，采用消解规则构造证明的方法，它的基本做法是把前提中的公式和结论的否定都化成等值的合取范式，以这些合取范式中的所有简单析取式作为前提，用消解规则构造证明。如果能得到空式，则证明推理是正确的

第4章 一阶逻辑基本概念

量词用来表达出个体与总体之间的内在联系和数量关系，这就是一阶逻辑所研究的内容
一阶逻辑也称作一阶谓词逻辑或谓词逻辑

4.1 一阶逻辑命题符号化

个体词是指所研究对象中可以独立存在的具体的或抽象的客体
将表示具体或特定的客体个体词称作个体常项，一般用小写英文字母$a,b,c$表示
将表示抽象或泛指的个体词称作个体变项，常用$x,y,z$表示，并称个体变项的取值范围为个体域(或论域)
个体域可以是有穷集合也可以是无穷集合
有一个特殊的个体域，它是由宇宙间一切事物组成的，称作全总个体域

谓词是用来刻画个体词性质及个体词之间相互关系的词，常用$F,G,H$表示
表示具体性质或关系的谓词称作谓词常项，表示抽象或泛指的性质或关系的谓词称作谓词变项

一般地，含$n(n\geqslant 1)$个个体变项$x_1,x_2,\cdots, x_n$的谓词$P$称作$n$元谓词，记作$P(x_1,x_2,\cdots,x_n)$
$n$元谓词是以个体域为定义域，以$\{0,1\}$为值域的$n$元函数或关系
将不带个体变项的谓词称作$0$元谓词

表示个体常项或变项之间数量关系的词称作量词
“一切的”，“所有的”，“每一个”，“任意的”，“凡”，“都”等词统称作全称量词，用符号$\forall $表示
“存在”，“有一个”，“有的”，“至少有一个”等词统称作存在量词，用符号$\exists $表示

特性谓词的作用是将个体变元局限止在满足该谓词代表的性质或关系的范围之内
若个体域为全总个体域，对个体变项的范围用医院特性谓词描述
特性谓词的使用规则
(1) 对于全称量词$\forall x$，其特性谓词作为蕴含式的前件加入
(2) 对于存在量词$\exists x$，其特性谓词作为合取式的合取项加入

当$F$是谓词常项时，$\forall xF(x)$是一个命题. 如果把个体域中的任何一个个体$a$代入，$F(a)$都为真，则$\forall xF(x)$为真；否则$\forall xF(x)$为假. $\exists xF(x)$也是一个命题. 如果个体域中存在一个个体$a$，使得$F(a)$为真，则$\exists xF(x)$为真；否则$\exists xF(x)$为假.

4.2 一阶逻辑公式及其解释

一阶语言是用于一阶逻辑的形式语言，一阶逻辑是建立在一阶语言上的逻辑体系.

个体常项符号、函数符号和谓词符号称作非逻辑符号，个体变项符号、量词符号、联结词符号和括号与逗号称作逻辑符号

定义4.2 $L$的项定义如下.
(1) 个体常项符号和个体变项符号是项
(2) 若$\varphi (x_1,x_2,\cdots,x_n)$是$n$元函数符号，$t_1,t_2,\cdots,t_n$是$n$个项，则$\varphi (t_1,t_2,\cdots,t_n)$是项
(3) 所有的项都是有限次使用(1),(2)得到的
定义4.3 设$R(x_1,x_2,\cdots,x_n)$是$L$的$n(n\geqslant 1)$元谓词符号，$t_1,t_2,\cdots,t_n$是$L$的$n$个项，称$R(t_1,t_2,\cdots,t_n)$是原子公式
定义4.4 合式公式的定义如下
(1) 原子公式是合式公式
(2) 若$A$是合式公式，则$(\neg A)$也是合式公式
(3) 若$A,B$是合式公式，则$(A\land B),(A\lor B),(A\to B),(A\leftrightarrow B)$也是合式公式
(4) 若$A$是合式公式，则$\forall xA,\exists xA$也是合式公式
(5) 只有有限次的应用(1)-(4)构成的符号串才是合式公式
$L$的合式公式也称作谓词公式，简称为公式
定义4.5 在公式$\forall xA$和$\exists xA$中，称$x$为指导变元，$A$为量词的辖域. $\forall x$和$\exists x$的辖域中，$x$的所有出现都称作约束出现，$A$中不是约束出现的其他变项均称作自由出现
定义4.6 设$A$是任意的公式，若$A$中不含自由出现的个体变项，则称$A$为封闭的公式，简称作闭式.

个体域及个体常项符号、函数符号、谓词符号的指定称作解释，指定自由出现的个体变项的值称作赋值

定义4.7 设$L$是由$L$生成的一阶语言，$L$的解释$I$由下面4部分组成
(a) 非空个体域$D_I$.
(b) 对每一个个体常项符号$a\in L$，有一个$\bar {a}\in D_I$，称$\bar {a}$为$a$在$I$中的解释.
(c) 对每一个$n$元函数符号$f\in L$，有一个$D_I$上的$n$元函数$\bar {f}:D^n_I\to D_I$，称$\bar {f}$为$f$在$I$中的解释.
(d) 对每一个$n$元谓词符号$F\in L$，有一个$D_I$上的$n$元谓词常项$\bar {F}$，称$\bar {F}$为$F$在$I$中的解释.
$I$下的赋值$\sigma$：对每一个个体变项符号$x$指定$D_I$中的一个值$\sigma (x)$.
设公式$A$，规定：在解释$I$和解释$\sigma$下

1. 取个体域$D_I$
2. 若$A$中含个体常项符号$a$就将它替换成$\bar {a}$.
3. 若$A$中含函数符号$f$就将它替换成$\bar {f}$.
4. 若$A$中含谓词符号$F$就将它替换成$\bar {F}$
5. 若$A$中含自由出现的个体变项符号$x$就将它替换成$\sigma (x)$
   把这样所得到的公式记作$A’$. 称$A’$为$A$在$I$和$\sigma$下的解释，或$A$在$I$和$\sigma$下被解释成$A’$
   定义4.8 设$A$为一公式，若$A$在任何解释和该解释下的任何赋值下均为真，则称$A$为永真式(或称作逻辑有效式). 若$A$在任何解释和该解释下的任何赋值均为假，则称$A$为矛盾式(或永假式). 若$A$在任何解释和该解释下的一个赋值使$A$为真，则称$A$是可满足式
   定义4.9 设$A_0$是含命题变项$p_1,p_2,\cdots,p_n$的命题公式，$A_1,A_2,\cdots,A_n$是$n$个谓词公式，用$A_i(1\leqslant i\leqslant n)$处处代替$A_0$中的$p_i$，所得的公式$A$称为$A_0$的代换实例.
   定理4.1 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式

第5章 一阶逻辑等值演算和推理

5.1 一阶逻辑等值式与置换规则

定义5.1 设$A,B$是一阶逻辑中任意两个公式，若$A\leftrightarrow B$是永真式，则称$A$与$B$等值，记作$A\Leftrightarrow B$. 称$A\Leftrightarrow B$是等值式.

1. 量词否定等值式
   (1) $\neg \forall xA(x)\Leftrightarrow \exists x\neg A(x)$
   (2) $\neg \exists xA(x)\Leftrightarrow \forall x\neg A(x)$
2. 量词辖域收缩与扩张等值式
   (1) $\forall x(A(x)\lor B) \Leftrightarrow \forall xA(x)\lor B$.
   $\forall x(A(x)\land B)\Leftrightarrow \forall xA(x)\land B$.
   $\forall x(A(x)\to B)\Leftrightarrow \exists xA(x)\to B$.
   $\forall x(B\to A(x))\Leftrightarrow B\to \forall xA(x)$.
   (2) $\exists x(A(x)\lor B)\Leftrightarrow \exists xA(x)\lor B$.
   $\exists x(A(x)\land B)\Leftrightarrow \exists xA(x)\land B$.
   $\exists x(A(x)\to B)\Leftrightarrow \forall xA(x)\to B$.
   $\exists (B\to A(x))\Leftrightarrow B\to \exists xA(x)$.
3. 量词分配等值式
   (1) $\forall x(A(x)\land B(x))\Leftrightarrow \forall xA(x)\land \forall xB(x)$.
   (2) $\exists x(A(x)\lor B(x))\Leftrightarrow \exists xA(x)\lor \exists xB(x)$.

规则

1. 置换规则 设$\Phi (A)$是含公式$A$的公式，$\Phi (B)$是用公式$B$取代$\Phi (A)$中所有的$A$之后所得到的公式. 那么，若$A\Leftrightarrow B$，则$\Phi (A)\Leftrightarrow \Phi (B)$.
2. 换名规则 设$A$为一公式，将$A$中某量词辖域中的一个约束变项的所有出现及相应的指导变元全部改成该量词辖域中未曾出现过的某个个体变项符号，公式中其余部分不变，将所得公式记作$A’$，则$A’\Leftrightarrow A$.

5.2 一阶逻辑前束范式

定义5.2 具有如下形式$Q_1x_1Q_2x_2\cdots Q_kx_kB$的一阶逻辑公式称作前束范式，其中$Q_i(1\leqslant i\leqslant k)$为$\forall $或$\exists $，$B$为不含量词的公式.
定理5.1(前束范式存在定理) 一阶逻辑中的任何公式都存在等值的前束范式.

5.3 一阶逻辑的推理理论

在一阶逻辑中，从前提$A_1,A_2,\cdots,A_k$出发推出结论$B$的推理的形式结构，依然采用如下的蕴含式形式$A_1\land A_2\land \cdots \land A_k\to B$. 若为永真式，则称推理正确，否则称推理不正确.
在一阶逻辑中称永真式的蕴含式为推理定律. 若一个推理的形式结构是推理定律，则这个推理是正确的.

后面关于自然推理系统的定义就不写了

第2部分

第5部分

参考

• 《离散数学（第2版）》，屈婉玲、耿素云、张立昂，高等教育出版社