1. 命题逻辑从“一句话”到“推理引擎”的蜕变很多朋友一听到“命题逻辑”或者“离散数学”头就开始大了觉得这肯定是数学家们玩的抽象游戏离我们这些写代码、搞技术的普通人太远了。我刚开始学的时候也是这么想的直到后来在写一个智能设备的规则引擎时被一堆复杂的“如果...那么...”条件绕得晕头转向才猛然发现命题逻辑这套东西简直就是为我们量身定定的“思维脚手架”。它不是什么高深的理论而是一套极其严谨的“语言规范”专门用来描述和操作那些非真即假的陈述句。你可以把它想象成编程里的布尔代数但更基础、更通用是任何涉及条件判断、规则推理的底层逻辑。那么命题逻辑到底能做什么呢简单说它能帮你把一句句模糊的自然语言比如“如果下雨我就不出门”翻译成精确的、可以被计算机或我们自己严格推理的符号公式。然后你可以像做数学题一样对这些公式进行“计算”验证它们是否自相矛盾或者从一堆已知条件中必然地推导出某个结论。这个过程就是逻辑推理。无论是设计一个复杂的业务规则系统还是理解人工智能中的知识表示甚至是日常的代码逻辑梳理掌握命题逻辑都能让你思路无比清晰避免掉进逻辑陷阱。这篇文章我就想用最“人话”的方式带你从最基础的“命题”和“联结词”开始一步步搭建起命题逻辑的完整知识体系并重点演示如何用真值表和演绎法这两个超级实用的工具去解决实际问题。2. 命题与联结词构建逻辑世界的“原子”与“粘合剂”2.1 什么才算一个合格的“命题”命题逻辑的起点是一个个最简单的“原子”单元我们称之为命题。它的定义非常严格一个具有确切真值的陈述句。这里有两个关键点“陈述句”和“确切真值”。“陈述句”好理解就是用来描述一件事实的句子不能是疑问句、祈使句或者感叹句。比如“今天天气很好”是陈述句“请把门关上”就不是。“确切真值”是核心。一个命题的真值必须是明确的“真”True记作1或T或者“假”False记作0或F而且这个真值是客观存在的不依赖于我们是否知道。这是最容易混淆的地方。我举个例子“地球是圆的。”这是一个命题它的真值是“真”。“113”也是一个命题它的真值是“假”。那么“火星上存在生命”呢很多人会觉得我们不知道啊所以它不是命题。错了它依然是命题。因为“火星上是否存在生命”这件事在客观现实中有一个确定的答案要么有要么没有只是我们人类目前还不知道而已。它的真值是“确切存在”的所以它是一个命题。反过来像“你好帅啊”、“这朵花真美”这种带有主观评价色彩的句子就没有客观的真假所以它们不是命题。理解这一点至关重要它划清了逻辑讨论的边界。在命题逻辑里我们只关心那些能够明确判断真假的陈述并把它们抽象成一个个简单的符号比如用 P 表示“今天下雨”用 Q 表示“我带伞”。至于 P 和 Q 在现实中具体是什么逻辑本身并不关心。2.2 五大联结词让原子命题“化学反应”起来单个命题能表达的信息太有限了。我们需要把简单的命题组合起来表达更复杂的意思。这就需要用到命题联结词它们是逻辑世界的“粘合剂”或“运算符”。最核心的有五个我挨个给你掰开揉碎了讲保证比教科书上的定义好懂十倍。否定非¬这是最简单的单目运算符。如果 P 是一个命题那么 ¬P读作“非P”就表示 P 的相反情况。它的真值规则最简单P 真则 ¬P 假P 假则 ¬P 真。就像开关的“关闭”状态是“开启”状态的否定。合取与∧对应自然语言中的“并且”。命题 P ∧ Q 为真当且仅当 P 和 Q同时为真。只要有一个为假整个合取式就是假的。比如“我今天加班P并且明天休息Q”只有我既加了班又休息了这句话才成立。这个“同时成立”的要求非常严格。析取或∨这是最容易出错的地方。在经典命题逻辑中析取是“可兼或”。也就是说P ∨ Q 为真只要 P 和 Q 中至少有一个为真。它包含了“P真Q假”、“P假Q真”和“P真Q真”三种情况。比如“我喝茶P或喝咖啡Q”我两样都喝这句话依然成立。这和我们日常口语中说“或者”时有时会排除两者都选的情况不可兼或如“要么…要么…”是不同的。逻辑里的默认“或”是可兼的这一点务必记牢。蕴含如果…则…→这是最难理解也最重要的一个联结词。P → Q 读作“如果P则Q”。它的真值表是反直觉的只有当P为真而Q为假时P → Q 才为假其他情况P假Q真、P假Q假、P真Q真下P → Q 都为真。为什么我们可以把它理解成一个“承诺”或“保证”当P这个条件发生时我保证Q一定会发生。如果P发生了我做出了承诺的条件但Q没发生承诺没兑现那这个承诺就是假的P→Q为假。如果P根本没发生承诺的条件不成立那么无论Q发不发生我这个承诺都没有被违反所以我们可以认为这个“如果…则…”的陈述在逻辑上没有被证伪因此视为真。这种理解在数学和编程中非常普遍比如“如果x0则打印x”。当x不大于0时这个语句什么都不做你并不能说这个条件语句是“假”的。等价当且仅当↔P ↔ Q 为真表示P和Q的真值完全相同同真或同假。它就像是逻辑上的“等于号”。在数字电路里它对应“同或”门。为了让你看得更清楚我把这五个联结词的真值表整理如下PQ¬PP ∧ QP ∨ QP → QP ↔ QTTFTTTTTFFFTFFFTTFTTFFFTFFTT这张表就是你进行所有逻辑计算的“九九乘法表”一定要烂熟于心。刚开始你可以多写几次很快就能形成条件反射。2.3 联结词使用的“坑”与实战技巧在实际应用中直接从自然语言翻译成逻辑公式时最容易踩两个坑。第一个就是刚才说的“或”的理解。比如公司规定“迟到或早退将扣奖金。”这里的“或”通常是可兼的即又迟到又早退扣奖金这件事依然成立而且可能扣得更多。但如果说“选修课你选A门或选B门”这里的“或”可能就是不可兼的因为通常你不能同时选两门。在形式化时对于不可兼或我们需要用 (P ∨ Q) ∧ ¬(P ∧ Q) 这样的组合来表示。第二个坑是“蕴含”的翻译。“如果P则Q”在逻辑上只关心P和Q的真假关系不关心它们之间是否有因果关系。比如“如果太阳从西边出来那么我就给你一百万。”在逻辑上因为“太阳从西边出来”是假的所以整个蕴含式是真的这听起来荒谬但在逻辑体系里是自洽的。我们使用蕴含更多是为了进行推理当我们知道P→Q为真并且P也为真时我们就可以必然地推出Q为真。这才是它的核心价值。我个人的经验是在编程或设计规则时先把所有自然语言描述的条件用P、Q、R这样的符号和五大联结词重写一遍。这个过程本身就能帮你发现很多模糊和歧义的地方。比如“用户是VIP且消费满100元或者使用优惠码即可免运费。”这句话就有歧义“且”和“或”的优先级是怎样的是“(VIP且满100) 或 用优惠码”还是“VIP且 (满100 或 用优惠码)”用逻辑公式写出来歧义立刻就消失了。3. 命题公式、解释与真值表给逻辑表达式“算个命”3.1 命题公式用规则搭建的复杂句子有了命题原子如P, Q, R和联结词¬, ∧, ∨, →, ↔我们就可以像搭积木一样按照一定的语法规则组合它们形成命题公式。规则很简单单个命题变元是公式如果A是公式那么¬A也是公式如果A和B是公式那么(A∧B)、(A∨B)、(A→B)、(A↔B)也都是公式。通过不断应用这些规则我们就能构造出非常复杂的逻辑表达式比如 ((P → Q) ∧ ¬Q) → ¬P。写复杂公式时括号非常重要它明确了运算的优先级。通常的优先级是否定¬最高然后是合取∧和析取∨最后是蕴含→和等价↔。和算术里先乘除后加减一样。不确定的时候就多用括号这样最保险。3.2 解释与真值表穷举所有可能性一个命题公式里通常含有多个命题变元比如P, Q。给这些变元分别赋予一个具体的真值T或F这一组赋值就称为该公式的一个解释。对于一个有n个变元的公式一共有2ⁿ种可能的解释因为每个变元有2种选择。真值表就是一个超级实用的工具它系统地列出公式在所有可能解释下的真值。制作真值表的步骤非常机械列出公式中所有不同的命题变元。列出所有2ⁿ种真值组合。按照运算优先级逐步计算公式中每个子部分在不同解释下的真值直到算出整个公式的真值。我们举个实战例子。公式G (P → Q) ∧ P。我们想知道在什么情况下G会为真 先列真值表PQP → Q(P → Q) ∧ PTTTTTFFFFTTFFFTF从这个表可以一眼看出只有当P和Q都为真时整个公式G才为真。这意味着如果我们知道G为真就可以反推出P和Q必须同时为真。真值表就像给逻辑公式做了一次全面的“体检”它的所有行为特征都一览无余。3.3 公式的分类永真、永假与可满足根据真值表的结果我们可以把命题公式分为三类永真式重言式在所有可能的解释下公式的真值都为真。例如 P ∨ ¬P排中律。这种公式表达的是逻辑上的绝对真理。永假式矛盾式在所有可能的解释下公式的真值都为假。例如 P ∧ ¬P矛盾律。这种公式表达的是逻辑上的绝对谬误。可满足式至少存在一种解释使得公式的真值为真。也就是说它不是永假的。永真式当然是可满足的但可满足式不一定永真。绝大部分我们遇到的公式都是可满足式。判断一个公式属于哪一类最直接的方法就是画真值表。如果最后一列全为T就是永真式全为F就是永假式有T有F就是可满足式。在程序验证或电路设计里我们常常需要证明某个设计逻辑是永真的即无论输入什么输出都符合预期或者证明某些条件不可能同时成立即它们的合取是永假的从而发现需求矛盾。3.4 基本等价关系逻辑世界的“化简公式”就像代数里有交换律、结合律一样命题逻辑里也有一系列基本等价关系。利用它们我们可以对复杂的逻辑公式进行化简或变形而不改变其真值。这非常有用尤其是在手工推导或者优化逻辑电路时。我挑几个最常用、也最容易和数字电路知识类比的给你看看双重否定律¬¬P ⇔ P。负负得正。幂等律P ∧ P ⇔ P P ∨ P ⇔ P。自己和自己“与”或“或”还是自己。交换律/结合律/分配律和代数里的乘加类似。比如 P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R)。德·摩根律¬(P ∧ Q) ⇔ ¬P ∨ ¬Q ¬(P ∨ Q) ⇔ ¬P ∧ ¬Q。这是最重要的定律之一它描述了“且”和“或”在否定下的转换关系。记不住的时候可以想“否定的且变成或的否定”“否定的或变成且的否定”。蕴含等值式P → Q ⇔ ¬P ∨ Q。这是我之前提到过的把难以理解的蕴含转化成了简单的析取。这个公式务必背熟它是很多推理的基石。等价等值式P ↔ Q ⇔ (P → Q) ∧ (Q → P)。这说明“等价”就是两个方向的“蕴含”同时成立。掌握这些等价关系后你就可以像化简代数式一样化简逻辑式。例如判断 (P ∧ Q) ∨ (P ∧ ¬Q) 是什么。根据分配律它可以化为 P ∧ (Q ∨ ¬Q)而 (Q ∨ ¬Q) 是永真的永真式与任何公式合取都等于原公式所以最终这个式子等价于 P。看化简后逻辑清晰多了无论Q是真假只要P为真原式就为真。4. 范式为逻辑表达式找到“标准身份证”4.1 析取范式与合取范式两种标准形状当逻辑公式变得非常复杂时我们需要一种标准化的形式来分析和比较它们。这就引入了范式的概念。你可以把范式理解为逻辑表达式的“标准型”。有两种最基本的范式析取范式公式被写成多个短语的析取∨。每个短语又是多个文字命题变元或其否定的合取∧。形如(A ∧ B) ∨ (¬A ∧ C) ∨ (D)。合取范式公式被写成多个子句的合取∧。每个子句又是多个文字的析取∨。形如(A ∨ B) ∧ (¬A ∨ C) ∧ (D)。简单说析取范式就是“积之和”先合取再析取合取范式就是“和之积”先析取再合取。任何命题公式都可以通过等价变换化归为这两种范式之一。范式化就像把一道菜的所有原料和步骤标准化便于我们后续的“烹饪”推理或计算。4.2 主范式包含所有变量的“完整身份证”析取范式和合取范式还不够“标准”因为同一个公式可能有多种不同的范式表示。我们需要更严格的“主范式”。主范式的特点是它的每个最小单元短语或子句必须包含公式中所有命题变元。这就引出了两个核心概念极小项和极大项。极小项是包含所有变元的一次合取式且每个变元以原形或否定形式恰好出现一次。例如对于变元P, Q极小项有四个P∧Q, P∧¬Q, ¬P∧Q, ¬P∧¬Q。每个极小项只在一种特定的解释下为真比如P∧Q只在P真Q真时为真。极大项是包含所有变元的一次析取式且每个变元以原形或否定形式恰好出现一次。同样对于P, Q极大项也有四个P∨Q, P∨¬Q, ¬P∨Q, ¬P∨¬Q。每个极大项只在一种特定的解释下为假。主析取范式就是由极小项析取而成主合取范式就是由极大项合取而成。一个公式的主析取范式清晰地告诉我们在哪些解释下公式为真而它的主合取范式则清晰地告诉我们在哪些解释下公式为假。它们互为补充共同构成了一个公式的“完整真值档案”。4.3 真值表技术求主范式的“傻瓜”方法如何求一个公式的主范式最直观、最不容易出错的方法就是真值表技术。我手把手带你走一遍流程。假设我们有公式 G (P → Q) ∧ R。我们想求它的主析取范式。列出真值表公式有三个变元P, Q, R所以有2³8种解释。PQRP → Q(P → Q) ∧ R0001000111010100111110000101001101011111找出使公式为真的解释从表上看是第2行(P0,Q0,R1)、第4行(P0,Q1,R1)和第8行(P1,Q1,R1)。为每个真解释写出对应的极小项第2行 (0,0,1)对应 ¬P ∧ ¬Q ∧ R第4行 (0,1,1)对应 ¬P ∧ Q ∧ R第8行 (1,1,1)对应 P ∧ Q ∧ R 规则变元值为1就取原形值为0就取否定将所有极小项析取起来这就是主析取范式。 G 的主析取范式 (¬P ∧ ¬Q ∧ R) ∨ (¬P ∧ Q ∧ R) ∨ (P ∧ Q ∧ R)看是不是很简单主析取范式就是“所有为真的情况取或”。同理如果你想求主合取范式就找出所有使公式为假的解释为每个假解释写出对应的极大项规则相反变元值为0取原形值为1取否定然后将这些极大项合取起来。对于上表为假的解释是第1,3,5,6,7行。你可以自己练习写出G的主合取范式。4.4 范式转换与实战意义既然有了主析取范式我们也可以间接得到主合取范式。因为所有极小项和所有极大项是互补的。一个公式的主析取范式包含了所有使其为真的极小项那么剩下的极小项就是使其为假的。而这些剩下的极小项的否定恰恰就是使其为假的极大项。有一套系统的转换方法但有了真值表这个利器直接求往往更快。那么费这么大劲求主范式有什么用呢实战意义巨大。首先判断两个逻辑公式是否等价看它们的主范式是否相同就行了。其次在数字电路设计中主析取范式直接对应着“与或”表达式可以用来设计组合逻辑电路主合取范式则对应“或与”表达式。最后在人工智能的知识表示和推理中范式化是进行归结推理等自动化推理的基础。把知识库里的每一条规则都化成范式机器才能高效地进行逻辑演算。5. 命题逻辑的推理理论从“知道”到“推出”学了一大堆符号和计算最终目的是为了推理。推理就是从一些已知为真的命题前提按照逻辑规则推导出另一个新的命题结论。如果前提为真时结论必然为真我们就说这个推理是有效的或结论是前提的逻辑结果。5.1 推理的有效性不是关于真假而是关于形式这是关键点逻辑推理关心的是形式上的有效性而不是前提和结论在现实中的真假。一个推理是有效的意味着如果所有前提都为真那么结论不可能为假。至于前提本身是不是真的逻辑学不管。例如“如果猪会飞那么月亮是奶酪做的。猪会飞。所以月亮是奶酪做的。”这个推理在形式上是有效的使用了“肯定前件”的规则尽管它的两个前提在现实中都是假的。5.2 四大判断方法总有一款适合你如何判断一个推理“前提P1, P2, ..., Pn结论H”是否有效呢有四种常用的方法。1真值表技术最笨但最可靠把前提的合取P1 ∧ P2 ∧ ... ∧ Pn和结论H放在同一个真值表里。检查在所有使前提合取为真的解释下结论H是否也都为真。如果是则推理有效。这方法直观但变元一多比如超过4个真值表就会非常庞大手算很麻烦。2推理定律利用已知的“逻辑公式”这是一些公认的有效推理模式就像数学里的定理。常用的有假言推理P → Q, P ⇒ Q 如果P则Q现在有P所以有Q拒取式P → Q, ¬Q ⇒ ¬P 如果P则Q现在非Q所以非P析取三段论P ∨ Q, ¬P ⇒ Q P或Q现在不是P所以是Q构造性二难(P→Q) ∧ (R→S), P ∨ R ⇒ Q ∨ S如果你要证明的推理恰好符合某个定律那直接就可以说它有效。但很多复杂推理需要组合使用多个定律。3演绎法步步为营的推导证明这是最常用、也最像我们平时做数学证明的方法。它允许我们在推导过程中引入前提P规则、引用已知的等价式或蕴含式T规则以及为了证明条件结论而引入附加前提CP规则。整个过程就像搭积木每一步都必须有明确的依据。我举个例子演示一下。证明推理前提 P→Q, Q→R, P结论 R。1. P→Q 前提引入 (P规则) 2. P 前提引入 (P规则) 3. Q 由1,2假言推理 (T规则) 4. Q→R 前提引入 (P规则) 5. R 由3,4假言推理 (T规则)你看我们一步步从前提推出了结论。演绎法的好处是结构化、可检查非常适合人脑思考和机器执行。4反证法归谬法从结论的反面找矛盾如果你想证明从前提能推出H你可以先假设结论H不成立即¬H为真然后将这个¬H作为一个附加前提和原来的前提放在一起。如果你能从这一组前提中推导出一个矛盾比如推出某个命题A和它的否定¬A同时成立那么就说明你的假设¬H是错误的从而原结论H必须成立。反证法在直接证明困难时非常有用。5.3 实战演绎法像写程序一样写证明演绎法是逻辑推理的“编程语言”。我分享一个稍微复杂点的、使用CP规则的例子这在证明形如“如果A则B”的结论时常用。 要证明前提 P→(Q→R)结论 (P→Q)→(P→R)。证明这种“如果...则...”的结论标准操作就是使用CP规则把结论的前件 (P→Q) 作为附加前提引入然后看能否推出后件 (P→R)。1. P→(Q→R) 前提引入 (P规则) 2. P→Q 附加前提引入 (CP规则的前提) 3. | P 附加前提引入 (为了证明P→R再次使用CP规则) 4. | Q→R 由1,3假言推理 (T规则) 5. | Q 由2,3假言推理 (T规则) 6. | R 由4,5假言推理 (T规则) 7. P→R 由3-6CP规则 (因为假设P推出了R) 8. (P→Q)→(P→R) 由2-7CP规则 (因为假设P→Q推出了P→R)这个证明里嵌套使用了两次CP规则结构非常清晰。写熟练之后你会发现这跟写一个函数调用另一个函数很像。逻辑的严谨性就体现在这每一步的“规则引用”上。在实际工作中无论是设计一个复杂的业务规则系统还是编写一段需要严密条件判断的代码甚至是进行软件测试用例的设计这种演绎推理的思维都能极大地帮助你理清逻辑脉络避免遗漏和错误。我习惯在设计复杂条件分支时先把所有条件和预期动作用命题符号写出来然后尝试用演绎法推演一遍常常能发现那些隐藏的、冲突的或者冗余的规则。命题逻辑不是束之高阁的理论而是打磨我们思维清晰度的最好工具。从理解每一个联结词开始到熟练运用真值表和演绎法这个过程本身就是在训练一种抓住问题本质、进行无懈可击推导的能力。