This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0000169319 Reproduction Date:
In logic, necessity and sufficiency are implicational relationships between statements. The assertion that one statement is a necessary and sufficient condition of another means that the former statement is true if and only if the latter is true. That is, the two statements must be either simultaneously true or simultaneously false.^{[1]}^{[2]}^{[3]} In ordinary English, 'necessary' and 'sufficient' indicate relations between conditions or states of affairs, not statements. Being a male sibling is a necessary and sufficient condition for being a brother. Fred's being a male sibling is necessary and sufficient for the truth of the statement that Fred is a brother.
A true necessary condition in a conditional statement makes the statement true (see "truth table" immediately below). In formal terms, a consequent N is a necessary condition for an antecedent S, in the conditional statement, "N if S ", "N is implied by S ", or N \Leftarrow S. In common words, we would also say "N is weaker than S " or "S cannot occur without N ". For example, it is necessary to be Named, to be called "Socrates".
A true sufficient condition in a conditional statement ties the statement's truth to its consequent. In formal terms, an antecedent S is a sufficient condition for a consequent N, in the conditional statement, "if S, then N ", "S implies N ", or S \Rightarrow N. In common words, we would also say "S is stronger than N " or "S guarantees N ". For example, "Socrates" suffices for a Name.
A necessary and sufficient condition requires both of these implications (S \Rightarrow N and N \Rightarrow S) to hold. Using the previous statement, this is expressed as "S is necessary and sufficient for N ", "S if and only if N ", or S \Leftrightarrow N.
The assertion that Q is necessary for P is colloquially equivalent to "P cannot be true unless Q is true," or "if Q is false then P is false." By contraposition, this is the same thing as "whenever P is true, so is Q ". The logical relation between them is expressed as "If P then Q " and denoted "P \Rightarrow Q " (P implies Q), and may also be expressed as any of "Q, if P "; "Q whenever P "; and "Q when P." One often finds, in mathematical prose for instance, several necessary conditions that, taken together, constitute a sufficient condition, as shown in Example 5.
To say that P is sufficient for Q is to say that, in and of itself, knowing P to be true is adequate grounds to conclude that Q is true. (However, knowing P not to be true does not, in and of itself, provide adequate grounds to conclude that Q is not true.) The logical relation is expressed as "If P then Q " or "P \Rightarrow Q," and may also be expressed as "P implies Q." Several sufficient conditions may, taken together, constitute a single necessary condition, as illustrated in example 5.
A condition can be either necessary or sufficient without being the other. For instance, being a mammal (N) is necessary but not sufficient to being human (S), and that a number x is rational (S) is sufficient but not necessary to x's being a real 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 the Fourth of July" is a necessary and sufficient condition for "today is Independence Day in the United States." Similarly, a necessary and sufficient condition for invertibility of a matrix M is that M has a nonzero determinant.
Mathematically speaking, necessity and sufficiency are dual to one another. For any statements S and N, the assertion that "N is necessary for S " is equivalent to the assertion that "S is sufficient for N." 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 mathematical predicate N with the set T(N) of objects, events, or statements for which N holds true; then asserting the necessity of N for S is equivalent to claiming that T(N) is a superset of T(S), while asserting the sufficiency of S for N is equivalent to claiming that T(S) is a subset of T(N).
To say that P is necessary and sufficient for Q is to say two things, that P is necessary for Q and that P is sufficient for Q. Of course, it may instead be understood to say a different two things, namely that each of P and Q is necessary for the other. And it may be understood in a third equivalent way: as saying that each is sufficient for the other. One may summarize any—and thus all—of these cases by the statement "P if and only if Q," which is denoted by P \Leftrightarrow Q.
For example, in graph theory a graph G is called bipartite if it is possible to assign to each of its vertices the color black or white in such a way that every edge of G 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-length cycles. Thus, discovering whether a graph has any odd cycles tells one whether it is bipartite and vice versa. A philosopher^{[4]} might characterize this state of affairs thus: "Although the concepts of bipartiteness and absence of odd cycles differ in intension, they have identical extension.^{[5]}
If P is necessary and sufficient for Q, then Q is necessary and sufficient for P, because necessity of one for the other is equivalent to sufficiency of the other for the first one. Both of these statements (that one of P or Q is necessary and sufficient for the other) are equivalent to both of the statements "P is true if and only if Q is true" and "Q is true if and only if P is true".
Epistemology, Computer science, Philosophy, Aesthetics, Metaphysics
Logic, Logical truth, Mathematical logic, Set theory, Philosophical logic
Axiom of choice, Mathematical logic, Category theory, Mathematics, Foundations of mathematics
Philosophy, Metaphysics, Psychology, Logic, Philosophy of mind
Logic, Rhetoric, Classical logic, Truth, Non-classical logic
Logic, Linguistics, Language, Noam Chomsky, Bertrand Russell