Inlogic andmathematics,necessity andsufficiency are terms used to describe aconditional or implicational relationship between twostatements. For example, in theconditional statement: "IfP thenQ",Q isnecessary forP, because thetruth ofQ is "necessarily" guaranteed by the truth ofP. (Equivalently, it is impossible to haveP withoutQ, or the falsity ofQ ensures the falsity ofP.)[1] Similarly,P issufficient forQ, becauseP being true always or "sufficiently" implies thatQ is true, butP not being true does not always imply thatQ is not true.[2]
In general, a necessary condition is one (possibly one of several conditions) that must be present in order for another condition to occur, while a sufficient condition is one that produces the said condition.[3] The assertion that a statement is a "necessaryand sufficient" condition of another means that the former statement is trueif and only if the latter is true. That is, the two statements must be either simultaneously true, or simultaneously false.[4][5][6]
Inordinary English (alsonatural language) "necessary" and "sufficient" often indicate relations between conditions or states of affairs, not statements. For example, being round is a necessary condition for being a circle, but is not sufficient since ovals and ellipses are round but not circles – while being a circle is a sufficient condition for being round. Any conditional statement consists of at least one sufficient condition and at least one necessary condition.
Indata analytics, necessity and sufficiency can refer to differentcausal logics,[7] wherenecessary condition analysis andqualitative comparative analysis can be used as analytical techniques for examining necessity and sufficiency of conditions for a particular outcome of interest.
In the conditional statement, "ifS, thenN", the expression represented byS is called theantecedent, and the expression represented byN is called theconsequent. This conditional statement may be written in several equivalent ways, such as "N ifS", "S only ifN", "S impliesN", "N is implied byS",S →N,S ⇒N and "N wheneverS".[8]
In the above situation of "N whenever S",N is said to be anecessary condition forS. In common language, this is equivalent to saying that if the conditional statement is a true statement, then the consequentNmust be true—ifS is to be true (see third column of "truth table" immediately below). In other words, the antecedentS cannot be true withoutN being true. For example, in order for someone to be calledSocrates, it is necessary for that someone to beNamed. Similarly, in order for human beings to live, it is necessary that they have air.[9]
One can also sayS is asufficient condition forN (refer again to the third column of the truth table immediately below). If the conditional statement is true, then ifS is true,N must be true; whereas if the conditional statement is true and N is true, then S may be true or be false. In common terms, "the truth ofS guarantees the truth ofN".[9] For example, carrying on from the previous example, one can say that knowing that someone is calledSocrates is sufficient to know that someone has aName.
Anecessary and sufficient condition requires that both of the implications and (the latter of which can also be written as) hold. The first implication suggests thatS is a sufficient condition forN, while the second implication suggests thatS is a necessary condition forN. This is expressed as "S is necessary and sufficient forN ", "Sif and only ifN", or.
| S | N | |||
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | T | F | F |
| F | F | T | T | T |
The assertion thatQ is necessary forP is colloquially equivalent to "P cannot be true unlessQ is true" or "if Q is false, then P is false".[9][1] Bycontraposition, this is the same thing as "wheneverP is true, so isQ".
The logical relation betweenP andQ is expressed as "ifP, thenQ" and denoted "P ⇒Q" (PimpliesQ). It may also be expressed as any of "P only ifQ", "Q, ifP", "Q wheneverP", and "Q whenP". One often finds, in mathematical prose for instance, several necessary conditions that, taken together, constitute a sufficient condition (i.e., individually necessary and jointly sufficient[9]), as shown in Example 5.
IfP is sufficient forQ, then knowingP to be true is adequate grounds to conclude thatQ is true; however, knowingP to be false does not meet a minimal need to conclude thatQ is false.
The logical relation is, as before, expressed as "ifP, thenQ" or "P ⇒Q". This can also be expressed as "P only ifQ", "P impliesQ" or several other variants. It may be the case that several sufficient conditions, when taken together, constitute a single necessary condition (i.e., individually sufficient and jointly necessary), as illustrated in example 5.
A condition can be either necessary or sufficient without being the other. For instance,being amammal (N) is necessary but not sufficient tobeing human (S), and that a numberis rational (S) is sufficient but not necessary tobeing areal number (N) (since there are real numbers that are not rational).
A condition can be both necessary and sufficient. For example, at present, "today is theFourth of July" is a necessary and sufficient condition for "today isIndependence Day in theUnited States". Similarly, a necessary and sufficient condition forinvertibility of amatrixM is thatM has a nonzerodeterminant.
Mathematically speaking, necessity and sufficiency aredual to one another. For any statementsS andN, the assertion that "N is necessary forS" is equivalent to the assertion that "S is sufficient forN". Another facet of this duality is that, as illustrated above, conjunctions (using "and") of necessary conditions may achieve sufficiency, while disjunctions (using "or") of sufficient conditions may achieve necessity. For a third facet, identify every mathematicalpredicateN with the setT(N) of objects, events, or statements for whichN holds true; then asserting the necessity ofN forS is equivalent to claiming thatT(N) is asuperset ofT(S), while asserting the sufficiency ofS forN is equivalent to claiming thatT(S) is asubset ofT(N).
Psychologically speaking, necessity and sufficiency are both key aspects of the classical view of concepts. Under the classical theory of concepts, how human minds represent a category X, gives rise to a set of individually necessary conditions that define X. Together, these individually necessary conditions are sufficient to be X.[10] This contrasts with the probabilistic theory of concepts which states that no defining feature is necessary or sufficient, rather that categories resemble a family tree structure.
To say thatP is necessary and sufficient forQ is to say two things:
One may summarize any, and thus all, of these cases by the statement "Pif and only ifQ", which is denoted by, whereas cases tell us that is identical to.
For example, ingraph theory a graphG is calledbipartite if it is possible to assign to each of its vertices the colorblack orwhite in such a way that every edge ofG has one endpoint of each color. And for any graph to be bipartite, it is a necessary and sufficient condition that it contain no odd-lengthcycles. Thus, discovering whether a graph has any odd cycles tells one whether it is bipartite and conversely. A philosopher[11] might characterize this state of affairs thus: "Although the concepts of bipartiteness and absence of odd cycles differ inintension, they have identicalextension.[12]
In mathematics, theorems are often stated in the form "P is true if and only ifQ is true".
Because, as explained in previous section, necessity of one for the other is equivalent to sufficiency of the other for the first one, e.g. isequivalent to, ifP is necessary and sufficient forQ, thenQ is necessary and sufficient forP. We can write and say that the statements "P is trueif and only ifQ, is true" and "Q is true if and only ifP is true" are equivalent.
| Major fields |
| ||||
|---|---|---|---|---|---|
| Foundations | |||||
| Lists |
| ||||
