Editing Negation (section)

==Properties==

===Double negation===

Within a system of [[classical logic]], double negation, that is, the negation of the negation of a proposition <math>P</math>, is [[logically equivalent]] to <math>P</math>.  Expressed in symbolic terms, <math>\neg \neg P \equiv P</math>. 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 (mathematics)|involution]] of period two.

However, in [[intuitionistic logic]], the weaker equivalence <math>\neg \neg \neg P \equiv \neg P</math> does hold. This is because in intuitionistic logic, <math>\neg P</math> is just a shorthand for  <math>P \rightarrow \bot</math>, and we also have <math>P  \rightarrow \neg \neg P </math>. Composing that last implication with triple negation <math>\neg \neg P  \rightarrow  \bot </math> implies that <math>P \rightarrow \bot</math> .

As a result, in the propositional case, a sentence is classically provable if its double negation is intuitionistically provable. This result is known as [[Double-negation translation|Glivenko's theorem]].

===Distributivity===

[[De Morgan's laws]] provide a way of [[Distributive property|distributing]] negation over [[disjunction]] and [[logical conjunction|conjunction]]:

:<math>\neg(P \lor Q) \equiv (\neg P \land \neg Q)</math>,&nbsp; and
:<math>\neg(P \land Q) \equiv (\neg P \lor \neg Q)</math>.

===Linearity===
Let <math>\oplus</math> denote the logical [[xor]] operation. In [[Boolean algebra]], a linear function is one such that:

If there exists <math>a_0, a_1, \dots, a_n \in \{0,1\}</math>,
<math>f(b_1, b_2, \dots, b_n) = a_0 \oplus (a_1 \land b_1) \oplus \dots \oplus (a_n \land b_n)</math>,
for all <math>b_1, b_2, \dots, b_n \in \{0,1\}</math>.

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]], a self dual function is a function such that:

<math>f(a_1, \dots, a_n) = \neg f(\neg a_1, \dots, \neg a_n)</math> for all
<math>a_1, \dots, a_n \in \{0,1\}</math>.
Negation is a self dual logical operator.

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