Negation#Programming

Classical negation is an operation on one logical value, typically the value of a proposition, that produces a value of true when its operand is false, and a value of false when its operand is true. Thus if statement $P$ is true, then $\backslash neg\; P$ (pronounced "not P") would then be false; and conversely, if $\backslash neg\; P$ is true, then $P$ would be false.

The truth table of $\backslash neg\; P$ is as follows:

:

Negation can be defined in terms of other logical operations. For example, $\backslash neg\; P$ can be defined as $P\; \backslash rightarrow\; \backslash bot$ (where $\backslash rightarrow$ is logical consequence and $\backslash bot$ is absolute falsehood). Conversely, one can define $\backslash bot$ as $Q\; \backslash land\; \backslash neg\; Q$ for any proposition {{mvar|Q}} (where $\backslash land$ is logical conjunction). 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, where contradictions are not necessarily false. As a further example, negation can be defined in terms of NAND and can also be defined in terms of NOR.

{{anchor|Algebra}} Algebraically, classical negation corresponds to complementation in a Boolean algebra, and intuitionistic negation to pseudocomplementation in a Heyting algebra. These algebras provide a semantics for classical and intuitionistic logic.

The negation of a proposition {{mvar|p}} is notated in different ways, in various contexts of discussion and fields of application. The following table documents some of these variants:

The notation $Np$ is Polish notation.

In set theory, $\backslash setminus$ is also used to indicate 'not in the set of': $U\; \backslash setminus\; A$ is the set of all members of {{mvar|U}} that are not members of {{mvar|A}}.

Regardless how it is notated or symbolized, the negation $\backslash neg\; P$ can be read as "it is not the case that {{mvar|P}}", "not that {{mvar|P}}", or usually more simply as "not {{mvar|P}}".

{{See also|Logical connective#Order of precedence}}

As a way of reducing the number of necessary parentheses, one may introduce precedence rules: ¬ has higher precedence than ∧, ∧ higher than ∨, and ∨ higher than →. So for example, $P\; \backslash vee\; Q\; \backslash wedge\{\backslash neg\; R\}\; \backslash rightarrow\; S$ is short for $(P\; \backslash vee\; (Q\; \backslash wedge\; (\backslash neg\; R)))\; \backslash rightarrow\; S.$

Here is a table that shows a commonly used precedence of logical operators.{{citation|title=Discrete Mathematics Using a Computer|first1=John|last1=O'Donnell|first2=Cordelia|last2=Hall|first3=Rex|last3=Page| publisher=Springer| year=2007| isbn=9781846285981|page=120|url=https://books.google.com/books?id=KKxyQQWQam4C&pg=PA120}}.

Within a system of classical logic, double negation, that is, the negation of the negation of a proposition $P$, is logically equivalent to $P$. Expressed in symbolic terms, $\backslash neg\; \backslash neg\; P\; \backslash 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 $\backslash neg\; \backslash neg\; \backslash neg\; P\; \backslash equiv\; \backslash neg\; P$ does hold. This is because in intuitionistic logic, $\backslash neg\; P$ is just a shorthand for $P\; \backslash rightarrow\; \backslash bot$, and we also have $P\; \backslash rightarrow\; \backslash neg\; \backslash neg\; P$. Composing that last implication with triple negation $\backslash neg\; \backslash neg\; P\; \backslash rightarrow\; \backslash bot$ implies that $P\; \backslash rightarrow\; \backslash 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.

De Morgan's laws provide a way of distributing negation over disjunction and conjunction:

:$\backslash neg(P\; \backslash lor\; Q)\; \backslash equiv\; (\backslash neg\; P\; \backslash land\; \backslash neg\; Q)$,  and

:$\backslash neg(P\; \backslash land\; Q)\; \backslash equiv\; (\backslash neg\; P\; \backslash lor\; \backslash neg\; Q)$.

Let $\backslash oplus$ denote the logical xor operation. In Boolean algebra, a linear function is one such that:

If there exists $a\_0,\; a\_1,\; \backslash dots,\; a\_n\; \backslash in\; \backslash \{0,1\backslash \}$,

$f(b\_1,\; b\_2,\; \backslash dots,\; b\_n)\; =\; a\_0\; \backslash oplus\; (a\_1\; \backslash land\; b\_1)\; \backslash oplus\; \backslash dots\; \backslash oplus\; (a\_n\; \backslash land\; b\_n)$,

for all $b\_1,\; b\_2,\; \backslash dots,\; b\_n\; \backslash in\; \backslash \{0,1\backslash \}$.

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.

In Boolean algebra, a self dual function is a function such that:

$f(a\_1,\; \backslash dots,\; a\_n)\; =\; \backslash neg\; f(\backslash neg\; a\_1,\; \backslash dots,\; \backslash neg\; a\_n)$ for all

$a\_1,\; \backslash dots,\; a\_n\; \backslash in\; \backslash \{0,1\backslash \}$.

Negation is a self dual logical operator.

In first-order logic, there are two quantifiers, one is the universal quantifier $\backslash forall$ (means "for all") and the other is the existential quantifier $\backslash exists$ (means "there exists"). The negation of one quantifier is the other quantifier ($\backslash neg\; \backslash forall\; xP(x)\backslash equiv\backslash exists\; x\backslash neg\; P(x)$ and $\backslash neg\; \backslash exists\; xP(x)\backslash equiv\backslash forall\; x\backslash neg\; P(x)$). For example, with the predicate P as "x is mortal" and the domain of x as the collection of all humans, $\backslash forall\; xP(x)$ means "a person x in all humans is mortal" or "all humans are mortal". The negation of it is $\backslash neg\; \backslash forall\; xP(x)\backslash equiv\backslash exists\; x\backslash neg\; P(x)$, meaning "there exists a person x in all humans who is not mortal", or "there exists someone who lives forever".

{{See also|Double negation}}

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 $P$ to both $Q$ and $\backslash neg\; Q$, infer $\backslash neg\; P$; this rule also being called reductio ad absurdum), negation elimination (from $P$ and $\backslash neg\; P$ infer $Q$; this rule also being called ex falso quodlibet), and double negation elimination (from $\backslash neg\; \backslash 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 $\backslash bot$. In this case the rule says that from $P$ and $\backslash 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 $\backslash neg\; P$ of $P$ is defined as $P\; \backslash rightarrow\; \backslash 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.

{{redirect|!vote|use of !votes in Wikipedia discussions|Wikipedia:Polling is not a substitute for discussion#Not-votes|selfref=yes}}

As in mathematics, negation is used in computer science to construct logical statements.

if (!(r == t))

{

/*...statements executed when r does NOT equal t...*/

}

The exclamation mark "!" signifies logical NOT in B, C, and languages with a C-inspired syntax such as C++, Java, JavaScript, Perl, and PHP. "NOT" is the operator used in ALGOL 60, BASIC, 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 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. This is often used to create ones' complement (or "~" in C or C++) and two's complement (just simplified to "-" or the negative sign, as this is equivalent to taking the arithmetic negation of the number).

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)

{

if (x < 0)

return -x;

else

return x;

}

To demonstrate logical negation:

unsigned int abs(int x)

{

if (!(x < 0))

return x;

else

return -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 (depending on the compiler used, the actual instructions performed by the computer may differ).

In C (and some other languages descended from C), double negation (!!x) is used as an idiom to convert x to a canonical Boolean, ie. an integer with a value of either 0 or 1 and no other. Although any integer other than 0 is logically true in C and 1 is not special in this regard, it is sometimes important to ensure that a canonical value is used, for example for printing or if the number is subsequently used for arithmetic operations.{{cite web |last1=Egan |first1=David |title=Double Negation Operator Convert to Boolean in C |url=https://dev-notes.eu/2019/10/Double-Negation-Operator-Convert-to-Boolean-in-C/ |website=Dev Notes}}

The convention of using ! to signify negation occasionally surfaces in ordinary written speech, as computer-related slang 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".Raymond, Eric and Steele, Guy. [https://books.google.com/books?id=g80P_4v4QbIC&pg=PA18&lpg=PA18 The New Hacker's Dictionary], p. 18 (MIT Press 1996).Munat, Judith. [https://books.google.com/books?id=UOPXXYslemYC&pg=PA148&lpg=PA148 Lexical Creativity, Texts and Context], p. 148 (John Benjamins Publishing, 2007).

In Kripke semantics where the semantic values of formulae are sets of possible worlds, negation can be taken to mean set-theoretic complementation{{citation needed|date=August 2012}} (see also possible world semantics for more).

{{Div col|colwidth=20em}}

• Affirmation and negation (grammatical polarity)
• Ampheck
• Apophasis
• Binary opposition
• Bitwise NOT
• Contraposition
• Cyclic negation
• Negation as failure
• NOT gate
• Plato's beard
• Square of opposition

{{Div col end}}

{{reflist}}

• Gabbay, Dov, and Wansing, Heinrich, eds., 1999. What is Negation?, Kluwer.
• Horn, L., 2001. A Natural History of Negation, University of Chicago Press.
• 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.
• {{cite journal | last1 = Tettamanti | first1 = Marco | last2 = Manenti | first2 = Rosa | last3 = Della Rosa | first3 = Pasquale A. | last4 = Falini | first4 = Andrea | last5 = Perani | first5 = Daniela | last6 = Cappa | first6 = Stefano F. | last7 = Moro | first7 = Andrea | year = 2008 | title = Negation in the brain: Modulating action representation | doi = 10.1016/j.neuroimage.2008.08.004 | journal = NeuroImage | volume = 43 | issue = 2| pages = 358–367 | pmid=18771737| s2cid = 17658822 }}

• {{cite SEP |url-id=negation |title=Negation |first=Laurence R. |last=Horn |first2=Heinrich |last2=Wansing}}
• {{springer|title=Negation|id=p/n066170}}
• [http://mathworld.wolfram.com/NOT.html NOT], on MathWorld

; Tables of Truth of composite clauses

• {{cite web|url= http://www.math.hawaii.edu/~ramsey/Logic/NotAnd.html|title= Table of truth for a NOT clause applied to an END sentence|archive-url= https://web.archive.org/web/20000301195359/http://www.math.hawaii.edu/~ramsey/Logic/NotAnd.html|archive-date= 1 March 2000|url-status= live}}
• {{cite web|url= http://www.math.hawaii.edu/~ramsey/Logic/NotAnd.html|title= NOT clause of an END sentence|archive-url= https://web.archive.org/web/20000301195359/http://www.math.hawaii.edu/~ramsey/Logic/NotAnd.html|archive-date= 1 March 2000|url-status= live}}
• {{cite web|url= http://www.math.hawaii.edu/~ramsey/Logic/NotOr.html|title= NOT clause of an OR sentence|archive-url= https://web.archive.org/web/20000117134708/http://www.math.hawaii.edu/~ramsey/Logic/NotOr.html|archive-date= 17 January 2000|url-status= live}}
• {{cite web|url= http://www.math.hawaii.edu/~ramsey/Logic/NotIfThen.html|title= NOT clause of an IF...THEN period|archive-url= https://web.archive.org/web/20000301223435/http://www.math.hawaii.edu/~ramsey/Logic/NotIfThen.html/|archive-date= 1 March 2000|url-status= live}}

{{Logical connectives}}

{{Common logical symbols}}

{{Formal semantics}}

{{Mathematical logic}}

{{Authority control}}

Category:Semantics

Category:Logical connectives

Category:Unary operations

Category:Articles with example C++ code

Category:Formal semantics (natural language)