否定是逻辑学中对陈述加以否认的一种运算。若 是一个命题,其否定通常写作 ,读作“非 ”。在经典逻辑中,否定会反转真值: 为真,当且仅当 为假。其他逻辑系统则通过可反驳性、不相容性、信息状态,或确立某一命题的不可能性来解释否定。
否定是数学推理的基础。借助否定,可以陈述某个方程无解,区分一个定理及其逆命题,表达一个全称断言不成立,以及构造反证法论证。否定还将逻辑语法与集合的补运算、布尔运算、电子开关和计算中的条件判定联系起来。其看似简单的含义背后,隐藏着若干需要辨明的区别:“每个对象都具有某种性质”的否定,并不是“每个对象都不具有该性质”;而没有某个陈述的证明,通常也不等于证明了该陈述的否定。
有关否定的核心数学问题,在于它如何与其他联结词、量词、证明及语义结构相互作用。经典逻辑、直觉主义逻辑和次协调逻辑对这些问题给出了不同的回答,因此,否定成为比较各种数学基础体系与推理理论时的一个主要着眼点。
经典语义与记法
在命题逻辑中,否定是一元联结词,即以一个公式为参数。若 是公式,则 也是公式。其他常见记法包括 、,以及某些编程语言中的 !P。上划线也可以表示逻辑否定以外的运算,因此其含义取决于上下文。
经典语义为每个命题赋予两个真值之一,通常记作 和 ,或 和 。否定的真值表如下:
若 是采用数值真值的赋值,则
因此,否定是一种对合运算:连续应用两次便会恢复原来的真值。等价式
在经典逻辑中有效。这说的是逻辑等价,而非表达式在字面上完全相同: 和 仍是不同的字符串,具有不同的句法结构。
否定的辖域是它所作用的公式。括号用于区分 (“并非 和 都成立”)与 (“ 不成立,且 成立”)。按照通常的优先级约定,否定的结合优先级高于合取或析取。因此, 通常表示 ,而不是 。当公式包含多个联结词时,明确使用括号尤为重要。
否定出现在经典逻辑的若干典型定律中。排中律是 ;不矛盾律是 。两者在每一种经典赋值下都为真。不过,它们表达的是不同的主张:排中律断言一个命题及其否定穷尽了所有可能,而不矛盾律则否认两者同时为真。它们并非同一原理的两种说法。
在经典语义中,假由常量 表示,而否定可定义为
反过来,实质蕴涵可以表示为 。这些相互定义表明,逻辑语言不必将每一个常见联结词都作为初始符号。它们究竟是否有效,取决于所采用的逻辑:通过蕴涵和假来定义否定的方式在直觉主义逻辑中仍然适用,但经典逻辑中用析取来刻画蕴涵的方式则不适用。
量化陈述与数学陈述的否定
在一阶逻辑中,否定不仅与命题联结词相互作用,也与量词相互作用。经典逻辑中,量词与否定之间有如下等价关系:
第一条表示,全称断言不成立,当且仅当存在反例。第二条表示,没有任何对象满足某个条件,当且仅当每个对象都不满足该条件。这些等价关系是针对指定论域的语义陈述;改变论域,可能会改变等价式任一侧的真假。
例如,“每个整数都是偶数”的否定是“存在一个不是偶数的整数”,而不是“每个整数都是奇数”。后者是一个强得多的断言,而且是假的。同样,“某个整数是解”的否定是“没有整数是解”,而不是“某个整数不是解”,因为整数中可能既有解,也有非解。
否定含有嵌套量词的陈述时,既要变换量词,也要注意保持量词的顺序:
在整数范围内,“对每个 ,都存在一个大于 的 ”的否定是“存在一个 ,使得没有任何整数 大于 ”。如果交换否定后所得量词的顺序,就会得到不同的陈述。 这样的限制条件也必须始终附属于相应的变量。
数学分析中的定义说明了作用域为何重要。对于实数数列 ,收敛于 意味着
它在经典逻辑中的否定是
因此,不收敛于 要求存在一个固定的正容差,无论沿数列取到多靠后的位置,仍能找到超出该容差范围的项。这并不要求从某一项起,所有项都始终处于该容差范围之外。例如,一个在 和 之间交替取值的数列不收敛于 ,却会无穷多次回到 。
关系符号往往已包含否定的含义: 是 的简写, 是 的简写。在实数范围内, 的否定是 。这种改写依赖于通常的线性序所具有的性质。在一般的偏序中, 不成立未必意味着 ,因为两个元素可能不可比。从语法上说,总可以对一个公式取否定;但若要用某种熟悉的“相反”关系来替代这一否定,则需要额外的数学假设。
证明规则与矛盾的作用
证明系统将否定的含义与支配其使用的规则区分开来。在自然演绎中,如果假设 会导出谬误,否定引入规则就允许推导出 :
方括号表示一个临时假设,在得出结论时予以撤销。由此得到的证明表明, 与现有假设不相容,而不只是记录一次证明 的尝试未能成功。
否定消去规则通常具有如下形式:
另有一条通常称为爆炸律或谬误消去的规则,允许从 推出任意结论 。经典逻辑和直觉主义逻辑都接受爆炸律。极小逻辑则不采用这条规则,这表明,能够推导出矛盾与允许从该矛盾推出任何命题,在形式上是可以分离的。证明论的不同论述对这些规则的具体命名有所不同。
一个核心区别涉及两种间接论证形式。要证明 ,可以先假设 ,再导出矛盾。这是构造性的否定引入。要证明 ,则可以先假设 ,导出矛盾,再得出 。后一种反证法在不受限制地使用时,依赖一条特属于经典逻辑的原理。没有这条原理,该论证只能得到 。
因此,双重否定消去规则
标志着经典推理与直觉主义推理之间的一条重要界线。相比之下, 在直觉主义逻辑中是有效的:如果 成立,假设 就会立即产生矛盾。对于一个已知可判定的命题,也就是说,已经证明了 的命题,双重否定消去对该命题而言在直觉主义逻辑中同样有效。
否定也解释了蕴涵式与其逆否命题在经典逻辑中的等价关系:
从左到右的推导在直觉主义逻辑中有效。给定 ,假设 ,再结合 ,就会产生矛盾。从右到左的推导在直觉主义逻辑中则并非普遍有效。无论哪一个方向,都不能据此推出否命题 ,因为它是另一个不同的陈述。
这些区别在数学证明中很重要,因为否定性结论所包含的信息可能不同于肯定性结论。证明不存在具有某种性质的对象,并不需要给出任何对象。反过来,用经典逻辑证明“不存在这样的对象”是不可能的,可以确立其存在性,却不必给出一个具体的见证对象。从否定性陈述过渡到肯定性的存在断言在何种情况下是正当的,取决于所采用的推理规则。
布尔代数、补运算与范式
否定在布尔代数中有其代数实现。布尔代数具有运算 、 和补运算,以及最小元 和最大元 。元素 的补元 满足
在布尔代数中,补元是唯一的。经典命题公式可以解释为代数表达式,而逻辑等价则对应于在所有赋值下均相等。
标准例子来自集合论。对于固定的全集 ,幂集 在交、并和相对补运算下构成布尔代数:
全集的选择至关重要。如果 是偶整数集,那么它在整数集中的补集是奇整数集;而它在实数集中的补集还包含所有非整数。除非已经固定了所处的全集,否则仅凭 本身无法确定其补集。
否定的代数性质遵循德摩根定律:
它们的集合论形式表明,交集的补集等于各补集的并集,并集的补集等于各补集的交集。否定还会反转次序。如果 ,那么 。在逻辑上,如果 蕴涵 ,那么 蕴涵 。
这些恒等式为系统地变换公式提供了依据。如果一个公式仅使用合取、析取,以及只作用于原子公式的否定,那么它就是否定范式。在经典逻辑中,要得到这种形式,首先消去蕴涵,再利用德摩根定律将否定向内推进,并消去双重否定。例如,
进一步运用分配律,可以得到合取范式或析取范式。这些范式中的文字是原子命题或其否定。这类变换保持真值条件不变,但将合取对析取进行分配,或反过来将析取对合取进行分配,都可能使公式长度大幅增加。
这个等式涉及互补事件的概率,而不是介于真与假之间的额外真值。对于每一个结果,关于结果的命题仍然非真即假,而与该命题对应的事件可以具有从 到 的任意概率。特别是,概率为零通常并不意味着不可能:在 上的连续均匀分布下,每个由某一指定结果构成的单点事件的概率均为零,尽管该结果属于样本空间。
直觉主义否定与构造性含义
在直觉主义逻辑中,否定通常定义为蕴涵假:
根据布劳威尔—海廷—柯尔莫哥洛夫解释, 的证明是一种构造,它能将任何声称是 的证明的对象转化为矛盾。这种解释并不将“ 尚未得到证明”等同于“ 已得到证明”。前者描述的是知识状态,后者则要求在数学上作出反驳。
这一区别解释了为什么直觉主义逻辑一般不承认 普遍成立。一个析取命题的构造性证明通常必须给出某个确定的析取支的证明。因此,若普遍断言每个命题都可证明或可反驳,就需要比经典真值表解释更多的东西。尽管如此,直觉主义逻辑仍能证明 ,并且对于已建立适当判定程序的命题,它也接受排中律。
克里普克语义利用偏序排列的信息状态,精确刻画了这一区别。如果一个状态强迫某个命题,那么此后的每个状态都必须继续强迫该命题。在标准的直觉主义模型中,一个状态强迫 ,当且仅当它的任何扩展状态都不强迫 。因此,当前状态不强迫 ,比强迫 要弱:未来的某个扩展状态仍可能确立 。
考虑一个具有两个状态 的模型,其中原子命题 仅在 处被强迫。在 处, 和 都不被强迫,因为在扩展状态 处, 仍然是可能的。然而, 强迫 ,因为两个状态都不强迫 。因此,双重否定消去在这个模型中不成立。这里并没有给 赋予第三种经典真值;相反,这种语义追踪的是信息的持续性及其可能的扩展。
与之对应的代数结构是海廷代数。在这里, 是满足 的最大元素 ,称为 的伪补元。与布尔补元不同,它不一定满足 。对于拓扑空间 的开子集,有
在 中,若 ,则 ,它严格包含 。
一些熟悉的否定恒等式在构造性框架下仍然成立,另一些则只能以较弱的形式成立。直觉主义逻辑能够证明
以及
但一般而言,它不能证明由 可推出 ,也不能证明由 可推出 。对合取命题或全称命题的反驳,并不一定能以构造性方式指明某个被反驳的分项或给出一个反例。
经典逻辑与直觉主义逻辑之外的否定
非经典逻辑对经典逻辑中关于否定的说明作出了不同方面的修改。有些逻辑拒绝接受每个命题都恰好具有两个真值之一的假设;另一些逻辑则保留了形式上熟悉的否定律,却改变了后承关系。因此,仅凭否定运算的符号或双重否定的表现,并不足以充分刻画这一运算;指定真值和推理规则也同样重要。
在多值逻辑中,系统可以包含一个表示不确定性的真值。强克里普克三值逻辑使用 、 和一个通常记为 的中间值。否定将 与 互换,而 。当 的真值为 时, 和 的真值都为 。如果只有 被视为指定值,排中律就不成立。不过,双重否定仍会还原原来的真值。这表明,对合否定与整套经典逻辑原则并非一回事。
次协调逻辑则拒绝爆炸原理:矛盾不一定能推出任意命题。一个有影响力的例子是悖论逻辑,其真值分别解释为仅真、仅假以及亦真亦假。否定将前两个值互换,并保持第三个值不变。仅真和亦真亦假都是指定值。如果 亦真亦假,那么 和 都取指定值,但一个与之无关、仅假的命题 则不必取指定值。因此,从 到 的推理不成立。
次协调性不应与“任何矛盾都可以接受”的主张混为一谈,也不应与“某些矛盾确实为真”这一哲学主张混淆。它是后承关系的一种性质。次协调系统能够区分信息不一致与平凡性,也能够施加额外条件,使经典推理在这些条件下得以恢复。因此,这类逻辑适用于对不一致理论以及包含冲突记录的数据库进行形式化处理。
另一些系统则在同一种语言中区分不同类型的否认。强否定可以表示明确的虚假性,而另一种算子则表示未能验证或缺乏支持。在某些模态逻辑中,否定通过如下对偶关系与必然性和可能性相互联系:
这里的“不必然”对应的是“可能不”,而不只是无条件地断言 。
在模糊逻辑中,真值程度可以取遍 ,一种常见的否定运算是 。这在数值上类似于经典逻辑中的取补运算,但真值程度并不天然就是概率。此外,不同的模糊逻辑系统采用不同的否定运算。在哥德尔模糊逻辑中,将否定定义为蕴涵零时,其值在 处为 ,在所有 处均为 ;这种否定不具有对合性。这些例子说明,序反转性、端点互换性、对合性和不相容性等性质必须分别考察。
计算、电路与自动推理
在数字电子技术中,非门实现布尔否定。输入为 时,输出为 ;输入为 时,输出为 。实际电路通过电压范围来表示这些值,而非界限绝对分明的抽象状态。在互补金属氧化物半导体反相器中,低电平输入使上拉通路导通,高电平输入使下拉通路导通。开关延迟和功耗属于物理实现层面,而真值表描述的是电路的逻辑抽象。
否定也有助于实现函数完备性。与非运算定义为 ,或非运算定义为 ,二者都能在不使用其他类型逻辑门的情况下表达任意布尔函数。例如,将与非门的两个输入端连接在一起,就能计算 。再通过适当组合,即可实现合取和析取。相比之下,只使用与门和或门的电路所计算的函数对每个输入都具有单调性,无法表达不受限制的否定运算。
编程语言会区分逻辑否定与记号相似的其他运算。对布尔值应用逻辑非,会将其真值反转。按位取反会翻转固定位宽表示中的每一位。算术一元负号则产生加法逆元。对于表示 的 位无符号字,按位取反后的值为 ;它通常并不表示 。在二进制补码算术中,可以通过逐位取反再加一来实现算术取负,但须受该表示方式的取值范围限制。
否定在自动定理证明中具有核心地位。经典反驳法通过检验
是否不可满足,来判断结论 是否能从前提 推出。命题逻辑的布尔可满足性问题求解器处理由正文字和负文字组成的子句。归结法将 和 这样的子句结合起来,得到 。推导出空子句即可证明不可满足性。正是 的这两个互补出现,使这一归结步骤成为可能。
计算系统还使用一些称为否定、但并非普通经典否定的运算。在 SQL 中,涉及 NULL 的许多比较会产生 UNKNOWN 结果,而 NOT UNKNOWN 仍为 UNKNOWN。WHERE 条件只选出条件为真的行,不会选出条件为未知的行。逻辑编程常使用失败即否定:在规定的操作条件下,如果证明某个目标的肯定形式的尝试失败,那么该目标的否定形式便判为成功。其含义取决于程序语义以及对信息完备性的假设。
最后,柯里—霍华德对应将构造性否定与类型论联系起来。若将命题解释为类型,将假解释为空类型,那么 就对应于函数类型 。该类型的一个项表明,不可能存在类型为 的项。未能找到类型为 的程序,本身并不构成对这种函数的构造,因此,未能找到证据与拥有不可能性的证据之间的区别得以保留。
历史发展与自然语言解释
对否定的系统研究早于符号数理逻辑。亚里士多德区分了肯定与否定,并分析了直言命题之间的矛盾关系。在传统分类中,“所有 都是 ”与“有些 不是 ”相矛盾,而“没有 是 ”与“有些 是 ”相矛盾。历史上对这些关系的讨论涉及一个问题:是否预先假定主项所指的类中存在对象。现代一阶逻辑通常会明确表述这些存在性假设。
十九世纪的代数逻辑赋予了否定一种可供演算的形式。乔治·布尔在1847年和1854年出版的著作中,用代数方法处理类的补运算;相对于以 表示的全集,类 的补集可以表示为 。奥古斯塔斯·德摩根研究了与如今以他命名的定律相关的逻辑关系。戈特洛布·弗雷格于1879年出版的《概念文字》,推动了在精确的推理语言中对联结词和量化进行形式化处理。
二十世纪初,与 L. E. J. 布劳威尔相关的数学基础研究纲领,对不加限制地使用经典逻辑原则提出了挑战,尤其反对在涉及无限数学论域的推理中无条件使用排中律。阿伦德·海廷于1930年对直觉主义逻辑所作的形式化,使由此产生的差异能够通过精确的规则来表达。后来的代数语义和克里普克式语义表明,直觉主义否定可以作为一种系统的数学运算加以研究,而不只是被视为缺少某些经典公理的结果。
自然语言中的否定与这些形式运算有关,但两者并非逐词对应。英语中的“not”可以作用于谓词、量词或更大的分句。“Every student did not pass”(每个学生都没有通过)既可理解为否认所有学生都通过了,也可在某些语境中理解为断言所有学生都未通过。形式记号无需依赖语调或对话语境,就能区分
词汇上的反义词也不总是逻辑上的互补概念。“不开心”未必与“并非开心”完全同义,因为日常描述可能容许中性状态或中间状态。多个否定表达式也可能是在加强同一个否定,而不是相互抵消:具有否定一致现象的语言和方言,就提供了这方面的语法实例。因此,形式逻辑中的双重否定消去律,并不是解释所有含有两个否定词的句子时都适用的一般规则。
此外,日常对话还允许对措辞、隐含意义或预设加以否定,而不只是直接否认一个命题。“这个结果不是好,而是出色”通常是在否定一种不够恰当的描述,而非否认结果具有任何正面品质。数学语言通过固定论域、定义谓词以及明确展示作用域来减少这类歧义。在将含有“只有”“除非”、受限量词或唯一性断言的陈述形式化时,这些约定的必要性尤为明显。