1 基本概念
命题逻辑以“命题”为最基本对象，讨论这些命题在真假意义上的组合关系。它不关心句子内部的语法成分如何构成，而只关心整个句子是否为真，以及多个句子经过逻辑联结后真值如何变化。
1.1 命题与真值
命题逻辑中的核心，是能够判断真假的陈述。只有当一个语句能够明确地判定为真或假时，它才适合作为分析对象。
1.1.1 命题的定义
命题通常指具有确定真值的陈述句。例如，“2 是偶数”可以判定为真，“7 是偶数”可以判定为假。相对地，疑问句、祈使句以及含糊不清、无法确定真假的表达，一般不视为命题。
1.1.2 真与假的取值
在经典命题逻辑中，命题只有两种基本取值：真与假。真值分析就是研究这些取值在逻辑组合中的传递方式，以及复杂语句在不同条件下会呈现出何种真假状态。
1.2 命题变元与常量
为了便于形式化表达，逻辑中常用符号代表具体命题或固定真值。
1.2.1 命题变元
命题变元是用来表示不特定命题的符号，通常记作 p、q、r 等。它们本身不带固定内容，但在不同语境下可以代表具体陈述，因此适合用于刻画一般性的逻辑结构。
1.2.2 真常量与假常量
真常量与假常量分别表示恒为真的命题和恒为假的命题，常记作 ⊤ 和 ⊥。它们在逻辑运算中起到基准作用，常用于简化表达式和构造标准形式。
1.3 复合命题
多个简单命题可以通过联结词组合成结构更复杂的命题。
1.3.1 由联结词构成的表达式
复合命题是由命题变元、常量以及逻辑联结词构成的表达式，如“非 p”“p 且 q”“p 或 q”。这类表达式的真值由其组成部分及联结方式共同决定。
1.3.2 命题公式与语法树
命题公式是按照语法规则构造出来的合法表达式。为分析其结构，常用语法树表示公式中各联结词的层级关系，便于观察运算顺序与子公式之间的依赖。
2 逻辑联结词
逻辑联结词是命题逻辑的运算核心，用来把简单命题组合成复杂命题。不同联结词对应不同的真值变化规则。
2.1 否定
否定表示对一个命题真值的反转。
2.1.1 否定的语义
若命题 p 为真，则其否定 ¬p 为假；若 p 为假，则 ¬p 为真。否定刻画的是“不是如此”的逻辑关系，是最基本的单目运算。
2.1.2 否定的性质
否定具有反转真值、双重恢复原值等特点。连续两次否定通常等价于原命题，这一性质在化简和证明中十分常见。
2.2 合取与析取
合取与析取是最常见的二元联结词，分别对应“并且”和“或者”的逻辑意义。
2.2.1 合取的真值条件
合取通常记作 p ∧ q，只有在 p 与 q 同时为真时才为真；只要其中一项为假，整体就为假。它体现了“同时成立”的要求。
2.2.2 析取的真值条件
析取通常记作 p ∨ q，只要 p 或 q 至少有一个为真，整体就为真。经典命题逻辑中的析取一般允许两者同时为真，因此并不表示排他关系。
2.2.3 结合律、交换律与分配律
合取与析取都满足交换律和结合律，意味着交换顺序或改变括号位置不会改变结果。它们之间还存在分配关系，可用于重写和简化复杂公式。
2.3 蕴含与等值
蕴含与等值用于表达条件关系与完全一致关系，是推理结构中极为重要的联结词。
2.3.1 蕴含的定义
蕴含通常记作 p → q，读作“如果 p，那么 q”。在经典语义下，只有当前件为真而后件为假时，整个蕴含式为假；其余情况均为真。这一规定使它能自然对应条件推理的形式。
2.3.2 逆命题、否命题与逆否命题
对于 p → q，可构造逆命题 q → p、否命题 ¬p → ¬q 以及逆否命题 ¬q → ¬p。三者并不都与原命题等价，其中逆否命题与原命题在经典命题逻辑中等价，常用于证明。
2.3.3 双条件与逻辑等值
双条件通常记作 p ↔ q，表示 p 与 q 同真同假。它可以理解为双向蕴含。若两个命题在所有赋值下都具有相同真值，则称它们逻辑等值。
3 语义与真值分析
命题逻辑的语义部分关注公式如何在各种赋值下获得真值，并借此判断公式之间的关系。
3.1 赋值与解释
赋值是把抽象符号与具体真值联系起来的方式。
3.1.1 命题变元赋值
赋值函数把每个命题变元指定为真或假。不同赋值对应不同情境，从而使同一公式在不同条件下可能呈现不同结果。
3.1.2 公式在赋值下的值
一旦各个变元的值确定，复合公式的真值便可根据联结词的语义递归计算出来。这个过程从原子命题出发，逐层推得整个公式的结果。
3.2 真值表
真值表是分析命题逻辑最直观、最标准的工具之一。
3.2.1 真值表的构造方法
构造真值表时，先列出涉及的所有命题变元，再穷尽所有可能的真假组合，最后逐步计算各个子公式和整体公式的真值。它适合检验公式恒真性、可满足性以及等值关系。
3.2.2 公式分类：永真式、矛盾式与可满足式
若公式在所有赋值下都为真，称为永真式；若在所有赋值下都为假，称为矛盾式；若至少存在一种赋值使其为真，则称为可满足式。三者构成命题公式的重要分类。
3.3 逻辑后承
逻辑后承描述前提与结论之间的语义保证关系。
3.3.1 语义蕴涵
若在所有使前提组为真的赋值下，结论也为真，则称前提语义蕴涵结论。它强调的是“不会出现前提真而结论假的情况”。
3.3.2 逻辑后承关系
逻辑后承是前提集合到结论之间的一种关系记号，常写作 Γ ⊨ φ。若 Γ 中所有公式都真时 φ 必真，则称 φ 是 Γ 的逻辑后承。这一概念是语义层面的推理基础。
4 推理理论
推理理论研究从前提推出结论的形式方法，强调证明过程的规范性与可检验性。
4.1 证明与推导
证明是通过一系列规则把结论从已知命题中导出的过程。
4.1.1 直接证明
直接证明从前提出发，按照允许的推理规则逐步推出目标命题。它通常结构清晰，适合处理蕴含、合取等形式明确的命题。
4.1.2 间接证明
间接证明通过假设结论不成立，或者假设其否定成立，再推出矛盾，从而反证原命题成立。这类方法常用于处理难以直接构造的结论。
4.2 常用推理规则
推理规则是命题逻辑证明系统中的基本操作方式。
4.2.1 假言推理
假言推理也称肯定前件式：若已知 p→q 且 p 为真，则可推出 q 为真。它是最典型的条件推理规则之一。
4.2.2 拒取式与析取三段论
拒取式可由 p→q 与 ¬q 推出 ¬p，常对应否定后件的推理。析取三段论则是由 p∨q 以及 ¬p 推出 q，反映了“至少一个成立”的选择性结论。
4.2.3 构造性两难
构造性两难是指若 p→r、q→s，且 p∨q 成立，则可推出 r∨s。它常用于把“分情况讨论”的论证形式转化为统一结论。
4.3 可靠性与完备性
可靠性与完备性衡量一个逻辑系统与其语义之间的匹配程度。
4.3.1 可靠性定理
可靠性定理表明：凡是能够在形式系统中证明出的公式，在语义上也必然有效。也就是说，证明系统不会推出错误结论。
4.3.2 完备性定理
完备性定理表明：凡是语义上有效的公式，都能够在相应的形式系统中被证明出来。它说明推理规则足以捕捉全部语义有效性。
5 等值变形与定律
等值变形用于在保持真值不变的前提下改写公式，是分析与证明中的重要技术。
5.1 基本等值定律
基本等值定律提供了最常见的逻辑化简模式。
5.1.1 双重否定律
双重否定律指出 ¬¬p 与 p 等值。它允许在公式中消去连续两次否定，简化表达。
5.1.2 德摩根律
德摩根律说明否定可以分配到合取与析取内部，并同时改变联结词类型，例如 ¬(p∧q) 等值于 ¬p∨¬q。它在转换和化简中应用极广。
5.1.3 吸收律
吸收律表明某些复杂组合可被更简单的部分“吸收”，如 p∨(p∧q) 与 p 等值。它有助于减少冗余结构。
5.2 推导与化简
借助等值定律，可以把复杂公式变成更便于分析的形式。
5.2.1 代入与替换原理
若两个公式等值，则在任何更大的公式中都可以用其中一个替换另一个，而不改变整体真值。这个原理是等值变形合法性的基础。
5.2.2 公式化简方法
化简通常通过消去多余否定、展开或压缩联结结构、合并重复项等方式进行。目标是在保持等值的前提下得到更简洁、可读性更强的表达式。
5.3 范式转换
范式是把公式整理成标准结构的结果，便于机械处理和算法实现。
5.3.1 合取范式
合取范式是若干子句的合取，每个子句通常是若干文字的析取。它在自动推理和可满足性分析中非常常见。
5.3.2 析取范式
析取范式是若干项的析取，每个项通常是若干文字的合取。它与合取范式对称，适合从另一角度描述公式结构。
5.3.3 主析取范式与主合取范式
主析取范式与主合取范式是更规范的标准形式，其中每一项或子句都与一组完整赋值对应。它们为公式比较、化简和算法处理提供了统一框架。
6 经典命题逻辑的性质
经典命题逻辑建立在确定二值语义之上，因此呈现出一些鲜明性质。
6.1 排中律与矛盾律
这两条原则是经典逻辑的典型特征。
6.1.1 排中律的形式化
排中律表示对任一命题 p，p∨¬p 恒真。它表达了“要么如此，要么不如此”的二值断言。
6.1.2 矛盾律的形式化
矛盾律表示 p∧¬p 恒假。它排除了一个命题同时真又假的可能性，是经典逻辑一致性的基础之一。
6.2 反证与归谬
反证法在命题逻辑中具有重要地位，尤其适合处理否定性结论。
6.2.1 归谬法的逻辑结构
归谬法通常先假设待证命题的否定成立，再通过推导得到矛盾，由此反推出原命题为真。其核心在于利用矛盾来排除错误前提。
6.2.2 间接证明的应用
间接证明常用于存在性、唯一性以及否定命题的论证。它能够避免直接构造困难，使证明路径更为灵活。
6.3 逻辑系统的表达能力
命题逻辑能够精确表达很多基本关系，但也存在明显边界。
6.3.1 公式可表达的关系
命题逻辑擅长表达由有限命题及其真值关系组成的结构，例如条件关系、并列关系、排除关系和组合性约束。对于只关心整体真假而不分析内部成分的场景，它十分有效。
6.3.2 表达能力的局限性
命题逻辑无法直接表达“所有”“存在”等量化信息，也难以描述对象之间的内部结构与关系。若要处理更细致的对象层面信息，通常需要引入谓词逻辑。
7 相关扩展与应用
命题逻辑虽然形式简单，但它是许多更复杂理论与实际应用的基础。
7.1 谓词逻辑的引入
谓词逻辑在命题逻辑之上进一步细化了表达能力。
7.1.1 从命题到谓词
命题逻辑把句子视为不可分割的整体，而谓词逻辑则分析对象及其性质、关系。这样，原本只能整体判断真假的表达，可以被拆分为更细的逻辑结构。
7.1.2 量词的加入
全称量词和存在量词使逻辑能够表达“对所有对象”以及“至少存在一个对象”等陈述。它们显著提升了形式系统的表达范围。
7.2 计算机科学中的应用
命题逻辑在计算机领域具有广泛而实际的用途。
7.2.1 布尔代数与电路设计
命题逻辑与布尔代数关系密切，可直接用于分析开关电路、逻辑门和数字系统。一个命题联结词往往对应一种基本电路操作，因此真值表也可用于检验电路功能。
7.2.2 程序验证与自动定理证明
在程序验证中，命题逻辑可用于表示条件、分支和断言，帮助检查程序是否满足预期性质。自动定理证明则利用公式化、范式转换和搜索算法，对逻辑结论进行机械推导。
7.3 日常推理与形式化思维
命题逻辑不仅是抽象理论，也有助于整理现实中的论证。
7.3.1 论证分析
将自然语言论证拆分为前提、结论和中间推理步骤，有助于识别论证是否成立。命题逻辑提供了把日常表达转化为可检验形式的工具。
7.3.2 常见逻辑谬误的识别
通过命题逻辑，可以辨认一些常见错误，如把“若 p 则 q”误当作“若 q 则 p”，或在析取推理中遗漏必要条件。对这些谬误的识别，有助于提高论证的严谨性。