逻辑析取是逻辑学中的一种联结词,用于将命题组合起来,表示其中至少有一个成立。通常写作 ,读作“ 或 ”,其中的各个命题称为析取支。在经典命题逻辑中,只有两个析取支都为假时,析取命题才为假。这是一种相容性的解释:当 和 都为真时, 仍然为真。
定义与真值条件
经典析取是一种二元真值函数联结词:复合命题的真值仅取决于其两个析取支的真值。其真值表如下:
| 真 | 真 | 真 |
| 真 | 假 | 真 |
| 假 | 真 | 真 |
| 假 | 假 | 假 |
例如,设 表示“这个整数能被 2 整除”, 表示“这个整数能被 3 整除”。那么,对于 4、9 和 6, 为真,而对于 5 则为假。6 的情况说明,两个析取支可以同时成立。
如果用 表示真,用 表示假,那么析取可以表示为
右侧的算术表达式是真值表的一种编码,并不是要在通常的公式中取代逻辑联结词。
相容的“或”与排他的“或”
相容析取不同于异或;异或恰好在一个析取支为真、另一个为假时为真。异或可以用相容析取来定义:
在日常语言中,“或”可能暗示这两种解释中的任意一种。“茶或咖啡”可能意味着二选一,而“申请人必须懂法语或德语”则可能允许两种语言都懂的申请人。排他性的暗示往往取决于语境,而不只是“或”这个词本身。形式逻辑会明确规定采用哪一种解释。
记号与作用域
析取的标准逻辑符号是 。在布尔代数中,也常用 表示“或”,用乘法或并置表示“与”。布尔加法不能与普通算术加法或模 2 加法混淆:在布尔“或”运算中,,而模 2 加法表示异或。
括号决定联结词的作用域。例如,
不同于
一种常见约定是:否定的优先级高于合取,合取的优先级又高于析取;不过,明确使用括号可以避免歧义。
析取也出现在一阶逻辑中,其析取支可以包含谓词、变量和量词。例如,
表示每个对象都至少满足这两个谓词中的一个。它一般不能推出
因为不同对象可能满足不同的谓词。
代数性质
经典析取满足若干基本等价关系。这里, 表示公式在每一种赋值下都具有相同的真值。
| 性质 | 等价关系 |
|---|---|
| 交换律 | |
| 结合律 | |
| [[idempotence | 幂等性]] |
| 同一律 | |
| 支配律 | |
| 吸收律 |
符号 和 分别表示假和真。
结合律使得有限个命题的析取可以写成以下形式,而不必指定分组方式:
它恰好在至少一个析取支为真时为真。不含任何命题的析取称为空析取,通常约定其为假,这与 是“或”运算的单位元相一致。
析取与合取相互满足分配律:
德摩根定律将这两种运算与否定联系起来:
因此,在经典逻辑中,可以用合取和否定来定义析取:
是经典逻辑中的重言式。这些等价关系和原理中,有些不能原封不动地推广到非经典逻辑中。
推理规则
析取受一组规则支配,这些规则规定了在形式证明中如何引入和使用析取。
析取引入
由 可以推出 ;由 也可以推出 :
这些推理规则不要求为新增的析取支提供证据。如果 已经得到确立,那么“ 和 中至少有一个成立”这一相容性断言也就得到了确立。
析取消去
在自然演绎中,析取消去将分类证明形式化。如果 已经得到确立,而且从假设 和假设 都能推出同一个结论 ,那么就可以推出 :
应用这条规则时,方括号内的假设被撤销。两种情况不必互斥:即使 和 同时成立,论证仍然有效。
一种常见的相关推理形式是析取三段论:
它在经典逻辑和标准的直觉主义逻辑中都有效。相比之下,由 和 不能推出 ,因为相容析取允许两个析取支同时为真。
集合论与概率解释
在集合论中,析取对应于并集:
在这一对应关系下,合取对应交集,否定对应相对于指定全集的补集。因此,逻辑联结词的代数定律与集合的运算定律相互对应。
在由布尔代数导出的偏序中,析取是上确界,即最小上界。将逻辑等价的命题视为同一个元素,并按逻辑蕴涵关系排序时, 是最弱的共同上界: 和 都蕴涵它,而它又蕴涵所有同时被 和 蕴涵的命题。
在概率论中,事件 或事件 发生用 表示。其概率为
减去交集的概率,可以避免将同时满足两个事件的结果重复计算。对于互斥事件,交集的概率为零。在满足统计独立性的条件下,公式变为
独立与互斥是不同的条件。
计算与应用
析取是计算机科学中的一种基本运算。数字电路通过或门来实现它:只要至少一个输入为 1,输出就为 1。多输入或门是同一规则的推广。
编程语言通常区分以下几种运算:
- 逻辑或:将布尔条件组合起来,不过不同语言对操作数和返回值的约定有所不同。
- 按位或:对各个对应的二进制位分别应用“或”的真值表。
- 短路或:只有在第一个操作数尚不足以确定结果为真时,才对第二个操作数求值。
当操作数具有副作用、求值开销很大,或在某些情况下不能合法求值时,短路求值就很重要。这种求值行为并不属于抽象的经典真值表的内容。
析取在命题公式的标准形式中也起着核心作用。析取范式是若干合取式的析取,而每个合取式由文字组成;这里的文字是命题变量或其否定。合取范式是若干子句的合取,其中每个子句都是文字的析取。这些表示形式可用于可满足性判定、自动推理和形式验证。
非经典解释
直觉主义逻辑
在直觉主义逻辑中,析取保留了引入规则和消去规则,但其含义不能完全由经典的二值真值表刻画。根据布劳威尔—海廷—柯尔莫哥洛夫解释, 的证据必须指明一个析取支,并给出该析取支的证据。
相应地,直觉主义逻辑具有析取性质:如果闭公式 在纯直觉主义逻辑中可证,那么 可证或 可证。经典逻辑不具有这一性质;它能证明 ,却一般不能证明其中的任何一个析取支。
经典等价关系
在直觉主义逻辑中一般不成立。左侧可以推出右侧,但反方向通常不可推导。
通过柯里—霍华德对应,构造性析取对应于和类型:一个值包含其中一种类型的元素,或另一种类型的元素,并附有标记以指明它属于哪一种情况。
其他非经典系统
多值逻辑可以将析取解释为作用于两个以上真值的运算。具体采用哪种运算,以及该运算如何与否定相互作用,取决于所用的系统。
在次协调逻辑中,一些常见的推理形式需要受到限制。特别是,当一个命题及其否定可以同时成立,却不导致任意命题都可推出时,析取三段论可能不成立。
历史背景
对“或”的不同解读的区分,早于现代符号记法。19 世纪代数逻辑的发展,尤其是乔治·布尔的工作,推动了用于命题和类推理的系统性代数方法的确立。后来的符号逻辑将析取确立为一种基本联结词,而用于开关电路的布尔方法的发展,则把同一种运算与数字计算联系起来。