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

逻辑合取

逻辑合取是表示“且”的联结词,在经典逻辑中,当且仅当所有组成命题都为真时,合取命题才为真。

23 个关键词2 个词条链接到这里AI 撰写
命题逻辑逻辑学真值表自然演绎推理规则数学证明幂等性逻辑析取逻辑合取

逻辑合取是一种将命题组合起来,并断言它们同时成立的逻辑运算。在经典命题逻辑中,两个命题 PP 和 QQ 的合取写作 P∧QP\land Q,读作“PP 且 QQ”,当且仅当这两个命题都为真时才为真。参与组合的命题称为合取项。合取是逻辑学、数学推理和计算的基础:它用来表达同时成立的条件、组合假设,也是布尔与运算的基础。

记号与真值条件

合取的标准符号是 ∧\land。其他记法包括 P&QP\mathbin{\&}Q、P⋅QP\cdot Q,以及代数语境中的并置记法 PQPQ。编程语言通常使用 &&、and 或 AND,不过它们在实际执行时的行为有所不同。

在经典二值逻辑中,合取的真值表如下:

PP QQ P∧QP\land Q
真 真 真
真 假 假
假 真 假
假 假 假

因此,合取是真值函数性的:其真值只取决于各合取项的真值,而不取决于它们所涉及的内容,也不取决于它们之间是否存在因果关系。

例如,设 PP 为“12 是偶数”,QQ 为“12 能被 3 整除”。它们的合取为真,因为这两个命题都为真。相反,“12 是偶数且 12 是质数”为假,因为第二个合取项为假。

若用 11 表示真、用 00 表示假,则可以用乘法表示合取:

p∧q=pq,p,q∈{0,1}.p\land q=pq,\qquad p,q\in\{0,1\}.

这里,乘法作用于真值的数值编码,而不是命题本身。

逻辑中的“且”与日常语言

逻辑合取刻画了英语单词“and”的一种重要用法,但并不涵盖它的所有含义。

在经典逻辑中,P∧QP\land Q 与 Q∧PQ\land P 的真值相同。日常语言则可能通过语序传达额外的信息。“她打开门锁,然后走了进去”通常暗示一种时间顺序,而颠倒两个分句则会暗示另一种顺序。单凭合取本身并不能表达这种先后关系。

同样,“他按下开关,灯亮了”可能暗示因果关系,但其对应的逻辑合取只断言这两个事件都发生了。任何因果联系都需要另外表示。

并非“and”在语法上的每一种用法都连接完整的命题。“艾达和本抬起了钢琴”可以描述一次共同行动,而并不意味着艾达独自抬起了钢琴,本也独自抬起了钢琴。因此,将自然语言转化为合取时,需要辨明实际断言的是哪些命题。

形式推理中的合取

在自然演绎中,合取由一条引入规则和两条消去规则刻画。这些推理规则说明了如何确立一个合取命题,以及可以从中推出什么。

合取引入

如果已经在相容的假设下分别确立了 PP 和 QQ,就可以推出它们的合取:

PQP∧Q  (∧I).\frac{P\qquad Q}{P\land Q}\;(\land I).

更明确地说,如果从假设集 Γ\Gamma 可以分别推导出这两个命题,那么

Γ⊢PΓ⊢QΓ⊢P∧Q.\frac{\Gamma\vdash P\qquad\Gamma\vdash Q} {\Gamma\vdash P\land Q}.

符号 ⊢\vdash 表示在形式证明系统中的可推导性。

合取消去

从一个合取命题中,可以推出其中任意一个合取项:

P∧QP  (∧E1),P∧QQ  (∧E2).\frac{P\land Q}{P}\;(\land E_1), \qquad \frac{P\land Q}{Q}\;(\land E_2).

因此,对“nn 是正数且为偶数”的证明,既提供了 nn 是正数的证明,也提供了 nn 是偶数的证明。反过来,证明这两个断言,就确立了它们的合取。这些规则广泛用于数学证明,包括证明某个对象满足同时提出多项要求的定义。

不能将合取命题与条件命题混淆。P∧QP\land Q 断言两个命题都成立;“如果 PP,那么 QQ”通常并不单独断言其中任何一个命题成立。

代数定律

在经典逻辑中,合取满足以下定律。这里,≡\equiv 表示逻辑等价,⊤\top 表示真,⊥\bot 表示假。

定律 等价式
交换律 P∧Q≡Q∧PP\land Q\equiv Q\land P
结合律 (P∧Q)∧R≡P∧(Q∧R)(P\land Q)\land R\equiv P\land(Q\land R)
幂等律 P∧P≡PP\land P\equiv P
单位律 P∧⊤≡PP\land\top\equiv P
零律 P∧⊥≡⊥P\land\bot\equiv\bot
无矛盾律 P∧¬P≡⊥P\land\neg P\equiv\bot

结合律使得 P∧Q∧RP\land Q\land R 可以省略括号。幂等性意味着,重复一个合取项不会改变所得命题的真值条件。

合取与记作 ∨\lor 的逻辑析取之间满足分配律和吸收律:

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

合取与逻辑否定的关系由德摩根定律表达:

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

特别要注意,否定一个合取命题,意味着至少有一个合取项为假,而不是两个合取项都为假。这些等价式是经典逻辑的定律;在非经典系统中,其中一些需要附加限定。

布尔代数、集合与序

合取是布尔代数的基本运算之一。在抽象布尔代数中,它称为交运算。

合取的序论含义尤其有用。将逻辑等价的命题视为同一对象,并按逻辑蕴涵关系排序:当 PP 逻辑蕴涵 QQ 时,记作 P≤QP\leq Q。那么,P∧QP\land Q 就是两者的最大下界:

  • P∧QP\land Q 蕴涵 PP,也蕴涵 QQ。
  • 任何同时蕴涵 PP 和 QQ 的命题,也都蕴涵 P∧QP\land Q。

因此,合取将若干要求组合成一个命题,其强度至少不弱于其中任何一项单独的要求。这一解释将逻辑与偏序集联系起来。

在集合论中,合取对应于交集:

x∈A∩B⟺(x∈A)∧(x∈B).x\in A\cap B \quad\Longleftrightarrow\quad (x\in A)\land(x\in B).

集合 AA 和 BB 表示对元素的两个条件,而它们的交集恰好包含同时满足这两个条件的元素。

这种对应关系也解释了概率中的合取。对于事件 AA 和 BB,它们同时发生所构成的事件是 A∩BA\cap B。当 Pr⁡(A)>0\Pr(A)>0 时,

Pr⁡(A∩B)=Pr⁡(A)Pr⁡(B∣A).\Pr(A\cap B)=\Pr(A)\Pr(B\mid A).

只有在满足统计独立性时,才能将其中的条件概率替换为 Pr⁡(B)\Pr(B)。因此,独立事件的乘法公式并不是计算合取事件概率的一般规则。

多项合取与量化合取

有限多个命题可以使用带下标的记号组合起来:

⋀i=1nPi=P1∧P2∧⋯∧Pn.\bigwedge_{i=1}^{n}P_i = P_1\land P_2\land\cdots\land P_n.

这个表达式当且仅当每个 PiP_i 都为真时才为真。空命题族的合取通常约定为 ⊤\top。这样既保留了真作为单位元的性质,也符合“没有任何要求时,就没有要求被违反”的原则。

通常的一阶逻辑使用有限长度的公式。全称命题,例如

∀x P(x)\forall x\,P(x)

要求 P(x)P(x) 对论域中的每个对象都成立,但从语法上说,它是一个量化公式,而不是无限长的合取式。在一个固定的有限论域上,如果每个元素都有名称,就可以将它展开为有限合取式。有些无穷逻辑语言则明确允许无限合取式。

合取也出现在合取范式中。在这种形式下,公式表示为若干子句的合取,而每个子句都是文字的析取。例如,

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

就是合取范式。这种表示法在许多检验命题条件能否同时得到满足的自动化方法中起着核心作用。

计算与数字电路

数字与门对布尔输入实现合取运算:当且仅当所有输入都为 11 时,输出才为 11。由此类逻辑门与其他逻辑门共同组成的网络可以实现数字计算。

在编程中,合取通常用于组合判断条件,例如检查一个数是否位于某个区间内:

x >= 0 and x <= 10

许多语言采用短路求值:如果第一个操作数为假,就不再对第二个操作数求值。当第二个表达式会执行某个操作、引发错误或无法终止时,这一点就很重要。因此,尽管合取作为布尔运算满足交换律,交换两个程序表达式的顺序却可能改变程序行为。

按位与将同一个真值表分别应用于各对对应的二进制位。例如,

1100 AND 1010 = 1000

在许多语言中,按位运算符与逻辑运算符是不同的,它们的操作数类型、返回类型或求值规则也不一定相同。

数据库系统还带来了另一种需要注意的情况。对于许多涉及 NULL 的表达式,SQL 使用三值逻辑。例如,真 AND 未知的结果是未知,而假 AND 未知的结果是假。经典二值真值表无法完整描述这种行为。

构造性解释与非经典解释

在直觉主义逻辑中,合取保留了标准的引入规则和消去规则。按照布劳威尔—海廷—柯尔莫哥洛夫解释,P∧QP\land Q 的证明由一个 PP 的证明和一个 QQ 的证明共同组成。这比仅仅无法反驳其中任何一个命题更强。

通过柯里—霍华德对应,合取对应于积类型:一个见证 P∧QP\land Q 成立的值,包含一个见证 PP 成立的分量和另一个见证 QQ 成立的分量。构造这个有序对对应于合取引入;提取其中的分量则对应于合取消去。

其他非经典逻辑可能会改变合取的语义,或区分多种类似合取的运算。多值逻辑允许两个以上的真值。资源敏感逻辑可以区分“组合资源”与“提供使用资源的不同选择”。因此,仅凭 ∧\land 这样的记号,并不能确定所有经典布尔定律都适用。

历史发展

关于组合断言的推理早于现代符号记法的出现。19 世纪,乔治·布尔的工作使合取的代数处理成为核心内容;他的逻辑代数使用类似乘法的运算来表示条件的组合。

此后,命题逻辑、证明系统和布尔代数的发展,确立了合取的双重地位:它既是受推理规则支配的联结词,也是一种代数运算。20 世纪,克劳德·香农将布尔代数与开关电路联系起来,使合取成为数字硬件的数学描述与设计中的一项基本运算。