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

逻辑等价

逻辑等价是指两个公式在指定逻辑所允许的每一种解释下都具有相同真值的关系。

21 个关键词1 个词条链接到这里2 个尚未撰写AI 撰写
逻辑学命题逻辑一阶逻辑等价关系逻辑后承真值表德摩根定律幂等性逻辑等价

逻辑等价是指两个公式在指定的逻辑学系统所允许的每一种解释下都具有相同真值的关系。在经典命题逻辑中,如果对两个公式的命题变元进行的每一种真值赋值,都使这两个公式具有相同的真值,那么它们就是逻辑等价的。在一阶逻辑中,两个公式必须在每一种结构以及对其自由变元的每一种赋值下都具有相同的真值。逻辑等价使我们能够用一个表达式替换另一个表达式,而不改变其逻辑内容。

定义与记号

对于经典命题公式 φ\varphi 和 ψ\psi,逻辑等价定义为

φ≡ψ⟺v(φ)=v(ψ) for every truth assignment v.\varphi \equiv \psi \quad\Longleftrightarrow\quad v(\varphi)=v(\psi) \text{ for every truth assignment }v.

这里,真值赋值为每个命题变元指定真或假,而逻辑联结词的含义决定了复合公式的真值。

例如,

p→q≡¬p∨q.p\to q \equiv \neg p\lor q.

这两个公式都恰好在 pp 为真且 qq 为假时为假。

常用记号包括 φ≡ψ\varphi\equiv\psi 和 φ⇔ψ\varphi\Leftrightarrow\psi,但具体约定有所不同。记号

⊨φ↔ψ\models\varphi\leftrightarrow\psi

表示这两个公式之间的双条件式是逻辑有效的。

逻辑等价是一种等价关系:

  • 自反性:φ≡φ\varphi\equiv\varphi。
  • **对称性:**如果 φ≡ψ\varphi\equiv\psi,那么 ψ≡φ\psi\equiv\varphi。
  • **传递性:**如果 φ≡ψ\varphi\equiv\psi 且 ψ≡χ\psi\equiv\chi,那么 φ≡χ\varphi\equiv\chi。

这一关系取决于所采用的逻辑及其语义。除非另有说明,基本的等价律通常都是针对经典逻辑而言的。

等价、双条件式与后承

必须区分逻辑等价与双条件式。表达式 φ↔ψ\varphi\leftrightarrow\psi 是所研究语言中的一个公式;而断言 φ≡ψ\varphi\equiv\psi 通常是一个关于两个公式的陈述。

双条件式可以在某一种解释下为真,却并非在所有解释下都有效。例如,只要 pp 和 qq 的真值相同,p↔qp\leftrightarrow q 就为真,但相互独立的变元 pp 和 qq 并不逻辑等价。

逻辑等价也可以通过相互的逻辑后承来刻画:

φ≡ψ⟺φ⊨ψ and ψ⊨φ.\varphi\equiv\psi \quad\Longleftrightarrow\quad \varphi\models\psi \text{ and } \psi\models\varphi.

单向后承是较弱的关系。例如,

p∧q⊨p,p\land q\models p,

但 pp 并不逻辑蕴涵 p∧qp\land q。因此,这个合取式与 pp 并不等价。

等价关注的是逻辑上的真值条件,而非措辞、所谈论的对象或解释作用。两个公式可能看起来截然不同,却彼此等价。反过来,两个在现实世界中碰巧都为真的陈述,也未必逻辑等价。

真值表

真值表提供了一种直接检验命题公式是否等价的方法。当且仅当两个公式的最终结果列在每一行都相同时,它们才是等价的。

蕴涵式及其析取形式的真值表如下:

pp qq p→qp\to q ¬p∨q\neg p\lor q
真 真 真 真
真 假 假 假
假 真 真 真
假 假 真 真

只要有一行的真值不同,就足以否定等价性。这样一行所对应的赋值称为反例赋值。

例如,一个蕴涵式通常并不等价于它的逆命题:

p→q≢q→p.p\to q\not\equiv q\to p.

令 pp 为假、qq 为真,就会使第一个蕴涵式为真,而第二个为假。

对于 nn 个不同的命题变元,完整的真值表有 2n2^n 行。因此,这种方法能够对任何有限的命题逻辑输入给出确定结论,但对于较大的公式,代价可能很高。

主要等价律

标准等价律提供了可以反复使用的变换方式,无须每次都构造完整的真值表。在以下公式中,⊤\top 表示真,⊥\bot 表示假。

定律 等价式
双重否定律 ¬¬p≡p\neg\neg p\equiv p
交换律 p∧q≡q∧pp\land q\equiv q\land p,以及 p∨q≡q∨pp\lor q\equiv q\lor p
结合律 (p∧q)∧r≡p∧(q∧r)(p\land q)\land r\equiv p\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),以及交换 ∧\land 和 ∨\lor 后得到的对偶定律
幂等律 p∧p≡pp\land p\equiv p,以及 p∨p≡pp\lor p\equiv p
吸收律 p∨(p∧q)≡pp\lor(p\land q)\equiv p,以及 p∧(p∨q)≡pp\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
蕴涵律 p→q≡¬p∨qp\to q\equiv\neg p\lor q
逆否律 p→q≡¬q→¬pp\to q\equiv\neg q\to\neg p
双条件律 p↔q≡(p→q)∧(q→p)p\leftrightarrow q\equiv(p\to q)\land(q\to p)
排中律 p∨¬p≡⊤p\lor\neg p\equiv\top
不矛盾律 p∧¬p≡⊥p\land\neg p\equiv\bot

德摩根定律描述了否定如何使合取与析取相互转换。幂等性和吸收律可以消除冗余成分。这些恒等式与其他定律共同支持系统性的公式化简和标准形式转换。

这些定律中的字母可以代表任意公式,而不仅仅是单个变元。

替换与代数结构

在经典命题逻辑中,逻辑等价允许进行替换:在一个较大的公式中,可以将某处出现的公式替换为与其等价的公式,而不改变整个公式的真值条件。

若 C[−]C[-] 是一个带有指定位置的公式,那么

φ≡ψ⟹C[φ]≡C[ψ].\varphi\equiv\psi \quad\Longrightarrow\quad C[\varphi]\equiv C[\psi].

例如,将 p→qp\to q 替换为 ¬p∨q\neg p\lor q,可得

r∧(p→q)≡r∧(¬p∨q).r\land(p\to q) \equiv r\land(\neg p\lor q).

这一性质成立,是因为经典逻辑联结词的输出完全由其输入的真值决定。

按照逻辑等价关系将公式划分为等价类,就会得到一种代数结构。合取、析取和否定在这些等价类上诱导出相应的运算,从而构成一个布尔代数。因此,语法形式不同的公式可以表示同一个布尔代数元素。

在涉及变元约束或含义依赖于语境的算子的语言中,替换需要更加谨慎。一阶逻辑中的替换必须避免自由变元被意外捕获。在自然语言中关于信念的陈述里,不能仅因两个表达式的真值相同就直接相互替换,否则可能改变陈述的含义。

一阶逻辑中的等价与背景理论

对于一阶公式,语义定义为

φ≡ψ⟺M,s⊨φ exactly when M,s⊨ψ\varphi\equiv\psi \quad\Longleftrightarrow\quad \mathcal M,s\models\varphi \text{ exactly when } \mathcal M,s\models\psi

其中要求上述条件对每一个结构 M\mathcal M 和每一种变元赋值 ss 都成立。

结构给出了论域,以及语言中非逻辑符号的解释。含有自由变元的公式需要指定赋值;而对于语句,其真假与赋值无关。

重要的量词等价式包括

¬∀x φ≡∃x ¬φ,¬∃x φ≡∀x ¬φ.\neg\forall x\,\varphi\equiv\exists x\,\neg\varphi, \qquad \neg\exists x\,\varphi\equiv\forall x\,\neg\varphi.

量词的顺序通常不能颠倒:

∀x ∃y R(x,y)≢∃y ∀x R(x,y).\forall x\,\exists y\,R(x,y) \not\equiv \exists y\,\forall x\,R(x,y).

第一个公式允许为每个 xx 选取不同的见证 yy;第二个公式则要求存在同一个见证,对每个 xx 都适用。

等价也可以定义为相对于理论 TT 的等价,其中 TT 是一组背景假设:

φ≡Tψ⟺T⊨φ↔ψ.\varphi\equiv_T\psi \quad\Longleftrightarrow\quad T\models\varphi\leftrightarrow\psi.

此时,两个公式只需要在 TT 的模型中具有相同的真值。例如,在以 ee 表示单位元的群语言中,公式 x⋅x=xx\cdot x=x 与 x=ex=e 相对于群公理是等价的,但在对这些符号作出解释的任意结构中则未必等价。这一区分在模型论中至关重要。

语义等价与可证等价

语义等价通过解释来定义。可证等价则通过证明系统来定义:可以在该系统中推导出双条件式,或者可以按照该系统的规则,从每个公式推导出另一个公式。

这两个概念通过可靠性与完备性联系起来。可靠性保证可推导的等价关系在语义上有效。完备性则保证每个语义等价关系都能在证明系统内得到证明。

对于标准的经典一阶逻辑演算,哥德尔完备性定理提供了这种联系。完备性并不意味着存在一种总能判定一阶公式是否等价的算法:对于任意一阶公式,不存在一种通用且总能终止的判定程序。

在自然演绎中,证明双条件式通常需要进行两个方向的推导:一是从 φ\varphi 推导出 ψ\psi,二是从 ψ\psi 推导出 φ\varphi。

计算中的用途与局限

逻辑等价是公式化简、数字电路比较、自动推理和形式验证的基础。

对于经典命题公式,等价性检验可以归约为可满足性检验:

φ≡ψ⟺(φ∧¬ψ)∨(¬φ∧ψ) is unsatisfiable.\varphi\equiv\psi \quad\Longleftrightarrow\quad (\varphi\land\neg\psi)\lor(\neg\varphi\land\psi) \text{ is unsatisfiable}.

上式中的公式表达的是异或:它恰好在原来的两个公式真值不同时为真。因此,使该公式为真的赋值就提供了一个否定等价性的反例。

对于任意命题公式,在标准的多项式时间归约下,等价性检验是 coNP 完全的。不过,实际使用的求解器仍然能够处理许多规模较大且具有一定结构的实例。

等价与等可满足性之间有一个重要区别。等可满足的公式仅仅在是否存在满足它们的解释这一点上一致;它们不必具有相同的满足解释。一些高效变换会引入辅助变元,保持的是可满足性,而不是扩充词汇表上的等价性。这对于许多可满足性任务已经足够,但不足以支持不受限制的替换。

对逻辑系统的依赖

经典逻辑中的等价式在其他逻辑中并不一定仍然成立。

在直觉主义逻辑中,

p→¬¬pp\to\neg\neg p

是有效的,但双重否定消去,即 ¬¬p→p\neg\neg p\to p,一般并不有效。因此,pp 与 ¬¬p\neg\neg p 在直觉主义逻辑中通常并不等价。同样,经典逻辑中将 p→qp\to q 与 ¬p∨q\neg p\lor q 视为等价的做法,在直觉主义逻辑中也不成立。

在多值逻辑和次协调逻辑中,定义等价时必须注意具体的语义。具有相同的语义值、彼此互为逻辑后承,以及两者之间的双条件式有效,这些条件未必刻画同一种关系。因此,提出等价性断言时,必须明确所采用的逻辑,并在相关情况下明确给出背景假设。