Negation

In logic, negation, also called the logical complement, is an operation that takes a proposition to another proposition "not ", written , which is interpreted intuitively as being true when is false, and false when is true. Negation is thus a unary (single-argument) logical connective. It may be applied as an operation on notions, propositions, truth values, or semantic values more generally. In classical logic, negation is normally identified with the truth function that takes truth to falsity and vice versa. In intuitionistic logic, according to the Brouwer–Heyting–Kolmogorov interpretation, the negation of a proposition is the proposition whose proofs are the refutations of .

Negation
NOT
Definition
Truth table
NOT ANSI
Normal forms
Disjunctive
Conjunctive
Zhegalkin polynomial
Post's lattices
0-preservingno
1-preservingno
Monotoneno
Affineyes
Self-dualyes

Definition

No agreement exists as to the possibility of defining negation, as to its logical status, function, and meaning, as to its field of applicability..., and as to the interpretation of the negative judgment, (F.H. Heinemann 1944).[1]

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. So, if statement is true, then (pronounced "not P") would therefore be false; and conversely, if is false, then would be true.

The truth table of is as follows:

True False
False True

Negation can be defined in terms of other logical operations. For example, can be defined as (where is logical consequence and is absolute falsehood). Conversely, one can define as for any proposition (where is logical conjunction). The idea here is that any contradiction is false. 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, can be defined as , where is logical disjunction.

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

Notation

The negation of a proposition is notated in different ways in various contexts of discussion and fields of application. Among these variants are the following:

Notation Plain Text Vocalization
¬p Not p
~p Not p
-p Not p
Np En p
p'
  • p prime,
  • p complement
̅p
  • p bar,
  • Bar p
!p
  • Bang p
  • Not p

The notation Np is Łukasiewicz notation.

In set theory is also used to indicate 'not member of': is the set of all members of that are not members of .

No matter how it is notated or symbolized, the negation 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 , is logically equivalent to . Expressed in symbolic terms, . 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 we do have the equivalence of . 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.

Distributivity

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

,  and
.

Linearity

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

If there exists , , for all .

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:

for all . 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 setting is to take as primitive rules of inference negation introduction (from a derivation of to both and , infer ; this rule also being called reductio ad absurdum), negation elimination (from and infer ; this rule also being called ex falso quodlibet), and double negation elimination (from infer ). 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 then must not be the case (i.e. 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 and 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 of is defined as . 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

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 "!" 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. Some modern computers and operating systems will display ¬ as ! on files encoded in ASCII. 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. This is often used to create ones' complement or "~" in C or C++ and two's complement (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).

This convention occasionally surfaces in written speech, as computer-related slang for not. The phrase !voting, for example, means "not voting".

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

See also

References

  1. ^ Horn, Laurence R (2001). "Chapter 1". A NATURAL HISTORY OF NEGATION (PDF). Stanford University: CLSI Publications. p. 1. ISBN 1-57586-336-7. Retrieved 29 December 2013.

Further reading

  • 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.
  • Tettamanti, Marco; Manenti, Rosa; Della Rosa, Pasquale A.; Falini, Andrea; Perani, Daniela; Cappa, Stefano F.; Moro, Andrea (2008). "Negation in the brain: Modulating action representation". NeuroImage. 43 (2): 358–367. doi:10.1016/j.neuroimage.2008.08.004. PMID 18771737.

External links

Tables of Truth of composite clauses
Additive inverse

In mathematics, the additive inverse of a number a is the number that, when added to a, yields zero.

This number is also known as the opposite (number), sign change, and negation. For a real number, it reverses its sign: the opposite to a positive number is negative, and the opposite to a negative number is positive. Zero is the additive inverse of itself.

The additive inverse of a is denoted by unary minus: −a (see the discussion below). For example, the additive inverse of 7 is −7, because 7 + (−7) = 0, and the additive inverse of −0.3 is 0.3, because −0.3 + 0.3 = 0 .

The additive inverse is defined as its inverse element under the binary operation of addition (see the discussion below), which allows a broad generalization to mathematical objects other than numbers. As for any inverse operation, double additive inverse has no net effect: −(−x) = x.

Adzera language

Adzera (also spelled Atzera, Azera, Atsera, Acira) is an Austronesian language spoken by about 30,000 people in Morobe Province, Papua New Guinea.

Affirmation and negation

In linguistics and grammar, affirmation and negation (abbreviated respectively AFF and NEG) are the ways that grammar encodes negative and positive polarity in verb phrases, clauses, or other utterances. Essentially an affirmative (positive) form is used to express the validity or truth of a basic assertion, while a negative form expresses its falsity. Examples are the sentences "Jane is here" and "Jane is not here"; the first is affirmative, while the second is negative.

The grammatical category associated and with affirmative and negative is called polarity. This means that a sentence, verb phrase, etc. may be said to have either affirmative or negative polarity (its polarity may be either affirmative or negative). Affirmative is typically the unmarked polarity, whereas a negative statement is marked in some way, whether by a negating word or particle such as English not, an affix such as Japanese -nai, or by other means, which reverses the meaning of the predicate. The process of converting affirmative to negative is called negation – the grammatical rules for negation vary from language to language, and a given language may have more than one method of doing so.

Affirmative and negative responses (especially, though not exclusively, to questions) are often expressed using particles or words such as yes and no, where yes is the affirmative and no the negative particle.

Aptamimamsa

Aptamimamsa (also Devāgamastotra) is a Jain text composed by Acharya Samantabhadra, a Jain acharya said to have lived about the latter part of the second century A.D. Āptamīmāṁsā is a treatise of 114 verses which discusses the Jaina view of Reality, starting with the concept of omniscience (Kevala Jnana) and the attributes of the Omniscient.

Cotard delusion

Cotard delusion is a rare mental illness in which the affected person holds the delusional belief that they are already dead, do not exist, are putrefying, or have lost their blood or internal organs. Statistical analysis of a hundred-patient cohort indicates that the denial of self-existence is a symptom present in 45% of the cases of Cotard's syndrome; 55% of the patients present delusions of immortality.In 1880, the neurologist Jules Cotard described the condition as Le délire des négations ("The Delirium of Negation"), a psychiatric syndrome of varied severity. A mild case is characterized by despair and self-loathing, while a severe case is characterized by intense delusions of negation and chronic psychiatric depression. The case of Mademoiselle X describes a woman who denied the existence of parts of her body and of her need to eat. She said that she was condemned to eternal damnation and therefore could not die a natural death. In the course of suffering "The Delirium of Negation", Mademoiselle X died of starvation.

The Cotard delusion is not mentioned in either the Diagnostic and Statistical Manual of Mental Disorders (DSM) or the tenth edition of the International Statistical Classification of Diseases and Related Health Problems (ICD-10) of the World Health Organization.

De Morgan's laws

In propositional logic and boolean algebra, De Morgan's laws are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathematician. The rules allow the expression of conjunctions and disjunctions purely in terms of each other via negation.

The rules can be expressed in English as:

the negation of a disjunction is the conjunction of the negations; and
the negation of a conjunction is the disjunction of the negations;

or

the complement of the union of two sets is the same as the intersection of their complements; and
the complement of the intersection of two sets is the same as the union of their complements.

or

not (A or B) = not A and not B; and
not (A and B) = not A or not B

In set theory and Boolean algebra, these are written formally as

where

In formal language, the rules are written as

and

where

Applications of the rules include simplification of logical expressions in computer programs and digital circuit designs. De Morgan's laws are an example of a more general concept of mathematical duality.

Dialectic

Dialectic or dialectics (Greek: διαλεκτική, dialektikḗ; related to dialogue), also known as the dialectical method, is at base a discourse between two or more people holding different points of view about a subject but wishing to establish the truth through reasoned arguments. Dialectic resembles debate, but the concept excludes subjective elements such as emotional appeal and the modern pejorative sense of rhetoric. Dialectic may be contrasted with the didactic method, wherein one side of the conversation teaches the other. Dialectic is alternatively known as minor logic, as opposed to major logic or critique.

Within Hegelianism, the word dialectic has the specialised meaning of a contradiction between ideas that serves as the determining factor in their relationship. Dialectic comprises three stages of development: first, a thesis or statement of an idea, which gives rise to a second step, a reaction or antithesis that contradicts or negates the thesis, and third, the synthesis, a statement through which the differences between the two points are resolved. Dialectical materialism, a theory or set of theories produced mainly by Karl Marx and Friedrich Engels, adapted the Hegelian dialectic into arguments regarding traditional materialism.

Dialectic tends to imply a process of evolution and so does not naturally fit within formal logic (see logic and dialectic). This process is particularly marked in Hegelian dialectic and even more so in Marxist dialectic which may rely on the evolution of ideas over longer time periods in the real world; dialectical logic attempts to address this.

Double negation

In propositional logic, double negation is the theorem that states that "If a statement is true, then it is not the case that the statement is not true." This is expressed by saying that a proposition A is logically equivalent to not (not-A), or by the formula A ≡ ~(~A) where the sign ≡ expresses logical equivalence and the sign ~ expresses negation.

Like the law of the excluded middle, this principle is considered to be a law of thought in classical logic, but it is disallowed by intuitionistic logic. The principle was stated as a theorem of propositional logic by Russell and Whitehead in Principia Mathematica as:

"This is the principle of double negation, i.e. a proposition is equivalent of the falsehood of its negation."
Double negative

A double negative is a grammatical construction occurring when two forms of negation are used in the same sentence. Multiple negation is the more general term referring to the occurrence of more than one negative in a clause. In some languages, double negatives cancel one another and produce an affirmative; in other languages, doubled negatives intensify the negation. Languages where multiple negatives affirm each other are said to have negative concord or emphatic negation. Portuguese, Persian, Russian, Spanish, Neapolitan, Italian, Japanese, Bulgarian, Czech, Polish, Afrikaans, Hebrew, Ukrainian, and some dialects of English, such as African-American Vernacular English, are examples of negative-concord languages, while Latin and German do not have negative concord. It is cross-linguistically observed that negative-concord languages are more common than those without.Languages without negative concord typically have negative polarity items that are used in place of additional negatives when another negating word already occurs. Examples are "ever", "anything" and "anyone" in the sentence "I haven't ever owed anything to anyone" (cf. "I haven't never owed nothing to no one" in negative-concord dialects of English, and "Nunca devi nada a ninguém" in Portuguese, lit. "Never have I owed nothing to no one", or "Non ho mai dovuto nulla a nessuno" in Italian). Note that negative polarity can be triggered not only by direct negatives such as "not" or "never", but also by words such as "doubt" or "hardly" ("I doubt he has ever owed anything to anyone" or "He has hardly ever owed anything to anyone").

Stylistically, in English, double negatives can sometimes be used for affirmation (e.g. "I'm not feeling not good"), an understatement of the positive ("I'm feeling good"). The rhetorical term for this is litotes.

Double tilde

Double tilde may refer to:

Approximation

Double negation

Existential quantification

In predicate logic, an existential quantification is a type of quantifier, a logical constant which is interpreted as "there exists", "there is at least one", or "for some". Some sources use the term existentialization to refer to existential quantification. It is usually denoted by the logical operator symbol ∃, which, when used together with a predicate variable, is called an existential quantifier ("∃x" or "∃(x)"). Existential quantification is distinct from universal quantification ("for all"), which asserts that the property or relation holds for all members of the domain.

False (logic)

In logic, false or untrue is the state of possessing negative truth value or a nullary logical connective. In a truth-functional system of propositional logic it is one of two postulated truth values, along with its negation, truth. Usual notations of the false are 0 (especially in Boolean logic and computer science), O (in prefix notation, Opq), and the up tack symbol ⊥.Another approach is used for several formal theories (for example, intuitionistic propositional calculus) where the false is a propositional constant (i.e. a nullary connective) ⊥, the truth value of this constant being always false in the sense above.

Intuitionistic logic

Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems of intuitionistic logic do not include the law of the excluded middle and double negation elimination, which are fundamental inference rules in classical logic. Intuitionistic logic is one example of a logic in a family of non-classical logics called paracomplete logics: logics that refuse to tautologically affirm the law of the excluded middle.

Formalized intuitionistic logic was originally developed by Arend Heyting to provide a formal basis for Brouwer's programme of intuitionism. From a proof-theoretic perspective, Heyting’s calculus is a restriction of classical logic in which the law of excluded middle and double negation elimination have been removed. Excluded middle and double negation elimination can still be proved for some propositions on a case by case basis, however, but do not hold universally as they do with classical logic.

Several systems of semantics for intuitionistic logic have been studied. One of these semantics mirrors classical Boolean-valued semantics but uses Heyting algebras in place of Boolean algebras. Another semantics uses Kripke models. These, however, are technical means for studying Heyting’s deductive system rather than formalizations of Brouwer’s original informal semantic intuitions. Semantical systems claiming to capture such intuitions, due to offering meaningful concepts of “constructive truth” (rather than merely validity or provability), are Gödel’s dialectica interpretation, Kleene’s realizability, Medvedev’s logic of finite problems, or Japaridze’s computability logic. Yet such semantics persistently induce logics properly stronger than Heyting’s logic. Some authors have argued that this might be an indication of inadequacy of Heyting’s calculus itself, deeming the latter incomplete as a constructive logic.

Kokota language

Kokota is an Austronesian language spoken by perhaps as many as 1,200 people in three villages on Santa Isabel in the Solomon Islands. These villages are, the villages of Goveo and Sisiga, which lie on the north coast, and Hurepelo which lies on the south coast. People in all three villages use the language daily, but may eventually shift to neighboring Cheke Holo to the west, a language spoken by many more people who have recently settled between Goveo and Sisiga (Palmer 2009:1–2).

Law of excluded middle

In logic, the law of excluded middle (or the principle of excluded middle) states that for any proposition, either that proposition is true or its negation is true. It is one of the so called three laws of thought, along with the law of noncontradiction, and the law of identity. The law of excluded middle is logically equivalent to the law of noncontradiction by De Morgan's laws. However, no system of logic is built on just these laws, and none of these laws provide inference rules, such as modus ponens or De Morgan's laws.

The law is also known as the law (or principle) of the excluded third, in Latin principium tertii exclusi. Another Latin designation for this law is tertium non datur: "no third [possibility] is given". It is a tautology.

The principle should not be confused with the semantical principle of bivalence, which states that every proposition is either true or false.

Logical connective

In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a symbol or word used to connect two or more sentences (of either a formal or a natural language) in a grammatically valid way, such that the value of the compound sentence produced depends only on that of the original sentences and on the meaning of the connective.

The most common logical connectives are binary connectives (also called dyadic connectives) which join two sentences which can be thought of as the function's operands. Also commonly, negation is considered to be a unary connective.

Logical connectives along with quantifiers are the two main types of logical constants used in formal systems such as propositional logic and predicate logic. Semantics of a logical connective is often, but not always, presented as a truth function.

A logical connective is similar to but not equivalent to a conditional operator.

Mu (negative)

The Japanese and Korean term mu (Japanese: 無; Korean: 무) or Chinese wu (traditional Chinese: 無; simplified Chinese: 无), meaning "not have; without", is a key word in Buddhism, especially Zen traditions.

Negation of the Diaspora

The negation of the Diaspora (Hebrew: שלילת הגלות‎, shlilat ha'galut, or Hebrew: שלילת הגולה‎, shlilat ha'golah) is a central assumption in many currents of Zionism. The concept encourages the dedication to Zionism and it is used to justify the denial of the feasibility of Jewish emancipation in the Diaspora. Life in the Diaspora would either lead to discrimination and persecution or to national decadence and assimilation. A more moderate formulation says that the Jews as a people have no future without a "spiritual center" in the Land of Israel.

Tautology (logic)

In logic, a tautology (from the Greek word ταυτολογία) is a formula or assertion that is true in every possible interpretation. A simple example is "(x equals y) or (x does not equal y)" (or as a less abstract example, "The ball is green or the ball is not green").

Philosopher Ludwig Wittgenstein first applied the term to redundancies of propositional logic in 1921. (It had been used earlier to refer to rhetorical tautologies, and continues to be used in that alternative sense.) A formula is satisfiable if it is true under at least one interpretation, and thus a tautology is a formula whose negation is unsatisfiable. Unsatisfiable statements, both through negation and affirmation, are known formally as contradictions. A formula that is neither a tautology nor a contradiction is said to be logically contingent. Such a formula can be made either true or false based on the values assigned to its propositional variables. The double turnstile notation is used to indicate that S is a tautology. Tautology is sometimes symbolized by "Vpq", and contradiction by "Opq". The tee symbol is sometimes used to denote an arbitrary tautology, with the dual symbol (falsum) representing an arbitrary contradiction; in any symbolism, a tautology may be substituted for the truth value "true," as symbolized, for instance, by "1."

Tautologies are a key concept in propositional logic, where a tautology is defined as a propositional formula that is true under any possible Boolean valuation of its propositional variables. A key property of tautologies in propositional logic is that an effective method exists for testing whether a given formula is always satisfied (or, equivalently, whether its negation is unsatisfiable).

The definition of tautology can be extended to sentences in predicate logic, which may contain quantifiers, unlike sentences of propositional logic. In propositional logic, there is no distinction between a tautology and a logically valid formula. In the context of predicate logic, many authors define a tautology to be a sentence that can be obtained by taking a tautology of propositional logic and uniformly replacing each propositional variable by a first-order formula (one formula per propositional variable). The set of such formulas is a proper subset of the set of logically valid sentences of predicate logic (which are the sentences that are true in every model).

This page is based on a Wikipedia article written by authors (here).
Text is available under the CC BY-SA 3.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.