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...
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...
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...
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.
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 p → F, 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....
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: p → q can be defined as ¬p ∨ q, 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...
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".
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.
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....
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.
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 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 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 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...
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...
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...
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...
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...
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...
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
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....
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...
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 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...
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...
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.
~
~P v ~Q would be a correct display of distribution using de morgans law.(^ is and, v is or)
{0,1} such that
b1) ⊕ ... ⊕ (an 
bn), for all b1, ... , bn 
{0,1}.
{0,1}. Negation is a self dual logical operator.
