In
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from prem ...
, negation, also called the logical complement, is an
operation
Operation or Operations may refer to:
Arts, entertainment and media
* ''Operation'' (game), a battery-operated board game that challenges dexterity
* Operation (music), a term used in musical set theory
* ''Operations'' (magazine), Multi-Man ...
that takes a
proposition
In logic and linguistics, a proposition is the meaning of a declarative sentence. In philosophy, " meaning" is understood to be a non-linguistic entity which is shared by all sentences with the same meaning. Equivalently, a proposition is the no ...
to another proposition "not
", written
,
or
. It is interpreted intuitively as being true when
is false, and false when
is true. Negation is thus a
unary logical connective
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...
. It may be applied as an operation on
notions,
proposition
In logic and linguistics, a proposition is the meaning of a declarative sentence. In philosophy, " meaning" is understood to be a non-linguistic entity which is shared by all sentences with the same meaning. Equivalently, a proposition is the no ...
s,
truth value
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values ('' true'' or '' false'').
Computing
In some pro ...
s, or
semantic values more generally. In
classical logic, negation is normally identified with the
truth function
In logic, a truth function is a function that accepts truth values as input and produces a unique truth value as output. In other words: The input and output of a truth function are all truth values; a truth function will always output exactly o ...
that takes ''truth'' to ''falsity'' (and vice versa). In
intuitionistic logic, according to the
Brouwer–Heyting–Kolmogorov interpretation, the negation of a proposition
is the proposition whose proofs are the refutations of
.
Definition
''Classical negation'' is an
operation
Operation or Operations may refer to:
Arts, entertainment and media
* ''Operation'' (game), a battery-operated board game that challenges dexterity
* Operation (music), a term used in musical set theory
* ''Operations'' (magazine), Multi-Man ...
on one
logical value, typically the value of a
proposition
In logic and linguistics, a proposition is the meaning of a declarative sentence. In philosophy, " meaning" is understood to be a non-linguistic entity which is shared by all sentences with the same meaning. Equivalently, a proposition is the no ...
, that produces a value of ''true'' when its operand is false, and a value of ''false'' when its operand is true. Thus if statement is true, then
(pronounced "not P") would then be false; and conversely, if
is false, then would be true.
The
truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arg ...
of
is as follows:
:
Negation can be defined in terms of other logical operations. For example,
can be defined as
(where
is
logical consequence
Logical consequence (also entailment) is a fundamental concept in logic, which describes the relationship between statements that hold true when one statement logically ''follows from'' one or more statements. A valid logical argument is on ...
and
is
absolute falsehood). Conversely, one can define
as
for any proposition (where
is
logical conjunction
In logic, mathematics and linguistics, And (\wedge) is the truth-functional operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective that represents thi ...
). The idea here is that any
contradiction is false, and while these ideas work in both classical and intuitionistic logic, they do not work in
paraconsistent logic
A paraconsistent logic is an attempt at a logical system to deal with contradictions in a discriminating way. Alternatively, paraconsistent logic is the subfield of logic that is concerned with studying and developing "inconsistency-tolerant" syst ...
, where contradictions are not necessarily false. In classical logic, we also get a further identity,
can be defined as
, where
is
logical disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor ...
.
Algebraically, classical negation corresponds to
complementation in a
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
, and intuitionistic negation to pseudocomplementation in a
Heyting algebra. These algebras provide a
semantics
Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy, linguistics and comput ...
for classical and intuitionistic logic, respectively.
Notation
The negation of a proposition is notated in different ways, in various contexts of discussion and fields of application. The following table documents some of these variants:
The notation N''p'' is
Łukasiewicz notation.
In
set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
,
is also used to indicate 'not in the set of':
is the set of all members of that are not members of .
Regardless how it is notated or
symbolized, the negation
can be read as "it is not the case that ", "not that ", or usually more simply as "not ".
Properties
Double negation
Within a system of
classical logic, double negation, that is, the negation of the negation of a proposition
, is
logically equivalent to
. Expressed in symbolic terms,
. In
intuitionistic logic, a proposition implies its double negation, but not conversely. This marks one important difference between classical and intuitionistic negation. Algebraically, classical negation is called an
involution of period two.
However, in
intuitionistic logic, the weaker equivalence
does hold. This is because in intuitionistic logic,
is just a shorthand for
, and we also have
. Composing that last implication with triple negation
implies that
.
As a result, in the propositional case, a sentence is classically provable if its double negation is intuitionistically provable. This result is known as
Glivenko's theorem.
Distributivity
De Morgan's laws provide a way of
distributing negation over
disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor ...
and
conjunction:
:
, and
:
.
Linearity
Let
denote the logical
xor
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
operation. In
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
, a linear function is one such that:
If there exists
,
,
for all
.
Another way to express this is that each variable always makes a difference in the
truth-value of the operation, or it never makes a difference. Negation is a linear logical operator.
Self dual
In
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
, a self dual function is a function such that:
for all
.
Negation is a self dual logical operator.
Negations of quantifiers
In
first-order logic, there are two quantifiers, one is the universal quantifier
(means "for all") and the other is the existential quantifier
(means "there exists"). The negation of one quantifier is the other quantifier (
and
). For example, with the predicate ''P'' as "''x'' is mortal" and the domain of x as the collection of all humans,
means "a person x in all humans is mortal" or "all humans are mortal". The negation of it is
, meaning "there exists a person ''x'' in all humans who is not mortal", or "there exists someone who lives forever".
Rules of inference
There are a number of equivalent ways to formulate rules for negation. One usual way to formulate classical negation in a
natural deduction setting is to take as primitive rules of inference ''negation introduction'' (from a derivation of
to both
and
, infer
; this rule also being called ''
reductio ad absurdum''), ''negation elimination'' (from
and
infer
; this rule also being called ''ex falso quodlibet''), and ''double negation elimination'' (from
infer
). One obtains the rules for intuitionistic negation the same way but by excluding double negation elimination.
Negation introduction states that if an absurdity can be drawn as conclusion from
then
must not be the case (i.e.
is false (classically) or refutable (intuitionistically) or etc.). Negation elimination states that anything follows from an absurdity. Sometimes negation elimination is formulated using a primitive absurdity sign
. In this case the rule says that from
and
follows an absurdity. Together with double negation elimination one may infer our originally formulated rule, namely that anything follows from an absurdity.
Typically the intuitionistic negation
of
is defined as
. Then negation introduction and elimination are just special cases of implication introduction (
conditional proof) and elimination (
modus ponens
In propositional logic, ''modus ponens'' (; MP), also known as ''modus ponendo ponens'' (Latin for "method of putting by placing") or implication elimination or affirming the antecedent, is a deductive argument form and rule of inference ...
). In this case one must also add as a primitive rule ''ex falso quodlibet''.
Programming language and ordinary language
As in mathematics, negation is used in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
to construct logical statements.
if (!(r t))
The
exclamation mark "
!
" signifies logical NOT in
B,
C, and languages with a C-inspired syntax such as
C++,
Java
Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's mo ...
,
JavaScript
JavaScript (), often abbreviated as JS, is a programming language that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of websites use JavaScript on the client side for webpage behavior, of ...
,
Perl
Perl is a family of two high-level, general-purpose, interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it also referred to its redesigned "sister language", Perl 6, before the latter's name was offic ...
, and
PHP. "
NOT
" is the operator used in
ALGOL 60,
BASIC, and languages with an ALGOL- or BASIC-inspired syntax such as
Pascal
Pascal, Pascal's or PASCAL may refer to:
People and fictional characters
* Pascal (given name), including a list of people with the name
* Pascal (surname), including a list of people and fictional characters with the name
** Blaise Pascal, Frenc ...
,
Ada
Ada may refer to:
Places
Africa
* Ada Foah, a town in Ghana
* Ada (Ghana parliament constituency)
* Ada, Osun, a town in Nigeria
Asia
* Ada, Urmia, a village in West Azerbaijan Province, Iran
* Ada, Karaman, a village in Karaman Province, T ...
,
Eiffel and
Seed7. Some languages (C++, Perl, etc.) provide more than one operator for negation. A few languages like
PL/I and
Ratfor use
¬
for negation. Most modern languages allow the above statement to be shortened from
if (!(r t))
to
if (r != t)
, which allows sometimes, when the compiler/interpreter is not able to optimize it, faster programs.
In computer science there is also ''bitwise negation''. This takes the value given and switches all the
binary 1s to 0s and 0s to 1s. See
bitwise operation
In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic oper ...
. This is often used to create
ones' complement or "
~
" in C or C++ and
two's complement (just simplified to "
-
" or the negative sign since this is equivalent to taking the arithmetic negative value of the number) as it basically creates the opposite (negative value equivalent) or mathematical complement of the value (where both values are added together they create a whole).
To get the absolute (positive equivalent) value of a given integer the following would work as the "
-
" changes it from negative to positive (it is negative because "
x < 0
" yields true)
unsigned int abs(int x)
To demonstrate logical negation:
unsigned int abs(int x)
Inverting the condition and reversing the outcomes produces code that is logically equivalent to the original code, i.e. will have identical results for any input (note that depending on the compiler used, the actual instructions performed by the computer may differ).
This convention occasionally surfaces in ordinary written speech, as computer-related
slang
Slang is vocabulary (words, phrases, and linguistic usages) of an informal register, common in spoken conversation but avoided in formal writing. It also sometimes refers to the language generally exclusive to the members of particular in-gr ...
for ''not''. For example, the phrase
!voting
means "not voting". Another example is the phrase
!clue
which is used as a synonym for "no-clue" or "clueless".
[Munat, Judith.]
Lexical Creativity, Texts and Context
p. 148 (John Benjamins Publishing, 2007).
Kripke semantics
In
Kripke semantics where the semantic values of formulae are sets of
possible worlds, negation can be taken to mean
set-theoretic complementation (see also
possible world semantics for more).
See also
*
Affirmation and negation (grammatical polarity)
*
Ampheck
*
Apophasis
*
Binary opposition
A binary opposition (also binary system) is a pair of related terms or concepts that are opposite in meaning. Binary opposition is the system of language and/or thought by which two theoretical opposites are strictly defined and set off against one ...
*
Bitwise NOT
*
Contraposition
*
Cyclic negation
In many-valued logic
Many-valued logic (also multi- or multiple-valued logic) refers to a propositional calculus in which there are more than two truth values. Traditionally, in Aristotle's logical calculus, there were only two possible values ( ...
*
Logical conjunction
In logic, mathematics and linguistics, And (\wedge) is the truth-functional operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective that represents thi ...
*
Logical disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor ...
*
Negation as failure
*
NOT gate
*
Plato's beard
*
Square of opposition
In term logic (a branch of philosophical logic), the square of opposition is a diagram representing the relations between the four basic categorical propositions.
The origin of the square can be traced back to Aristotle's tractate '' On Interp ...
*
Truth function
In logic, a truth function is a function that accepts truth values as input and produces a unique truth value as output. In other words: The input and output of a truth function are all truth values; a truth function will always output exactly o ...
*
Truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arg ...
References
Further reading
*
Gabbay, Dov, and Wansing, Heinrich, eds., 1999. ''What is Negation?'',
Kluwer.
*
Horn, L., 2001. ''A Natural History of Negation'',
University of Chicago Press
The University of Chicago Press is the largest and one of the oldest university presses in the United States. It is operated by the University of Chicago and publishes a wide variety of academic titles, including '' The Chicago Manual of Style' ...
.
*
G. H. von Wright, 1953–59, "On the Logic of Negation", ''Commentationes Physico-Mathematicae 22''.
* Wansing, Heinrich, 2001, "Negation", in Goble, Lou, ed., ''The Blackwell Guide to Philosophical Logic'',
Blackwell.
*
External links
*
*
NOT on
MathWorld
;
Tables of Truth of composite clauses
*
*
*
*
{{Mathematical logic
Semantics
Logical connectives
Unary operations
Articles with example C++ code
Formal semantics (natural language)