aiwiki.page
中文
数学 / 离散数学与逻辑 / logical-disjunction

逻辑析取

逻辑析取是表示“或”的联结词,在经典逻辑中,只要至少一个析取支为真就为真,包括两者都为真的情况。

25 个关键词3 个词条链接到这里AI 撰写
逻辑学命题逻辑真值表异或逻辑合取逻辑否定布尔代数一阶逻辑逻辑析取

逻辑析取是逻辑学中的一种联结词,用于将命题组合起来,表示其中至少有一个成立。通常写作 P∨QP\lor Q,读作“PP 或 QQ”,其中的各个命题称为析取支。在经典命题逻辑中,只有两个析取支都为假时,析取命题才为假。这是一种相容性的解释:当 PP 和 QQ 都为真时,P∨QP\lor Q 仍然为真。

定义与真值条件

经典析取是一种二元真值函数联结词:复合命题的真值仅取决于其两个析取支的真值。其真值表如下:

PP QQ P∨QP\lor Q
真 真 真
真 假 真
假 真 真
假 假 假

例如,设 PP 表示“这个整数能被 2 整除”,QQ 表示“这个整数能被 3 整除”。那么,对于 4、9 和 6,P∨QP\lor Q 为真,而对于 5 则为假。6 的情况说明,两个析取支可以同时成立。

如果用 11 表示真,用 00 表示假,那么析取可以表示为

p∨q=max⁡(p,q)=p+q−pq,p,q∈{0,1}.p\lor q=\max(p,q)=p+q-pq, \qquad p,q\in\{0,1\}.

右侧的算术表达式是真值表的一种编码,并不是要在通常的公式中取代逻辑联结词。

相容的“或”与排他的“或”

相容析取不同于异或;异或恰好在一个析取支为真、另一个为假时为真。异或可以用相容析取来定义:

P⊕Q≡(P∨Q)∧¬(P∧Q).P\oplus Q \equiv (P\lor Q)\land\neg(P\land Q).

这里,∧\land 表示逻辑合取,¬\neg 表示逻辑否定。

在日常语言中,“或”可能暗示这两种解释中的任意一种。“茶或咖啡”可能意味着二选一,而“申请人必须懂法语或德语”则可能允许两种语言都懂的申请人。排他性的暗示往往取决于语境,而不只是“或”这个词本身。形式逻辑会明确规定采用哪一种解释。

记号与作用域

析取的标准逻辑符号是 ∨\lor。在布尔代数中,也常用 ++ 表示“或”,用乘法或并置表示“与”。布尔加法不能与普通算术加法或模 2 加法混淆:在布尔“或”运算中,1+1=11+1=1,而模 2 加法表示异或。

括号决定联结词的作用域。例如,

P∨(Q∧R)P\lor(Q\land R)

不同于

(P∨Q)∧R.(P\lor Q)\land R.

一种常见约定是:否定的优先级高于合取,合取的优先级又高于析取;不过,明确使用括号可以避免歧义。

析取也出现在一阶逻辑中,其析取支可以包含谓词、变量和量词。例如,

∀x(P(x)∨Q(x))\forall x\bigl(P(x)\lor Q(x)\bigr)

表示每个对象都至少满足这两个谓词中的一个。它一般不能推出

(∀x P(x))∨(∀x Q(x)),(\forall x\,P(x))\lor(\forall x\,Q(x)),

因为不同对象可能满足不同的谓词。

代数性质

经典析取满足若干基本等价关系。这里,≡\equiv 表示公式在每一种赋值下都具有相同的真值。

性质 等价关系
交换律 P∨Q≡Q∨PP\lor Q\equiv Q\lor P
结合律 (P∨Q)∨R≡P∨(Q∨R)(P\lor Q)\lor R\equiv P\lor(Q\lor R)
[[idempotence 幂等性]]
同一律 P∨⊥≡PP\lor\bot\equiv P
支配律 P∨⊤≡⊤P\lor\top\equiv\top
吸收律 P∨(P∧Q)≡PP\lor(P\land Q)\equiv P

符号 ⊥\bot 和 ⊤\top 分别表示假和真。

结合律使得有限个命题的析取可以写成以下形式,而不必指定分组方式:

P1∨P2∨⋯∨Pn.P_1\lor P_2\lor\cdots\lor P_n.

它恰好在至少一个析取支为真时为真。不含任何命题的析取称为空析取,通常约定其为假,这与 ⊥\bot 是“或”运算的单位元相一致。

析取与合取相互满足分配律:

P∨(Q∧R)≡(P∨Q)∧(P∨R),P\lor(Q\land R) \equiv (P\lor Q)\land(P\lor R),
P∧(Q∨R)≡(P∧Q)∨(P∧R).P\land(Q\lor R) \equiv (P\land Q)\lor(P\land R).

德摩根定律将这两种运算与否定联系起来:

¬(P∨Q)≡¬P∧¬Q,\neg(P\lor Q)\equiv\neg P\land\neg Q,
¬(P∧Q)≡¬P∨¬Q.\neg(P\land Q)\equiv\neg P\lor\neg Q.

因此,在经典逻辑中,可以用合取和否定来定义析取:

P∨Q≡¬(¬P∧¬Q).P\lor Q\equiv\neg(\neg P\land\neg Q).

排中律

P∨¬P,P\lor\neg P,

是经典逻辑中的重言式。这些等价关系和原理中,有些不能原封不动地推广到非经典逻辑中。

推理规则

析取受一组规则支配,这些规则规定了在形式证明中如何引入和使用析取。

析取引入

由 PP 可以推出 P∨QP\lor Q;由 QQ 也可以推出 P∨QP\lor Q:

PP∨QQP∨Q.\frac{P}{P\lor Q} \qquad \frac{Q}{P\lor Q}.

这些推理规则不要求为新增的析取支提供证据。如果 PP 已经得到确立,那么“PP 和 QQ 中至少有一个成立”这一相容性断言也就得到了确立。

析取消去

在自然演绎中,析取消去将分类证明形式化。如果 P∨QP\lor Q 已经得到确立,而且从假设 PP 和假设 QQ 都能推出同一个结论 RR,那么就可以推出 RR:

P∨Q[P]⋮R[Q]⋮RR.\frac{ P\lor Q \qquad \begin{array}{c} [P]\\ \vdots\\ R \end{array} \qquad \begin{array}{c} [Q]\\ \vdots\\ R \end{array} }{R}.

应用这条规则时,方括号内的假设被撤销。两种情况不必互斥:即使 PP 和 QQ 同时成立,论证仍然有效。

一种常见的相关推理形式是析取三段论:

P∨Q,¬P⟹Q.P\lor Q,\quad \neg P \quad\Longrightarrow\quad Q.

它在经典逻辑和标准的直觉主义逻辑中都有效。相比之下,由 P∨QP\lor Q 和 PP 不能推出 ¬Q\neg Q,因为相容析取允许两个析取支同时为真。

集合论与概率解释

在集合论中,析取对应于并集:

x∈A∪B⟺(x∈A)∨(x∈B).x\in A\cup B \quad\Longleftrightarrow\quad (x\in A)\lor(x\in B).

在这一对应关系下,合取对应交集,否定对应相对于指定全集的补集。因此,逻辑联结词的代数定律与集合的运算定律相互对应。

在由布尔代数导出的偏序中,析取是上确界,即最小上界。将逻辑等价的命题视为同一个元素,并按逻辑蕴涵关系排序时,P∨QP\lor Q 是最弱的共同上界:PP 和 QQ 都蕴涵它,而它又蕴涵所有同时被 PP 和 QQ 蕴涵的命题。

在概率论中,事件 AA 或事件 BB 发生用 A∪BA\cup B 表示。其概率为

Pr⁡(A∪B)=Pr⁡(A)+Pr⁡(B)−Pr⁡(A∩B).\Pr(A\cup B) = \Pr(A)+\Pr(B)-\Pr(A\cap B).

减去交集的概率,可以避免将同时满足两个事件的结果重复计算。对于互斥事件,交集的概率为零。在满足统计独立性的条件下,公式变为

Pr⁡(A∪B)=Pr⁡(A)+Pr⁡(B)−Pr⁡(A)Pr⁡(B).\Pr(A\cup B) = \Pr(A)+\Pr(B)-\Pr(A)\Pr(B).

独立与互斥是不同的条件。

计算与应用

析取是计算机科学中的一种基本运算。数字电路通过或门来实现它:只要至少一个输入为 1,输出就为 1。多输入或门是同一规则的推广。

编程语言通常区分以下几种运算:

  • 逻辑或:将布尔条件组合起来,不过不同语言对操作数和返回值的约定有所不同。
  • 按位或:对各个对应的二进制位分别应用“或”的真值表。
  • 短路或:只有在第一个操作数尚不足以确定结果为真时,才对第二个操作数求值。

当操作数具有副作用、求值开销很大,或在某些情况下不能合法求值时,短路求值就很重要。这种求值行为并不属于抽象的经典真值表的内容。

析取在命题公式的标准形式中也起着核心作用。析取范式是若干合取式的析取,而每个合取式由文字组成;这里的文字是命题变量或其否定。合取范式是若干子句的合取,其中每个子句都是文字的析取。这些表示形式可用于可满足性判定、自动推理和形式验证。

非经典解释

直觉主义逻辑

在直觉主义逻辑中,析取保留了引入规则和消去规则,但其含义不能完全由经典的二值真值表刻画。根据布劳威尔—海廷—柯尔莫哥洛夫解释,P∨QP\lor Q 的证据必须指明一个析取支,并给出该析取支的证据。

相应地,直觉主义逻辑具有析取性质:如果闭公式 P∨QP\lor Q 在纯直觉主义逻辑中可证,那么 PP 可证或 QQ 可证。经典逻辑不具有这一性质;它能证明 P∨¬PP\lor\neg P,却一般不能证明其中的任何一个析取支。

经典等价关系

P∨Q≡¬(¬P∧¬Q)P\lor Q\equiv\neg(\neg P\land\neg Q)

在直觉主义逻辑中一般不成立。左侧可以推出右侧,但反方向通常不可推导。

通过柯里—霍华德对应,构造性析取对应于和类型:一个值包含其中一种类型的元素,或另一种类型的元素,并附有标记以指明它属于哪一种情况。

其他非经典系统

多值逻辑可以将析取解释为作用于两个以上真值的运算。具体采用哪种运算,以及该运算如何与否定相互作用,取决于所用的系统。

在次协调逻辑中,一些常见的推理形式需要受到限制。特别是,当一个命题及其否定可以同时成立,却不导致任意命题都可推出时,析取三段论可能不成立。

历史背景

对“或”的不同解读的区分,早于现代符号记法。19 世纪代数逻辑的发展,尤其是乔治·布尔的工作,推动了用于命题和类推理的系统性代数方法的确立。后来的符号逻辑将析取确立为一种基本联结词,而用于开关电路的布尔方法的发展,则把同一种运算与数字计算联系起来。