Logical negation is a unary operation in logic that forms the denial of a proposition. If is a proposition, its negation is usually written and read “not ” or “it is not the case that .” In classical logic, is true exactly when is false. Negation is fundamental to reasoning about contradictions, defining complements, expressing restrictions, and constructing mathematical proofs. Its interpretation is not identical in every logical system: some systems distinguish falsity from lack of evidence, or allow truth-value patterns beyond true and false.
Notation and scope
Common notations for negation include , , and, particularly in digital logic, . Programming languages often use !P or not P. These symbols belong to different notational conventions and need not have identical behavior outside their intended settings.
Negation takes one formula as its argument, unlike binary operations such as conjunction and disjunction. Its scope is the formula to which it applies. Parentheses can therefore change the meaning substantially:
- : it is not the case that both and hold.
- : does not hold, and does.
- : neither nor holds.
Negation usually binds more tightly than conjunction or disjunction, so ordinarily means . Explicit parentheses avoid dependence on such conventions.
Negation should also be distinguished from the denial of a particular word or predicate in ordinary language. The negation of “The object is red” is “The object is not red,” not “The object is blue.” A contrary assertion may exclude the original assertion without exhausting all the ways it could be false.
Classical semantics
In classical propositional logic, negation is truth-functional: its output depends only on the truth value of its argument. Its truth table is:
| True | False |
| False | True |
Writing true as and false as , a classical truth valuation satisfies
Thus negation reverses the two truth values. This numerical representation describes a logical operation; it does not make negation ordinary numerical subtraction in general.
Three central classical principles involve negation:
- Double negation: is logically equivalent to .
- Noncontradiction: is always true.
- Excluded middle: is always true.
The law of excluded middle concerns truth, not knowledge: it does not assert that a person can determine which alternative holds.
A proposition and its negation are contradictories in classical logic: exactly one is true. By contrast, two contrary propositions cannot both be true but may both be false.
Laws involving other logical operations
Negation interacts systematically with other connectives. De Morgan’s laws state that
and
Here denotes logical equivalence: the formulas have the same truth value under every classical valuation.
For example, “It is not both cold and wet” permits three possibilities: cold but not wet, wet but not cold, or neither. It does not mean “It is neither cold nor wet.”
For material implication,
so its negation is
Thus a classical conditional is false precisely when its antecedent is true and its consequent is false. Negating “If the switch is on, the lamp is lit” requires the switch to be on and the lamp not to be lit; it does not merely reverse the direction of the conditional.
Classical contraposition gives
These equivalences depend on the logical system. Some are not available in their full classical form in constructive or other nonclassical logics.
Negation and quantifiers
In first-order logic, negation interacts with universal and existential quantification. Classically,
and
Consequently:
- “Not every integer is even” means that at least one integer is not even.
- “There is no integer with the stated property” means that every integer lacks that property.
“Not all” must not be confused with “none.” The former denies universality; the latter denies the existence of any instance.
With multiple quantifiers, their order must be preserved while each quantifier is exchanged for the other as negation is moved inward. For example,
These transformations are important when stating counterexamples, negating definitions, and checking the meaning of mathematical claims.
Negation in mathematical proof
In natural deduction, negation is often characterized through a symbol , representing falsity or contradiction. A common definition is
To prove , one temporarily assumes and derives , then discharges the assumption. This is negation introduction. From together with , one may derive .
Classical proof by contradiction also permits proving by assuming and deriving a contradiction. The distinction matters: that argument first establishes , and the additional step to uses double-negation elimination.
A derivation of and is distinct from the rule that any conclusion follows from contradiction. The latter is called the principle of explosion. Classical and intuitionistic logic accept explosion, while some other systems do not.
Failure to prove a proposition is not itself a proof of its negation. In a formal theory, a statement can be undecided by the available axioms: neither the statement nor its negation need be derivable. This distinction separates semantic claims about truth from syntactic claims about provability.
Algebraic and set-theoretic interpretations
In Boolean algebra, negation is represented by complementation. For an element , its complement satisfies
In set theory, the corresponding operation is complement relative to a specified universe :
The universe is essential: a complement is not generally an unrestricted “set of everything not in .” Set union and intersection correspond to disjunction and conjunction, so De Morgan’s laws become identities about complements of unions and intersections.
In probability, if is an event and its complement, then
This describes the probability that an event does not occur, rather than a negative probability.
Nonclassical interpretations
Intuitionistic negation
In intuitionistic logic, is ordinarily understood as : a proof of would yield a contradiction. Under the Brouwer–Heyting–Kolmogorov interpretation, proving a negation therefore requires a construction that transforms any proposed proof of into a contradiction.
Intuitionistic logic validates
but does not validate for arbitrary . Refuting a refutation of a statement need not supply a constructive proof of the statement itself. Similarly, excluded middle is not a general intuitionistic theorem.
Some classical negation laws survive unchanged, while others weaken. For instance,
holds intuitionistically, whereas
is not generally valid.
Many-valued and paraconsistent systems
Many-valued logics introduce additional truth values and specify how negation acts on them. In a common three-valued treatment, negation exchanges true and false while leaving an “unknown” value unchanged. There is no single negation operation shared by all many-valued systems.
Paraconsistent logic rejects the unrestricted inference of arbitrary conclusions from a contradiction. Depending on the system, and may coexist without making every formula derivable. Paraconsistency by itself does not require the philosophical claim that contradictions are actually true.
These differences show that negation is characterized partly by its surrounding semantics and inference rules, not solely by the symbol .
Computing and practical interpretation
In computer science, logical NOT is used in conditional expressions, search filters, digital circuits, and formal verification. A Boolean NOT gate implements the classical two-valued truth table.
Logical negation must be distinguished from bitwise complement. Logical NOT reverses a Boolean condition, whereas bitwise complement reverses each bit in a representation. Their results and data types may differ.
Missing information also complicates negation. In SQL’s three-valued treatment of NULL, negating an unknown comparison ordinarily yields unknown rather than true. In some logic-programming systems, negation as failure treats the failure of a specified proof search as grounds for accepting a negative condition. This is an operational convention, not unrestricted classical inference from absence of proof.
Natural-language negation introduces further difficulties involving scope, context, and presupposition. “Everyone did not attend” may be read as either “Not everyone attended” or “Nobody attended.” Formal notation resolves such ambiguity by specifying exactly which proposition or quantified formula is negated.