离散数学 - 命题逻辑

一、命题与联结词

1.1 联结词的向量值函数理解

可以将联结词理解成一个 n 元函数，完成的是将 $\{0,1\}^n$ 到 $\{0,1\}$ 的映射，特别的，如果当 n 等于零的时候，可以预见，联结词函数退化成了一个常值函数，也就是 0 和 1 。所以 0 和 1 也被称为零元真值函数。

1.2 联结词的运算符理解

其实联结词还可以理解为运算符，比如合取就是变种的乘法，异或就是变种的加法，更往深里说，应该是运算符就是一种向量值函数。

二、公式和真值赋值

2.1 原子公式

命题变元被称为原子公式。

2.2 公式

当我们回顾公式的定义时，应该意识到，这是一个语法定义，其目的是为了描述一种特殊的字符串，这种字符串当被赋予意义以后，就可以来表明一个命题 。总之，要意识到公式没有意义，它只是一种形式。这也是原子公式概念的提出的意义，把命题变元过分强调的语义性质剥离掉。

公式的定义采用递归定义，也就是：

• 0 , 1 是公式。

• 原子公式是公式。

• 用逻辑联结词连接的公式是公式。

  突然想到，公式的递归定义跟树的递归定义是否有相似性呢。应该是有的，任何比较自然的字符串好像都是递归定义的。

  另外还要一个有 S 生成的公式 A 的概念，S 是联结词的集合，这样就可以对字符串有了进一步的限制。

2.3 真值赋值

从全体命题变元的集合到集合 $\{0,1\}$ 的函数，被称为真值赋值。这么说 v 也是一个向量值函数，自变量向量的维数就是命题变元的个数。也就是说，真值赋值为每个命题变元指定了真值。由此衍生出几个书写规范：

• $p^v$ 表示 v 赋给命题变元 p 的真值。
• $v(A)$ 表示 A 在真值赋值 v 下的值。
• $v=(p/1,q/0)$ 就是对 v 的解释，这个 v 把 p 赋成 1，把 q 赋成 0 。
• $v[p_1/q_1,\dots p_n/q_n]$ 不是 $v$ ，而是在 v 的基础上修改了一些

如果真值赋值 v 使得 $v(A)=1$ ，那么称 v 满足 A。

2.4 变元相关性定理思考

设 A 是公式，$v_1，v_2$ 是真值赋值，对于 A 中出现的每个命题变元 p，$p^{v_1}=p^{v_2}$ ，则 $v_1(A)=v_2(A)$ 。

这个定理看似再说 $v_1,v_2$ 其实说的是，真值赋值决定且唯一决定了 A 的值，这与 “证明唯一性的时候证明存在 a，b 满足条件且 a = b” 一样，都是描述的手段。

2.5 可满足式，永真式，重言式，矛盾式，不可满足式，永假式

如果每一个真值赋值 v 都满足 A 。那么称 A 是永真式，也称重言式，重言式的提出可能是为了后面区分谓词逻辑做准备。

如果每一个真值赋值都不满足 A 。那么 A 也称永假式、矛盾式、不可满足式。

如果至少有一个真值赋值满足 A 。则称 A 是可满足式。

可以看到，命题逻辑里的公式的语义和语法的区分不太明显，语法基本上不强调，似乎因为命题变元的变化太少。

2.6 可判定与可解

如果 S 是一个公式集合且包含于 W 中，P 是一个程序，且 P 满足以下条件：

1. P 以 W 中元素为输入量
2. 当输入的是 S 中的元素时，P 运行终止且输出 “是”。
3. 当输入的不是 S 中的元素时，P 运行终止且输出 “否”。

称 P 解 S 的判定问题，如果有一个程序解 S 的判定问题，就称 S 的判定问题是可解的。它这个定义总给我感觉是一个语法定义，好像计算机没有办法知道自己在干什么一样。

三、等值演算和对偶定理

3.1 总论

等值演算是说的是不同公式之间的等价关系，具体就表现在无论是哪个真值赋值，两个公式的值都是相同的。而对偶和对偶定理的提出，其实是对等值式模式的一种总结。他自己并不能作为等值模式的一种，是更高一维的东西。

3.2 等值式模式

3.2.1 思考

等值式模式错综复杂，那么什么是重要的呢？我认为涉及 $\vee, \wedge, \neg$ 的是重要的，因为在这一章的最重头戏是范式，而范式必须处理成含 有上述三种联结词的公式，所以比较重要。而如果抛开做题来看的话，研究各种联结词是怎样与 01 作用的显然更有用，因为在利用位运算的时候会用到。

3.2.2 分配律

$$\begin{aligned} A\vee(B\wedge C)\Leftrightarrow (A\vee B)\wedge(A \vee C)\\ A\wedge(B\vee C)\Leftrightarrow (A\wedge B)\vee(A \wedge C)\\ A\wedge(B\oplus C)\Leftrightarrow (A\wedge B)\oplus(A \wedge C) \end{aligned}$$

在异或是并不对偶的，我也没有办法，只能死记了。

3.2.3 吸收律

$$\begin{aligned} A\vee(A\wedge B)\Leftrightarrow A\\ A\wedge(A\vee B)\Leftrightarrow A \end{aligned}$$

这个东西乍看之下好像是可以用分配律轻松获得的，但是我推导了一下，还是不是那么显然的。

3.2.4 德摩根律

$$\begin{aligned} \neg(A\vee B)\Leftrightarrow\neg A\wedge\neg B\\ \neg(A\wedge B)\Leftrightarrow\neg A\vee\neg B \end{aligned}$$

3.2.5 化归律

$$\begin{aligned} A\rightarrow B \Leftrightarrow \neg A\vee B\\ A\leftrightarrow B\Leftrightarrow(A\rightarrow B)\wedge(B\rightarrow A)\\ A\oplus B\Leftrightarrow(A\wedge \neg B)\vee(B\wedge \neg A) \end{aligned}$$

名字是我瞎起的，主要是为了说明其他联结词与上述三个联结词之间的转换。

3.3 对偶

设 A 是有 $\{0,1,\neg,\vee,\wedge\}$ 生成的公式，将 A 中的 $\vee$ 和 $\wedge$ 互换，0 和 1 互换，就可以得到 $A^\prime$ ，$A$ 和 $A^\prime$ 互为对偶式。

对于相反的真值赋值，对偶式满足

$$v(A)=\neg v^\prime(A^\prime)$$

3.4 对偶定理

如果 $A\Leftrightarrow B$，则 $A^\prime\Leftrightarrow B^\prime$，他可以使记忆的数量减少。

四、范式

4.1 文字

原子公式和原子公式的否定被称为文字。

4.2 简单析取合取式

有且只有文字组成的析取式或者合取式被称为简单析取合取式。

4.3 极大项与极小项

极大项与极小项是从简单析取式合取式中衍生出的概念，设存在一个原子公式集合 $\{p_1\dots p_n\}$ ，那么如果一个简单析取式里的每一项都有这个集合里的元素的文字组成，且每个元素都出现且只出现一遍，那么就称这个简单析取式为这个集合的极大项，极大项具有唯一使其为假的真值赋值，反之，则可以定义极小项，极小项具有唯一使其为真的真值赋值。

极小项可以抽象出一个向量与他对应，比如 $p\wedge q\wedge\neg r$ 可以对应 $(1,1,0)$ ，这个向量是唯一使极小项的值取 1。这是极为自然的，因为它海哥前面有没有否定符号有关，我们只要看前面没有否定符号，就认为是 1，而有否定符号，就认为是 0，但这其实不是有道理的，顶多算是一种做题技巧。

极大项也可以抽象出一个向量，但是 $p\wedge q\wedge\neg r$ 对应的不是 $(1,1,0)$，而是 $(0,0,1)$ 这个向量是唯一使极大项取值为 0 的向量，这才叫一一对应。

4.4 析取合取范式

如果组成析取式和合取式的公式均是简单合取式析取式，则称为范式。

有 0 是 0 个公式的析取，1 是 0 个公式的合取。

4.5 主范式

如果析取式的所有组成项都是极小项，那么他就是一个主析取范式。

如果合取式的所有组成项都是极大项，那么他就是一个主合取范式。

4.6 主范式与真值表

不难想到，主范式里面的极大项和极小项与输入向量有对应关系，具体的对应关系是这样的。

主析取范式里面对应的所有向量值和主合取范式里面对应的所有向量值的没有重复，也没有遗漏，刚好就是所有输入向量的可能取值，举个例子

$$A=(\neg p\rightarrow r)\wedge(q\leftrightarrow p)$$

列出真值表

p	q	r	$(q\leftrightarrow p)$	$(\neg p\rightarrow r)$	$(\neg p\rightarrow r)\wedge(q\leftrightarrow p)$
1	1	1	1	1	1
1	1	0	1	1	1
1	0	1	0	1	0
1	0	0	0	0	0
0	1	1	0	1	0
0	1	0	0	1	0
0	0	1	1	1	1
0	0	0	1	0	0

A 的主析取范式是

$$(\neg p\wedge\neg q\wedge r)\vee(p\wedge q\wedge\neg r)\vee( p\wedge q\wedge r)$$

恰好就对应三个可以使 A 为 1 的向量。

A 的主合取范式是

$$(p\vee q\vee r)\wedge(p\vee\neg q\vee r)\wedge(p\vee\neg q\vee\neg r)\wedge(\neg p\vee q\vee r)\wedge(\neg p\vee q\vee\neg r)$$

恰好就是对应三个使 A 为 0 的向量，但是需要注意的是，对应规则不可以搞混，不是看有没有否定符号（其实最快的办法就是看有没有），本质是看使极大项赋值为 0 的量。

在教材中，他没有明确指出相同公式的极大项和极小项间的关系，他在已知主合取范式后依然采用的是先用自然语言描述一下非 A，然后在迂回不清的说了怎么求 A 的主析取范式，这显然是不好的。真正的方法应该是像上述一样的。

在有了这个知识后，我们就可以用主范式来分析公式的性质了，当公式为永真式的时候，那么他取值恒为 1，那么他就有 $2^n$ 个极小项，没有极大项，那么他的主析取范式就有 $2^n$ 项，主合取范式就有 0 项，那么显然主合取范式与原公式等值，所以主合取范式必须是 1，这也是 1 是 0 个公式合取的由来。当公式为永假式的时候，他的取值恒为 0，那么最后他的主合取范式会有 $2^n$ 项，主析取范式就有 0 项，为了保证等值，就需要说明 0 是 0 个公式的析取。

最后补充一下我的直观理解，我想了两种方法，都还不错。一种是运算符，如果把合取理解成乘法，那么只有每一个乘项都不为 0，他才能不为 0，有点像多项式连乘的感觉，主合取范式就是分解出根的 $(x-x_1)(x-x_2)$ 只有取 $x=x_1,x=x_2$ 的时候才有 0 值出现，这么看的话，讲一个公式化为主合取范式的过程就是分解因式。而析取可以理解为加法，或者是加法和大于 0 的不等式的结合 $(x-x_1)^2+(x-x_2)^2>0$ 就是很好的例子，这种理解可以很好的解释 0 个项的情况。另一种理解是把他理解为电路，对于主合取范式来说，可以把它理解为一根电线，里面的项就是这个导线上的元件，显然没有元件的时候电路是导通的，所以有电流流过，取值为 1。对于主析取范式，可以把他的项理解为一条并联支路，如果项为 0，那么就没有电流流过了。

五、联结词完全集

5.1 完全集

显然有了范式的铺垫，那么 $\{\vee, \wedge, \neg\}$ 显然是完全集了，证明方法就是范式的意义。但是它不是最小完全集。

5.2 最小完全集

$\{\neg,\vee\},\{\neg,\wedge\},\{\neg,\rightarrow\}$ 是比较常见的最小完全集，如果想证明一个集合是完全集，只需要用已知完全集里的元素去表示这个集合里的联结词就好了，而如果想证明时最小完全集，就必须去掉一个元素以后证明这个集合不是完全集，证明不是完全集的方法就是找到一个联结词 F，然后发现用现在这个集合里的联结词没法表示他。

可以看到，无论是两种证明中的哪一种，都必须涉及表示，我们这么说表示，如果想要表示一个 n 元联结词 F，那么只能用 n 个不同命题的变元，但是并不限制相同命题变元在公式中出现的次数（不出现到出现很多次），结合已知联结词，看看能不能表示 F 的真值表，但是因为有了出现次数不限的条件，是没有办法爆算出来的，大部分时候是要观察 F 的真值表具有的性质，而用已知联结词没法表示的性质。所以解法难且不唯一。对 F 的选择也很讲究。