logical negation

TheInfoList

OR:

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 premi ...
, 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-Ma ...
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 ...
$P$ to another proposition "not $P$", written $\neg P$, $\mathord P$ or $\overline$. It is interpreted intuitively as being true when $P$ is false, and false when $P$ 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 ...
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 pr ...
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 $P$ is the proposition whose proofs are the refutations of $P$.

# 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-Ma ...
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 ...
, 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 $\neg P$ (pronounced "not P") would then be false; and conversely, if $\neg P$ 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 argum ...
of $\neg P$ is as follows: : Negation can be defined in terms of other logical operations. For example, $\neg P$ can be defined as $P \rightarrow \bot$ (where $\rightarrow$ is logical consequence and $\bot$ is absolute falsehood). Conversely, one can define $\bot$ as $Q \land \neg Q$ for any proposition (where $\land$ 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 th ...
). The idea here is that any
contradiction In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle' ...
is false, and while these ideas work in both classical and intuitionistic logic, they do not work in paraconsistent logic, where contradictions are not necessarily false. In classical logic, we also get a further identity, $P \rightarrow Q$ can be defined as $\neg P \lor Q$, where $\lor$ 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 In mathematics, a Heyting algebra (also known as pseudo-Boolean algebra) is a bounded lattice (with join and meet operations written ∨ and ∧ and with least element 0 and greatest element 1) equipped with a binary operation ''a'' → ''b'' of ''i ...
. 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 comp ...
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 concer ...
, $\setminus$ is also used to indicate 'not in the set of': $U \setminus A$ is the set of all members of that are not members of . Regardless how it is notated or symbolized, the negation $\neg P$ 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 $P$, is
logically equivalent 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 premises ...
to $P$. Expressed in symbolic terms, $\neg \neg P \equiv P$. 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 $\neg \neg \neg P \equiv \neg P$ does hold. This is because in intuitionistic logic, $\neg P$ is just a shorthand for $P \rightarrow \bot$, and we also have $P \rightarrow \neg \neg P$. Composing that last implication with triple negation $\neg \neg P \rightarrow \bot$ implies that $P \rightarrow \bot$ . 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 In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathe ...
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 Conjunction may refer to: * Conjunction (grammar), a part of speech * Logical conjunction, a mathematical operator ** Conjunction introduction, a rule of inference of propositional logic * Conjunction (astronomy) In astronomy, a conjunction occ ...
: :$\neg\left(P \lor Q\right) \equiv \left(\neg P \land \neg Q\right)$,  and :$\neg\left(P \land Q\right) \equiv \left(\neg P \lor \neg Q\right)$.

## Linearity

Let $\oplus$ 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 $a_0, a_1, \dots, a_n \in \$, $f\left(b_1, b_2, \dots, b_n\right) = a_0 \oplus \left(a_1 \land b_1\right) \oplus \dots \oplus \left(a_n \land b_n\right)$, for all $b_1, b_2, \dots, b_n \in \$. 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: $f\left(a_1, \dots, a_n\right) = \neg f\left(\neg a_1, \dots, \neg a_n\right)$ for all $a_1, \dots, a_n \in \$. Negation is a self dual logical operator.

## Negations of quantifiers

In
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quant ...
, there are two quantifiers, one is the universal quantifier $\forall$ (means "for all") and the other is the existential quantifier $\exists$ (means "there exists"). The negation of one quantifier is the other quantifier ($\neg \forall xP\left(x\right)\equiv\exists x\neg P\left(x\right)$ and $\neg \exists xP\left(x\right)\equiv\forall x\neg P\left(x\right)$). For example, with the predicate ''P'' as "''x'' is mortal" and the domain of x as the collection of all humans, $\forall xP\left(x\right)$ means "a person x in all humans is mortal" or "all humans are mortal". The negation of it is $\neg \forall xP\left(x\right)\equiv\exists x\neg P\left(x\right)$, 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 In logic and proof theory, natural deduction is a kind of proof calculus in which logical reasoning is expressed by inference rules closely related to the "natural" way of reasoning. This contrasts with Hilbert-style systems, which instead use a ...
setting is to take as primitive rules of inference ''negation introduction'' (from a derivation of $P$ to both $Q$ and $\neg Q$, infer $\neg P$; this rule also being called ''
reductio ad absurdum In logic, ( Latin for "reduction to absurdity"), also known as ( Latin for "argument to absurdity") or ''apagogical arguments'', is the form of argument that attempts to establish a claim by showing that the opposite scenario would lead to a ...
''), ''negation elimination'' (from $P$ and $\neg P$ infer $Q$; this rule also being called ''ex falso quodlibet''), and ''double negation elimination'' (from $\neg \neg P$ infer $P$). 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 $P$ then $P$ must not be the case (i.e. $P$ 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 $\bot$. In this case the rule says that from $P$ and $\neg P$ 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 $\neg P$ of $P$ is defined as $P \rightarrow \bot$. Then negation introduction and elimination are just special cases of implication introduction ( conditional proof) and elimination ( modus ponens). 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 practical disciplines (includin ...
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, ofte ...
, Perl, and
PHP PHP is a general-purpose scripting language geared toward web development. It was originally created by Danish-Canadian programmer Rasmus Lerdorf in 1993 and released in 1995. The PHP reference implementation is now produced by The PHP Group. ...
. "NOT" is the operator used in ALGOL 60,
BASIC BASIC (Beginners' All-purpose Symbolic Instruction Code) is a family of general-purpose, high-level programming languages designed for ease of use. The original version was created by John G. Kemeny and Thomas E. Kurtz at Dartmouth College ...
, and languages with an ALGOL- or BASIC-inspired syntax such as Pascal, Ada, Eiffel and Seed7. Some languages (C++, Perl, etc.) provide more than one operator for negation. A few languages like
PL/I PL/I (Programming Language One, pronounced and sometimes written PL/1) is a procedural, imperative computer programming language developed and published by IBM. It is designed for scientific, engineering, business and system programming. ...
and
Ratfor Ratfor (short for ''Rational Fortran'') is a programming language implemented as a preprocessor for Fortran 66. It provides modern control structures, unavailable in Fortran 66, to replace GOTOs and statement numbers. Features Ratfor provide ...
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 operati ...
. This is often used to create
ones' complement The ones' complement of a binary number is the value obtained by inverting all the bits in the binary representation of the number (swapping 0s and 1s). The name "ones' complement" (''note this is possessive of the plural "ones", not of a si ...
or "~" in C or C++ and
two's complement Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
(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).

*
Affirmation and negation In linguistics and grammar, affirmation (abbreviated ) and negation () are ways in which grammar encodes positive and negative polarity into verb phrases, clauses, or other utterances. An affirmative (positive) form is used to express the vali ...
(grammatical polarity) * Ampheck *
Apophasis Apophasis (; , ) is a rhetorical device wherein the speaker or writer brings up a subject by either denying it, or denying that it should be brought up. Accordingly, it can be seen as a rhetorical relative of irony. The device is also called par ...
*
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 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 operati ...
*
Contraposition In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a stateme ...
* Cyclic negation *
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 th ...
*
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 argum ...