逻辑联结词是用于从其他公式构造复合公式的符号或表达式。常见的例子包括否定(“非”)、合取(“且”)、析取(“或”)和蕴涵(“如果……那么……”)。在经典命题逻辑中,每个联结词都表示一个真值函数:复合公式的真值仅取决于其组成部分的真值。更一般地说,联结词可以通过证明规则来解释,也可以通过涉及普通真假值以外信息的语义来解释。它们是逻辑学、数学推理和计算机领域所用形式语言的基本组成部分。
语法与解释
联结词的元数是指它所接受的公式参数的数量。否定是一元的:它从公式 构成 。合取是二元的:它从 和 构成 。真值常量通常用 表示真、用 表示假,可以视为不需要任何参数的零元联结词。
形式系统的语法规定哪些表达式是合式的。例如,一种命题语言可以允许按照以下规则递归生成公式:
- 每个命题变元都是公式。
- 如果 是公式,那么 也是公式。
- 如果 和 是公式,那么 和 也是公式。
- 除非由这些规则生成,否则其他表达式都不是公式。
语义为这些表达式赋予意义。在经典二值语义中,一个 元联结词被解释为一个函数
其中, 表示假, 表示真。赋值为命题变元指定真值,而联结词的解释则将这一赋值扩展到复合公式。
区分语法与语义十分重要:联结词是形式语言的一个组成要素,而真值函数只是它的一种可能解释。同一符号在不同的逻辑系统中可能有不同的解释。
主要的经典联结词
最常用的经典联结词概述如下。
| 联结词 | 常用记号 | 通常读法 | 真值条件 |
|---|---|---|---|
| 否定 | 非 | 当且仅当 为假时为真 | |
| 合取 | 且 | 当且仅当两者都为真时为真 | |
| 相容析取 | 或 | 至少有一个为真时为真 | |
| 实质蕴涵 | 如果 ,那么 | 当且仅当 为真且 为假时为假 | |
| 双条件 | 当且仅当 | 当且仅当两者真值相同时为真 | |
| 不相容析取 | 要么 ,要么 ,但不能两者都成立 | 当且仅当两者真值不同时为真 |
这些二元真值函数可以用真值表表示:
| 真 | 真 | 真 | 真 | 真 | 真 | 假 |
| 真 | 假 | 假 | 真 | 假 | 假 | 真 |
| 假 | 真 | 假 | 真 | 真 | 假 | 真 |
| 假 | 假 | 假 | 假 | 真 | 真 | 假 |
相容析取允许两个选项同时为真。异或则排除了这种可能。日常语言中的“或”可能表达其中任一种含义,具体取决于语境。
用实质蕴涵翻译日常条件句时,有一个尤其重要的局限。公式 既不声称 与 之间存在因果联系,也不声称两者在内容上具有相关性。在经典解释下,它仅仅等价于 ,因此只要 为假,它就为真。涉及时间、因果和反事实的条件句通常需要进一步分析。
双条件是语言内部的一个公式。这不同于声称两个公式逻辑等价;后者意味着它们在每一种赋值下都具有相同的真值。在经典命题逻辑中, 和 逻辑等价,当且仅当 在每一种赋值下都为真。
辖域、分组与优先级
联结词的辖域是公式中它所作用的部分。括号可以明确标示辖域:
否认 和 同时为真,而
则断言 为假且 为真。
一种常见的优先级约定是:否定优先于合取,合取优先于析取,蕴涵和双条件则排在它们之后。因此, 通常被读作 。不过,不同文献和编程语言的约定有所不同,因此在可能产生歧义时,使用括号很重要。
合取和析取满足结合律,因此 这样的表达式无须指定分组方式。蕴涵不满足结合律:
与
通常并不等价。省略括号时,连续出现的蕴涵通常按约定采用右结合的方式分组。
逻辑定律与代数结构
经典联结词满足一些等价关系,可用于变换和化简公式。合取与析取满足交换律、结合律,并且彼此之间满足分配律。它们还满足幂等性:
这里的 表示逻辑等价,而不是语言中的另一个联结词。
德摩根定律揭示了否定与合取、析取之间的关系:
其他重要的经典定律包括双重否定消去,即 ,以及排中律,后者指出 恒为真。
这些运算构成了布尔代数的基础。它们还与集合论中的运算存在直接对应关系:合取对应交集,析取对应并集,否定对应相对于某个固定全集的补集。例如,一个元素属于 ,就必须同时属于 和 。
表达能力与函数完备性
元数为 的不同经典真值函数共有
个。这是因为可能的输入组合有 种,而每一种输入组合都可以独立地对应两种输出中的任意一种。因此,一元真值函数有四个,二元真值函数有十六个。
如果通过组合一组联结词中的成员,可以表达每一个正元数的布尔真值函数,就称这组联结词具有**函数完备性**。集合 和 都具有函数完备性。例如,
有两个二元联结词各自单独使用就足以实现函数完备性:
- 与非(NAND),也称谢费尔竖线,定义为 。
- 或非(NOR),也称皮尔士箭头,定义为 。
仅使用与非,就可以将否定和合取表示为
相比之下,仅有合取和析取而没有否定,并不具有函数完备性。由它们构造的公式具有单调性:将一个输入从假改为真,不会使输出从真变为假。
函数完备性关注的是能否表达,而不是表达效率。等价公式在长度、电路规模或求值开销上可能相差很大。
联结词与推理规则
联结词用于构成公式;推理规则则允许从前提过渡到结论。两者的作用不同。表达式 是一个公式,而肯定前件式则是一条允许从前提 和 推出结论 的规则。
在自然演绎中,联结词通过引入规则和消去规则来刻画。合取引入规则允许在 和 均已得到证明后推出 。合取消去规则则允许从合取式推出其中任一组成部分。
蕴涵引入规则允许先在临时假设 下推导出 ,然后解除这一假设,从而确立 。蕴涵消去规则就是肯定前件式。这些规则在证明论中处于核心地位,并提供了一种不以经典真值表为出发点来理解联结词的方式。
在一阶逻辑中,命题联结词用于组合包含谓词和变元的公式。“任意”和“存在”等量词通常与命题联结词加以区分,因为量词会约束变元,而不只是组合完整的公式。
非经典解释
逻辑联结词并不限于经典的二值真值函数。
在直觉主义逻辑中,联结词的意义与什么算作证明密切相关。按照布劳威尔—海廷—柯尔莫哥洛夫解释, 的证明提供两个组成部分各自的证明,而 的证明则提供其中一个组成部分的证明,并指明证明的是哪一个。 的证明提供一种构造,能够将 的任意证明转化为 的证明。在这一框架下,排中律和双重否定消去并不是可以不加限制地使用的有效原则。
在模态逻辑中,通常读作“必然”的 和读作“可能”的 等算子,并不是仅由其参数在单个世界中的真值决定的普通真值函数。在克里普克语义下,它们的解释取决于可达世界中的真值。
多值逻辑使用两种以上的真值,并为联结词指定相应的运算。次协调逻辑拒绝接受从矛盾可以推出任意结论这一普遍原则。因此,否定及其他联结词的行为取决于所选择的逻辑系统,而不仅仅取决于用来书写它们的那些熟悉符号。
历史发展与应用
古代斯多亚学派的逻辑学家研究了涉及完整命题以及对应于条件、合取和选择的表达式的推理模式。19世纪,乔治·布尔的工作发展了逻辑运算的代数处理方法。后来的符号逻辑建立了形式语言,使人们能够系统地研究联结词及其规则。
20世纪,克劳德·香农展示了布尔代数在开关电路中的应用。这一联系为数字硬件设计提供了基础;在数字硬件中,逻辑门实现与、或、非、与非等运算。
在软件中,布尔运算符用于构造分支、筛选和搜索所需的条件。不过,它们在计算中的行为可能不同于纯粹的逻辑解释:短路求值可以跳过某个操作数,而当该操作数的求值会产生副作用时,这一点就十分重要。数据库系统也可能使用第三种值来表示未知信息,而不是采用经典二值逻辑。
联结词在形式验证中至关重要,规约和程序性质都以公式表达。自动推理系统对这些公式进行操作,以检验可满足性、确定逻辑后承,或检查系统是否满足给定要求。