发布日期: 2025-04-19

更新日期: 2025-04-22

文章字数: 5k

离散数学 Chap.1 逻辑与证明

本系列离散数学博文基于Youtube易志偉老师的免费课程整理而来, 目的在于系统的梳理计算机专业课的基础知识, 并为将来的面试做好充分的准备.
除本系列外, 计算机考研相关还包括数据结构 / 操作系统 / 计算机组成原理 / 计算机网络的相关内容.

引子, 为什么要学离散?

在开始梳理前, 稿主认为有必要明确, 离散数学在计算机体系中占据一个怎样的地位?

尤其是, 离散数学甚至不在408的考试范围内, 为什么要学这门课?
以笔者的理解, 离散数学为计算机的很多结构建立了 基本模型 , 并在其上提出了很多解决关于该模型问题的 通用方法 . 在今后的学习中, 很多情况下我们离不开这些模型.

本博文不太像知识的梳理, 更多的是博主根据课程内容与自己的理解进行的知识概述, 希望能对读者的学习过程有所帮助.

1.1 逻辑

离散数学为什么要先讲逻辑呢? 因为计算机的很多功能脱不开逻辑, 如果脱离了逻辑, 那计算机就不能叫计算机了, 该叫计算器.

1.1.1 命题

首先, 需要明确几个概念:

概念: 命题(Propositions) / 命题的真值(Truth Value)
命题指一个可以 明确判别真假 的 陈述句 .
命题的真假 指这个命题到底 是真是假(True or False) .

请读者注意, 命题一定要有两层意思在里面:

它是有 对错之分的 , 也就是说, 你一看到它就能觉得这东西有对错.
它是 能明确判别真假的 .

例子: 命题 / 非命题
命题: $ 2+3 = 5 $ ; $ 5+7=10 $ ; 星期二的下一天是星期三.
非命题: $ x+3 = 5 $ ; 你好! ; 我是学生, 请给我钱.

那问题来了, 上面的命题还挺短的, 如果命题贼长, 那每次都要写一遍也太费劲了, 所以给了个东西叫 命题变量(Propositional Variables)

概念: 命题变量(Propositional Variables)
指可以代表一个命题的一个变量.

其实说白了就是把一个句子用一个字母指代一下.

注意: 命题变量请务必用小写字母来表示

所以, 命题被定义出来了, 就可以被组合起来计算了, 因此有个单独的模块叫 命题计算(Propositional Calculus) .

计算的话, 通常不会对单独一个命题进行计算, 那太简单了. 所以出现了 复合命题 .

概念: 复合命题(Compound Proposition)
即被多个命题以及逻辑运算组合而成的新命题.

例子: 复合命题
北京是中国的首都, 并且北京在中国的华北地带.
这就是两个命题的组合.

这个概念不难, 但重要在其中有个要求, 就是必须用 逻辑运算(也叫逻辑算子 / Logical Operators) 给它们串起来. 那有哪些逻辑运算呢 ?

1.1.2 逻辑运算符

1.1.2.1 非(Negation / Not)

概念: 非(Negation)
$ p $ 是一个命题, 则通常用 $ \neg p $ 或 $ \overline{p} $ 来表示非p . 即p的否定.

说白了, 其表达的意思就是 p是错的(Is not the state of p.). 这意味着 $ p $ 与 $ \neg p $ 的 真值是相反的 .

1.1.2.2 且(Conjunction / And)

概念: 且(Conjunction)
$ p, q $ 是两个命题, 则通常用 $ p \land q $ 来表示 p且q .

意思是 只有p和q均为真, p且q才为真 . 画个真值表:

$$
\begin{array}{|c|c|c|}
\hline
p & q & p \land q \\
\hline
T & T & T \\
T & F & F \\
F & T & F \\
F & F & F \\
\hline
\end{array}
$$

1.1.2.3 或(Disjunction / Or)

概念: 或(Disjunction)
$ p, q $ 是两个命题, 则通常用 $ p \lor q $ 来表示 p或q .

意思是 只有p和q均为假, p或q才为假 . 画个真值表:

$$
\begin{array}{|c|c|c|}
\hline
p & q & p \lor q \\
\hline
T & T & T \\
T & F & T \\
F & T & T \\
F & F & F \\
\hline
\end{array}
$$

1.1.2.4 异或(Exclusive OR / XOR)

我们先给真值表:

$$
\begin{array}{|c|c|c|}
\hline
p & q & p \oplus q \\
\hline
T & T & F \\
T & F & T \\
F & T & T \\
F & F & F \\
\hline
\end{array}
$$

概念: 异或(Exclusive OR)
$ p, q $ 是两个命题, 则通常用 $ p \oplus q $ 来表示 p异或q .

意思是只有二者不同时, 异或才为真.

1.1.2.5 条件运算符(Conditional Operator / Only if)

概念: 条件运算符(Conditional Operator)
$ p, q $ 是两个命题, 则通常用 $ p \to q $ 来表示 若p则q .

给出真值表:

$$
\begin{array}{|c|c|c|}
\hline
p & q & p \to q \\
\hline
T & T & T \\
T & F & F \\
F & T & T \\
F & F & T \\
\hline
\end{array}
$$

这里显然可能有些反常识, 因为 $ p $ 为假时, 该命题也为真. 这是因为当 $ p $ 前提都不满足, 则我们自然无法明确 $ p $ 与 $ q $ 的逻辑关系, 因此此时我们认为这种命题是对的.

用一种更广泛令人接收的说法:

若 $ p \to q $ , 则 $ p $ 是 $ q $ 的充分条件 , $ q $ 是 $ p $ 的必要条件 .

注意: 条件运算符的各种说法
我去, 这玩意能说的方法可太多了, 什么if, unless, only if, … 读者就细品吧, 这东西挺多样的 :(

我们这里扩展一下, 多写一些东西:

$$
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
p & q & \neg p & \neg q & p \to q & q \to p & \neg p \to \neg q & \neg q \to \neg p \\
\hline
T & T & F & F & T & T & T & T \\
T & F & F & T & F & T & T & F \\
F & T & T & F & T & F & F & T \\
F & F & T & T & T & T & T & T \\
\hline
\end{array}
$$

哎嘿, 这后面四列怎么有点相似呢是不是. 这种情况通常用一个三等于来表示:

$$ (p \to q) \equiv (\neg q \to \neg p) $$

$$ (q \to p) \equiv (\neg p \to \neg q) $$

这里就是提一下, 具体我们下一节再唠.

1.1.2.6 双条件运算符(Biconditional Operator)

概念: 双条件运算符(Biconditional Operator)
$ p, q $ 是两个命题, 则通常用 $ p \leftrightarrow q $ 来表示 p q必须同时成立 .

事实上, 它有另一种表达方式:

$$ (p \leftrightarrow q) \equiv (p \to q) \land (q \to p) $$

那意思很简单, 就是前键跟后键必须相同, 这个式子才成立.

给个真值表:

$$
\begin{array}{|c|c|c|}
\hline
p & q & p \leftrightarrow q \\
\hline
T & T & T \\
T & F & F \\
F & T & F \\
F & F & T \\
\hline
\end{array}
$$

1.1.2.7 运算符的优先权

直接给个表:

$$
\begin{array}{|c|c|}
\hline
operator & priority \\
\hline
\neg & 1 \\
\land & 2 \\
\lor & 3 \\
\to & 4 \\
\leftrightarrow & 5 \\
\hline
\end{array}
$$

给个记忆方式, 其实 $ \neg $ 类似于数学运算中的 $ - $ (负号) , $ \land $ 类似于 $ \times $ (乘) , $ \lor $ 类似于 $ + $ (加) , 剩下俩是逻辑运算, 在它们之后.

1.2 逻辑等价

逻辑等价(Propositional Equivalences) , 即通过一些正确的关系, 来将一个复杂的逻辑表达式化简为比较简单的表达式的过程.

给两个定义:

概念: 永真式 / 重言式(Tautology)
一个复合逻辑命题, 它永远为真.

概念: 矛盾式(Contradiction)
一个复合逻辑命题, 它永远为假.

例子: 永真式 / 重言式

$$
\begin{array}{|c|c|c|c|}
\hline
p & \neg p & p \land \neg p & p \lor \neg p \\
\hline
T & F & F & T \\
F & T & F & T \\
\hline
\end{array}
$$

所以, 我们给出 逻辑等价 的定义:

概念: 逻辑等价(Propositional Equivalences)
$ p, q $ 是两个命题, 如果 $ p \leftrightarrow q $ 是一个永真式, 则称 $ p, q $ 逻辑等价, 记作: $ p \equiv q $ .

例子: 逻辑等价

$$ (p \to q) \equiv (\neg q \to \neg p) $$

$$ (q \to p) \equiv (\neg p \to \neg q) $$

1.2.1 常用的逻辑等价关系

注意: 逻辑等价的证明方法
底下这一堆, 其实证明方式都是 画真值表 . 容笔者犯个懒, 读者如果想证明就自己画一下就好.

1.2.1.1 恒等律(Identity Laws)

$$ p \land True \equiv p $$

$$ p \lor False \equiv p $$

应该好理解, 上面是乘1, 下面是加0.

1.2.1.2 支配律(Domination Laws)

$$ p \lor True \equiv True $$

$$ p \land False \equiv False $$

一个道理, 上面是加1, 下面是乘0.

1.2.1.3 幂等律(Idempotent Laws)

$$ p \land p \equiv p $$

$$ p \lor p \equiv p $$

自己乘自己和自己加自己.

1.2.1.4 双重否定(Double Negation)

$$ \neg (\neg p) \equiv p $$

负负得正.

1.2.1.5 结合律(Associative Laws)

俩式子:

$$ (p \land q) \land r \equiv p \land (q \land r) $$

$$ (p \lor q) \lor r \equiv p \lor (q \lor r) $$

1.2.1.6 交换律(Commutative Laws)

俩式子:

$$ p \land q \equiv q \land p $$

$$ p \lor q \equiv q \lor p $$

1.2.1.7 分配律(Distributive Laws)

$$ p \land (q \lor r) \equiv (p \land q) \lor (p \land r) $$

$$ p \lor (q \land r) \equiv (p \lor q) \land (p \lor r) $$

还记得笔者说的记忆逻辑运算的方法吗, 把 $ \lor $ 记成加法, 把 $ \land $ 记成乘法.
加法和乘法是不是有交换律 / 结合律 / 分配律?
这里一个意思.

1.2.1.8 德摩根律(De Morgan Laws)

德摩根律有两个式子:

$$ \neg(p \lor q) \equiv \neg p \land \neg q $$

$$ \neg(p \land q) \equiv \neg p \lor \neg q $$

1.2.1.9 吸收率(Absorption Laws)

$$ p \land (p \lor q) \equiv p $$

$$ p \lor (p \land q) \equiv p $$

1.2.1.10 永真律 / 矛盾律(Nogation Laws)

$$ p \land \neg p \equiv False $$

$$ p \lor \neg p \equiv True $$

1.2.1.11 关于条件运算符

$$ p \to q \equiv \neg q \to \neg p $$

$$ p \to q \equiv \neg p \lor q $$

还有些过于复杂的玩意, 咱就不写了.

1.2.1.12 关于双条件运算符

$$ p \leftrightarrow q \equiv (p \to q) \land (q \to p) $$

$$ p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q) $$

$$ p \leftrightarrow q \equiv \neg p \leftrightarrow \neg q $$

1.2.2 逻辑运算

上面一大堆, 但是实际上读者做熟练了会发现一个常用的原则.

一般而言, 最优先处理的永远是这俩玩意: $ \to $ 或 $ \leftrightarrow $ . 因为这俩玩意在式子里面搞得逻辑关系挺乱的. 那怎么处理?
$ p \to q \equiv \neg p \lor q $
$ p \leftrightarrow q \equiv (p \to q) \land (q \to p) $
$ p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q) $

这种俩费劲的玩意倒腾完之后就可以直接套别的公式了.

本处实际上就是公式的运用, 实在没什么可以说的, 读者就自行找些题目练习一下就好.

1.3 谓词逻辑

谓词逻辑(Predicate Logic) , 相比于我们之前的内容更进一步, 能够更方便的表示一些很麻烦的玩意, 我们给个例子.

例子: 谓词逻辑
假如你现在要表示这么个意思, 你们班上的所有人年龄都大于18岁 .
我们只用我们之前学的, 会发现这东西太麻烦了, 我得一个个把人都列出来, 然后写出所有人的这个陈述: <人名>的年龄大于18岁 .
这太费劲了.

因此, 可以引入一些如 $ P(x) $ 的谓词以及两个量词 $ \forall, \exists $ , 来表示上面这个意思.

啥是谓词?

概念: 谓词(Predicate)
简单来说, 谓词就是一个陈述句模板, 它把原本陈述句中的名词(或判断对象)转变为了一个变量 .
这样的话就很好理解, 谓词本身是 没有对错的 . (都有不确定变量了还怎么判断对错)
而经过填充后, 谓词才能形成一个命题, 进而被判断对错.

那继续下一个问题, 我们怎么填充谓词? 先给出这俩量词的含义:

概念: 全称量词( $ \forall $ )
$ \forall P(x) $ 表示在指定的域中, 每一个元素x都使谓词P(x)为真.

概念: 存在量词( $ \exists $ )
$ \exists P(x) $ 表示在指定的域中, 至少有一个元素x都使谓词P(x)为真.

回到最开始的问题, 我可以这么设置:
$ P(x) $ : $ x $ 在你们班, 且年龄大于18岁.
$ \forall x P(x) $ .

读者品一下, 是不是就是最开始那个命题的意思?

关于两个量词的展开式

其实两个量词更像一种简写, 它们是可以被展开的:

$$ \forall xP(x) \equiv P(x_1) \land P(x_2) \land … \land P(x_n) $$

$$ \exists xP(x) \equiv P(x_1) \lor P(x_2) \lor … \lor P(x_n) $$

那我们再想想, 是不是这个式子就成立(用德摩根律):

$$
\begin{align*}
\neg (\forall xP(x)) & \equiv \neg (P(x_1) \land P(x_2) \land … \land P(x_n)) \\
& \equiv \neg P(x_1) \lor \neg P(x_2) \lor … \lor \neg P(x_n) \\
& \equiv \exists (\neg P(x))
\end{align*}
$$

另一个也成立, 这里就不写了(懒):

$$ \neg (\exists xP(x)) \equiv \forall x (\neg P(x)) $$

这俩玩意我们用人话解释一下, 意思就是:

所有x都满足条件 的否定命题是 存在x不满足条件 .
存在x满足条件 的否定命题是 所有x都满足条件 .

是不是顺口多了 :)

再往后, 我们还要明确一下这俩量词的优先级, 扩充一下表:

$$
\begin{array}{|c|c|}
\hline
operator & priority \\
\hline
\forall, \exists & 1 \\
\neg & 2 \\
\land & 3 \\
\lor & 4 \\
\to & 5 \\
\leftrightarrow & 6 \\
\hline
\end{array}
$$

这俩玩意的优先级 非常非常高 , 甚至比 $ \neg $ 还要更加优先一些.

还有一些比较麻烦的事情, 我们在这里一并说一下, 我们假设 $ P(x, y) $ 意思是 x喜欢y , x, y的取值范围是班上的人, 请读者比较一下下面几个式子:

$ \forall x \forall y P(x, y) $ : 班上所有同学都互相喜欢
$ \exists x \exists y P(x, y) $ : 班上存在一对同学, 其中一个喜欢另一个
$ \forall x \exists y P(x, y) $ : 班上所有的人都有另一个喜欢的人
$ \exists y \forall x P(x, y) $ : 班上有一个人被其它所有同学都喜欢着
$ \exists x \forall y P(x, y) $ : 班上有一个人喜欢其它所有人
$ \forall y \exists x P(x, y) $ : 对于班上的所有人, 都能找到另一个人喜欢自己

希望通过这一堆例子, 能跟读者说明白, 量词的顺序是很重要的! , 往往不同量词的顺序会产生截然不同的效果.

另外一个需要注意的点, 即这种东西:

$$ \forall x (P(x) \to Q(x)) $$

只有加了 $ \forall x $ 后面那一层的括号之后, 才能代表x的作用范围是后面这一整条语句. 因此读者在书写或化简时, 请注意括号的使用, 不要漏掉它.

1.4 推理与证明

1.4.1 这是个啥?

我们前面捣鼓了那么半天, 其实真正的目的就在这, 我们要尝试着根据我们知道的一些事情, 用我们学过的一些玩意, 推导出一些我们不知道, 或者需要证明的一些事情.

上面这个过程有两个更加正式的词语来定义它:

概念: 前提(Premises)
从本质上来讲, 就是 若干个命题 . 这些命题是我们已知的, 且真值一定为真.

概念: 结论(Conclusion)
其实也是一个或多个命题, 这个命题是我们需要证明的.

所以我们其实可以把我们的目标写成这个样子, 假设前提为 $ p_1, p_2, …, p_n $ , 结论为 $ q $ , 我们希望证明:

$$ (p_1 \land p_2 \land … \land p_n) \to q $$

是个 永真式 .

1.4.2 我们怎么做?

首先需要肯定的是, 我们其实前面已经写了挺多的公式, 这已经为我们做推理造就了很好的条件. 但问题在于, 它们太基础了, 因此我们这里还得给一些更加常用的推理公式:

肯定前键式: $ [p \land (p \to q)] \to q $ , p为真, p能推出q, 那q一定为真.
否定后键式: $ [\neg q \land (p \to q)] \to \neg p $ , q为假, p能推出q, 那p一定为假.
假言三段论: $ [(p \to q) \land (q \to r)] \to (p \to r) $ , p能推出q, q能推出r, 那p一定能推出r.
选言三段论: $ [(p \lor q) \land \neg p] \to q $ , p或q是真的, 但p是假的, 那q一定是真的.
加法规则: $ p \to (p \lor q) $ , p是真的, 则p或上任何一个命题都一定是真的.
简化规则: $ (p \land q) \to p $ , p和q是真的, 那p(q也一样)一定是真的.
合取规则: $ [(p) \land (q)] \to (p \land q) $ , p是真的, q是真的, 那 p和q 也是真的.
归结规则: $ [(p \lor q) \land (\neg p \lor r)] \to (q \lor r) $ , p或q是真的, 非p或r是真的, 那q和r一定有一个真的.

希望读者能理解, 上面的式子笔者尽可能每一个都给出一个比较 通俗易懂 的解释, 但真要证明的话, 还是需要使用我们在 1.2 中唠叨完的式子来证明的. 笔者这里就不证明了 ~~(哥们, 用Markdown写完整证明, 真能把人写裂开)~~

到此, 其实逻辑部分我们能讲的知识就差不多了, 其余的工作, 就是留给读者的 灵活运用 , 那就不是笔者能做到的工作了对吧 :)

1.4.3 额外补充, 关于条件表达式的证明法

很遗憾, 最后我们还是逃不开这个条件表达式, 这东西在逻辑里面实在是太常见了. $ p \to q $ , 如果让我们得到这个结论, 我们该怎么整?
当然, 上述章节中我们提到的方法理论上一定可行对吧, 这叫做 直接证明(Direct Proof) , 我们假设p为真, 随后只要根据其它的前提得到q就可以.

但很现实的一点是, 有时候直接证明是很困难的一件事. 因此, 这里给出其余几种思路;

逆否证明(Proof by Contraposition) : 即证明结论的一个 等价命题 , 在上例中, 我们也可以证明 $ \neg q \to \neg p $ .
反证法(Proof by Contradiction) : 即 假设结论是假的 , 随后如果能推出与前提的矛盾, 则说明结论是真的. 上例中, 我们可以假设 $ p \land \neg q $ 为真, 随后再尝试推出其与其它前提的矛盾即可.
空泛证明 / 平凡证明(Vacuous and Trivial Proof) : 这种情况专门针对结论的一部分进行证明. 在上例中, 假如我们能证明 $ p $ 永远是假的(矛盾式) 或者 $ q $ 永远是真的(重言式) . 那自然结论一定是真的.