Negation
Encyclopedia
In logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

 and mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, negation, also called logical complement, is an operation
Operation (mathematics)
The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation....

 on propositions, truth values, or semantic values more generally. Intuitively, the negation of a proposition is true when that proposition is false, and vice versa. In classical logic
Classical logic
Classical logic identifies a class of formal logics that have been most intensively studied and most widely used. The class is sometimes called standard logic as well...

 negation is normally identified with the truth function that takes truth to falsity and vice versa. In intuitionistic logic
Intuitionistic logic
Intuitionistic logic, or constructive logic, is a symbolic logic system differing from classical logic in its definition of the meaning of a statement being true. In classical logic, all well-formed statements are assumed to be either true or false, even if we do not have a proof of either...

, according to the Brouwer–Heyting–Kolmogorov interpretation, the negation of a proposition p is the proposition whose proofs are the refutations of p. In Kripke semantics
Kripke semantics
Kripke semantics is a formal semantics for non-classical logic systems created in the late 1950s and early 1960s by Saul Kripke. It was first made for modal logics, and later adapted to intuitionistic logic and other non-classical systems...

 where the semantic values of formulae are sets of possible worlds, negation is set-theoretic complementation.

Definition

Classical negation is an operation on one logical value
Logical value
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth.In classical logic, with its intended semantics, the truth values are true and false; that is, classical logic is a two-valued logic...

, typically the value of a proposition
Proposition
In logic and philosophy, the term proposition refers to either the "content" or "meaning" of a meaningful declarative sentence or the pattern of symbols, marks, or sounds that make up a meaningful declarative sentence...

, that produces a value of true when its operand is false and a value of false when its operand is true. So, if statement A is true, then ¬A would therefore be false; and conversely, if ¬A is true, then A would be false.

The truth table
Truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...

 of ¬p is as follows:
Truth table of ¬p
p ¬p
True False
False True


Classical negation can be defined in terms of other logical operations. For example, ¬p can be defined as pF, where "→" is logical implication and F is absolute falsehood. Conversely, one can define F as p & ¬p for any proposition p, where "&" is logical conjunction
Logical conjunction
In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....

. The idea here is that any contradiction
Contradiction
In classical logic, a contradiction consists of a logical incompatibility between two or more propositions. It occurs when the propositions, taken together, yield two conclusions which form the logical, usually opposite inversions of each other...

 is false. While these ideas work in both classical and intuitionistic logic, they do not work in Brazilian logic, where contradictions are not necessarily false. But in classical logic, we get a further identity: pq can be defined as ¬pq, where "∨" is logical disjunction
Logical disjunction
In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...

: "not p, or q".

Algebraically, classical negation corresponds to complementation in a Boolean algebra, and intuitionistic negation to pseudocomplementation in a Heyting algebra
Heyting algebra
In mathematics, a Heyting algebra, named after Arend Heyting, is a bounded lattice equipped with a binary operation a→b of implication such that ∧a ≤ b, and moreover a→b is the greatest such in the sense that if c∧a ≤ b then c ≤ a→b...

. These algebras provide a semantics
Algebraic semantics
An programming language theory, the algebraic semantics of a programming language is a form of axiomatic semantics based on algebraic laws for describing and reasoning about program semantics in a formal manner....

 for classical and intuitionistic logic respectively.

Notation

The negation of a proposition p is notated in different ways in various contexts of discussion and fields of application. Among these variants are the following:
Notation Vocalization
¬p not p
p not p
~p not p
Np en p
p prime,

p complement

p bar,

bar p

bang p


In Set Theory \ is also used to indicate 'not member of': U \ A is the set of all members of U that are not members of A.

No matter how it is notated or symbolized, the negation ¬p / −p can be read as "it is not the case that p", "not that p", or usually more simply (though not grammatically) as "not p".

Double negation

Within a system of classical logic
Classical logic
Classical logic identifies a class of formal logics that have been most intensively studied and most widely used. The class is sometimes called standard logic as well...

, double negation, that is, the negation of the negation of a proposition p, is logically equivalent to the p. Expressed in symbolic terms, ¬(¬p) ⇔ p. In intuitionistic logic
Intuitionistic logic
Intuitionistic logic, or constructive logic, is a symbolic logic system differing from classical logic in its definition of the meaning of a statement being true. In classical logic, all well-formed statements are assumed to be either true or false, even if we do not have a proof of either...

, 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
Intuitionistic logic
Intuitionistic logic, or constructive logic, is a symbolic logic system differing from classical logic in its definition of the meaning of a statement being true. In classical logic, all well-formed statements are assumed to be either true or false, even if we do not have a proof of either...

 we do have the equivalence of ¬¬¬p and ¬p. Moreover, in the propositional case, a sentence is classically provable if its double negation is intuitionistically provable. This result is known as Glivenko's theorem
Glivenko's theorem
Glivenko's theorem is a basic result showing a close connection between classical and intuitionistic propositional logic. It was proven by Valery Glivenko in 1929, with the aim of showing that intuitionistic logic is consistent and coherent...

.

Distributivity

~~
this is not true, you cannot distribute not across a logical equivalence. You can only distribute a negation of a statement.
~(P^Q) ~P v ~Q would be a correct display of distribution using de morgans law.(^ is and, v is or)

Linearity

In Boolean algebra, a linear function is one such that:

If there exists a0, a1, ... , an {0,1} such that
f(b1, ... , bn) = a0 ⊕ (a1 b1) ⊕ ... ⊕ (an bn), for all b1, ... , bn {0,1}.

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 one such that:

If f(a1, ... , an) = ~f(~a1, ... , ~an) for all a1, ... , an {0,1}. Negation is a self dual logical operator.

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
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...

 setting is to take as primitive rules of inference negation introduction (from a derivation of p to both q and ¬q, infer ¬p; this rule also being called reductio ad absurdum
Reductio ad absurdum
In logic, proof by contradiction is a form of proof that establishes the truth or validity of a proposition by showing that the proposition's being false would imply a contradiction...

), negation elimination (from p and ¬p infer q; this rule also being called ex falso quodlibet), and double negation elimination (from ¬¬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 ⊥. In this case the rule says that from p and ¬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 ¬p of p is defined as p→⊥. Then negation introduction and elimination are just special cases of implication introduction (conditional proof
Conditional proof
A conditional proof is a proof that takes the form of asserting a conditional, and proving that the antecedent of the conditional necessarily leads to the consequent....

) and elimination (modus ponens
Modus ponens
In classical logic, modus ponendo ponens or implication elimination is a valid, simple argument form. It is related to another valid form of argument, modus tollens. Both Modus Ponens and Modus Tollens can be mistakenly used when proving arguments...

). In this case one must also add as a primitive rule ex falso quodlibet.

Programming

As in mathematics, negation is used in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

 to construct logical statements.

if (!(r t))
{
/*...statements executed when r does NOT equal t...*/
}

The "!" signifies logical NOT in B, C, and languages with a C-inspired syntax such as C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...

, Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...

, JavaScript
JavaScript
JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....

, Perl
Perl
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...

, and PHP
PHP
PHP is a general-purpose server-side scripting language originally designed for web development to produce dynamic web pages. For this purpose, PHP code is embedded into the HTML source document and interpreted by a web server with a PHP processor module, which generates the web page document...

. "NOT" is the operator used in ALGOL 60
ALGOL 60
ALGOL 60 is a member of the ALGOL family of computer programming languages. It gave rise to many other programming languages, including BCPL, B, Pascal, Simula, C, and many others. ALGOL 58 introduced code blocks and the begin and end pairs for delimiting them...

, BASIC, and languages with an ALGOL-inspired syntax such as Pascal, Ada, Eiffel
Eiffel (programming language)
Eiffel is an ISO-standardized, object-oriented programming language designed by Bertrand Meyer and Eiffel Software. The design of the language is closely connected with the Eiffel programming method...

 and Seed7. Some languages (C++, Perl, etc.) provide more than one operator for negation. A few languages like PL/I
PL/I
PL/I is a procedural, imperative computer programming language designed for scientific, engineering, business and systems programming applications...

 and Ratfor
Ratfor
Ratfor is a programming language implemented as a preprocessor for Fortran 66. It provided modern control structures, unavailable in Fortran 66, to replace GOTOs and statement numbers.- Features :...

, use ¬ for negation. Some modern computers and operating systems will display ¬ as ! on files encoded in ASCII
ASCII
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...

.

In computer science there is also bitwise negation. This takes the value given and switches all the binary
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...

 1s to 0s and 0s to 1s. See bitwise operation
Bitwise operation
A bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. This is used directly at the digital hardware level as well as in microcode, machine code and certain kinds of high level languages...

. This is often used to create ones' complement
Signed number representations
In computing, signed number representations are required to encode negative numbers in binary number systems.In mathematics, negative numbers in any base are represented by prefixing them with a − sign. However, in computer hardware, numbers are represented in binary only without extra...

 or "~" in C or C++ and two's complement
Two's complement
The two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two...

 (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)
{
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 (note that depending on the compiler used, the actual instructions performed by the computer may differ).
See also
  • Logical conjunction
    Logical conjunction
    In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....

  • Logical disjunction
    Logical disjunction
    In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...

  • NOT gate
  • Bitwise NOT
  • Ampheck
  • Apophasis
    Apophasis
    Apophasis refers, in general, to "mention by not mentioning". Apophasis covers a wide variety of figures of speech.-Apophasis:...

  • Cyclic negation
  • Double negative elimination
    Double negative elimination
    In propositional logic, the inference rules double negative elimination allow deriving the double negative equivalent by adding or removing a pair of negation signs...

  • Grammatical polarity
    Grammatical polarity
    Grammatical polarity is the distinction of affirmative and negative. In English, grammatical polarity is generally indicated by the presence or absence of the modifier not, which negates the statement. Many other languages contain similar modifiers: Italian and Interlingua have non, Spanish has...

  • Minimal negation operator
  • Negation (linguistics)
  • Negation as failure
  • Square of opposition
    Square of opposition
    In the system of Aristotelian logic, the square of opposition is a diagram representing the different ways in which each of the four propositions of the system are logically related to each of the others...


External links
  • NOT, on MathWorld
    MathWorld
    MathWorld is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science Digital Library grant to the University of Illinois at...

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK