命题逻辑入门：从基础概念到实际应用
命题逻辑入门：从基础概念到实际应用
命题逻辑是离散数学中的一个重要分支，它研究如何通过逻辑运算符对命题进行演算。本文将从命题的定义出发，介绍命题演算的基本运算规则，以及其在计算机科学中的应用，包括系统规范、布尔搜索和逻辑谜题等。
前言
离散数学是数学的一个分支，具体但简单点，即是研究逻辑演算的一个数学分支。一般来说，如果确定了一个数学语句为真的，那么它就可以被称作定理。离散数学在很多领域都有重要的应用，尤其在计算机领域。比如说我们可以判断算法是否正确，系统的安全性以及人工智能等等。
命题
命题有两个特点：
- 陈述句
- 可以判断真假
离散数学使得依据命题的逻辑可以演算，这种依据命题的演算我们称之为命题逻辑或者命题演算。基于此，在离散数学领域，命题可以是变量，因为演算的形式为变量。通常用p，q，r，s...来表示。
既然可以演算，就涉及到单位。这里的单位通常是指最小量，而非自然科学所指的单位。比如1是整数域的单位。所以这涉及到原子命题的概念，即：
[如果一个命题不能被比它更小的命题表达，那么这样的命题被称为原子命题。 ]
我们可以通过已知的命题构造新的命题，这种新的命题被称为复合命题。
命题演算
构造复合命题也就是命题演算，既然是演算就要有新的运算规则，正如加减乘除一样。引入新的运算规则不能局限于形式逻辑，它也是现实观察的最一般的，所有人都清楚的道理。正如1+1=2一样，这是不言自明的，如果要对它进行证明，现代数学也完全没有问题，但就其目前所需要的精度并不需要。
四个基础的逻辑运算符——非，且，或，异或的真值如下。
除了四个基本的逻辑运算符以外，还有条件语句这种命题演算，其真值如下。
条件语句的情况复杂一些，因为它涉及到否命题，反命题，逆反命题。可以通过真值表得出如下结论。
[原命题与逆反命题具有相同的真值，否命题与反命题具有相同的真值。 ]
如果一个命题与另一个命题互为条件，则其复合命题称为双条件语句，如图。
双条件语句用自然语言表述为“当且仅当”，所以双条件语句可以用另外一种数学语言表述。
[p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p) ]
我们在证明双条件语句时通常也是采用这种方法。
在一般的关于命题真值表述是采用T或F，如果是在计算机相关领域中则采用1或0表述，如图。其中的1或0我们称为比特运算符。
基本逻辑运算符的优先级
模糊逻辑
除了精确的逻辑，还有模糊的逻辑，这种称为模糊逻辑。模糊逻辑的真值是用数值表示的，它的取值在0和1之间，0表示假，1表示真。所以模糊逻辑的命题演算略有不同。假设p表示一个模糊逻辑的命题，则非演算如下。
[\lnot p = 1 - p ]
如果q也是一个模糊逻辑的命题，则且演算如下。
[p \land q = min(p, q) ]
或演算如下。
[p \lor q = max(p,q) ]
系统规范
系统规范是命题演算的一个比较典型的应用。在硬件工程与软件工程当中常常涉及到系统规范，因为这样的工程通常使用自然语言描述，而我们需要将自然语言转换为逻辑语言以此来判断这个工程的描述中是否有错误。只要这些自然语言是一致的，那么就是规范的。示例如下。
诊断信息要么被存储在缓冲区要么被重新发送
诊断信息不会被存储在缓冲区
如果诊断信息被存储在缓冲区，那么它会被重新发送
令(p)表示诊断信息被存储在缓冲区，(q)表示诊断信息被重新发送。所以这三条语句可以用命题表示为
[p \lor q,\lnot p,p \rightarrow q ]
(p)为假时，(\lnot p)为真。此时(p \rightarrow q)一定为真，欲使(p \lor q)为真，则(q)必须为真。所以这三者是一致的，符合系统规范的要求。
系统规范的一个作用是在开始一个工程或项目前我们就可以知道在逻辑上它成不成立，进而判断是否要开始工作，所谓磨刀不误砍柴工。
布尔搜索
布尔搜索常常应用于浏览器搜索中，多数搜索引擎也支持布尔搜索。同样，它也是基于基本的命题演算而来。主要有三个关键字构成——AND，OR，NOT。它们分别对应且，或，非演算。这里以谷歌为例。在搜索框中输入旅游城市 AND 中国，则搜索结果同时符合旅游城市与中国两个要求。其余两个同理。
初识逻辑谜题
命题演算的另一个应用就是逻辑谜题，逻辑谜题的内容比较多，有时常常涉及到命题等价。解决逻辑命题的一般思路如下。
- 将自然语言转化为逻辑语言（命题）
- 将命题做必要拆分，确定好原子命题
- 将各个命题用命题变量表示，复合命题一般用逻辑运算符连接
- 经过命题演算，得出一个最终的表达式，这个表达式可以判断最终的真假
为什么是初始逻辑谜题，那是因为命题演算中常常要涉及到命题等价式，这在下一节中才会提到。一个例子如下。
现有三个箱子，只有一个箱子有财宝，每个箱子上都写有一句提示语但是只有一个提示语是真的，你可以根据提示语选择哪个箱子。你只有一次机会选择一个，若有财宝则可获得。为方便描述，箱子风别被标记为A、B、C。提示语分别如下。A：这个箱子什么也没有；B：这个箱子没有财宝；C、箱子B有财宝。
解：我们的目的是为了选择有财宝的箱子，这个箱子什么都没有等价于没有财宝，至于这个箱子没有财宝是否有其它东西不是我们所在意的。令(p)表示箱子A有财宝，(q)表示箱子B有财宝，(r)表示箱子C有财宝。所以这三个箱子的提示语可以被分别表示为(\lnot p)，$ \lnot q(，)q$。因为只有一个箱子有财宝，所以有三种情况，要么A，要么B，要么C。这三种情况用命题表示如下。
[(\lnot p \land \lnot(\lnot q) \land \lnot q) \lor (\lnot(\lnot p) \land \lnot q \land \lnot q) \lor (\lnot(\lnot p) \land \lnot(\lnot q) \land q) ]
整个式子由三个分式构成，分式之间用或连接，这是因为存在三种情况。因为提示语只有一句是真实的，事实上，我们分别假设了三种情况，每个分式代表一种情况。分式内部用且连接，这使得假设的情况不为真，则整个分式为假。现在我们需要化简整个式子，因为这个例子已经说明了背景为真，所以一定可以化简，但是到了复杂的问题时，其题目背景本身就是假（并非题目出错），我们需要通过命题演算得出矛盾式从而得出结论。
[(p \land \lnot q) \lor (p \land q) ]
通过分配律有
[p \land (q \lor \lnot q) ]
(q \lor \lnot q)一定为真，若要使整个式子为真，则p一定为真。因此，财宝在箱子A中。
一些经典问题
在过去，命题用自然语言描述时常常会十分混乱，现在命题不但可以用变量代替而且通过一些逻辑运算符连接起来做一些像加减乘除计算题一样解决逻辑问题。
一个运用条件语句的经典问题
问题：你来到一个村庄旅游，现在你来到了一个岔路口，有两条分支。根据你提前做好的旅游计划，一条路通往废墟，另一条路通往文化博物馆。现在你迷路了，同时没有可供导航的设备。这个村庄的人们正在过一种节日，对于外地人的回答只会做出肯定的或否定的回答，它可能撒谎也有可能不撒谎。你只有一次提问的机会，请问你会做出怎样的问题以达到目的。
解：如果你直接问“左边路口通往废墟吗？”，你得不出有用的结论。因为只有两种可能，你不知道它是否撒谎。语句“左边路口通往废墟吗？”是一般疑问句，这意味着其回答要么是肯定的，要么是否定的。这与命题有很高的相似性。因此，我们需要基于此构造一个复合命题。结合村民的特点，他的回答要么肯定要么否定。而这也可以成为一个命题。
不妨令(p)表示“我问你左边的路口通往废墟”，(q)表示“回答是”；(t)表示村民是说真话的，(f)表示村民是说假话的。所以((t \land p \rightarrow q) \lor (f \land p \rightarrow \lnot (\lnot q)))就表示“如果我问你左边的路口通往废墟，那么你回答是”，因为代词“你”可以是说真话的村民也可以是说假话的村民。他们最终回答的结果一定是一样的，因为(q \equiv \lnot (\lnot p))。现在我们来分析一下。
假设左边的路口通往废墟，村民不撒谎，那么他会回答是；村民撒谎，在得知左边的路口通往废墟，他一定回答否，即(\lnot p)，但是村民是要撒谎的，所以命题要被否定，最后回答是，即(\lnot (\lnot p))。同理，假设左边的路口不通往废墟，村民不撒谎，回答否；村民撒谎，在得知左边的路口不通往废墟，他一定回答是，但是村民要撒谎，最后回答否。
即你一定会得到一个有用的答复。就其原因，我们利用了说谎村民一定说谎的特性，通过两次否定得到肯定答复，使得说真话的村民与说谎的村民得到一样的答复。
回顾整个问题，它是建立在条件语句这一结构下的。所以在现实中你不能直接使用这种方法来避免说谎，细心的读者会发现题目中有很多隐性的假定条件，比如村民恒定地说谎。