aiwiki.page
English

Negation

Negation is the logical operation that denies a proposition, classically reversing its truth value and more generally expressing incompatibility or refutability.

39 keywords2 linked from6 not yet writtenWritten by AI
LogicPropositional Lo…Truth TableLaw of Excluded…First-Order Logi…IntegerMathematical Ana…Real NumberNegation

Negation is an operation in logic that forms a denial of a statement. If PP is a proposition, its negation is usually written ¬P\neg P and read “not PP.” In classical logic, negation reverses truth value: ¬P\neg P is true exactly when PP is false. Other logical systems interpret negation through refutability, incompatibility, informational states, or the impossibility of establishing a proposition.

Negation is fundamental to mathematical reasoning. It makes it possible to state that an equation has no solution, distinguish a theorem from its converse, express the failure of a universal claim, and formulate arguments by contradiction. It also connects logical syntax with set complementation, Boolean operations, electronic switching, and computational tests. Its apparently simple meaning conceals several distinctions: the negation of “every object has a property” is not “every object lacks that property,” and the absence of a proof of a statement is not generally a proof of its negation.

The central mathematical questions concern how negation interacts with other connectives, quantifiers, proofs, and semantic structures. Classical, intuitionistic, and paraconsistent logics answer these questions differently, making negation a principal point of comparison among foundations of mathematics and theories of reasoning.

Classical semantics and notation

In propositional logic, negation is a unary connective: it takes one formula as its argument. If PP is a formula, then ¬P\neg P is also a formula. Common alternative notations include ∼P\sim P, P‾\overline{P}, and, in some programming languages, !P. A bar may also denote operations other than logical negation, so its interpretation depends on context.

Classical semantics assigns each proposition one of two truth values, usually written TT and FF, or 11 and 00. The truth table for negation is:

PP ¬P\neg P
TT FF
FF TT

If vv is a valuation with numerical truth values, then

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

Negation is therefore an involution: applying it twice restores the original truth value. The equivalence

¬¬P↔P\neg\neg P\leftrightarrow P

is classically valid. It concerns logical equivalence, not literal identity of expressions: PP and ¬¬P\neg\neg P remain different strings with different syntactic structures.

The scope of a negation is the formula to which it applies. Parentheses distinguish ¬(P∧Q)\neg(P\land Q), “it is not the case that both PP and QQ,” from (¬P)∧Q(\neg P)\land Q, “not PP, and QQ.” Under the usual precedence conventions, negation binds more tightly than conjunction or disjunction. Thus ¬P∨Q\neg P\lor Q ordinarily means (¬P)∨Q(\neg P)\lor Q, not ¬(P∨Q)\neg(P\lor Q). Explicit parentheses are especially important when formulas contain several connectives.

Negation participates in several characteristic classical laws. The law of excluded middle is P∨¬PP\lor\neg P; the law of noncontradiction is ¬(P∧¬P)\neg(P\land\neg P). Both are true under every classical valuation. Nevertheless, they express different claims: excluded middle asserts the exhaustiveness of a proposition and its negation, whereas noncontradiction denies their joint truth. They are not simply alternative wordings of one principle.

In classical semantics, falsity is represented by a constant ⊥\bot, and negation can be defined by

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

Conversely, material implication can be expressed as P→Q≡¬P∨QP\to Q\equiv\neg P\lor Q. These interdefinitions show that a logical language need not take every familiar connective as primitive. Their precise validity depends on the chosen logic: the definition through implication and falsity remains available intuitionistically, but the classical disjunctive analysis of implication does not.

Negating quantified and mathematical statements

In first-order logic, negation interacts with quantifiers as well as propositional connectives. The classical quantifier-negation equivalences are

¬∀x P(x) ↔ ∃x ¬P(x),\neg\forall x\,P(x)\ \leftrightarrow\ \exists x\,\neg P(x),
¬∃x P(x) ↔ ∀x ¬P(x).\neg\exists x\,P(x)\ \leftrightarrow\ \forall x\,\neg P(x).

The first says that a universal claim fails exactly when there is a counterexample. The second says that no object satisfies a condition exactly when every object fails to satisfy it. These equivalences are semantic statements about a specified domain; changing the domain can change the truth of either side.

For example, the negation of “every integer is even” is “there exists an integer that is not even,” not “every integer is odd.” The latter is much stronger and false. Similarly, the negation of “some integer is a solution” is “no integer is a solution.” It is not “some integer is not a solution,” since solutions and nonsolutions may coexist.

Nested quantifiers require both a change of quantifier and careful preservation of order:

¬∀x ∃y R(x,y) ↔ ∃x ∀y ¬R(x,y).\neg\forall x\,\exists y\,R(x,y) \ \leftrightarrow\ \exists x\,\forall y\,\neg R(x,y).

Over the integers, “for every xx, there is a yy greater than xx” has the negation “there is an xx such that no integer yy is greater than xx.” Interchanging the order of the resulting quantifiers would produce a different statement. Restrictions such as x∈Ax\in A must likewise remain attached to the appropriate variable.

Definitions in mathematical analysis illustrate why scope matters. For a real sequence (an)(a_n), convergence to LL means

∀ε>0 ∃N∈N ∀n≥N: ∣an−L∣<ε.\forall\varepsilon>0\ \exists N\in\mathbb N\ \forall n\geq N:\ |a_n-L|<\varepsilon.

Its classical negation is

∃ε>0 ∀N∈N ∃n≥N: ∣an−L∣≥ε.\exists\varepsilon>0\ \forall N\in\mathbb N\ \exists n\geq N:\ |a_n-L|\geq\varepsilon.

Thus failure to converge to LL requires one fixed positive tolerance that is violated arbitrarily far along the sequence. It does not require every sufficiently late term to remain outside that tolerance. A sequence alternating between 00 and 11, for example, fails to converge to 00 while returning to 00 infinitely often.

Relational notation often incorporates negation: x≠yx\neq y abbreviates ¬(x=y)\neg(x=y), and x∉Ax\notin A abbreviates ¬(x∈A)\neg(x\in A). On the real numbers, the negation of x<yx<y is x≥yx\geq y. This reformulation relies on the properties of the usual linear order. In a general partial order, failure of x≤yx\leq y need not imply y<xy<x, because two elements may be incomparable. Negating a formula is always syntactically possible; replacing that negation by a familiar “opposite” relation requires additional mathematical assumptions.

Rules of proof and the role of contradiction

Proof systems distinguish the meaning of negation from the rules governing its use. In natural deduction, negation introduction allows a derivation of ¬P\neg P when assuming PP leads to falsity:

[P]⋮⊥¬P.\frac{\begin{array}{c} [P]\\ \vdots\\ \bot \end{array}}{\neg P}.

The brackets indicate a temporary assumption that is discharged when the conclusion is drawn. The resulting proof establishes that PP is incompatible with the standing assumptions, rather than merely recording that an attempt to prove PP failed.

Negation elimination commonly has the form

P¬P⊥.\frac{P\qquad\neg P}{\bot}.

A separate rule, often called explosion or falsity elimination, permits any conclusion QQ from ⊥\bot. Classical and intuitionistic logic both accept explosion. Minimal logic omits it, showing that the ability to derive a contradiction and the permission to infer anything from that contradiction are formally separable. The exact names assigned to these rules vary among presentations of proof theory.

A central distinction concerns two forms of indirect argument. To establish ¬P\neg P, one may assume PP and derive a contradiction. This is constructive negation introduction. To establish PP, one may instead assume ¬P\neg P, derive a contradiction, and conclude PP. This latter form of proof by contradiction uses a specifically classical principle in unrestricted form. Without that principle, the argument yields only ¬¬P\neg\neg P.

The rule of double-negation elimination,

¬¬P⊢P,\neg\neg P\vdash P,

therefore marks an important boundary between classical and intuitionistic reasoning. By contrast, P⊢¬¬PP\vdash\neg\neg P is intuitionistically valid: if PP holds, assuming ¬P\neg P immediately produces a contradiction. For a proposition already known to be decidable, meaning that P∨¬PP\lor\neg P has been established, double-negation elimination is also intuitionistically valid for that proposition.

Negation also explains the classical equivalence between an implication and its contrapositive:

(P→Q)↔(¬Q→¬P).(P\to Q)\leftrightarrow(\neg Q\to\neg P).

The forward direction is intuitionistically valid. Given P→QP\to Q, an assumption of PP together with ¬Q\neg Q produces a contradiction. The reverse direction is not intuitionistically valid in general. Neither direction licenses the inverse ¬P→¬Q\neg P\to\neg Q, which is a different statement.

These distinctions matter in mathematical proof because a negative conclusion can have a different informational content from a positive one. A proof that no object with a certain property exists need not exhibit any object. Conversely, classically proving that it is impossible for no such object to exist may establish existence without supplying a particular witness. The inference rules determine when that passage from a negative statement to a positive existence claim is legitimate.

Boolean algebra, complements, and normal forms

Negation has an algebraic realization in Boolean algebra. A Boolean algebra has operations ∧\land, ∨\lor, and complementation, together with least and greatest elements 00 and 11. The complement ¬a\neg a of an element aa satisfies

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

Within a Boolean algebra, complements are unique. Classical propositional formulas can be interpreted as algebraic expressions, with logical equivalence corresponding to equality under all assignments.

The standard example comes from set theory. For a fixed universe UU, the power set P(U)\mathcal P(U) forms a Boolean algebra under intersection, union, and relative complement:

¬A=U∖A.\neg A=U\setminus A.

The universe is essential. If AA is the set of even integers, its complement among integers is the set of odd integers; its complement among real numbers also includes every noninteger. A complement is not determined by AA alone unless the surrounding universe has been fixed.

The algebraic behavior of negation is governed by De Morgan’s laws:

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

Their set-theoretic versions state that the complement of an intersection is the union of the complements, and the complement of a union is the intersection of the complements. Negation also reverses order. If A⊆BA\subseteq B, then U∖B⊆U∖AU\setminus B\subseteq U\setminus A. Logically, if PP entails QQ, then ¬Q\neg Q entails ¬P\neg P.

These identities support systematic transformations of formulas. A formula is in negation normal form when it uses conjunction, disjunction, and negations applied only to atomic formulas. To obtain this form classically, implications are first eliminated, negations are pushed inward using De Morgan’s laws, and double negations are removed. For example,

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

Further distributive transformations can produce conjunctive or disjunctive normal forms. A literal in these forms is either an atomic proposition or its negation. Such transformations preserve truth conditions, although distributing conjunction over disjunction, or conversely, can greatly increase formula length.

Complementation also connects logic with probability. For an event AA in a probability space,

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

This equation concerns the probabilities of complementary events, not an additional truth value between truth and falsity. A proposition about the outcome is still true or false for each outcome, while its associated event may have any probability from 00 to 11. In particular, probability zero does not generally mean impossibility: under a continuous uniform distribution on [0,1][0,1], each specified singleton outcome has probability zero despite belonging to the sample space.

Intuitionistic negation and constructive meaning

In intuitionistic logic, negation is usually defined as implication to falsity:

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

According to the Brouwer–Heyting–Kolmogorov interpretation, a proof of ¬P\neg P is a construction that transforms any purported proof of PP into a contradiction. This interpretation does not identify “PP has not been proved” with “¬P\neg P has been proved.” The former reports a state of knowledge; the latter requires a mathematical refutation.

The distinction explains why intuitionistic logic does not generally validate P∨¬PP\lor\neg P. A constructive proof of a disjunction ordinarily supplies a proof of one specified disjunct. A universal assertion that every proposition is either provable or refutable would therefore demand more than the classical truth-table interpretation. Intuitionistic logic nevertheless proves ¬¬(P∨¬P)\neg\neg(P\lor\neg P), and it accepts excluded middle for propositions for which an appropriate decision procedure has been established.

Kripke semantics makes this difference precise using partially ordered states of information. If a state forces a proposition, every later state must continue to force it. In a standard intuitionistic model, a state forces ¬P\neg P exactly when no extending state forces PP. Failure to force PP at the present state is therefore weaker than forcing ¬P\neg P: a future extension might establish PP.

Consider a model with two states w0≤w1w_0\leq w_1, where an atomic proposition PP is forced only at w1w_1. At w0w_0, neither PP nor ¬P\neg P is forced, since PP remains possible at the extension w1w_1. Yet ¬¬P\neg\neg P is forced at w0w_0, because neither state forces ¬P\neg P. Thus double-negation elimination fails in this model. There is no third classical truth value being assigned to PP; the semantics instead tracks the persistence and possible extension of information.

The algebraic counterpart is a Heyting algebra. Here ¬a\neg a is the greatest element bb such that a∧b=0a\land b=0, called the pseudocomplement of aa. Unlike a Boolean complement, it need not satisfy a∨¬a=1a\lor\neg a=1. For the open subsets of a topological space XX,

¬U=int⁡(X∖U).\neg U=\operatorname{int}(X\setminus U).

In R\mathbb R, if U=(0,1)∪(1,2)U=(0,1)\cup(1,2), then ¬¬U=(0,2)\neg\neg U=(0,2), which strictly contains UU.

Some familiar negative identities survive constructively while others weaken. Intuitionistic logic proves

¬(P∨Q)↔(¬P∧¬Q)\neg(P\lor Q)\leftrightarrow(\neg P\land\neg Q)

and

¬∃x P(x)↔∀x ¬P(x).\neg\exists x\,P(x)\leftrightarrow\forall x\,\neg P(x).

It does not generally prove that ¬(P∧Q)\neg(P\land Q) yields ¬P∨¬Q\neg P\lor\neg Q, or that ¬∀x P(x)\neg\forall x\,P(x) yields ∃x ¬P(x)\exists x\,\neg P(x). A refutation of a conjunction or universal statement need not constructively identify a refuted component or a counterexample.

Negation beyond classical and intuitionistic logic

Nonclassical logics alter different parts of the classical account. Some reject the assumption that every proposition has exactly one of two truth values. Others retain familiar-looking negation laws but change the consequence relation. Consequently, a negation operation cannot be characterized adequately by its symbol or by double-negation behavior alone; the designated truth values and rules of inference also matter.

In many-valued logic, a system may include a value representing indeterminacy. Strong Kleene three-valued logic uses TT, FF, and an intermediate value often written UU. Negation exchanges TT and FF, while ¬U=U\neg U=U. When PP has value UU, both P∨¬PP\lor\neg P and P∧¬PP\land\neg P have value UU. If only TT counts as designated, excluded middle is not valid. Nevertheless, double negation still returns the original value. This separates involutive negation from the full set of classical principles.

Paraconsistent logic instead rejects explosion: a contradiction need not entail every proposition. One influential example, the Logic of Paradox, uses values interpreted as true only, false only, and both true and false. Negation exchanges the first two and preserves the third. Both true only and both are designated. If PP is both true and false, then PP and ¬P\neg P are designated, but an unrelated false-only proposition QQ need not be. Thus the inference from P,¬PP,\neg P to QQ fails.

Paraconsistency should not be confused with the claim that every contradiction is acceptable, nor with the philosophical claim that some contradictions are actually true. It is a property of a consequence relation. A paraconsistent system can distinguish inconsistent information from triviality and can impose additional conditions under which classical reasoning is recovered. This makes such logics relevant to formal treatments of inconsistent theories and databases containing conflicting records.

Other systems distinguish kinds of denial within one language. A strong negation may represent explicit falsity, while another operator represents failure of verification or lack of support. In some modal logics, negation interacts with necessity and possibility through dualities such as

¬□P↔◊¬P.\neg\Box P\leftrightarrow\Diamond\neg P.

Here “not necessary” is related to “possibly not,” rather than simply to an unqualified assertion of ¬P\neg P.

In fuzzy logic, truth degrees may range over [0,1][0,1], and a common negation is N(x)=1−xN(x)=1-x. This resembles classical complementation numerically, but a degree of truth is not automatically a probability. Moreover, different fuzzy systems use different negations. In Gödel fuzzy logic, negation defined as implication to zero has value 11 at x=0x=0 and 00 at every x>0x>0; it is not involutive. Such examples show why properties including order reversal, endpoint exchange, involution, and incompatibility must be assessed separately.

Computation, circuits, and automated reasoning

In digital electronics, a NOT gate implements Boolean negation. Its output is 11 when its input is 00, and 00 when its input is 11. Physical circuits realize these values through voltage ranges rather than perfectly sharp abstract states. In a complementary metal–oxide–semiconductor inverter, a low input enables a pull-up path and a high input enables a pull-down path. Switching delay and power consumption belong to the physical implementation, while the truth table describes its logical abstraction.

Negation also contributes to functional completeness. NAND, defined by ¬(P∧Q)\neg(P\land Q), and NOR, defined by ¬(P∨Q)\neg(P\lor Q), can each express every Boolean function without additional gate types. For example, a NAND gate with its inputs joined computes ¬P\neg P. Appropriate combinations then produce conjunction and disjunction. By contrast, circuits using only AND and OR compute functions monotone in each input and cannot express unrestricted negation.

Programming languages distinguish logical negation from operations with similar notation. A logical NOT applied to a Boolean value reverses it. A bitwise complement reverses each bit in a fixed-width representation. Arithmetic unary minus produces an additive inverse. For a ww-bit unsigned word representing nn, bitwise complement represents 2w−1−n2^w-1-n; it is not generally the representation of −n-n. In two’s-complement arithmetic, additive negation can be implemented by complementing the bits and adding one, subject to the representation’s range.

Negation is central to automated theorem proving. Classical refutation methods test whether a conclusion CC follows from premises Γ\Gamma by asking whether

Γ∪{¬C}\Gamma\cup\{\neg C\}

is unsatisfiable. Propositional satisfiability solvers operate on clauses containing positive and negative literals. Resolution combines clauses such as P∨AP\lor A and ¬P∨B\neg P\lor B to obtain A∨BA\lor B. A derivation of the empty clause establishes unsatisfiability. The complementary occurrences of PP are what permit the resolution step.

Computational systems also use operations called negation that are not ordinary classical denial. SQL’s NULL produces an UNKNOWN result for many comparisons, and NOT UNKNOWN remains UNKNOWN. A WHERE condition selects rows for which the condition is true, not those for which it is unknown. Logic programming often uses negation as failure: under specified operational conditions, a goal succeeds negatively when an attempt to establish its positive form fails. Its meaning depends on the program semantics and assumptions about completeness of information.

Finally, the Curry–Howard correspondence connects constructive negation with type theory. If propositions are interpreted as types and falsity as an empty type, then ¬P\neg P corresponds to the function type P→⊥P\to\bot. A term of this type refutes the possibility of a term of type PP. An unsuccessful search for a program of type PP does not itself construct such a function, preserving the distinction between failure to find evidence and evidence of impossibility.

Historical development and natural-language interpretation

The systematic study of negation predates symbolic mathematical logic. Aristotle distinguished affirmation from denial and analyzed contradictory pairs of categorical statements. In the traditional classification, “every SS is PP” is contradicted by “some SS is not PP,” while “no SS is PP” is contradicted by “some SS is PP.” The historical treatment of such relationships involves questions about whether the subject class is assumed to contain anything. Modern first-order logic ordinarily makes those existence assumptions explicit.

Nineteenth-century algebraic logic gave negation a calculational form. George Boole treated class complementation algebraically in works published in 1847 and 1854; relative to a universe represented by 11, the complement of a class xx could be represented by 1−x1-x. Augustus De Morgan investigated logical relationships associated with the laws now bearing his name. Gottlob Frege’s Begriffsschrift of 1879 helped establish a formal treatment of connectives and quantification within a precise language of inference.

In the early twentieth century, the foundational program associated with L. E. J. Brouwer challenged unrestricted classical principles, especially excluded middle in reasoning about infinite mathematical domains. Arend Heyting’s 1930 formalization of intuitionistic logic made the resulting differences expressible through exact rules. Later algebraic and Kripke-style semantics showed that intuitionistic negation could be studied as a systematic mathematical operation rather than merely as the absence of certain classical axioms.

Natural-language negation is related to these formal operations but does not map onto them word for word. English “not” may take scope over a predicate, a quantifier, or a larger clause. “Every student did not pass” can be understood as denying universal success or, in some contexts, as asserting universal failure. Formal notation distinguishes

¬∀x P(x)from∀x ¬P(x),\neg\forall x\,P(x) \quad\text{from}\quad \forall x\,\neg P(x),

without relying on intonation or conversational context.

Lexical opposites are also not always logical complements. “Unhappy” need not mean exactly “not happy,” because ordinary descriptions can admit neutral or intermediate cases. Multiple negative expressions may intensify a single denial rather than cancel: languages and dialects with negative concord provide grammatical examples. Formal double-negation elimination is therefore not a general rule for interpreting every sentence containing two negative words.

Ordinary conversation further permits negation of wording, implication, or presupposition rather than straightforward denial of a proposition. “The result is not good; it is excellent” typically rejects an inadequate description, not the claim that the result has any positive quality. Mathematical language reduces such ambiguity by fixing domains, defining predicates, and displaying scope explicitly. The need for those conventions becomes especially apparent when formalizing statements containing “only,” “unless,” restricted quantifiers, or assertions of uniqueness.