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

逻辑否定

逻辑否定是否定命题的一元运算,在经典逻辑中反转真值,在非经典系统中则有不同解释。

17 个关键词3 个词条链接到这里AI 撰写
逻辑学命题逻辑真值表排中律德摩根定律一阶逻辑自然演绎反证法逻辑否定

逻辑否定是逻辑学中的一种一元运算,用于构成对一个命题的否定。如果 PP 是一个命题,它的否定通常写作 ¬P\neg P,读作“非 PP”或“并非 PP”。在经典逻辑中,¬P\neg P 为真当且仅当 PP 为假。否定是推理中处理矛盾、定义补集、表达限制条件以及构造数学证明的基础。不同逻辑系统对否定的解释并不完全相同:有些系统区分“为假”与“缺乏证据”,有些则允许真、假之外的真值情形。

记号与辖域

常见的否定记号包括 ¬P\neg P、∼P\sim P,以及尤其常用于数字逻辑的 P‾\overline{P}。编程语言则常用 !P 或 not P。这些符号分属不同的记号约定,在各自预定的使用环境之外,其行为未必相同。

否定只以一个公式为运算对象,这与合取、析取等二元运算不同。否定的辖域就是它所作用的公式。因此,括号可能显著改变表达式的含义:

  • ¬(P∧Q)\neg(P\land Q):并非 PP 和 QQ 同时成立。
  • (¬P)∧Q(\neg P)\land Q:PP 不成立,而 QQ 成立。
  • ¬(P∨Q)\neg(P\lor Q):PP 和 QQ 都不成立。

否定的优先级通常高于合取和析取,因此 ¬P∧Q\neg P\land Q 一般表示 (¬P)∧Q(\neg P)\land Q。明确加上括号,就不必依赖这类约定。

逻辑否定还应与日常语言中对某个特定词语或谓词的否认相区分。“这个物体是红色的”的否定是“这个物体不是红色的”,而不是“这个物体是蓝色的”。一个相反的断言可能排除原断言,却未必穷尽原断言为假的所有情形。

经典语义

在经典命题逻辑中,否定是真值函数性的:其输出仅取决于运算对象的真值。它的真值表如下:

PP ¬P\neg P
真 假
假 真

用 11 表示真、00 表示假,则经典真值赋值 vv 满足

v(¬P)=1−v(P).v(\neg P)=1-v(P).

因此,否定会反转这两个真值。这种数值表示描述的是一种逻辑运算,并不意味着否定一般就是普通的数值减法。

经典逻辑中有三条核心原则涉及否定:

  • 双重否定:¬¬P\neg\neg P 与 PP 逻辑等价。
  • 不矛盾律:¬(P∧¬P)\neg(P\land\neg P) 恒真。
  • 排中律:P∨¬PP\lor\neg 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).

这里的 ≡\equiv 表示逻辑等价:在每一种经典真值赋值下,等式两边的公式都有相同的真值。

例如,“并非既冷又潮湿”允许三种可能:冷但不潮湿、潮湿但不冷,或者既不冷也不潮湿。它并不等于“既不冷也不潮湿”。

对于实质蕴涵,有

P→Q≡¬P∨Q,P\to Q\equiv\neg P\lor Q,

因此它的否定为

¬(P→Q)≡P∧¬Q.\neg(P\to Q)\equiv P\land\neg Q.

所以,一个经典条件命题为假,当且仅当其前件为真、后件为假。否定“如果开关打开,灯就亮”意味着开关打开而灯不亮,而不是仅仅把条件命题的方向倒过来。

经典逻辑中的逆否等价给出

(P→Q)≡(¬Q→¬P).(P\to Q)\equiv(\neg Q\to\neg P).

这些等价关系取决于所采用的逻辑系统。在构造性逻辑或其他非经典逻辑中,其中一些关系并不能以完整的经典形式成立。

否定与量词

在一阶逻辑中,否定与全称量化、存在量化之间存在相应的关系。在经典逻辑中,

¬∀x P(x)≡∃x ¬P(x)\neg\forall x\,P(x)\equiv\exists x\,\neg P(x)

以及

¬∃x P(x)≡∀x ¬P(x).\neg\exists x\,P(x)\equiv\forall x\,\neg P(x).

因此:

  • “并非每个整数都是偶数”意味着至少有一个整数不是偶数。
  • “不存在具有所述性质的整数”意味着每个整数都不具有该性质。

“并非所有”不能与“一个也没有”混淆。前者否定普遍性,后者则否定任何实例的存在。

当公式含有多个量词时,在将否定向内移的过程中,需要逐一将两种量词互换,同时保持它们的次序不变。例如,

¬∀x ∃y R(x,y)≡∃x ∀y ¬R(x,y).\neg\forall x\,\exists y\,R(x,y) \equiv \exists x\,\forall y\,\neg R(x,y).

这些变换对于陈述反例、否定定义以及核查数学断言的含义都很重要。

数学证明中的否定

在自然演绎中,否定通常通过表示假或矛盾的符号 ⊥\bot 来刻画。一种常见定义是

¬P:=P→⊥.\neg P := P\to\bot.

要证明 ¬P\neg P,可以暂时假设 PP,由此推导出 ⊥\bot,然后解除该假设。这称为否定引入。由 PP 和 ¬P\neg P 可以推导出 ⊥\bot。

经典反证法还允许通过假设 ¬P\neg P 并推导出矛盾来证明 PP。这里的区别很重要:该论证首先确立的是 ¬¬P\neg\neg P,再进一步得到 PP 则要用到双重否定消去。

推导出 PP 和 ¬P\neg P,与允许从矛盾推出任意结论的规则并不是一回事。后者称为爆炸原理。经典逻辑和直觉主义逻辑都接受爆炸原理,而另一些系统则不接受。

未能证明一个命题,本身并不构成对其否定的证明。在一个形式理论中,现有公理可能无法判定某个陈述:该陈述及其否定都可能无法推导出来。这一区分将关于真值的语义断言与关于可证明性的句法断言区分开来。

代数与集合论解释

在布尔代数中,否定由取补运算表示。对于元素 aa,其补元 ¬a\neg a 满足

a∧¬a=0,a∨¬a=1.a\land\neg a=0, \qquad a\lor\neg a=1.

在集合论中,对应的运算是相对于指定全集 UU 取补集:

U∖A={x∈U:¬(x∈A)}.U\setminus A=\{x\in U:\neg(x\in A)\}.

全集不可或缺:补集一般并不是不受任何限制的“所有不属于 AA 的东西组成的集合”。集合的并与交分别对应析取与合取,因此德摩根定律便成为关于并集、交集之补集的恒等式。

在概率中,如果 AA 是一个事件,AcA^{c} 是其补事件,那么

Pr⁡(Ac)=1−Pr⁡(A).\Pr(A^{c})=1-\Pr(A).

它描述的是某事件不发生的概率,而不是负的概率。

非经典解释

直觉主义否定

在直觉主义逻辑中,¬P\neg P 通常理解为 P→⊥P\to\bot:对 PP 的证明会导出矛盾。按照布劳威尔—海廷—柯尔莫哥洛夫解释,证明一个否定命题,需要给出一种构造,能将任何提出的 PP 的证明转化为矛盾。

在直觉主义逻辑中,

P→¬¬P,P\to\neg\neg P,

是有效的,但对于任意 PP,¬¬P→P\neg\neg P\to P 并不普遍有效。驳倒对一个陈述的反驳,未必能给出该陈述本身的构造性证明。同样,排中律也不是直觉主义逻辑中的一般定理。

一些经典的否定定律保持不变,另一些则有所减弱。例如,

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

在直觉主义逻辑中成立,而

¬(P∧Q)→¬P∨¬Q\neg(P\land Q)\to\neg P\lor\neg Q

并不普遍有效。

多值系统与次协调系统

多值逻辑引入额外的真值,并规定否定如何作用于这些真值。在一种常见的三值处理中,否定交换真与假,同时保持“未知”值不变。并不存在所有多值系统共同采用的唯一否定运算。

次协调逻辑拒绝从矛盾不受限制地推出任意结论。视具体系统而定,PP 与 ¬P\neg P 可以共存,而不至于使每个公式都能被推导出来。次协调性本身并不要求接受“矛盾确实可以为真”这一哲学主张。

这些差异表明,否定的特征部分取决于它所处系统的语义和推理规则,而不只是符号 ¬\neg 本身。

计算与实际解释

在计算机科学中,逻辑非用于条件表达式、搜索筛选条件、数字电路和形式验证。布尔非门实现的就是经典二值真值表。

逻辑否定必须与按位取反区分开来。逻辑非反转一个布尔条件的真值,而按位取反则翻转某种表示中的每一个比特。两者的结果及数据类型可能不同。

信息缺失也会使否定变得复杂。在 SQL 对 NULL 的三值处理中,对结果未知的比较取否定,通常仍得到未知,而不是真。在一些逻辑编程系统中,失败即否定将指定的证明搜索失败视为接受某个否定条件的依据。这是一种操作层面的约定,并不是允许在经典逻辑中不受限制地从缺乏证明推出否定结论。

自然语言中的否定还会带来涉及辖域、语境和预设的其他困难。英语中的“Everyone did not attend”既可能被理解为“并非所有人都出席了”,也可能被理解为“没有人出席”。形式记号通过准确指定被否定的命题或量化公式,消除这类歧义。