Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Negation

From Wikipedia, the free encyclopedia
Logical operation
For negation in linguistics, seeAffirmation and negation. For other uses, seeNegation (disambiguation).

Negation
NOT
Venn diagram of Negation
Definition¬x{\displaystyle \lnot {x}}
Truth table(01){\displaystyle (01)}
Logic gate
Normal forms
Disjunctive¬x{\displaystyle \lnot {x}}
Conjunctive¬x{\displaystyle \lnot {x}}
Zhegalkin polynomial1⊕x{\displaystyle 1\oplus x}
Post's lattices
0-preservingno
1-preservingno
Monotoneno
Affineyes
Self-dualyes
Logical connectives
NOT¬A,−A,A¯,∼A{\displaystyle \neg A,-A,{\overline {A}},{\sim }A}
ANDA∧B,A⋅B,AB,A&⁡B,A&&⁡B{\displaystyle A\land B,A\cdot B,AB,A\mathop {\&} B,A\mathop {\&\&} B}
NANDA∧¯B,A↑B,A∣B,A⋅B¯{\displaystyle A\mathrel {\overline {\land }} B,A\uparrow B,A\mid B,{\overline {A\cdot B}}}
ORA∨B,A+B,A∣B,A∥B{\displaystyle A\lor B,A+B,A\mid B,A\parallel B}
NORA∨¯B,A↓B,A+B¯{\displaystyle A\mathrel {\overline {\lor }} B,A\downarrow B,{\overline {A+B}}}
XNORA⊙B,A∨¯B¯{\displaystyle A\odot B,{\overline {A\mathrel {\overline {\lor }} B}}}
└equivalentA≡B,A⇔B,A⇋B{\displaystyle A\equiv B,A\Leftrightarrow B,A\leftrightharpoons B}
XORA∨_B,A⊕B{\displaystyle A\mathrel {\underline {\lor }} B,A\oplus B}
└ nonequivalentA≢B,A⇎B,A↮B{\displaystyle A\not \equiv B,A\not \Leftrightarrow B,A\nleftrightarrow B}
impliesA⇒B,A⊃B,A→B{\displaystyle A\Rightarrow B,A\supset B,A\rightarrow B}
nonimplication (NIMPLY)A⇏B,A⊅B,A↛B{\displaystyle A\not \Rightarrow B,A\not \supset B,A\nrightarrow B}
converseA⇐B,A⊂B,A←B{\displaystyle A\Leftarrow B,A\subset B,A\leftarrow B}
converse nonimplicationA⇍B,A⊄B,A↚B{\displaystyle A\not \Leftarrow B,A\not \subset B,A\nleftarrow B}
Related concepts
Applications
Category

Inlogic,negation, also called thelogical not orlogical complement, is anoperation that takes apropositionP{\displaystyle P} to another proposition "notP{\displaystyle P}", written¬P{\displaystyle \neg P},∼P{\displaystyle {\mathord {\sim }}P},P′{\displaystyle P^{\prime }}[1] orP¯{\displaystyle {\overline {P}}}.[citation needed] It is interpreted intuitively as being true whenP{\displaystyle P} is false, and false whenP{\displaystyle P} is true.[2][3] For example, ifP{\displaystyle P} is "The dog runs", then "notP{\displaystyle P}" is "The dog does not run". An operand of a negation is called anegand ornegatum.[4]

Negation is aunarylogical connective. It may furthermore be applied not only to propositions, but also tonotions,truth values, orsemantic values more generally. Inclassical logic, negation is normally identified with thetruth function that takestruth tofalsity (and vice versa). Inintuitionistic logic, according to theBrouwer–Heyting–Kolmogorov interpretation, the negation of a propositionP{\displaystyle P} is the proposition whose proofs are the refutations ofP{\displaystyle P}.

Definition

[edit]

Classical negation is anoperation on onelogical value, typically the value of aproposition, that produces a value oftrue when its operand is false, and a value offalse when its operand is true. Thus if statementP{\displaystyle P} is true, then¬P{\displaystyle \neg P} (pronounced "not P") would then be false; and conversely, if¬P{\displaystyle \neg P} is true, thenP{\displaystyle P} would be false.

Thetruth table of¬P{\displaystyle \neg P} is as follows:

P{\displaystyle P}¬P{\displaystyle \neg P}
TrueFalse
FalseTrue

Negation can be defined in terms of other logical operations. For example,¬P{\displaystyle \neg P} can be defined asP→⊥{\displaystyle P\rightarrow \bot } (where→{\displaystyle \rightarrow } islogical consequence and⊥{\displaystyle \bot } isabsolute falsehood). Conversely, one can define⊥{\displaystyle \bot } asQ∧¬Q{\displaystyle Q\land \neg Q} for any propositionQ (where∧{\displaystyle \land } islogical conjunction). The idea here is that anycontradiction is false, and while these ideas work in both classical and intuitionistic logic, they do not work inparaconsistent 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.

Algebraically, classical negation corresponds tocomplementation in aBoolean algebra, and intuitionistic negation to pseudocomplementation in aHeyting algebra. These algebras provide asemantics for classical and intuitionistic logic.

Notation

[edit]

The negation of a propositionp is notated in different ways, in various contexts of discussion and fields of application. The following table documents some of these variants:

NotationPlain textVocalization
¬p{\displaystyle \neg p}¬p ,7p[5]Notp
∼p{\displaystyle {\mathord {\sim }}p}~pNotp
−p{\displaystyle -p}-pNotp
Np{\displaystyle Np}Enp
p′{\displaystyle p'}p'
  • p prime,
  • p complement
p¯{\displaystyle {\overline {p}}} ̅p
  • p bar,
  • Barp
!p{\displaystyle !p}!p
  • Bangp
  • Notp

The notationNp{\displaystyle Np} isPolish notation.

Inset theory,∖{\displaystyle \setminus } is also used to indicate 'not in the set of':U∖A{\displaystyle U\setminus A} is the set of all members ofU that are not members ofA.

Regardless how it is notated orsymbolized, the negation¬P{\displaystyle \neg P} can be read as "it is not the case thatP", "not thatP", or usually more simply as "notP".

Precedence

[edit]
See also:Logical connective § Order of precedence

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

Here is a table that shows a commonly used precedence of logical operators.[6]

OperatorPrecedence
¬{\displaystyle \neg }1
∧{\displaystyle \land }2
∨{\displaystyle \lor }3
→{\displaystyle \to }4
↔{\displaystyle \leftrightarrow }5

Properties

[edit]

Double negation

[edit]

Within a system ofclassical logic, double negation, that is, the negation of the negation of a propositionP{\displaystyle P}, islogically equivalent toP{\displaystyle P}. Expressed in symbolic terms,¬¬P≡P{\displaystyle \neg \neg P\equiv P}. Inintuitionistic 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 aninvolution of period two.

However, inintuitionistic logic, the weaker equivalence¬¬¬P≡¬P{\displaystyle \neg \neg \neg P\equiv \neg P} does hold. This is because in intuitionistic logic,¬P{\displaystyle \neg P} is just a shorthand forP→⊥{\displaystyle P\rightarrow \bot }, and we also haveP→¬¬P{\displaystyle P\rightarrow \neg \neg P}. Composing that last implication with triple negation¬¬P→⊥{\displaystyle \neg \neg P\rightarrow \bot } implies thatP→⊥{\displaystyle P\rightarrow \bot } .

As a result, in the propositional case, a sentence is classically provable if its double negation is intuitionistically provable. This result is known asGlivenko's theorem.

Distributivity

[edit]

De Morgan's laws provide a way ofdistributing negation overdisjunction andconjunction:

¬(P∨Q)≡(¬P∧¬Q){\displaystyle \neg (P\lor Q)\equiv (\neg P\land \neg Q)},  and
¬(P∧Q)≡(¬P∨¬Q){\displaystyle \neg (P\land Q)\equiv (\neg P\lor \neg Q)}.

Linearity

[edit]

Let⊕{\displaystyle \oplus } denote the logicalxor operation. InBoolean algebra, a linear function is one such that:

If there existsa0,a1,…,an∈{0,1}{\displaystyle a_{0},a_{1},\dots ,a_{n}\in \{0,1\}},f(b1,b2,…,bn)=a0⊕(a1∧b1)⊕⋯⊕(an∧bn){\displaystyle f(b_{1},b_{2},\dots ,b_{n})=a_{0}\oplus (a_{1}\land b_{1})\oplus \dots \oplus (a_{n}\land b_{n})},for allb1,b2,…,bn∈{0,1}{\displaystyle b_{1},b_{2},\dots ,b_{n}\in \{0,1\}}.

Another way to express this is that each variable always makes a difference in thetruth-value of the operation, or it never makes a difference. Negation is a linear logical operator.

Self dual

[edit]

InBoolean algebra, a self dual function is a function such that:

f(a1,…,an)=¬f(¬a1,…,¬an){\displaystyle f(a_{1},\dots ,a_{n})=\neg f(\neg a_{1},\dots ,\neg a_{n})} for alla1,…,an∈{0,1}{\displaystyle a_{1},\dots ,a_{n}\in \{0,1\}}.Negation is a self dual logical operator.

Negations of quantifiers

[edit]

Infirst-order logic, there are two quantifiers, one is the universal quantifier∀{\displaystyle \forall } (means "for all") and the other is the existential quantifier∃{\displaystyle \exists } (means "there exists"). The negation of one quantifier is the other quantifier (¬∀xP(x)≡∃x¬P(x){\displaystyle \neg \forall xP(x)\equiv \exists x\neg P(x)} and¬∃xP(x)≡∀x¬P(x){\displaystyle \neg \exists xP(x)\equiv \forall x\neg P(x)}). For example, with the predicateP as "x is mortal" and the domain of x as the collection of all humans,∀xP(x){\displaystyle \forall xP(x)} means "a person x in all humans is mortal" or "all humans are mortal". The negation of it is¬∀xP(x)≡∃x¬P(x){\displaystyle \neg \forall xP(x)\equiv \exists x\neg P(x)}, meaning "there exists a personx in all humans who is not mortal", or "there exists someone who lives forever".

Rules of inference

[edit]
See also:Double negation

There are a number of equivalent ways to formulate rules for negation. One usual way to formulate classical negation in anatural deduction setting is to take as primitive rules of inferencenegation introduction (from a derivation ofP{\displaystyle P} to bothQ{\displaystyle Q} and¬Q{\displaystyle \neg Q}, infer¬P{\displaystyle \neg P}; this rule also being calledreductio ad absurdum),negation elimination (fromP{\displaystyle P} and¬P{\displaystyle \neg P} inferQ{\displaystyle Q}; this rule also being calledex falso quodlibet), anddouble negation elimination (from¬¬P{\displaystyle \neg \neg P} inferP{\displaystyle 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 fromP{\displaystyle P} thenP{\displaystyle P} must not be the case (i.e.P{\displaystyle 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⊥{\displaystyle \bot }. In this case the rule says that fromP{\displaystyle P} and¬P{\displaystyle \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¬P{\displaystyle \neg P} ofP{\displaystyle P} is defined asP→⊥{\displaystyle P\rightarrow \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 ruleex falso quodlibet.

Programming language and ordinary language

[edit]

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

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

Theexclamation mark "!" signifies logical NOT inB,C, and languages with a C-inspired syntax such asC++,Java,JavaScript,Perl, andPHP. "NOT" is the operator used inALGOL 60,BASIC, and languages with an ALGOL- or BASIC-inspired syntax such asPascal,Ada, andEiffel. Some languages (C++, Perl, etc.) provide more than one operator for negation. A few languages likePL/I andRatfor use¬ for negation. Most modern languages allow the above statement to be shortened fromif (!(r == t)) toif (r != t), which allows sometimes, when the compiler/interpreter is not able to optimize it, faster programs.

In computer science there is alsobitwise negation. This takes the value given and switches all thebinary 1s to 0s and 0s to 1s. This is often used to createones' complement (or "~" in C or C++) andtwo's complement (just simplified to "-" or thenegative sign, as this is equivalent to taking thearithmetic 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)

unsignedintabs(intx){if(x<0)return-x;elsereturnx;}

To demonstrate logical negation:

unsignedintabs(intx){if(!(x<0))returnx;elsereturn-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 anidiom to convertx 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.[7]

Usage in colloquial language

[edit]
For use of "!vote" in Wikipedia, seeWikipedia § Dispute resolution, andWikipedia:Polling is not a substitute for discussion § Not-votes.

The convention of using! to signify negation occasionally surfaces incolloquial language, as computer-relatedslang fornot. For example, the phrase!clue is used as a synonym for "no-clue" or "clueless".[8][9]

Another example is the expression!vote which means "not a vote".[10] In this context, the exclamation mark is used atWikipedia to survey opinions while negating "majority rule", in order "to have a consensus-building discussion, where the proper course is determined by the strength of the respective arguments."[10]

Kripke semantics

[edit]

InKripke semantics where the semantic values of formulae are sets ofpossible worlds, negation can be taken to meanset-theoretic complementation[citation needed] (see alsopossible world semantics for more).

See also

[edit]

References

[edit]
  1. ^Virtually all Turkish high school math textbooks use p' for negation due to the books handed out by the Ministry of National Education representing it as p'.
  2. ^Weisstein, Eric W."Negation".mathworld.wolfram.com. Retrieved2 September 2020.
  3. ^"Logic and Mathematical Statements - Worked Examples".www.math.toronto.edu. Retrieved2 September 2020.
  4. ^Beall, Jeffrey C. (2010).Logic: the basics (1. publ ed.). London: Routledge. p. 57.ISBN 978-0-203-85155-5.
  5. ^Used as makeshift in early typewriter publications, e.g.Richard E. Ladner (January 1975). "The circuit value problem is log space complete for P".ACM SIGACT News.7 (101):18–20.doi:10.1145/990518.990519.
  6. ^O'Donnell, John; Hall, Cordelia; Page, Rex (2007),Discrete Mathematics Using a Computer, Springer, p. 120,ISBN 9781846285981.
  7. ^Egan, David."Double Negation Operator Convert to Boolean in C".Dev Notes.
  8. ^Raymond, Eric and Steele, Guy.The New Hacker's Dictionary, p. 18 (MIT Press 1996).
  9. ^Munat, Judith.Lexical Creativity, Texts and Context, p. 148 (John Benjamins Publishing, 2007).
  10. ^abHarrison, Stephen. "Wikipedia's War on the Daily Mail",Slate Magazine (July 1, 2021).

Further reading

[edit]

External links

[edit]
Tables of Truth of composite clauses
Central concepts
Topics
Areas
Phenomena
Formalism
Formal systems
Concepts
See also
General
Theorems (list)
 and paradoxes
Logics
Traditional
Propositional
Predicate
Set theory
Types ofsets
Maps and cardinality
Set theories
Formal systems (list),
language and syntax
Example axiomatic
systems (list)
Proof theory
Model theory
Computability theory
Related
Authority control databasesEdit this at Wikidata
Retrieved from "https://en.wikipedia.org/w/index.php?title=Negation&oldid=1317323053"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp